试卷格式

复 旦 大 学 计 算 机 科 学 技 术 学 院 数 据 结 构 期 末 考 试 试 卷 ( 参 考 答 案 与 评 分 标 准 ) A 卷 共 8 页 课 程 代 码 :COMP130004.01-03 考 试 形 式 : 开 卷 闭 卷 2012 年 1 月 ( 本 试 卷 答 卷 时 间 为 120 分 钟, 答 案 必 须 写 在 试 卷 上, 做 在 草 稿 纸 上 无 效 ) 专 业 学 号 姓 名 成 绩 题 号 一 二 三 四 总 分 得 分 ( 装 订 线 内 不 要 答 题 ) 一 填 空 题 (25%,1~8 题 每 题 2 分 ) 1 设 W 为 一 个 二 维 数 组, 其 每 个 数 据 元 素 占 用 4 个 字 节, 行 下 标 i 从 0 到 7, 列 下 标 j 从 0 到 3, 则 二 维 数 组 W 的 数 据 元 素 共 占 用 个 字 节 若 按 行 顺 序 存 放 二 维 数 组 W, 其 起 始 地 址 为 100(10 进 制 ), 则 二 维 数 组 元 素 W[6,3] 的 起 始 地 址 为 (10 进 制 表 示 ) 128, 208 2 后 缀 算 式 9 2 3 + - 10 2 / - 的 值 为 中 缀 算 式 (3+4X)-2Y/3 对 应 的 后 缀 算 式 为 -1, 3 4 X * + 2 Y * 3 / - 3 由 权 值 分 别 为 11,8,6,2,5 的 叶 子 结 点 生 成 一 棵 哈 夫 曼 树, 它 的 带 权 路 径 长 度 为 71 4 在 有 序 表 (12,24,36,48,60,72,84) 中 二 分 查 找 关 键 字 72 时 所 需 进 行 的 关 键 字 比 较 次 数 为 2 5 在 含 n 个 顶 点 和 e 条 边 的 无 向 图 ( 无 自 环 重 边 ) 的 邻 接 矩 阵 中, 零 元 素 的 个 数 为 n 2-2e 6 已 知 一 棵 完 全 二 叉 树 中 共 有 768 结 点, 则 该 树 中 共 有 个 叶 子 结 点 384 7 有 向 图 的 边 集 为 {(a, c), (a, e), (e, b), (e, d), (b, d), (d, c), (c, f), 该 图 的 一 个 拓 扑 排 序 为 : a e b d c f 8 当 输 入 序 列 局 部 有 序 或 元 素 个 数 较 小 时, 在 快 速 排 序 选 择 排 序 插 入 排 序 归 并 排 序 堆 第 1 页

排 序 中, 最 佳 的 排 序 方 法 是 插 入 排 序 9 假 设 两 个 队 列 共 享 一 个 循 环 向 量 空 间 ( 参 见 右 图 ), 其 类 型 Queue2 定 义 如 下 : typedef struct{ DateType data[maxsize]; int front[2],rear[2]; Queue2; 对 于 i=0 或 1,front[i] 和 rear[i] 分 别 为 第 i 个 队 列 的 头 指 针 和 尾 指 针 请 对 以 下 算 法 填 空, 实 现 第 i 个 队 列 的 入 队 操 作 int EnQueue (Queue2 *Q, int i, DateType x) {// 若 第 i 个 队 列 不 满, 则 元 素 x 入 队 列, 并 返 回 1; 否 则 返 回 0 if(i<0 i>1)return 0; if(q->rear[i] == Q->front[ ]) return0; Q->data[ ] = x; Q->rear[i] = [ ]; return1; (i+1)%2 ( 或 1-i); Q->rear[i]; (Q->rear[i]+1)%Maxsize; ( 每 空 1 分 ) 10 以 下 是 一 个 判 断 二 叉 树 是 否 平 衡 的 程 序, 对 于 平 衡 的 二 叉 树,depth 将 会 返 回 其 高 度 ( 对 于 非 平 衡 二 叉 树 不 要 求 返 回 ) 请 在 空 白 处 填 上 代 码 完 成 程 序 (6 分 ) bool isbalanced( BiTreeNode * proot, int& depth) { if(proot == NULL){ ; return ; int leftdepth, rightdepth; if( ) { int dif = leftdepth rightdepth; if( ) { depth = (1+leftDepth) > (1+ rightdepth)? 1+leftDepth : 1+ rightdepth; return ; return false; 第 2 页

depth = 0(1 分 ) true(1 分 ) 分 ) isbalanced(proot->left, leftdepth) && isbalanced(proot->right, rightdepth) (2 dif >= -1 && dif <= 1(1 分 ) true(1 分 ) 二 选 择 题 (10%) 1 对 于 双 向 循 环 链 表, 每 个 结 点 有 两 个 指 针 域 next 和 prior, 分 别 指 向 前 驱 和 后 继 在 p 指 针 所 指 向 的 结 点 之 后 插 入 s 指 针 所 指 结 点 的 操 作 应 为 ( ) A. p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; B. p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; C. s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; ( 装 订 线 内 不 要 答 题 ) D. s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; D 2 一 个 栈 的 输 入 序 列 为 1 2 3, 则 下 列 序 列 中 不 可 能 是 栈 的 输 出 序 列 的 是 ( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 C 3 采 用 开 放 定 址 法 处 理 散 列 表 的 冲 突 时, 其 平 均 查 找 长 度 ( ) A. 低 于 链 接 法 处 理 冲 突 B. 高 于 链 接 法 处 理 冲 突 C. 与 链 接 法 处 理 冲 突 相 同 D. 高 于 二 分 查 找 B 4 假 设 一 个 有 n 个 顶 点 和 e 条 弧 的 有 向 图 用 邻 接 表 表 示, 则 删 除 与 某 个 顶 点 v i 相 关 的 所 有 弧 的 时 间 复 杂 度 是 ( ) A.O(n) B.O(e) C.O(n+e) D.O(n*e) C 5 设 有 6 个 结 点 的 无 向 图, 该 图 至 少 应 有 ( ) 条 边 才 能 确 保 是 一 个 连 通 图 A.5 B.6 C.7 D.8 A 三 问 答 题 (40%) 1 设 一 棵 m 叉 树 中 有 N1 个 度 数 为 1 的 结 点,N2 个 度 数 为 2 的 结 点,,Nm 个 度 数 为 m 的 结 点, 则 该 树 中 共 有 多 少 个 叶 子 结 点?( 请 写 出 求 解 过 程 )(5 分 ) 第 3 页

度 数 为 i 的 结 点 的 孩 子 个 数 为 i N 除 了 根 结 点, 其 他 结 点 都 是 某 结 点 的 孩 子, 且 父 亲 结 i 点 唯 一 因 此 该 树 共 有 total = m 1+ i Ni 个 结 点 i= 1 度 数 大 于 0 的 结 点 都 是 非 叶 子 结 点, 因 此 内 部 结 点 个 数 inner = m Ni i= 1 叶 子 结 点 个 数 leaf = total inner = m m 1 + ( i 1) N = 1 + ( i 1) N i i= 1 i= 2 评 分 标 准 : 总 分 5 分, 分 析 过 程 正 确 或 者 部 分 正 确 为 1-5 分, 否 则 为 0 分 i 2 一 个 线 性 表 为 B=(12,23,45,57,20,03,78,31,15,36), 设 散 列 表 为 HT[0..12], 散 列 函 数 为 H(key)= key % 13 并 用 线 性 探 查 法 解 决 冲 突, 请 画 出 散 列 表, 并 计 算 等 概 率 情 况 下 查 找 成 功 的 平 均 查 找 长 度 (5 分 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查 找 成 功 的 平 均 查 找 长 度 :ASL SUCC=14/10= 1.4 ( 散 列 表 4 分, 查 找 成 功 的 平 均 查 找 长 度 1 分 ) 3 已 知 二 叉 树 的 存 储 结 构 为 二 叉 链 表, 阅 读 下 面 算 法 typedef struct node { DateType data; Struct node * next; ListNode; typedef ListNode * LinkList; LinkList Leafhead = NULL; Void Inorder (BinTree T){ LinkList s; If(T){ Inorder(T->lchild); If ((!T->lchild)&&(!T->rchild)){ 第 4 页

s=(listnode*)malloc(sizeof(listnode)); s->data=t->data; s->next=leafhead; Leafhead=s; Inorder(T->rchild); 对 于 如 下 所 示 的 二 叉 树 (1) 画 出 执 行 上 述 算 法 后 所 建 立 的 结 构 ;(4 分 ) (2) 说 明 该 算 法 的 功 能 (2 分 ) ( 装 订 线 内 不 要 答 题 ) (1)Leafhead F H G D (2) 中 序 遍 历 二 叉 树, 按 遍 历 序 列 中 叶 子 结 点 数 据 域 的 值 构 建 一 个 以 Leafhead 为 头 指 针 的 逆 序 单 链 表 ( 或 按 二 叉 树 中 叶 子 结 点 数 据 自 右 至 左 链 接 成 一 个 链 表 ) 4 一 棵 二 叉 树 的 先 序 序 列 为 ABCDGEF, 中 序 序 列 为 CBDGAFE 请 画 出 该 二 叉 树 并 将 其 中 序 线 索 化, 后 将 二 叉 树 转 换 为 相 应 的 森 林 (5 分 ) ( 二 叉 树 :1 分 ): ( 中 序 线 索 :2 分 ): A B E NULL C D F NULL G ( 森 林 :2 分 ): 第 5 页

5 对 于 以 下 AVL 树, 依 次 插 入 关 键 码 35 28 5 请 画 出 每 插 入 一 个 关 键 码 之 后 AVL 树 的 形 状 (6 分 ) 80 50 110 20 60 90 120 10 40 70 100 30 插 入 35(2 分 ): 插 入 28(2 分 ): 80 80 50 110 50 110 20 60 90 120 30 60 90 120 10 35 70 100 20 35 70 100 30 40 10 28 40 插 入 5(2 分 ): 80 30 110 20 50 90 120 10 28 35 60 100 5 40 70 第 6 页

评 分 标 准 : 总 分 6 分, 每 次 插 入 后 的 形 状 2 分 6 已 知 一 个 连 通 图 如 下 图 所 示, 试 给 出 图 的 邻 接 矩 阵 和 邻 接 表 存 储 示 意 图, 若 从 顶 点 v1 出 发 对 该 图 进 行 遍 历, 分 别 给 出 一 个 按 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 顶 点 序 列. (8 分 ) (1) 图 的 邻 接 矩 阵 (1 分 ) (2) 邻 接 表 存 储 示 意 图 (1 分 ) (3) 从 v1 开 始 的 深 度 优 先 遍 历 的 顶 点 序 列 (2 分 ) (4) 分 析 在 深 度 遍 历 过 程 中, 分 别 使 用 邻 接 矩 阵 和 邻 接 表 存 储 的 算 法 复 杂 度 (2 分 ) (6) 讨 论 在 图 遍 历 问 题 中, 这 两 种 存 储 方 式 的 优 劣 ( 2 分 ) (1) 图 的 邻 接 矩 阵 (1 分 ) ( 装 订 线 内 不 要 答 题 ) 0 1 0 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 0 (2) 邻 接 表 存 储 示 意 图 (1 分 ) (3) 深 度 优 先 遍 历 的 顶 点 序 列 : v1,v2,v3, v5,v4, v6 (2 分 ) ( 有 多 个 答 案 ) (4) 深 度 优 先 邻 接 矩 阵 复 杂 度 :O(n 2 ),n 为 顶 点 数 ; 邻 接 表 复 杂 度 :O(n+e),n 为 顶 点 数, e 为 边 的 条 数 (2 分 ) (5) 在 图 的 遍 历 算 法 中, 遍 历 一 个 顶 点 的 邻 居, 对 于 邻 接 矩 阵, 时 间 复 杂 度 为 O(n), 而 邻 接 表 只 需 要 该 顶 点 的 邻 居 数 量 复 杂 度 ; 因 此 对 于 整 个 图 的 遍 历, 如 深 度 优 先 广 度 优 先 等, 邻 接 矩 阵 需 要 O(n 2 ), 而 邻 接 表 时 间 复 杂 度 为 O(n+e), 当 图 为 稀 疏 图 时, 邻 接 表 的 时 间 复 杂 度 优 于 邻 接 矩 阵, 而 且 存 储 开 销 也 优 于 邻 接 矩 阵 ; 当 图 为 密 集 图 时, 两 者 性 能 差 不 多 ; 总 的 来 说, 邻 接 表 的 时 间 复 杂 度 和 空 间 存 储 开 销 都 优 于 邻 接 矩 阵 (2 分 ) 7 分 析 对 比 AVL 树 和 Hash 的 时 空 特 性, 并 讨 论 它 们 的 适 合 场 合 (6 分 ) 第 7 页

时 空 特 性 : AVL 树 是 高 度 平 衡 的 二 叉 查 找 树, 查 找 时 间 复 杂 度 为 O(logn),Hash 的 查 找 时 间 复 杂 度 为 O(1) 存 储 开 销 Hash 往 往 比 AVL 树 小 适 合 场 合 : Hash 必 须 处 理 冲 突, 而 AVL 树 不 存 在 这 种 问 题 对 于 删 除 操 作,AVL 树 的 时 间 开 销 很 稳 定, 为 O(logn), 而 Hash, 如 果 采 用 拉 链 法 处 理 冲 突, 则 删 除 操 作 易 于 实 现, 如 果 采 用 开 放 定 址 法, 则 删 除 操 作 很 难 实 现, 因 此 开 放 定 址 法 的 Hash 不 适 合 更 新 频 繁 的 数 据 存 储 另 外,AVL 树 对 数 据 的 存 储 是 有 序 的, 而 Hash 对 数 据 的 存 储 并 不 能 反 映 数 据 之 间 的 大 小 关 系 因 此,AVL 树 适 用 于 有 序 的 数 据 存 储, 而 Hash 适 用 于 数 据 量 比 较 大 且 分 布 比 较 均 匀, 对 数 据 排 序 无 要 求 的 数 据 存 储 四 算 法 题 (25%, 第 一 题 要 求 写 代 码 ; 后 两 题 要 求 写 伪 代 码 或 步 骤 清 晰 的 解 题 思 路 ) 1 堆 是 一 种 很 常 用 的 数 据 结 构, 其 中 的 一 个 重 要 用 途 是 优 先 队 列 以 整 数 最 小 堆 为 例, 写 出 优 先 队 列 ( 最 小 优 先 ) 的 两 个 基 本 操 作 的 代 码 :(10 分 ) (1) 入 队, 即 插 入 一 个 元 素 到 存 放 堆 的 数 组 的 末 尾, 然 后 调 整 堆 (2) 出 队, 即 删 除 堆 顶 节 点, 然 后 调 整 堆 void insert( int k, int a[], int n ) {// 假 设 新 的 元 素 k 先 被 放 在 堆 末 尾 位 置 a[n] 单 元 中 n++; int j = n-1; int i = (j-1)/2; while(j > 0) { if(a[i] <= k) break; a[j] = a[i]; j = i; i = (i-1)/2; a[j] = k; int deletemin( int a[], int n ) {// 假 设 在 堆 顶 元 素 被 删 除 之 前, 堆 中 共 有 n 个 元 素 a[0] = a[n-1]; n--; int i = 0; int temp = a[i]; while((j = 2*i + 1) < n) { if( j<n-1 && a[j+1] < a[j]) j++; if(a[j] >= temp) break; a[i] = a[j]; i = j; 第 8 页

a[i] = temp; 2 堆 的 另 外 一 个 常 用 场 合 是 求 top k 问 题 假 设 我 们 已 经 有 一 个 n 个 元 素 的 最 小 堆, 如 果 用 最 直 观 的 方 法 求 最 小 的 k 个 元 素, 其 计 算 复 杂 度 为 O(klogn) 试 问 : 如 何 在 更 小 的 复 杂 度 内 求 top k 问 题? 用 伪 代 码 描 述 你 的 方 法, 并 给 出 复 杂 度 证 明 (7 分 ) 假 设 原 最 小 堆 为 H, 新 建 一 个 最 小 堆 H,H 初 始 化 为 空 将 最 小 堆 H 的 堆 顶 元 素 a 插 入 H ; 然 后 以 下 步 骤 执 行 k 次 : 将 H 的 堆 顶 元 素 a 删 除 并 输 出, 然 后 将 a 在 H 中 的 两 个 孩 子 插 入 H 中 为 了 快 速 找 到 a 在 H 中 的 两 个 孩 子,H 存 储 的 实 际 上 是 元 素 在 H 中 的 下 标, 而 大 小 比 较 通 过 下 标 读 取 H 中 对 应 的 元 素 ( 装 订 线 内 不 要 答 题 ) 由 于 k 次 对 H 的 删 除 操 作, 最 多 将 2 个 新 元 素 插 入 H 中, 因 此 H 的 大 小 不 超 过 2k 每 次 插 入 删 除 操 作 复 杂 度 都 为 O(log2k), 因 此 算 法 复 杂 度 为 O(klogk) 评 分 标 准 : 满 分 :O(klogk) 或 者 更 好 若 提 出 了 快 速 排 序 的 partition 函 数 (O(n) 复 杂 度 ), 给 4 分 3 给 定 一 个 无 向 图 G(V, E),V 为 顶 点 集 合,E 为 边 集 合 对 于 V 中 的 两 个 顶 点 u 和 v, 如 果 图 中 存 在 一 条 u 到 v 的 路 径, 则 称 u 和 v 彼 此 可 达 设 计 一 种 数 据 结 构, 将 图 G 进 行 预 处 理 得 到 该 数 据 结 构, 使 得 对 于 任 意 u 和 v, 通 过 该 数 据 结 构 可 以 在 常 数 时 间 得 到 u 和 v 是 否 彼 此 可 达 要 求 该 数 据 结 构 存 储 开 销 为 O( V ), 预 处 理 复 杂 度 为 O( V + E ) (8 分 ) 注 意 图 中 的 结 点 从 0 开 始 用 整 数 连 续 编 号 图 Graph 上 的 操 作 有 : 取 得 结 点 总 数 int GetVertexNum( ); 取 得 u 之 后 的 v 的 下 一 个 邻 接 顶 点 int GetNextNeighbor(int v,int u),u 为 -1 则 取 得 v 的 第 一 个 邻 接 顶 点, 返 回 -1 表 示 没 有 下 一 个 邻 接 顶 点 了 ; 可 以 直 接 使 用 数 组 链 表 栈 和 队 列 这 些 基 本 数 据 结 构 及 其 上 的 基 本 操 作, 但 要 注 释 每 个 所 使 用 操 作 的 含 义 (1) 描 述 所 设 计 的 数 据 结 构, 描 述 如 何 得 到 该 数 据 结 构, 并 写 出 预 处 理 的 代 码 (2) 描 述 如 何 通 过 该 数 据 结 构 在 常 数 时 间 内 得 到 u 和 v 是 否 可 达, 并 写 出 相 应 代 码 本 题 考 察 学 生 对 连 通 分 量 的 掌 握 和 运 用 使 用 BFS 算 法 得 到 图 的 N 个 连 通 分 量, 为 每 个 连 通 分 量 分 配 一 个 id 用 一 个 包 含 V 个 元 素 的 数 组 connectedcom[ V ], 记 录 每 个 顶 点 属 于 的 连 通 分 量 id, 即 connectedcom[u] 表 示 u 属 于 的 联 通 分 量 对 于 u 和 v, 若 connectedcom[u] = connectedcom[v], 则 u 和 v 彼 此 可 达 评 分 标 准 : 本 题 答 案 不 唯 一, 可 以 是 BFS DFS, 也 可 以 是 并 查 集 总 共 8 分 思 路 2 分 思 路 清 晰 正 确 为 2 分, 方 法 不 限 于 参 考 答 案 这 一 种, 思 路 不 完 全 正 第 9 页

确 最 多 为 1 分, 没 写 为 0 分 ; 算 法 1-6 分 第 10 页