2017杭州师范大学计算机825计算机基础真题.pdf

杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 1 页 ）杭州师范大学2017年招收攻读硕士研究生入学考试题考 试 科 目 代 码 ： 825考 试 科 目 名 称 ： 计 算 机 基 础说 明 ： 考 生 答 题 时 一 律 写 在 答 题 纸 上 ， 否 则 漏 批 责 任 自 负 。第 一 部 分 ： 程 序 设 计 基 础 （ C 语 言 ）一 、 判 断 题 （ 每 小 题 2分 ， 共 20 分 ）1、 C语 言 的 标 识 符 是 区 分 大 小 写 的 。 （ ）2、 在 编 译 C源 程 序 时 ， 计 算 机 根 本 不 会 去 识 别 各 个 变 量 名 的 具 体 含 义 ， 因 此 命 名规 范 对 编 写 C程 序 而 言 不 是 必 要 的 ， 而 且 有 可 能 会 降 低 编 写 C源 程 序 的 效 率 。（ ）3、 C语 言 中 ， 注 释 不 可 以 出 现 在 程 序 中 任 意 的 地 方 。 （ ）4、 C语 言 程 序 中 的 变 量 必 须 先 声 明 后 使 用 。 （ ）5、 在 C语 言 中 ， B和 “B“在 内 存 中 的 表 示 没 有 区 别 。 （ ）6、 一 个 复 合 语 句 是 作 为 一 个 语 句 处 理 的 且 在 逻 辑 上 相 互 关 联 的 一 组 语 句 。 （ ）7、 C语 言 程 序 的 三 种 基 本 结 构 是 顺 序 结 构 、 分 支 （ 选 择 ） 结 构 和 循 环 结 构 。 （ ）8、 C语 言 的 double类 型 数 据 可 以 精 确 表 示 任 何 实 数 。 （ ）9、 在 C语 言 中 ， 将 语 句 “ if(x=5) y+;” 误 写 作 “ if(x=5) y+;” ， 将 导 致 编译 错 误 。 （ ）10、 在 switch语 句 中 ， 表 达 式 和 常 量 表 达 式 的 值 只 能 是 整 型 、 字 符 型 或 枚 举 型 。（ ）二 、 单 项 选 择 题 （ 每 小 题 2分 ， 共 40分 ）1、 程 序 的 开 发 步 骤 中 不 包 括 （ ） 。杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 2 页 ）A. 撰 写 文 档 B. 程 序 测 试 C. 编 译 链 接 D. 运 行 程 序2、 以 下 （ ） 为 有 效 变 量 名 。A. 234 B. 1926sum C. a double z; 则 以 下 语 句 中 错 误 的 是 （ ） 。A. scanf(“%2d*%d%lf“, B. scanf(“%x%*d%o“, C. scanf(“%d,%lx,%le“, D. scanf(“%x%o%6.2f“, 7、 以 下 程 序 的 输 出 结 果 是 （ ） 。#include int main(void) int a = 1234;printf(“%2dn“, a);return 0;A. 1234 B. 提 示 出 错 、 无 结 果 C. 12 D. 348、 以 下 非 法 的 赋 值 语 句 是 （ ） 。A. n=+i; B. x=(j-); C. +(i+1); D. j+;9、 已 知 ： int x=5,y=5,z=5; 执 行 语 句 ： x%=y+z; 后 ， x的 值 是 （ ） 。A. 0 B. 5 C. 6 D. 110、 “ 变 量 a 的 值 为 5 或 是 6” 应 表 示 为 （ ） 。A. a = 5|a = 6 B. a = 5|a = 6C. a = 5while(k=1)k+;while循 环 执 行 的 次 数 是 （ ） 。A. 无 限 次 B. 有 语 法 错 ， 不 能 执 行C. 一 次 也 不 执 行 D. 执 行 一 次13、 语 句 for(i = 1; i void m(int x, int y) x = 3;y0 = 3;int main(void) int x = 0;int y1;m(x, y);printf(“%d#%dn“, x, y0);return 0;2、 以 下 程 序 的 输 出 结 果 是 _。#include #include struct NODE int num;struct NODE *next;int main(void) struct NODE *p, *q, *r;int sum = 0;p = (struct NODE *)malloc(sizeof(struct NODE);q = (struct NODE *)malloc(sizeof(struct NODE);r = (struct NODE *)malloc(sizeof(struct NODE);p-num = 1;q-num = 2;r-num = 3;p-next = q;杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 5 页 ）q-next = r;r-next = NULL;sum += q-next-num;sum += p-num;printf(“%dn“, sum);return 0;3、 下 列 程 序 执 行 后 ， 文 件 example.txt中 内 容 是 _。#include #include void fun(char *filename, char *str) FILE *fp;int i;fp = fopen(filename, “w“);for(i = 0; i strlen(str); +i)fputc(stri, fp);fclose(fp);int main(void) fun(“example.txt“, “gelivable“);fun(“example.txt“, “awesome“);return 0;第 二 部 分 ： 数 据 结 构一 、 单 选 题 （ 每 小 题 2分 ， 共 40 分 ）1、 下 列 程 序 段 的 时 间 复 杂 度 为 ( )。count = 0;for (k = 1; k = n; k *= 2)for (j = 1; j = n; j+)count+;杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 6 页 ）A、 O(log2n) B、 O(n) C、 O(nlog2n) D、 O(n2)2、 设 顺 序 线 性 表 中 有 n个 数 据 元 素 ， 则 删 除 表 中 第 i个 元 素 需 要 移 动 ( )个元 素 。 A、 n-i B、 n+l -i C、 n-1-i D、 i3、 一 个 栈 的 入 栈 序 列 是 a,b,c,d,e,则 栈 的 不 可 能 的 输 出 序 列 是 ( )。A、 edcba B、 decba C、 dceab D、 abcde4、 下 列 选 项 中 ， 可 以 使 用 二 分 法 查 找 （ binarysearch） 的 关 键 字 序 列 是 ( )，假 设 所 有 数 据 均 保 存 的 数 组 中 。A、 500, 200, 450, 180 B、 500, 450, 200, 180C、 180， 500， 200， 450 D、 180, 200, 500,4505、 循 环 队 列 SQ的 存 储 空 间 是 数 组 dm， 队 头 、 队 尾 指 针 分 别 是 front和 rear，则 执 行 出 队 列 操 作 后 其 头 指 针 front值 是 ( )。A front=front+1 B. front=(front+1)%(m-1)C. front=(front-1)%m D. front=(front+1)%m6、 设 二 维 数 组 Amn按 行 优 先 顺 序 存 储 ， 如 果 A00的 地 址 是 LA， 每 个 元 素占 1个 字 节 ， 则 元 素 Aij的 地 址 为 ( )。A、 LA+(i*m+j) B 、 LA+(i*n+j) C 、 LA+(i-1)*n+j-1 D、LA+(i-1)*m+j-17、 用 “ 左 孩 子 -兄 弟 ” （ left child right sibling） 表 示 法 作 为 树 的 存 储 结 构 ，一 棵 结 点 个 数 大 于 2的 树 转 化 为 二 叉 树 后 ( )。A、 二 叉 树 的 根 仅 含 左 子 树 B、 二 叉 树 的 根 仅 含 右 子 树C、 二 叉 树 的 根 既 含 左 子 树 又 含 右 子 树 D、 以 上 三 种 情 况 均 可 能8、 对 右 边 的 二 叉 树 做 中 序 遍 历 （ inorder traversal） 的 结 果是 ( )。A、 debxac B、 abdexc C、 edxbca D、 abcdxe9、 设 线 性 表 的 长 度 为 n， 则 顺 序 查 找 成 功 的 平 均 比 较 次 数 为( )。 A、 n B、 n/2 C、 (n+1)/2 D、 (n-1)/210、 在 下 列 排 序 算 法 中 ， 平 均 时 间 复 杂 度 为 O（ nlog2n） 的 是 ( )。A、 直 接 插 入 排 序 （ Insertion sort） B、 快 速 排 序 （ Quick sort）C、 起 泡 排 序 （ Bubble sort） D、 基 数 排 序 （ radix sort）a cb xd e杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 7 页 ）11、 在 下 列 排 序 算 法 中 ， 需 要 线 性 附 助 空 间 O(n)的 算 法 是 ( )。A、 堆 排 序 （ Heap sort） B、 归 并 排 序 （ Merge sort）C、 快 速 排 序 （ Quick sort） D、 希 尔 排 序 （ Shell sort）12、 如 果 G是 一 个 共 有 n个 顶 点 的 有 向 完 全 图 ， 则 该 图 中 共 有 ( )条 弧 。A、 （ n2-1） /2 B、 n(n-1) / 2 C、 n(n-1) D、 n2-113、 用 Dijkstra算 法 求 无 向 网 的 单 源 点 最 短 路 径 ， 假 设 用 邻 接 矩 阵 作 为 图 的 存 储结 构 ， 则 算 法 的 时 间 复 杂 度 为 ( )。A、 O(n + e) B、 O(n) C、 O(n2) D、 O(n*e)其 中 ： n为 图 中 的 顶 点 数 ， e为 图 中 边 的 个 数 。14、 对 下 图 的 有 向 图 进 行 拓 扑 排 序 ， 得 到 的 拓 扑 序 列 可 能 是 ( )。A、 3,1,2,6,4,5 B、 3,1,2,4,6,5 C、 3,1,4,2,5,6 D、 3,1,4,2,6,515、 二 叉 树 的 第 k层 的 结 点 数 最 多 为 ( )。A、 2k-1 B、 2K+1 C、 2K-1 D、 2k-116、 设 有 6 个 顶 点 的 有 向 图 ， 该 图 至 少 应 有 ( )条 边 才 能 确 保 是 一 个 连 通 图 。A、 6 B、 5 C、 7 D、 817、 已 知 单 链 表 A长 度 为 m， 单 链 表 B长 度 为 n， 若 将 B连 接 到 A的 末 尾 ， 在 没 有链 尾 指 针 的 情 况 下 ， 算 法 的 时 间 复 杂 度 为 ( )。A、 O(1) B、 O(n) C、 O(m) D、 O(m + n)18、 对 一 棵 完 全 二 叉 树 进 行 层 序 (从 上 到 上 ， 从 左 到 右 )从 1开 始 编 号 。 则 编 号 为n的 结 点 若 存 在 右 孩 子 ， 其 位 置 是 ( )。A、 2n B、 2n-1 C、 2n+1 D、 2n 19、 单 链 表 和 双 向 循 环 链 表 表 示 List时 常 常 增 加 一 个 头 结 点 ， 其 目 的 是 ( )。A.为 了 简 化 查 找 算 法 B.为 了 简 化 归 并 算 法C.为 插 入 删 除 操 作 时 不 需 要 做 特 殊 的 处 理 D.以 上 说 法 都 不 对 。3 41 6 2 5杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 8 页 ）20、 在 下 图 所 示 的 4 棵 二 叉 树 中 ， ( )不 是 完 全 二 叉 树 (Complete BinaryTree)。A、 B、 C、 D、二 、 综 合 应 用 题 （ 共 35分 ）1、 简 述 堆 栈 和 队 列 的 特 点 ， 并 分 别 给 出 应 用 实 例 。 (10分 )2、 已 知 一 棵 二 叉 树 的 中 序 序 列 和 后 序 序 列 分 别 如 下 ， 请 画 出 该 二 叉 树 。 (10分 )中 序 序 列 ： D I G J L K B A E C H F后 序 序 列 ： I L K J G D B E H F C A3、 请 写 出 在 二 叉 查 找 树 （ Binary Search Tree） 中 查 找 某 个 值 的 算 法 。 （ 15分 ）杭 州 师 范 大 学 硕 士 研 究 生 入 学 考 试 命 题 纸2017 年 考 试 科 目 代 码 825 考 试 科 目 名 称 计 算 机 基 础 （ 本 考 试 科 目 共 9页 ， 第 9 页 ）