数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年

《数据结构》试卷（A卷）（考试时间：100分钟）

填空（每空2分，共40分）

..数据结构式具有相同性质的数据元装的（I）。

2.通常程序在调用另•个程序时，都需要使用•个（2）来保存被调用程序内分配的局部变卜、形式参数的

存储空间以及返回地址。

3.有6行8列的二维数组A,每个元素川相邻的6个字节存储，存储册按字节编址，已知A的起始存储地址（基址）

为1000.在行优先存储和列优先々贮情况下A［5.5］的存储地址分别为（3）一.<4）。

4.完全二叉树第4个节点的父节点是第（5）节点,左孩子是第（6）个节点。如果该二叉树有10层，

刚共有⑺个节点.

5.请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队

满的条件分别分：⑻.（9）.

6,字符串t="child"，s="cake”,请写出下歹ij函数的结果:StrLength（t）=（10）;Concat（SubString（s,3,1）,

SubString（t,2,2））=（11）.

£一棵二叉树为

则后序序列为（12）,中序序列为（13）,先序序列为（14）°

8.请用数据序列［53,17,12,66,58,70,87,25,56,60}构造一棵二义排序树（15）-

9.。一个栈输入的序列式1,2,3,则可能的且以2为开头的输出序列是（16）,不可能的序列是U7）.

10.有n个结点的无向完全图的边数分别为（18）。

11.要从数据：2,3,4,8,9,11,13查找H,若采用折半查找法，则在（19）次比较后,才找到该数据。

2在直接插入排序、哥尔排序、冒泡排序和快速排序中，平均情况下（入）一最快。

二简答题:

1给定{15,3,14,2,6,9,16,17）,试为这8个数设计哈夫曼编码,并计

和其带权路径长度。

2请对卜图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使

用图画出每一步过程）。

3假定存在数据表：（3,4,5,7,24,30,54,63,72,87,95,102）,请解决如下问题：

假设哈希函数为：H（key）=keymod13,用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出

存放状态：

4森林和二叉树的转换，画出和下列二叉树相应的森林

殳要将序列（46,79序6,38,40,84）中的关键码按升序重新排列，写出快速排序的过程。（每•步过程）

三程序题（10分）

编写算法判别给定二叉树是否为完全二叉树

《数据结构》（A卷）答案

填空（每空2分，共40分）

1.集合。

2.递归工作栈。

3.1270,1210.

4.2,8,1023o

5.Q.front==Q.rear,Q.front==（Q.rear+1）%10»

6.5,“iak”.

DECB1IGFA,BDCEAFHG,ABCDEFGH

8.

9.231或213,312。

10.n(n-l)/2«

11.2。

12.快速排序.

二.简答题（每题10分，共50分）

..图不唯-WPL=229

3.

0123456789101112

：02543453077287952463

4.

5.

(46,79,56,38,40,84)

(40,38,46,56,79,84)

(38,40,46,56,79,84)

三.程序题(10分)

.ntIsFull_Bitree(BitreeT)〃判断二叉树是否完全二叉树，是则返回1,否则返回0

(InitQueue(Q);flag=0;

EnQueue(Q,T)：〃建立工作队列

while(!QueueEmpty(Q))

{DeQueue(Q,p);

if(!p)flag=l;〃如果孩子为空，则说明左孩子为空

elseif(flag)return0:

else

(

EnQueue(Q,p->lchild):

EnQucue(Q,p->rchild):〃不管孩子是否为空,都入队列

|

}//while

return1;

j//IsFull_Bitree

中国矿业大学2011-2012学年

《数据结构》试卷（B卷）（考试时间：100分钟）一.填空（每空2分，共40分）

:.数据结构是指数据及其相互之间的°当结点之间存在M对N（M：N）的联系时，称这种结构为

2.通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储

空间以及返回地址。

3.有6行8列的二维数组A,每个元素用相邻的6个字节存储，存储器按字节编址，己知A的起始存储地址（基址）

为1000,在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_

4.设目标T="abccdcdccbaa"，模式P="cdcc”，则第次匹配成功。

5.请描述在循环队列中,(队列用Q表示,队头和队尾指针分别由front和rear表示，该队列有MS个存储空间)，

判断队空和队满的条件分别分：____________,。

6.对于一个长度为n的单链存储的线性表，在表头插入元素的时间豆杂度为，在表尾插入元素的时间且

杂度为____________.

二在具有n个单元的循环队列中，队满时共有个元素。

8.深度为k的二叉树的结点总数，最多为一个。最少为个。

9二叉树中元素按照顺序存储方式存放在如卜・•维数组中，则结点G所在层次为°

01234567891011121314

ABCDEFGHIJ

10.有n个结点的无向完全图和有向完全图的边数分别为.

11.图的深度优先遍历算法类似于树的»

12.要从序列{1,3,5,7,9,11,13}中查找11,若采用折半查找法，则在次比较后，才找到该数据。

13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下____最快，其时间更杂度为_________。

二简答题：(每题10分，共50分)

1.假设9个字母为：ABCDEFGI,权值分别为5,13,7,4,20.34,16,9,8。试为这9个字母设计哈夫

越编码。并计算其带权路径长度。

2.已知一个图的顶点集V和边集E分别为：

V=(1,2,3,4,5,6,7};

E={<2,1>,<3,2>,<3,6〉，<4,3>,<4,5>,<4,6〉，<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}：

若存储它采用邻接表，试写出临界表。并且仔个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，

或拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

3.intPrimo(intn)

{inti=l：

intx=(int)sqrt(n);

while(++i<=x)

if(n%i==0)break:

if(i>x)return1;

elsereturn0;}

(1)指出该算法的功能；

(2)该算法的时间豆杂度是多少？请说明。

4.假定存在数据表；(3,4,5,7,24,30,54,63,72,87,95,102),请解决如下问题；

1)假设哈希函数为：H(key)=keymodl3,用该哈希函数将数据表存入长度为13的哈希表，(利用线性探测)

请画出存放状态；

2)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数；

5设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则写出希尔(shell)

律序的过程，初始步长为4

三程序题

清写出折半查找方法的函数Search_Bin(SSTableS,valuev).要求：

1）函数名使用给出的函数名，参数SSTable表示序列,使用一维数组存放，下标从0开始，value表示要查找的

谊：

2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1：

3）不用写出主困数与相关定义，如果使用其他函数，请注明函）数用途。

中国矿业大学2011-2012学年

《数据结构》试卷（B卷）（答案）

专业：班级：序号：姓名：

一.填空（每空2分，共40分）

1.联系.图（或图结构）.

2.通常程序在调用另•个程序时，都需要使用•个」［L来保存被调用程序内分配的局部变送、形式参数的存储空

间以及返回地址。

3.有6行8列的二维数组A,每个元素川相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）

为1000,在行优先存储和列优先存贮情况下A［5,5］的存储地址分别为1270,1210

<,设目标T="abccdcdccbaa”，模式叫“cdcc"，则第次匹配成功。

5.清描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），

判断队空和队满的条件分别分：_Q.front==Q.rear,Q.front==（Q.rea^+1）%MS_«

6.0（1）0（n）_o

7.在具有n个单元的循环队列中，队满时共有n-1个元索。

8.深度为k的二叉树的结点总数，最多为2T个。最少为k个。

9二叉树中元索按照顺序存储方式存放在如卜.•维数组中，则结点G所在层次为30

01234567891011121314

ABCDEFGHIJ

10.有n个结点的无向完全图和有向完全图的边数分别为n（n1）/2,n（n-l）____.

11.图的深度优先遍历算法类似于树的先序.

12.要从序列｛1,3,5,7,9,11,13｝中查找11,若采用折半查找法，则在2次比较后,才找到该数据。

13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下最快，其时间且杂度为。快

速排序,0（n1gn）

二简答题：（每题10分，共50分）

1.假设9个字母为：ABCDEFGF,权值分别为5,13,7,4,20,34,16,9,8。试为这9个字母设计哈夫

员编码。并计算其带权路径长度。

116

6848

34342820

18161513

9978

54

2.拓朴排序为：4365721

3.(1)判断n是否是素数(或质数)

⑵0

4.假定存在数据表：(3,4,5,7,24,30,54,63,72,87,95,102),请解决如下问题：

1)假设哈希函数为：H(key);keymod13,用该哈希函数将数据表存入长度为13的哈希表，(利用线性探测)

请画出存放状态：

0123456789101112

102543453077287952463

24,63,102共计比较了3次

2)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数：

5设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关捱码按字母序的升序重新排列，则

写出希尔(shell)排序的过程，初始步长为4

ShellP,A,C,S,Q,D,F,¥,R,II,M,

C,A,,FD,M,H,P,S,Q,¥,R,

ACDFIIMPQRSY

三程序题

清写出折半查找方法的函数Search_Bin(SSTableS,valuev).要求：

1)函数名使用给出的函数名，参数SSTable表示序列，使用一维数组存放，下标从0开始，value表示要查找的

道：

2)如果找到，则函数返回值为该数在序列中的位置，否则返回T:

3)不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。

见课本

Intsearch(arrayST,Keykey)

Low=1;high<=high;

Vhile(low<high){

Nid=(low+high)/2;

If(key=array[mid],key)returnmid;

Elseif(key<array[mid],key)high=mid-l;

Elselow-mid+1;}return0)

计第机学院2010-2011学年第一学期

《数据结构》试卷(A卷)(考试时间：100分钟)

专业：班级：序号：姓名：

一.填空(每空2分，共40分)

1.双向循环健表中，P指针所指向的结点的前驱指针域和后继指针域分别用“ior和nexl表示，删除P指针所指

向的结点，则其基本操作为_______,free（p）.

2.通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储

空间以及返回地址。

3.有6行8列的二维数组A,每个元索用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）

为1000,在行优先存储和列优先存贮情况下A［5,5］的存储地址分别为_

4.设目标T="abccdcdccbaa"，模式P="cdcc”,则笫次匹配成功。

5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），

判断队空和队满的条件分别分：,。

6.字符串t="averycutechild",s="Ilikecoffeeandcake”,请写出下列函数的结果：StrLength（t）

=:Concat（SubString（s,3,15）,SubString（t,12,6））=°

7.•棵二叉树的后序序列为DECBHGFA，中序序列为BDCEAFHG,请画出这棵树的结构.

品请用数据序列［53,13,24,37,18,90｝构造•棵二叉揖序树」

9.二叉树的中序遍历相当于对应树的遍历，或者对应森林的遍历。

10.二叉树中元素（完全序列）按照顺序存储方式存放在如卜・•维数组中，则结点G所在层次为。

01234567891011121314

ABCDEFG11IJ

11.有n个结点的无向完全图和有向完全图的边数分别为,.

12.要从数据：1,3,5,1,9,11,13查找11,若采用折半查找法，则在次比较后，才找到该数据。

13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下最快，其时间更杂度为—

二.简答题（每题10分，共50分）

1假设9个字母为：ABCDEFGHI,权值分别为5,13,7,4,20,34,16,9,8。试为这9个字母设计哈夫

里编码。并计算其带权路径长度。（要求画出树、写出编码，计算WPL）

2请对下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树。（要求使用图画出每一步过程）

3.试利用Dijkstra算法求图中从顶点VI到其他各顶点间的最短路

径，写出执行算法过程中各步的状态。（G使用邻接矩阵表示，要求使用表描述耳法中每一步顶点与状态的变化情况,

即求解过程）

I.假定存在数据表：（3,4,5,7,24,30,54,63,72,87,95,102）,请解决如下问题：

3）假设哈希函数为：H（key）二keymod13,用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）

请画出存放状态；

4）请按比较顺序写出查找102的过程中比较的数值，以及比较的次数：

5设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，贝人

<1>写出冒泡排序的过程：（每一步过程）

（2）写出希尔（shell）排序的过程，初始步长为4。（每一步过程）

三.程序题（10分）

端写算法判别给定二叉树是否为完全二叉树。要求：

1）函数为：intIsFullBitree（BitreeT）〃判断二叉树是否完全二叉树，是刚返回1,否则返回0

2）不用写主函数；3）如使用其他函数，请注释。

《数据结构》（A卷）答案

一.填空（每空2分，共40分）

1.p->prior->next=p->next,p->next->prior=p->prior.

2.递归工作栈.

3.1270,1210。

5.Q.front==Q.rear,Q.front==(Q.rear+1)%MS。

6.17,“likecoffeeandchild”。

A53

13.快速排序,0(nlgn).

二.简答题

1先将概率放大100倍，以方便构造哈夫曼树。

w={7,19,2,6,32,3,21,10},按哈夫曼规则：[[(2,3),6],(7,10)],……19,21,32

2清对下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）！邻接矩阵为:

043X00CO00C

40559coooc

3505oocooo

oo550765<

oo9oo703ooc

cocooo6302c%1

ooxoo5oo20

oox54ooco6I

3

®©©Q

@~©(D

©J)》®®

©O<e>

Q®®

4

0

其后续序列为：BHECIGFAD

5

没要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则:

目泡排序一趟扫描的结果是HCQPAMSRDFXY：

初始步长为4的希尔(shell)排序一趟的结果是PACSQHFXRDVY；

一路归并排序一趟扫描的结果是HQCYAPMSDRFX：

火速排序•趟扫描的结果是FHCDFAMQRSYX；

淮排序初始建堆的结果是ADCRFQYSYPHX。

三.程序题(10分)

ntIsFull_Bitree(BitreeT)〃判断二叉树是否完全二叉树，是则返回1,否则返回0

(

Ini(Queue(Q);

flag=0;

FnQiiPUP(Q,T);〃建立工作队列

while(!QueueErapty(Q))

(

{

DeQueue(Q,p):

if(!p)flag=l:

elseif(flag)return0;

else

|

EnQueue(Q,p->IchiId);

EnQueue(Q.p->rchild)：//不管孩子是否为空，都入队列

}

}//while

return1;

!//IsFull_Bitree

计算机学院2010-2011学班第一学期

《数据结构》试卷(B卷)(考试时间：100分钟)

专业：班级:序号：姓名：

填空(每空2分，共40分)

.•双向循环链表中，结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，则其

基本操作为一,一<.

2.通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变珏、形式参数的存储

空间以及返回地址。

3.有6行8列的二维数组A,每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址(基址)

为1000,在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为______，,/

4.设目标T="abccdcdccbaa"，模式P="cdcc”，则第次匹配成功。

5.请描述在循环队列中，(队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间)，

判断队空和队满的条件分别分：,.

6.字符串t="averycutechild",s="Ilikecoffeeandcake”,请写出下列函数的结果：StrLength(s)

=;Concat(SubString(s,3,15),SubString(t,12,6))=»

7.在具有n个单元的循环队列中，队满时共有个元素。

8,深度为k的二义树的结点总数，最多为一个。展少为个。

0二叉树中元素按照顺序存储方式存放在如下一维数组，3则结点C所在层次为

04567891011121314

ABCDEFG11IJ

10.iTn个结点的无向完全图和有•向完全图的边数分别为，

11.图的深度优先遍历算法类似于树的o

12.要从序列｛I,3,5,7,9,11,13｝中查找11,若采用折半查找法，则在次比较后，才找到该数据。

13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下最快，其时间复杂度为_______。

二简答题：(每题10分，共50分)

1.假设9个字母为：ABCDEFGh权值分别为5,13,7,4,20,34,16,9,8。试为这9个字母设计哈夫

曼编码。并计算其带权路径长度。

2.森林和二叉树的转换，画出和下列二叉树相应的森林

4.假定存在数据表：(3,4,5,7,24,30,54,63,72,87,95,102),请解决如下问题：

1)假设哈希函数为：H(key)=keymod13,用该哈希函数将数据表存入长度为13的哈希表，(利用线性探测)

请画出存放状态：

2)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数：

5设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键码按字母序的升序重新排列，则：

(1)写出冒泡排序的过程：

(2)写出希尔(shell)排序的过程，初始步长为4

三程序题

清写出折半套找方法的函数Search_Bin(SSTableS,valuev)«要求：

1)函数名使用给出的函数名，参数SSTable表示序列，使用•维数组存放，下标从0开始，value表示要查找的

道；

2)如果找到，则函数返回值为该数在序列中的位置，否则返回T：

3)不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。

计算机学院2010-2011学年第一学期

《数据结构》试卷(B卷)(答案)

专业：班级：序号：姓名：

填空(每空2分，共40分)

:.双向循环跳表中，结点的前驱指针域和后维指针域分别用prior和next表示，删除P指针所指向的结点，则其

扶本操作为p->prior->nnxt=p->nnxt,p->novt->print-p->prinr.

2.通常程序在调用另•个程序时，都需要使用•个」1L来保存被调用程序内分配的局部变武、形式参数的存储空

间以及返回地址。

3.有6行8列的二维数组A,每个元素川相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址(基址)

为1000,在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为1270,1210

4.设目标T="abccdcdccbaa”，模式叫“cdcc"，则第次匹配成功。

5,请描述在循环队列中,(队列用Q表示,队头和队尾指针分别由front和rear表示，该队列有MS个存储空间)，

判断队空和队满的条件分别分：_Q.front==Q.rear,Q.front==(Q.rea"+l)%MS_«

6.字符串t="averycutechild">s="Ilikecoffeeandcake”,请写出卜,列函数的结果：StrLength(s)

=_22_;Concat(SubString(s,3,15),SubString(t,12,6))=_1ikecoffeeandchiId_»

工在具有n个单元的循环队列中，队涧时共有nT个元素。

8,深度为k的二义树的结点总数，4多为2T个。最少为k个。

9二义树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为3。

0I234567891011121314

ABCDEFGHIJ

10.iTn个结点的无向完全图和存■向完全图的边数分别为n(n-l)/2,n(n-l)°

11.图的深度优先遍历算法类似于树的先•.

12.要从序列｛1,3,5,7,9,11,13｝中查找11,若采用折半查找法，则在2次比较后,才找到该数据。

13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下最快，其时间复杂度为/快

速排序,0(n1gn)

二简答题；(每题10分，共50分)

1.假设9个字母为：ABCDEFGI,权值分别为5,13,7,4,20.34,16,9,8。试为这9个字母设计哈夫

曼编码.并计算其带权路径长度。

116

6848

34342820

181615

9978

54

2.森林和二叉树的转换，画出和下列二叉树相应的森林

4.假定存在数据表：(3,4,5,7,24,30,54,63,72,87,95,102),请解决如下问题：

5)假设哈希函数为：H(key)=keymodl3,用该哈希函数将数据表存入长度为13的哈希表，(利用线性探测)

请画出存放状态：

0123456789101112

102543453077287952463

24,63,102共计比较了3次

6)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数：

5设要将序列(Q,H,C,Y,P,A,M,S,R,D,RX)中的关键码按字母序的升序重新排列，则：

<1>写出冒泡排序的过程；

(2)写出希尔(shell)排序的过程,初始步长为4

ShellP,A,C,S,Q,D,F,Y,R,H,M,

C,A,,FD,M,H,P,S,Q,Y,R,

ACDFHMPQRSY

三程序题

清写出折半查找方法的函数SearchBin(SSTableS,valuev)。要求：

1)函数名使用给出的函数名，参数SSTable表示序列，使用一维数组存放，下标从0开始，value表示要查找的

道；

2)如果找到，则函数返回值为该数在序列中的位置，否则返回T:

3)不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。

见课本

intsearch(arrayST,Keykey)

Low=1;high<=high：

While(low<high){

Mid=(low+high)/2;

If(key=array[mid].key)returnmid;

Elseif(key<array[mid].key)high=mid-l;

Elselow=mid+l;}return0)

计算机学院2009-2010学年第•学期

《数据结构》试卷（A卷）（考试时间：100分钟）

单项选择（每小题2分，共20分）

..卜面程序段的时间复杂度是_____。

for（i=0:i<n:i++）

for(j=l;j<m;j++)

A[i][j]=O；

A.0(n)B.0(m+n+l)C.0(m+n)D.0(m*n)

2.在n个结点的顺序表中，算法的时间且杂度是0（1）的操作是一。

1）访问第i个结点（IWiWn）和求第i个结点的直接前驱（2WiWn）

2）在笫i个结点后插入一个新结点（IWiWn）

3）删除第i个结点（Wn）

4）将n个结点从小到大排序

3.在单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则机行.

A.s->next=p;p->next=s;

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

C.s->next=p->next;p=s：

D.p->next=s;s->next=p;

■I.若己知・•个栈的入栈序列是1,2,3,…，n,其输出序列为pl,p2,p3.•••,pn,若pl=n,则pi