大学数据结构期末考试试题.pdf

“数 据 结 构”期 末 考 试 试 题 一、单 选 题(每 小 题 2 分，共 12分)1.在 一 个 单 链 表 HL中，若 要 向 表 头 插 入 一 个 由 指 针 p 指 向 的 结 点，则 执 行()。A.HL=ps p-next=HLB.p 一 next=HL；HL=p3C.p-next=Hl；p=HL：D.p 一 next=HL一 next;HL-next=p；2.n 个 顶 点 的 强 连 通 图 中 至 少 含 有()A.n1条 有 向 边 B.n条 有 向 边 C.n(n1)/2 条 有 向 边 D.n(n 1)条 有 向 边 3.从 一 棵 二 叉 搜 索 树 中 查 找 一 个 元 素 时，其 时 间 复 杂 度 大 致 为()。A.O(l)B.O(n)C.O(lOgzn)D,O(n2)4.由 权 值 分 别 为 3,8,6,2,5 的 叶 子 结 点 生 成 一 棵 哈 夫 曼 树，它 的 带 权 路 径 长 度 为()。A.24 B.48C.72 D.535.当 一 个 作 为 实 际 传 递 的 对 象 占 用 的 存 储 空 间 较 大 并 可 能 需 要 修 改 时，应 最 好 把 它 说 明 为()参 数，以 节 省 参 数 值 的 传 输 时 间 和 存 储 参 数 的 空 间。A.整 形 B.引 用 型 C.指 针 型 D.常 值 引 用 型 6.向 一 个 长 度 为 n 的 顺 序 表 中 插 人 一 个 新 元 素 的 平 均 时 间 复 杂 度 为()。A.0(n)B.0(1)C.0(n2)D.0(10g2n)二、填 空 题(每 空 1分，共 28分)1.数 据 的 存 储 结 构 被 分 为-、-、-和-四 种。2.在 广 义 表 的 存 储 结 构 中，单 元 素 结 点 与 表 元 素 结 点 有 一 个 域 对 应 不 同，各 自 分 别 为 域 和 一 一 域。3.-中 缀 表 达 式 3十 x*(2.4/56)所 对 应 的 后 缀 表 达 式 为-4.在 一 棵 高 度 为 h 的 3 叉 树 中，最 多 含 有 结 点。5.假 定 一 棵 二 叉 树 的 结 点 数 为 18,则 它 的 最 小 深 度 为-，最 大 深 度 为-,6.在 一 棵 二 叉 搜 索 树 中，每 个 分 支 结 点 的 左 子 树 上 所 有 结 点 的 值 一 定 一 一 该 结 点 的 值，右 子 树 上 所 有 结 点 的 值 一 定 一 一 该 结 点 的 值。7.当 向 一 个 小 根 堆 插 入 一 个 具 有 最 小 值 的 元 素 时，该 元 素 需 要 逐 层 一 一 调 整，直 到 被 调 整 到 位 置 为 止。8.表 示 图 的 三 种 存 储 结 构 为-、-和-9.对 用 邻 接 矩 阵 表 示 的 具 有 n 个 顶 点 和 e 条 边 的 图 进 行 任 一 种 遍 历 时，其 时 间 复 杂 度 为，对 用 邻 接 表 表 示 的 图 进 行 任 一 种 遍 历 时，其 时 间 复 杂 度 为.10.从 有 序 表(12,18,30,43,56,78,82,95)中 依 次 二 分 查 找 43和 56元 素 时，其 查 找 长 度 分 别 为 和-11.假 定 对 长 度 n=144的 线 性 表 进 行 索 引 顺 序 查 找，并 假 定 每 个 子 表 的 长 度 均 为，则 进 行 索 引 顺 序 查 找 的 平 均 查 找 长 度 为 一 一，时 间 复 杂 度 为-12.一 棵 B一 树 中 的 所 有 叶 子 结 点 均 处 在 一 一 上。13.每 次 从 无 序 表 中 顺 序 取 出 一 个 元 素，把 这 插 入 到 有 序 表 中 的 适 当 位 置，此 种 排 序 方 法 叫 做 一 排 序；每 次 从 无 序 表 中 挑 选 出 一 个 最 小 或 最 大 元 素，把 它 交 换 到 有 序 表 的 一 端，此 种 排 序 方 法 叫 做 一 一 排 序。14.快 速 排 序 在 乎 均 情 况 下 的 时 间 复 杂 度 为 一 一，最 坏 情 况 下 的 时 间 复 杂 度 为 一 一。三、运 算 题(每 小 题 6 分，共 24分)1.假 定 一 棵 二 叉 树 广 义 表 表 示 为 a(b(c,d),c(,8),分 别 写 出 对 它 进 行 先 序、中 序、后 序 和 后 序 遍 历 的 结 果。序 序 序 t先 中 后 2.V 和 边 集 G 分 别 为：V=0,1,2,3,4,5；E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10,则 求 出 该 图 的 最 小 生 成 树 的 权。最 小 生 成 树 的 权；3.假 定 一 组 记 录 的 排 序 码 为(46,79,56,38,40,84,50,42),则 利 用 堆 排 序 方 法 建 立 的 初 始 堆 为 一 一。4.有 7 个 带 权 结 点，其 权 值 分 别 为 3,7,8,2,6,10,14,试 以 它 们 为 叶 子 结 点 生 成 一 棵 哈 夫 曼 树，求 出 该 树 的 带 权 路 径 长 度、高 度、双 分 支 结 点 数。带 权 路 径 长 度：-高 度：-双 分 支 结 点 数：-。四、阅 读 算 法，回 答 问 题(每 小 题 8 分，共 16分)1.V01dAC(List&L)(InitList(L)；InsertRear(L;25);InsertFront(L,50)；IntaL4=5,8,12,15,36);for(inti=0:i5;i+)if(ai%2=0)InsertFront(L,ai)；elselnsertRear(I.,ai)；)该 算 法 被 调 用 执 行 后，得 到 的 线 性 表 L 为：2.void AG(Queue&Q)(InitQueue(Q)；inta5=6,12,5,15,8；for(int i=0;i5;i+)QInsert(Q,ai)；QInsert(Q,QDelete(Q)；QInsert(Q,20)；QInsert(Q,QDelete(Q)+16)；whi le(!QueueEmpty(Q)coutQDelete(Q)”；)该 算 法 被 调 用 后 得 到 的 输 出 结 果 为：五、算 法 填 空，在 画 有 横 线 的 地 方 填 写 合 适 的 内 容(每 小 题 6 分，共 12分)1.从 一 维 数 组 An)中 二 分 杳 找 关 键 字 为 K 的 元 素 的 递 归 算 法，若 杳 找 成 功 则 返 回 对 应 元 素 的 下 标，否 则 返 回 一 1。IntBinsch(ElemTypeA,Intlow,int high,KeyTypeK)if(low=high)(int mid=(low+high)/2；if(K=Amid.key)-；else if(Kdata=X)return 1;/根 结 点 的 层 号 为 1/向 子 树 中 查 找 x结 点 elseint cl=NodeLevel(BT 一 left,X)；if(cl=l)return cl+1;int c2=:if-;/若 树 中 不 存 在 X 结 点 则 返 回。else return 0；)六、编 写 算 法(8分)按 所 给 函 数 声 明 编 写 一 个 算 法，从 表 头 指 针 为 HL的 单 链 表 中 查 找 出 具 有 最 大 值 的 结 点，该 最 大 值 由 函 数 返 回，若 单 链 表 为 空 则 中 止 运 行。ElemType MaxValue(LNOde*HL);“数 据 结 构”期 末 考 试 试 题 答 案 一、单 选 题(每 小 题 2 分，共 12分)评 分 标 准；选 对 者 得 2分，否 则 不 得 分。1.B 2.B 3.C 4.D 5.B 6.A二、填 空 题(每 空 1分，共 28分)1.顺 序 结 构 链 接 结 构 索 引 结 构 散 列 结 构(次 序 无 先 后)2.值(或 data)子 表 指 针(或 sublist)3.3 x 2.4 5/6 一*十 4.(3h-1)/25.5 186.小 于 大 于(或 大 于 等 于)7.向 上 堆 顶 8.邻 接 矩 阵 邻 接 表 边 集 数 组(次 序 无 先 后)9.0(n2)0(e)10.1 311.13 0()12.同 一 层 13.插 人 选 择 14.0(nlog2n)0(向 三、运 算 题(每 小 题 6 分，共 24分)1.先 序：a,b,c,d,e,f,e/2 分 中 序：c b,d,a,f,8,e/2 分 后 序：c,d,b,e,f e,a/2 分 2.最 小 生 成 树 的 权：31/6 分 3.(84,79,56,42,40,46,50,38)/6 分 4.带 权 路 径 长 度：131/3 分 高 度：5/2 分 双 分 支 结 点 数：6/1分 四、阅 读 算 法，回 答 问 题(每 小 题 8 分，共 16分)评 分 标 准：每 小 题 正 确 得 8 分，出 现 一 处 错 误 扣 4 分，两 处 及 以 上 错 误 不 得 分。1.(36,12,8,50,25,5,15)2.5 15 8 6 20 28五、算 法 填 空，在 画 有 横 线 的 地 方 填 写 合 适 的 内 容(每 小 题 6 分，共 12分)1.feturn mid/2 分 returnBinsch(A,low,mid 1,K)/2 分 returnBmsch(A,mid+1,high,K)/2 分 2.NodeLevel(BT)right,X)/3 分(c2=l)returnc2 十 1/3 分 六、编 写 算 法(8分)评 分 标 准：请 参 考 语 句 后 的 注 释，或 根 据 情 况 酌 情 给 分。ElemType MaxValue(LNodeO*HL。)if(HL=NU1L)/2 分 cerr”Linked list is empty!endl；exit(l)；ElemTypemax：HL 一)data；/3 分 LN0de*p=HI 一 next：/4 分 while(PI：NULL)/7分 if(maxdata)max=p-data：p=p-next；returnmaxs/8 分 数 据 结 构 复 习 资 料 一、填 空 题 1.数 据 结 构 是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的 操 作 对 象 以 及 它 们 之 间 的 关 系 和 运 算 等 的 学 科。2.数 据 结 构 被 形 式 地 定 义 为（D,R）,其 中 D 是 数 据 元 素 的 有 限 集 合,R 是 D 上 的 关 系 有 限 集 合。3.数 据 结 构 包 括 数 据 的 逻 辑 结 构、数 据 的 存 储 结 构 和 数 据 的 运 算 这 三 个 方 面 的 内 容。4.数 据 结 构 按 逻 辑 结 构 可 分 为 两 大 类，它 们 分 别 是 线 性 结 构 和 非 线 性 结 构.5.线 性 结 构 中 元 素 之 间 存 在 一 对 一 关 系,树 形 结 构 中 元 素 之 间 存 在 一 对 多 关 系,图 形 结 构 中 元 素 之 间 存 在 钮 及 关 系。6.在 线 性 结 构 中，第 一 个 结 点 没 有 前 驱 结 点,其 余 每 个 结 点 有 且 只 有 1个 前 驱 结 点；最 后 一 个 结 点 没 有 后 续 结 点,其 余 每 个 结 点 有 且 只 有 1个 后 续 结 点。7.在 树 形 结 构 中，树 根 结 点 没 有 前 驱 结 点,其 余 每 个 结 点 有 且 只 有 1 个 前 驱 结 点:叶 子 结 点 没 有 后 续 结 点,其 余 每 个 结 点 的 后 续 结 点 数 可 以 任 意 多 个 o8.在 图 形 结 构 中，每 个 结 点 的 前 驱 结 点 数 和 后 续 结 点 数 可 以 任 意 多 个.9.数 据 的 存 储 结 构 可 用 四 种 基 本 的 存 储 方 法 表 示，它 们 分 别 是 顺 序、链 式、索 引 和 散 列。10.数 据 的 运 算 最 常 用 的 有 5种，它 们 分 别 是 插 入、删 除、修 改、查 找、排 序。11.一 个 算 法 的 效 率 可 分 为 时 间 效 率 和 空 间 效 率。12.在 顺 序 表 中 插 入 或 删 除 一 个 元 素，需 要 平 均 移 动 表 中 一 半 元 素,具 体 移 动 的 元 素 个 数 与 表 长 和 该 元 素 在 表 中 的 位 置 有 关。13.线 性 表 中 结 点 的 集 合 是 有 限 的,结 点 间 的 关 系 是 一 对 一 的。14.向 一 个 长 度 为 n 的 向 量 的 第 i个 元 素（1近 iWn+1）之 前 插 入 一 个 元 素 时，需 向 后 移 动 n-i+1个 元 素。15.向 一 个 长 度 为 n 的 向 量 中 删 除 第 i个 元 素（IWiWn）时，需 向 前 移 动 n-i 个 元 素。16.在 顺 序 表 中 访 问 任 意 一 结 点 的 时 间 复 杂 度 均 为 必 因 此，顺 序 表 也 称 为 随 机 存 取 的 数 据 结 构。17.顺 序 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置 迹 定 相 邻。单 链 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置 正 速 _相 邻。18.在 单 链 表 中，除 了 首 元 结 点 外，任 一 结 点 的 存 储 位 置 由 其 直 接 前 驱 结 点 的 链 域 的 值 指 示。19.在 n 个 结 点 的 单 链 表 中 要 删 除 已 知 结 点*p,需 找 到 它 的 前 驱 结 点 的 地 址,其 时 间 复 杂 度 为 0（n）。20.向 量、栈 和 队 列 都 是 线 性 结 构,可 以 在 向 量 的 任 何 位 置 插 入 和 删 除 元 素:对 于 栈 只 能 在 栈 顶 插 入 和 删 除 元 素；对 于 队 列 只 能 在 队 尾 插 入 和 队 首 删 除 元 素。21.栈 是 一 种 特 殊 的 线 性 表，允 许 插 入 和 删 除 运 算 的 一 端 称 为 栈 顶 不 允 许 插 入 和 删 除 运 算 的 一 端 称 为 栈 底.22.队 列 是 被 限 定 为 只 能 在 表 的 一 端 进 行 插 入 运 算,在 表 的 另 一 端 进 行 删 除 运 算 的 线 性 表。23.不 包 含 任 何 字 符（长 度 为 0）的 串 称 为 空 串:由 一 个 或 多 个 空 格（仅 由 空 格 符）组 成 的 串 称 为 空 白 串。24.子 串 的 定 位 运 算 称 为 串 的 模 式 匹 配；被 匹 配 的 主 串 称 为 目 标 串,子 串 称 为 模 式。25.假 设 有 二 维 数 组 As*.每 个 元 素 用 相 邻 的 6 个 字 节 存 储，存 储 器 按 字 节 编 址。已 知 A 的 起 始 存 储 位 置（基 地 址）为 1000,则 数 组 A 的 体 积（存 储 量）为 288 B；末 尾 元 素 体 的 第 一 个 字 节 地 址 为 1282；若 按 行 存 储 时，元 素 A”的 第 一 个 字 节 地 址 为（8+4）X6+1000=1072:若 按 列 存 储 时，元 素 批 的 第 一 个 字 节 地 址 为（6X7+4）X6+1000）=1276。26.由 3个 结 点 所 构 成 的 二 叉 树 有 5种 形 态。27.一 棵 深 度 为 6 的 满 二 叉 树 有 又+%=0+m=%-1=31个 分 支 结 点 和 产=3 2 个 叶 子。注：满 二 叉 树 没 有 度 为 1的 结 点，所 以 分 支 结 点 数 就 是 二 度 结 点 数。28.-棵 具 有 2 5 7 个 结 点 的 完 全 二 叉 树，它 的 深 度 为 9（注：用 L log2（n）J+l=L 8.xx J+l=929.设 一 棵 完 全 二 叉 树 有 700个 结 点，则 共 有 3 5 0 个 叶 子 结 点。答：最 快 方 法：用 叶 子 数=n/2=35030.设 一 棵 完 全 二 叉 树 具 有 1000个 结 点，则 此 完 全 二 叉 树 有 5 0 0 个 叶 子 结 点,有 499 个 度 为 2 的 结 点,有 1 个 结 点 只 有 非 空 左 子 树，有 Q 个 结 点 只 有 非 空 右 子 树。答：最 快 方 法：用 叶 子 数=n/2=500,n2=no-l=499.另 外，最 后 一 结 点 为 2i属 于 左 叶 子，右 叶 子 是 空 的，所 以 有 1个 非 空 左 子 树。完 全 二 叉 树 的 特 点 决 定 不 可 能 有 左 空 右 不 空 的 情 况，所 以 非 空 右 子 树 数=0.31.在 数 据 的 存 放 无 规 律 而 言 的 线 性 表 中 进 行 检 索 的 最 佳 方 法 是 顺 序 查 找（线 性 查 找）.32.线 性 有 序 表（a”秘，aw）是 从 小 到 大 排 列 的，对 一 个 给 定 的 值 k,用 二 分 法 检 索 表 中 与 k 相 等 的 元 素，在 查 找 不 成 功 的 情 况 下，最 多 需 要 检 索 8 次。设 有 100个 结 点，用 二 分 法 查 找 时，最 大 比 较 次 数 是 33.假 设 在 有 序 线 性 表 a20上 进 行 折 半 查 找，则 比 较 一 次 查 找 成 功 的 结 点 数 为 1：比 较 两 次 查 找 成 功 的 结 点 数 为，;比 较 四 次 查 找 成 功 的 结 点 数 为 8；平 均 查 找 长 度 为 3.7。解：显 然，平 均 查 找 长 度=0（logs）5次（2）.但 具 体 是 多 少 次，则 不 应 当 按 照 公 式 ASL=，ilk）g2（+l）来 计 算（即（21X1O&21）/20=4.6次 并 不 正 确！因 为 这 是 在 假 设 n=2-l的 情 况 下 推 导 出 来 的 公 式。n应 当 用 穷 举 法 罗 列：全 部 元 素 的 查 找 次 数 为=（1+2X2+4X3+8X4+5X5）=74：ASL=74/20=3.7!34.折 半 查 找 有 序 表（4,6,12,20,28,38,50,70,88,100）,若 查 找 表 中 元 素 20,它 将 依 次 与 表 中 元 素 28,6,12,20 比 较 大 小。35.在 各 种 查 找 方 法 中，平 均 查 找 长 度 与 结 点 个 数 n 无 关 的 查 找 方 法 是 散 列 查 找。36.散 列 法 存 储 的 基 本 思 想 是 由 关 键 字 的 值 决 定 数 据 的 存 储 地 址。二、判 断 正 误（在 正 确 的 说 法 后 面 打 勾，反 之 打 叉）(x)1.链 表 的 每 个 结 点 中 都 恰 好 包 含 一 个 指 针。答：错 误。链 表 中 的 结 点 可 含 多 个 指 针 域，分 别 存 放 多 个 指 针。例 如，双 向 链 表 中 的 结 点 可 以 含 有 两 个 指 针 域，分 别 存 放 指 向 其 直 接 前 趋 和 直 接 后 继 结 点 的 指 针。(X)2.链 表 的 物 理 存 储 结 构 具 有 同 链 表 一 样 的 顺 序。错，链 表 的 存 储 结 构 特 点 是 无 序，而 链 表 的 示 意 图 有 序。(X)3.链 表 的 删 除 算 法 很 简 单，因 为 当 删 除 链 中 某 个 结 点 后，计 算 机 会 自 动 地 将 后 续 的 各 个 单 元 向 前 移 动。错，链 表 的 结 点 不 会 移 动，只 是 指 针 内 容 改 变。(X)4.线 性 表 的 每 个 结 点 只 能 是 一 个 简 单 类 型，而 链 表 的 每 个 结 点 可 以 是 一 个 复 杂 类 型。错，混 淆 了 逻 辑 结 构 与 物 理 结 构，链 表 也 是 线 性 表！且 即 使 是 顺 序 表，也 能 存 放 记 录 型 数 据。(X)5.顺 序 表 结 构 适 宜 于 进 行 顺 序 存 取，而 链 表 适 宜 于 进 行 随 机 存 取。错，正 好 说 反 了。顺 序 表 才 适 合 随 机 存 取，链 表 恰 恰 适 于“顺 藤 摸 瓜”(X)6.顺 序 存 储 方 式 的 优 点 是 存 储 密 度 大，且 插 入、删 除 运 算 效 率 高。错，前 一 半 正 确，但 后 一 半 说 法 错 误，那 是 链 式 存 储 的 优 点。顺 序 存 储 方 式 插 入、删 除 运 算 效 率 较 低，在 表 长 为 n 的 顺 序 表 中，插 入 和 删 除 一 个 数 据 元 素，平 均 需 移 动 表 长-半 个 数 的 数 据 元 素。(X)7.线 性 表 在 物 理 存 储 空 间 中 也 一 定 是 连 续 的。错，线 性 表 有 两 种 存 储 方 式，顺 序 存 储 和 链 式 存 储、后 者 不 要 求 连 续 存 放。(X)8.线 性 表 在 顺 序 存 储 时，逻 辑 上 相 邻 的 元 素 未 必 在 存 储 的 物 理 位 置 次 序 上 相 邻。错 误。线 性 表 有 两 种 存 储 方 式，在 顺 序 存 储 时，逻 辑 上 相 邻 的 元 素 在 存 储 的 物 理 位 置 次 序 上 也 相 邻。(X)9.顺 序 存 储 方 式 只 能 用 于 存 储 线 性 结 构。错 误.顺 序 存 储 方 式 不 仅 能 用 于 存 储 线 性 结 构，还 可 以 用 来 存 放 非 线 性 结 构，例 如 完 全 二 叉 树 是 属 于 非 线 性 结 构，但 其 最 佳 存 储 方 式 是 顺 序 存 储 方 式。(后 一 节 介 绍)(X)10.线 性 表 的 逻 辑 顺 序 与 存 储 顺 序 总 是 一 致 的。错，理 由 同 7。链 式 存 储 就 无 需 一 致。(X)11.线 性 表 的 每 个 结 点 只 能 是 一 个 简 单 类 型，而 链 表 的 每 个 结 点 可 以 是 一 个 复 杂 类 型。错，线 性 表 是 逻 辑 结 构 概 念，可 以 顺 序 存 储 或 链 式 存 储，与 元 素 数 据 类 型 无 关。(X)12.在 表 结 构 中 最 常 用 的 是 线 性 表，栈 和 队 列 不 太 常 用。错，不 一 定 吧？调 用 子 程 序 或 函 数 常 用，CPU中 也 用 队 列。(V)13.栈 是 一 种 对 所 有 插 入、删 除 操 作 限 于 在 表 的 一 端 进 行 的 线 性 表，是 一 种 后 进 先 出 型 结 构。(V)14.对 于 不 同 的 使 用 者，一 个 表 结 构 既 可 以 是 栈，也 可 以 是 队 列，也 可 以 是 线 性 表。正 确，都 是 线 性 逻 辑 结 构，栈 和 队 列 其 实 是 特 殊 的 线 性 表，对 运 算 的 定 义 略 有 不 同 而 已。(X)15.栈 和 链 表 是 两 种 不 同 的 数 据 结 构。错，栈 是 逻 辑 结 构 的 概 念，是 特 殊 殊 线 性 表，而 链 表 是 存 储 结 构 概 念，二 者 不 是 同 类 项。(X)16.栈 和 队 列 是 一 种 非 线 性 数 据 结 构。错，他 们 都 是 线 性 逻 辑 结 构，栈 和 队 列 其 实 是 特 殊 的 线 性 表，对 运 算 的 定 义 略 有 不 同 而 已。(V)17.栈 和 队 列 的 存 储 方 式 既 可 是 顺 序 方 式，也 可 是 链 接 方 式。(V)18.两 个 栈 共 享 一 片 连 续 内 存 空 间 时 1 为 提 高 内 存 利 用 率，减 少 溢 出 机 会，应 把 两 个 栈 的 栈 底 分 别 设 在 这 片 内 存 空 间 的 两 端。(X)19.队 是 一 种 插 入 与 删 除 操 作 分 别 在 表 的 两 端 进 行 的 线 性 表，是 一 种 先 进 后 出 型 结 构。错，后 半 句 不 对。(X)20.一 个 栈 的 输 入 序 列 是 12345,则 栈 的 输 出 序 列 不 可 能 是 12345。错，有 可 能。(V)21.若 二 叉 树 用 二 叉 链 表 作 存 贮 结 构，则 在 n 个 结 点 的 二 叉 树 链 表 中 只 有 匚 1_个 非 空 指 针 域。(X)22.二 叉 树 中 每 个 结 点 的 两 棵 子 树 的 高 度 差 等 于 1。(J)23.二 叉 树 中 每 个 结 点 的 两 棵 子 树 是 有 序 的。(X)24.二 叉 树 中 每 个 结 点 有 两 棵 非 空 子 树 或 有 两 棵 空 子 树。(X)25.二 叉 树 中 每 个 结 点 的 关 键 字 值 大 于 其 左 非 空 子 树(若 存 在 的 话)所 有 结 点 的 关 键 字 值，且 小 于 其 右 非 空 子 树(若 存 在 的 话)所 有 结 点 的 关 键 字 值。(应 当 是 二 叉 排 序 树 的 特 点)(X)26.二 叉 树 中 所 有 结 点 个 数 是 其 中 k 是 树 的 深 度。(应 2T)(X)27.二 叉 树 中 所 有 结 点，如 果 不 存 在 非 空 左 子 树，则 不 存 在 非 空 右 子 树。(x)28.对 于 i 棵 非 空 二 叉 树，它 的 根 结 点 作 为 第 一 层，则 它 的 第 i层 上 最 多 能 有 21个 结 点。(应(4)29.用 二 叉 链 表 法(link-rlink)存 储 包 含 n个 结 点 的 二 叉 树，结 点 的 2n个 指 针 区 域 中 有 n+1个 为 空 指 针。(V)30.具 有 12个 结 点 的 完 全 二 叉 树 有 5 个 度 为 2 的 结 点。三、单 项 选 择 题(B)1.非 线 性 结 构 是 数 据 元 素 之 间 存 在 一 种:A)一 对 多 关 系 B)多 对 多 关 系 C)多 对 一 关 系 D)一 对 一 关 系(C)2.数 据 结 构 中，与 所 使 用 的 计 算 机 无 关 的 是 数 据 的 结 构；A)存 储 B)物 理 0 逻 辑 D)物 理 和 存 储(C)3.算 法 分 析 的 目 的 是：A)找 出 数 据 结 构 的 合 理 性 B)研 究 算 法 中 的 输 入 和 输 出 的 关 系 0 分 析 算 法 的 效 率 以 求 改 进 D)分 析 算 法 的 易 懂 性 和 文 档 性(A)4.算 法 分 析 的 两 个 主 要 方 面 是：A)空 间 复 杂 性 和 时 间 复 杂 性 B)正 确 性 和 简 明 性 0 可 读 性 和 文 档 性 D)数 据 复 杂 性 和 程 序 复 杂 性(C)5.计 算 机 算 法 指 的 是：A)计 算 方 法 B)排 序 方 法 C)解 决 问 题 的 有 限 运 算 序 列 D)调 度 方 法(B)6.计 算 机 算 法 必 须 具 备 输 入、输 出 和 等 5 个 特 性。A)可 行 性、可 移 植 性 和 可 扩 充 性 B)可 行 性、确 定 性 和 有 穷 性 0 确 定 性、有 穷 性 和 稳 定 性 D)易 读 性、稳 定 性 和 安 全 性(C)7.数 据 在 计 算 机 存 储 器 内 表 示 时，物 理 地 址 与 逻 辑 地 址 相 同 并 且 是 连 续 的，称 之 为:(A)存 储 结 构(B)逻 辑 结 构(C)顺 序 存 储 结 构(D)链 式 存 储 结 构(B)8.一 个 向 量 第 一 个 元 素 的 存 储 地 址 是 100,每 个 元 素 的 长 度 为 2,则 第 5个 元 素 的 地 址 是(A)110(B)108(C)100(D)120(A)9.在 n 个 结 点 的 顺 序 表 中，算 法 的 时 间 复 杂 度 是 0(1)的 操 作 是:(A)访 问 第 i个 结 点(1近 iWn)和 求 第 i个 结 点 的 直 接 前 驱(2WiWn)(B)在 第 i个 结 点 后 插 入 一 个 新 结 点(IWiWn)(C)删 除 第 i个 结 点(1近 i近 n)(D)将 n 个 结 点 从 小 到 大 排 序(B)10.向 一 个 有 127个 元 素 的 顺 序 表 中 插 入 一 个 新 元 素 并 保 持 原 来 顺 序 不 变，平 均 要 移 动 一 个 元 素(A)8(B)63.5(C)63(D)7(A)11.链 接 存 储 的 存 储 结 构 所 占 存 储 空 间：(A)分 两 部 分，一 部 分 存 放 结 点 值，另 一 部 分 存 放 表 示 结 点 间 关 系 的 指 针(B)只 有 一 部 分，存 放 结 点 值(C)只 有 一 部 分，存 储 表 示 结 点 间 关 系 的 指 针(D)分 两 部 分，一 部 分 存 放 结 点 值，另 一 部 分 存 放 结 点 所 占 单 元 数(B)12.链 表 是 一 种 采 用 存 储 结 构 存 储 的 线 性 表;(A)顺 序(B)链 式(C)星 式(D)网 状(D)13.线 性 表 若 采 用 链 式 存 储 结 构 时，要 求 内 存 中 可 用 存 储 单 元 的 地 址:(A)必 须 是 连 续 的(B)部 分 地 址 必 须 是 连 续 的(C)一 定 是 不 连 续 的(D)连 续 或 不 连 续 都 可 以(B)1 4.线 性 表 L 在 情 况 下 适 用 于 使 用 链 式 结 构 实 现.(A)需 经 常 修 改 L 中 的 结 点 值(B)需 不 断 对 L 进 行 删 除 插 入(C)L 中 含 有 大 量 的 结 点(D)L 中 结 点 结 构 复 杂(B)15.栈 中 元 素 的 进 出 原 则 是 A.先 进 先 出 B.后 进 先 出 C.栈 空 则 进 D.栈 满 则 出(C)16.若 已 知 一 个 栈 的 入 栈 序 列 是 1,2,3,，n,其 输 出 序 列 为 pl,p2,p3,，pn,若 pl=n,则 pi为 A.i B.n=i C.n-i+1 D.不 确 定(B)17.判 定 一 个 栈 ST(最 多 元 素 为 mO)为 空 的 条 件 是A.ST-top0 B.ST-top=0 C.ST-topOmO D.ST-top=mO(C)18.在 一 个 图 中，所 有 顶 点 的 度 数 之 和 等 于 图 的 边 数 的 倍。A.1/2 B.1 C.2 D.4(B)19.在 一 个 有 向 图 中，所 有 顶 点 的 入 度 之 和 等 于 所 有 顶 点 的 出 度 之 和 的 倍。A.1/2 B.1 C.2 D.4(B)20.有 8 个 结 点 的 无 向 图 最 多 有 条 边。A.14 B.28 C.56(C)21.有 8 个 结 点 的 有 向 完 全 图 有 条 边。A.14 B.28 C.56D.112D.112(B)22.在 表 长 为 n 的 链 表 中 进 行 线 性 查 找，它 的 平 均 查 找 长 度 为 A.A S L=n;B.A S L=(n+l)/2;C.A S L=V n+1：D.A S 1 o g2(n+1)-1(A)23.折 半 查 找 有 序 表(4,6,10,12,20,30,50,70,88,100)若 查 找 表 中 元 素 58,则 它 将 依 次 与 表 中 比 较 大 小，查 找 结 果 是 失 败。A.20,70,30,50 B,30,88,70,50 C.20,50 D.30,88,50(C)24.对 22个 记 录 的 有 序 表 作 折 半 查 找，当 查 找 失 败 时，至 少 需 要 比 较 次 关 键 字。A.3 B.4 C.5 D.6(A)25.链 表 适 用 于 _ 查 找 A.顺 序 B.二 分 法 C.顺 序，也 能 二 分 法 D.随 机 数 据 结 构 与 算 法 复 习 题 一、选 择 题。1.在 数 据 结 构 中，从 逻 辑 上 可 以 把 数 据 结 构 分 为 C。A.动 态 结 构 和 静 态 结 构 B.紧 凑 结 构 和 非 紧 凑 结 构 C.线 性 结 构 和 非 线 性 结 构 D.内 部 结 构 和 外 部 结 构 2.数 据 结 构 在 计 算 机 内 存 中 的 表 示 是 指。A.数 据 的 存 储 结 构 B.数 据 结 构 C.数 据 的 逻 辑 结 构 1).数 据 元 素 之 间 的 关 系 3.在 数 据 结 构 中，与 所 使 用 的 计 算 机 无 关 的 是 数 据 的 A 结 构。A.逻 辑 B.存 储 C.逻 辑 和 存 储 I).物 理 4.在 存 储 数 据 时，通 常 不 仅 要 存 储 各 数 据 元 素 的 值，而 且 还 要 存 储 C.A.数 据 的 处 理 方 法 B.数 据 元 素 的 类 型 C.数 据 元 素 之 间 的 关 系 D.数 据 的 存 储 方 法 5.在 决 定 选 取 何 种 存 储 结 构 时，-一 般 不 考 虑。A.各 结 点 的 值 如 何 B.结 点 个 数 的 多 少 C.对 数 据 有 哪 些 运 算 I).所 用 的 编 程 语 言 实 现 这 种 结 构 是 否 方 便。6.以 下 说 法 正 确 的 是。A.数 据 项 是 数 据 的 基 本 单 位 B.数 据 元 素 是 数 据 的 最 小 单 位 C.数 据 结 构 是 带 结 构 的 数 据 项 的 集 合 D.一 些 表 面 上 很 不 相 同 的 数 据 可 以 有 相 同 的 逻 辑 结 构 7.算 法 分 析 的 目 的 是 C,算 法 分 析 的 两 个 主 要 方 面 是 5，(1)A.找 出 数 据 结 构 的 合 理 性 C.分 析 算 法 的 效 率 以 求 改 进(2)A.空 间 复 杂 度 和 时 间 复 杂 度 C.可 读 性 和 文 档 性 B.研 究 算 法 中 的 输 入 和 输 出 的 关 系 C.分 析 算 法 的 易 读 性 和 文 档 性 B.正 确 性 和 简 明 性 D.数 据 复 杂 性 和 程 序 复 杂 性8.下 面 程 序 段 的 时 间 复 杂 度 是，als=0;for(I=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;9.下 面 程 序 段 的 时 间 复 杂 度 是，ofor(i=0;in;i+)for(j=0;jm;j+)Aij=0;10.下 面 程 序 段 的 时 间 复 杂 度 是 0(l o g 3 n)。i=0；while(inext=NULLC.head-next=head D head!=NULL15.带 头 结 点 的 单 链 表 head为 空 的 判 定 条 件 是 A.head=NULL B head-next=NULLC.head-next=head D head!二 NULL16.若 某 表 最 常 用 的 操 作 是 在 最 后 个 结 点 之 后 插 入 一 个 结 点 或 删 除 最 后 一 个 结 点，则 采 用 D 存 储 方 式 最 节 省 运 算 时 间。A.单 链 表 B.给 出 表 头 指 针 的 单 循