2015年广西桂林电子科技大学数据结构考研真题.doc

发布时间：2023-11-14 发布人：admin 分类：说明书资料大小：0.12M 资料格式：doc 举报版权申诉

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

文本预览

2015 年广西桂林电子科技大学数据结构考研真题 )。 )。 )。一选择题（2 分/题，共 20 分） 1、在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( A．直接前趋 B.直接后继 C.开始结点 D.终端结点 2、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为( A．O（1） B.O（log2n） C.O（n） D.O（n2） 3、常用于函数调用的数据结构是( A.栈 B.队列 C.链表 D.数组 4、若一个算法的时间复杂度用 T(n)表示，其中 n 的含义是（ A．问题规模 B．语句条数 C．循环层数 D．函数数量 5、具有线性结构的数据结构是（ A．树 B．图 C．栈和队列 D．广义表 6、以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列是（）。）。） A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6 C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v4

) 7、对线性表进行二分查找时，要求线性表必须( A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 8、指针 p1 和 p2 分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（） A.p1－＞next=p2－＞next;p2－＞next=p1－＞next; B. p2－＞next=p1－＞next;p1－＞next=p2－＞next; C. p=p2－＞next; p1－＞next=p;p2－＞next=p1－＞next; D. p=p1－＞next; p1－＞next= p2－＞next；p2－＞next=p; 9、队列的特点是（） A.允许在表的任何位置进行插入和删除 B.只允许在表的一端进行插入和删除 C.允许在表的两端进行插入和删除 D.只允许在表的一端进行插入，在另一端进行删除 10、在一棵二叉树中，度为 2 的结点数为 15，度为 1 的结点数为 3，则叶子结点数为（） A.12 B.16 C.18 D.20 二、在栈的输入端元素的输入顺序为 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)遍历左子树。已知一棵二叉树如图所示，请给出其 RNL 遍历的结果序列。（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，50，65}，试按

元素的次序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并画出删除 45 后的二叉排序树。 (15 分) 八、（1）画出下面网络的邻接矩阵；（2）给出从顶点 1 出发的深度优先序列和广度优先序列（相同情况的小标号在前）；（3）用 prim 算法构造网络的最小生成树，并给出生成树的权值。（15 分）九. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K 为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题： (1) 画出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较? (3) 若查找关键字60，需要依次与哪些关键字比较?

(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（20 分）十、设有两个按升序排列的单链表 X 和 Y，其头指针分别为 p，q 结点结构说明如下：试设计一个算法 void concat（node *p，*q）将它们合并成一个以 p 为头指针的单链表 Z，使其仍然有序。（15 分）十一、树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。设二叉树结点结构为：(lchild,data,bf,rchild), lchild,rchild 是左右儿子指针；data 是数据元素；bf 是平衡因子，编写递归算法计算二叉树中各个结点的平衡因子。（15 分）

分享到：

赞收藏

资料库

2015年广西桂林电子科技大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料