数据结构耿国华附录答案

数据结构 附录A 样卷一

一、判断题：（10 分） 正确在括号内打√，错误打× (×) 1.在单链表中，头结点是必不可少的。

（×）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。 (√) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 (×) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 (√) 5. 在一个大根堆中，最小元素不一定在最后。

(√) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （√）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 （√）8. 内部排序是指排序过程在内存中进行的排序。 （×）9. 拓扑排序是指结点的值是有序排列。

(×)10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。 二、选择题(30分, 每题1.5分)

1．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：___B___ A． head==NULL B. Head->next==NULL C.head->next==head D.

数据结构 附录A 样卷一 一、判断题：（10 分）

正确在括号内打√，错误打×

( ) 1.在单链表中，头结点是必不可少的。

（ ）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。 ( ) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 ( ) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 ( ) 5. 在一个大根堆中，最小元素不一定在最后。

( ) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ ）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 （ ）8. 内部排序是指排序过程在内存中进行的排序。 （ ）9. 拓扑排序是指结点的值是有序排列。

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

二、选择题(30分, 每题1.5分)

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

A． head=NIL B. head^.next=NIL

数据结构 附录A 样卷一

一、判断题：（10 分） 正确在括号内打√，错误打× (×) 1.在单链表中，头结点是必不可少的。

（×）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。 (√) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 (×) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 (√) 5. 在一个大根堆中，最小元素不一定在最后。

(√) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （√）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 （√）8. 内部排序是指排序过程在内存中进行的排序。 （×）9. 拓扑排序是指结点的值是有序排列。

(×)10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。 二、选择题(30分, 每题1.5分)

1．有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：___B___ A． head==NULL B. Head->next==NULL C.head->next==head D.

第一章 绪论

一、问答题

1. 什么是数据结构？

2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。

二、判断题（在各题后填写“√”或“×”）

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ） 2. 算法就是程序。（ ）

3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ） 三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++) for(j=1;j<=i;j++)

for(k=1;k<=j;k++) x=x+1;

【解答】

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3

第一章 绪论

一、问答题

1. 什么是数据结构？

2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。

二、判断题（在各题后填写“√”或“×”）

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（ ） 2. 算法就是程序。（ ）

3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（ ） 三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++) for(j=1;j<=i;j++)

for(k=1;k<=j;k++) x=x+1;

【解答】

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3

第1章 绪 论

习 题

一、问答题

1. 什么是数据结构？

2. 四类基本数据结构的名称与含义。 3. 算法的定义与特性。 4. 算法的时间复杂度。 5. 数据类型的概念。

6. 线性结构与非线性结构的差别。 7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 参数传递的主要方式及特点。 10. 抽象数据类型的概念。 二、判断题

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2. 算法就是程序。

3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。 三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++) for(j=1;j<=i;j++)

for(k=1;k<=j;k++) x=x+1;

[提示]：

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2

…

i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2

f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (

第一章 习题答案2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽

（3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型

（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作

（9）有限性、输入、可行性 4、（1）A（2）C（3）C

5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定

（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A

B：H、L、I、E、A C：F、M

D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C

3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什

第1章 绪 论

习题

一、问答题

1. 什么是数据结构？

2. 四类基本数据结构的名称与含义。 3. 算法的定义与特性。 4. 算法的时间复杂度。 5. 数据类型的概念。

6. 线性结构与非线性结构的差别。 7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 参数传递的主要方式及特点。 10. 抽象数据类型的概念。 二、判断题

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2. 算法就是程序。

3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++) for(j=1;j<=i;j++)

for(k=1;k<=j;k++) x=x+1;

[提示]：

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2 …

i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2

f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)n

第1章 绪 论

习题

一、问答题

1. 什么是数据结构？

2. 四类基本数据结构的名称与含义。 3. 算法的定义与特性。 4. 算法的时间复杂度。 5. 数据类型的概念。

6. 线性结构与非线性结构的差别。 7. 面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？ 9. 参数传递的主要方式及特点。 10. 抽象数据类型的概念。 二、判断题

1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。 2. 算法就是程序。

3. 在高级语言（如C、或 PASCAL）中，指针类型是原子类型。

三、计算下列程序段中X=X+1的语句频度

for(i=1;i<=n;i++) for(j=1;j<=i;j++)

for(k=1;k<=j;k++) x=x+1;

[提示]：

i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3时： 1+2+3 = (1+3)×3/2 = (3+32)/2 …

i=n时： 1+2+3+……+n = (1+n)×n/2 = (n+n2)/2

f(n) = [ (1+2+

第一章 习题答案 2、××√ 3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型

（5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作

（9）有限性、输入、可行性 4、（1）A（2）C（3）C

5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章 习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定

（4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A

B：H、L、I、E、A C：F、M

D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C

3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。

头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首