824数据结构与算法设计A

本文格式为Word版，下载可任意编辑——824数据结构与算法设计A

XX科技大学

2023年硕士研究生入学考试试题A

─────────────────────────────────

科目编号：824科目名称：数据结构与算法设计

考生须知：

1、答案必需写在答题纸上，写在试题或草稿纸上不给分。

2、答题须用蓝、黑色钢笔或圆珠笔，用铅笔、红色笔者不给分。3、答题必需写清题号，字迹要明白，卷面要保持整齐。4、试题要随答题纸一起交回。

一、单项选择题（每题2分，共30分）

（1）并归排序的时间繁杂度是（）。

A．O(n2)B．O(nlog2n)C．O(n)D．O(log2n)

（2）设一个链表最常用的操作是在末尾插入结点和删除尾结点，选用（）存储结构最节省时间。

A．单链表B．单循环链表C．带尾指针的单循环链表D．带头结点的双循环链表（3）散列文件是一种（）。

A．顺序文件B．索引文件C．链接文件D．计算机寻址文件（4）常用于函数调用的数据结构是（）。

A．栈B．队列C．数组D．链表（5）两个矩阵Ams,Bsn相乘的时间繁杂度是（）。

A．O(n2)B．O(s2)C．O(msn)D．O(mn)（6）图的广度优先探寻遍历使用的数据结构是（）。

A．栈B．队列C．集合D．树

（7）在单链表中，每个存贮结点有两个域，即数据域和指针域，指针域指向该结点的（）。A．直接前驱B．直接后继C．开始结点D．终端结点（8）在已知头指针的单链表中，要在其尾部插入一个新结点，其时间繁杂度是（）。A．O(n2)B．O(1)C．O(n)D．O(log2n)（9）在链队列中执行入队操作，（）。

A．需判断队是否为空B．限定在链表头p进行

C．需判断队是否为满D．限定在链表尾p进行

（10）对序列（95，83，62，70）进行冒泡排序（由小到大），第2趟排序后的结果为（）。A．（70，83，62，95）B．（70，62，83，95）

共5页第1页

C．（62，70，83，95）D．（83，62，70，95）（11）以下选项中与数据的存储结构无关的术语是（）。

A．栈B．链队列C．顺序表D．链表

（12）已知循环队列的存贮空间大小为m，对头指针front指向对头元素，对尾指针rear

指向对尾元素的下一个位置，则向对列中插入新元素时，修改指针的操作是（）。A．rear=（rear-1）％mB．rear=（rear+1）％m

C．front=（front-1）％mD．front=（front+1）％m（13）对于广义表A，若head(A)=tail(A)，则A为（）。

A．(())B．()C．((),())D．((),(),())（14）若一棵具有n个结点的二叉树的先序遍历和后序遍历的次序正好相反，则该二叉树应是（）。

A．结点均无左孩子的二叉树B．高度为n的二叉树

C．结点均无右孩子的二叉树D．存在度为2的结点的二叉树（15）平均时间繁杂度为O(nlog2n)的稳定排序算法是（）。

A．快速排序B．堆排序C．归并排序D．冒泡排序

二、填空题（每题2分，共20分）

（1）数据结构由数据的规律结构、存贮结构和数据的三部分组成。（2）广义表A=(a,b,(c,d,(e,f)),G)的长度为。

（3）以数据集{25,4,15,5,1}为权值构造一棵哈夫曼树，其带权路径长度为。（4）在高度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是。

（5）若某哈夫曼树有m个叶子结点，则该哈夫曼树共有个结点。

（6）向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和操作。

（7）在队列中，允许插入的一端称为。

（8）在一棵二叉树中，度为1的结点数是3，度为2的结点数是4，则该二叉树有个叶子结点。

（9）具有n个顶点的连通无向图，其生成树有条边。

（10）当关键字序列基本有序时，快速排序、简单项选择择排序和直接插入排序三种排序算法

中，运行效率最高的是。

共5页第2页

三、简答题（任选5道题，每题8分，共40分）

（1）什么是线性表？寻常有哪些存贮方式？其各自的优缺点是什么？

（2）什么是顺序队列的“假溢出〞现象？有哪些处理方式？如何判断队满和队空？（3）什么是二叉树的顺序存储方式？其优缺点有哪些？（4）图的存储结构有哪些？其各自的优缺点是什么？（5）静态查找有哪三种方法？各自的查找效率如何？

（6）什么样的图其最小生成树是唯一的？用Prim和Kruskal算法求最小生成树的时间繁杂度各为多少？他们分别适合于哪种类型的图？

四、应用题（每题10分，共40分）

（1）已知待排序记录的关键字序列为{25,96,11,63,57,78,44}，请回复以下问题：

（a）画出堆排序的初始堆（大根堆）；（b）画出第2次重建堆之后的堆。

（2）已知关键字序列为{56,23,41,79,38,62,18}，用散列函数H(key)=key％11将其散列到

散列表HT[0…10]中，采用线性探测法处理冲突，请回复以下问题：（a）画出散列存储后的散列表；

（b）求在等概率下查找成功的平均查找长度。

（3）已知某二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG，请回复以下问题：

（a）画出此二叉排序树；

（b）若将此二叉排序树看作森林的二叉链表存储，画出对应的森林。

（4）下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。请回复以下问题：

（a）画出该带权有向图的图形；

（b）从顶点V1为起点的广度优先遍历的顶点序列及对应的生成树；（c）以顶点V1为起点的深度优先遍历的顶点序列及对应的生成树；（d）由顶点V1到顶点V3的最短路径。

(顶点边)1V12V23V3?4V45V56V6?230110338618?542?233336?（出边表）429625?共5页第3页

五、算法设计题（任选2题，每题10分，共20分）

（1）假定二叉树结点的存储结构定义如下：typedefstructnode

{chardata；

structnode*lchild；structnode*rchild；}NODE；

试编写C（或Java）语言函数voidexchange(NODE*t)，其功能是交换二叉树的各

结点的左右子树（根结点指针为t）。

（2）以二叉链表为存储结构，编写按层次顺序（同一层自左至右）遍历二叉树的算法。（3）给定头指针为ha的单链表A，和头指针为hb的递增有序单链表B。试利用表A和

表B的结点，将表A和表B归并为递增有序单链表C，其头指针为hc（允许有一致的data值，表A、B、C均带有头结点）。

阅读下面的函数merge（），请给有下划线的位置填空，使之成为完整的算法（程序）。表结点的类型定义如下：

structnode{intdata;

structnode*next;};C语言算法如下：

voidmerge(structnode*ha,structnode*hb,structnode*hc){

structnode*pc,*qc,*pa,*fa;intsearch;hc=hb;hb=NULL;pa=ha->next;free(ha);while(pa){pc=hc;qc=hc->next;

search=1;//设置查找标志while(