资源描述：
《2016年真题910数据结构(2016-B)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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
2、->next=s(D)p->next=s;3.用链接方式存储的队列，在进行插入运算时()。(A)仅修改头指针 (B)头、尾指针都要修改(C)仅修改尾指针(D)头、尾指针可能都要修改4.下列编码中属前缀码的是()（A）{1,01,000,001}（B）{1,01,011,010}（C）{0,10,110,11}（D）{0,1,00,11}5.两个字符串相等的充要条件是（）。(A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等(C)同时具备(A)和(B)两个条件(D)以上答案都不对6.设一维数组
3、中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)7.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为（）。(A)15(B)16(C)17(D)478.下面答案（）是二叉排序树。(A)二叉树中的每个结点的两棵子树的高度差的绝对值不大于１(B)二叉树中的每个结点的两棵子树的高度差等于１(C)二叉树中的每个结点的两棵子树是有序的(D)二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字
4、值，且小于其右子树（如果存在）所有结点的关键字值。9.已知有向图G=（V,E）,其中V={V1,V2,V3,V4,V5,V6,V7},E={,,第3页共3页,,,,,},G的拓扑序列是（）。(A)V1,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.利
5、用直接插入排序法的思想建立一个有序线性表的时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)二、设一数列的输入顺序为12345，若采用栈结构，并以A和D分别表示入栈和出栈操作，试问：能否得到下面的输出顺序，如果能，给出合法的入栈和出栈的操作顺序；如果不能解释为什么。（共10分）（1）能否得到输出顺序为32514的序列。（5分）（2）能否得到输出顺序为42135的序列。（5分）三、已知一棵二叉树的先根序列（A,B,D,E,C,F,G）和中根序列（D,B,E,A,
6、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分）六、已知一个带权图G的顶点集V和边集E分别为：（共15）V=
7、{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请完成：第3页共3页（1）画出图G；（3分）（2）画出图G的邻接表表示；（3分）（3）写出从顶点v1出发进行深度优先搜索（DFS）产生的深度优先生成树；（4分）（4）从顶点v1开始，用Pr
8、im算法构造图G的一棵最小生成树，并画出生成过程（5分）七、请用图示说明图从顶点a到其余各顶点之间的最短路径。(15分)八、给出关键字序列{4,5,1,2,8,6,7,3,10,9}的希尔排序过程，对于每一个增量写一次排序后的序列（10分）九、设散列表的地址范围是[0..9]，散列函数为H（key）=（key2+2）MOD9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。（15分）十、设计在顺序有序表
