浙江大学2000年计算机科学基础考研试题

　　浙江大学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

　　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+3-i);

　　printf( “%d” ,s);

　　for(s=0, i=0; I<3; i++)

　　s+=*(*a=3-i);

　　printf( “%d” ,s);

　　}

　　问题：上述程序运行后，将输出 。

　　2 #include

　　#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

　　if(!graph.count)}

　　graph.count=top;

　　top=i;

　　}

　　for(i=0;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树的程序。