《2015年广西桂林电子科技大学数据结构考研真题》由会员分享，可在线阅读，更多相关《2015年广西桂林电子科技大学数据结构考研真题（5页珍藏版）》请在金锄头文库上搜索。
1、历年考试真题1/520152015 年广西桂林电子科技大学数据结构年广西桂林电子科技大学数据结构考研真题考研真题一 选择题（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问题规模B语句条数C循环层数D函数数量
2、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，v4历年考试真题2/57、对线性表进行二分查找时，要求线性表必须()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.12B.16C.18D.20二、在栈的输入端元素的输入顺序为 1，2
4、，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 分）历年考试真题3/5四、假设二叉树的 RNL 遍历算法定义如下：若二叉树非空，则依次执行如下操作：(1)遍历右子树；(2)访问根节点；(3)遍历左子树。已知一棵二叉树如图所示，请给出其 RNL 遍历的结果序
5、列。（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，55，30，75，40，
6、50，65，试按历年考试真题4/5元素的次序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并画出删除 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，需要依次与哪些关键字比较?历年考试真题5/5(4)假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（20 分）十、设有两个按升序排列的单链表 X 和 Y，其头指针分别为 p，q 结点结构说明如下：试设计一个算法 void concat（node*p，*q）将它们合并成一个以 p 为头指针的单链表 Z，使其仍然有序。（15 分）十一、树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild),lchild,rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。（15 分）
