20 06—20 07完全二叉树算法学年第 2 学期
《 数据结构与算法 》考试试卷（A卷）
（时间120分钟）
院/系              专业            姓名              学号             
题  号
一
二
三
四
五
六
七
总分
得分
得分
一、选择题（每小题2分，共20分）
1、数据结构中，与所使用的计算机无关的是数据的            结构。
    A. 存储结构        B. 物理结构        C. 逻辑结构        D. 物理和存储结构
2、循环链表的主要优点是          。
A. 不再需要头指针了      B. 已知某个结点的位置后，能很容易到它的直接前驱结点
C. 在进行删除操作后，能保证链表不断开  D. 从表中任一结点出发都能遍历整个链表
3、栈和队列都是        。
A. 顺序存储的线性结构                  B.链式存储的非线性结构
C. 限制存取点的线性结构                D.限制存取点的非线性结构
4、串的长度是指              。
A. 串中所含不同字母的个数            B. 串中所含不同字符的个数
C. 串中所含字符的个数                  D. 串中所含非空格字符的个数
5、若某二叉树的先序和中序遍历序列分别为ABCD、ACDB，则该二叉树的后序遍历序列为        。
A. DBCA          B. ADCB          C. DCBA      D. CDBA
6、有n个叶子结点的哈夫曼树，其结点总数为        。
A．2n-1          B．2n              C．2n+1          D．不确定。
7、无向图的邻接矩阵一定是          。
A. 对角矩阵      B. 稀疏矩阵    C. 三角矩阵      D. 对称矩阵
8、以下序列中                  符合堆的定义。
A. (2,40,20,25,30)    B. (2,20,40,25,30)    C. (40,25,2,30,20)    D. (40,25,2,20,30)
9、下列排序方法中属于不稳定排序方法的是        。
A.直接插入排序        B.冒泡排序        C.快速排序      D.归并排序
10、设有一个用线性探测法解决冲突得到的散列表(或哈希表)如下图所示，散列函数为H(k)=k % 11，若要查元素14，探查的次数为        。
0
1
2
3
4
5
6
7
8
9
10
13
25
80
16
17
6
14
(第一题，第10小题图)
A.5          B.9          C.3        D.6
得分
二、填空题（每小题2分，共20分）
1、一个“好”的算法要考虑以下标准：正确性 、可读性 、                和高效率与低存储量需求。
2、对于二维数组a[0..4,0..5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,3]相对于数组空间起始地址的偏移量是                    。
3、若一棵完全二叉树共有101个结点，则该二叉树的叶子结点个数是                。
4、在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为            个。
5、适用于折半查的表的存储方式及元素排列要求为                        。
6、设顺序存储的某线性表共有123个元素，按分块查的要求等分为3块。若对索引表采用顺序查方法来确定子块，且在确定的子块中也采用顺序查方法，则在等概率的情况下，分块查成功的平均查长度为                  。
7、采用                遍历二叉排序树，可以得到一个关键字的有序序列。
8、以数据集{2,5,7,8,9}为权值构造一棵哈夫曼树，则其带权路径长度WPL为            。
9、求图的最小生成树的两种算法中，其中                  算法适合于求稀疏图的最小生成树。
10、图的深度优先搜索遍历类似于树的                  遍历。
得分
三、判断题（每小题1分，共10分）
1、顺序表结构适宜于进行顺序存取，而链表则适宜于进行随机存取。  （      ）
2、两个栈共享一片连续内存空间时，为提高内存利用效率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。    （      ）
3、栈和队列都是线性表，只是在插入和删除时受到了一些限制。      （      ）
4、空串是由空格构成的串。      （      ）
5、KMP算法的特点是在模式匹配过程中指示主串的指针不会变小或回溯。    （      ）
6、折半查法的查速度一定比顺序查法快。    （      ）
7、二叉树是度为2的有序树。        （      ）
8、完全二叉树中，若一个结点没有左孩子，则它必是树叶。      （      ）
9、迪杰斯特拉(Dijkstra)算法是按照路径长度逐步递减的次序产生最短路径的方法。  （      ）
10、有e条边的无向图，在邻接表中有e个结点。  （      ）
得分
四、应用题（每小题10分，共30分）
1、设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，并画出所对应的二叉树。
2、已知待排序的序列为(12,2，16,30,28,10,16,20,6,18)，试完成:
(1)根据以上序列，建立堆排序的初始堆(要求先输出最大值)，请画出主要过程和最后堆的结果图；
(2)输出最大值后，如何得到次大值，请画出主要过程及相应的结果图。
3、对如下所示的连通图，试分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskar)算法构造其最小生成树，并给出其构造过程。

得分
五、算法设计题（每小题10分，共20分）
1、试设计算法，对带头结点的单链表实现就地逆置，即利用原单链表中的结点的存储单元，将链表L
 
逆置为：
其中，单链表及结点定义如下：
typedef struct LNode {
        ElemType data；
        struct LNode *next；
}LNode，*LinkList；
2、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针,如下图所示)，试编写相应的入队列算法void EnQueue(Queue *Q, QElemType e)。其中队列类型定义如下：
typedef struct Node {
        ElemType data；
        struct Node *next；
}Node，*Queue；