数据结构（C++）有关练习题
实验一 复习C++有关知识实验目的:通过实验掌握下列知识: 1、复习C++有关基本知识；2、熟悉VC编程、编译和调试环境；内容及步骤:编写一个类Complex，定义复数的加法、减法、乘法和除法运算，要求在编写该类时重载这些运算操作符，并重载I/O操作符，以便输入和输出复数；实验报告要求:按要求写出完整的实验代码；实验二 单链表结构及计算实验目的:通过实验掌握下列知识: 1、熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；2、继续熟悉VC编程、编译和调试环境；内容及步骤:1、 设有一个线性表(e0,e1,e2,e3,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原地址内容置换为(en-1,en-2,…,e3,e2,e1,e0)。2、 针对带附加头结点的单链表，试编写下列函数：A． 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL；B． 球最大值函数max：通过单链表的一趟遍历，在单链表中确定值最大的结点；C． 统计函数number：统计单链表中具有给定值x的所有元素数量；D． *建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂度为O(n)。E． *整理函数tideup：在非递减有序的单链表中删除值相同的多余结点。实验报告要求:按要求写出完整的实验代码；实验三 堆栈结构与递归实验目的:通过实验掌握下列知识: 1、掌握堆栈的结构和运算应用；2、掌握并运用递归的概念进行编程；内容及步骤:1、 借助堆栈实现单链表上的逆置运算；要求： a. 用C++编程；b. 首先用C++实现单链表编程，再基于编写好的单链表类，实现堆栈类的定义和实现。c. 链表类和堆栈类都要包含必要的成员函数(按照教材要求)。2、 已知a[n]为整数数组，试写出实现下列运算的递归代码(C或C++代码均可)：要求： a.
求数组中的最大整数；b. 求n个数的和；c. 利用堆栈类，将本题a和b的代码改成非递归的方式。实验报告要求:按要求写出完整的实验代码；实验四 综合(课程设计)内容及步骤:1、假定一维数组a[n]中的每个元素值均在[0，200]区间内，用C++编写一个算法，分别统计出落在[0，20]，[21，50]，[51，80]，[81，130]，[131，200]等各区间内的元素个数。2、 请用C++编写一个算法，完成以下功能：a. 从键盘输入一段文字，以$作结束符号；b. 统计文字中的文本行数，字母，数字以及其他符号的数量，并在屏幕上显示；3、 请用C++编写一个算法，完成矢量的加法与成法运算，运算规则如下：a. 矢量加法：(a1,a2,……,an)+(b1,b2,……,bn)=(a1+b1,a2+b2,……,an+bn)；b. 矢量减法：(a1,a2,……,an)-(b1,b2,……,bn)=(a1-b1,a2-b2,……,an-bn)；c. 矢量点积：(a1,a2,……,an)*(b1,b2,……,bn)=(a1*b1,a2*b2,……,an*bn)；d. 矢量与实数相乘：a*(b1,b2,……,bn)=(a*b1,a*b2,……,a*bn)；4、 请用C++结合链表编写一个简单的机票订票程序，要求完成以下功能：a. 允许出现多个班机；b. 创建一个班机链表，每个节点都包含指向一个乘客链表的指针；c. 该程序要有顾客购票，查询班机起飞降落时间，班机订票情况等3个功能，并实现菜单选项5、 用C++编写一个简单的行编辑器，每个结点保存一行文本，程序以E file开始，然后显示行数和提示符，如果输入I,后面跟着一个数字n，就在第n行之前插入后续文本，如果I后面没有跟数字，就在当前行之前插入文本，如果输入D，后面跟着m，n，一个数字n或者没有数字，就分别删除m到n行，第n行或者当前行，命令L用于显示文本；6、 用C++编写求多项式的和与积的算法，要求如下： a. 要求从键盘分别输入2个多项式的系数以及最高次幂；b. 通过重载操作符+和*，完成多项式的和与积的计算；c. 输出运算结果；7、 编写一个程序，将10进制数转换为其它（2-9）进制数。可以将要转换的数重复除以基数，然后讲除的余数按反方向排列来实现；8、 已知A[n]为正数数组，试写出实现下列运算的递归算法；a. 求数组A中的最大整数；b. 求n个数的平均值；c. 求n个整数的平均值；9、 已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法：a. 求链表中的最大整数；b. 求链表的结点个数；c. 求所有整数的平均数；告要求:写出能运行的完整的代码。实验五 二叉树(一)实验目的:通过实验掌握下列知识: 1、熟悉二叉树的存储结构和遍历算法；2、通过二叉树遍历操作了解递归的本质和方法；内容及步骤:1、 试建立一个二叉搜索树，并实现以下成员函数：a. 默认构造函数和带数据域、左子树指针、右子树指针的构造函数；b. 按照二叉搜索树的要求设计插入函数Insert(int Info)；c. 用递归的方法设计前序遍历和后续遍历函数，遍历时要输出遍历的每个结点；d. 设计一个构造函数，当对象结束时，要释放整个二叉搜索树所占的内存空间(提示，通过后序遍历算法找到叶结点，并删除叶结点，不断重复此过程，直到整科树为空)；2、实现1所要求的代码后，运行设计好的代码，将以下的几组整数序列建成搜索二叉树，并记录下它们的前序遍历序列和后序遍历序列：a. 1、3、5、7、9；b. 1、13、35、13、27；c. 50、25、78、13、44、99、66。实验报告要求:1、 按要求记录下二叉搜索树的完整实验代码；2、 按要求记录下要求的输出结果。实验六 二叉树(二)实验目的:通过实验掌握下列知识: 1、继续熟悉二叉树的存储结构和遍历算法；2、熟悉二叉搜索树的应用，并做一个小型的课程设计；内容及步骤:1、 在前一个实验的基础上，继续增加搜索函数Search(int Info)(如果找到结点，返回指向该结点的指针，如果没有，则返回空指针)和删除函数bool Delete(int Info)，如果找到结点，则删除该结点，并保持二叉搜索树的基本结构，并返回true，否则返回false；2、利用二叉搜索树实现一个音像商店(小型书店、小型超市、或小型药店)的交易管理系统，要求实现以下功能：a. 该系统应该有一个字符型的主菜单；b. 能按字母顺序显示库存商品的名称和数量；c. 能添加和删除新的商品；d. 当输入一个商品时，能显示该商品是否在库存中，如存在库存中，则显示其名称和数量，否则显示“未找到”。e. 如有可能，请建立一个存储商品名称和数量的文本文件，并为二叉搜索树建立一个成员函数SetupInventory()，用于从该文本文件中读取库存商品的数据，实验报告要求:1、 按要求记录下二叉搜索树的完整实验代码；2、 按要求记录下要求的输出结果。实验六 图(课程设计)实验目的:通过实验掌握下列知识: 1、熟悉图的存储结构和遍历算法；2、熟悉图的应用，并做一个小型的课程设计；内容及步骤:1、 设计一个图的类，采用临接表法进行存储，该图每个结点的数据类型类模板的模板参数进行定义(注：需先设计一个结点类Node)；2、 为该类分别设计一个实现深度优先搜索和广度优先搜索的成员函数，并要输出搜索结果；注： 1、为了让你设计的图类拥有数据，可以设计一个成员函数，用于构造你自己预先设计好的图；2、要求的图如下,也可以自己构造图，但是需要注意的是，图不能是退化的单链表：实验报告要求:1、 按要求记录下图的类的完整实验代码；2、 纪录你所使用的图；3、 按要求记录下要求的输出结果；实验八 综合实验内容及步骤:1、请使用C++编写班级学生学籍管理程序每个学生的信息包括：姓名、学号和英语、数学、程序设计及体育成绩。从键盘输入数据，建立数据文件student.dat，然后，利用C++编程完成如下处理：(１)对学生姓名或学号进行查询，显示其信息 。(２)对所有学生，按班级计算每一科平均成绩。(３)分别按英语、数学、程序设计及体育成绩排序并输出到文件。注：要用面向对象的方法来设计程序，每个班是一个类的实例；2、用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。(1)通讯录是按姓名项的字母顺序排列的；(2)能查找通讯录中某人的信息；(3)能添加和删除通讯录中的指定项。注：要用面向对象的方法来设计程序，每个通讯录是一个类的实例；3、从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，进行编码并且输出。注：可用C或C++编写。4、用邻接矩阵或邻接图实现一个有向图的存储，并实现单源最短路径算法的实现(这个类的一个成员函数)，并能输出该图的关键路径。注：1、要用面向对象的方法设计代码；2、一个图是一个类的实例；3、类中要指出该图的起点。实验报告要求:写出完整的代码。习题1
绪论------------------------------------------------------------------------------------6习题2
线性表---------------------------------------------------------------------------------8习题3
栈和队列------------------------------------------------------------------------------11习题4
串---------------------------------------------------------------------------------------13习题5
数组------------------------------------------------------------------------------------15习题6
树与二叉树---------------------------------------------------------------------------17习题7
图---------------------------------------------------------------------------------------24习题8
查找------------------------------------------------------------------------------------31习题9
排序------------------------------------------------------------------------------------34第1部分
C++基本知识各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学发展过程中，早期数据结构教材大都采用PASCAL语言为描述工具，后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C++语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C++语言的学生而编写。编写实验指导书目的为了配合理论教学。程序要求在C++ Builder开发环境之下调试运行，采用面向对象方法进行设计。典型的数据结构被设计成为类（class），典型算法设计成为类的函数成员，然后在主函数中声明创建类对象，根据实际需要调用重要的算法。由于C++的使用具有一定的难度，为了同学更好的学习数据结构自身的知识内容，减轻描述工具所带来的困难，这里针对数据结构上机实验所必须的C++基本知识（结构体、类等等）做补充介绍。一、 源程序组成这部分内容详细参见本指导书的第3部分的程序实例。二、结构体及运用数据结构课程所研究的问题均运用到“结构体”和“类”。在C++语言中结构体和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式：struct
结构体类型名{
类型名1
变量名1；
//数据子域类型名2
变量名2；……类型名n
变量名n；}其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是：结构体类型名
结构体变量名；一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型（int
char 等），也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数组。它们也可以称为结构体的数据成员，它们的访问控制具有‘公有’属性。1. 通过“结构体变量名.数据子域” 可以访问数据子域。// 设计Student结构体，在主程序中运用。#include
#include
#include
struct
Student
//定义结构体Student{
long
num;
//
学号int
x;
//
成绩char
name[10];
//
姓名}int main( ) { Student
s1;
//声明创建一个结构体变量s1//为s1的数据子域提供数据s1.num=1001 ;
s1. x=83;
strcpy( s1.name, “ 李
明”)；
//输出结构体变量s1 的内容coutcoutcout_getch(); return 0;}2. 设计一维数组，每个数组元素是Student结构体类型，通过以下语句段可以说明结构体数组的一般用法：通过“结构体数组名[下标].数据子域”访问数据域。Student
a[5];
//声明创建一个结构体数组afor(int
i=0, i{
cout>a[i].num;
//输出数组元素a[i]的学号域cout> a[i].name；
//输出数组元素a[i]的姓名域cout>a[i].x;
//输出数组元素a[i]的成绩域
}
以上是关于结构体的基本概念和简单运用。三、
类的基本概念及运用类的是面向对象程序的基本单位。类是由数据成员和相关的函数成员组成。从面向对象的角度考虑“学生”这个类，它不仅包括“学生”的一般属性：学号、姓名、成绩等等，还应包括对于这些属性的操作：输入/输出、听课、实验、等等。
类定义的一般格式：class
类名{
若干数据成员；若干函数成员；}；类的数据成员和函数成员均存在访问控制权限问题。访问控制分为三种：公有（public）、私有(private)和受护(protected)。数据成员的定义和结构体中的数据域定义是相似的。不同的是它们必须明确访问控制。而公有数据成员，可以认为与结构体的数据域的访问权限相同。成员函数的定义又和一般函数的定义基本相同。不同的是类中成员函数也必须明确访问控制权限。如果在类之中定义成员函数带函数体，并未有什么特殊之处。如果在类之中仅有成员函数的原型声明，当在类定义之外定义函数体时，需要加上类限定标识“类名：：”。下面是“学生”类的定义：class
Students
//定义类结构体Students{
private:
//私有成员long
num;
//
学号int
x;
//
成绩char
name[10];
//
姓名public:
//公有成员Students();~Students() { };void SetDat( long n, int x0, char *na0 ) { num=n;
x=x0;
strcpy( name,na0);}void PrintOut( );
//输出函数的原型声明…….;};void
Students::PrintOut( )
// 输出函数前加Students::
{
coutcoutcout
}在主程序中运用类
Students。int main( ) {
Students
s;
//声明创建一个类对象s，调用构造函数s.PrintOut( );
//输出s的内容long
m;
int y;
char
xname[10];
coutcin>>m>>y>>xname;s. SetDat( m, y, xname ) ;
//修改对象s数据
s. PrintOut();
//输出改变后s的内容_getch(); return 0;}运行结果：姓名：O学号：0成绩：0
输入学号，成绩，姓名：1001
90
WangMing姓名：WangMing学号：1001成绩：90这个例题中数据成员全部定义为私有（private），以便保证数据安全性。而函数成员全部定义为公有（public）成员函数，可以作为类对外部的的接口。 通过s. SetDat( m, y, xname ) ; 直接访公有函数成员SetDat(
)， 将实参（主函数的局部变量m, y, xname） 的数据赋给私有数据成员 num，x，name。
通过 s.PrintOut( );直接访公有函数成员PrintOut( )，间接访问输出私有成员num，x，name。四、 结构体在类中的使用1．结构体数组做类的数据成员const int MAXSIZE=100;
// 数组的容量struct
ElemType
// 数据元素的类型{
int numb;char name[20];long tel;};class Sqlist{ private:ElemType
elem[MAXSIZE];
//结构体ElemType类型的数组elem[ ]做数据成员int length;public:Sqlist( void);~Sqlist(){ };//其他函数……};2.结构体指针变量做类的数据成员struct NodeType
// 结点的结构定义{
int
data;
//
数据域
NodeType *next;
//
指针域
};class Link
//类声明{ private:NodeType
*Head;
//指向结构构体NodeType的指针变量Head做数据成员
public:Link ( ){
Head=new NodeType;
// 为头结点申请空间Head->next=Head;
// 头结点Head 形成空环};~ Link (){ };void
creat();void
outs();
};第2部分
书面练习题习题1
绪论1.1
单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①
、数据信息在计算机中的②
以及一组相关的运算等的课程。① A．操作对象　　　Ｂ．计算方法　　Ｃ．逻辑结构　　Ｄ．数据映象② A．存储结构
Ｂ．关系
Ｃ．运算
Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①
的有限集合，R是D上的②
有限集合。① A．算法
Ｂ．数据元素
Ｃ．数据操作
Ｄ．数据对象② A．操作
Ｂ．映象
Ｃ．存储
Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成
。A．动态结构和静态结构
Ｂ．紧凑结构和非紧凑结构
Ｃ．线性结构和非线性结构
Ｄ．内部结构和外部结构4. 算法分析的目的是①
，算法分析的两个主要方面是②
。① A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进
D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性
B. 正确性和简明性C. 可读性和文档性
D. 数据复杂性和程序复杂性5. 计算机算法指的是①
，它必具备输入、输出和②
等五个特性。①
A. 计算方法
B. 排序方法C. 解决问题的有限运算序列
D. 调度方法② A. 可行性、可移植性和可扩充性
B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性
D. 易读性、稳定性和安全性1.2
填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括
、
和
三种类型，树形结构和图形结构合称为
。2. 在线性结构中，第一个结点
前驱结点，其余每个结点有且只有
个前驱结点；最后一个结点
后续结点，其余每个结点有且只有
个后续结点。3. 在树形结构中，树根结点没有
结点，其余每个结点有且只有
个直接前驱结点，叶子结点没有
结点，其余每个结点的直接后续结点可以
。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以
。5. 线性结构中元素之间存在
关系，树形结构中元素之间存在
关系，图形结构中元素之间存在
关系。6. 算法的五个重要特性是__
__ , __
__ , ___
_
, __
__ , _
___。7. 分析下面算法（程序段），给出最大语句频度
，该算法的时间复杂度是__
__。for (i=0;i
for (j=0;j
A[i][j]=0;8. 分析下面算法（程序段），给出最大语句频度
，该算法的时间复杂度是__
__。for (i=0;i
for (j=0; jA[i][j]=0;9. 分析下面算法（程序段），给出最大语句频度
，该算法的时间复杂度是__
__。s=0;for (i=0;i
for (j=0;j
for (k=0;k
s=s+B[i][j][k];sum=s;10. 分析下面算法（程序段）给出最大语句频度
，该算法的时间复杂度是__
__。i=s=0;while (s{
i++;
s+=i;
//s=s+i }
11. 分析下面算法（程序段）给出最大语句频度
，该算法的时间复杂度是__
__。i=1;while (i
i=i*2;1.3 算法设计题1. 试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值.2. 试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。习题答案1.1
1. C , A
2. B,D
3. C
4. C, A
5. C,B1.2
1. 线性结构、树形结构、图形结构，非线性结构2. 没有、1、没有、13. 前驱、1、后续、任意多个4. 任意多个5. 一对一、一对多、多对多6. 有穷性、确定性、可行性、输入、输出7. 最大语句频度：n2 ， 时间复杂度：. O (n2)8. 最大语句频度：n (n+1)/2 ， 时间复杂度：. O (n2)9. 最大语句频度：n3 ， 时间复杂度：. O (n3)10. 最大语句频度：n
， 时间复杂度：.
O (n )
11. 最大语句频度：log2n， 时间复杂度：. O (log2n )习题2
线性表2.1 单项选择题1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__
__。A. 110
B. 108
C. 100
D. 1202. 线性表的顺序存储结构是一种__ _的存储结构，而链式存储结构是一种__
_的存储结构。A．随机存取
B．索引存取
C．顺序存取
D．散列存取3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__
_。A. 正确
B. 不正确4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__
_。A. 必须是连续的
B. 部分地址必须是连续的C. 一定是不连续的
D. 连续或不连续都可以5. 在以下的叙述中，正确的是__
_。A. 线性表的顺序存储结构优于链表存储结构B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况D. 线性表的链表存储结构优于顺序存储结构6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__
_。A. 正确
B. 不正确7. 不带头结点的单链表head为空的判定条件是____。A. head= =NULL
B. head->next= =NULLC. head->next= =head
D. head!=NULL8. 带头结点的单链表head为空的判定条件是____。A. head= =NULL
B. head->next= =NULLC. head->next= =head
D. head!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足____。A. p->next= =NULL
B. p= =NULLC. p->next= =head
D. p= =head
10. 在双向循环链表的p所指结点之后插入s所指结点的操作是____。A. p->right=s;
s->left=p;
p->right->left=s;
s->right=p->right;B. p->right=s;
p->right->left=s;
s->left=p;
s->right=p->right;C. s->left=p;
s->right=p->right;
p->right=s;
p->right->left=s;D. s->left=p;
s->right=p->right;
p->right->left=s;
p->right=s;11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。A. s->next=p->next;
p->next=s;
B. p->next=s->next;
s->next=p;B. q->next=s;
s->next=p;
C.
p->next=s;
s->next=q;12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。A.
s->next=p;
p->next=s;
B. s->next=p->next;
p->next=s;C.
s->next=p->next;
p=s;
C. p->next=s;
s->next=p;13. 在一个单链表中，若删除p所指结点的后续结点，则执行____。A. p->next= p->next->next；
B. p= p->next;
p->next= p->next->next；C. p->next= p->next;
D. p= p->next->next；14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。A. n
B. n/2
C. (n-1)/2
D. (n+1)/215. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__
__。A. O(1)
B. O(n)
C. O (n2)
D. O (nlog2n)16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是__
__。A. O(1)）
B. O(n)
C. O (n2)
D. O (n*log2n)2.2
填空题（将正确的答案填在相应的空中）1. 单链表可以做__
__的链接存储表示。2. 在双链表中，每个结点有两个指针域，一个指向____
__，另一个指向___ __。3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q->next!=p)
q=q->next;s= new
Node;
s->data=e;q->next=
;
//填空s->next=
;
//填空4. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p->next;p->next= _
___;
//填空delete
;
//填空5. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__
__和p->next=____的操作。6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__
__；在给定值为x的结点后插入一个新结点的时间复杂度是__
__。2.3 算法设计题:1.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,…. an）逆置为(an, an-1,…., a1)。3. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。4. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。习题答案2.1
1. B
2. A, C
3. B
4. D
5. C
6. A
7. A
8. B9. C
10. D
11.B
12.B
13.A
14.D
15.B
16.C2.2
1. 线性结表
2. 前驱结点、后继结点3.
s, p
4.
q->next,
q5.
p->next, s
6.
O (1)
, O (n)习题3 栈和队列3.1
单项选择题1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。A. edcba
B. decba
C. dceab
D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。A. i
B. n=i
C. n-i+1
D. 不确定3. 栈结构通常采用的两种存储结构是____。A. 顺序存储结构和链式存储结构B. 散列方式和索引方式C. 链表存储结构和数组D. 线性存储结构和非线性存储结构4. 判定一个顺序栈ST（最多元素为m0）为空的条件是____。A.
top !=0
B. top= =0
C.
top !=m0
D. top= =m0-15. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。A. top！=0
B. top= =0
C. top！=m0
D. top= =m0-16. 栈的特点是____，队列的特点是____。A. 先进先出
B. 先进后出7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ __。(不带空的头结点)A. HS—＞next=s;B.
s—＞next= HS—＞next;
HS—＞next=s;C.
s—＞next= HS;
HS=s;D.
s—＞next= HS;
HS= HS—＞next;8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__
__。(不带空的头结点) A. x=HS;
HS= HS—＞next;
B.
x=HS—＞data;C. HS= HS—＞next; x=HS—＞data;
D.
x=HS—＞data; HS= HS—＞next;9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，4，110. 判定一个循环队列QU（最多元素为m0）为空的条件是____。A. rear - front= =m0
B. rear-front-1= =m0C. front= = rear
D. front= = rear+111. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是____。A. ((rear- front)+ Maxsize)% Maxsize = =m0B. rear-front-1= =m0
C. front= =rear
D. front= = rear+112. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。A. (rear-front+m)%m
B. rear-front+1C. rear-front-1
D. rear-front13. 栈和队列的共同点是____。A. 都是先进后出
B. 都是先进先出C. 只允许在端点处插入和删除元素
D. 没有共同点3.2
填空题（将正确的答案填在相应的空中）1. 向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。2. 向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。3. 向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个元素。4. 向栈中压入元素的操作是____。5. 对栈进行退栈时的操作是____。6. 在一个循环队列中，队首指针指向队首元素的____。7. 从循环队列中删除一个元素时，其操作是____。8. 在具有n个单元的循环队列中，队满时共有____个元素。9. 一个栈的输入序列是12345，则栈的输出序列43512是____。10. 一个栈的输入序列是12345，则栈的输出序列12345是____。3.3 算法设计题:1. 输入一个任意的非负十进制整数,输出与其等值的八进值数。2. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E↑F3. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。习题答案3.1
1. C
2. C
3. A
4. B
5.D
6. BA
7.C
8. B
9. C
10. C
11. A
12. A
13.C
3.2
1. 线性、任何、栈顶、队尾、队首
2. n-i+1
3. n-i4.先移动栈顶指针，后存入元素
5. 先取出元素，后移动栈顶指针6.前一个位置
7. 先移动队首元素，后取出元素8. n-1
9. 不可能的
10. 可能的习题4
串4.1
单项选择题1．以下叙述中正确的是
。A.串是一种特殊的线性表
B.串的长度必须大于零C.串中无素只能是字母
D.空串就是空白串2．空串与空格串是相同的，这种说法____。A. 正确
B. 不正确3．串是一中特殊的线性表，其特殊性体现在____。A. 可以顺序存储
B. 数据元素是一个字符C. 可以链接存储
D. 数据元素可以是多个字符4．设有两个串p和q，求q在p中首次出现的位置的运算称作____。A. 连接
B. 模式匹配C. 求子串
D. 求串长5．设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是____。A. BCDEF
B. BCDEFGC. BCPQRST
D. BCDEFEF6．设串的长度为n，则它的子串个数为
。A.n
B.n(n+1)
C.n(n+1)/2
D.n(n+1)/2+14.2
填空题（将正确的答案填在相应的空中）1．串的两种最基本的存储方式是____。2．两个串相等的充分必要条件是____。3．空串是____，其长度等于____。4．空格串是____，其长度等于____。5．设s=’I︺AM︺A︺TEACHER’,其长度是____。4.3
判断题1．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。
（）2．子串定位函数的时间复杂度在最坏情况下为O（n*m），因此子串定位函数没有实际使用的价值。
（）3．KMP算法的最大特点是指主串的指针不需要回溯。
（）4．设模式串的长度为m，目标串的长度为n；当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价也可能会更为节省。
（）5．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 （）4.3 算法设计题1．编写算法，从串s 中删除所有和串 t相同的子串。2．编写算法，实现串的基本操作Replace(&S,T,V)。3．写一个递归算法来实现字符串逆序存储，要求不另设存储空间。习题答案4.1
1．A
2．B
3．B
4．B
5．D
6．C4.2
1．顺序存储方式和链接存储方式2．两个串的长度相等且对应位置的字符相同3．零个字符的串、零4．由一个或多个空格字符组成的串、其包含的空格个数5．144.3
×
×
√
√
×4.4
3.
void reverse(char
arr[]){char ch;int i=1; do{cin>>ch;reverse(arr);arr[i]=ch;i++;}while(ch!=’#’&&i}习题5
数组和广义表5.1 单项选择题1. 常对数组进行的两种基本操作是____。A. 建立与删除
B. 索引和修改
C. 对数据元素的存取和修改
D. 查找与索引2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要①_
_个字节；M数组的第8列和第5行共占②____个字节。① A. 90
B. 180
C. 240
D. 540② A. 108
B. 114
C. 54
D. 603. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。A. 80
B. 100
C.240
D. 2704. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。A. SA+141
B. SA+144
C. SA+222
D. SA+2255. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。A. SA+141
B. SA+180
C. SA+222
D. SA+2255.2
填空题（将正确的答案填在相应的空中）1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_______。2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是____。3. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是____。4．求下列广义表操作的结果：(1) GetTail[GetHead[((a,b),(c,d))]];(2) GetTail[GetHead[GetTail[((a,b),(c,d))]]]5.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子banana分别从下列广义表中分离出来.(1)
L1=(((apple)),((pear)),(banana),orange);(2)
L2=(apple,(pear,(banana),orange));5.3 算法设计题:1. 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放结果矩阵。2. 假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A，B之外的附加空间，你的算法能否达到O（m+n）的时间复杂度？其中m和n分别为A，B矩阵中非零元的数目。3．试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。习题答案5.1
1. C
2. D,A
3.C
4. C
5. B
5.2
1. LOC (A[0][0])+(n*i+j)*k
2.
200+（6*20+12）= 3263. 1000+((18-10)*6 +(9-5))*4 = 12084．(1). (b)
(2). (d)5.
(1) GetHead [GetHead[GetTail[GetTail[L1]]]];(2) GetHead [GetHead [GetHead[GetTail[L2 ]]]];习题6
树和二叉树6.1
单项选择题1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。A. 正确
B. 错误2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为
个。
A．15
B．16
C．17
D．473. 按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。A. 3
B. 4
C. 5
D. 64. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。A. 5
B. 6
C. 30
D. 325. 深度为5的二叉树至多有____个结点。A. 16
B. 32
C. 31
D. 106. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_
___。 A. 2h
B. 2h-1
C. 2h+1
D. h+17. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。A. n=h+m
B. h+m=2n
C. m=h-1
D. n=2 h-18. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。A.不发生改变
B.发生改变
C.不能确定
D.以上都不对9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。
A. uwvts
B. vwuts
C. wuvts
D. wutsv10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。
A. 正确
B. 错误11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。A. bdgcefha
B. gdbecfha
C. bdgaechf
D. gdbehfca12. 在一非空二叉树的中序遍历序列中，根结点的右边____。A. 只有右子树上的所有结点
B. 只有右子树上的部分结点C. 只有左子树上的部分结点
D. 只有左子树上的所有结点13. 如图6.1所示二叉树的中序遍历序列是____。A. abcdgef
B. dfebagc
C. dbaefcg
D. defbagc图6.1
14. 一棵二叉树如图6.2所示，其中序遍历的序列为__
__。A. abdgcefh
B. dgbaechf
C. gdbehfca
D. abcdefgh15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是
。A．a在b的右方
B．a在b的左方C．a是b的祖先
D．a是b的子孙16. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。
A. acbed
B. decab
C. deabc
D. cedba17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。A. 二叉链表
B. 广义表存储结构
C. 三叉链表
D. 顺序存储结构18. 如图6.3所示的4棵二叉树，____不是完全二叉树。19. 如图6.4所示的4棵二叉树，____是平衡二叉树。20. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。A. t—＞left=NULL
B. t—＞ltag=1C. t—＞ltag=1且t—＞left=NULL
D. 以上都不对21. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。
A. 正确
B. 错误22. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。
A. 正确
B. 错误23. 具有五层结点的二叉平衡树至少有____个结点。A. 10
B. 12
C. 15
D. 1724. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同D.以上都不对25. 树最适合用来表示____。A. 有序数据元素
B. 无序数据元素 C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据6.2
填空题（将正确的答案填在相应的空中）1. 有一棵树如图6.5所示，回答下面的问题：⑴ 这棵树的根结点是____；⑵ 这棵树的叶子结点是____；⑶ 结点k3的度是____；⑷ 这棵树的度是____；⑸ 这棵树的深度是____；⑹ 结点k3的子女是____；⑺ 结点k3的父结点是____；2. 指出树和二叉树的三个主要差别____、____、____。3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是___
_。4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为__
__。5. 深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=____。7. 一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。8. 结点最少的树为____，结点最少的二叉树为____。9. 现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。10. 由如图6.7所示的二叉树，回答以下问题：⑴ 其中序遍历序列为____；⑵ 其前序遍历序列为____；⑶ 其后序遍历序列为____；6.3
简答题1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。3. 由如图6.7所示的二叉树，回答以下问题：（1）画出该二叉树的中序线索二叉树；（2）画出该二叉树的后序线索二叉树；（3）画出该二叉树对应的森林。4. 已知一棵树如图6.8所示，转化为一棵二叉树，表示为____。5. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。6. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少?7. 证明:一棵满k叉树上的叶子结点数n 和非叶子结点数n 之间满足以下关系:n =(k-1)n +16.4
算法设计题1. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。2．试编写算法，对一棵二叉树,统计叶子的个数。3．试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。7. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。8. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。习题答案6.1
1. B
2. B
3. C
4. C
5. C
6. A
7. D
8. A
9. C
10. A11. D
2. A
13. B
14. B
15. B
16. D
17. C
18. C
19. B
20. B
21. B
22. B
23. B
24. A
25. C 6.2
1. ⑴ k1
⑵ k2,k5,k7,k4
⑶ 2
⑷ 3
⑸ 4
⑹ k5,k6
⑺ k1 2. 树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分；3. 树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解决树的有关问题。4. 如图6.9所示 5.
2 k-1 、
2 k-1
、
2 k-2+16.
n2+17.
2 i-1
2[log2n+1]-1
2[log2n+1] –18. 只有一个结点的树；空的二叉树9.
5；如图6.10所示10. dgbaechif 、abdgcefhi 、gdbeihfca 、6.3
1.
5种,
图6.112. 二叉树如图6.12所示。3.
中序线索二叉树如图6.13（左）所示；后序线索二叉树如图6.13（右）所示；该二叉树转换后的的森林如图6.14所示。4. 图6.8的树转化为一棵二叉树如下，图6.15：5. 画出构造Huffman树如图6.16所示，计算其带权路径长度为
。6. 一棵含有N个结点的k叉树,可能达到的最大深度 h=N-k+1 ，最小深度各为: logkN+1。习题7
图7.1
单项选择题1．在一个图中，所有顶点的度数之和等于所有边数的____倍。A. 1/2
B. 1
C. 2
D. 4 2．任何一个无向连通图的最小生成树
。A.只有一棵
B.有一棵或多棵
C.一定有多棵
D.可能不存在3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。A. 1/2
B. 1
C. 2
D. 44．一个有n个顶点的无向图最多有____条边。A. n
B. n(n-1)
C. n(n-1)/2
D. 2n5．具有4个顶点的无向完全图有____条边。A. 6
B. 12
C. 16
D. 206．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。A. 5
B. 6
C. 7
D. 87．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。A. n
B. n+1
C. n-1
D. n/28．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。A. n
B. (n-1)2
C. n-1
D. n29．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。① A. n
B. n+1
C. n-1
D. n+e② A. e/2
B. e
C.2e
D. n+e
10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②__。① A. a,b,e,c,d,f
B. e,c,f,e,b,d
C. a,e,b,c,f,d
D. a,e,d,f,c,b② A. a,b,c,e,d,f
B. a,b,c,e,f,d
C. a,e,b,c,f,d
D. a,c,f,d,e,b11．已知一有向图的邻接表存储结构如图7.2所示。⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。A. v1,v2,v3,v5,v4
B. v1,v2,v3,v4,v5C. v1,v3,v4,v5,v2
D. v1,v4,v3,v5,v2⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。A. v1,v2,v3,v4,v5
B. v1,v3,v2,v4,v5C. v1,v2,v3,v5,v4
D. v1,v4,v3,v5,v212．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。A. 求关键路径的方法
B. 求最短路径的Dijkstra方法C. 宽度优先遍历算法
D. 深度优先遍历算法15．关键路径是事件结点网络中
。A.从源点到汇点的最长路径
B.从源点到汇点的最短路径C.最长的回路
D.最短的回路16．下面不正确的说法是
。（1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；（2）AOE网工程工期为关键活动上的权之和；（3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。A.（1）
B.（2）
C.（3）
D.（1）、（2）17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是
。A.逆拓朴有序的
B.拓朴有序的
C.无序的18．在图7.3所示的拓朴排列的结果序列为
。A.125634
B.516234
C.123456
D.52163419．一个有n个顶点的无向连通图，它所包含的连通分量个数为
。A.0
B.1
C.n
D.n+120．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为
。A.k1
B.k2
C.k1-k2
D.k1+k221．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为
。A.k1
B.k2
C.k1-k2
D.k1+k27.2
填空题（将正确的答案填在相应饿空中）1．n个顶点的连通图至少____条边。2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。图7.4
图G的邻接表5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。7．如果含n个顶点的图形成一个环，则它有
棵生成树。8．一个非连通无向图，共有28条边，则该图至少有
个顶点。9．遍历图的过程实质上是
。BFS遍历图的时间复杂度为
，DFS遍历图的时间复杂度为
，两者不同之处在于
，反映在数据结构上的差别是
。10．一个图的
表示法是唯一的，而
表示法是不唯一的。11．有向图中的结点前驱后继关系的特征是
。12．若无向图G的顶点度数最小值大于等于
时，G至少有一条回路。13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是
的。7.3
综合题1．已知如图7.5所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接距阵；（3）邻接表；（4）逆邻接表；（5）强连通分量。2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （1）图7.6（2）图7.73．试列出图7.8中全部的拓扑排序序列。图7.84．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。图7.95．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下：(1)请画出该AOE图。(2)计算完成整个计划需要的时间。(3)求出该AOE网的关键路径。∝ 6 4 5 ∝ ∝ ∝ ∝ ∝∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝∝ ∝ ∝ ∝ ∝ ∝ 9 7 ∝∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝习题答案7.1
1. C
2.B
3.B
4. C
5. A
6. A
7.C8.D
9. AC 10.DB
11. CB
12. A
13. D
14.D
15.A
16.A
17.A
18.B
19.B
20.B
21.A 7.2
1.n-1
2. 1;0
3. 1
4.v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v65.求矩阵第i列非零元素之和 6. 将矩阵第i行全部置为零7.n8.99.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）；遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过的结点。10．邻接矩阵
邻接表11．一个结点可能有若干个前驱，也可能有若干个后继12．213．唯一7.3
1.2.(1)．（2）3．1523641526341562345612345162345126345123644．5．(1)该AOE图为：(2)完成整个计划需要18天。(3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，）习题8
查找8.1
单项选择题1.顺序查找法适合于存储结构为____的线性表。A. 散列存储
B. 顺序存储或链接存储C. 压缩存储
D. 索引存储2.对线性表进行二分查找时，要求线性表必须____。A. 以顺序方式存储
B. 以链接方式存储C. 以顺序方式存储，且结点按关键字有序排序D. 以链接方式存储，且结点按关键字有序排序3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.A. n
B. n/2
C. (n+1)/2
D. (n-1)/24.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。A．O（n2）
B. O(nlog2n)
C. O(n)
D. O(log2n)5.二分查找和二叉排序树的时间性能____。A. 相同
B. 不相同6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。A. 1
B. 2
C. 4
D. 87.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr (15)=4;
addr (38)=5;
addr (61)=6;
addr (84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是____。A. 8
B. 3
C. 5
D. 98.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。A. 35/12
B. 37/12
C. 39/12
D. 43/129．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为
。A.从第0个元素往后查找该数据元素B.从第1个元素往后查找该数据元素C.从第n个元素往开始前查找该数据元素D.与查找顺序无关10．解决散列法中出现的冲突问题常采用的方法是
。A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址
。A.必须大于等于原散列地址B.必须小于等于原散列地址C.可以大于或小于但不能等于原散列地址D.地址大小没有具体限制12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于
。A.静态查找表
B.动态查找表 C.静态查找表与动态查找表
D两种表都不适合13.散列表的平均查找长度
。A.与处理冲突方法有关而与表的长度无关B.与处理冲突方法无关而与表的长度有关C.与处理冲突方法有关而与表的长度有关D.与处理冲突方法无关而与表的长度无关8.2
填空题（将正确的答案填在相应的空中）1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。3.折半查找的存储结构仅限于____，且是____。4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____；6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行
次查找可确定成功；查找47时，需进行
次查找成功；查找100时，需进行
次查找才能确定不成功。7．二叉排序树的查找长度不仅与
有关，也与二叉排序树的
有关。8．一个无序序列可以通过构造一棵
树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。9．平衡二叉排序树上任一结点的平衡因子只可能是
、
或
。10．
法构造的哈希函数肯定不会发生冲突。11．在散列函数H(key)=key%p中，p应取____。12．在散列存储中，装填因子 的值越大，则____； 的值越小，则____。8.3
综合练习题:1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。2.含九个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？3.试从空树开始，画出按以下次序向2-3树即3阶B-树中插入关键码的建树过程：20,30,50,52,60,68,70.如果此后删除50和68，画出每一步执行后2-3树的状态。4. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。5. 已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树，注意边插入边平衡。习题答案8.1
1．B
2．C
3．C
4．D
5．B
6．C
7．D
8．B 9．C
10．D
11．C
12．B
13．C8.2
1. （n+1）/2 、((n+1)*log2(n+1))/n-1 、1+ （ 为装填因子）2. 哈希表查找法3. 顺序存储结构、有序的4. 1、2、4、8、5、3．7（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12）5. O（n）、O(log2n)6．2、4、37．结点个数n、生成过程8．二叉排序树9．0、1、-110．直接定址11．素数12．存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小习题9
排序9.1
单项选择题1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用____排序法。A. 起泡排序
B. 快速排序
C. 堆排序
D. 基数排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。A.
插入排序
B. 选择排序
立即下载
上传者：
apple_rice
时间：
2008-01-02