数据结构习题1

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.归并。 四、 相应的哈夫曼编码为：

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｝ 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 其余的地址中为空。

第一章 绪论 一、选择题

1.组成数据的基本单位是（ ）

（A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（ ）以及它们之间的相互关系。 （A）理想结构，物理结构 （B）理想结构，抽象结构 （C）物理结构，逻辑结构 （D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（ ） （A）动态结构和静态结构 （B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构

4.数据结构是一门研究非数值计算的程序设计问题中计算机的 （①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构 （B）关系 （C）运算 （D）算法 5.算法分析的目的是（）。

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

（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性

6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法

② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性 （D）易读性、稳定性和安全性 二、判断题

1.数据的机内表示称为数据的存储结构。（ ） 2.算法就是程序。（ ）

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

4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（ ） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（ ） 三、填空题

1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。

3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。

4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。

6.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。

9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。