习题一
? 1.1 数据结构按逻辑结构可分为两大类，分别是线性结构和非线性结构.
? 1.2 数据的逻辑结构可分为四种（或四种基本结构），分别是集合结构、线性结构、树状结构、图状结构.
? 1.3 线性结构反应结点间的逻辑关系是一对一的，非线性结构反应结点间的逻辑关系是一对多或多对多.
? 1.4 一个算法的效率可分为时间效率和空间效率.
? 1.5 在树形结构中，树根结点没有前驱结点，其余每个结点的有且仅有1个前驱结点；叶子结点没有后继结点；其余每个结点的后续可以有多个结点
? 1.6 在图形结构中，每个结点的前驱结点数和后续结点数可以有多个结点
? 1.7 线性结构中元素之前存在一对一关系；树形结构中元素之间存在一对多关系；图形结构中元素之间存在多对多关系.
? 1.8 下面程序段的时间复杂度是O ( n 2 ) \mathbf{O(n^2)}O(n2).
for(i =0;i < n;i++)
for(j = 0;j < n;j++)
A[i][j] = 0;
? 1.9 下面程序段的时间复杂度是O ( n 1 2 ) \mathbf{O(n^{\frac{1}{2}})}O(n21).
i = s = 0;
while(s<n){i++;s += i;}
? 1.10 下面程序段的时间复杂度是O ( n 2 ) \mathbf{O(n^2)}O(n2).
s = 0;
for(i = 0;i < n;i++)
for(j = 0;j < n;j++)
s += B[i][j];
? 1.11 下面程序段的时间复杂度是O ( l o g 3 n ) \mathbf{O(log_{3}n)}O(log3n).
for(s = i = 1;i<= n;i = i*3) s+= i;
? 1.12 算法时间复杂度的分析通常有两种方法，即事后统计和事前估计的方法，通常我们对算法求时间复杂度时，采用后一种方法.
? 1.13 一个算法的时间复杂度为 T ( n ) = 3 n 3 + n l o g 2 n + 2 n T(n)=3n^3+nlog_{2}n+2nT(n)=3n3+nlog2n+2n，其渐进时间复杂度为O ( n 3 ) \mathbf{O(n^3)}O(n3).
? 1.14 抽象数据类型包括数据及其关系 和操作.
? 1.15 抽象数据类型应该包括数据、关系、操作.
习题二
? 2.1 线性表是一种典型的线性结构.
? 2.2 顺序表中逻辑上相邻的元素的物理位置相邻.
? 2.3 要从一个顺序表删除一个元素时，被删除的元素之后的所有元素均需前移一个位置，移动过程是从前向后依次移动每一个元素.
? 2.4 在线性表的顺序存储中，元素之间的逻辑关系是通过物理存储位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过结点的指针域决定的.
? 2.5 在双向链表中，每个结点含有两个指针域，一个指向前驱结点，另一个指向后继结点.
? 2.6 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用顺序存储结构为宜. 相反，当经常进行的是插入和删除操作时，则采用链式存储结构为宜.
? 2.7 顺序表中逻辑上相邻的元素，物理位置一定相邻，单链表中逻辑上相邻的元素，物理位置不一定相邻.
? 2.8 根据线性表的链式存储结构中每一个结点所含指针的个数，链表可分为单链表和双向链表；而根据指针的链接方式，链表又可分为非循环链表和循环链表.
? 2.9 在单链表中设置头结点的作用是使空表和非空表统一、算法处理一致.
? 2.10 对于一个具有 n nn 个结点的单链表，在已知的结点 p pp 后插入一个新结点的时间复杂度为O ( 1 ) \mathbf{O(1)}O(1)，在给定值为 x xx 的结点前插入一个新结点的时间复杂度为O ( n ) \mathbf{O(n)}O(n).
? 2.11 若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空.
习题三
? 3.1 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶位置插入和删除元素；对于队列只能在队尾位置插入元素和在 队首 位置删除元素.
? 3.2 对于一个栈作进栈运算时，应先判别栈是否为栈满，作退栈运算时，应先判别栈是否为栈空，当栈中元素个数为 m mm 时，作进栈运算时发生上溢，则说明栈的可用最大容量为 m \mathbf{m}m. 为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样只有当两个栈的栈顶指针相等时才产生上溢.
? 3.3 设有一空栈，现有输入序列 1 , 2 , 3 , 4 , 5 1,2,3,4,51,2,3,4,5，经过 push,push,pop,push,pop,push,push 后，输出序列是2、3.
? 3.4 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为O ( 1 ) \mathbf{O(1)}O(1).
习题四
? 4.1 两个字符串相等的充要条件为两个串的长度相等和对应位置的字符相等.
? 4.2 串是指含 n 个字符的有限序列(n ≥ 0 n\geq 0n≥0).
? 4.3 空串是指不含任何字符的串，空串是指仅含空格字符的字符串.
? 4.4 一维数组的逻辑结构是线性结构，存储结构是顺序结构；对于二维或多维数组，分为以行序为主序和以列序为主序两种不同的存储方式.
? 4.5 对于一个二维数组 A[m][n]，若按行序为主序存储，则任一元素 A[i][j] 相当于 A[0][0] 的地址为i × n + j \mathbf{i\times n+j}i×n+j个元素位置.
? 4.6 一个广义表为 (a, (a, b), d, e, ((i, j), k))，则该广义表的长度为5，深度为3.
? 4.7 一个稀疏矩阵如下，则对应的三元组线性表为((0, 2, 2), (1, 0, 3), (2, 2, -1), (2, 3, 5)).
[ 0 0 2 0 3 0 0 0 0 0 − 1 5 ] \begin{bmatrix} 0 & 0 & 2 & 0 \\ 3 & 0 & 0 & 0 \\ 0 & 0 & -1 & 5 \\ \end{bmatrix}03000020−1005
? 4.8 一个 n × n n\times nn×n 的对称矩阵，如果以行为主序或以列为主序只存其下三角，则其容量为n(n+1)/2.
? 4.9 已知广义表 A = ((a, b, c), (d, e, f))，则运算 tail(head(tail(A))) =(e, f).
? 4.10 设有一个 10 阶的对称矩阵 A，采用压缩存储方式以行序为主序存储其下三角，a 00 a_{00}a00 为第一个元素，其存储地址为 0，每个元素占有 1 个存储地址空间，则 a 85 a_{85}a85 的地址为41.
? 4.11 已知广义表 Ls = (a, (b, c, d), e)，运用 head 和 tail 函数取出 Ls 中的原子 b 的运算是head(head(tail(Ls))).
习题五
? 5.1 假定一棵树的广义表表示为 A(B(E), C(F(H, I, J), G), D)，则该树的度为3，树的深度为4，终端结点的个数为6，单分支结点的个数为1，双分支结点的个数为1，三分支结点的个数为2，C 结点的双亲结点为A，其孩子结点为F和 结点G.
? 5.2 对于一个有 n 个结点的二叉树，当它为一棵理想平衡二叉树时具有最小高度：⌈ l o g 2 ( n + 1 ) ⌉ \lceil log_{2}(n+1)\rceil⌈log2(n+1)⌉，当它为一棵单支树具有最大高度：n.
? 5.3 由带权为 3，9，6，2，5 的 5 个叶子结点构成一棵哈夫曼树，则带权路径长度为55.
? 5.4 在一棵二叉排序树上按中序遍历得到的结点序列是一个有序序列.
? 5.5 对于一棵具有 n 个结点的二叉树，当进行二叉链表存储时，指针域的总数为2n个，其中 n-1 个用于链接孩子结点，n+1个空闲着
? 5.6 在一棵二叉树中，度为 0 的结点个数为 n 0 n_{0}n0，度为 2 的结点个数为 n 2 n_{2}n2，则 n 0 = n_{0}=n0=n 2 + 1 \mathbf{n_{2}+1}n2+1
? 5.7 一棵深度为 k 的满二叉树的结点总数为2 k − 1 \mathbf{2^k-1}2k−1，一棵深度为 k 的完全二叉树的结点总数的最小值为2 k − 1 \mathbf{2^k-1}2k−1，最大值为2 k − 1 \mathbf{2^k-1}2k−1.
? 5.8 由三个结点构成的二叉树，共有5种不同的形态.
? 5.9 设高度为 h 的二叉树中只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为2h-1.
? 5.10 一棵含有 n 个结点的 k 叉树，单支树形态达到最大深度，理想平衡 k 叉树形态达到最小深度。对于一棵具有 n 个结点的完全二叉树，若一个结点的编号为 i (1 ≤ i ≤ n)，则它的左孩子结点的编号为2i，右孩子结点的编号为2i+1，双亲结点的编号为⌊ i / 2 ⌋ \mathbf{\lfloor i/2\rfloor}⌊i/2⌋.
? 5.11 哈夫曼树是指带权路径长度最小的二叉树.
? 5.12 空树是指结点数为0.
? 5.13 二叉树的链式存储结构有二叉链表和三叉链表两种.
? 5.14 三叉链表比二叉链表多一个指向双亲的指针域.
? 5.15 线索是指指向结点前驱或结点后继信息的指针.
? 5.16 线索链表中的 rtag 域值为1时，表示该结点无右孩子，此时rightChild域为指向该结点后继线索的指针.
? 5.17 本节中我们学习的树的存储结构有广义表表示法、父指针表示法、子女链表表示法、子女-兄弟表示法.
习题六
? 6.1 在一个图中，所有顶点的度数之和等于所有边数的2 倍.
? 6.2 在一个具有 n 个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有 n 个顶点的有向完全图中，包含有n(n-1)条边.
? 6.3 假定一个有向图的顶点集合为 {a, b, c, d, e, f}，边集为 {<a,c>, <a,e>, <c,f>, <d,c>,<e,b>,<e,d>}，则出度为 0 的顶点个数为2，入度为 1 的顶点个数为4.
? 6.4 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要n-1条边.
? 6.5 表示图的三种存储结构为邻接矩阵、邻接表、临界多重表.
? 6.6 在一个连通图中存在着1个连通分量.
? 6.7 图中的一条路径长度为 k，该路径所含的顶点数为k+1.
? 6.8 若一个图的顶点集为{a, b, c, d, e, f}，边集为{(a, b), (a, c), (b, c), (d, e)}，则该图含有3个连通分量.
? 6.9 对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为n × n \mathbf{n\times n}n×n
? 6.10 对于具有 n 个顶点和 e 条边的无向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为n 和2e.
? 6.11 对于具有 n 个顶点和 e 条边的有向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为n和e.
? 6.12 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有出边和入边结点.
? 6.13 对于一个具有 n 个顶点和 e 条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为O ( n ) \mathbf{O(n)}O(n)和O ( e / n ) \mathbf{O(e/n)}O(e/n).
? 6.14 假定一个有向图具有 n 个顶点和 e 条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为O ( n 2 ) \mathbf{O(n^2)}O(n2)和O ( n + e ) \mathbf{O(n+e)}O(n+e).
? 6.15 图的深度优先搜索遍历算法是一种递归算法，图的广度优先搜索遍历算法需要使用队列
? 6.16 对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为n和n-1.
? 6.17 若一个连通图中每个边上的权值均不同，则得到的最小生成树是唯一（唯一/不唯一）的。根据图的逻辑结构进行某种次序的遍历，得到的顶点序列是不唯一（唯一/不唯一）的.
? 6.18 假定一个有向图的边集为{<a, c>, <a, e>, <c, f>, <d, c>, <e, b>, <e, d>}，对该图进行拓扑排序得到的顶点序列为aebdcf.
? 6.19 某无向图中顶点数和边数分别为 n 和 e，所有顶点的度数之和为 d，则 e =d/2.
? 6.20 某有向图中顶点数和边数分别为 n 和 e，所有顶点的入度数之和为 d，则 e =d.
习题七
? 7.1 以顺序查找方法从长度为 n nn 的顺序表或单链表中查找一个元素时，平均查找长度为(n+1)/2，时间复杂度为O ( n ) \mathbf{O(n)}O(n).
? 7.2 对长度为 n nn 的查找表进行查找时，假定查找第 i ii 个元素的概率为 p i p_{i}pi，查找长度（即在查找过程中依次同有关元素比较的总次数）为c 1 c_{1}c1，则在查找成功情况下的平均查找长度的计算公式为∑ p i c i \mathbf{\sum{p_{i}c_{i}}}∑pici
? 7.3 假定一个顺序表的长度为 40，并假定查找（带监视哨）每个元素的概率都相同，则在查找成功情况下的平均查找长度为20.5，在查找不成功情况下的平均查找长度41.
? 7.4 以折半查找方法从长度为 n nn 的有序表中查找一个元素时，平均查找长度约等于l o g 2 ( n + 1 ) \mathbf{log_{2}(n+1)}log2(n+1)，时间复杂度为O ( l o g 2 n ) \mathbf{O(log_{2}n)}O(log2n).
? 7.5 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成顺序存储的有序表.
? 7.6 从有序表 ( 12 , 18 , 30 , 43 , 56 , 78 , 82 ) (12,18,30,43,56,78,82)(12,18,30,43,56,78,82) 中分别折半查找 43 和 56 时，其比较次数为1和3.
? 7.7 假定对长度 n = 50 n=50n=50 的有序表进行折半查找，则对应的判定树高度为 6，最后一层结点数为19.
? 7.8 假定在索引查找中，查找表长度为 n，每个子表的长度相等，设为 s，则进行成功查找的平均查找长度为(n/s+s)/2+1.
? 7.9 在索引查找中，假定查找表（即主表）的长度为 96，被等分为 8 个子表，则进行索引查找的平均查找长度为11.
? 7.10 在一颗二叉排序树中，每个分支结点的左子树所有结点的值一定小于该结点的值，右子树上所有结点的值一定大于该结点的值.
? 7.11 对一颗二叉排序树进行中序遍历时，得到的结点序列是一个递增有序序列.
? 7.12 从一颗二叉排序树中查找一个元素时，若元素的值等于根节点的值，则表明查找成功，若元素的值小于根节点的值，则继续向左子树查找，若元素的值大于根节点的值，则继续向右子树查找.
? 7.13 向一颗二叉排序树中插入一个元素时，若元素的值小于根节点的值，则接着向根节点的左子树插入，若元素的值大于根节点的值，则接着向根节点的右子树插入.
? 7.14 根据 n nn 个元素建立一颗二叉排序树的时间复杂度大致为O ( n l o g 2 n ) \mathbf{O(nlog_{2}n)}O(nlog2n).
? 7.15 在一棵平衡二叉树中，每个结点的左子树高度与右子树高度之差的绝对值不超过1.
? 7.16 假定对线性表 (38, 25, 74, 52, 48) 进行哈希存储，采用 H(K) = K % 7 作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰5次存储冲突.
? 7.17 假定对线性表(38, 25, 74, 52, 48)进行哈希存储，采用 H(K) = K % 7 作为哈希函数，采用线性探测法处理冲突，则查找成功的平均长度为2，查找不成功的平均长度为22/7.
? 7.18 在线性表的哈希存储中，装填因子 α \alphaα 又称为装填系数，若用 m 表示哈希表的长度，n 表示线性表中的元素的个数，则 α \alphaα 等于n/m.
? 7.19 对线性表 (18, 25, 63, 50, 42, 32, 90) 进行哈希存储时，若选用 H(K) = K % 9 作为哈希函数，则哈希地址为 0 的元素有3个，为 5 的元素有2个
? 7.20 为了能有效地应用哈希查找技术，必须解决的两个问题是选择好的哈希函数 和拟定解决冲突的方案.
习题八
? 8.1 每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此排序方法叫做直接插入排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做选择排序.
? 8.2 每次直接或通过支点元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做快速排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序.
? 8.3 在简单选择排序中，记录比较次数的时间复杂度为O ( n 2 ) \mathbf{O(n^2)}O(n2)，记录移动次数的时间复杂度为O ( n ) \mathbf{O(n)}O(n).
? 8.4 对 n nn 个记录进行冒泡排序时，最少的比较次数为n − 1 n-1n−1，最少的趟数为1.
? 8.5 快速排序在平均情况下的时间复杂度为O ( n l o g 2 n ) O(nlog_{2}n)O(nlog2n)，在最坏情况下的时间复杂度为O ( n 2 ) O(n^2)O(n2).
? 8.6 若对一组记录 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80) 进行直接插入排序，当把第 8 个记录插入到前面已排序的有序表时，为寻找插入位置需比较4次.
? 8.7 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，则利用堆排序法建立的初始小根堆为(38, 40 56, 79, 46, 84).
? 8.8 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，在冒泡排序的过程中进行第一趟排序（从左往右比较）后的结果为(46, 56, 38, 40, 79, 84).
? 8.9 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，在冒泡排序的过程中进行第一趟排序（从右往左比较）时，元素 79 将最终下沉到其后第1个元素的位置（从 0 开始）
? 8.10 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，对其进行快速排序的过程中，共需要3或2趟排序
? 8.11 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，对其进行快速排序的第一次划分后，右区间内元素的个数为4，左区间元素的个数为3.
? 8.12 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为[40, 38] 46 [79, 56, 80]
? 8.13 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的子表个数为3个.
? 8.14 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，对其进行归并排序的过程中，第三趟归并后的第 2 个子表为[28, 46].
? 8.15 假定一组记录为 ( 46 , 79 , 56 , 38 , 40 , 80 ) (46,79,56,38,40,80)(46,79,56,38,40,80)，对其及逆行归并排序的过程中，共需要4趟完成.
? 8.16 在时间复杂度为 O ( n l o g 2 n ) O(nlog_{2}n)O(nlog2n) 的所有排序方法中，折半插入和归并排序方法是稳定的.
? 8.17 在时间复杂度为 O ( n 2 ) O(n^2)O(n2) 的所有排序方法中， 排序方法是最不稳定的直接选择.
? 8.18 在所有排序方法中，快速排序方法采用的是二分法的思想.
? 8.19 在所有排序方法中，堆排序方法使数据的组织采用的是完全二叉树的思想.
? 8.20归并排序在所有排序方法中， 方法采用的是两两有序表合并的思想.
? 8.21冒泡排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮.
? 8.22直接插入排序方法每次使无序表中的第一个记录插入到有序表中的合适位置.
? 8.23直接选择排序方法每次从无序表中顺序找出一个最小值，然后与无序表中的第一个元素交换.