下载文档原格式
第6章数组和广义表1．简述数组属于线性表的原因。
答：数组可以看成是线性表在下述含义上的扩展：线性表中的数据元素本身也是一个线性表。
在n维数组中的每个数据元素都受着n个关系的约束，在每个关系中，数据元素都有一个后继元素（除去最后一个元素）和一个前驱元素（除去最前一个元素）。
因此，这n个关系中的任一关系，就其单个关系而言仍是线性关系。
例如，m×n的二维数组的形式化定义如下：2．n阶对称矩阵A的下三角元素存储在一维数组B中，则B包含多少个元素?答：B中包含n阶对称矩阵A的下三角和主对角线上的元素，其元素个数为1+2+…+n=(n(n+1))/2，所以B包含(n(n+1))/2个元素。
3．设有三对角矩阵A n×n（从A1，1开始），将其三对角线上元素逐行存于数组B ［1．．m］中，使B［k］＝A i，j，求：（1）用i，j表示k的下标变换公式；（2）用k表示i，j的下标变换公式。
答：在三对角矩阵中，除了第一行和最后一行各有两个元素外，其余各行均有三个非零元素，所以共有3n-2个非零元素。
（1）主对角线左下角的对角线上的元素的下标有关系式：i=j+1，此时的k有：k=3(i-1)=2(i-1)+j主对角线上的元素的下标有关系式：i=j，此时的k有：k=3(i-1)+1=2(i-1)+j主对角线右上角的对角线上的元素的下标有关系式：i=j-1，此时的k有：k=3(i-1)+2=2(i-1)+j综合起来得到：k=2(i-1)+j（2）k与i，j的变换公式为：i=k/3+1；j=k-2(i-1)4．用十字链表表示一个有k个非0元素的m×n的稀疏矩阵，则其总的节点数为多少?答：该十字链表有一个十字链表头节点，MAX(m，n)个行、列头节点。
另外，每个非零元素对应一个节点，即k个元素节点，所以共有MAX(m，n)+k+1个节点。
5．设定二维整数数组B［0．．m-1，0．．n-1]的数据在行、列方向上都按从小到大的顺序排序，且整型变量x中的数据在B中存在。
第四部分模拟试题李春葆《数据结构教程》（第4版）模拟试题及详解（一）一、单项选择题（每小题2分，共20分）1．队列的特点是（）。
A．先进后出B．先进先出C．任意位置进出D．前面都不正确【答案】B2．有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（）遍分配与收集。
A．nB．dC．rD．n-d【答案】B【解析】基数排序是按组成关键字的各位值进行分配收集而完成的。
3．在二叉树节点的先序序列、中序序列和后序序列中，所有叶子节点的先后顺序（）。
A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同【答案】B【解析】无论是哪种遍历方式，遍历叶子节点时，都是先访问左子树，后访问右子树。
4．限定在一端加入和删除元素的线性表称为（）。
A．双向链表B．单向链表C．栈D．队列【答案】C【解析】根据栈后进先出的特性，可见栈都在一端对元素进行操作。
5．设内存工作区可容纳8个记录，初始文件共有64个关键字不同的记录，且已按关键字递减排列，如用置换．选择排序产生初始归并段，最长初始归并段所含记录数是（）。
A．6B．7C．8D．9【答案】C【解析】对于置换选择排序，输入的文件是以关键字降序排列时，所得的初始归并段的最大长度为工作区的大小。
当输入的文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段。
6．设森林F对应的二叉树为B，它有m个节点，B的根为p，p的右子树上的节点个数为n，森林F中第一棵树的节点个数是（）。
A．m-n-1B．n+lC．m-n+1D．m-n【答案】D7．设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（）。
A．12B．13C．14D．15【答案】C【解析】k一路平衡归并，归并趟数公式s=[1og k m]，m指归并段数，s指趟数。
要三遍完成遍历，那就看两遍完成排序的需遍历的最小数。
把s=2和m=198带入公式，可知两遍完成排序时k最小为15，所以k<15。
李春葆《数据结构教程》（第4版）笔记和课后习题详解第8章图8.1复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。
采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。
抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。
（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。
②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。
③出度以顶点i为起点的出边的数目，称为该顶点的出度。
一个顶点的入度与出度的和为该顶点的度。
（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。
（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。
②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。
（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。
（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。
②路径长度路径长度是指一条路径上经过的边的数目。
（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。
李春葆《数据结构教程》（第4版）笔记和课后习题详解第11章外排序11.1复习笔记一、外排序概述文件存储在外存上，因此外排序方法与各种外存设备的特征有关。
外排序的基本方法是归并排序法。
它分为以下两个步骤：1．生成若干初始归并段（顺串）将一个文件（含待排序的数据）中的数据分段读入内存，在内存中对其进行内排序，并将经过排序的数据段（有序段）写到多个外存文件上。
2．多路归并对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。
二、磁盘排序1．磁盘排序概述磁盘是直接存取设备，读／写一个数据块的时间与当前读／写头所处的位置关系不大，存放在磁盘中的文件的排序属典型的外排序。
磁盘排序过程如图11-1所示.图11-1磁盘排序过程磁盘中的F in文件包括待排序的数据，通过相关算法将F in文件中数据一部分一部分地调入内存（每个记录被读一次）处理，产生若干个文件F1～F n（每个记录被写一次），它们都是有序的，称为顺串。
然后再次将F1～F n文件中的记录调入内存（每个记录被读一次），通过相关归并算法产生一个有序的F out文件（每个记录被写一次），从而达到数据排序的目的。
可见，提高排序速度很重要的一个方面是减少对数据的扫描遍数。
2．生成初始归并段使用置换—选择的排序算法用于生成较长的初始归并段。
采用置换—选择排序算法生成初始归并段时，内排序基于选择排序，即从若干个记录中通过关键字比较选择一个最小的记录，同时在此过程中进行记录的输入和输出，最后生成若干个长度可能各不相同的有序文件。
基本步骤如下：（1）从待排序文件F in中按内存工作区WA的容量（设为w）读入w个记录，设归并段编号i=1；（2）从WA中选出关键字最小的记录R min；（3）将R min 记录输出到文件F i 中，作为当前归并段的一个成员；（4）若F in 不空，则从F in 中读入下一个记录到WA 中替代刚输出的记录；（5）从WA 工作区中所有大于或等于R min 的记录中选择出最小记录作为新的R min ，转（3），直到选不出这样的R min ；（6）置i=i+1，开始一个新的归并段；（7）若WA 工作区已空，则初始归并段已全部产生，否则转（2）。
第2章线性表2.1 复习笔记一、线性表及其逻辑结构1．线性表的定义线性表是具有相同特性的数据元素的一个有限序列。
该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。
当n=0时，表示线性表是一个空表，即表中不包含任何元素。
2．线性表的表示设序列中第i（i表示逻辑序号）个元素为a i（1≤i≤n），则线性表的一般表示为：（a1，a2，…，a i，a i+1，…，a n）其中a1为第一个元素，又称做表头元素，a2为第二个元素，…，a n为最后一个元素，又称做表尾元素。
一个线性表可以用一个标识符来命名，如用L命名上面的线性表，则：L=（a1，a2，…，a i，a i+1，…，a n）线性表中的元素是与位置有关的，即第i个元素a i处在第i-1个元素a i-1的后面和第i+1个元素a i+1的前面。
这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构，用二元组表示为：L=（D，R），其中：对应的逻辑结构如图2-1所示。
图2-1 线性表的逻辑结构示意图3．线性表的抽象数据类型描述抽象数据类型线性表的定义如下：二、线性表的顺序存储结构1．顺序表（1）线性表的存储结构线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，如图2-2所示。
图2-2 线性表到顺序表的映射由于线性表中逻辑上相邻的两个元素在对应的顺序表中的存储位置也相邻，所以这种映射称为直接映射。
这样，线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素（1≤i≤n-1）的存储位置紧接在第i个元素的存储位置的后面。
假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（即字节数）为sizeof（ElemType），整个线性表所占用存储空间的大小为n×sizeof（ElemType），其中n表示线性表的长度。
在C／C++语言中，线性表的顺序存储结构是利用数组来实现的，数组的基本类型就是线性表中元素的类型，数组的大小要大于等于线性表的长度。
第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。
答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。
对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。
答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。
最后返回s3串。
对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。
（1）计算模式P的nextval函数值。
（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。
答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。
表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。
因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。
上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。
第6章数组和广义表一、选择题1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A．13B．33C．18D．40【答案】B【解析】对于对称矩阵,a i,j=a j,i。
为了节省存储空间，为多个相同的元素只分配一个存储空间。
对于对称矩阵，元素下表之间的对应关系为：当i>=j时，k=i(i-1)/2+j -1；当i< =j 时，k=j(j-1)/2+i-1。
其中k相当于地址空间的标号，i为行号，j为列号。
因为第一个元素存储地址为1，所以最后计算的k需要加1。
所以a85的存储位置为8*（8-1）/2+5=33。
2．设有数组A[i，j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。
A．BA+141B．BA+180C．BA+222D．BA+225【答案】B【解析】在计算中，可以考虑按照列存放时，A[5,8]在内存的位置，比较容易计算元素的首地址。
比如A[5，8]顺序存放时，它是第7*8+5=61个元素，由于首地址为BA，所以它的存储首地址为BA+（61-1）*3=180+BA。
3．数组通常具有的两种基本操作是（）。
A．查找和修改B．查找和索引C．索引和修改D．建立和删除【答案】A【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。
根据数组的性质，数组通常具有的两种基本运算是排序和查找。
4．将一个A[1．.100，1．.100]的三对角矩阵，按行优先存入一维数组B[1．.298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A．198B．195C．197【答案】B【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下：k=2i+j-2。
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。
（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。
数据元素是数据的基本单位。
有时候，一个数据元素可以由若干个数据项组成。
② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。
③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。
（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③ 施加在数据上的操作，即数据的运算。
（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。
一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第10章内排序10.1 复习笔记一、排序的基本概念1．定义排序，就是整理表中的元素，使之按关键字递增或递减的顺序排列，本章仅讨论递增排序的情况。
其确切定义如下：输入：n个元素，R0，R1，…，R n-1，相应的关键字分别为k0，k1，…，k n-1。
输出：R i0，R i1，…，R in-1，使得k i0≤k i1≤…≤k in-1。
因此，排序算法就是要确定0，1，…，n-1的一种排列i0，i1，…，i n-1，使表中的元素依此排列整理后按关键字有序。
2．排序的稳定性（1）稳定如果待排序的表中，存在多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。
（2）不稳定若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：排序算法的稳定性是针对所有输入实例而言的。
在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
3．内排序和外排序（1）内排序在排序过程中，若整个表都是放在内存中处理，排序时不涉及内、外存数据的交换，则称之为内排序。
内排序适用于元素个数不很多的小表。
（2）外排序若排序过程中要进行内、外存数据的交换，则称之为外排序。
外排序则适用于元素个数很多，不能一次将全部元素放入内存的大表。
内排序是外排序的基础。
（3）排序方法的其他分类①需要关键字比较的排序需要关键字比较的排序方法有插入排序、选择排序、交换排序和归并排序等。
②不需关键字比较的排序不需要关键字比较的排序方法有基数排序。
4．排序数据的组织在本章中，以顺序表作为排序数据的存储结构，假设关键字类型为整型。
待排序的顺序表中数据元素的类型定义如下：二、插入排序1．插入排序的思想及方法基本思想是：每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中的适当位置，直到全部元素插入完成为止。
主要有两种插入排序方法，即直接插入排序和希尔排序。
1章答案1.简述数据与数据元素的关系与区别。
解：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2.数据结构和数据类型有什么区别？解：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3.设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000 g（n）=25n3+5000n2 h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
解：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。
4.用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
解：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5.设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）解：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6.有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第5章递归1．有以下递归函数：分析调用fun（5）的输出结果。
答：调用递归函数fun（5）时，先递推直到递归出口，然后求值。
这里的递归出口语句是，递推时执行的语句是，求值时执行的语句是调用fun（5）的输出结果如下：2．已知A[n]为整数数组，编写一个递归算法求n个元素的平均值。
答：设avg（A，i）返回A[0．．i]这i+1个元素的平均值，则递归模型如下：对应的递归算法如下：求A[n]中n个元素平均值的调用方式为：avg（A，n-1）。
3．设计一个算法求整数n的位数。
答：设f（n）为整数n的位数，其递归模型如下：对应的递归算法如下：4．设有一个不带表头节点的单链表L，其节点类型如下：设计如下递归算法：（1）求以L为首节点指针的单链表的节点个数。
（2）正向显示以L为首节点指针的单链表的所有节点值。
（3）反向显示以L为首节点指针的单链表的所有节点值。
（4）删除以L为首节点指针的单链表中值为x的第一个节点。
（5）删除以L为首节点指针的单链表中值为x的所有节点。
（6）输出以L为首节点指针的单链表中最大节点值。
（7）输出以L为首节点指针的单链表中最小节点值。
答：根据单链表的基本知识，设计与各小题对应的递归算法如下：（1）（2）（3）（4）（5）（6）（7）上机实验题5实验题1 编写一个程序exp5-1.cpp，求解皇后问题：在n×n的方格棋盘上，放置n 个皇后，要求每个皇后不同行、不同列、不同左右对角线。
要求：（1）皇后的个数n由用户输入，其值不能超过20，输出所有的解。
（2）采用递归方法求解。
实验题2编写一个程序exp5-2.cpp，求解背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的总价值最大。
第9章查找一、选择题1．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。
A．（n-1）／2B．n／2C．（n+1）／2D．n【答案】C【解析】最快查找一次成功，最慢查找n次成功。
平均查找次数为（1+2+3+…+n）/n，那么ASL=(n+1)/2。
2．在一个有N个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（）。
A．O（1）B．O（N）C．O（N2）D．O（NlogN）【答案】B【解析】二分查找的时间复杂度为O(logn)。
在一个用N个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0（N）。
3．对线性表进行折半查找时，要求线性表必须（）。
A．以顺序方式存储B．以顺序方式存储，且数据元素有序C．以链接方式存储D．以链接方式存储，且数据元素有序【答案】B【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
4．下列二叉排序树中查找效率最高的是（）。
A．平衡二叉树B．二叉查找树C．没有左子树的二叉排序树D．没有右子树的二叉排序树【答案】A【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。
这就保证了二叉树的深度是log2n级别的。
二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。
B、C、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。
5．当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。
第12章文件12.1 复习笔记一、文件的基本概念1．文件概述（1）定义文件是性质相同的记录的集合。
（2）按关键字划分①单关键字文件若文件中的记录只有一个惟一标识记录的主关键字，则称之为单关键字文件；②多关键字文件若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称之为多关键字文件。
（3）按是否定长划分①定长文件若文件中各记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称作定长文件；②不定长文件若文件中各记录含有的信息长度不等，则称作不定长文件。
2．文件的逻辑结构及操作（1）文件的逻辑结构文件中各记录之间存在着逻辑关系，当一个文件的各个记录按照某种次序排列起来时，各记录之间就自然地形成了一种线性关系。
在这种次序下，文件中每个记录最多只有一个直接后继记录和一个直接前驱记录，而文件的第一个记录只有直接后继没有直接前驱，文件的最后一个记录只有直接前驱而没有直接后继。
此时，文件可看成是一种线性结构。
（2）文件操作①检索文件检索就是在文件中查找满足给定条件的记录，它既可以按记录的逻辑号（即记录存入文件时的顺序编号）查找，也可以按关键字查找。
②维护文件维护主要是指对文件进行记录的插入、删除及修改等更新操作。
此外，为提高文件的效率，还要进行再组织操作、文件被破坏后的恢复操作以及文件中数据的安全保护等。
3．文件的存储结构（1）概念文件的存储结构是指文件在外存上的组织方式。
采用不同的组织方式就得到不同的存储结构。
（2）基本的组织方式①顺序组织；②索引组织；③哈希组织；④链组织。
文件组织的各种方式往往是这四种基本方式的结合。
二、顺序文件1．定义顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序跟物理顺序一致的文件。
若顺序文件中的记录按其主关键字有序，则称此顺序文件为顺序有序文件；否则称为顺序无序文件。
2．优点顺序文件的主要优点是连续存取的速度较快，即若文件中第i个记录刚被存取过，而下一个要存取的是第i+1个记录，则这种存取将会很快完成。
第12章文件一、选择题1．哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。
A．哈希函数B．除余法中的质数C．冲突处理D．哈希函数和冲突处理【答案】D【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
2．下述文件中适合于磁带存储的是（）。
A．顺序文件B．索引文件C．哈希文件D．多关键字文件【答案】A【解析】磁带存储是一种顺序存储，顺序文件(sequential file)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。
因此顺序文件适合磁带存储。
二、判断题1．倒排文件是对次关键字建立索引。
（）【答案】√【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表)，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
2．倒排序文件的优点是维护简单。
（）【答案】×【解析】倒排文件的优点是检索记录较快。
特别是对某些询问，不用读取记录，就可得到解答。
3．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
（）【答案】×【解析】哈希文件是使用一个函数（算法）来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。
哈希表是根据关键码值而直接进行访问的数据结构。
4．文件系统采用索引结构是为了节省存储空间。
（）【答案】×【解析】是为了缩短查找的时间，牺牲了一部分存储空间。
5．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）【答案】×【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
6．对磁带机而言，ISAM是一种方便的文件组织方法。
第11章外排序一、选择题1．下列排序算法中，其中（）是稳定的。
A．堆排序，起泡排序B．快速排序，堆排序C．直接选择排序，归并排序D．归并排序，起泡排序【答案】D2．若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A．快速排序B．堆排序C．归并排序D．直接插入排序【答案】C【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。
不稳定排序有：快速排序、堆排序、shell排序。
时间复杂度平均为O（nlog2n）的有：归并排序、堆排序、shell排序、快速排序。
3．在下面的排序方法中，辅助空间为O（n）的是（）。
A．希尔排序B．堆排序C．选择排序D．归并排序【答案】D4．下列排序算法中，占用辅助空间最多的是（）。
A．归并排序B．快速排序C．希尔排序D．堆排序【答案】A【解析】归并排序的辅助空间为O（n），快速排序所占用的辅助空间为O（logn），堆排序所占用的辅助空间为O（1）。
5．将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A．NB．2N-1C．2ND．N-1【答案】A【解析】归并排序基本思想：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。
最简单的归并是直接将两个有序的子表合并成一个有序的表。
归并排序最好情况下的复杂度为O（n）。
6．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A．插入B．选择C．希尔D．二路归并【答案】A【解析】解此题需要熟知各种排序方法的基本思想。
插入排序的基本思想是：假设待排序的记录存放在数组R[0．．n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0．．i-1]和R[i．．n-1]，其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨称其为无序区。
将当前无序区的第1个记录R[i]插入到有序区R[0．．i-1]中适当的位置上。
第8章图8.1 复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。
采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。
抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。
（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。
②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。
③出度以顶点i为起点的出边的数目，称为该顶点的出度。
一个顶点的入度与出度的和为该顶点的度。
（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。
（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。
②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。
（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。
（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。
②路径长度路径长度是指一条路径上经过的边的数目。
（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。
第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。
（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。
数据元素是数据的基本单位。
有时候，一个数据元素可以由若干个数据项组成。
② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。
③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。
（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③ 施加在数据上的操作，即数据的运算。
（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。
一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。
r j表示集合R中的第j个关系，m为R中关系的个数，特别地，若m=0，则R是一个空集，表明集合D中的数据元素间不存在任何关系，彼此是独立的，这和数学中集合的概念是一致的。
R中的一个关系r是序偶的集合，对于r中的任一序偶<x，y>（x，y∈D），把x称作序偶的第一节点，把y称作序偶的第二节点，称序偶的第一节点为第二节点的前驱节点，称第二节点为第一节点的后继节点。
若某个节点没有前驱节点，则称该节点为开始节点；若某个节点没有后继节点，则称该节点为终端节点。
对于对称序偶，即<x，y>∈R，且<y，x>∈R（x，y∈D），可用圆括号代替尖括号，即（x，y）∈R。
数据结构还可以利用图形形象地表示出来，图形中的每个节点对应一个数据元素，两节点之间的连线对应关系中的一个序偶。
2.逻辑结构类型（1）集合集合是指数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
（2）线性结构线性结构是指该结构中的节点之间存在一对一的关系。
其特点是开始节点和终端节点都是惟一的，除了开始节点和终端节点以外，其余节点都有且仅有一个前驱，有且仅有一个后继。
线性表就是一种典型的线性结构。
（3）树形结构树形结构是指该结构中的节点之间存在一对多的关系。
其特点是每个节点最多只有一个前驱，但可以有多个后继，且终端节点可以有多个。
二叉树就是一种典型的树形结构。
（4）图形结构图形结构是指该结构中的节点之间存在多对多的关系。
其特点是每个节点的前驱和后继的个数都可以是任意的。
图形结构可能没有开始节点和终端节点，也可能有多个开始节点、终端节点。
树形结构和图形结构统称为非线性结构。
3.存储结构类型（1）顺序存储结构① 存储方式该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元里，节点之间的逻辑关系由存储单元的邻接关系来体现。
通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。
② 优点a.节省存储空间；b.可实现对节点的随机存取。
③ 缺点不便于修改，对节点进行插入、删除运算时，可能要移动一系列的节点。
（2）链式存储结构① 存储方式该结构不要求逻辑上相邻的节点在物理位置上也相邻，节点间的逻辑关系是由附加的指针字段表示的。
通常链式存储结构要借助于计算机程序设计语言的指针类型来描述。
② 优点便于修改，在进行插入、删除运算时，仅需修改相应节点的指针域，不必移动节点。
③ 缺点a.与顺序存储方法相比，链式存储方法的主要缺点是存储空间的利用率较低；b.由于逻辑上相邻的节点在存储空间中不一定相邻，所以不能对节点进行随机存取。
（3）索引存储结构① 存储方式该结构通常是在存储节点信息的同时，还建立附加的索引表。
索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中关键字惟一标识一个节点，地址是指向节点的指针。
② 优点a．这种带有索引表的存储结构可以大大提高数据查找的速度；b．可以对节点进行随机访问；c．仍保持较高的数据修改运算效率。
③ 缺点增加了索引表，降低了存储空间的利用率。
（4）散列（或哈希）存储结构① 存储方式该结构的基本思想是根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该节点的存储地址。
② 优点查找速度快。
③ 缺点哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。
哈希存储方法一般只适合要求对数据进行快速查找和插入的场合。
上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映像。
4.数据类型和数据结构（1）数据类型① C／C++语言的基本数据类型a．int型int型是整型，可以有三个限定词short、long和unsigned，分别对应短整数、长整数和无符号整数。
b．bool型bool型是逻辑型，其取值只能是false（假）和true（真）。
c．float型float型是单精度浮点型。
d．double型double型是双精度浮点型。
e．char型char型是字符型，用于存放单个字符。
② C／C++语言的指针类型存放地址的变量称作指针变量。
有关指针的两个操作是：a.定义了int i，则&i操作是取变量i的地址；b.定义了int*p（这里的p是指向一个整数的指针），则*p操作是取p指针所指的值，即取p所指地址的内容。
③ C／C++语言的数组类型数组是同一类型的一组有序数据元素的集合。
数组有一维数组和多维数组。
数组名标识一个数组，下标指示一个数组元素在该数组中的顺序位置。
数组下标的最小值称为下界，在C／C++中数组下界总为0。
数组下标的最大值称为上界，在C／C++中数组上界为数组大小减1。
④ C／C++语言中的结构体类型结构体由一组称作结构体成员的项组成，每个结构体成员都有自己的标识符。
⑤ C／C++语言中的共用体类型共用体是把不同的成员组织为一个整体，在存储器中共享一段存储单元，但不同的成员以不同的方式被解释。
⑥ C／C++语言中的自定义类型C／C++语言中允许使用typedef关键字来指定一个新的数据类型名。
⑦ 引用运算符C++语言中提供了一种引用运算符“&”，当建立引用时，程序用另一个已定义的变量或对象（目标）的名字初始化它，从那时起，引用就作为目标的别名使用，对引用的改动实际就是对目标的改动。
引用常用于函数形参中，采用引用型形参时，在函数调用时会将形参的改变回传给实参。
（2）抽象数据类型① 抽象数据类型定义抽象数据类型（ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算。
② 表示方法其基本格式如下：ADT抽象数据类型名{数据对象：数据对象的声明数据关系：数据关系的声明基本运算：基本运算的声明}ADT抽象数据类型名其中基本运算的声明格式为：a.基本运算名（参数表）：运算功能描述；b.基本运算有两种参数：赋值参数，只为运算提供输入值；引用参数，以&打头，除可提供输入值外，还将返回运算结果。
③ 特征抽象数据类型有两个重要特征：a.数据抽象：强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）；b.数据封装：是指将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）如C++中的类来实现。
二、算法及其描述，1.算法概述（1）定义数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运算（抽象运算）和具体存储结构上的运算（运算实现）。
算法是在具体存储结构上实现某个抽象运算。
算法是对特定问题的求解步骤的一种描述。
.（2）特点① 有穷性；② 确定性；③ 可行性；④ 有输入；⑤ 有输出。
程序可以无穷循环，不一定满足有穷性，但算法必须满足有穷性。
2.算法描述常用于描述算法的C／C++语言基本语句：（1）输入语句scanf（格式控制字符串，输入项表）；（2）输出语句printf（格式控制字符串，输出项表）；（3）赋值语句变量名=表达式；（4）条件语句if（条件）语句；或者if（条件）语句1 else语句2；（5）循环语句while（表达式）循环体语句；do循环体语句；while表达式；或者for（赋初值表达式1；条件表达式2；步长表达式3）循环体语句；（6）返回语句return（返回表达式）；（7）定义函数语句函数返回值类型函数名（类型名形参1，类型名形参2，…）函数返回值类型函数名（类型名形参1，类型名形参2，…）{说明部分；函数语句部分；}（8）调用函数语句函数名（实参1，实参2，…）；三、算法分析1.算法设计的目标（1）正确性；（2）可使用性；（3）可读性；（4）健壮性；（5）高效率与低存储量需求。
2.算法效率分析通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。
一般采用事前分析估算法来分析算法效率。
一个算法的执行时间可以由其中基本运算的执行次数来计量。
算法中基本运算执行次数T（n）是问题规模n的某个函数f（n），记作：T（n）=O（f（n））记号“O”读作“大O”（是Order的简写，意指数量级），它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同。
各种不同数量级对应的值存在着如下关系：O（1）<O（log2n）<O（n）<O（nlog2n）<O（n2）<O（n3）<O（2n）<O（n!）算法的时间复杂度（用f（n）表示）采用这种数量级的形式表示后，只需要分析算法中影响算法执行时间的主要部分即可，不必对每一步都进行详细的分析。
一般情况下，计算一个算法的基本运算次数是相当困难的，甚至是不可能的（因为一个算法的不同输入往往产生不同的运算次数，而一个算法的所有不同输入的数目可能十分庞大）。
