第一部分 选择题

一、单项选择题（本大题共14小题，每小题1分，共14分）在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.算法分析的目的是( C )

A.找出数据结构的合理性 B.研究算法中的输入/输出关系

C.分析算法的效率以求改进 D.分析算法的易读性

2.在需要经常查找结点的前驱与后继的场合中，使用( B )比较合适。

A.单链表 B.双链表

C.顺序表 D.循环链表

3.下面关于线性表的叙述中，错误的为( D )

A.顺序表使用一维数组实现的线性表

B.顺序表必须占用一片连续的存储单元

C.顺序表的空间利用率高于链表

D.在链表中，每个结点只有一个链域

4.带头结点的单链表head为空的判断条件是( B )

A. head=NIL B. head->next=NIL

C. head->next=head D. head< >NIL

5.队列通常采用两种存储结构是( A )

A.顺序存储结构和链表存储结构 B.散列方式和索引方式

C.链表存储结构和数组 D.线性存储结构和非线性存储结构

6.按照二叉树的定义，具有3个结点的二叉树有( C )种。

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

7.二叉树的结构如下图所示，其中序遍历的序列为( )

A.a,b,d,g,c,e,f,h

B.d,g,b,a,e,c,h,f

C.g,d,b,e,h,f,c,a

D.a,b,c,d,e,f,g,h

8.深度为5的二叉树至多有( C )个结点。 (2^M-1)

A.16 B.32 C.31 D.10

9.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为 ( A )

A.n B.n+1 C.n-1 D.n+边数

10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( C )条边。

A.n B.n+1 C.n-1 D.n/2

11.静态查找表与动态查找表二者的根本差别在于( B )

A.它们的逻辑结构不一样

B.施加在其上的操作不同

C.所包含的数据元素的类型不一样

D.存储实现不一样

12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的( D )方法是散列文件的关键。

A.散列函数 B.除余法中的质数

C.冲突处理 D.散列函数和冲突处理

13.对于大文件的排序要研究在外设上的排序技术，即( C )

A.快速排序法 B.内排序法

C.外排序法 D.交叉排序法

14.设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( C )法。

A.冒泡排序 B.快速排序

C.堆排序 D.基数排序

二、判断题(判断下列各题，正确的在题干后面括号内打“√”，错误的打“×”。每小题2分，共20分)

1.所谓数据的逻辑结构指的是数据元素之间的逻辑关系。( )

2.在线性结构中，每个结点都有一个直接前驱和一个直接后继。( )

3.插入和删除是数组的两种基本操作。( )

4.在链栈的头部必须要设置头结点。( )

5.在二叉树中插入结点则该二叉树便不再是二叉树。( )

6.查找表的逻辑结构是集合。( )

7.静态查找表的检索与修改被分成两个不交叉的阶段分别进行。( )

8.在索引顺序文件中插入新的记录时，必须复制整个文件。( )

9.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。( )

10.对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是0(n2)( )

三、填空题(每小题2分，共30分)

1.程序设计的实质是________和________。

2.设由字符串a=′data′、b=′structure′、c=′-′,则a与c连接然后与b连接的结果为：________。

3.通常单链表的头结点指的是________；单链表的首结点指的是________。

4.一个队列的入队序列是a、b、c、d，则队列的输出序列为________。

5.栈结构通常采用的两种存储结构是________和________。

6.具有N个结点的完全二叉树的深度为________。

7.树的三种主要的遍历方法是：________、________和层次遍历。

8.在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于________。

9.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造________和解决________。

10.索引顺序表上的查找分两个阶段：(1)________；(2)________。

11.散列文件中的记录通常是成组存放的。若干的记录组成一个存储单位，称作________。

12.就文件而言，按用户的观点所确定的基本存储单元称为________。按外设的观点所确定的基本存储单元称为________。

13.文件的检索有三种方式：________存取、________存取和按关键字存取。

14.最简单的交换排序方法是________排序。

15.外排序的基本方法是________。

四、应用题(每小题6分，共18分)

1.假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。

2.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的哈夫曼编码。

3.有初始的无序序列为{98,65,38,40,12,51,100,77,26,88},给出对其进行归并排序(升序)的每一趟的结果。

五、设计题(每小题6分，共18分)

1.假设用一个循环单链表来表示队列(称为循环链队)，该队列中只设一个队尾指 针rear,不设队首指针。请编写向循环链队中插入一个元素X的过程。

2.以邻接表为存储结构，写出连通图的深度优先搜索算法。

3.设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数：H(key)=key MOD 13, 采用线性探测法解决冲突，试在0～18的散列地址空间中对该关键字序列构造散列表。

数据结构导论试题参考答案

一、单项选择题(每小题1分，共14分) 1.C 2.B 3.D 4.B 5.A

6.C 7.B 8.C 9.A 10.C

11.B 12.D 13.C 14.C

二、判断题(每小题2分，共20分)

1. × 2. × 3. ×? 4. × 5. ×?

6. √ 7. √ 8. × 9. × 10. √? 三、填空题(每小题2分，共30分) 1.(1)数据表示 (2)数据处理。 2.′data-structure′。 3.(1)在单链表第一个结点之前增设的一个类型相同的结点

(2)表结点中的第一个结点。 4. a、b、c、d。 5.(1)顺序存储结构 (2)链表存储结构。

6.〔log2N〕+1。

7.(1)先根遍历 (2)后根遍历。

8.1。

9.(1)散列函数 (2)冲突。

10.(1)确定待查元素所在的块 (2)在块内查找待查的元素。

11.桶。

12.(1)逻辑结构 (2)物理结构。

13.(1)顺序 (2)直接。

14.冒泡排序。 15.归并。 四、应用题(每小题6分，共18分) 1.顺序实现：

const maxsize∶=100; ｛顺序表的容量｝ type datatype=record ｛档案数据类型｝

name∶string〔10〕;｛姓名｝

number∶integer;｛学号｝

sex∶boolean;｛性别｝

age∶integer;｛年龄｝

end;

type slist =record

data∶array 〔1..maxsize〕 of datatype;

last∶integer;

end;

链接实现：

type pointer=↑node;

node=record

name∶string 〔10〕;｛姓名｝

number∶interger； ｛学号｝

sex∶ boolean;｛性别｝

age∶integer;｛年龄｝

next∶pointer;｛结点的后继指针｝

end;

list=pointer;

2.哈夫曼树为：

相应的哈夫曼编码为：

a:001 b:10 c:01 d:000 e:11

画出正确的哈夫曼树给4分，写出相应哈夫曼编码给2分

3.

初始无序序列： 98 65 38 40 12 51 100 77 26 88

｛98｝ ｛65｝ ｛38｝ ｛40｝ ｛12｝ ｛51｝ ｛100｝｛77｝ ｛26｝｛88｝

第一次归并： ｛65 98｝ ｛38 40｝ ｛12 51｝ ｛77 100｝ ｛26 88｝

第二次归并： ｛38 40 65 98｝ ｛12 51 77 100｝ ｛26 88｝

第三次归并： ｛12 38 40 51 65 77 98 100｝ ｛26 88｝

第四次归并： ｛12 26 38 40 51 65 77 88 98 100｝

五、设计题(每小题6分，共18分)

1.PROCEDURE insert (VAR rear∶pointer; x∶integer);

VAR head, tmp∶pointer;

BEGIN

new(tmp);

tmp↑.data∶=x;

if (rear=NIL) then ｛循环队列为空，新结点是队列的首结点｝

BEGIN

rear∶=tmp;

rear↑.next∶=tmp;

END

else ｛队列不空，将新结点插入在队列尾｝

BEGIN

head∶=rear↑.next;

rear↑.next∶=tmp;

rear∶=tmp;

rear↑.next∶=head;

END

END;

2.procedure dfs(g:adj-list;v1∶integer);

｛从v1出发，深度优先遍历图g｝

begin

write(v1);

visited(v1)∶=true; ｛标志v1已访问｝

p=g〔v1〕.link; ｛找v1的第一个邻接点｝

while p< >nil do

〔 if not (visited〔p↑.vertex〕)

then dfs(g,p↑.vertex);

p∶=p↑.next〕 ｛找v1的下一个邻接点｝

end;

以邻接表为存储结构，连通图的深度优先搜索就是顺序查找链表。

3.构造过程如下：

H(19)=19 MOD 13=6

H(01)=01 MOD 13=1

H(23)=23 MOD 13=10

H(14)=14 MOD 13=1(冲突)

H(14)=(1+1) MOD 19=2

H(55)=55 MOD 13=3

H(20)=20 MOD 13=7

H(84)=84 MOD 13=6 (冲突)

H(84)=(6+1) MOD 19=7 (仍冲突)

H(84)=(6+2) MOD 19=8

H(27)=27 MOD 13=1 (冲突)

H(27)=(1+1) MOD 19=2 (冲突)

H(27)=(1+2) MOD 19=3 (仍冲突)

H(27)=(1+3) MOD 19=4

H(68)=68 MOD 13=3 (冲突)

H(68)=(3+1) MOD 19=4 (仍冲突)

H(68)=(3+2) MOD 19=5

H(11)=11 MOD 13=11

H(10)=10 MOD 13=10 (冲突)

H(10)=(10+1) MOD 19=11 (仍冲突)

H(10)=(10+2) MOD 19=12

H(77)=77 MOD 13=12 (冲突)

H(77)=(12+1) MOD 19=13

因此，各关键字相应的地址分配如下：

address(01)=1

address(14)=2

address(55)=3

address(27)=4

address(68)=5

address(19)=6

address(20)=7

address(84)=8

address(23)=10

address(11)=11

address(10)=12

address(77)=13

其余的地址中为空。