耿国华数据结构附录样卷答案.docx

耿国华数据结构附录样卷答案.docx

《耿国华数据结构附录样卷答案.docx》由会员分享，可在线阅读，更多相关《耿国华数据结构附录样卷答案.docx（17页珍藏版）》请在冰点文库上搜索。

耿国华数据结构附录样卷答案

附录A样卷一

1.判断题：

（10分）

正确在括号内打错谋打X

（）1•在单链表中，头结点是必不可少的。

（）2.如果一个二叉树中没有度为1的结点，则必为满二叉树。

（）3.循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。

（）4•顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。

（）5.在一个大根堆中，最小元素不一定在最厉。

（）6.在一个有向图屮，所有顶点的入度之和等于所有顶点的出度之和。

（）7.在采用线性探测法处理冲突的散列表屮，所有同义词在表屮相邻。

（）&内部排序是指排序过程在内存中进行的排序。

（）9.拓扑排序是指结点的值是有序排列。

（）10.A0E网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。

一•、选择题（30分，每题1・5分）

1.有一个含头结点的单链表，头指针为head,则判断其是否为空的条件为:

A.

head=NILB.head*.next=NIL

C.head*.next=head

D.headONIL

或

A.

head~NULLB.Head->next~NULL

C.head->next==headD.

Head!

=NULL

2.

非空的循环单•链表head的尾指针p满足一

0

A.

p）next二NILB.p=NIL

C.p\next=head

D・p=head

或

A.

p->next=NULLB.p==NULL

C.P->next=headD.

p=head

3.

链表不具有的特点是o

A.可随机访问任一个元素B、插入删除不需要移动元素

C.不必事先估计存储空间D.所需空间与线性表的长度成正

比

4.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则

釆用存储方式最节省运算时间。

A、单链表B、双链表C、单循环链表D.带头结点的

双循环链表

5.若线性表最帘用的操作是存取第i个元索及其前驱的值，则采用存储方式节省

时间。

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

表

6.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输岀序列不可能的是o

A、A,B>C>D

B、

D,

C,

B,

A

C、A,C,D,B

D、

D,

A,

B,

C

7.一个队列的入队序列是1,2,

3,4,则队列的输出序列是

O

A.4,3,2,1

1,2,3,4C、1,

4,

3,

2

D、3,2,4,1

8.设循环队列中数组的下标范围是Pn,其头尾指针分别为f,r,若队列中元素个数为O

A.r-fBr-f+1C、（r-f+l）modnD.（r-f+n）

modn

9.串是o

A、不少于一个字母的序列B、任意个字母的序列

C、不少于一个字符的序列D、有限个字符的序列

10.数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000

的连续内存单元中.则A[5,5]的地址是。

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

11.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行

编号，根结点编号为1,则编号为49的结点的左孩了的编号为o

A.98B、99C、50D、48

12.朮二叉树从1开始编号，要求每个结点的编号人于其左右孩子的编号，同一个结点的

左右孩子中，其左孩了的编号小于其右孩子的编号，则可采用实现编号。

A、先序遍历B、中序遍历C、后序遍历D.从根开始进行

层次遍历

13.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。

A.空或只有一个结点B.高度等于其结点数

C>任一结点无左孩子D.任一结点无右孩子

14.在有n个叶了结点的哈夫曼树中，其结点总数为o

A.不确定Bx2nC.2n+lD、2nT

15.一个有n个顶点的无向图最多有条边。

A>nB>n（nT）C^n（nT）/2D.2n

16.任何一个无向连通图的最小生成树o

A.只有一棵B、有一棵或多棵C、一定有多棵D、可

能不存在

17.一组记录的关键字为（46,79,56,38,40,84）,利用快速排序的方法，以第一个

记录为基准得到的一次划分结果为o

A.38,

40,

46,

56,

79,84

B、40,

38,

46,

79,

56,84

C>40,

38,

46,

56,

79,84

D、40,

38,

46,

84,

56,79

18.已知数据表A中每个元素距其最终位置不远，则釆用排序算法最节省时间。

A、堆排序B>插入排序C、快速排序D、直接选择排序

19.下列排序算法中，算法可能会出现下血情况：

初始数据有序时，花费时间反

而最多。

A、堆排序B、冒泡排序C、快速排序D.SHELL排序

20.对于键值序列（12,13,11,18,60,15,7,18,25,100）,用筛选法建堆，必须

从键值为的结点开始。

A、100B、60C、12D、15

三、填空题（40分）

1在顺序表（即顺序存储结构的线性表）屮插入一个元索，需要平均动个元索.

2.快速排序的最坏悄况，其待排序的初始排列是.

3.为防止在图中走回，应设立.

4.一个栈的输入序列为123,写出不可能是栈的输出序更。

5.N个结点的二叉树，采用二叉链表存放，空链域的个数为•

6.要在一个单链表中p所指结点之后插入s所指结点时，

应执行和的操作.

7.Dijkstra算法是按的次序产生一点到其余各顶点最短路径的算

法.

8.在N个结点完全二叉树中，其深度是

9.对二叉排序树进行遍历，可得到结点的有序排列.

10.设一哈希表表长M为100,用除留余数法构造哈希函数，即H（K）二KMODP（P<=M>,

为使函数具有较好性能，P应选

11・单链表与多重链表的区别是

12.深度为6（根层次为1）的二叉树至多有个结点。

13.已知-■•维数组A[0..20][0..10]采用行序为主方式存储，每个元素占4个存储单元,并

且A[0][0]的存储地址是1016,则A[10][5]的存储地址是

14.循环单链表3中，指针P所指结点为表尾结点的条件是

15.在查找方法屮，平均查找长度与结点个数无关的查找方法是o

16.队列的特性是

17.具有3个结点的二叉树有种

18.已知一棵一.叉树的前序序列为ABDFCE,屮序序列为DFBACE,后序序列为

19.已知一个图的邻接矩阵表示，要删除所自从第i个结点出发的边，在邻接矩阵运算是

四、构造题：

（30分）

1.已知关键字序列为：

（75,33,52,41,12,8&66,27）哈希表长为10,哈希函数为：

H（k）=KMOD7,解决冲突用线性探测再散列法，构造哈希表，求等概率下竇找成功的平均查找长度。

E1

2.已知无向图如图1所示，

（1）给出图的邻接表。

（2）从A开始，给出一棵广度优先生成树。

3.给定叶结点权值：

（1,3,5,6,7,8）,构造哈夫曼树，并计算其带权路径长度。

4.从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树:

（24,88,42,97,22,15,7,13）□

5.

对长度为8的有序表，给出折半賁找的判定树，给出等概率情况下的平均査找长度。

6.已知一棵树如图2所示，要求将该树转化为二叉树。

5.算法设计题（40分）

［算法题可用类PASCAL或类C语言■每题20分］

1.已知一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并输出二叉树中非终端结点（输岀无顺序要求）。

2.编写算法.判断带头结点的双循环链表L是否对称。

对称是指：

设各元索值ahan,则有ai=an-i*i

即指：

&!

=3n>fl2=fln-l

结点结构为

prior

data

next

数据结构附录B样卷二

一.简答题（15分，每小题3分）

1.简要说明算法与程序的区别。

2.在哈希表中，发生冲突的可能性与哪些因素有关？

为什么？

3.说明在图的遍历屮，设置访问标志数组的作用。

4.说明以下三个概念的关系：

头指针，头结点，首元素结点。

5.在一般的顺序队列中.什么是假溢出？

怎样解决假溢出问题？

二、判断题（10分，每小题1分）

正确在括号内打错谋打X

（）

（1）广义表（（（a）,b）,c）的表头是（（a）,b）,表尾是（c）o

（）

（2）在哈夫曼树屮，权值最小的结点离根结点最近。

（）（3）基数排序是高位优先排序法。

（）（4）在平衡二叉树屮，任意结点左右子树的高度建（绝对值）不超过1。

（）（5）在单链表中，给定任一结点的地址p,则可用下述语句将新结点s插入结点p的后面:

p->next=s;s->next=p-〉next;

（）（6）抽彖数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。

（）（7）数组元素的下标值越大，存取时间越长。

（）（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

（）（9）拓扑排序是按A0E网中每个结点事件的最早发生时间对结点进行排序。

（）（10）长度为1的串等价于一个字符型常杲。

三、单项选择题（10分，每小题1分）

1.排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。

这是哪种排序方法的基木思想？

A.堆排序B.直接插入排序C.快速排序D.冒泡排序

2.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该:

A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元索全部置为0

O将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部腔为0

3.有一个含头结点的双向循环链表，头指针为head,処其为空的条件是：

A.head->priro==NULL

C・head->next=head

4・在顺序表（3,6,&10,12,15,值11,所需的关键码比较次数为：

A）2B）3C）4

B.head->next==NULL

D.head-〉next-〉priro==NULL

16,1&21,25,30）中，用折半法杏找关键码

D）5

5.以下哪一个不是队列的基木运算？

A）从队尾插入一个新元素B）从队列中删除第i个元素

C）判断一个队列是否为空D）读取队头元素的值

6.在长度为n的顺序表的第i个位置上插入一个元索（1WiWn+1）,元索的移动次数为:

A）n・i+1B）n-iC）iD）i-1

7.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为：

A）顺序表B）用头指针表示的循环单链表

O用尾指针表示的循环单链表D）单链表

8.对包含n个元素的哈希表进行査找，平均查找长度为：

A）0（log2n）B）0（n）C）O（nlogm）D）不直接依赖于n

9.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点

进行编号，根结点编号为1,则编号最大的非叶结点的编号为：

10.某二叉树结点的中序序列为A.B、C、D、E、F、G,后序序列为B.D、C.A.F、G.E,则其左子树中结点数日为：

A）3B）2C）4D）5

4.填空题（10分，每空1分）

1.填空完成下血一趙快速排序算法：

intQKPass（RecordTyper[],intlow,inthigh）

{x=rTlow1：

while（low

{

while（low=x.key）

high；

if（low

{r[]=r[high]；low++;}

while（low

low++;

if（low

{r[]=r[low]；high—;}

}

r[low]=x；returnlow;

}

2.假没用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加入队列时,

需执行下面语句：

；；R=S；

3.通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。

4.已知一个3行.4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序

存储，则排在第8个位置的元素是：

5.高度为h的完全二叉树最少有个结点。

5.构造题（20分）

1.（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。

DS=（D,R）

0={a,b,c,d,e,f,g}

R={T}

T={,,,,,,

,,,,,}

2.（6分）对以下关键字序列建立哈希表：

（SUN,MON,TUE,WED,THU,FRI,SAT），哈希函数为H（K）=（K中最厉一个字母在字母表屮的序号）MOD7。

用线性探测法处理冲突，要求构造一个装填因了为0.7的哈希表，并计算出在等概率情况下資找成功的平均資找长度。

3.（6分）将关键字序列（3,26,12,61,38,40,97,75,53,87）调整为人根堆。

4.（4分）已知权值集合为:

{5,7,2,3,6,9},要求给出哈夫曼树，并计算其带权路径长度WPLo

六、算法分析题（10分）

阅读下面程序，并冋答有关问题。

其中BSTree为用一•叉链表表示的一•叉排序树类型。

（1）简要说明程序功能。

（5分）

（2）n个结点的满二叉树的深度h是多儿？

（3分）

（3）假设二叉排序树祐$亡是有n个结点的满一•叉树，给出算法的时间复杂度。

（2分）intProc（BSTree*bst,KeyTypeK）

{BSTreef,q,s;

s=（BSTree）malloc（sizeof（BSTNode））;

s->key=K;s->lchild=NULL;s->rchild=NULL;

if（*bst=NULL）{*bst=s;return1;}f=NULL;q=*bst;

while（q!

=NULL）

{if（Kkey）

{f=q；q=q-〉lchild：

}

else

{f=q;q=q->rchild;}

}

if（Kkey）f->lchild=s;

elsef->rchild=s;

return1;

）

七、算法设计题（25分）

1.己知一个带头结点的幣数单链表L,要求将其拆分为一个正敝数单链表L1和一个负鞭数单链表L2。

（9分）

2.无向图采用邻接表存储结构，编写算法输出图中各连通分武的结点序列。

（8分）

3.编写一个建立二叉树的算法，要求采用二叉链表存储结构。

（8分）

数据结构附录A样卷•参考答案

•:

判断题

题号

1

2

3

4

5

6

7

8

9

10

答案

X

X

J

X

J

V

V

J

X

X

二：

选择题

題

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

答

B

C

A

D

D

D

B

D

D

A

A

C

B

C

C

B

C

B

C

B

三：

填空

1表长的•半2排好序列3,J3125N+16S・>ne：

a=：

P・>M）dP・>n£）d=S7路径递增

8Tqq

（2）（Z）<）中序1097II链域个数不同1263H147614P・》wghwul15fife

列査找16先进先出17518FDBECA19将炬阵第i行全部置0

四，构造题

计算函数值

key

75

33

Si

41

12

88

66

27

Key%7

5

5

3

6

5

4

3

6

（1）哈希表（4分.每对1个0.5分）

index

0

1

2

3

4

5

6

7

8

9

key

27

52

88

75

33

41

12

66

（2）比较次数（3分）

kev

•r

75

35

52

41

12

88

66

27

Cmp

1

2

1

2

4

1

7

5

/\SL=（1+2+1+2+4+1+7+5）/8=23/«

5,

（1）

（2）ASL=（1+2»2+4*3+1*4）/8=21/8=2.62

《数拡结构》附录B样卷「：

参考答案

一、简容题（15分，毎小题3分）

6.算法是解决特定问题的操作序列.可以用多种方式描述。

程序是算法在计算机屮的实现，与具体的计算机语言有关。

7.主要与哈希函数、装填因子□有关。

如果用哈希函数计算的地址分布均匀，则冲突的可能性较小.如果装填因子a较小.则哈希农较稀疏，发生冲突的可能性较小。

8.图中结点可能有多个前驱，设置访问标志数组主要是为了避免用复访问同一个结点。

9.头指针指向头结点.头结点的后继域指向首元索结点.

10・当队尾到达数组最后一个单元时，就认为队满•但此时数组前面可能还有空单元，因此叫假溢出.

解决的方法是采用循环队列，即令最后-个单元的后继是第•个单元。

二、判析题（10分，毎小题1分）

（1）

（V）

（2）

（X）（3）（X）⑷

（V）

（5）

（X）

（6）

3）

（7）

（X）（8）（V）（9）

（X）

（10）

（X）

三.单项选择题（10夕

毎小题1分）

1.D）

2.

B）

3.C）4.C）

5.

B）

6.A）

7.

0

8.D）9.C）

10.

C）

四.填空题（10分，毎空1分〉

1.

highlow

lowhigh

2.

S->next=R->next；

R->next=S:

3.

时间空间

4・A[2,3]5・

2卜1

五、

.构适题（20分）

1.

（4分）

2.（6分）

0I23456789

SUNMONTHUFRIWEDTUESAT

ASUc=（1X4+2X2+3）/7=11/7

3.（6分）

4・（4分）己知权值集合为：

{5,7,2,3.6.9},要求给出哈夫曼树，并计算其带权路径长度WPL。

WPL=2X（9+6+7）+3X5+4X（2+3）=79

六、算法分析题（10分）

斛：

（1）在二叉排序树屮插入关键字为K的结点

（2）h=log：

（n+1）或h=[log：

n]+1（方括号农示向下取整）

（3）0（log：

（n+1））或0（log：

n）