2012年全国硕士研究生统一入学考试自命题试题

2012年全国硕士研究生统一入学考试自命题试题

学科与专业名称：计算机技术，软件工程

考试科目代码与名称：830数据结构

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上•律不给分。

―-选择题（每题2分，共30分）

1.队列操作的原则是（）。

A.先进先出B.后进先出C.只能进行插入D.只能进行删除

2.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）o

A.edcbaB.decbaC.dceabD.abode

3.采用顺序查找法查找长度为n的线性表时,每个元素的平均查找长度为（）。

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

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

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

5.设单链表中指针p指着结点A,若要删除A之后的结点（若存在），则需要修改指针的操作为

（）。

A.p->next=p->next->nextB.p=p->next

C.p=p->next->nextD.p->next=p

6.在内部排序中，排序时不稳定的有（）。

A.插入排序B.冒泡排序C.快速排序D.归并排序

7.在AOE网中，完成工程的最短时间是（）。

A.从源点到汇点的最长路径的长度B.从源点到汇点的最短路径的长度

C.最长的回路的长度D.最短的回路的长度

8.以下（）方法所用辅助存储空间最大。

A.堆排序B.希尔排序C.快速排序D.归并排序

9.具有8个顶点的无向图至少应有（）条边才能确保是一个连通图。

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

10.对具有n个结点的有序表中折半查找时，其时间复杂度是（）。

A.O（nlog2n）B.O（log2n）C.O（n）D.O（n2）

11如果希望对平衡二叉树遍历的结果是升序的，应采用（）遍历方法。

A.先序B.中序C.后序D.层次

考试科目：数据结构共5页，第1页

12.稀疏矩阵一般的压缩存储方法有两种，即：（）。

A.二维数组和三维数组B.三元组和散列

C.三元组和十字链表D.散列和十字链表

13.循环队列中是否可以插入下一个元素（）。

A.与曾经进行过多少次插入操作有关.

B.只与队尾指针的值有关，与队头指针的值无关.

C.只与数组大小有关，与队首指针和队尾指针的值无关

D.与队头指针和队尾指针的值有关.

14.在线索化二叉树中，T所指结点没有左子树的充要条件是（）。

A.T->left=NULLB.T->ltag=l

C.t->ltag=l且t->left=NullD.以上都不对

15.以下说法中不正确的是（）。

A.无向图中的极大连通子图称为连通分量

B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D.有向图的遍历不可采用广度优先搜索方法

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

1.一组记录（50,40,95,20,15,70,60,45,80）进行冒泡排序时，第一趟需进行相邻

记录的交换的次数为。

2.数据结构按逻辑结构可分为两大类，它们分别o

3.由n个权值构成的哈夫曼树共有个结点。

4.在散列表（hash）查找中，评判一个散列函数优劣的两个主要条件是：

和O

5.单链表中设置头结点的作用是o

6.一棵深度为k的满二叉树的结点总数为,一棵深度为k的完全二叉树的结

点总数的最小值为»

7.一个无向图有n个顶点和e条边，则所有顶点的度的和为。

8.在二叉链表中判断某指针p所指结点为叶子结点的条件是。

9.堆栈是一种操作受限的线性表，它只能在线性表的进行插入和删除操作，对栈的

访问是按照的原则进行的。

10.若某记录序列的关键字序列是（235,346,021,558,256）,用链式基数排序方法排序,

第一次收集的结果是o

考试科目：数据结构共5页，第2页

三.判断题（每题1分，共10分，正确的选3错误的选f）

1.如果T2是由树T1转换而来的二叉树，那T1中结点的先序就是T2中结点的先序。（）

2.在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。

（）

3.线性表中的每一个元素都有一个前驱和后继元素。（）

4.按中序遍历一颗二叉排序树所得到的中序遍历序列f是一个递增序列。（）

5.若网中有几条关键路径，提高一条关键路径上的活动的速度，不能导致整个工程缩短工期。

（）

6.一颗满二叉树同时又是一颗平衡树。（）

7.数据结构是研究数据的物理结构、逻辑结构以及它们之间的相互关系。（）

8.拓扑排序是一种内部排序的算法。（）

9.已知一颗树的先序序列和后序序列，一定能构造出该树。（）

10.n阶对称矩阵可压缩存储到产/2个元的空间中。（）

四.简答题(50分)

1.给定关键字序列T=(65,57,45,39,12,98,86,35),采用快速排序算法，以第一个

元素为枢轴，对该序列由小到大排序，并写出具体排序过程。(8分)

2.简述下列算法的功能。(6分)

voidProcess(LinkList&L,intx,inty){//L线性表的元素递增有序排列

LinkListp=L,q,s;

if((p->next)&&(x<=y))

{while(p->next&&p->next->data<=x)p=p->next;

If(p->next)returnERROR;

q=p->next;

while(q->next&&q->next->data<y)

{s=q;q=q->next;free(s);}

p->next=q->next;

free(q);

3.使用克鲁斯卡尔算法构造出图1所示的图G的一棵最小生成树（要求写出构造过程）。（10

分）

考试科目：数据结构共5页，第3页

4.已知一个图如图2所示，若从顶点a出发，按深度优先搜索法进行遍历，写出可能得到

的一种顶点序列；按广度优先搜索法进行遍历，写出可能得到的一种顶点序列。（4分）

5.给定图3所示带权有向图及其邻接矩阵,利用Floyd算法，求每一对顶点之间的最短路

径及其路径长度（要求写出求解过程）。（12分）

0812

603

580

X

图3

6.给出一组关键字的序列为｛12,15,34,37,39,22,38,66,74,80,107）,假设哈

希函数为Hash（key）=keymod11,画出按照链地址法处理冲突构造所得的哈希表，并在记录

的查找概率相等的前提下，计算成功查找的平均查找长度。（10分）

五.算法填空，(每空2分，共16分)

1.下面的算法将元素e加入队列Q中，请在处填上适当内容，使其成为一个完整算

法。

typedefstructQNode{

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;

typedefstruct{

QueuePtrfront;//队头指针

QueuePtrrear;//队尾指针

)LinkQueue,*LinkQueuePtr;

BooleanEnQueue(LinkQueuePtrQ,QElemTypee){〃元素e加入到队列Q中

p=;

if(!p)returnFALSE;

考试科目：数据结构共5页，第4页

p->data=e;

p->next=:

_______=P；

Q->rear=;

returnTRUE;

2.下面是先序遍历二叉树的算法非递归算法，请在处填上适当内容，使其成为一个

完整算法。

typedefstructBiTNode{//结点结构

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指针

}BiTNode,*BiTree;

voidPreOrderTraverse(BiTree,Status(*Visit)(TElemType)){

〃采用二叉链表存储结构,Visit是对结点操作的应用函数

InitStack(S);

BiTreep=T;

while(){

if(p){Visit(p->data);

p=p->lchild;

)

else{;

P=:

六.编写算法（24）

I.试编写统计二叉树中叶子结点个数的算法。（10分）

2.设计一个图的数组表示存储结构，并编写采用数组表示法构造一个无向网的算法。（14分）

考试科目：数据结构共5页，第5页

2014年招收攻读硕士学位研究生入学考试试题（A卷）

招生专业与代码：计算机系统结构081201,计算机软件与理论081202,计算机应用技术

081203,软件工程083500,计算机技术（专业学位）085211,软件工程（专业学位）085212

考试科目名称及代码：数据结构830

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上•律不给分。

一.选择题（每题2分，共30分）

1.数据结构是研究数据的（）以及它们之间的相互关系.

A.理想结构，物理结构B.理想结构，抽象结构

C.物理结构，逻辑结构D.抽象结构，逻辑结构

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

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

3.从一个长度为n的顺序表中删除第i个元素（IWiWn）时，需向前移动（）个元素.

A.n-iB.n-i+1C.n-i-1D.i

4.具有n个顶点的完全有向图的边数为（）.

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

5.快速排序在（）情况下最不利于发挥其长处.

A.被排序的数据量太大.B.被排序数据中含有多个相同的关键字.

C.被排序的数据完全无序D.被排序的数据已基本有序

6.线性表采用链式存储时，其地址（）.

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续与否均可以

7.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）

A.edcbaB.decbaC.dceabD.abcde

8.采用顺序查找法查找长度为n的线性表时,每个元素的平均查找长度为（）

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

9.下列哪种排序需要的附加存储开销最大（）.

A快速排序B堆排序C归并排序D插入排序

10.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图.

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

11.对具有n个结点的有序表中折半查找时，其时间复杂度是（）.

A.O（log2n）B.O（nlog2n）C.O（n）D.O（n2）

12.通过一趟排序就能从整个记录序列中选择出具有最大（或最小）关键字的记录，这种排序

方法是（）.

A.归并排序B.快速排序C.直接插入排序D.堆排序

考试科目：数据结构共4页，第1页

13.在AOE网中，完成工程的最短时间是（）.

A.从源点到汇点的最短路径的长度B.从源点到汇点的最长路径的长度

C.最长的回路的长度D.最短的回路的长度

14.设单链表中指针p指着结点A,若要删除A之后的结点（若存在），则需要修改指针的操作为

（）.

A.p->next=p->next->nextB.p=p->next

C.p=p->next->nextD.p->next=p

15.下面的序列中，（）是堆.

A.1,2,8,4,3,9,10,5B.1,5,10,6,7,8,9,2

C.9,8,7,6,4,8,2,1D.9,8,7,6,5,4,3,7

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

1.线性结构中元素之间存在一对一关系，树型结构中元素之间存在关系，

图型结构中元素之间存在关系.

2.单链表中设置头结点的作用是.

3.由n个权值构成的哈夫曼树共有个结点.

4.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法

是•

5.队列只允许在表的一端插入，在另一端删除;插入的一端叫，删除的一端叫；

对队列的访问是按照的原则进行的.

6.在哈希查找方法中，要解决两方面的问题，它们分别是及

三.判断题（每题1分，共10分，正确的选t,错误的选f）

1.已知一颗树的先序序列和后序序列，一定能构造出该树.（）

2.双循环链表中，任一结点的前驱指针均为不空.（）

3.对于n个记录的集合进行冒泡排序，在最坏情况下的时间复杂度是0（n）（）

4.快速排序是排序算法中最快的一种.（）

5.设有序的关键字序列是（2,5,8,9,12,14,16,18,20,22,25）,当用折半查找方

法查找关键字22时，需经3次比较运算.（）

6.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h.（）

7.散列法存储的思想是由关键字值决定数据的存储地址。（）

8.连通图的广度优先搜索中可以采用队列来暂存刚访问过的顶点.（）

9.一棵m阶B-树中每个结点最多有m棵子树，非终端结点最少有2棵子树.（）

10.冒泡排序是稳定的.（）

考试科目：数据结构共4页，第2页

四.简答题（共45分）

1.已知一棵二叉树的中序为CDBAGFHE,后序为DCBGHFEA,画出这棵二叉树.（6分）

2.如图1所示的AOE网（VI表示工程的开始,V8表示工程的结束），假设工程从时间0开始,

求出所有事件和活动允许发生的最早及最晚时间，并给出关键路径.（14分）

3.简述下列算法的功能.(6分)

voidprocess(Sqlist&L)//L为线性表,用顺序存储结构表示

{inti=0,j;

While(i<L.length&&L.elem[i]!=X)

i++；

for(j=i+l;j<L.length;j++)

if(L.elem[j]!=X)

{L.elem[i]=L.elem[j];

i++;}

L.length=i;

)

4.己知一棵3阶的B-树如图2所示，依次插入关键字30及90,分别画出每插入一个关键字后

考试科目：数据结构共4页，第3页

5.已知序列(12,178,200,530,765,149,52,6),请采用链式基数排序方法对该序列作升序

排序，给出排序过程.(12分)

五.算法填空，(每空2分，共20分)

1.以下算法功能是：插入元素e为新的栈顶元素,完成算法的空格部分.

StatusPush(SqStack&S,ElemTypee){

if(S.top-S.base>=S.Stacksize){

S.base=(ElemType*)realloc(S.base,

(S.Stacksize+STACKINCREME)*_______Q________)；

if(②)exit(OVERFLOW);

S.top=S.base+;

S.Stacksize=S.Stacksize+STACKINCREMENT;

)

*S.top=(4);

top=®;

returnOK;

)

2.以下是图的广度遍历算法，完成算法的空格部分.

VoidBFSTraverse(GraphG,Status(*visit)(intv)){

for(v=0;v<G.vexnum;++v)visited[v]=False;

initQueue(Q);

for(v=0;@;++v)

if(!visited[v]){

visited[v]=True;Visit(v);

EnQueue(Q,v);

while(IQueueEmpty(Q)){

⑦_________；

for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))

if(⑧){

Visited[w]=®;Visit(w);

⑩；

)

)

)

)

六.编写算法(25分)

1.设计将两个有序链表合并为一个有序链表的算法.假设有序链表的元素按照非递减排

列.(10分)

2.给定带权有向图G和源点V。，设计V。到其余顶点的最短路径.(15分)

考试科目：数据结构共4页，第4页

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

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

1.线性表采用链式存储时，其地址（）。

A.必须是连续的B.部分地址必须是连续的

C.一定是不连续的D.连续与否均可以

2.若有一个栈的输入序列是1,2,3,…，n,输出序列的第一个元素是n,则第i个输出元素

是（）。

A.n-iB.n-i-lC.n-i+1D.不确定

3.己知单链表上一结点的指针为p,则删除该结点后继的正确操作语句是（）。

A.s=p->next;p=p->next;free（s）;B.p=p->next;free（p）;

C.s=p->next;p->next=s->next;free（s）;D.p=p->next;free（p->next）;

4.若使用邻接矩阵表示某有向图，则矩阵中非零元素的个数等于（

A.图中顶点的数目B.图中边的数目

C.图中边的数目的两倍D.无法确定

5.下列哪种排序需要的附加存储开销最大（）«

A.快速排序B.堆排序C.归并排序D.插入排序

6.下面哪一方法可以判断出一个有向图是否有环（即回路）（）。

A.拓扑排序B.求最短路径C.求最小生成树D.广度优先遍历

7.具有n个顶点的无向图至少应有（）条边才能确保是一个连通图.

A.n-1B.nC.n+1D.2n

8.对线性表进行折半查找时，要求线性表必须（）。

A.以顺序方式存储B.以顺序方式存储,且结点按关键字有序排序

C.以链接方式存储D.以链接方式存储，且结点按关键字有序排序

9.若使用二叉链表作为树的存储结构，在有n个结点的二叉链表中非空的链域的个数为（）。

A.n-1B.2n-lC.n+1D.2n+l

10.在内部排序中，排序时不稳定的有（）。

A.插入排序B.冒泡排序C.快速排序D.归并排序

11.一个具有500个结点的完全二叉树具有一个孩子的结点个数最多为（）。

A.1B.250C.0D.249

2016年全国硕士研究生统一入学考试自命题试题（A卷）

学科、专业名称：计算机科学与技术、软件工程

研究方向：计算机系统结构081201,计算机软件与理论081202,计算机应用技术081203,

软件工程083500,计算机技术（专业学位）085211,软件工程（专业学位）085212

考试科目名称及代码：数据结构830

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

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

1.在线索化二叉树中，T所指结点没有左子树的充要条件是（）。

A.T->lchild=NULLB.T->ltag=l

C.t->ltag=l且t->Ichiki=NullD.以上都不对

2.一个带有头结点的单链表为空的判定条件是（）。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

3.线性链表不具有的特点是（）o

A.随机访问B.不必预估所需存储空间大小

C.插入与删除时不必移动元素D.所需空间与线性表长度成正比

4.在下面的排序方法中，稳定的是（）。

A.希尔排序B.堆排序C插入排序D.快速排序

5.设有n个待排序的记录关键字，则在堆排序中需要（）辅助记录空间。

A.0(1)B.0(n)C.0(nlog2n)D.0(n2)

6.数组A[5][6]的每个元素占5个字节,将其按行优先次序存储。假设元素的

存储地址为1000,则元素A[5,5]的存储地址为（）。

A.1140B.1145C.1120D.1125

7.高度为n的完全二叉树的结点数至少为（）。

A.2向B.2nl+1C.2nD.2n+l

8.设有一个无向图6=（V,E）和G'=（V'，E'）,如果G'为G的生成树，则下面不正确

的说法是（）。

A.G'为G的子图B.G'为G的连通分量

C.G'为G的极小连通子图且V'=VD.G'为G的一个无环子图

9.在有向图的邻接表存储结构中顶点V在表结点中出现的次数是（）。

A.顶点V的度B.顶点V的出度

C.顶点V的入度D.依附于顶点V的边数

10.关键路径是事件结点网络中（）。

A.最短的回路B.从源点到汇点的最短路径

C.最长的回路D.从源点到汇点的最长路径

考试科目：数据结构共5页，第1页

11.一个有n个结点的无向图最多有（）条边。

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

12.对某个无向图的邻接矩阵来说，（）。

A.第i行上的非零元素个数和第i列的非零元素个数一定相等

B.矩阵中的非零元素个数等于图中的边数

C.第i行上，第i列上非零元素总数等于顶点Vi的度数

D.矩阵中非全零行的行数等于图中的顶点数

13.平衡二叉树的平均查找长度是（）o

A.0（n2）B.O（nlog2n）C.0（n）D.O（log2n）

14.下列哪种排序需要的附加存储开销最大（）。

A.快速排序B.堆排序C.归并排序D.插入排序

15.设一数列的顺序为1,2,345,6,通过栈操作可以得到（）的输出序列。

A.3,2,5,6,4,1B.1,5,4,6,2,3

C.6,4,3,2,5,1D.3,5,6,2,4,1

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

1.在一个长度为n的顺序表中删除第i个元素时，需向前移动个元素。

2.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针

则执行出队操作时front指针的值应更新为front=。

3.在单链表中，若要删除指针p所指结点的后一结点，则需要执行下列语句：（设q为指针

变量）q=p->next;；。

4.在有n个结点的二叉链表中，值为NULL的链域的个数为。

5.二叉树中度为0的结点数为30,度为1的结点数为30,总结点数为。

6.在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为，整个

堆排序过程的时间复杂度为。

7.对于n个记录（假设每个记录含d个关键字）进行链式基数排序,总共需要进行趟

分配和收集。

8.设有向图G中有向边的集合£={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},则该图的

一种拓扑序列为。

三.判断题（每题1分，共10分，正确的选3错误的选f）

1.在n个顶点的无向图中，若边数>n-l,则该图必是连通图。（）

2.具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（）

3.使用散列法存储时，哈希表的大小可随意选取，通常取10的倍数。（）

4.向一个二叉排序树插入新的结点时，新插入的结点总是叶子结点（）

5.数据元素是数据的最小单位。（）

6.普里姆（Prim）算法相对于克鲁斯卡尔（Kruskal）算法更适合求一个稀疏图G的最小生成树。

（）

7.向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。（）

8.向一棵B-树插入元素的过程中，若最终引起树根结点的分裂，则新树高度为原树的高度

加1。（）

9.无向图的邻接矩阵一定是对称阵。（）

10.对小根堆进行层次遍历可以得到一个有序序列。（）

考试科目：数据结构共5页，第2页

四.简答题（45分）

1.已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKIJD,求解

下列问题：

（1）画出此二叉树。（4分）

（2）将该二叉树转换成森林。（4分）

2.设有一组关键字（71,23,73,14,55,89,33,43,48）,采用哈希函数：H（key）=key%10,采

用开放地址的二次探测再散列方法解决冲突，试在散列地址空间中对该关键字序列（按从左

到右的次序）构造哈希表，并计算在查找概率相等的前提下，成功查找的平均查找长度。

（7分）

3.设有一组初始记录关键字为（3,1,4,6,8,2,5）,要求构造一棵平衡二叉树，并给出构造过程。

（5分）

4.对图1所示的无向加权图完成下列要求：

（1）写出它的邻接表；（5分）

（2）按克鲁斯卡尔（Kruskal）算法求其最小生成树，并给出其过程。（6分）

（3）给出从顶点a开始的深度优先搜索序列和深度优先生成树。（4分）

5.已知序列（142,543,123,65,453,879,572,434,111,242,811,102）。

（1）采用希尔排序对该序列作升序排序，请给出第一趟排序的结果（初始步长为7）。（5分）

（2）采用堆排序对该序列作升序排序，请给出初始堆以及第一趟排序的结果。（5分）

五.算法填空，（每空2分，共20分）

1.下面算法实现对一个不带头结点的单链表L进行就地（不增加额外存储空间）逆置。请

在________处填上适当内容，使其成为一个完整算法。

typedefintDataType;

typedefstruct{

DataTypedata;

structNode*next;

}Node;

typedefNode*LinkList;

考试科目：数据结构共5页，第3页

LinkListReverse(LinkListL)

(

LinkListp,q;

if(!L)return;〃链表为空返回

p=L->next;q=L->next;L->next=NULL;

while(q)

(

q=q->next;

(1)

⑵

p=q;

)

returnL;

)

2.下面是一个采用二叉链表存储结构，中序遍历线索二叉树T的算法。Visit是对结点操

作的应用函数。请在__________处填上适当内容，使其成为一个完整算法。

/*二叉树的二叉线索存储表示*/

TypedefenumPointerTag{Link,Thread};

typedefstructBiThrNode{

TelemTypedata;

structBiThrNode*lchild,*rchild;

PointerTagLTag,RTag;

}BiThrNode,*BiThrTree;

StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TelemTypee))

(

BiThrNode*p;

D=(3)______

while(p!=T){〃空树或遍历结束时p==T

while(p->LTag==Link)(4)

if(!Visit(p->data))returnERROR;

while(p->RTag==Thread&&

(

(6)

Visit(p->data)；

)

⑺

)

returnOK;

考试科目：数据结构共5页，第4页

3.下面是一个利用递归对二叉排序树进行查找的算法。请在__________处填上适当内容,

使其成为一个完整算法。

typedefstructBTreeNode{

TelemTypedata;

structBTreeNode*lchild,*rchild;

)BTreeNode;

boolFind(BTreeNode*T,TelemType&item)

(

if((8))

returnFALSE;〃查找失败

else{

if(item==T->data)〃查找成功

returnTRUE;

elseif(item<T->data)

returnFind((9),item);

else

returnFind((10),item);

)

六.编写算法（25分）

1.设有一组初始记录关键字序列（K”上，…，KQ,要求设计一个算法能够在O（n）的时

间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K”右半部分的

每个关键字均大于等于Ki。（10分）

2.设有一整型数组w保存n个字符的权值（均大于0）,请写出

（1）构造赫夫曼树（Huffman）的算法。（8分）

（2）求各字符赫夫曼编码的算法。（7分）

考试科口：数据结构共5页，第5页

2017年全国硕士研究生统一入学考试自命题试题（B卷）

学科、专业名称：计算机科学与技术、软件工程

研究方向：计算机系统结构081201,计算机软件与理论081202,计算机应用技术081203,

软件工程083500,计算机技术（专业学位）085211,软件工程（专业学位）085212

考试科目名称及代码：数据结构830

考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

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

1.一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1

2.循环队列用数组存放其元素值，已知其头尾指针分别是front和rear,则当前队列中

的元素个数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front

3.平衡二叉树的平均查找长度是（）。

A.0（n2）B.O（nlog2n）C.0（n）D.O（log2n）

4.设F是由Tl、T2和T3三棵树组成的森林，与F对应的二叉树为B,TI、T2和T3的结点

数分别为Ni、N2和N3,则二叉树B的根结点的左子树的结点数为（）。

A.Ni-1B.N2-lC.N2+N3D.N1+N3

5.计算机内部数据处理的基本单元是（）。

A.数据B.数据元素C.数据项D.数据库

6.设按照从上到下、从左到右的顺序从1开始对完全二叉树的结点进行顺序编号，则编号为i

结点的左孩子结点的编号为（

A.2i+lB.2iC.i/2D.2i-l

7.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。

A.第i行非0元素的个数之和B.第i列非0元素的个数之和

C.第i行。元素的个数之和D.第i列0元素的个数之和

8.设一组初始记录关键字序列为（16,25,12,30,47/1,23,36,9,18,31）,则以增量d=5的一趟希尔

排序结束后的结果为（）。

A.11,23,12,9,18,16,25,36,30,47,31B.11,23,12,9,16,18,25,36,47,30,31

C.16,23,12,9,11,18,25,36,30,47,31C.9,11,12,16,18,23,25,30,36,47,31

9.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

A.nB.n-1C.mD.m-1

10.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树中总共有

（）个空指针域。

A.2m-1B.2mC.2m+lD.4m

11.对于线性表（7,34,55,25,64,46,20,10）进行散列存储时，若选用H（K）=K%9作

为散列函数，则散列地址为1的元素有（）个。

A.1B.2C.3D.4

考试科目：数据结构共5页，第1页

12.下面程序的时间复杂为（）。

for（i=l,s=0；i<=n；i++）{t=l；for（j=l；j<=i；j++）{t=t*j；s=s+t；}}

A.O（n）B.O（n2）C.O（n3）D.0（n4）

13.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（）。

A.0B.1C.nD.n+1

14.设无向图G中边的集合E={（a,b）,（a,e）,（a,c）,（b,e）,（e,d）,（d,f）,（f,c）},则从顶点a出

发进行深度优先遍历可以得到的一种顶点序列为（）o

A.aebcfdB.acfebdC.aedfcbD.aedfbc

15.设指针变量p指向双向链表中结点A,指针变量s指向被插入的结点X,则在结点A的后

面插入结点X的操作序列为（）。

A.p->next=s；s->prior=p；p->next->prior=s；s->prior=p->nest；

B.s->prior=p;s->next=p->next;p->next=s;s->next->prior=s;

C.p->prior=s；p->nest->prior=s；s->prior=p；s->next=p->prior；

D.s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；

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

1.采用堆排序、快速排序、冒泡排序，对初态为有序的表，最省时间的是。

2.设一组初始记录关键字序列为（49,38,65,97,76,13,27,50）,则第4