温州大学数据结构2017-2018,2020-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]存放位置在921,Data⑵⑵存放位置在965,每

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

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

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

个元素出栈后即进入队列Que。若6个元素出列的顺序为a2、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=(fiont-l)%MAXD.front=(front+l)%MAX

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

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

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

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

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

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

typedefstructNode{

ElementTypedata;

structNode*left;

structNode*right;

JBTNode,*Blree;

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

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

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

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

BTreecreateBTree（intbl,inttl,iiitb2,intt2）

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

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

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

的所有顶点和边。）

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

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

请回答下列问题:

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

V0VIV2V3V4V5

最早发生时间

最晚发生时间

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

ala2a3a4a5a6a7a8

最早开始时间

最晚开始时间

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

三、综合应用题（共4小题，每小题15分，共60分）

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

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

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

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

/*顺序表结构*/

typedefintElementType;

typedefstruct{

ElementTypearray[MAX];/*存放元素的数组*/

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

intcapacity;/*容量*/

}*SeqList;

intarrange（SeqListlist）

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

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

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

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

3.假设用于通信的电文由字符集｛a,b,c,d,e,£g,h｝中的字符组成，这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分）。

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

LB相力U后得至ILA：3x3+3x2+4o

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

structNode｛〃链表的数据结构

intcoef;//系数

intexpon;〃指数

structNode*next;

}Node,*LinkList;

voidpolyAdd(LinkListpolyl,LinkListpoly2)〃计算多项式的和

（请考生在答题纸上答题，在此试题纸上答题无效）

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

1.在数据结构中，与所使用的计算机无关的是数据的（）。

A.逻辑结构B.存储结构

C.逻辑结构和存储结构D.物理结构

2.算法的时间复杂度属于一种（）。

A.事前统计的方法B.事前分析估算的方法

C.事后统计的方法D.事后分析估算的方法

3.线性表中的所有元素都有一个前驱元素和后继元素。这个说法是()。

A.正确的B.错误的

4.链式存储的存储结构所占存储空间()

A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B.只有一部分，存放结点值

C.只有一部分，存储表示结点间关系的指针

D.分两部分，一部分存放结点值，另一部分存放结点所占单元数

5.经过以下栈运算后，x的值是()。

initStack(s);push(s,a);push(s,b);pop(s,&x);top(s,&x);

A.aB.bC.1D.0

6.数组A中，每个元素的长度为4个字节，行下标i从1到8,列下标j从1到10,从首地址

100开始连续存放在存储器内。若该数组按行主序存放，则元素A[8][5]的起始地址为()；

若该数组按列主序存放，则元素A[8J⑸的起始地址为()。

A.396,217B,396,256C.256,396D.256,217

7.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是()。

A.9B.11C.12D.不确定

8.设有无向连通图G中的边集氏{(A,B),(A,C),(A,E),(B,E),(E,D),(D,F),(F,C)}。若从

顶点A出发按深度优先搜索进行遍历，则可能得到的一种顶点序列为()。

A.{A,B,E,C,D,F}B.{A,C,F,E,B,D}

C.{A,E,B,C,F,D}D.{A,E,D,F,C,B)

9.对于长度为9的有序顺序表，若采用折半查找法，在等概率情况下查找成功的平均查找长度

为()的值除以9。

A.20B.18C.25D.22

10.排序算法的稳定性是指()。

A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C.排序算法的性能与待排序元素的数量关系不大

D.排序算法的性能与待排序元素的数量关系密切

二、填空题(共5小题，每小题10分，共50分)

1.请完成下面顺序表的操作。顺序表的类型如下。

typedefstruct)

ElementType*array;/*存放元素的数组刃

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

intcapacity;/*容量*/

JSeqList;

/*在顺序表的第i个位置插入元素X*/

intinsertList(SeqList*L,inti,ElementTypex)

(

if(L->length>=L->capacity){

return0;

)

if(i<1||i>L->length+l){

return0;

)

for(k=L->length-1;k>=i-l;k-){

L->array[k+l]=L->arraylk];

return1;

)

2.假设通讯电文中只用到A,B,C,D,E,F六个字母，它们在电文中出现的相对频率分别为：

8,3,16,10,5,20。(1)用这些信息构造哈夫曼树；(2)计算该哈夫曼树的带权路径长度。

这棵哈夫曼树有个结点；该哈夫曼树的带权路径长度(WPL)：。

3.己知序列{99,5,36,7,22,17,46,12,2,19,25,28,1,92},用这些序列建小根堆。

按照从上到下，从左到右，小根堆的结点序列是：。

4.已知序列{13,2,16,3,8,28,4,10,5,6,7},请按照下面的快速排序算法，给出该序列作升序排

列时前三趟的结果。

第]趟：;

第2趟：；

第3趟：o

typedefintElementType;

intpartition(ElementTyper[],intlow,inthigh)

(

intpivot;

pivot=r[lowj;

while(low<high){

while(low<high&&r[high]>=pivot){

high-;

)

r[low]=r[high];

while(low<high&&r[low]<=pivot){

low++;

)

r[high]=r[low];

}一

r[lowj=pivot;

returnlow;

)

voidqSort(ElemenlTyper[],intlow,inthigh)

(

intpos;

if(low<high){

pos=partition(r,low,high);/*将r[Iow..high]一分为二*/

qSort(r,low,pos-1);/*对左边子表快速排序*/

qSort(r,pos+1,high);/*对右边子表快速排序*/

)

)

voidquickSort(ElementTyper[],intn){

qSort(r,1,n);

)

5.计算下图所示的AOE网中各顶点所表示的事件最早发生时间、最晚发生时间和各边所表示的

活动最早开始时间、最晚开始时间，找出关键路径并计算关键路径的长度。

(1)(5分)

各事件的最早发生时间和最晚发生时间:

vOvlv2v3v4v5v6v7v8

最早发生时间

最晚发生时间

各活动的最早开始时间和最晚开始时间:

ala2a3a4a5a6a7a8A9alOall

最早开始时间

最晚开始时间

(2)关键路径：；关键路径的长度：o(5分)

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

1.设计一个高效算法，删除顺序表中所有元素值为X的元素。假设顺序表的数据元素类型为整

型。要求：(1)用下面指定的顺序表结构；(2)时间复杂度为O(n)、空间复杂度为0(1)；(3)

算法用下面的函数原型表示。

/*顺序表结构*/

typedefintElementType;

typedefstruct{

ElementType*array;/*存放元素的数组*/

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

intcapacity;/*容量*/

(SeqList;

/*删除所有元素值为x的元素*/

voiddeleteAHX(SeqList*L,intx);

2.有两个单链表LA和LB,它们的元素均为非递减有序排列。编写一个算法，将它们合并成一

个单链表，要求合并后的单链表中的元素也是非递减有序序列，并且不需要额外申请结点空

间。例如，LA=(2,2,3),LB=(1,3,3,4),合并后为(1,2,2,3,3,3,4)。要求：(1)用下面指定

的链表结构；(2)算法用下面的函数原型表示。

/*链表结构*/

typedefstructNode{

ElementTypedata;

structNode*next;

[Node,*LinkList;/*LinkLisl为结构指针类型*/

/*两个单链表的合并。

LA表示第1个单链表，LB表示第2个单链表。相加到LA单链表*/

voidmergeList(LinkListLA,LinkListLB);

3.编写一个算法，完成对一棵二叉树的左右子树的交换。二叉树的存储结构如下：

typedefstructNode{

ElementTypedata;

structNode*left;

structNode*right;

)BTNode,*BTree;

4.暑假，小白准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为

了节省经费以及方便计划旅程，小白希望在出发之前知道任意两个城市之间的最短路径。请

设计算法帮助小白解决这个问题！

温州大学

2017年硕士研究生招生考试试题（A卷）

牛目代码及名称：831数据结构适用专业：081201计算机系统结构081202

计算机软件与理论

（请考生在答题纸上答题，在此试题纸上答题无效）

四、单项选择题（每小题3分，共45分）

1.线性表中的每一个元素都有一个前驱和后继元素。这个断言是（）。

A.正确的B.错误的

2.线性表的链接实现有利于（）运算。

A插入B.读表元C.查找D.定位

3.在一个带有头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

A.HL=p;p->next=HL;B.p->next=HL;HL=p;

C.p->next=Hl;p=HL;D.p->next=HL->next;HL->next=p;

4.字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）

个不同的字符串？

A.15B.14C.16D.21

5.采用链结构存储线性表时，其结点地址（）。

A.必须是连续的B.连续不连续都可以

C.部分地址必须是连续的D.必须是不连续的

6.队列的删除操作是在（）进行。

A.队首B.队尾C.队前D,对后

7.当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则退栈时，用（）语句

修改top指针。

A.top++;B.top=0;C.top—;D.top=N;

8.二叉树的第i层上最多含有结点数为（）。

A.TB.2^-1C.2iuD.2i+1-l

9.完全二叉树中，若一个结点没有左孩子，则它必是叶子。这个断言是（）。

A.正确的B.错误的

10.不使用递归也可实现二叉树的先序、中序和后序遍历。这个断言是（）。

A.正确的B.错误的

11.对于下图的AOE网中，计算顶点4所表示的事件最早发生时间丫以4）是（）。

A.6B.11C.12D.13

12.采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。这个断言是（）。

A.正确的B.错误的

13.已知数据序列为｛34,76,45,18,26,54,92,65｝,按照依次插入结点的方法生成一棵二叉排序

树，则该树的深度为（）。说明：如果树只有一个结点，深度为1。

A.4B.5C.6D.7

14.有一棵平衡二叉树，它的广义表表示为40（30,130（60,150））,在它中插入关键字50后，重新调整

得到一棵新平衡二叉树，在新平衡二叉树中，关键字60所在结点的左、右子结点的关键字分别是（）。

A.30,130B.30,150C.40,130D.50,130

15.对不稳定的排序算法，不论采用何种描述方式，总能举出一个说明它不稳定的实例来。这个断言

是（）。

A.正确的B.错误的

五、简答题（每个小问5分，共35分）

1.已知二叉树的后序遍历序列为41253,中序遍历序列为45213,则它的先序遍历序列？

2.以｛3,7,8,2,6,10,14）为，权值构造一棵Huffman树，这棵Huffman树的WPL?

3.对于下图，按照Kruskal算法构造它的-一棵最小生成树，拭写出在最小生成树中依次得到的各条边。

4.对一组关键字序列｛20,66,34,98,15,53,21,58,2,10,44,30｝,散列函数为H（key）=key%

13,表长为13。用线性探测法（F（i）=i）处理冲突，计算在等概率情况下查找成功的平均查找长度

和查找不成功的平均查找长度。

ASLSUCC=

^^•unsucc

5.给定关键字序列｛72,87,61,23,94,16,5,58｝,建小根堆。画出小根堆。

6.设一组初始记录关键字序列｛5,2,6,3,8）,以第一个记录关键字5为基准进行一趟快速排序的

结果？

六、算法填空题（每空2分，共30分）

1.本题针对线性表的链式存储结构，完成相应的算法。

typedefintElementType;

typedefstructNode{

ElementTypedata;

structNode*next;

}Node,*LinkList;

voidoutputList(LinkListL)/*输出带头结点的单链表*/

(

Node*p;

m；/*使p指向单链表的第i个结点*/

whHe(p!=NULL){

printf(p->data);

(2);/*p后移*/

)

)

voidinsertHead(LinkListL,ElementTypex)/*L指向头结点。在单链表中插入一个结点。头插法*/

(

/*开辟空间*/

___________L3)____________;

s->data=x;

/*链接*/

___________(42___________;

___________(5)___________;

2.下面是三元组表的存储结构及相应的算法，完成相应的算法。

typedefstruct{

introw,col;/*非零元素的行下标和列下标*/

ElementTypevalue;/*非零元素的值*/

{Triple;

#defineMAXSIZE1000/*非零元素个数最多为1000*/

typedefstrucl{/*非零元素的三元组表*/

Tripledata[MAXSIZE+1];/*data[0]不用*/

intm,n,number;/*矩阵的行数m,列数n和非零元素个数number*/

JTSMatrix;

/*采用”列序递增”法，将矩阵A转置为矩阵B*/

voidtransposeTSMatrix(TSMatrix*A,(6))

(

intcol,t,p;

B->m=A->n;

B->n=A->m;

B->number=A->number;

if(A->number>0)

(

p=0;/*记录下标*/

for(col=l;col<=___________(_22____________:col++){/*三元组表A的列值*/

/*从头至尾扫描三元组表A,寻找列为col的三元组进行转置*/

for((8);t<=(9);t++){

if(A->data[t].col==col){

_____oo)_____;

B->data[p].row=A->data[t].col;

B->data[p].col=A->data[t].row;

B->data[p].value=A->data[t].value;

)

)

)

3.下面是图的邻接表存储结构及相应的算法，完成相应的算法。

#defineMAXVEX100/*最大顶点数*/

typedefcharVirtexType;

structALGraphStruct;

typedefstructALGraphStruct*ALGraph;

typedefstructEdgeNode{

intadj\fertex;/*该边所指的顶点的位置*/

intweight;/*边的权*/

structEdgeNode*nextEdge;/*指向下一条边的指针*/

JEdgeNode;

typedefstructVNode{

XfertexTypedata;/*顶点信息*/

EdgeNode*firslEdge;/*指向第一条依附该顶点的边的弧指针*/

}VNode;

structALGraphStruct{

VNodevexs[MAXVEX];

intvertexNum,edgeNum;/*图的当前顶点数和弧数*/

)；

/*在无向网中插入一条边。

插入的边结点作为边链表的第1个结点。

如果待插入的边己存在，存储小权值。*/

voidaddEdge(ALGraphg,\fertexTypevl,\fertexTypev2,intw)

(

EdgeNode

inti=locate\fertex(g,vl);/*找顶点vl的位置*/

intj=locate\fertex(g,v2);/*找顶点vl的位置*/

if(i==-l||j==-l)

__________CID___________;

s=findEdge(g,i,j);

if(s!=NULL){

t=findEdge(g,j,i);

if(s->weight>w){

s->weight=w;

(12);

return;

)

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s・>adj\fertex=j;

s->weight=w;

__________03)___________;

g->vexs[i].firstEdge=s;

t=(EdgeNode*)malloc(sizeof(EdgeNode));

t->adj\fertex=i;

t->weight=w;

__________04)___________;

g->vexs[j].firstEdge=t;

(15);

七、算法设计题（共40分）

i.按照给定的函数原型完成冒泡排序。（io分）

/*冒泡排序（升序）*/

voidbubbleSort（intr[],intn）;

2.下面是顺序表的结构，设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复

杂度为0（1）。假设顺序表的数据元素类型为整型。（10分）

typedefintElementType;

typedefstruct{

ElementType*array;/*存放元素的数组*/

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

intcapacity;/*容量*/

JSeqList;

3.下面是哈夫曼树的存储结构，按照给定的函数原型完成求哈夫曼编码算法。（20分）

#defineN20/*叶子结点数*/

typedefstruct{

intweight;/*结点的权值*/

intparent;/*双亲的下标*/

intleft;/*左孩子结点的下标*/

intright;/*右孩子结点的下标*/

JHTNode,HTree;

/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/

/*第1个参数存储哈夫曼树，第2个参数存储哈夫曼编码，第3个参数是叶子数*/

voidcreateHuffmanCode（HTreeht[],char*hc[],intn）;

温州大学

2018年硕士研究生招生考试试题（A卷）

斗目代码及名称：831数据结构适用专业：081201计算机系统结构081202

计算机软件与理论

（请考生在答题纸上答题，在此试题纸上答题无效）

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

1.计算机所处理的数据一般具有某种内在联系，这是指（）。

A.数据和数据之间存在某种关系

B.数据元素和数据元素之间存在某种关系

C.数据元素内部具有某种结构

D.数据项和数据项之间存在某种关系

2.顺序存储方式只能用于线性结构，不能用于非线性结构。这个断言是（）。

A.正确的B.错误的

3.设某算法完成对n个元素进行处理，所需的时间是T（n）=100nlog2n+200n+500,则该算法的时间复

杂度是（）。

A.0（1）B.O（n）C.O（nlogn）D.O（nlogn+n）

4.采用顺序存储的两个栈它的共享空间为lop[i]代表第i个栈（i=l,2）的栈顶，栈1的底

在S[l],栈2的底在S[m],则栈满的条件是（）。

A.top[2]-top[l]=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.top[1]=top[2]

5.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有（）个。

A.99B.100C.101D.102

6.无向图G有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3,则图

G至少有（）个顶点。

A.10B.11C.12D.13

7.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。

A.nB.（n-l）/2C.n-1D.n2

8.适合于折半查找的表的存储方式及元素排列要求为（）o

A.链接存储，元素无序B.链接存储，元素有序

C.顺序存储，元素无序D.顺序存储，元素有序

9.排序算法的稳定性是指（）.

A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C.排序算法的性能与待排序元素的数量关系不大

D.排序算法的性能与待排序元素的数量关系密切

10.5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。

A.8B.14C.15D.25

九、简答题（4小题，每小题10分，共40分）

1.找出满足以下条件的所有二叉树：（1）二叉树的前序序列与中序序列相同；（2）二叉树的中序序列

与后序序列相同；（3）二叉树的前序序列与后序序列相同。

2.假设通讯电文中只用到A,B,C,D,E,F六个字母，它们在电文中出现的相对频率分别为：8,

3,16,10,5,20。（1）构造哈夫曼树。（2）计算该哈夫曼树的带权路径长度WPL。

3.己知序列{355,672,91,83,781,34,410,76,125,320},建大根堆。

4.已知序列{12,2,16,30,8,28,4,10,20,6,18},请按照下面的快速排序算法，给出该序列作升序排列

时前三趟的结果。

intpartition(ElementTyper[],intlow,inthigh)

intpivot;

pivot=r[low];

while(low<high){

while(low<high&&r[high]>=pivot){

high-;

)

r[low]=r[high];

while(low<high&&r[