2016年真题910数据结构(2016-A)

《2016年真题910数据结构(2016-A)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、桂林电子科技大学2016年研究生统一入学考试试题科目代码：910科目名称：数据结构请注意：答案必须写在答题纸上（写在试题上无效）。一、选择题（2分/题，共20分）1．执行下面程序段时，执行S语句的次数为（）。for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)S;A.B./2C.n(n+1)D.n(n+1)/22．线性链表不具有的特点是（）。（A）随机访问（B）不必事先估计所需存储空间大小（C）插入与删除时不必移动元素（D）所需空间与线性表长度成正比3．在一个单链表中，若p所指结点之后插入一个结点s，则执行（）。(A)q=p-

2、>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++15.对于图进行从顶点1开始的深度优先搜索遍历，可得到顶点访问序列（）第3页共3页A.1,2,4,5,7,6,3B.1,2,4,3,5,6,7C.1,2,4,5,7,6,3D.1,2,3,4,5,6,76．有拓扑排序的图，一定是（）。A．有环图

3、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，42B）19，28，20，40，23，42C）42，40，28，23，20，19D）42，28，40，20，23，1

4、910．就平均时间而言，下列排序方法中最差的一种是（）（A）堆排序（B）快速排序（C）希尔排序（D）直接选择排序二、有5个元素，其入栈次序为：A,B,C,D,E,在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个，D第二个出栈）次序有那几个:（10分）三、已知某二叉树的前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ，请完成：（1）画出该二叉树；（2）将该二叉树转换为对应的森林。（10）四、假设二叉树的RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；(3)遍历左子树。已知一棵二叉树如图所示

5、，请给出其RNL遍历的结果序列。（10分）五、给定序列K={12，8，10，14，16，6}，请完成：第3页共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}，试按元素的次序依次

6、插入一棵初始为空的二叉排序树（1）画出插入完成之后的二叉排序树。（7分）（2）画出删除42之后的二叉排序树。（8分）八、请用图示说明图从顶点a到其余各顶点之间的最短路径。(15分)九、已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，试：（共15分）（1）计算出每一个元素的散列地址并在下图中填写出散列表：（7分）`0123456（2）求出在查找每一个元素概率相等情况下的平均查找长度。（8分）十、设计在链式结构上实现简单选择排序算法。（15）十一

7、．假设二叉树采用二叉链表存储结构，设计一个算法，求二叉树b中值为x的结点的层号。（15）第3页共3页