数据结构试题-温州大学2021年硕士研究生招生考试专业课真题

绝密★考试结束前温州大学

2021年硕士研究生招生考试试题

科目代码及名称：826数据结构

适用专业（方向）：081200计算机科学与技术

请考生按规定用笔将所有试题的答案写在答题纸上，在此试题纸上答题无效

一、单项选择题（共10小题，每小题4分，共40分）

1.数组的逻辑结构不同于下列（）的逻辑结构。

A.线性表B.栈

C.队列D.树

2.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A.低于链接法处理冲突B.高于链接法处理冲突

C.与链接法处理冲突相同D.高于二分查找

3.一个线性表中最常用操作是根据第i个元素获取其前驱节点i-1,则（）方式存储最节省

存储空间。

A.单链表B.循环双链表C.循环单链表D.顺序表

4.哪种遍历方式在遍历它的左子树和右子树之前遍历它自身？（）

A.后序遍历B.先序遍历

C.中序遍历D.层次遍历

5.设有一个二维数组Data[m][n],假设Data[0][0]存放位置在921,Data⑵⑵存放位置在965,每

个元素占一个空间，问Data[3][3]存放在（）位置？

A.987B.986C.985D.996

第1页共9页

6.设栈Stack和队列Que的初始状态为空，元素al>a2>a3、a4、a5和a6依次通过栈Stack,一

个元素出栈后即进入队列Que。若6个元素出列的顺序为。、a4、a3、a6、a5和al,则栈Stack

的容量至少应该是()。

A.6B.4

C.3D.2

7.下列四种排序中()的空间复杂度最大。

A.插入排序B.冒泡排序

C.归并排序D.堆排序

8.用指向左、右孩子结点的二个引用域的二叉链表存储有n个结点的二叉树，则一共有()

个空的引用域。

A.n+1B.n-1C.nD.不能确定

9.设一组初始记录关键字序列(25,12,26,23,38),以第一个记录关键字25为基准进行一趟

快速排序的结果为()。

A.12,23,25,38,26B.23,12,25,38,26

C.23,12,25,26,38D.12,23,26,25,28

10.设数组data[MAX]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行

出队操作后其头指针front值为()

A.front=front+lB.front=(front+l)%(MAX-1)

C.front=(front-l)%MAXD.front=(front+l)%MAX

第2页共9页

二、分析题（共5小题，每小题10分，共50分）

1.从给定二叉树的先序和中序遍历序列，可以构造一棵二叉树。已知先序遍历序列为

{ABCDEFGH）,中序遍历序列为{DCBEAGFH）,完成以下要求。

（1）实现由先序、中序构造二叉树程序（7分）。

（2）画出构造的二叉树（3分）。

注：将下述代码抄写到答题纸上，并在答题纸上编写完成createBTree函数的代码。

typedefstructNode{

ElementTypedata;

structNode*left;

structNode*right;

JBTNode,*BTree;

intpre[MAX],in[MAX];〃存放先序、中序遍历序列

〃先序、中序遍历构造二叉树

〃bl,H分别是先序序列的下界（下标）和上界（下标）

〃b2,t2分别是中序序列的下界（下标）和上界（下标）

BTreecreateBTree（intbl,inttl,intb2,intt2）

第3页共9页

2.用普里姆算法构造图1所示的无向图从顶点vO开始的最小生成树。完成以下要求。

（1）从图2开始，依次画出最小生成树生成过程（6分）。

（注：从图2开始，根据算法过程，每幅图依次增加一个顶点及相应的边。图n中应保留图n-1

的所有顶点和边。）

（2）简述普里姆算法（4分）。

图1图2图3

第4页共9页

3.双链表的数据结构如下所示。请实现在双链表的表头节点之后插入新节点操作。

注：将下述代码抄写到答题纸上，并在答题纸上编写完成doubleLinkedListHeadlnsert函数的代码。

typedefstructDNode〃数据结构

(

ELEMTYPdata;

structDNode*prev;

structDNode*next;

}DNode;

typedefstructDoubleLinkedList〃数据结构

(

DNode*head;

intlen;

}DoubleLinkedList;

intdoubleLinkedListHeadInsert(DoubleLinkedList*dlList,ELEMTYPx)〃函数原型

4.在如图的平衡二叉树节点A的左子树的左子树上插入节点5,导致平衡二叉树不平衡，完成以

下要求。

（1）绘出调整后的平衡二叉树（6分）。

（2）指出这种失衡的类型并简要其调整过程（4分）。

第5页共9页

5.某工程中AOE网如下图所示。为了更好的完成工作，需要帮助他们找出关键活动和关键路径。

请回答下列问题:

（1）各事件的最早发生时间和最晚发生时间（4分）。

V0VIV2V3V4V5

最早发生时间

最晚发生时间

（2）各活动的最早开始时间和最晚开始时间（4分）。

ala2a3a4a5a6a7a8

最早开始时间

最晚开始时间

（3）关键路径：；关键路径的长度：（2分）。

第6页共9页

三、综合应用题(共4小题，每小题15分，共60分)

1.调整整数数组array口中的元素位置,并返回分界位置L使所有值为奇数的元素均落在array[l..i]

上，使所有值为偶数的元素均落在aiTay[i+l..h]±o

要求：(1)时间复杂度为O(n)、空间复杂度为0(1)；(2)算法用下面的函数原型表示。

注：将下述代码抄写到答题纸上，并在答题纸上编写完成arrange函数的代码。

/*顺序表结构*/

typedefintElementType;

typedefstruct{

ElementTypearray[MAXI;/*存放元素的数组刃

intlength;/*已经有多少元素*/

intcapacity;/*容量*/

}*SeqList;

intarrange(SeqListlist)

第7页共9页

2.邻接矩阵法存储有向图及度的计算：

（1）写出图中有向图的邻接矩阵（6分）。

（2）计算图中各顶点的出度、入度和度（6分）。

（3）描述根据有向图的邻接矩阵计算有向图的度的算法（3分）。

3.假设用于通信的电文由字符集｛4'3&%[811｝中的字符组成，这8个字符在电文中出现的

频率为｛0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10｝。

（1）画出哈夫曼树（8分）。

（2）计算最小带权路径和（3分）。

（3）给出各字符的编码，左孩子编号0,右孩子编号1（4分）。

第8页共9页

4.编写一个算法，用下面指定的链表结构实现两个多项式相加。如LA:2X2+3,LB:3X3+X2+1,LA和