发布时间 : 星期二 文章2006-2007第2学期数据结构与算法试卷（A卷）更新完毕开始阅读7e546621998fcc22bdd10d44
安徽大学20 06—20 07学年第 2 学期 《 数据结构与算法 》考试试卷（A卷）
（时间120分钟）
院/系 专业 姓名 学号
题 号 得
一 二 三 四 五 六 七 总分 分 一、选择题（每小题2分，共20分）
得分 1、数据结构中，与所使用的计算机无关的是数据的 结构。
A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储结构
2、循环链表的主要优点是 。
A. 不再需要头指针了 B. 已知某个结点的位置后，能很容易找到它的直接前驱结点 C. 在进行删除操作后，能保证链表不断开 D. 从表中任一结点出发都能遍历整个链表 3、栈和队列都是 。
A. 顺序存储的线性结构 C. 限制存取点的线性结构
B.链式存储的非线性结构 D.限制存取点的非线性结构
4、串的长度是指 。
A. 串中所含不同字母的个数 C. 串中所含字符的个数
B. 串中所含不同字符的个数 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 13 3 25 4 80 5 16 6 17 7 6 8 14 9 10
A.5 B.9 C.3 D.6
《 数据结构与算法 》试卷 第 1 页 共 5 页
二、填空题（每小题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个结点。 （ ）
《 数据结构与算法 》试卷 第 2 页 共 5 页
四、应用题（每小题10分，共30分）
得分 1、设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，并画出所对应的二叉树。
1 2 4 6 7 13 T2
( 第四题，第1小题图 )
9 8 3 5 T1
10 14 T3
11 12
2、已知待排序的序列为(12,2，16,30,28,10,16,20,6,18)，试完成:
(1)根据以上序列，建立堆排序的初始堆(要求先输出最大值)，请画出主要过程和最后堆的结果图； (2)输出最大值后，如何得到次大值，请画出主要过程及相应的结果图。
《 数据结构与算法 》试卷 第 3 页 共 5 页
3、对如下所示的连通图，试分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskar)算法构造其最小生成树，并给出其构造过程。
2 2 1 4 5 5 1 4 3 2 3 7 4 6 6 3 ( 第四题，第3小题图 )
《 数据结构与算法 》试卷 第 4 页 共 5 页
五、算法设计题（每小题10分，共20分）
得分
1、试设计算法，对带头结点的单链表实现就地逆置，即利用原单链表中的结点的存储单元，将链表L a1 a2 L an ^ ?
an an-1 逆置为： L a1 ^ ?
其中，单链表及结点定义如下： typedef struct LNode { ElemType data；
struct LNode *next；
}LNode，*LinkList；
2、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针,如下图所示)，试编写相应的入队列算法void EnQueue(Queue *Q, QElemType e)。其中队列类型定义如下：
typedef struct Node { ElemType data； a1 a2 an ? Q struct Node *next；
}Node，*Queue； 第五大题，第2小题图
《 数据结构与算法 》试卷 第 页 共 5 页
5