中国科学技术大学
一九九一年招收硕士学位研究生入学考试试题
试题名称:程序设计
选择题(20分)
(从可供选择的答案中选出一个正确的,标上“√”记号.其中:1—4题每题1分,5—12题每题2分)
递归过程结构清晰,程序易度,正确性也容易证明,又不需要附加空间,运行效率亦高.因此,递归是一种很有用的工具.
这种说法完全正确.
这种说法不完全正确.
这种说法完全错误.
二进制数1101100与100110的和,用十进制数表示为:
(1) 74 (2) 75 (3) 82 (4) 83
汇编程序的输出不包括:
目标程序.
浮动模块.
问题程序的结果.
机器语言程序.
用随机算法存取数据记录的方法是:
(1) 顺序 (2) 相对 (3) 交替 (4) 直接
栈的输入序列是1,2,…,n,输出序列是,,…,,若 (1 i n),则有:>>…>.
这种说法正确.
这种说法错误.
平衡二叉树中,若某个节点的左、右孩子的平衡银子为零,则该节点的平衡因子一定是零.
这种说法正确.
这种说法错误.
只要散列表的存贮单元数大于关键字的个数,对于任意取值的关键字,总能找到一个一对一的散列函数表来避免冲突.
这种说法正确.
这种说法错误.
设广义表为L=((a,b,c)).下列的哪个运算能将c分离出来?
tail(L)
tail(tail(L))
tail(head(L))
head(tail(tail(head(L))))
在下列三种次序的线索二叉树中,哪种次序的线索数对查找指定节点在该次序下的后继节点效果较差?
前序线索数
中序线索数
后序线索数
用单循环链表表示的队列,若仅设一个指针,但要求出队和入队操作方便,应当选用
(1) 头指针 (2) 尾指针
对二叉排序数进行从右到左的中根遍历,则所得的节点序列是按关键字
无序排列.
非递减有序排列.
非递增有序排列.
ISAM文件和VSAM文件属于
顺序文件.
索引非顺序文件.
索引顺序文件.
散列文件.
选择填空(8分)
(从可供选择的答案中,选择合适的答案,把号码填入相应的_____中,每空0.5分)
____是适用于描述操作系统等控制程序的语言,贝尔研究所开发UNIX时使用这种语言;____是访问数据库所使用的语言,当初是特定厂家的RDB专用语言,现在可适用于多种RDB;____是初学者会话型语言,是80年代前期个人计算机的主要语言;____是50年代开发的语言,其特征之一是程序和数据都以相同的表示形式进行描述.它广泛的运用于符号处理领域;____是主要面向科学技术计算的语言,可以用近似一般数学式的形式进行描述,它是在计算机发展史上最先在实用领域获得成功的编译语言.
(1) ALGOL (2) BASIC (3) C (4) COBOL (5) FORTRAN (6) LISP
(7) PASCAL (8) PL/1 (9) PROLOG (10) SQL
用汇编语言开发软件时,首先用______编写______程序,在用汇编程序将其变成_____,在变换后的程序中,有效地址尚未分配,任意存贮空间均可再分配的这种程序称为______目标程序.利用____把几个程序连结在一起,有效地已经分配的形式的程序,称为____目标程序.编写好的程序可以用___进行追踪和修改.
(1) 机器语言 (2) 绝对 (3) 浮动 (4) 调试程序 (5) 翻译机
(6) 源 (7) 文本编辑程序 (8) 连结程序
在内部排序方法中,设初始的已排序序列为空,从未排序序列中一次取出元素,与已排序序列中元素作比较,将其放入已排序序列的正确位置上,这种排序方法叫_____,基于交换的排序方法是______和______;利用某种算法,根据记录的关键字值计算出排序位置的方法是______.
(1) 选择排序 (2) 插入排序 (3) 杂凑排序 (4) 冒泡排序
(5) 堆排序 (6) 基数排序 (7) 快速排序 (8) 归并排序
解答下列问题(10分)
对长度为10的有序表进行折半查找,在等概率的假设下,其查找成功的平均查找长度是多少?
一颗深度为h的满k叉树有如下性质:第h层上的节点都是叶子节点,其余各层上每个节点都有k颗非空子树.如果按层次顺序从1开始对全部节点编号.(根为第一层).问:
第i层的节点数目是多少?
编号为n的节点,它的双亲节点(若存在)的编号是多少?
编号为n的节点,它的第i个孩子节点(若存在)的编号是多少?
编号为n的节点,满足什么条件下有右兄弟,其右兄弟的编号是多少?
写出下面程序的运行结果(10分)
program priout(input,output);
procedure print(f1,f2:integer);
var f3:integer;
begin
if f1<=f2 then
begin
if f2 mod f1 =0 then
f3:=f1+1
else
f3:=f1+3;
print(f3,f2-1);
end
writeln(f1, ' ',f2);
end
begin
printf(4,16);
end.
有52张扑克牌,开始它们全部正面朝上.从第2张牌开始,把凡是2的倍数位置上的牌翻成正面朝下;接着从第3张牌开始,把凡是3的倍数位置上的牌正面朝上的翻成正面朝下, 正面朝下的翻成正面朝上;接着从第4张牌开始,把凡是4的倍数位置上的牌按此规律翻转.依此类推,直到第1张要翻的牌是第52张牌为止.试用高级语言编出你的程序.要求程序中具备统计最后有几张牌正面朝上,并打印出它们的位置.
写一算法将向量A[1..n]中的元素循环右移k位,且要求算法的时间和空间代价分别是O(n)和O(1).
已知G=（V，E）是连通图，V={1，2，…，n}.写一算法求G的一颗广度优先生成树T.要求G和T均用邻接表表示.邻接表的类型定义如下:
TYPE link=^node
node=RECORD
vex:1..n;
next:link
END
adjlist=ARRAY[1..n] OF link;
注:算法中若用到队列操作,可直接调用.
(20分)
