2001年10月甘肃自考02142数据结构导论真题参考答案

全国2001年10月高等教育自学考试

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

课程代码：02142

点击查看：【真题试卷】

一、单项选择题(每小题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

其余的地址中为空。