中国科学技术大学考研试题.pdf

中国科学技术大学 一九九五年招收硕士学位研究生入学考试试题 试题名称 程序设计 一 选择题 1 一颗深度为 6 的平衡二叉树 其每个非终端节点的平衡因子均为 1 则该树共有 个节点 2 分 a 14 b 16 c 18 d 20 e 22 f 24 2 一个有 28 条边的非连通无向图 至少应有 个节点 2 分 a 6 b 7 c 8 d 9 e 10 f 11 3 一颗 124 个叶节点的完全二叉树 最多有 个节点 2 分 a 247 b 248 c 249 d 250 e 251 4 按锦标赛排序的方法 决定出 8 位运动员之间的名次顺序排列 至少需编排 场次的比赛 考虑最坏 情况 2 分 a 13 b 14 c 15 d 16 e 17 5 已知Head Tail Head S Head Tail Tail S a 广义表S满足上式 则S为 其中 方括号表示 广义表 圆括号表示函数 如 a b 表示由 a b 构成的广义表 而 Head 表示取广义表的头部 2 分 a a b b a b b a a b c a a b b d b a a b e a b b a f b b a a 6 在下列三种次序的线索二叉树中 对查找指定节点在该次序下的后继效果较差 2 分 a 前序线索树 b 中序线索树 c 后序线索树 7 有二叉树的前序和后序遍历序列唯一的确定这颗二叉树 2 分 a 能 b 不能 8 在下列两种求图的最小生成树的算法中 算法适合于求边稀疏的网的最小生成树 2 分 a Prim b Kruskal 9 下列无向图的存储结构中 在对无向图的边进行操作时 如删除一条边 存储结构更为合适 a 邻接表 b 邻接多重表 10 在下述几中树中 可以表示静态查找表 2 分 a 次优查找树 b 二叉排序树 c B 树 d 平衡二叉树 11 答案写在填空的字母后面 1 在文件 局部有序 或文件长度较小的情况下 最佳内部排序的方法是 A 2 快速排序在最坏情况下 时间复杂度是 B 比 C 的性能差 3 就平均时间而言 D 最佳 共 4 分 A a 直接插入排序 b 起泡排序 c 简单选择排序 B a O n log n b O 2 n c O 3 n C a 堆排序 b 起泡排序 c 选择排序 D a 堆排序 b 快速排序 c 归并排序 12 一程序规定的职能是 输入三个整数作为三边的边长构成三角形 判别是等腰三角形 等边三角形 或是一般三角形 再做计算 若用等价类划分方法对该程序做功能测试 至少应对该程序的输入 数据考虑 A 个等价类 其中包括 B 个有效等价和 C 个无效等价类 A B C 答案写在填空的 字母后面 1 3 2 5 3 7 4 12 5 15 6 18 7 21 8 25 9 33 10 40 13 二叉树如图所示 1 给出先序遍历的节点的顺序 2 给出中序遍历的节点的顺序 3 给出后序遍历的节点的顺序 4 用二叉链表 作为存储结构 将出现多少个空指针 nil 域 共 4 分 14 下列函数 6 分 function calc x y integer integer begin if y 1 then calc x else calc calc x y 1 x end a b 均为正整数 则 calc a b 1 a b 1 2 a b 3 a b 4 a a 15 程序段 read a b c 3 0 a b if c 0 then a 1 else a 1 0 1 0 c 1 0 b 保证该程序段运行不出错的必要条件是 4 分 1 b 0 2 a 0 and b 0 3 b 0 4 b 0 and c 0 二 程序改错与填空 1 指出下列程序段中的错误位置 对错误编号 说明理由 程序段一 8 分 label 1 const max 50 type day Mon Tue Wed Thu Fri Sat Sun var date day N integer begin a N N ord 0 b for date Mon to Sun do N ord succ date 1 c for n 1 to 10 do begin 1 语句 end goto 1 end 答 程序段二 8 分 program type input output var R real procedure print var x integer y real var z real procedure sum x integer y real var k real begin z x y k 3 z x x y end sum begin sum x y writeln x y z k end print begin 主程序 readln R print 15 R print R R end 答 2 阅读下列程序 填空使之成为一个完整的程序 该程序输出 N 个元素的全排列 例如 N 3 时 程序输出 为 1 2 3 2 1 3 3 2 1 2 3 1 1 3 2 3 1 2 12 分 程序 program pic input output const n 10 var A array 1 n of integer i k integer procedure output1 begin for i 1 to n do write A i 3 writeln end output1 procedure permute k integer var i t integer begin if k 1 then output1 else begin for i 1 to do begin t A k A k A i A i t t A k end for end else end permute begin k n for i 1 to k do A i i permute k end 三 编程题 语言可任选 要求思路清晰 书写工整 1 编写程序将一个循环队列的内容倒置 该循环队列存储在一个数组 A 1 n 中 例如图 a 中为倒置前的 队列 图 b 中为倒置后的队列 要求倒置后的队列从数组的第一个元素开始存储 整个程序的运行时间 为 O n 15 分 2 设计一个程序 使输入的句子按如下方式改造之后输出 1 单词之间只留一个空格做间隔 2 句子结束后必须紧跟句号 3 如果把句子的单词从左到右依次编号为 1 2 3 则对于第奇数个单词 只要直接复制就行了 而对 于第偶数个单词 应按反序打印 15 分 例如 输入句子是 this is a silly program 改造后的输出是 this si a yllis program 中国科学技术大学 一九九六年招收硕士学位研究生入学考试试题 试题名称 程序设计 一 单项选择 20 分 1 具有几个节点的完全二叉树的深度是 1 nlog2 2 nlog2 1 3 1 nlog2 4 nlog2 1 2 用单循环链表表示队列 正确的说法是 1 可设一个头指针使入队 出队都方便 2 可设一个尾指针使入队 出队都方便 3 必须设头 尾指针才能使入队 出队都方便 4 无论如何 只可能使入队方便 3 对无向图而言 同一条边在邻接表中用两个节点表示而在邻接多重表中只用一个节点表示 因此邻接 多重表所需存储量比邻接表 1 少一半 2 多 但差异不大 3 少 但差异不大 4 一个哈希函数被认为是 好的 如果它满足条件 1 哈希地址分布均匀 2 保证不产生冲突 3 所有哈希地址在表长范围内 4 满足 2 和 3 5 ISAM 文件和 VSAM 文件属于 1 索引非顺序文件 2 索引顺序文件 3 顺序文件 4 散列文件 6 在下述排序算法中 算法是稳定的排序算法 1 希尔排序 2 冒泡排序 3 快速排序 7 平衡二叉树中 若某个节点在左 右子节点的平衡因子为零 则该节点的平衡因子也一定是零 这种说 法 1 不正确 2 正确 8 在下属三种排序算法中 所需辅助存储量最多的是 所需存储量最少的是 平均速度最快 的是 1 堆排序 2 快速排序 3 归并排序 二 问答题 25 分 1 已知某电文中共出现 10 种不同的字母 各个字母出现的频率分别为 A 8 B 5 C 3 D 2 E 7 F 23 G 9 H 15 I 3 J 35 现在对这段电文用三进制进行编码 即码字由 0 1 2 组成 问电文编码总长度最少有多 少位 并画出图 2 A 是一个三对角矩阵 行数与列数相等 用压缩存储的方法将其压缩存储到一维的数组 SA 1 3n 2 中 按行序顺序存储 则 SA k 对应的矩阵元素的下标为 行值 i 列值 j 反过 来 若知道 A 中元素的下标 i j 则其存储位置 k 写出表达式 3 设 A 是一个栈 栈中共有 n 各元素 依次为 n21 a a aL 栈顶元素为 n a B 是一个循环队列 队列中 n 各元素依次为 n21 b b bL 队头元素为 1 b A B 均采用顺序存储结构且存储空间足够大 现要将栈中 元素全部移到队列中 使得队列中元素与栈中元素交替排列 即 B 中元素为 nn332211 a b a b a b a bL 问至少需要多少次基本操作才能完成上述工作 请写出具体步骤 要 求除 A B 外所用的其他附加存储量为 1 每次出栈 入栈 出队列 入队列均看作一次基本操作 4 试为下列二叉树建立后序线索 画出相应的后序线索二叉树 三 算法描述 15 分 以二叉链表作存储结构 编写按层次顺序 从根节点开始 遍历二叉树的算法 四 阅读下列程序 并回答 下列程序是否正确 为什么 如何修改 5 分 var a b c d e f integer procedure mult var x y z integer begin z 0 while x0 do begin if odd x then z z y y y z z x div 2 end end begin a 5 b 7 d 11 e 13 mult a b c 要求输出 c 15 mult d b e a f 要求输出 f 32 end 五 阅读下列程序说明和 C 程序 把应填入其中 处的字句 写在答卷的对应栏内 程序说明 对于正整数n 输出其和等于n且满足以下限制条件的所有正整数的和式 即组成和式的数字自左至右构 成一个非递增的序列 如 n 4 程序输出为 4 4 4 3 1 4 2 2 4 2 1 1 4 1 1 1 1 程序中给出了分别采用递归和非递归解法的两个函数 rd 和 nd 函数 rd 采用递归解法 它有两 个参数 a 和 k 其意义分别是被分解和式的数 n 及当前第 k 深度分解 算法思想是对 n 的所有合 理的和式分解 将分解出的数 称为和数 存于数组 a 中 当其中一个分解已不再需要进一步分解时 即 找到一个解 将存于数组 a 中的一个完整和式的和数输出 当还需要进一部分解时 以要进一部分解 的数及分解深度为参数 递归调用分解和式函数 函数 nd 以要分解的数为参数 另开设一个数组 r 用于存储当前还未分解的余数 在求一个解的第 k 步时 a k 为第k个和数 r k 为相应的余数 当找到一个分解后 此步r k 等于0 给出解 并做回溯处理 从当 前 k 退回到第一个不为 1 的和数 将其减 1 并将其余数加 1 准备去找另一个解 否则 生成下一步的分解 和数与余数 15 分 答 1 2 3 4 5 6 程序 define MAXN 100 int a MAXN r MAXN rd int n int k int j i for j j 1 j a k j if printf d d a 0 a 1 for i 2 i k i printf d a i printf n else nd int n int i k k 0 r 0 n do if printf d d a 0 a 1 for i 2 i 0 if k 0 a k r k else a k 1 r k 1 r k a k 1 k else while k 0 int test data 3 4 5 main int i for i 0 i 1 j 3 分 a k j if 3 分 printf d d a 0 a 1 for i 2 i 2 FibonacciTree d 2 T leftptr FibonacciTree d 1 T rightptr 1 画出深度为 4 的 Fibonacci 树 即用 d 4 调用上述算法的结果 7 分 2 从你画的树中分析深度 d 的 Fibonacci 树中结点总数和 Fibonacci 数的关系 Fibonacci 数定义如下 0 F 1 1 F 1 n F 1 n F 2 n F n 1 3 你所画出的 Fibonacci 树是否为平衡二叉树 若是 它是否为同样深度的平衡二叉树中节点数目最少的 一种 4 分 四 证明若二叉排序数中的一个结点存在两个孩子 则它的中序后继节点没有左孩子 则它的中序前趋节点 没有右孩子 10 分 五 共 25 分 设数组 A 1 n 含有 n 个互不相同的数 若 i A j 则偶对 i j 称为 A 的一个逆 1 列出数组 3 4 9 7 1 的五个逆 2 分 2 元素取自集合 1 2 3 n 的所有数组中 哪一个数组具有最多