郑州大学远程教育学院数据结构试题及答案

郑州大学现代远程教育

《数据结构》课程（本科)

学习指导书

郭纯一 编

 课程内容与基本要求

“数据结构\"在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图)和基本技术（查找和排序方法）三大部分.

本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上,会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法;还应初步掌握算法的时间和空间效率的分析方法.

 课程学习进度与指导 章节 第一章 课程内容 绪论 学时分配 4学时 10学时 学习指导 （均以课件学习为主） 重点掌握基本概念和时间复杂度的计算方法 重点掌握顺序结构和链式结构表示线性表的方法和操作的实现;结合具体例子理解编程实现一个问题的2种方法 重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用 重点掌握串的术语、串操作结果和不同存储结构的特点 重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及Huffman树和Huffman编码的构造方法 重点掌握图的术语、存储、遍历算法及应用；掌握最小生成树的2种构造方法及特点、会求拓扑排序序列和单源最短路径 重点掌握各种动态查找表的构造过程、性能分析、插入/删除方法；掌握静态查找表的顺序、折半和分块查找及ASL求法 掌握关于排序的术语及分类方法；重点掌握插入排序、交换排序、选择排序等内排序方法及其性能分析方法 第二章* 线性表 第三章 第四章 第七章＊ 栈和队列 串 8学时 2学时 树和二叉树 10学时 第八章 图 8学时 第九章* 查找 第十章＊

8学时 排序 8学时 第一章

一、 章节学习目标与要求

绪论

1、理解数据抽象和信息隐蔽原则

2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序

二、 本章重点、难点

重点:基本概念和术语,C语言描述算法的方式，简单程序的时间复杂度的求法。 难点：时间复杂度的计算方法和原则。

三、 章节练习

（一）选择题：

1． 具有线性结构的数据结构是__________.

A.图 B。 树 C. 集合 D。 栈 2． 计算机算法是指________。

A.计算方法和运算结果 B。调度方法 C. 解决某一问题的有限运算系列 D. 排序方法 3． 线性结构中，最后一个结点有________个后继结点。 A. 0 B。 1 C. 任意多 4。 算法分析的目的是________.

A. 找出数据结构的合理性 B. 研究算法中输入和输出的关系 C。 分析算法的效率以求改进 D.分析算法的可读性和可行性 5. 具有非线性结构的数据结构是__________。

A。图 B. 线性表 C。 串 D。 栈

6．算法具有5个特性：________、________、________、输入和输出。

A. 稳定性、确定性、可行性 B。 有穷性、确定性、可行性 C。 有穷性、安全性、可行性 D。 有穷性、确定性、可移植性 7．设n为正整数。则下面程序段的时间复杂度为________。

i=1; k=0;

while(i〈=n-1)｛

＠ k+=10＊i;

i++;

}

A。O（1） B. O（n） C. O(nlogn） D. O(n2） 8．设n为正整数。则下面程序段的时间复杂度为________。

k=0；

for(i=1；i<=n；i++）｛

for（j=i;j〈=n;j++） ＠ k++;

｝

A.O（1) B. O(n） C. O（nlogn) D. O（n2) （二）判断题：

1．在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。（ ) 2．任何一个算法的设计取决于数据的逻辑结构,而算法的实现则依赖于所采用的存储结构。 ( ）

3. 数据元素是数据的不可分割的最小单位。 （ ） 4. 算法分析的两个主要方面是时间复杂度和空间复杂度。 （ ）

第二章

一、 章节学习目标与要求

1、理解线性表的逻辑结构特性、顺序表和链表表示线性表的优缺点、循环链表和双向链表的特点。

2、 掌握线性表的两种存储方式及其实现：熟练掌握顺序表和链表的创建、插入元素、删除元素以及定位等常用操作的实现算法并会求相应算法的时间复杂度. 二、本章重点、难点

重点:线性表的特点、两种表示方式及它们的运算实现，会求算法的时间复杂度. 难点：单链表结构、特点及其实现 三、章节练习 (一)选择题：

1．顺序表是一种________的存储结构,单链表是________的存储结构。

A。 顺序存取 B。 随机存取 C。 索引存取

2．顺序表中第一个元素的起始存储地址为100，每个元素的长度为4，则第五个

线性表

元素的起始地址是_______。

A。 105 B. 110 C. 116 D。 120

3．非空循环单链表（head为头指针)的尾结点(由指针p所指示)应满足________。

A。 p—〉next==NULL； B. p==NULL; C。 p->next==head; D. p==head； 4．若在线性表的任何位置上插入元素的概率是相等的,那么在长度为n的顺序表

中插入一个元素时需平均移动________个元素。

A。 n B. （n—1）/2 C.n/2 D. (n+1)/2 5．在带头结点的非空单链表中,头结点的位置由________指示，首元结点的存储位置由________指示,除首元结点外，其它任一元素结点的存储位置由________指示。

A。 头指针 B. 头结点的指针域的指针 C。前驱结点的指针域的指针

6. 单链表的头指针为p，若有头结点，则表空的判断条件是______________；若不带头结点，则表空的判断条件是______________。

A。 p==NULL B。 p—>next==NULL C. p->next->next==NULL （二)判断题:

1．在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化,因此不需要移动元素。 （ )

2． 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系. （ ）

3. 在不带头结点的非空单链表中，首元结点的存储位置由头指针指示,除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。 （ ） (三）问答题:

1．若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）？为什么？

2．若线性表经常做插入/删除操作，则应采取什么存储结构？为什么? 3。 在单链表中设置头结点有什么作用？ （四）算法题：

1.设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法，将x插

入到链表的适当位置上，并仍保持该表的有序性。

2.设顺序表va中的数据元素递增有序.设计算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。

3。设计算法,实现单链表的就地逆置，即利用原表的存储空间将线性表（a1,a2，…，an)逆置为(an ，an-1,…，a1）.

第三章

一、 章节学习目标与要求

1、理解用栈和队列解决实际问题的方法。

2、掌握栈和队列的定义以及特性、它们的2种不同的存储表示方法(特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。 二、本章重点、难点

重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解 难点:循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式;能在具体问题中灵活运用栈和队列结构. 三、章节练习 (一）选择题：

1．一个栈的入栈序列是a，b，c，d,e,则栈的不可能的输出序列是________。

A。 edcba B.decba C。dceab D。abcde 2．栈和队列的共同点是_______.

A。 都是后进先出 B. 都是先进先出

C。 都是只允许在端点处插入和删除元素 D.无共同点

3．一个队列的入队序列是{1，2，3，4}，则队列的输出序列是______. A. ｛4321｝ B. {1234｝ C。 ｛1432} D。 ｛3241｝ 4．栈的入栈序列是1，2，…,n，输出序列为p1,p2，…pn，若p1=n， 则pi为_____.

A. i B. n—i C。 n-i+1 D。 不确定

5．队列是限定在________进行插入，在________进行删除的线性表。

A. 队头 B。 队尾 C。 任意位置

6．循环队列中，设队列元素依次存放在Q［0。.m]中,f、r分别指示队头元素位

栈和队列

置和队尾元素的下一个位置，约定存储m个元素时为队满。则队列空的判定方法是_______，队列满的判定方法是_______.

A.f==r B。 （f+1)％（m+1）==r C。 (r+1)％（m+1)==f D. (r+1)% m==f

（二）判断题：

1．若用户无法估计所用队列的最大长度，则最好采用链队列. （ ）

2．在链队列上删除队头元素时,只需修改头结点中的指针，不必修改尾指针. ( ） 3. 栈是限定仅在栈顶进行插入或删除操作的线性表。 （ ） 4。 队列是限定在队尾插入元素，在队头删除元素的线性表. （ ） (三）问答与算法题：

1．对于一个栈，若输入序列依次为｛A,B,C}, 试给出所有可能的输出序列。 2．假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法.

第四章

一、 章节学习目标与要求

1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。 2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。 二、本章重点、难点

重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解 难点:串的不同存储结构，区分它们和高级语言中串的存储方式的不同。 三、章节练习 (一)选择题：

1．设串s=\"I AM A STUDENT”， 则其串长是______。 A。 13 B。 14 C。 15 D。 16

2. 设s =”HE IS A WORKER\"，t=”WORKER”.则StrIndex(s,t,5）的返回值是_____。

A。 4 B。 5 C。 6 D. 9 E. 10 3. 串是一种特殊的线性表，其特殊性体现在_____.

串

A。 可以顺序存储 B。 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符

4。已知串s=”ABCDEFGH',则s的所有不同子串的个数为________。

A. 8 B。 9 C。 36 D。 37

5。设串s=”I am a teacher。’,则s的第8个字符起、长度为7的子串为_______。

A。 \"teacher. \" B。 \"teacher” C. \"a teacher\" D. \" teacher” 6. 设串s=\"student.\"，t=“good \则执行StrInsert(s,1,t)后，s为____。

A. ”good student。\" B。 ”good student” C。 \"goodstudent” D。 ” good teacher\" （二）判断题：

1．空串和空格串是相同的. （ ） 2。 如果两个串含有相同的字符，则它们是相同的。（ )

3。 串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。 （ ） 4. 在串的链式存储结构中，结点大小与存储密度之间没有关系。 （ ）

第七章 树和二叉树

一、章节学习目标与要求

1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱和后继的方法;理解树与森林的存储方法. 2、掌握二叉树的性质及表示;掌握二叉树的各种遍历方法（尤其是递归形式的)以及遍历在实际问题中的应用;掌握树及森林与二叉树的转换及遍历方式的对应；掌握Huffman树的构造方法以及构造Huffman编码的方法。 二、本章重点、难点

重点:二叉树的性质（及证明）、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman树及Huffman编码的构造方法 难点:各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题 三、章节练习 （一）选择题：

1．下列关于二叉树的说法中，正确的有_______。 A。 二叉树的度为2 B. 二叉树的度可以小于2

C。二叉树中至少有一个结点的度为2 D. 二叉树中任一个结点的度都为2 2．任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序_______。

A。 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 3．下面几个符号串编码集合中，不是前缀编码的是_____。

A。 {0,10,110，1111｝ B. {11,10，001，101,0001}

C。 ｛00,010，0110,1000} D. ｛b,c，aa,ac，aba,abb，abc｝ 4．二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法_______。

A。 正确 B。 不正确 C. 无法确定 （二)判断题：

1。哈夫曼树是带权叶子数目固定的二叉树中带权路径长度最小的. （ ) 2。根据二叉树的定义,具有3个结点的二叉树有5种不同的形态。 （ ）

—

3。 深度为k的完全二叉树至少有2k1个结点，至多有2k－1个结点。 （ ）

4. 具有n个结点的满二叉树,其叶子结点个数为

n1个. （ ） 25。 在哈夫曼树中，通常权值较大的结点离根较远。 （ ） （三）问答题：

1．下图所示森林转化为相应的二叉树，并在其上标出中序全线索.

2．证明:深度为k的二叉树上至多有2k-1个结点（k≥1）。

3。 证明：任何一棵满二叉树中的分支数B满足B=2（n0－1），其中n0为叶子结点个数。

4. 以数据集｛15，3,14，2，6，9，16，17｝为叶子的权值构造Huffman树,画出此树并计算其带权路径长度。

(四)算法题：

1。 假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递归算法按递增顺序输出树上各元素值。

2．编写递归算法, 交换二叉链表存储的二叉树中每个结点的左、右子树. 3。 编写递归算法，求以二叉链表存储的二叉树的深度。 4. 设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。

第八章 图

一、章节学习目标与要求 1、理解图的基本概念和术语.

2、掌握图的邻接矩阵和邻接表2种表示方法;掌握图的两种遍历算法及其求解连通性问题的方法；掌握用Prim算法和Kruskal算法构造最小生成树的过程和性能分析；掌握AOV网的拓扑排序方法 (不要求算法）,掌握用Dijkstra方法求解单源最短路径问题的方法(不要求算法）。 二、本章重点、难点

重点:图的数组表示法和邻接表表示法存储结构以及图的两种遍历方式，求最小生成树的两种方法,AOV网的拓扑排序方法,掌握单源最短路径的求法 难点：图的两种遍历算法的实现以及在图的连通性问题中的应用 三、章节练习 （一）选择题：

1. 4个顶点的无向完全图有_______条边.

A。 6 B. 12 C。 16 D. 20 2．无向图的邻接矩阵是一个_____。

A. 对称矩阵 B。 零矩阵 C。 对角矩阵 D。 上三角矩阵 3．图的广度优先遍历算法类似于二叉树的_____,图的深度优先遍历算法类似于二叉树的_____。

A。 先序遍历 B. 中序遍历 C。 后序遍历 D. 层序遍历 4。 对________，用Prim算法求最小生成树较为合适，而Kruskal算法适于构造____________图的最小生成树.

A。 完全图 B。 连通图 C. 稀疏图 D.稠密图

5。 对于含n个顶点、e条边的无向连通图,利用Prim算法构造最小生成树的时间复杂度______________，用Kruskal算法构造最小生成树的时间复杂度为______________。

A。 O（n) B. O（n2） C。 O(e） D. O（eloge) F. O(e2) （二）判断题：

1。 若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点，则该图一定是连通图。 （ ）

2. 若从无向图的一个顶点出发进行深度优先遍历可访问到图中所有顶点,则该图一定是连通图。 （ ）

3。 任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。 （ ) 4。 有n个顶点和n-1条边的无向图一定是生成树。 （ ） 5. 一棵有n个顶点的生成树有且仅有n—1条边。 ( ） 6.连通分量是无向图的极大连通子图，而生成树是无向图的极小连通子图。（ ) （三）问答及算法题：

010，该图有多少个顶点?如果是有1011。 一个图的邻接矩阵G.arcs=011向图，该图共有多少条弧？如果是无向图，该图共有多少条边？

2。已知如右图所示的有向图，写出该图的: （1）邻接矩阵 （2）一个可能的拓扑有序序列 （3)写出从1出发的深度优先遍历序列 （4）写出从5出发的广度优先遍历序列。

3。 假设有5项活动C1～C5，每项活动要求的前驱活动如下：

C1：无； C2：C1,C3; C3：C1； C4：C3,C5 C5：C2;

试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。 4。 基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。

第九章 查找

一、章节学习目标与要求

1、理解各种查找表的定义、各种查找方法的思想以及构造查找表所依据的原则. 2、掌握线性表表示的静态查找表的顺序查找和折半查找算法及其性能分析方法;掌握二叉排序树的创建、查找、插入、删除算法及其性能分析方法；掌握AVL树的平衡化旋转方法及其性能分析;掌握B—树的插入和删除时结点的和合并方法;掌握Hash法的查找、构造方法平均查找长度的计算方法。 二、本章重点、难点

重点:各种树结构表示的动态查找表和Hash表的构造方法

难点:二叉排序树的删除、AVL树的旋转处理、B—树的插入和删除、Hash法的构造以及各种查找表的平均查找长度的计算方法 三、章节练习 (一）选择题：

1。 ________二叉排序树可得到一个关键字的有序序列。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D。 层序遍历 2．用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表中结点的_____相同。

A。 关键字 B. 元素值 C。 散列地址 D。 含义

3．利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长度是______。

A。O（n2) B.O(nlogn) C.O(n) D. O（logn） 4．散列表的装填因子越大,则发生冲突的可能性就________. A。 越小 B。 越大 C。 不确定

5．线性表有256个元素,采用分块查找，若查找每个元素的概率相等，用顺序查找确定结点所在的块，每块有_____个元素时查找效率最佳。 A。 16 B。 20 C。 25 D. 256

6．用折半查找对长度为7的有序表进行查找，则等概率下查找成功时的平均查找长度为______。

A. 15/7 B. 17/7 C。 18/7 D。 19/7

7．有序表（1，32，41，45，62，75,77,82，95，100)，使用折半查找关键字为95的元素时，需要经过____次比较后才能查找成功。

A。 2 B。 3 C。 4 D。5 (二）判断题:

1. 折半查找和二叉排序树的查找时间性能一样。 （ ） 2。 在任意一棵非空的二叉排序树中，删除某结点后又将其插入，则所得的二叉排序树与删除前的二叉排序树形态相同. （ ） 3. 根据B—树的定义,在9阶B-树中，除根以外的任何一个非叶子结点中的关键字数目均在5～9之间。 （ ） 4。折半查找时,要求线性表必须是有序的且以顺序结构存储。 （ ） （三)问答题：

1。 设有一组关键字序列｛19，1,23,14，55，20，84,27，68，11,40}， （1） 按表中元素顺序构造一棵二叉排序树，画出这棵树，并求其在等概率情 况下查找成功时的平均查找长度。

（2）从空树开始,按表中元素顺序构造一棵2_3树(3阶B_树)，若此后再删除55，84,画出每一步执行后2_3树的状态.

2。 设散列函数H(key）=key MOD 7,用线性探测再散列法解决冲突。对关键字序列｛ 13，28，72，5，16，8，7，11 ｝在地址空间为0-10的散列区中建散列表,画出此表，并求等概率情况下查找成功时的平均查找长度。 3。 关键字序列：13，28,72，5,16，18，7，11，24，h (key） = key mod 11,

表长为11,用线性探测再散列处理冲突,试填写下表并计算每个关键字的比较次数和等概率情况下查找成功时的平均查找长度.

哈希表

0 1 2 3 4 5 6 7 8 9 10 比较次数 ASL=

4. 在地址空间为0—16的散列区中，对以下关键字序列(Jan，Feb,Mar,Apr,May， June，July，Aug,Sep,Oct，Nov，Dec)按链地址法处理冲突构造散列表，设散列函数H(x）=i/2,其中i为关键字中第一个字母在字母表中的序号。画出该散列表并求在等概率情况下查找成功时的平均查找长度。

第十章 排序

一、章节学习目标与要求

1、理解排序相关的定义以及排序方法的各种分类，理解各种排序方法的基本思想和依据原则。

2、掌握内部排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择排序等内排序的方法及其性能分析方法。 二、本章重点、难点

重点：各类内部排序方法所依据的原则、特点及典型算法. 难点：希尔排序、快速排序、堆排序 三、章节练习 （一)选择题：

1。 下列方法中,________是稳定的排序方法.

A．堆排序 B。 希尔排序 C. 快速排序 D。 折半插入排序

2。 设有1000个无序的元素，希望用最快的速度选出其中前20个最大的元素,最好用________排序方法。

A。 冒泡排序 B. 快速排序 C。 堆排序 D。 希尔排序 3．下列序列中，______是堆.

A。 ｛12，35,20，60,40，30｝ B。 ｛100，85,120,38，10，9，36} C. ｛1，5,6，24，7，3，4 ｝ D. ｛38，24，15，20，30，46｝ 4．在待排序的元素序列基本有序时，效率最高的排序方法是__ ____. A.插入排序 B.选择排序 C.快速排序 D. 归并排序

5．在下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是_______。

A. 堆排序 B。 起泡排序 C. 快速排序 D。 直接插入排序 6．对序列｛22，86，19，49,12，30，65,35,18}进行一趟排序后得到的结果为{18,12，19,22，49，30,65，35,86｝，则其使用的排序方法为_______. A。 插入排序 B. 选择排序 C。 快速排序 D。 起泡排序 7。 下列方法中，________算法的时间复杂度为O（n2）。

A。 堆排序 B. 希尔排序 C。 快速排序 D。 直接插入排序 8。 对n个记录的序列进行堆排序，最坏情况下的时间复杂度为______。 A。 O(logn） B. O（nlogn) C。 O(n) D.O(n2）

(二）判断题：

1.快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。（ ） 2。对一个堆按层次遍历，不一定能得到一个有序序列. （ ） 3.由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。 （ ） 4.快速排序算法在待排序数据有序时最不利于发挥其长处。 （ ） (三）问答题：

1.在快速排序过程中，通常取序列中的第1个记录作为枢轴，以它为“分界线\"重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，为改进之，应如何选取枢轴记录？

2。判断以下序列是否是堆，若不是,把它调整为堆（要求记录交换次数最少）,写出调整后的序列。

1)｛ 5，26，20,60,80，35，53，70 } 2）｛ 26,33,35，29，19，12,22 ｝

3.已知关键字序列{70，83，100，65，10，9,7，32},写出直接插入排序和快速排序每一趟结束时的关键字状态。

4.设关键字集合为｛10，2，14,8，12,13}，

(1)写出用希尔排序方法对序列排序时每一趟结束时的关键字状态。

（2)用堆排序方法对其从小到大排序，画出堆排序的初态、建堆和排序过程中重建堆的过程。

考试模拟题 客观题部分

一、单项选择题:（每空2分，共20分)

1. 单链表是线性表的一种________的存储结构。 A。 顺序存取 B。 随机存取 C。 索引存取 2. 栈和队列的共同点是________。

A. 都是后进先出 B。 都是先进先出

C。 都是只允许在端点处插入和删除元素 D。无共同点

3. 设s=\"HE IS A WORKER\"，t=”WORKER\"。则

index（s,t，5)的返回值是________.

A。 4 B。 5 C. 6 D。 9 E。 10 4. 串是一种特殊的线性表,其特殊性体现在________。

A. 可以顺序存储 B. 数据元素是一个字符 C。 可以链接存储 D。 数据元素可以是多个字符 5．树最适合用来表示_________。

A. 有序数据元素 B。 无序数据元素

C．元素之间具有分支层次关系的数据 D. 元素之间无关联的数据 6．4个顶点的无向完全图有__________条边。

A. 6 B。 12 C. 16 D。 20

7．散列表的装填因子越大，则发生冲突的可能性就_________。

A. 越小 B. 越大 C。 不确定

8。 在长度为n的有序表中折半查找一个元素的平均查找长度是_____。

A。O（n2） B.O(nlogn） C.O（n） D. O(logn) 9. 下列方法中，________是不稳定的排序方法.

A. 折半插入排序 B. 直接插入排序 C。 冒泡排序 D。 堆排序 10．________二叉排序树可得到一个关键字的有序序列。

A. 先序遍历 B。 中序遍历 C. 后序遍历 D。 层序遍历

二、是非题：（每题1分，共10分）(说明：正确的选“A\错误选“B\" ） 1． 线性表的顺序存储结构优于链式存储结构。 （ ） 2． 空串和空格串是相同的。 （ ） 3． 图结构中，每个结点的前驱和后续都可以有任意多个。 （ ） 4． 快速排序算法在待排序数据有序时最不利于发挥其长处。 （ ） 5． 连通网的最小生成树是唯一的。 （ ） 6． 栈是FIFO的线性表。 ( ） 7． 由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。（ ) 8． 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，

则该图一定是连通图。 （ ）

9． 折半查找方法要求查找表必须是关键字的有序表，但是对存储结构没有限

制。 （ ） 10． 在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的

所有结点。 （ ）

主观题部分

一、简答题：(50分）

1。 若线性表要求以最快的速度存取而表中元素变动不大,则应采取什么存储结构（顺序或链式结构）？为什么?(10分)

2.将下图所示森林转化为二叉树并在其上标出中序全线索。(10分)

3.已知如右图所示的有向图，写出该图的： （1）邻接矩阵 （2)一个可能的拓扑有序序列。 (10分）

4．设散列函数H（key)=key MOD 7，用线性探测再散列法解决冲突。对关键字序列｛ 13，28，72，5，16，8，7,9，11，29 }在地址空间为0—10的散列区中建散列表,画出此表，并求等概率情况下查找成功时的平均查找长度.（10分)

5．对于序列｛ 26,33，35，29,19，12，22 },

（1)判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调整为堆，写出调整的过程和调整后的序列. （5分) （2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。（5分)

二、算法设计题：（20分）

1、编写递归算法,计算二叉链表存储的二叉树的结点数目.（10分） 2、基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。 （10分)

附：答案或答案要点

第一章章节练习答案 （一）选择题:

1．D 2．C 3．A 4．C 5．A 6．B 7．B 8．D （二）判断题： 1．× 2．√ 3. × 4．√

第二章章节练习答案

（一)选择题： 1．B， A 2．C 3．C 4．C 5．A, B, C 6.B， A （二）判断题： 1．√ 2．√ 3．√ （三）问答题：

1．应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。

2．应采用链式结构.因为在链表中是以结点的指针变化来反映逻辑关系的变化,因此不需要移动元素，效率高.

3．头结点在位置上可视为首元结点的前驱，则做插入/输出操作时，i=1(即插入或删除的位置是1）时不需要做特别处理,否则i=1时需要修改头指针. （四）算法题：

1． status insert_L (LinkList L， ElemType x)

｛/＊带头结点*/ LinkList p，s;

for （p=L; p->next ＆& p—>next—>data〈x；p=p-〉next）； s=(LinkList ）malloc（sizeof(LNode)）； if （!s） return OVERFLOW；

s—>data=x； s—>next=p—>next; p->next=s； return OK; }

2．status insert_Sq（SqList *va,ElemType x）

{ int i;

if（ va->length==va-〉listsize） exit OVERFLOW; for( i=va—〉length-1;i>=0 ＆& va—〉elem[i]>x;-—i）

va->elem[i+1］= va->elem[i］;

va—〉elem［i+1]=x; va-〉length++; return OK; }

3．void reverse(LinkList L） ｛/*带头结点*/ LinkList p;

p=L—〉next; L—>next=NULL； for(; p; p=p->next)｛ q=p-〉next； p—>next=L—>next； L->next=p;

｝ }

第三章章节练习答案

（一）选择题：1。C 2。C 3。 B 4。C 5。 B, A 6. A，C （二)判断题：1．√ 2．× 3．√ 4．√ (三）问答与算法题：

1．所有可能的输出序列有：｛ABC}、｛ACB}、｛BAC｝、{BCA｝、{CBA｝ 2．算法：

＃define MAXQSIZE 100 typedef struct ｛

ElemType *elem; int front; int length; }CycQueue;

status EnQueue(CycQueue *Q， ElemType e） ｛

if (Q—〉length==MAXQSIZE） return ERROR; Q->elem[（Q-〉front+Q—>length) ％ MAXQSIZE］=e; Q—>length++; return OK; }

status DeQueue(CycQueue *Q， ElemType ＊e)

｛

if (Q—〉length==0） return ERROR; *e= Q->elem[Q—〉front]; Q->length - —; return OK； ｝

第四章章节练习答案

1。B 2. D 3. B 4. D 5。 B 6。 A 1.× 2.× 3.× 4。× 第七章章节练习答案

:1。 B 2。 A 3. B 4. B

1. √ 2。 √ 3。 √ 4。 √ 5 1．

。 ×（一）选择题：（二）判断题：

（一）选择题（二）判断题： （三）问答题：

2．证明：由于深度为k的二叉树的最大结点数为二叉树上每一层的最大结点数之和，而二叉树上第i层的最大结点数为2i—1。则

kk(第i层的最大结点数)2i-12k1 i1i13。 证明:设n0为叶子结点个数,n2为度为2的结点个数，

则由二叉树的性质2可知： n2= n0－1

又：满二叉树中只有度为2的结点和叶子结点， 所以满二叉树中的结点总数n= n2+ n0=2 n0－1 又：二叉树中的分支数B=n－1 所以：B=2 n0－1－1=2(n0－1）

4.

（16+17)*2+(9+14+15)*3+6＊4+(2+3)＊5=229

1． void output（BiTree t)

{

if （t）｛

output（t-〉lchild）； printf(t-〉data）; output（t-〉rchild)；

wpl=

（四）算法题： ｝ }

2. void exchange(BiTree t)

{

BiTree temp； if (t){

temp=t-〉lchild; t—>lchild= t->rchild; t->rchild=temp； exchange (t—> lchild）; exchange (t—〉rchild)； } }

3。 int depth(BiTree t）

{

int l,r； if (！t) return 0; l= depth （t-〉lchild）； r= depth (t—>rchild）; return （l〉=r？l：r）+1； ｝

4。 void leaf(BiTree t) {

if (!t） return 0;

if (!t—>lchild ＆＆ ！t->rchild） return 1； return leaf（t—>lchild)+leaf(t—〉rchild)； }

第八章章节练习答案

（一）选择题: 1。A 2。A 3。D， A 4.D， C 5.B， D （二）判断题： 1. √ 2. √ 3.× 4. × 5. √ 6. √ (三）问答及算法题：

1。 图有3个顶点,如果是有向图，该图共有5条弧；如果是无向图,该图共有3条边.

0002。（1)邻接矩阵: 000100010010000001001000000000 010（2）可能的拓扑序列为：156234 （注意4一定是最后一个,2一定在1和5后） (3）123456 （4）562431

3. 一个拓扑排序序列：C1 C3 C2 C5 C4

4．算法： int count (AlGraph G）

｛

for (i=0; ifor （i=0; i< G。vexnum； i++） if (!visited[i]) {sum++； dfs (G, i)；｝ return sum; }

void dfs (AlGraph G， int i) {

visited［i］=true;

for (p=G.vertices[i].firstarc; p； p=p->nextarc） { k=p—>adjvex;

if （!visited[k]） dfs(G， k);

｝ ｝

第九章章节练习答案

(一）选择题：1.B 2。C 3.D 4.B 5.A 6. B 7。 B （二）判断题：1。× 2. × 3。 × 4。 √ （三）问答题：

1。（1）

ASL=(1+2＊2+3*3+3＊4+2＊5）/11=36/11 (2) 2_3树:

（3) 删除 55:

删除84：

2．

ASL=(1+1+1+2+5+1+1+4

）

/8=16/8=2 3。

3、

哈希表

0 11 1 2 13 3 24 4 5 5 1

6 28 1

7 72 2

8 16 4

9 18 3

10 7 4

比较次数 1 1 2 ASL=（1+1+2+1+1+2+4+3+4）/9=19/9

4. 用链地址法处理冲突：（注意链表的有序性）

ASL=（7＊1+4＊2+1＊3）/12=18/12

第十章章节练习答案

（一）选择题：1.D 2.C 3。A 4.A 5.D 6.C 7。D 8.B (二）判断题：1。× 2.√ 3.× 4.√ (三）问答题:

1．应依据“三者取中\"的原则，比较第一个、最后一个和中间位置处记录的关键字，取关键字居中值的记录作为枢轴记录。 2．第一个序列是堆

第二个序列不是堆。调整为堆后的序列为{35，33，26,29，19，12，22｝ 3．初始序列：70，83，100，65，10，9，7，32

直接插入排序每一趟结束时的关键字状态： 第一趟:（70,83），100,65，10，9，7，32 第二趟:（70，83,100），65，10，9，7，32 第三趟:（65，70，83，100）,10，9，7，32

第四趟：（10，65，70，83，100)，9，7,32 第五趟:(9,10,65，70，83,100）,7，32 第六趟：(7,9,10,65，70，83，100）,32 第七趟：(7，9,10,32，65,70，83，100） 快速排序每一趟结束时的关键字状态：： 初始序列：70，83，100，65，10,9，7,32 第一趟： （32，7，9，65，10），70，（100,83) 第二趟： （10，7，9），32,（65）

第三趟： 83，（100) 第四趟： （9，7），10

第五趟: 7，9，10,32，65，70，83，100

4．(1）希尔排序:

d1=3： ｛8 2 13 10 12 14｝ d2=2： ｛8 2 12 10 13 14｝ d3=1: {2 8 10 12 13 14｝

（2） 堆排序初态: {10，2，14，8,12，13} 建堆:｛14 12 13 8 2 10｝

输出14之后再建堆：｛13 12 10 8 2 14｝ 输出13之后再建堆:｛12 8 10 2 13 14} 输出12之后再建堆：{10 8 2 12 13 14｝ 输出10之后再建堆:{8 2 10 12 13 14｝ 输出8之后再建堆:{2 8 10 12 13 14｝有序

考试模拟题答案 客观题部分： 一、单项选择题：

1。A 2。C 3.D 4.B 5。C 6.A 7。 B 8.D 9.D 10。B 二、判断题：

1。B 2。B 3。A 4。A 5。B 6.B 7.A 8.A 9.B 10。A

主观题部分： 一、简答题：

1。应采用顺序结构。因为顺序表是随机存取的存储结构,在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构. 2。

0003。000100010010000001001000000000 010可能的拓扑序列为：156234 （注意4一定是最后一个，2一定在1和5之后） 4.

ASL=（1+1+1+2+5+1+1+4)/8

5. (1) 该序列不是堆。

原始序列： { 26,33，35，29，19，12,22 ｝

交换26和35,建大顶堆：{35,33，26,29，19，12，22 } （2）直接插入排序过程：

原始序列： { （26），33，35,29，19,12，22 ｝

i=2： { （26,33），35，29，19，12，22 ｝

=16/8=2

i=3： { （26,33，35），29，19，12，22 } i=4: { （26，29，33，35）,19,12，22 ｝ i=5： ｛ （19，26，29，33，35)，12，22 ｝ i=6： { (12，19,26，29,33，35）,22 } i=7: ｛ (12，19，22，26，29，33，35）}

二、算法设计题:

。 int nodes（BiTree T) {

if（!T) return 0;

return nodes(T->lchild)+nodes(T—〉rchild）+1; }

2. int count (AlGraph G）

｛

int i, sum;

for (i=0； i〈G.vexnum； i++） visited［i］=false； sum=0；

for （i=0； i< G。vexnum; i++) if (!visited［i]) ｛sum++; dfs (G, i）;} return sum； ｝

void dfs （AlGraph G, int i） {

visited［i]=true;

for （p=G.vertices［i]。firstarc； p; p=p—〉nextarc) k=p-〉adjvex;

if (!visited［k]） dfs(G， k）;}

}

1 ｛