1、桂林电子科技大学2015年研究生统一入学考试试题科目代码：910 科目名称：数据结构请注意：答案必须写在答题纸上（写在试题上无效）。一 选择题（2分/题，共20分）1、在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( )。A直接前趋 B.直接后继 C.开始结点 D.终端结点 2、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为( )。AO（1） B.O（log2n） C.O（n） D.O（n2） 3、常用于函数调用的数据结构是( )。A.栈 B.队列 C.链表 D.数组4、若一个算法的时间复杂度用T(n)表示，其中n的含义是（ ）。A
2、问题规模 B语句条数 C循环层数 D函数数量5、具有线性结构的数据结构是（ ）。A树 B图 C栈和队列 D广义表6、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）Av1，v2，v3，v4，v5，v6，v7Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6Dv1，v2，v5，v6，v7，v3，v47、对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列8、指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一
3、个新的单循环链表，应执行的操作为（ ） A.p1next=p2next;p2next=p1next;B. p2next=p1next;p1next=p2next;C. p=p2next; p1next=p;p2next=p1next;D. p=p1next; p1next= p2next；p2next=p;9、队列的特点是（ ）A.允许在表的任何位置进行插入和删除B.只允许在表的一端进行插入和删除C.允许在表的两端进行插入和删除D.只允许在表的一端进行插入，在另一端进行删除10、在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ） A.12 B.16 C.18 D.2
4、0 二、在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程（用push（x）表示x进栈，pop(x)表示x退栈），若不能，简述理由。（10分）三、设待排序的排序码序列为12, 2, 16, 30, 28, 10, 16*, 20, 6, 18, 试写出使用直接插入排序每趟排序后的结果。并说明做了多少次排序码比较。（10分）四、假设二叉树的RNL遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；(3)遍历左子树。已知一棵二叉树如图所示，请给出其R
5、NL遍历的结果序列。（10分）五、给定叶子结点的权值集合15, 3,14, 2, 6, 9, 16, 17，构造相应的哈夫曼树，并计算其带权路径长度。 (10分)六、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。（1）100，85，98，77，80，60，82，40，20，10，66（2）100，98，85，82，80，77，66，60，40，20，10（3）100，85，40，77，80，60，66，98，82，10，20（4）10，20，40，60，66，77，80， 82，85，98，100 （10分）七、已知元素个数为8的字典，其关键码集合为45，20，
6、55，30，75，40，50，65，试按元素的次序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并画出删除45后的二叉排序树。 (15分) 八、（1）画出下面网络的邻接矩阵；（2）给出从顶点1出发的深度优先序列和广度优先序列（相同情况的小标号在前）；（3）用prim算法构造网络的最小生成树，并给出生成树的权值。 （15分）九. 设哈希(Hash)表的地址范围为017，哈希函数为：H (K)=K MOD 16, K 为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题：(1) 画
7、出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较?(3) 若查找关键字60，需要依次与哪些关键字比较?(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 （20分）十、设有两个按升序排列的单链表X和Y，其头指针分别为p，q结点结构说明如下：typedef struct nodelint data；struct nodel *nextnode；试设计一个算法void concat（node *p，*q）将它们合并成一个以p为头指针的单链表Z，使其仍然有序。（15分）十一二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild),lchild,rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。 （15分）第 4 页 共 4 页
