- 相關(guān)推薦
中科院計(jì)算機(jī)技術(shù)研究所1995年碩士生入學(xué)真題 程序設(shè)計(jì)
一.選擇1.一棵深度為6的平衡二叉樹(shù),其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為1,則該樹(shù)共有__個(gè)終端結(jié)點(diǎn).(2分)
a.14
b.16
c.18
d.20
e.22
f.24
2.一個(gè)有18條邊的非連通無(wú)向圖,至少應(yīng)有__個(gè)結(jié)點(diǎn).(2分)
a.6
b.7
c.8
d.9
e.10
f.11
3.一棵124個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù),最多有__個(gè)結(jié)點(diǎn).
a.247
b.248
c.249
d.250
e.251(2分)
4.按錦標(biāo)賽排序的方法，決定出8位運(yùn)動(dòng)員之間的名次順序排列,至少需編排_(tái)_場(chǎng)次的比賽.(考慮最壞)
a.13
b.14
c.15
d.16
e.17
(2分)
5.已知Head(Tail([Head(S),Head(Tail(Tail(S))]))廣義表滿足上式,則S為_(kāi)__.
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]]
(其中,方括號(hào)表示廣義表,圓括號(hào)表示函數(shù),Head()表示取廣義表的頭部)(2分)
6.在下列三種次序的線索二叉樹(shù)中,___對(duì)查找指定結(jié)點(diǎn)在該次序下的后繼效果較差.(2分)
a.前序線索樹(shù) b.中序線索樹(shù) c.后序線索樹(shù)
7.由二叉樹(shù)的前序和后序遍歷序列___唯一地確定這棵二叉樹(shù).(2分)
a.能 b. 不能
8.在下列兩種求圖的最小生成樹(shù)的算法中,__算法最適合于求邊稀疏的網(wǎng)的最小生成樹(shù)(2分)
a.Prim b.Kruskal
9.下列無(wú)向圖的存儲(chǔ)結(jié)構(gòu)中,在對(duì)無(wú)向圖的邊進(jìn)行操作時(shí),(如刪除一條邊)___存儲(chǔ)結(jié)構(gòu)更為適合.
a.鄰接表
b.鄰接多重表.
10.在下述幾種樹(shù)當(dāng)中,__可以表示靜態(tài)查找表.
a.次優(yōu)查找樹(shù);
b.二叉排序樹(shù);
c.B-樹(shù)
d.平衡二叉樹(shù)
11
(1).在文件局部有序或文件長(zhǎng)度較小的情況下,最優(yōu)內(nèi)部排序的方法是_A__.
(2).快速排序在最壞的情況下,時(shí)間復(fù)雜度是_B__,_C__的性能差;
(3)就平均時(shí)間而言,_D__最佳.
A.: (1)直接插入排序 (2)起泡排序 (3)簡(jiǎn)單選擇排序;
B.: (1)O(nlog(n)) (2)O(n^2) 3.O(n^3)
C.: (1)堆排序 (2)起泡排序 (3)選擇排序.
D.:(1)堆排序 (2)快速排序 (3) 歸并排序.
12.一程序規(guī)定的職能是"輸入三個(gè)整數(shù)作為三邊的邊長(zhǎng)構(gòu)成三角形,判別是等腰三角形,等邊三角形,或是一般三角形.再做計(jì)算..."若用等價(jià)類劃分方法對(duì)該程序作功能測(cè)試,至少應(yīng)對(duì)該程序的輸入數(shù)據(jù)考慮_A_個(gè)等價(jià)類,其中包括_B_個(gè)有效等價(jià)類和_C_個(gè)無(wú)效等價(jià)類.
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è)二叉樹(shù)如圖所示:
a
/
b e
/ /
c f g
/ /
d h
i
/
j
1.給出先序遍歷的結(jié)點(diǎn),訪問(wèn)順序________.
2.給出中序遍歷的結(jié)點(diǎn),訪問(wèn)順序________.
3.給出后序遍歷的結(jié)點(diǎn),訪問(wèn)順序________.
4.若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu),將出現(xiàn)多少個(gè)空指針域?__
(共四分)
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;
保證該程序段運(yùn)行不出錯(cuò)的必要條件是:___
(1).b>0;
(2).a>0 and b>0;
(3).b!=0;
(4).b!=0 and c!=0;
二.程序改錯(cuò)與填空:
1.指出下列程序段中的錯(cuò)誤位置,對(duì)錯(cuò)誤編號(hào)說(shuō)明理由:
程序段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:語(yǔ)句;
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.閱讀下列程序,填空使之成為一個(gè)完整的程序:
該程序輸出N個(gè)元素的全排列.
程序:
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.
三.編程題:(語(yǔ)言任選)
1.(15分)編寫(xiě)程序?qū)⒁粋�(gè)循環(huán)隊(duì)列的內(nèi)容倒置,該循環(huán)隊(duì)列存儲(chǔ)在一個(gè)數(shù)組A[1..n]
中,例如圖a中為倒置前的隊(duì)列,圖b中為倒置后的隊(duì)列.要求倒置后的隊(duì)列從數(shù)組的第一個(gè)元素開(kāi)始,整個(gè)程序的運(yùn)行時(shí)間為O(n).
2.設(shè)計(jì)一個(gè)程序,使輸入的句子按如下方式改造后輸出:
(1).單詞之間只留一個(gè)空格作間隔;
(2).句子結(jié)束后必須緊跟句號(hào);
(3).如果把句子的單詞從左到右依次編號(hào)為1,2,3...,則對(duì)于第奇數(shù)個(gè)單詞,只要直接復(fù)制就行了,而對(duì)于第偶數(shù)個(gè)單詞,應(yīng)按反序打印.
【中科院計(jì)算機(jī)技術(shù)研究所1995年碩士生入學(xué)真題 程序設(shè)計(jì)】相關(guān)文章：
農(nóng)信社筆試真題10-27
小升初英語(yǔ)面試真題201608-09
社團(tuán)面試問(wèn)題真題09-26
雀巢校園招聘經(jīng)典面試真題08-10
新華社面試真題02-27
考研英語(yǔ)二真題與答案09-28
小升初英語(yǔ)往年精選面試真題08-07
中考英語(yǔ)閱讀真題試題08-16
2016上海各校小升初面試真題08-07
網(wǎng)易游戲部門面試真題08-05