《数据结构研究生入学考试模拟题三》由会员分享，可在线阅读，更多相关《数据结构研究生入学考试模拟题三（3页珍藏版）》请在金锄头文库上搜索。
1、哈尔滨工业大学二七年硕士研究生考试模拟试题（三）考试科目：计算机专业基础适用专业：计算机科学与技术I 数据结构（含高级语言）部分（共 75 分）一、填空题（每空 1 分，共 13 分）1.一棵二叉树的第 i（）层最多有 个结点；一棵有 n（）个结0i 0n 点的满二叉树共有 叶子和 个非终端结点。 2.已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少为 。 3.已知一个图的邻接矩阵表示，删除所有从第 i 个结点出发的边的方法是 。 4.有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二 分查找值为 82 的结点时，需要 次比较后才能查找成功。
2、5.有一个长度为 12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率 情况下查找成功所需的平均比较次数为 。 6.一组记录的排序码为46，79，56，38，40，84，则利用堆排序的方法建立的初 始堆为 。 7.设有 1000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，最 好选用 排序法。 8.用某种排序方法对线性表25，84，21，47，15，27，68，35，20进行排序时， 元素序列的变化情况为25，84，21，47，15，27，68，35，20； 20，15，21，25，47，27，68，35，84； 15，20，21，25，35，27，47，68，8
3、4； 15，20，21，25，27，35，47，68，84，则所采用的排序方法为 。 9.直接存取文件时用 方法组织的。 10. 磁盘文件有 m 个初始归并段，采用 K 路归并时，所需的归并遍数为 。 11. 在选择树中， “败者”是指 。二、单项选择题（每题 1 分，共 6 分） 1.非空的单循环链表 Head 的尾结点 p 满足（ ） 。 A p-next=NULL Bp=NULL C p-Head=NULL D p=Head 2.一个具有 124 个叶结点的完全二叉树，最多有（ ）个结点。 A11 B10 C11 到 1025 之间 D10 到 1024 之间 3.若二叉树采用二叉链表存
4、储结构，要交换其所有分支结点的左、右子树的位置， 利用（ ）遍历方法最合适。A前序 B中序 C后序 D按层次 4.判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ） 。 A求关键路径的方法 B求最短路径的 Dijkstra 方法 C深度优先搜索遍历算法 D广度优先搜索遍历算法 5.下列四个序列中，哪一个是堆（ ） 。 A75，65，30，15，25，45，20，10B75，65，45，10，30，25，20，15 C75，45，65，30，15，25，20，10 D75，45，65，10，25，30，20，15 6.若数据表 A 中每个元素矩其最终位置不远，则采用（ ）排
5、序算法最省时 间。 A堆排序 B插入排序 C直接选择排序 D快速排序三、简答（共 26 分） 1.设 T 是一颗二叉树，除了叶子结点外，其它结点的度数均为 2，若 T 中有 6 个叶 结点，试问：（8 分） （1）T 中的最大深度和最小深度可能是多少？ （2）T 中共有多少非叶结点？ （3）若叶结点的权值分别为 1，2，3，4，5，6。请构造一棵 Huffman 树，并计算 该 Huffman 树的带权路径长度 WPL。 答：2.冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动， 试举例说明之。快速排序过程中有没有这种现象？（5 分） 答：3.设给定的关键字集合为20，1
6、5，40，35，45，25，50，30，10，并顺序输入。 （8 分） （1）构造一棵完全二叉树；（2）画出整理好的一棵堆树； （3）画出一棵输出一个排序记录后的二叉树；（4）画出重新调整好的堆树。 答：4.对以下关键字序列建立 Hash 表： （SUN，MON，TUE，WED，THU，FRI，SAT） 。Hash 函数为 H（K）=（关键 字中第一个字母仔字母表中的序号）MOD 7，用线性探测法处理冲突，求构造一 个装填因子为 0.7 的 Hash 表；并分别计算出在等概率情况下查找成功和不成功的 平均查找长度。 （5 分） 答：四、算法设计（共 30 分）1.假设以带头结点的循环链表表示队
7、列，并且只设一个指针指向队尾元素（注意不 设头指针） ，试设计相应的队列初始化、入队列和出队列的算法。 （6 分） 答：2.设计算法，完成在中序线索二叉树中查找指定结点在后序下的前驱结点。 （6 分） 答：3.编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带头结点的 双链表，算法返回头结点的地址。 （6 分） 答：4.已知一个顺序表中有 m 个记录，表中记录不依关键字有序，编写算法为该顺序表 建立一个有序的索引表，索引表中的每一项应含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到。 （6 分）( )O m答：5.设计一算法判断给定的二叉树是否以构成一个堆。 （6 分） 答：
