1、桂林电子科技大学2016年研究生统一入学考试试题科目代码：910 科目名称：数据结构请注意：答案必须写在答题纸上（写在试题上无效）。一、单项选择题（每小题2分，共20分）1. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为（ ）。(A)逻辑结构 (B)顺序存储结构 (C)链式存储结构 (D)以上都不对2. 在一个单链表中，若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;3. 用
2、链接方式存储的队列，在进行插入运算时( )。(A) 仅修改头指针 (B) 头、尾指针都要修改(C) 仅修改尾指针 (D) 头、尾指针可能都要修改4.下列编码中属前缀码的是( )（A）1,01,000,001 （B）1,01,011,010（C）0,10,110,11 （D）0,1,00,115. 两个字符串相等的充要条件是（ ）。(A) 两个字符串的长度相等 (B) 两个字符串中对应位置上的字符相等(C) 同时具备(A)和(B)两个条件(D) 以上答案都不对6. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。(A) O(n) (B) O(nlog2n) (C) O(
3、1) (D) O(n2)7. 假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为（ ）。(A) 15 (B) 16 (C) 17 (D) 478. 下面答案（ ）是二叉排序树。(A)二叉树中的每个结点的两棵子树的高度差的绝对值不大于(B) 二叉树中的每个结点的两棵子树的高度差等于(C) 二叉树中的每个结点的两棵子树是有序的(D) 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。9. 已知有向图G=（V,E）,其中V=V1,V2,V3,V4,V5,V6,V7,E=,G的拓扑序列是（ ）。 (A)V1
4、,V3,V4,V6,V2,V5,V7 (B)V1,V3,V2,V6,V4,V5,V7 (C)V1,V3,V4,V5,V2,V6,V7 (D)V1,V2,V5,V3,V4,V6,V710. 利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（ ）。 (A) O(n)(B) O(nlog2n) (C) O(n2)(D) O(1og2n)二、设一数列的输入顺序为12345，若采用栈结构，并以A 和D 分别表示入栈和出栈操作，试问：能否得到下面的输出顺序，如果能，给出合法的入栈和出栈的操作顺序；如果不能解释为什么。（共10分）（1） 能否得到输出顺序为32514 的序列。（5分）（2） 能否得到
5、输出顺序为42135 的序列。（5分）三、已知一棵二叉树的先根序列（A,B,D,E,C,F,G）和中根序列（D,B,E,A,F,G,C）（共10分）（1）画出这棵二叉树。（5分）（2）将（1）得到的二叉树转换为树林。（5分）四、有一份电文中共使用8个字符：a、b、c、d、e、f、g、h，它们出现的频率是5, 29, 7, 8, 14, 23, 3, 11（15分）（1）试画出对应的哈夫曼树；（5分）（2）每个字符的哈夫曼编码；（5分）（3）求带权外部路径长度(WPL)。（5分）五、对一组无序记录（72，38，96，23，15，54，60，45，83），画出建立原始大根堆（10分）六、已知一个带
6、权图G的顶点集V和边集E分别为：（共15）V = v1，v2，v3，v4，v5，E =(v1，v2)，(v1，v3)，(v1，v4)，(v2，v4)，(v2，v5)，(v3，v4)，(v4，v5) ，E中各边对应的权值如下：(v1，v2)：3， (v1，v3)：10， (v1，v4)：7， (v2，v4)：5，(v2，v5)：7， (v3，v4)：9， (v4，v5)：15请完成：（1）画出图G；（3分）（2）画出图G的邻接表表示；（3分）（3）写出从顶点v1出发进行深度优先搜索（DFS）产生的深度优先生成树；（4分）（4）从顶点v1开始，用Prim算法构造图G的一棵最小生成树，并画出生成过程（5分）七、请用图示说明图从顶点a到其余各顶点之间的最短路径。 (15分) 八、给出关键字序列4,5,1,2,8,6,7,3,10,9的希尔排序过程，对于每一个增量写一次排序后的序列（10分）九、设散列表的地址范围是 0.9 ，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。（15分）十、设计在顺序有序表中实现二分查找的算法。（15分）十一、设计判断两个二叉树是否相同的算法。（15）第 3 页 共 3 页
