中国科学技术大学 一九九二年招收硕士学位研究生入学考试试题 试题名称:程序设计 选择题(请将所选答案编号填入___中.每空一分) 使用 A 能阅读和修改文本文件; B 能协助人们寻找程序的出错位置.检查计算机各部件,报告故障信息的是 C .在支持开放策略的操作系统中,用户可按需要选择配置及必要的程序和设置参数.通过系统 D 形成所需要的操作系统.计算机接通电源后,往往先执行一段通常存放在ROM中的 E 把基本操作系统读入内存. A: ① 源程序 ② 编辑程序 ③ 显示程序 ④ 打印程序 B: ① 可执行程序 ② 连接编辑程序 ③ 编译程序 ④ 排错程序 C: ① 排错程序 ② 文件系统检查程序 ③ 诊断程序 ④ 格式化程序 D: ① 引导程序 ② 生成程序 ③ 装入程序 ④ 加载程序 E: ① 设备程序 ② 进程管理程序 ③ 调度程序 ④ 引导程序 在pascal语言中,正确的说法是____. ① 一个紧缩数组占据的内存是没有紧缩的原数组的五分之一. ② 仅字符数组可以被紧缩. ③ 使用紧缩数组的程序执行时间比不使用紧缩数组的同样程序满. ④ 紧缩数组的单个元素不可存取. 语句 if x<=y then z:=x else z:=2.0*x ; 执行该语句获得 x=z 结果的条件是____. ① x<=y ② x<y ③ x<=y or x=0 ④ x<=y and x<>0 程序段 read(a,b) c := 3.0 * a + b if c=0 then a := 1 else a := 1.0 / c + 1.0 / b ; 当输入数a、b满足______条件时不会出现运行错. ① a>0 and b>0 ② b>0 ③ b<>0 and c<>0 ④ b<>0 二维数组a的成员是6个字符组成的串. 行下标i的范围从0到8,列下标j的范围从1到10. 则存放a至少需要 A 个字节; a的第8列和第5行共占 B 个字节; 若a按行存放,元素a[8,5]的起始地址与a按列存放时的 C 元素的起始地址一致. A: ① 90 ② 180 ③ 240 ④ 540 B: ① 108 ② 114 ③ 54 ④ 60 C: ① a[8,5] ② a[3,10] ③ a[5,8] ④ a[0,9] 某字符串满足: concat(head(s),head(tail(tail(s))))= "ac" (head、tail的定义同广义表) 则S= ________ ① aabc ② acba ③ accc ④ acac 某表达式的前缀形式为: + - * ^ A B C D / E / F + G H 它的中缀形式为:  * C - D + E / F / G + H    设栈的输入序列为1,2,3,…n;输出序列为;若 则当时,为____;若存在k>1使,则当i>k时, 为______. = n – i + 1 ; (2) 不确定 (3) = n – ( i – k ) 设高度为h的二叉树上只有度为0和度为2的节点,则此类二叉树中所含的节点数至少为 A ,至多为 B . A: ① 2h ② 2h - 1 ③ 2h + 1 ④ h + 1 B: ①  ②  ③ -1 ④  一颗含有17个关键字的三阶B树,其非叶节点数最少不能少于___个,最多可以为___个. ① 3 ② 4 ③ 5 ④ 6 ⑤ 7 ⑥ 8 设有6个节点的无向图,该图至少应有___条边才能确保是一个连通图. ① 5 ② 6 ③ 7 ④ 8 ⑤ 9 ⑥ 10 ⑦ 11 ⑧ 12 请填充下面流程图中的(1)—(5),使之成为完整的流程图.该图为ACM函数的非递归求解过程. 该解法设了二个栈M、N. 假设栈充分大,无溢出危险.top为栈指针. (10分) 下面是用FORTRAN语言和PASCAL语言写的程序.任意选读其中一个,计算Value(1),Value(2)的结果. (10分) FORTRAN integer function value(M) M0 = M M1 = 0 L = 1 10 if (M0 .EQ. 0) goto 20 M1 = M1 + mod (M0,2)*L M0 = M0/2 L = L*4 Goto 10 20 M0 = M1 + 17 M1 = 0 L = 1 M1 = M1 + mod(M0,2)*L M0 = M0/4 L = L*2 if (M0 .NE. 0) goto 30 value = M1 return end PASCAL function value(M:integer):integer; var M0,M1,L:integer; begin M0 := M; M1 := 0; L := 1; while not(M0=0) do begin M1 := M1 + mod(M0,2)*L; M0 := M0 div 2; L := L*4 end; M0 := M1 * 17; M1 := 0; L := 1; repeat M1 := M1 + mod (M0,2)*L; M0 := M0 div 4; L := L*2 until M0 = 0; value := M1 end 下面三道程序设计题可任选FORTRAN,PASCAL,C等一种语言编写. 请编写一程序.将n阶方阵A(n>=2)就地按顺时针方向旋转90度,即转移到,其中k=j;l=n+1-i.特别当n为奇数时(例n=2m+1).方阵中心的元素(即)不必旋转.(就地旋转是不允许用另一个矩阵作工作单元). 例如4阶方阵旋转如下: 可编写为子程序或过程,其参数为矩阵A和阶数N. (20分) 设有一颗n个节点的二叉树,其各节点的值均不相同.已知该树的前序序列和中序序列分别存放在向量pre[1..n]和ino[1..n]中,试写一算法建立该树的二叉链表.该算法可写成过程形式.但需要说明参数类型及意义. (20分) 已知有n个元素存放在向量S[1..n]中,其值各不相同,请写一递归算法,生成并输出n个元素的所有排列.