第7章
习题答案
一、单项选择题
在一个图中，所有顶点的度数之和等于图的边数的____倍。
答案：C.2
解析：在无向图中，每条边贡献两个度数（每个端点一个），因此度数之和是边数的两倍。
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__倍。
答案：B.1
解析：在有向图中，每条边对应一个入度和一个出度，因此入度之和等于出度之和，且都等于边数。
有8个结点的无向图最多有__条边。
答案：B.28
解析：无向完全图的边数为?n(n?1)/2?，代入?n=8得?8×7/2=28。
有8个结点的无向连通图最少有___条边。
答案：C.7
解析：无向连通图的最少边数为生成树的边数，即?n?1=8?1=7。
有8个结点的有向完全图有__条边。
答案：C.56
解析：有向完全图的边数为?n(n?1)，代入?n=8?得?8×7=56。
用邻接表表示图进行广度优先遍历时，通常是采用___来实现算法的。
答案：B.队列
解析：广度优先遍历（BFS）使用队列管理待访问顶点，确保按层次遍历。
用邻接表表示图进行深度优先遍历时，通常是采用____来实现算法的。
答案：A.栈
解析：深度优先遍历（DFS）通常使用栈（或递归调用栈）实现，以探索路径深度。
深度优先遍历类似于二叉树的
答案：A.先序遍历
解析：DFS的访问顺序（根-子节点）与二叉树的先序遍历（根-左-右）相似。
广度优先遍历类似于二叉树的
答案：D.层次遍历
解析：BFS按层次访问顶点，与二叉树的层次遍历一致。
任何一个无向连通图的最小生成树
答案：B.一棵或多棵
解析：最小生成树可能不唯一（例如，图中存在相同权重的边时可能有多个），但一定存在。
二、填空题
图有?邻接矩阵、邻接表?等存储结构，遍历图有?深度优先遍历、广度优先遍历?等方法。
有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的?出度。
如果n个顶点的图是一个环，则它有?n?棵生成树。(以任意一顶点为起点，得到n-1条边)
n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为?O(n2)。
n个顶点e条边的图，若采用邻接表存储，则空间复杂度为?O(n+e)。
设有一稀疏图G，则G采用?邻接表?存储较省空间。
设有一稠密图G，则G采用?邻接矩阵?存储较省空间。
图的逆邻接表存储结构只适用于?有向?图。
已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是?将邻接矩阵的第i行全部置为0。
图的深度优先遍历序列?不唯一。
第8章
习题答案
一、单项选择题
如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。
答案：C.分块查找
解析：分块查找结合了顺序查找和折半查找的优点，块内可无序（适应动态插入/删除），块间有序（支持较快查找）。
对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
答案：C.5
*解析：n=22时，折半查找树的最大高度为5（因?2422≤25），查找失败时至少需比较5次（最坏情况）。*
在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。
答案：D.RR
解析：A的右孩子平衡因子为1（右重），且插入发生在右子树的右子树，故需RR旋转。
已知一个有序表(13,18,24,35,47,50,62,83,90,115,134)，当二分查找值为90的元素时，查找成功的比较次数为()。
答案：B.2
*解析：第一次mid=5（值5090），第二次mid=8（值90），共2次比较。*
下面关于哈希查找的说法，不正确的是（）。
答案：A.采用链地址法处理冲突时，查找一个元素的时间是相同的
解析：查找时间取决于链表长度，不同关键字的哈希冲突链长度可能不同，查找时间不一定相同。
设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。
答案：D.9
*解析：H(49)=5（冲突），探测序列：*
(5+12)%14=6（冲突，有61）
(5?12)%14=4（冲突，有15）
(5+22)%14=9（空闲，成功放置）。
采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字()。
答案：A.不一定都是同义词
解析：线性探测可能引发“堆积”，探测路径上可能包含非同义词（不同哈希地址的关键字）。
由n个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，