中科院計算機技術(shù)研究所1995年碩士生入學(xué)真題 程序設(shè)計

一.選擇
1.一棵深度為6的平衡二叉樹,其每個非終端結(jié)點的平衡因子均為1,則該樹共有__個終端結(jié)點.(2分)
a.14
b.16
c.18
d.20
e.22
f.24

2.一個有18條邊的非連通無向圖,至少應(yīng)有__個結(jié)點.(2分)
a.6
b.7
c.8
d.9
e.10
f.11

3.一棵124個葉結(jié)點的完全二叉樹,最多有__個結(jié)點.
a.247
b.248
c.249
d.250
e.251(2分)

4.按錦標(biāo)賽排序的方法，決定出8位運動員之間的名次順序排列,至少需編排__場次的比賽.(考慮最壞)
a.13
b.14
c.15
d.16
e.17
(2分)

5.已知Head(Tail([Head(S),Head(Tail(Tail(S))]))廣義表滿足上式,則S為___.
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]]
(其中,方括號表示廣義表,圓括號表示函數(shù),Head()表示取廣義表的頭部)(2分)

6.在下列三種次序的線索二叉樹中,___對查找指定結(jié)點在該次序下的后繼效果較差.(2分)
a.前序線索樹 b.中序線索樹 c.后序線索樹

7.由二叉樹的前序和后序遍歷序列___唯一地確定這棵二叉樹.(2分)
a.能 b. 不能

8.在下列兩種求圖的最小生成樹的算法中,__算法最適合于求邊稀疏的網(wǎng)的最小生成樹(2分)
a.Prim b.Kruskal

9.下列無向圖的存儲結(jié)構(gòu)中,在對無向圖的邊進行操作時,(如刪除一條邊)___存儲結(jié)構(gòu)更為適合.
a.鄰接表
b.鄰接多重表.

10.在下述幾種樹當(dāng)中,__可以表示靜態(tài)查找表.
a.次優(yōu)查找樹;
b.二叉排序樹;
c.B-樹
d.平衡二叉樹

11
(1).在文件局部有序或文件長度較小的情況下,最優(yōu)內(nèi)部排序的方法是_A__.
(2).快速排序在最壞的情況下,時間復(fù)雜度是_B__,_C__的性能差;
(3)就平均時間而言,_D__最佳.
A.: (1)直接插入排序 (2)起泡排序 (3)簡單選擇排序;
B.: (1)O(nlog(n)) (2)O(n^2) 3.O(n^3)
C.: (1)堆排序 (2)起泡排序 (3)選擇排序.
D.:(1)堆排序 (2)快速排序 (3) 歸并排序.

12.一程序規(guī)定的職能是"輸入三個整數(shù)作為三邊的邊長構(gòu)成三角形,判別是等腰三角形,等邊三角形,或是一般三角形.再做計算..."若用等價類劃分方法對該程序作功能測試,至少應(yīng)對該程序的輸入數(shù)據(jù)考慮_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.設(shè)二叉樹如圖所示:
a
/
b e
/ /
c f g
/ /
d h

i
/
j
1.給出先序遍歷的結(jié)點,訪問順序________.
2.給出中序遍歷的結(jié)點,訪問順序________.
3.給出后序遍歷的結(jié)點,訪問順序________.
4.若用二叉鏈表作為存儲結(jié)構(gòu),將出現(xiàn)多少個空指針域?__
(共四分)

14.下列函數(shù)
function calc(x,y :integer): integer;
begin
if y=1 then calc:=x
else calc:=calc(x,y-1)+x
end;
a,b均為正整數(shù),則 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;
保證該程序段運行不出錯的必要條件是:___
(1).b>0;
(2).a>0 and b>0;
(3).b!=0;
(4).b!=0 and c!=0;

二.程序改錯與填空:
1.指出下列程序段中的錯誤位置,對錯誤編號說明理由:
程序段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.{main progam}

2.閱讀下列程序,填空使之成為一個完整的程序:
該程序輸出N個元素的全排列.
程序:
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:=_________;
____________;
end;
end;
end;{permute}
begin
K:=n;
for i:=1 to k do A[i]:=i;
permute(k);
end.

三.編程題:(語言任選)
1.(15分)編寫程序?qū)⒁粋�循環(huán)隊列的內(nèi)容倒置,該循環(huán)隊列存儲在一個數(shù)組A[1..n]

中,例如圖a中為倒置前的隊列,圖b中為倒置后的隊列.要求倒置后的隊列從數(shù)組的第一個元素開始,整個程序的運行時間為O(n).

2.設(shè)計一個程序,使輸入的句子按如下方式改造后輸出:
(1).單詞之間只留一個空格作間隔;
(2).句子結(jié)束后必須緊跟句號;
(3).如果把句子的單詞從左到右依次編號為1,2,3...,則對于第奇數(shù)個單詞,只要直接復(fù)制就行了,而對于第偶數(shù)個單詞,應(yīng)按反序打印.

http://jzcjspjx.com/

【中科院計算機技術(shù)研究所1995年碩士生入學(xué)真題 程序設(shè)計】相關(guān)文章：

農(nóng)信社筆試真題10-27

小升初英語面試真題201608-09

社團面試問題真題09-26

雀巢校園招聘經(jīng)典面試真題08-10

新華社面試真題02-27

考研英語二真題與答案09-28

小升初英語往年精選面試真題08-07

中考英語閱讀真題試題08-16

2016上海各校小升初面試真題08-07

網(wǎng)易游戲部門面試真題08-05