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

班级：学号：姓名：装订线第1页共6页第2页共6页A顺序表B双链表C带头结点的双循环链表D单循环链表7、具有10个叶结点的二叉树中有个度为2的结点。A8B9C10D118、关键路径是事件结点网络中。A从源点到汇点的最长路径B从源点到汇点的最短路径C最长回路D最短回路9、对稀疏矩阵进行压缩存储目的是。A便于进行矩阵运算B便于输入和输出C节省存储空间D降低运算的时间复杂度10、在作进栈运算时，应先判别栈是否。A空B满C下溢D不用判别11、在下面的程序段中，对x的赋值语句的频度为。for(i=1;i=n;i++)for(j=1;j=n;j++)x=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)12、适用于折半查找的表的存储方式及元素排列要求为。A．链式存储，元素无序B．链式存储，元素有序C．顺序存储，元素无序D．顺序存储，元素有序13、设哈希表长为12，哈希函数是H(key)=keyMOD11，表中已有元素的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测再散列法解决冲突，则放入的位置是。A．8B．3C．5D．914、下面关于串的叙述中，哪一个是不正确的？。A.．串是字符的有限序列哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五六总分分数评卷人一、单项选择题（20分）1、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是。A快速排序B堆排序C归并排序D直接插入排序2、有五个元素按5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？。A54312B45312C34521D234153、比较次数与排序的初始状态无关的排序方法是。A直接插入排序B起泡排序C快速排序D简单选择排序4、一个有向无环图的拓扑排序序列是唯一的。A一定B不一定5、设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有个。An-1BnCn+1Dn+26、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。装订线第3页共6页第4页共6页B.空串是由空格构成的串C.空串不是空格串D.串既可以采用顺序存储，也可以采用链式存储15、双向链表中，在指针p指向的结点前插入指针q指向的结点的操作是。A.p-prior=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=p-prior;q-next=q;p-prior=q;p-prior=q;16、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是。A1和5B2和4C4和2D5和117、如果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)CcDd19、设无向图的顶点个数为n，则该图最多有条边。An-1Bn(n-1)/2Cn(n+1)/2Dn220、下列排序算法中，占用辅助空间最多的是。A.归并排序B.快速排序C.希尔排序D.堆排序二、填空题（20分）1、深度为k的完全二叉树至少有________个结点；k和结点总数n之间的关系是________。2、设数组a[1..5,1..8]的基地址为200，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[4,6]的存储地址为________；若以列序为主序顺序存储，则元素a[4,6]的存储地址为________。3、表达式A+((B*C-D)/E+F/G)的前缀表达式是________，后缀表达式是________。4、顺序存储结构是通过________表示元素之间的关系的；链式存储结构是通过________表示元素之间的关系的。5、高度为6的平衡二叉树至少有________个结点；具有4层非终端结点的三阶B-树至少有________个结点。6、动态查找表和静态查找表的重要区别在于前者包含有________和________运算，而后者不包含这两种运算。7、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的________和记录的________。8、文件由________组成；记录由________组成。9、数据结构中评价算法的两个重要指标是________和________。10、Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按________次序依次产生。有向图G可拓扑排序的判别条件是________。三、应用题（30分）1、对关键字序列{30,15,28,20,24,10,12,68,35}，构造一棵平衡二叉树并画图。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、下图为无向带权图，用克鲁斯卡尔算法构造其最小生成树，并写出选边的顺班级：学号：姓名：装订线第5页共6页第6页共6页序。四、算法题（30分）1、假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指结点的前趋变为p所指结点的后继结点。2、试给出二叉树的自上而下、自左而右的层次遍历算法。36511452ABDFCEG3