中国科学技术大学 一九九五年招收硕士学位研究生入学考试试题 试题名称:程序设计 选择题 一颗深度为6的平衡二叉树,其每个非终端节点的平衡因子均为1,则该树共有_____个节点.(2分) a) 14; b) 16; c) 18; d) 20; e) 22; f) 24 一个有28条边的非连通无向图,至少应有____个节点.(2分) a) 6; b) 7; c) 8; d) 9; e) 10; f) 11 一颗124个叶节点的完全二叉树,最多有___个节点.(2分) a) 247; b) 248; c) 249; d) 250; e) 251 按锦标赛排序的方法,决定出8位运动员之间的名次顺序排列,至少需编排____场次的比赛.(考虑最坏情况) (2分) a) 13; b) 14; c) 15; d) 16; e) 17 已知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]] 在下列三种次序的线索二叉树中,___对查找指定节点在该次序下的后继效果较差. (2分) a) 前序线索树 b) 中序线索树 c) 后序线索树 有二叉树的前序和后序遍历序列唯一的确定这颗二叉树. (2分) a) 能 b) 不能 在下列两种求图的最小生成树的算法中,___算法适合于求边稀疏的网的最小生成树. (2分) a) Prim; b) Kruskal 下列无向图的存储结构中,在对无向图的边进行操作时(如删除一条边)____存储结构更为合适 a) 邻接表 b) 邻接多重表 在下述几中树中,___可以表示静态查找表. (2分) a) 次优查找树; b) 二叉排序树; c) B- 树 d) 平衡二叉树 答案写在填空的字母后面 在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是 A 快速排序在最坏情况下,时间复杂度是 B ,比 C 的性能差 就平均时间而言, D 最佳 (共4分) A: a) 直接插入排序; b) 起泡排序; c) 简单选择排序; B: a) O(n log n); b) O(); c) O() C: a) 堆排序; b) 起泡排序; c) 选择排序 D: a) 堆排序; b) 快速排序; c) 归并排序 一程序规定的职能是:“输入三个整数作为三边的边长构成三角形,判别是等腰三角形,等边三角形,或是一般三角形,再做计算…….”.若用等价类划分方法对该程序做功能测试,至少应对该程序的输入数据考虑 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 设二叉树如图所示 给出先序遍历的节点 访问顺序;_________ 给出中序遍历的节点 访问顺序;_________ 给出后序遍历的节点 访问顺序;_________ 若用二叉链表?作为存储 结构,将出现多少个空指 针(nil)域?_____(共4分) 下列函数 (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 程序段 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) b0 4) b0 and c0 程序改错与填空 指出下列程序段中的错误位置,对错误编号,说明理由: 程序段一: (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. 答: ______________________________________________ _____________________________________________. 阅读下列程序,填空使之成为一个完整的程序.该程序输出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. 编程题: (语言可任选,要求思路清晰,书写工整) 编写程序将一个循环队列的内容倒置,该循环队列存储在一个数组A[1..n]中,例如图a中为倒置前的队列,图b中为倒置后的队列.要求倒置后的队列从数组的第一个元素开始存储,整个程序的运行时间为O(n). (15分) 设计一个程序,使输入的句子按如下方式改造之后输出: 单词之间只留一个空格做间隔; 句子结束后必须紧跟句号; 如果把句子的单词从左到右依次编号为1,2,3,…则对于第奇数个单词,只要直接复制就行了,而对于第偶数个单词,应按反序打印.(15分) 例如: 输入句子是: this    is   a   silly     program   ; 改造后的输出是: this  si  a  yllis  program .