【安徽大学 期末试题】2006-2007第2学期数据结构与算法试卷(A卷).docx

1、安徽大学20 0620 07学年第2学期数据结构与算法考试试卷（A卷）得 分（时间120分钟）题号.*四五.六七总分得分院/系专业姓名学号一、选择题（每小题2分，共20分）L1、数据结构中，与所使用的计算机无关的是数据的结构。2、A.存储结构 B.物理结构C.逻辑结构 D.物理和存储结构循环链表的主要优点是oA.不再需要头指针了 B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表3、栈和队列都是OA.顺序存储的线性结构C.限制存取点的线性结构B. 链式存储的非线性结构D.限制存取点的非线性结构4、串的长度是指A.串

2、中所含不同字母的个数C. 串中所含字符的个数B.串中所含不同字符的个数D.串中所含非空格字符的个数5、若某二叉树的先序和中序遍历序列分别为ABCD、ACDB,则该二叉树的后序遍历序列为A. DBCAB. ADCBC. DCBAD.CDBA6、有n个叶子结点的哈夫曼树,其结点总数为A. 2n-lB. 2nC. 2n+lD.不确定。7、无向图的邻接矩阵一定是OA.对角矩阵 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

3、, 20, 30)9、下列排序方法中属于不稳定排序方法的是A.直接插入排序B.冒泡排序C.快速排序D.归并排序10、设有一个用线性探测法解决冲突得到的散列表（或哈希表）如下图所示，散列函数为H（k）二k% 11,若 要查找元素14,探查的次数为oA. 5B. 9（第一题，第10小题图）C. 3D. 60123456789101325801617614二、填空题（每小题2分，共20分）1、一个“好”的算法要考虑以下标准：正确性、可读性、和高效率与低存储量需求。2、对于二维数组a0.4,0.5,设每个元素占1个存储单元，且以行为主序存储，则元素a2, 3相对于数组空间起始地址的偏移量是o3、若一棵

4、完全二叉树共有101个结点，则该二叉树的叶子结点个数是o4、在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为个。5、适用于折半查找的表的存储方式及元素排列要求为o6、设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均 查找长度为o7、采用遍历二叉排序树，可以得到一个关键字的有序序列。8、以数据集2, 5, 7, 8, 9为权值构造一棵哈夫曼树，则其带权路径长度WPL为。9、求图的最小生成树的两种算法中，其中算法适合于求

5、稀疏图的最小生成树。10、图的深度优先搜索遍历类似于树的遍历。三、判断题（每小题1分，共10分）1、顺序表结构适宜于进行顺序存取，而链表则适宜于进行随机存取。2、两个栈共享一片连续内存空间时，为提高内存利用效率，减少溢出机会, 这片内存空间的两端。（）应把两个栈的栈底分别设在3、栈和队列都是线性表，只是在插入和删除时受到了一些限制。4、空串是由空格构成的串。5、6、折半查找法的查找速度一定比顺序查找法快。7、二叉树是度为2的有序树。KMP算法的特点是在模式匹配过程中指示主串的指针不会变小或回溯。8、9、完全二叉树中，若一个结点没有左孩子，则它必是树叶。迪杰斯特拉（Dijkstra）算法是按照路

6、径长度逐步递减的次序产生最短路径的方法。10、有e条边的无向图，在邻接表中有e个结点。四、应用题(每小题10分，共30分)1、设 F=T1, T2, T32、已知待排序的序列为(12, 2, 16, 30,28, 10, 16, 20, 6, 18),试完成：(1) 根据以上序列，建立堆排序的初始堆(要求先输出最大值)，请画出主要过程和最后堆的结果图;(2) 输出最大值后，如何得到次大值，请画出主要过程及相应的结果图。3、对如下所示的连通图，试分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskar)算法构造其最小生成树，并 给出其构造过程。(第四题，第3小题图)五、算法设计题（每小题10分，共20分）1、试设计算法，对带头结点的单链表实现就地逆置，即利用原单链表中的结点的存储单元，将链表L逆置为：Lai 一壬其中，单链表及结点定义如下: typedef struct LNode ElemType data；struct LNode *next；LNode, *LinkList；2、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针,如下图所示），试编写相应的入队列算法void EnQueue（Queue *Q, QElemType e