2016年桂林电子科技大学考研专业课试题910数据结构(A).docx

1、桂林电子科技大学2016年研究生统一入学考试试题科目代码：910 科目名称：数据结构请注意：答案必须写在答题纸上（写在试题上无效）。一、 选择题（2分/题，共20分）1执行下面程序段时，执行S语句的次数为（ ）。 for ( int i = 1; i = n; i+ ) for ( int j = 1; j 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)

2、= + + + (B)= 2 + + 1 (C)= 4+ 3 + 2 + (D)= 3+ 2 + + 15.对于图进行从顶点1开始的深度优先搜索遍历，可得到顶点访问序列（ ）A.1,2,4,5,7,6,3 B.1,2,4,3,5,6,7C.1,2,4,5,7,6,3 D.1,2,3,4,5,6,76有拓扑排序的图，一定是（ ）。A有环图 B.无向图 C.无环有向图 D.无环任意图7对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列8关键路径是事件结点图中( ) A.从源点到汇点的最

3、短路径 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，1910就平均时间而言，下列排序方法中最差的一种是（ ） （A）堆排序 （B）快速排序 （C）希尔排序 （D）直接选择排序二、有5个元素，其入栈次序为：A,B,C,D,E,在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个，D第二个出栈）次序有那几个:（10分）三、

4、已知某二叉树的前序序列为 ABECDFGHIJ，中序序列为 EBCDAFHIGJ，请完成：（1）画出该二叉树；（2）将该二叉树转换为对应的森林。（10）四、假设二叉树的RNL遍历算法定义如下： 若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；(3)遍历左子树。已知一棵二叉树如图所示，请给出其RNL遍历的结果序列。（10分）五、给定序列K = 12，8，10，14，16，6 ，请完成：（1）按K中关键码的顺序依次插入一棵初始为空的二叉搜索树，画出插入完成后的二叉搜索树；（2）以序列K作为一组给定的权值，构造关于K的一棵哈夫曼（Huffman）树，并求它的带权外部路径长度。

5、（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 页