一、选择题(2’x10)

1. 在非空双向循环链表中q所指的结点前插入一个由p所指的链接点的过程依次为：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。

(A)rlink(q)←p (B)rlink(llink(q))←p

(C)rlink(llink(p))←p (D)rlink(rlink(p))←p

2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B 中，则在B中确定aij(i

(A) (B)
(C) (D)
3. 某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列。

(A)a，c，b，d (B)b，c，d，a

(C)c，d，b，a (D)d，c，a，b

4. 深度为h的满m叉数的第k层有_________个结点。(1≤k≤h)

(A)mk-1 (B)mk-1 (C)mh-1 (D)mh-1

5. 具有10个叶结点的二叉树中有_________个度为2的结点。

(A)8 (B)9 (C)10 (D)11

6. 要连通具有n个顶点的有向图，至少需要_________条边。

(A)n-1 (B)n (C)n+1 (D)2n

7. 已知有向图G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，
E={，，，，，，
，，}，G的拓扑序列是_________。

(A)v1，v3，v4，v6，v2，v5，v7 (B)v1，v3，v2，v6，v4，v5，v7

(C)v1，v3，v4，v5，v2，v6，v7 (D)v1，v2，v5，v3，v4，v6，v7

8. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为_________

(A) (B) (C) (D)n

9. 下面关于B树和B+树的叙述中，不正确的是_________

(A)B树和B+树都是平衡的多分树。

(B)B树和B+树都可用于文件的索引结构。

(C)B树和B+树都能有效地支持随机检索。

(D)B树和B+树都能有效地支持顺序检索。

10. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是_________。

(A)选择排序法 (B)插入排序法

(C)快速排序法 (D)堆积排序法

二、(10’)

有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。

三、(5’+10’+10’+5’)

为建立一个具有n份档案的档案库需要设计如下数据结构：所有档案存储在一个动态存储的双向循环链表中，每份档案占用一个地址连续的存储块成为该链表中的一个结点，整个链表为一个链接顺序文件，取名为dossier(档案)，同时分别建立两个索引，其中一个为稠密索引，取名为dense，另一个是表长为m的杂凑表索引，取名为bucket，该杂凑表采用链地址法处理冲突。上述两种索引中都分别存储在每一份档案的存储地址。

1. 请分别画出dossier、dense、bucket的结构示意图。

2. 分别设计出dossier、dense、bucket的数据结点的结构，即为了满足档案的插入、删除、查找的操作，每个结点必要的数据项的名称及其作用。

3. 针对上述结构，用简明的文字分别说明所有可能的查找方法(查找路径)。

4. 分别给出每一种查找方法在查找成功时的平均查找长度。

四、(10’)

已知num为无符号十进制整数，请写一非递归算法，该算法依次输出num对应的r进制的各位数字。要求算法中用到的堆栈采用线性链表存储结构。(1

五、(10’)

已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)

六、(10’x2)

设有一集合，其成员为任意类型的数据元素，基本操作为插入、删除和成员测试。若为该集合设计一个集合类型，则

1. 该集合可以采用哪几种存储结构？就存储空间开销以及操作而言，分别说明每种存储结构的特点