1.数据结构复习(5)

1 选择选择 1 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等 的学科 A B A 操作对象 计算方法 逻辑存储 数据映象 A 结构 关系 运算 算法 2 数据结构被形式地定义为 K R 其中 K 是 的有限集合 R 是 K 上的 有限集合 B D A 算法 数据元素 数据操作 逻辑结构 A 操作 映象 存储 关系 3 在数据结构中 从逻辑上可以把数据结构分成 C A 动态结构和静态结构 紧凑结构和非紧凑结构 线性结构和非线性结构 内部结构和外部结构 4 线性表的顺序存储结构是一种 A 的存储结构 线性表的链式存储结构是一种 B 的存储 结构 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 5 算法分析的两个主要方面是 A A 空间复杂性和时间复杂性 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 6 计算机算法指的是 它必具备输入 输出和 等五个特性 C B A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 A 可行性 可移植性和可扩充性 B 可行性 确定性和有穷性 C 确定性 有穷性和稳定性 D 易读性 稳定性和安全性 7 线性表的逻辑顺序与存储顺序总是一致的 这种说法 B A 正确 B 不正确 8 线性表若采用链式存储结构时 要求内存中可用存储单元的地址 D A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续或不连续都可以 9 在以下的叙述中 正确的是 B A 线性表的线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性 表 C 栈的操作方式是先进先出 D 队列的操作方式和先进后出 10 每种数据结构都具备三个基本运算 插入 删除和查找 这种说法 A A 正确 B 不正确 11 一个向量第一个元素的存储地址是 100 每个元素的长度为 2 则第 5 个元素的地址是 B A 110 B 108 C 100 D 120 12 一个栈的入栈序列 a b c d e 则栈的不可能的输出序列是 C A edcba B decba C dceab D abcde 13 若已知一个栈的入栈序列是 1 2 3 n 其输出序列为 p1 p2 p3 pn 若 p1 n 则 pi 为 C A i B n i C n i 1 D 不确定 2 14 栈结构通常采用的两种存储结构是 A A 顺序存储结构和链式存储结构 B 散列方式和索引方式 C 链表存储结构和数组 D 线性存储结构和非线性存储结构 15 判定一个栈 ST 最多元素为 m0 为空的条件是 B A ST top 0 B ST top 0 C ST top m0 D ST top m0 16 判定一个栈 ST 最多元素为 m0 为栈满的条件是 D A ST top 0 B ST top 0 C ST top m0 D ST top m0 17 栈的特点是 B 队列的特点是 A A 先进先出 B 先进后出 18 一个队列的入列序列是 1 2 3 4 则队列的输出序列是 B A 4 3 2 1 B 1 2 3 4 C 1 4 3 2 D 3 2 4 1 19 判定一个循环队列 QU 最多元素为 m0 为空的条件是 A A QU front QU rear B QU front QU rear C QU front QU rear 1 m0 D QU front QU rear 1 m0 20 判定一个循环队列 QU 最多元素为 m0 为满队列的条件是 C A QU front QU rear B QU front QU rear C QU front QU rear 1 m0 D QU front QU rear 1 m0 21 循环队列用数组 A 0 m 1 存放其元素值 已知其头尾指针分别是 front 和 rear 则当前队 列中的元素个数是 A A rear front m m B rear front 1 C rear front 1 D rear front 22 栈和队列的共同点是 C A 都是先进后出 B 都是先进先出 C 只允许在端点处插入和删除元素 D 没有共同点 23 不带头结点的单链表 head 为空的判定条件是 A A head NULL B head next NULL C head next head D head NULL 24 带头结点的单链表 head 为空的判定条件是 B A head NULL B head next NULL C head next head D head NULL 25 非空的循环单链表 head 的尾结点 由 p 所指向 满足 C A p next NULL B p NULL 3 C p next head D p head 26 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是 D 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 27 在一个单链表中 已知 q 所指结点是 p 所指结点的前驱结点 若在 q 和 p 之间插入 s 结点 则执行 C A s next p next p next s B p next s next s next p C q next s s next p D p next s s next q 28 在一个单链表中 若 p 所指结点不是最后结点 在 p 之后插入 s 所指结点 则执行 B A s next p p next s B s next p next p next s C s next p next p s D p next s s next p 29 在一个单链表中 若删除 p 所指结点的后续结点 则执行 A 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 30 从一个具有 n 个结点的单链表中查找其值等于 x 结点时 在查找成功的情况下 需平均比 较 个结点 A n B n 2 C n 1 2 D n 1 2 31 在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B A O 1 B O n C O n2 D O nlog2n 11 11 若线性表最常用的操作是存取第 i 个元素及其前趋的值 则采用 D 存储方式最节 省时间 A 单链表B 双链表C 单循环链表 D 顺序表 32 向一个栈顶指针为 HS 的链栈 不带空的头结点 中插入一个 s 所指结点时 执行 C 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 33 从一个栈顶指针为 HS 的链栈中删除一个结点时 用 x 保存被删结点的值 则执行 不带空的头结点 D A x HS HS HS next B x HS data C HS HS next x HS data D x HS data HS HS next 4 34 空串与空格串是相同的 这种说法 B A 正确 B 不正确 35 串是一种特殊的线性表 其特殊性体现在 D A 可以顺序存储 B 数据元素是一个字符 C 可以链接存储 D 数据元素可以是多个字符 36 设有两个串 p 和 q 求 q 在 p 中首次出现的位置的运算称作 B A 连接 B 模式匹配 C 求子串 D 求串长 37 设串 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 的结果串是 D A BCDEF B BCDEFG C BCPQRST D BCDEFEF 38 常对数组进行的两种基本操作是 C A 建立与删除 B 索引和修改 C 查找和修改 D 查找与索引 39 二维数组 M 的成员是 6 个字符 每个字符占一个存储单元 即一个字节 组成的串 行 下标 i 的范围从 0 到 8 列下标 j 的范围从 1 到 10 则存放 M 至少需要 D 个字节 M 的第 8 列和第 5 行共占 B 个字节 A 90 B 180 C 240 D 540 A 108 B 114 C 54 D 60 40 数组 A 中 A 的每个元素长度为 3 个字节 行下标 i 从 1 到 8 列下标 j 从 1 到 10 从首 地址 SA 开始连续存放在存储器内 存放该数组至少需要的单元数是 C A 80 B 100 C 240 D 270 41 数组 A 中 每个元素 A 的长度为 3 个字节 行下标 i 从 1 到 8 列下标 j 从 1 到 10 从首 地址 SA 开始连续存放在存储器内 该数组按行存放时 元素 A 8 5 的起始地址为 C A SA 141 B SA 144 C SA 222 D SA 225 42 数组 A 中 每个元素 A 的长度为 3 个字节 行下标 i 从 1 到 8 列下标 j 从 1 到 10 从首 地址 SA 开始连续存放在存储器内 该数组按列存放时 元素 A 5 8 的起始地址为 B A SA 141 B SA 180 C SA 222 D SA 225 43 1 二叉树的前序遍历序列中 任意一个结点均处在其子女结点的前面 这种说法 A A 正确 B 错误 44 由于二叉树中每个结点的度最大为 2 所以二叉树是一种特殊的树 这种说法 B A 正确 B 错误 45 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点 则此类二叉树中所包含的结点数至少 为 参考 2 h 1 1 A 2 h B 2 h 1 C 2 h 1 D h 1 46 已知某二叉树的后序遍历序列是 dabec 中序遍历序列是 debac 它的前序遍历序列是 D A acbed B decab C deabc D cedba 47 设 a b 为一棵二叉树上的两个结点 在中序遍历时 a 在 b 前的条件是 B A a 在 b 的右方B a 在 b 的左方 C a 是 b 的祖先D a 是 b 的子孙 5 48 假定在一棵二叉树中 双分支结点数为 15 单分支结点数为 30 个 则叶子结点数为 B 个 A 15B 16C 17D 47 49 某二叉树的前序遍历结点访问顺序是 abdgcefh 中序遍历的结点访问顺序是 dgbaechf 则 其后序遍历的结点访问顺序是 A A bdgcefha B gdbecfha C bdgaechf D gdbehfca 50 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值 小于其右孩 子的值 这种说法 B A 正确 B 错误 51 按照二叉树的定义 具有 3 个结点的二叉树有 C 种 A 3 B 4 C 5 D 6 52 树的基本遍历策略可分为先根遍历和后根遍历 二叉树的基本遍历策略可分为先序遍历 中序遍历和后序遍历 这里 我们把由树转化得到的二叉树叫做这棵数对应的二叉树 结 论 A 是正确的 A 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D 以上都不对 53 在一非空二叉树的中序遍历序列中 根结点的右边 A A 只有右子树上的所有结点 B 只有右子树上的部分结点 C 只有左子树上的部分结点 D 只有左子树上的所有结点 54 树最适合用来表示 C A 有序数据元素 B 无序数据元素 C 元素之间具有分支层次关系的数据 D 元素之间无联系的数据 55 任何一棵二叉树的叶结点在先序 中序和后序遍历序列中的相对次序 A A 不发生改变 B 发生改变 C 不能确定 D 以上都不对 56 对一个满二叉树 m 个树叶 n 个结点 深度为 h 则 无答案 A n h m B h m 2n C m h 1 D n 2 h 1 57 如果某二叉树的前序为 stuwv 中序为 uwtvs 那么该二叉树的后序为 C A uwvts B vwuts C wuvts D wutsv 58 设 n m 为一棵二叉树上的两个结点 在中序遍历时 n 在 m 前的条件是 C A n 在 m 右方 B n 是 m 祖先 C n 在 m 左方 D n 是 m 子孙 59 深度为 5 的二叉树至多有 C 个结点 A 16 B 32 C 31 D 10 60 在一个图中 所有顶点的度数之和等于所有边数的 C 倍 A 1 2 B 1 C 2 D 4 61 在一个有向图中 所有顶点的入度之和等于所有顶点的出度之和的 B 倍 A 1 2 B 1 C 2 D 4 62 带权有向图 G 用邻接矩阵 A 存储 则顶点 i 的入度等于 A 中 A 第 i 行非 的元素之和B 第 i 行非 且非 0 的元素个数 C 第 i 列非 的元素之和D 第 i 列非 且非 0 的元素个数 63 一个有 n 个顶点的无向图最多有 C 条边 A n B n n 1 C n n 1 2 D 2n 64 具有 4 个顶点的无向完全图有 A 条边 A 6 B 12 C 16 D 20 65 具有 6 个顶点的无向图至少应有 A 条边才能确保是一个连通图 A 5 B 6 C 7 D 8 6 66 在一个具有 n 个顶点的无向图中 要连通全部顶点至少需要 C 条边 A n B n 1 C n 1 D n 2 67 对于一个具有 n 个顶点的无向图 若采用邻接矩阵表示 则该矩阵的大小是 n n A n B n 1 2 C n 1 D n 2 68 对于一个具有 n 个顶点和 e 条边的无向图 若采用邻接表表示 则表头向量的大小为 A 所有邻接表中的接点总数是 C A n B n 1 C n 1 D n e A e 2 B e C 2e D n e 69 已知一个图如图 9 5 所示 若从顶点 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 b 70 根据有向图的深度优先遍历算法 从顶点 v1 出发 所得到的顶点序列是 A v1 v2 v3 v5 v4 B v1 v2 v3 v4 v5 C v1 v3 v4 v5 v2 D v1 v4 v3 v5 v2 根据有向图的宽度优先遍历算法 从顶点 v1 出发 所得到的顶点序列是 A v1 v2 v3 v4 v5 B v1 v3 v2 v4 v5 C v1 v2 v3 v5 v4 D v1 v4 v3 v5 v2 71 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 72 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 D A 先序遍历 B 中序遍历 C 后序遍历 D 按层遍历 73 判定一个有向图是否存在回路除了可以利用拓扑排序方法外 还可以利用 B A 求关键路径的方法 B 求最短路径的 Dijkstra 方法 C 宽度优先遍历算法 D 深度优先遍历算法 74 顺序查找法适合于存储结构为 B 的线性表 A 散列存储 B 顺序存储或链接存储 C 压缩存储 D 索引存储 75 对线性表进行二分查找时 要求线性表必须 C A 以顺序方式存储 B 以链接方式存储 C 以顺序方式存储 且结点按关键字有序排序 D 以链接方式存储 且结点按关键字有序排序 76 采用顺序查找方法查找长度为 n 的线性表时 每个元素的平均查找长度为 C A n B n 2 C n 1 2 D n 1 2 77 有一个有序表为 1 3 9 12 32 41 45 62 75 77 82 95 100 当二分查找值 82 为的结点时 C 次比较后查找成功 A 1 B 2 C 4 D 8 78 设哈希表长 m 14 哈希函数 H key key 11 表中已有 4 个结点 addr 15 4 addr 38 5 addr 61 6 addr 84 7 如用二次探测再散列处理冲突 关键字为 49 的结点的地址是 A A 8 B 3 C 5 D 9 填填 空空 题题 7 1 数据逻辑结构包括线性表 树和图线性表 树和图三种类型 树形结构和图形结构合称为非线性结构非线性结构 2 数据有四种基本的存储结构 它们是 顺序存储顺序存储 链式存储链式存储 索引存储 散列存储 3 若一个算法中的语句频度之和为 T n 3720n 4nlogn 则算法的时间复杂度为 O nlogn O nlogn 4 在线性结构中 第一个结点 无无 前驱结点 其余每个结点有且只有 一一 个前驱结点 最后 一个结点 无无 后续结点 其余每个结点有且只有 一一 个后续结点 5 在树形结构中 树根结点没有 前驱前驱 结点 其余每个结点有且只有 一一 个前驱结点 叶子 结点没有 前驱前驱 结点 其余每个结点的后续结点可以 最多有两个最多有两个 6 在图形结构中 每个结点的前驱结点数和后续结点数可以 任意多个任意多个 7 线性结构中元素之间存在 一对一一对一 关系 树形结构中元素之间存在 一对多一对多 关系 图形结 构中元素之间存在 多对多多对多 关系 8 算法的五个重要特性是 输入 输出 可行性 确定性和有穷性输入 输出 可行性 确定性和有穷性 9 下面程序段的时间复杂度是 O n m for i 0 i n i for j 0 j m j A i j 0 10 下面程序段的时间复杂度是 O N 2 s 0 for i 0 i n i for j 0 j n j s B i j sum s 11 下面程序段的时间复杂度是 O log3n i 1 while inext NULL 30 在一个单链表中 p 所指结点之后插入一个 s 所指结点时 应执行 s next p next 和 p next s 的操作 31 对于一个具有 n 个结点的单链表 在已知 p 所指结点后插入一个新结点的时间复杂度是 O 1 在给定值为 x 的结点后插入一个新结点的时间复杂度是 O n 32 已知二维数组 A m n 采用行序为主方式存储 每个元素占 k 个存储单元 并且第一个元 素的存储地址是 LOC A 0 0 则 A i j 的地址是 LOC A 0 0 i n j K 33 二维数组 A 10 20 采用列序为主方式存储 每个元素占一个存储单元并且 A 0 0 的存储 地址是 200 则 A 6 12 的地址是 200 12 10 6 326 34 二维数组 A 10 20 5 10 采用行序为主方式存储 每个元素占 4 个存储单元 并且 A 10 5 的存储地址是 1000 则 A 18 9 的地址是 1000 35 深度为 k 的完全二叉树至少有 2 k 1 个结点 至多有 2 k 1 个结点 若按自上而 下 从左到右次序给结点编号 从 1 开始 则编号最小的叶子结点的编号是 1 36 在一棵二叉树中 度为零的结点的个数为 n0 度为 2 的结点的个数为 n2 则有 n0 n2 1 37 一棵二叉树的第 i i 1 层最多有 2 i 1 个结点 一棵有 n n 0 个结点的满二叉 树共有 n 1 2 个叶子和 n 1 2 个非终端结点 38 设一棵二叉树的中序 后序遍历序列分别为 BDCEAFHG 和 DECBHGFA 则其先序遍历 序列为 A B C D E F G H 39 由如图 略 注 可在本复习资料后面任找一个二叉树 所示的二叉树 回答以下问题 其中序遍历序列为 其前序遍历序列为 其后序遍历序列为 40 以数据集 4 5 6 7 10 12 18 为结点权值所构造的 Huffman 树为 其带权路 径长度为 41 n 个顶点的连通图至少 n 1 条边 42 在无权图 G 的邻接矩阵 A 中 若 vi vj 或 vi vj 属于图 G 的边集合 则对应元素 A i j 等于 1 否则等于 0 9 43 在无向图 G 的邻接矩阵 A 中 若 A i j 等于 1 则 A j i 等于 1 44 已知一个有向图的邻接矩阵表示 计算第 i 个结点的入度的方法是 求第求第 i 列之和列之和 45 已知一个图的邻接矩阵表示 删除所有从第 i 个结点出发的边的方法是 第第 i 行全置行全置 0 46 已知如图所示的有向图 注 可在本复习资料后面任找一个图 请给出该图的 1 每个顶点的入 出度 2 邻接距阵 3 邻接表 4 逆邻接表 5 强连通分量 47 在各种查找方法中 平均查找长度与结点个数 n 无关的查找方法是 哈希表法哈希表法 48 二分查找的存储结构仅限于 顺序存储顺序存储 且是 有序的有序的 49 在散列函数 H key key p 中 p 应取 不大于表长且最接近表长的素数不大于表长且最接近表长的素数 50 假设在有序线性表 A 1 20 上进行二分查找 则比较一次查找成功的结点数为 1 则 比较二次查找成功的结点数为 2 则比较三次查找成功的结点数为 4 则比较四次 查找成功的结点数为 8 则比较五次查找成功的结点数为 16 平均查找长度为 10 5 51 对于长度为 n 的线性表 若进行顺序查找 则时间复杂度为 n 1 2 综综 合合 题 题 1 例例 2 1 已知集合 已知集合 A 和和 B 利用线性表的基础操作求这两个集合的并集 利用线性表的基础操作求这两个集合的并集 使使 A A B 且 且 B 不再单独存在 不再单独存在 void union List 求线性表的长度求线性表的长度 while ListEmpty Lb Lb 的元素未处理完的元素未处理完 ListDelete Lb 1 e 从从 Lb 删除第删除第 1 个元素赋给个元素赋给 e if LocateElem La e ListInsert La La len e La 中不存在和中不存在和 e 相同的数据元素相同的数据元素 则插入之则插入之 while DestroyList Lb 销毁线性表销毁线性表 Lb union 2 试用单链表作为存储结构 实现将线性表 试用单链表作为存储结构 实现将线性表 a0 a1 a2 an 1 就地逆置的操作 所谓 就地逆置的操作 所谓 就就 地地 指辅助空间为指辅助空间为 O 1 void InvertLinkedList LinkList p L L NULL 设逆置后的链表的初态为空表设逆置后的链表的初态为空表 while p p 为待逆置链表的头指针为待逆置链表的头指针 s p p p next 从从 p 所指链表中删除第一个结点所指链表中删除第一个结点 s 结点结点 s next L L s 将将 s 结点插入到逆置表的表头结点插入到逆置表的表头 3 试用顺序存储结构 实现将线性表 试用顺序存储结构 实现将线性表 a0 a1 an 1 就地逆置的操作 所谓 就地逆置的操作 所谓 就地就地 指辅指辅 助空间为助空间为 O 1 void Reverse SqList i j i j A elem i A elem j 交换交换 reverse 4 教材教材 P42 2 3 2 4 题题 答案略答案略 5 关键字序列关键字序列 T 53 27 36 15 69 42 请写出直接插入排序的中间过程序列 请写出直接插入排序的中间过程序列 待排元素序列 待排元素序列 53 27 36 15 69 42 第第 1 趟排序 趟排序 27 53 36 15 69 42 第第 2 次排序 次排序 27 36 53 15 69 42 第第 3 次排序 次排序 15 27 36 53 69 42 第第 4 次排序 次排序 15 27 36 53 69 42 第五次排序 第五次排序 15 27 36 42 53 69 6 关键字序列关键字序列 T 21 25 49 25 16 08 请写出冒泡排序的具体实现过程及算法 请写出冒泡排序的具体实现过程及算法 初态 初态 21 25 49 25 16 08 第第 1 趟冒泡结果趟冒泡结果 21 25 25 16 08 49 第第 2 趟冒泡结果趟冒泡结果 21 25 16 08 25 49 第第 3 趟冒泡结果趟冒泡结果 21 16 08 25 25 49 第第 4 趟冒泡结果趟冒泡结果 16 08 21 25 25 49 第第 5 趟冒泡结果趟冒泡结果 08 16 21 25 25 49 Void bubbleSort SqList While i 1 LastExchangeIndex 1 for j 1 j i j if L r j 1 key 0 T w k 背包剩余体积减少背包剩余体积减少 wk 11 k 继续考察下一件物品继续考察下一件物品 if T 0 StackTraverse S 输出一组解 之后回溯寻找下一组解输出一组解 之后回溯寻找下一组解 Pop S k T w k 退出栈顶物品 背包剩余体积增添退出栈顶物品 背包剩余体积增添 wk k 继续考察下一件物品继续考察下一件物品 while StackEmpty S k n knapsack 10 教材教材 P87 4 2 题题 答案略答案略 11 编写递归算法 计算二叉树中叶子结点的数目 编写递归算法 计算二叉树中叶子结点的数目 如何求深度类似 如何求深度类似 Void countLeaf BiTree T int countLeaf T lchild c countLeaf T rchild c 12 编写递归算法 将二叉树中所有结点的左右子树相互交换 编写递归算法 将二叉树中所有结点的左右子树相互交换 Void exchange BiTree t T lchhild T lchild T rchild T rchild t exchange T lchild exchange T rchild 13 假设用于通信的电文仅由假设用于通信的电文仅由 8 个字母个字母 a b c d e f g h 构成 它们在电文中出现的构成 它们在电文中出现的 概率分别为概率分别为 0 07 0 19 0 02 0 06 0 32 0 03 0 21 0 10 试为这 试为这 8 个字母设计哈夫曼编码 个字母设计哈夫曼编码 如果用如果用 0 7 的二进制编码方案又如何 的二进制编码方案又如何 14 画出下面二叉树的顺序存储结构图 画出下面二叉树的顺序存储结构图 12 15 画出下面二叉树的二叉链表存储结构图 画出下面二叉树的二叉链表存储结构图 16 画出下面树的双亲表示法存储结构图 画出下面树的双亲表示法存储结构图 17 画出下面树的孩子表示法存储结构图 画出下面树的孩子表示法存储结构图 18 画出下面树的孩子兄弟表示法存储结构图 树转为二叉树 画出下面树的孩子兄弟表示法存储结构图 树转为二叉树 19 画出下面图的邻接矩阵表示法存储结构图 另 有向图呢 带权图呢 画出下面图的邻接矩阵表示法存储结构图 另 有向图呢 带权图呢 13 20 画出下面图的邻接表存储表示法 画出下面图的邻接表存储表示法 链式存储链式存储 21 分别用克鲁斯卡尔算法和分别用克鲁斯卡尔算法和 Prim 普里姆 算法构造最小生成树 画出过程 普里姆 算法构造最小生成树 画出过程 注 参考注 参考 答案中中间过程已略去 答案中中间过程已略去 22 根据下面代码画出逻辑结构图和物理结构图 根据下面代码画出逻辑结构图和物理结构图 typedef struct ArcNode int adjvex struct ArcNode nextarc ArcNode typedef struct VNode char c ArcNode firstarc VNode AdjList 7 typedef struct AdjList vertices int vexnum arcnum ALGraph ALGraph G G arcnum 6 G vexnum 6 G vertices 1 c A G vertices 2 c B G vertices 3 c C G vertices 4 c D G vertices 5 c E G vertices 6 c F ArcNode a1 a2 a3 a4 a5 a6 G vertices 1 firstarc a1 adjvex 2 a1 nextarc a2 adjvex 3 a2 nextarc a3 adjvex 4 a3 nextarc NULL G vertices 2 firstarc a4 adjvex 5 a4 nextarc NULL G vertices 3 firstarc a5 adjvex 5 a5 nextarc NULL 14 G vertices 4 firstarc NULL G ve