计算机统考 计算机统考辅导 计算机统考大纲

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

一、根据下列各题要求填空
1语句：char s[]=²\tgraduate²;
        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+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(²%f\n²,*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
abcd e fg   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.count)}
          graph.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．给定项及相应的权如下表：
序号123456789
项ABCDEFGHI
权1567122546115


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

顶起