1．下列各项中属于逻辑结构的有 。 

A. 哈希表 B. 有序表 C. 单链表 D. 顺序表 

2．由3个结点组成的二叉树的深度可能是 。 

A．1 B.2 C.3 D.4 

3．将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][]在B数组中的位置k等于 。 

A．198 B.197 C.196 D.195 

4．一棵满二叉树同时又是一棵 。 

A. 完全二叉树 B. 二叉排序树 C . 正则二叉树 D. 平衡二叉树 

5．长度为n的顺序表，在任何位置上插入或删除一个元素的概率相等，插入一个元素时平均移动 个元素，删除一个元素时平均移动 个元素。 

A．（n+1）/2 B.n/2 C.(n-1)/2 D.(n-2)/2 

6. 用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，入栈和出栈的操作序列可表示成仅为由s和*组成的序列。下面的序列中合法的操作序列有 。 

A．s*ss*s** B.sss**s** C. s**s*ss* D.sss*s*s* 

7. 是特殊的线性表。 

A．队列 B.哈希表 C.栈 D.判定表 

8. 表长为25的哈希表，用除留余数法公式H(key)=key % p 或H(key)=key mod p， 

则p应取 为宜。 

A.23 B.24 C.25 D.26 

9．任一个有向图的拓扑序列 。 

A.可能不存在 B.有一个 C. 一定有多个 D.有一个可多个 

10．在下列的排序方法中， 方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。 

A.快速排序 B. 冒泡排序 C.堆排序 D. 插入排序 

11．若以{4,5,6,7,8}作为权值构造Huffmen树，则该树的带权路径长度为 。 

A.67 B.68 C.69 D.70 

12．设head(L)、tail()分别为取广义表表头和表尾的操作，则从广义表L=((x,y,z),a,(u,v,w))中取出原子u的运算为 。 

A.head(tail(tail(head(L)))) B.tail(head(head(tail(L)))) 

C.head(tail(head(taill(L)))) D.head(head(tail(tail(L)))) 

二、 填空题（共32分，每空2分） 

13．在单链表中设置头结点和作用是__________________ 。 

14．线索二叉树的左线索指向其___________ ，右线索指向其___________。 

15．树在计算机内的链式存存储表示方法有___________、___________和___________。 

16．__________________ 现象称为冲突。 

17．用（A,B）的形式表示边，对图1的无向图，从项点A开始求最小生成树，用 

Prim算法产生的边依次是________________ __，用Kruskal算法产生的边依次是__________________ 。 

18．用数组a[1]..a[n]表示循环队列sq，当循环队列sq满时，队有 __________个元素。 

19．判定树常用来表示____________的 查找过程。 

20．直接插入排序、堆排序算法的时间复杂度分别是__________ 、____________ 。 

21．树根的层次是1，则深度为8的完全二叉树至少有_____________ 个结点， 拥有100个结点的完全二叉树的最大层次数是___________ 。 

22．对n个记录进行2-路归并排序，一共需要进行 _____________趟归并。 

三．简答题（47分） 

23．（6分）有5个元素，其入栈次序为A,B,C,D,E，在各种可能的出栈序列中，第一个出栈元素是C且第二个出栈元素是D的出栈序列有哪几个？ 

24．（12分）一棵树的边的集合为{ (I,M), (I,N), (E,I), (B,E), (B,D), (C,B), (G,J), (G,K), 

(A,G), (A,F), (H,L),(A,H),(C,A) }。 

（1）画出这棵树。 

（2）哪个是根结点？哪些是叶子？ 

（3）树的深度是多少？ 

（4）将此树转化为相应的二叉树。 

（5）将转化所得的二叉树进行后序穿线，建立后序线索树。 

25．（7分）用十字链表存储稀疏矩阵的非零元，画出存放非零元的结点的结构图，并说明结点中各个域中分别存放什么内容？ 

26．（12分）对n个结点的有向图，采用邻接矩阵和邻接表表示时，如何判断下列问题： 

（1）图中有多少条边？ 

（2）任意两个顶点i和j是否有边相连？ 

（3）任意一个顶点的度是多少？ 

27．（10分）依次输入序列（62, 68, 30, 61, 25, 14, 53, 47, 90, 84）中的元素，生成一棵二叉排序树。 

四．算法设计（45分，每小题15分） 

要求： ① 用C语言、类C语言 或 类Pascal语言编写算法； 

② 应对算法中使用的数据类型给出必要的说明和注释。 

28．用带头结点的循环链表作为队列的存储表示，不设头指针而只设一个尾指针rear指向队尾结点。试写了该链式队列的出队算法。 

29．二叉树采用二叉链作为存储结构，写一递归算法计算二叉树的深度。 

30．已知(r1, r2, ……, rn) 是一个小顶堆，写一算法，使得增加一个元素rn +1后(r1, r2, ……, rn，rn +1)仍是一个堆。下载本文