内容发布更新时间 : 2024/12/24 2:31:35星期一 下面是文章的全部内容请认真阅读。

桂林电子科技大学2016年研究生统一入学考试试题

科目代码：910 科目名称：数据结构

请注意：答案必须写在答题纸上（写在试题上无效）。

一、 选择题（2分/题，共20分） 1．执行下面程序段时，执行S语句的次数为（ ）。 for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= i; j++ ) S; A. B. /2 C. n(n+1) D.n(n+1)/2 2．线性链表不具有的特点是（ ）。 （A）随机访问 （B）不必事先估计所需存储空间大小 （C）插入与删除时不必移动元素 （D）所需空间与线性表长度成正比 3．在一个单链表中，若p所指结点之后插入一个结点s，则执行（ ）。 (A)q = p->next; s->next = q; (B) q = p->next; p->next = s; (C) s->next = p->next;p->next = s (D) p->next = s; 4．一棵度为4的树，个数为 , , ,分别是度为1 ，2 ，3 ，4的结点个数，终端结点 ，则有（ ）。 (A)= + + + (B)= 2 + + 1 (C)= 4+ 3 + 2 + (D)= 3+ 2 + + 1 5.对于图进行从顶点1开始的深度优先搜索遍历，可得到顶点访问序列（ ） 第 1 页 共 3 页

A.1,2,4,5,7,6,3 B.1,2,4,3,5,6,7 C.1,2,4,5,7,6,3 D.1,2,3,4,5,6,7 6．有拓扑排序的图，一定是（ ）。 A．有环图 B.无向图 C.无环有向图 D.无环任意图 7．对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 8．关键路径是事件结点图中( ) A.从源点到汇点的最短路径 B.从源点到汇点的最长路径 C.最长回路 D.最短回路 9．关键码序列K = { 23， 40， 28， 19， 20， 42 }，经过筛选法建堆过程后，得到的小顶堆为（ ）。 A）19，20，28，40，23，42 B）19，28，20，40，23，42 C）42，40，28，23，20，19 D）42，28，40，20，23，19 10．就平均时间而言，下列排序方法中最差的一种是（ ） （A）堆排序 （B）快速排序 （C）希尔排序 （D）直接选择排序 二、有5个元素，其入栈次序为：A,B,C,D,E,在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个，D第二个出栈）次序有那几个:（10分） 三、已知某二叉树的前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ，请完成： （1）画出该二叉树； （2）将该二叉树转换为对应的森林。（10） 四、假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作： (1)遍历右子树； (2)访问根节点； (3)遍历左子树。 已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。（10分） 五、给定序列K = { 12，8，10，14，16，6 }，请完成： 第 2 页 共 3 页

（1）按K中关键码的顺序依次插入一棵初始为空的二叉搜索树，画出插入完成后的二叉搜索树； （2）以序列K作为一组给定的权值，构造关于K的一棵哈夫曼（Huffman）树，并求它的带权外部路径长度。 （15分） 六、已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。把第一个节点作为基准点。（10） 七、已知元素个数为8的字典，其关键码集合为{50，30，42，20，60，36，56，45，40}，试按元素的次序依次插入一棵初始为空的二叉排序树 （1）画出插入完成之后的二叉排序树。（7分） （2）画出删除 42之后的二叉排序树。（8分） 八、请用图示说明图从顶点a到其余各顶点之间的最短路径。 (15分) 九、 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：（共15分） （1）计算出每一个元素的散列地址并在下图中填写出散列表：（7分） ` 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。（8分） 十、设计在链式结构上实现简单选择排序算法。（15） 十一．假设二叉树采用二叉链表存储结构，设计一个算法，求二叉树b中值为x的结点的层 号。（15） 第 3 页 共 3 页