考研专业课：中国科技大学计算机真题（1996）
2014 考研专业课大纲已经发布，考生要对照大纲的变化好好复习，调整自己的规划。同时要关注各高校历年真题，利用真题和大纲做好考前的强化备考。文都教育 考研专业课频道为考生提供10大高校计算机复习考题，希望考生认真利用这些真题，仔细研究，寻找突破点，及时的查漏补缺，复习好计算机专业课，下面请看1996中国科技大学计算机真题。中国科技大学1996年考研试题(程序设计)
一、单项选择：(20分)
1、具有N个结点的完全二叉树的深度是：( )
(1) (2)/1 (3) (4)-1
2、用单循环链表表示队列，正确的说法是：( )
(1)可设一个头指针使入队、出队都方便
(2)可设一个尾指针使入队、出队都方便
(3)必须设头尾指针才能使入队、出队都方便
(4)无论如何，只可能使入队方便
3、对无向图而言，同一条边在邻接表中用两个结点表示，而在邻接多重表中只用一个结点表示，故此邻接多重表所需存储量比邻接表( )
(1)少一半 (2)多，但差异不大 (3)少，但差异不大
4、一个哈希函数被认为是“好的”，如果它满足条件( )
(1)哈希地址分布均匀
(2)保证不产生冲突
(3)所有哈希地址在表长范围内
(4)满足(2)和(3)
5、ISAM文件和VSAM文件属于( )
(1)索引非排序文件
(2)索引顺序文件
(3)顺序文件
(4)散列文件
6、在下述排序算法中( )算法是稳定的排序算法。
(1)希尔排序
(2)快速排序
(3)冒泡排序(BUBBLE SORT)
7、平衡二叉树中，若某个结点在左、右子结点的平衡因子为零，则该因子的平衡因子也一定是零，这种说法( )
(1)不正确 (2)正确
8、在下述三种排序算法中，所需辅助存储量最多的是( )，所需存储量最少的是( )，平均速度的是( )
(1)堆排列 (2)快速排列 (3)归并排列
二、问答题(25分)
1、已知某电文中共出现十种不同的字母，各个字母出现的频率分别为A：8，B：5，C：3，D：2，E：7，F：23，G：9，H：15，I：3，J：35，现在对这段电文用三进制进行编码(即码字由0，1，2，组成)，问电文编码总长度最少有多少位?并画出图。
2、A是一个三对角短阵、行数与列数相等，用压缩存储的方法将其压缩存储列一堆的数组SA中(按行顺序存储)，则SA对应的短阵元素的下标为：行值I=( )，列值J=( )，反过来，若知道A中元素的下标I，J，则其存储住值置K=( )。(写出表达式)
3、设A是一个栈，栈中共有N个元素，依次为A1，A2，AN，站顶元素为AN，B是一个循环队列，队列中N个元素依次为B1，B2，BN，对头元素为B1，A，B均采用顺序存储结构且存储空间足够大，现要将站中元素全部移到队列中，使得队列中元素与站中元素交替排列，即B中元素为B1，A1，B2，A2，B3，A3，BN，AN，问至少需要多少次基本操作才能完成上述工作，请写出具体步骤(要求除A，B外所用的其他附加存储量为1，每次出栈、入栈、出队列可均看作一次基本操
作)。
4、试为下列二叉树建立后序线索，画出相应的后序线索二叉树。
三、算法描述(15分)
以二叉链表作存储结构，编写按层次顺序(从根结点开始)遍历二叉树的算法。
四、阅读下列程序，并回答：下列程序是否正确?为什么?如何修改?
var a,b,c,d,e,f :integer;
procedure mult(var x,y,z:integer);
begin
z:=0;
while x0 do
begin
if odd(x) then z:=z+y;
y:=y+z;
z:=x div 2;
end;
end;
begin
a:=5;b:=7;d:=11;e:=13;
mult(a,b,c);{要求输出c=15}
mult(d-b,e-a,f);{要求输出f=32}
end.
五、阅读下列程序说明和C程序，把应填入其中方框处的字句，写在答卷的对应栏内。
[程序说明]
对于正整数N，输出其和等于N且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如N=4，程序输出为：
4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1
程序中分别采用递归和非递归解法的两个函数RD()和ND()。
函数RD()采用递归解法，它有两个参数N和K。其意义分别是被分解和式的数N，及当前第K度分解。算法思想是对N的所有合理的和式分解，将分解出的数(称为和数)存于数组A{}中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组A{}中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。
函数ND()以要分解的数为参数，另开设一个数组R{}，用于存储当前还未分解的余数。在求一个解的第K步时，A{K}为第K个和数，R{K}为相应的余数。当找到一个分解后(此步R{K}等于0)，输出解，并作回溯处理，从当前K退回到第一个不为1的和数，将其减1，并将其余数加1，准备去找另一个解，否则，生成下一步的分解和数与余数。(15分)
答：(1)----------(2)--------------
(3)----------(4)--------------
(5)----------(6)--------------
[程序]
#defin MAXN 100
int a,a;
rd(int n,int k)
{ int j,i;
for(j=(1);j>=1;j--)
{a=j;
if( (2) )
{ printf("%d=%d",a,a};
for(i=2;i
printf(" +%d",a);
printf("n");
eise(3)
}
}
nd(int n)
{ int i,k;
k=0; r =n;
do
{ if ( (4) )
{printf("%d=%d",a,a);
for(i=2;i
printf(".+ %d",a);
printf("n");
while (k >0 &&(5) ) k--;
if (k > 0) {a(k)--;r(k)++;}
}
else { a =(6);
r = r -a;
k++;
}
} while (k >0);
}
int test_data[] = {3,4,5};
main()
{ int i;
for(i =0;i
{ a =test_data;
rd(test_data,1);
printf("n________________nn");
nd(test_data);
printf("n________________nn")
}
}
六、设计一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后以表的形式输出结果。要求用一个二叉树来保存处理结果，字符串中的每个不同的字符用树中不同的结点描述，每个结点包含四个域，格式为：
字符
该字符的出现次数
指向ASCII码小于该字符的左子树指针
指向ASCII码大于该字符的右子树指针
因此程序的功能是依次从输入字符串中取出一个字符，把它们插入到树中(新出现字符)或修改原树中相应结点的“出现次数域”(已出现字符)。(20分)
部分参考答案：
一、2、 2、 2、 1、 2、 3、 1、 3、1、2
二、(1)4*2+3*2+5*2+1 =25
(2)I=+1 J=K-2 K=ZI-2+J
(3)步骤：1、先将站中所有元素依次入队，则站空，队为B1----BNAN---A1
2、将B1~BN依次出队、入队，则队列变为AN---A1B1---BN
3、将AN~~~A1出队入站则站为A1---AN (A1为站顶)，队为B1----BN
4、顺次BI出队、入队，AI出站入队，则最后为B1A1---BNAN
总共有2N+2N+2N+4N=10N个基本操作。
上面是中国科技大学1996年考研专业课 计算机的计算机真题，望考生通过做真题，考生能够发现自己的知识漏洞，及时的补充和纠正，争取精确、深度的把握专业课知识，打好专业课的基础。最后，都希望大家考研成功，加油!
更多考研专业课信息关注 文都教育
页:
[1]