浙江大学2000年计算机系研究生入学考试试题
考试科目：计算机科学基础

一、根据下列各题要求填空
1语句：char s[]=2/tgraduate2;
printf(“%s%d”,s+2,sizeof(s))；将输出：
A) graduate 10 B)graduate 11 (C)raduate 10 D) raduate 11

2对于int i, j，表达式I&&!j等价于：
A) !(!i||j) B)!(!i&&j) C)! (I&&j) D)i*!j

3下列程序段执行后s值为：
int I=1, s=0
do {if(!(i%2)) continue; s+=i;} while(++i<10);
A) 1 B)45 C)25 D)以上均不是

4执行下列语句后，a的值为：
int a;
#define M(x,y) (x/y)
a=M(4+2,3);
A）2 B）4 C）5 D）以上均不是

5对于：struct node {
char s[10];
int i;
}p[4];
下列哪个赋值是不正确的：
A)p[0].i=2 B)p[0].s= “abc” C)p->i=2 D)*(p->s)= ‘a’

6、执行完下列语句段后，i值为：
int f(int x)
{ return ((x>0)?x*f(x-1):2);}
int i;
i=f(f(1));
A)2 B)4 C)8 D)无限递归

7下面的C代码段用于计算s=x-x2/2+x3/3-x4/4+x5/5…的近似值，请填空：
int i=1;
double t,s;
t=x; s=t;
while (fabs(t>0.00001){ /*fabs(t):t的绝对值 */
i=i+1;
t=t*
s+=t;
}
8执行完下列语句段后，i值为：
int f(int x)
{ static int k=0;
x+=K++;
return x;
}
int i;
i=f(2)*f(2);

二阅读下列程序并回答相应问题
1 #include <stdio.h>
int a[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};
main()
{ int s, i;
for(s=0, i=0;i<3;i++)
s+=*(a[i]+3-i);
printf( “%d” ,s);
for(s=0, i=0; I<3; i++)
s+=*(*a=3-i);
printf( “%d” ,s);
}
问题：上述程序运行后，将输出 。

2 #include <stdio.h>
#define f(x) ((x)*(x)-1)
#define NEAR 1.0e-5
int g(float low, float upp, float * result)
{ float mid;
if (f(low)*f(upp)>=0||low?=upp) return 0;
while (upp-low>NEAR) {
mid=(low+upp)/2;
if(f(upp)*f(mid)<0) low=mid;
else if (f(low)*f(mid)<0) upp=mid;
else break;
}
*result=mid;
return 1;
}
main()
{ float *s;
if (g(0,3,s) printf(2%f/n2,*s);
}
问题：函数int g(float low, float upp, float 8result)的功能是什么？请估计该程序的输出结果是什么

？
三请用C编写一个用于对文本文件中的连续字符个数进行统计（即记录连续出现的字符个数，格式：个数-

字符，）的程序count.c.,运行方式为count fromfile tofile。如：当文本文件s.txt内容为“aaaabcccdd”

时，运行count s.txt t.tx后，文件文件t.tx的内容为“4-a,1-b,3-c,2-d，”。请在程序中加必要的注

释（12分）。

四证明任一点个数为n的二*树的高度至少为O(log n)。

五采秀顺序存储结构的二*树。如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

a b c d e f g H
(1)画出二*树表示及中序线索二*树；
(2)写出前序遍历和后序遍历的结果；
(3)画出把该二*树转换成森林的图；
(4) 设二*树采用链式存储结构，试编写一个按层次顺序（同一层次自左至右）遍历二*树的非递归算法。

六如下为拓扑排序的C程序，
1．列出对右图执行该程序后的输出结果。
2．在程序空白处填上适当语句。
Woid topsort (hdnodes graph[],int n)
{
int i, j, k, top;
node_pointer ptr;
top=-1;
for(i=0; i<n; i++)
if(!graph[i].count)}
graph[i].count=top;
top=i;
}
for(i=0;i<n;i++)
if( ){
fprintf9stderr, “/ngraph has a cycle |n” );
exit(1);
}
else{
j=top;
;
printf( “v%d, “,j);
for (ptr=graph[j].link; ptr;ptr=ptr->link){
k=ptr->vertex;
graph[k].count--;
if( ){
graph[k].count=top;
top=k;
}
}
}
}
}

七给定一组项及其权值，假定项都存放于二*树的树叶结点，则具有最小带权外部路径长度的树称为Huf

fman树，
1．给出构造Huffman树的算法。
2．给定项及相应的权如下表：

序号 1 2 3 4 5 6 7 8 9
项 A B C D E F G H I
权 15 6 7 12 25 4 6 1 15

画出执行上述算法后得到的Huffman树。
3．用C语言编写构造Huffman树的程序