哈尔滨工程大学-考研数据结构真题-5.doc

《哈尔滨工程大学-考研数据结构真题-5.doc》由会员分享，可在线阅读，更多相关《哈尔滨工程大学-考研数据结构真题-5.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、班级： 学号： 姓名： 装 订 线哈尔滨工程大学试卷考试科目: 数据结构A卷 题号一二三四五六总分分数评卷人A 顺序表 B 双链表 一、 单项选择题（20分）1、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 。 A 快速排序 B 堆排序 C 归并排序 D 直接插入排序 2、有五个元素按5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？ 。A 5 4 3 1 2 B 4 5 3 1 2 C 3 4 5 2 1 D 2 3 4 1 53、比较次数与排序的初始状态无关的排序方法是 。A 直接插入排序 B 起泡排序 C 快速排序 D 简单选择

2、排序4、一个有向无环图的拓扑排序序列 是唯一的。A 一定 B 不一定 5、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 个。A n-1 B n C n+1 D n+26、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 存储方式最节省时间。C 带头结点的双循环链表 D 单循环链表7、具有10个叶结点的二叉树中有 个度为2的结点。A 8 B 9 C 10 D 118、关键路径是事件结点网络中 。A 从源点到汇点的最长路径 B 从源点到汇点的最短路径C 最长回路 D 最短回路9、对稀疏矩阵进行压缩存储目的是 。A 便于进

3、行矩阵运算 B 便于输入和输出 C 节省存储空间 D 降低运算的时间复杂度10、在作进栈运算时，应先判别栈是否 。A 空 B 满 C 下溢 D 不用判别11、在下面的程序段中，对x的赋值语句的频度为 。for ( i=1; i= n; i+)for ( j=1; jprior=q; q-next=p; p-prior-next=q; q-prior=q；B. p-prior=q; p-prior-next=q; q-next=p; q-prior=p-prior;C. q-next=p; q-prior=p-prior; p-prior-next=q; p-prior=q;D. q-prior

4、=p-prior; q-next=q; p-prior=q; p-prior=q;16、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 。A 1和 5 B 2和4 C 4和2 D 5和1 17、如果T2是由树T1转换而来的二叉树，那么 T1中结点的后序遍历就是T2中结点的 。A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历 18、广义表A=(a,b,(c,d),(e,(f,g),则Head(Tail(Head(Tail(Tail(A)的值为 。A (g) B (d) C c D d

5、19、设无向图的顶点个数为n，则该图最多有 条边。A n-1 B n(n-1)/2 C n(n+1)/2 D n220、下列排序算法中，占用辅助空间最多的是 。A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序二、填空题（20分）1、深度为k的完全二叉树至少有_个结点； k和结点总数n之间的关系是 _。2、设数组a1.5,1.8的基地址为200，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a4,6的存储地址为_；若以列序为主序顺序存储，则元素a4,6的存储地址为_。3、表达式A+(B*C-D)/E+F/G)的前缀表达式是_，后缀表达式是_。4、顺序存储结构是通过_表示元素之

6、间的关系的；链式存储结构是通过_表示元素之间的关系的。5、高度为6的平衡二叉树至少有_个结点；具有4层非终端结点的三阶B-树至少有_个结点。6、动态查找表和静态查找表的重要区别在于前者包含有_和_运算，而后者不包含这两种运算。7、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_。8、文件由_组成；记录由_组成。9、数据结构中评价算法的两个重要指标是_和_。10、Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按_次序依次产生。有向图G可拓扑排序的判别条件是_。三、应用题（30分）1、 对关键字序列30,15,28,20,24,10,12,68,3

7、5，构造一棵平衡二叉树并画图。2、 对于关键字序列(503，87，512，61，908，120，897，275，653，462), 建立初始堆（小顶堆），并给出结点的交换次数。3、 一棵二叉树的前序序列是ABFGCHDEIJLK，中序序列是FGBHCDILJKEA，请画出该二叉树的后序线索二叉树。4、 假设字符A、B、C、D、E、F、G的应用频率分别是为0.06、0.24、0.14、0.08、0.04、0.16、0.28，请画出相应的编码哈夫曼树，并求其哈夫曼编码。5、 下图为无向带权图，用克鲁斯卡尔算法构造其最小生成树，并写出选边的顺36511452ABDFCEG3序。四、算法题（30分）1、 假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指结点的前趋变为p所指结点的后继结点。2、 试给出二叉树的自上而下、自左而右的层次遍历算法。第6页 共 6页第5页 共6页