一、单项选择题(每小题2分，共20分)
1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )
A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构
2.在长度为n的顺序表的第i (1≤i≤n+1)个位置上删除一个元素，元素的移动次数为( ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )
A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为( ) A.4 B.5 C.6 D.7 5.已给下图1，哪一项是该图的拓扑排序序列 ① （ ） ② ③
④ ⑤
(图1)
A．1，2，3，4，5 B．1，3，2，4，5 C．1，2，4，3，5 D．1，2，3，5，4 6. 一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归并后的结果为( )。
A.12,38,25,35,50,74,63,90 B.12,38,35,25,74,50,63,90 C.12,25,35,38,50,74,63,90 D.12,35,38,25,63,50,74,90 7.n个顶点的有向图中含有向边的数目最多为 ( )
A.n-1 B.n C.n(n-1)/2 D.n(n-1)
8.AVL树是一种平衡的二叉排序树，树中任一结点的( )
A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 9.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 10. 二叉树的第k层的结点数最多为( ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
二、填空题(每空1分，共10分)
1. 存储结构是逻辑结构的__________实现。
2. 直接插入排序需要_________个记录的辅助空间。
3. 设二维数组A[1..10,1..20]按行优先顺序存储,每个元素占4个存储单元，A[1，1]的存储
地址是1000，则A[5，6]的存储地址是 。
4. 在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于________。 5. 在具有n个单元的循环队列中，队满时共有_________个元素。
6. 在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素24，需进行 次元素之间的比较。
7. 深度为h的完全二叉树至少有_________个结点，至多有_________个结点。
8. 在直接插入排序和快速排序中，若初始数据基本有序，则选用_________；在冒泡排序和堆
排序中，若要求数据的稳定性，则选用_________。
1
三．简答题（每小题8分，共56分）
1． 设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均
查找长度。
2． 对关键字序列(42，13，24，91，23，16，05，58)进行堆排序，使之按关键字递增次序排
列，请写出排序过程中建初始堆的过程。
3． 已知散列表长度为11，散列函数为H(key)=key％11，处理冲突的方法为拉链法，请画出依
次插入关键字（8,10,14,19,21,23,28,32,48）以后的散列表。
4． 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求：
（1）画出该二叉树；（2）写出该二叉树的先序遍历序列；（3）画出该二叉树对应的森林。 5． 以数据集（7，19，2，6，32，3，21，10）为叶结点的权值，构造一棵哈夫曼树。 6． 已给无向图如图2所示，用Prim算法画出该图从顶点1开始的最小生成树。 A 6 2 1 2 3
5 10 3 4 5 6 7 8 （图2）
７．将图3所示的二叉树转化为森林。
B D C E F H (图3)
G 四．算法题（2小题，共14分）
1．试编写算法判断两棵二叉树是否等价。若二叉树T1和T2等价，则T1和T2都是空的二叉树；或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右子树与T2的右子树是等价的。
2．统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)
2
因篇幅问题不能全部显示，请点此查看更多更全内容