全真试题（五）
1．数据类型是一个 集合和定义在这个集合上的 的总称。
2．算法有五个特征它们是,,可行性、输入和输出。
3．一个线性表是n个元素的 。
4．在双向链表的结点中，除了含数据元素域外，还含有 个指针域。
5．栈是限定仅在 进行插入和删除的线性表。不含元素的空表称为 。
6．对于数组来说，一旦确定了它的 和,便可以为它分配内存空间。
7．树的 包含一个数据元素及若干指向其子树的分支。
8．满二叉树是一棵深度为k且含有 个结点的二叉树。
9．在有向图G中，如果对于每一对顶点Vi和Vj（Vi≠Vj），从Vi到Vj 和从Vj到Vi都存在路径，则称G为 。
10．根据排序过程中涉及到的存储器不同，可将排序方法分为 和 。
得分
评卷人
1．单链表结点的数据元素只能是哪一种？ （ ）
A．整型 B．字符串 C．任何数据类型 D．实型
2．若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种序列不可能得到？（ ）
A．ABCDE B．EDCBA C．BAEDC D．ECDBA
3．二叉树后序遍历的次序是什么？ （ ）
A 根、左子树、右子树 B左子树、根、右子树
C 左子树、右子树、根 D根、右子树、左子树
4．已给如图二叉树，它的中序遍历是哪一项？ （ ）
A．ABECDF B．ABCDEF C．CBDAEF D．CDBFEA
5．在串的静态存储结构中，下面的哪一项不是紧缩格式的特点？ （ ）
A．节省空间 B．存取速度慢
C．存取的速度快 D．一个存取单元可能放多个字符
6．已知完全二叉树有26个结点，则整棵二叉树有多少个度为1的结点？ （ ）
A．1 B．0 C．2 D．不确定
7．已给下图，哪一项是该图的拓扑排序？ （ ）

A．1，2，3，4，5 B．1，3，2，4，5
C．1，2，4，3，5 D．1，2，3，5，4
8．在常用的哈希表处理冲突的方法中，哪一种方法容易产生“二次聚集” （ ）
A．开放定址法 B．再哈希法 C．链地址法 E．都不会产生
9．直接插入排序的算法复杂性是多少？ （ ）
A．O（n2） B,O（nlogn） C,O(n) D,O(logn)
10.串联文件的记录之间有何关系?
A 相继的两个物理记录的存储位置相邻
B．物理记录之间的次序由指针相联
C．两个逻辑相邻的记录物理上相邻
D．都不是得分
评卷人
线索二叉树拓扑排序关键路径堆排序直接存取文件
得分
评卷人
已给一个栈S，写出对S的所有操作。
以数据集{3，4，5，8，12，18}为叶结点的权值，构造一棵哈夫曼树。
已给右图写出其邻接矩阵，并画出从顶点①
开始的最小生成树。

已给输入序列{17，60，29，38，42，50}，按除留余数法，填写如下哈希表。其中除留余数法的公式如下：
H（key）=key % 11
当出现冲突时，按Hi=（H（key）+1）MOD 11 的线性探测再散列的方法进行。
地址
0
1
2
3
4
5
6
7
8
9
10
关键字
已给有8个的无序序列：{49，38，65，97，76，13，27，49}，画出建立初始堆的过程的示例图。
已给无向图如下：
要求：写出该图从顶点①
开始的广度优先和深度优先搜索
序列，并画出该图的生成树
设栈用顺序结构实现，写出表示栈的数据结构，并实现如下操作：
void push_stak(stack s,elemtp x)
void pop_stack(stack s)
2．.设用邻接矩阵表示一个有向图，编写一个算法，求一个结点的入度和出度的和。
3．设thrt是指向中序双向线索二叉树头结点的指针，写出从thrt起沿后继点进行遍历的算法。