计算机技术研究所硕士生入学试题
一．选择
1．一棵深度为6的平衡二*树，其每个非终端结点的平衡因子均为1，则该树共有__个终端结点．（2分）
a．14
b．16
c．18
d．20
e．22
f．24
2．一个有18条边的非连通无向图，至少应有__个结点．（2分）
a．6
b．7
c．8
d．9
e．10
f．11
3．一棵124个叶结点的完全二*树，最多有__个结点．
a．247
b．248
c．249
d．250
e．251（2分）
4．按锦标赛排序的方法，决定出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]]
（其中，方括号表示广义表，圆括号表示函数，Head（）表示取广义表的头部）（2分）
6．在下列三种次序的线索二*树中，___对查找指定结点在该次序下的后继效果较差．（2分）
a．前序线索树 b．中序线索树 c．后序线索树
7．由二*树的前序和后序遍历序列___唯一地确定这棵二*树．（2分）
a．能 b．不能
8．在下列两种求图的最小生成树的算法中，__算法最适合于求边稀疏的网的最小生成树（2分）
a．Prim b．Kruskal
9．下列无向图的存储结构中，在对无向图的边进行操作时，（如删除一条边）___存储结构更为适合．
a．邻接表
b．邻接多重表．
10．在下述几种树当中，__可以表示静态查找表．
a．次优查找树；
b．二*排序树；
c．B－树
d．平衡二*树
11
（1）．在文件局部有序或文件长度较小的情况下，最优内部排序的方法是_A__．
（2）．快速排序在最坏的情况下，时间复杂度是_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．一程序规定的职能是"输入三个整数作为三边的边长构成三角形，判别是等腰三角形，等边三角形，或是一般三角形．再做计算．．．"若用等价类划分方法对该程序作功能测试，至少应对该程序的输入数据考虑_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．若用二*链表作为存储结构，将出现多少个空指针域?
（共四分）
14．下列函数
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；
保证该程序段运行不出错的必要条件是：
（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）．单词之间只留一个空格作间隔；
（2）．句子结束后必须紧跟句号；
（3）．如果把句子的单词从左到右依次编号为1，2，3．．．，则对于第奇数个单词，只要直接复制就行了，而对于第偶数个单词，应按反序打印．
最新评论（共0条）评论一句
Copyright©2007–2021 www.100xuexi.com All rights reserved 圣才学习网 版权所有
全国热线：400-900-8858（09:00-22:00），18001260133（09:00-22:00）
增值电信业务经营许可证 出版物经营许可证 网络文化经营许可证 广播电视节目制作经营许可证
