浙江大学1999年计算机系研究生入学考试试题
计算机科学基础
根据下列各题要求填空（每空3分，共24分）
判断整型变量i，j不同时为０的表达式（i，j不同时为０表达式值为１，同时为０表达式值为０）是：
执行完下列语句后，ｉ值为
int i;
int f(int x)
{ return ((x>0)?f(x-1)+f(x+2)+2:1);}
i=f(3);
(3)将Ａ定义为字符函数指针类型，可写为
（４）对于int i,表达式(j=i=5,i=j<>5+(1>=3<=5))的值为
（５）实现字符串拷贝的函数strcpy为
void strcpy(char *s,char *t) /*copy t to s*/
{ while( )
}
（６）下列程序判断字符串s是否对称，对称则返回1，否则返回0，如f(“abba”)返回1，f(“abab”)返回0
int f( )
{ int I=0,j=0;
whiel(s[j]) ( );
for(j--;I<j&&s[I]==s[j];I++,j--);
return ( )
}
阅读下列程序并回答相应问题(14分)
(1)(6分)
int i,a,b,c;
for(i=0;i<a;i++)
switch (b)
case 1:if (c+j>5) printf(“%c”,’y’);
else printf(“%c”,’x’);
break;
case 2:if (c+i<5) printf(“%c”,’y’);
else printf(“%c”,’x’);
break;
default: printf(“%c”,’x’);
问题：１上述程序若要输出yyx，a,b,c的初值应为：
２上述程序若要输出xy, a,b,c的初值应为
(2)(８分)
#include <stdio.h>
#define s(x,y) (x)^=(y)^=(x)^=(y)
int a[2][5]
void fun1(int v[])
{ int i,j,temp;
for(i=1;i<5;i++)
for(j=i-1;j>=0&&v[j]<v[j+1];j--)
s(v[j],v[j+1])
}
void fun2(int v1[],int v2[])
{ int i=0,j=0;
while(i<5&&j<5)
if(v1[i]>v2[j]) printf(“%d”,v1[i++]);
else printf(“%d”,v2[j++]);
while(i<5) printf(“%d”,v1[i++]);
while(j<5) printf(“%d”,v1[j++]);
printf(“/n”);
}
main()
{ int i,j;
for(i=0;i<2;i++)
for(j=0;j<5;j++)
scanf(“%d”,&a[I][j]);
fun1(a[0]);
fun1(a[1]);
for(i=0;i<2;i++)
for(j=0;j<5;j++)
printf(“%d”,a[I][j]);
printf(“/n”);
fun2(a[0],a[1]);
}
问题：当输入５ ２ ８ １３ １０ ７ ３ １１ ４ ８时，上述程序运行后，第一行将输出
，第二行将输出 .
请用Ｃ编写一个带命令行参数的程序grep.c，当运行grep word filename时将统计文本文件filename中
word出现的次数，其它运行方式均显示出错信息，如：运行grep double stdio.h将输出文
件stdio.h中double出现的次数。请在程序中加必要的注释(12分)
回答下列问题(每题４分，共２０分)
若用一个大小为６的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素
，再加入两个元素后，rer和front的值分别为多少
A)1和5
B)2和4
C)4和2
D)5和1
已知一棵二*树的前序遍历结果为abcdef，中序遍历结果为cbaedf，则后序遍历结果为
CBEFDA
FEDCBA
CBEDFA
不定
将s所指节点加到p所指节点之后（如下图），其语句为：
next
…….
p next
s
A)s->next=p+1;p->next=s;
B)(*p).next=s;(*s).next=(*p).next;
C)s->next=p->next;p->next=s->next;
D)s->next=p->next;p->next=s;
一个n个顶点的连通无向图，其边的个数至少为：
A)n-1 B)n C)n+1 D)nlogn
设HASH表的大小为26(0-25)，HASH函数为第一个字母的ASCII序数(A为0,B为1…)，线性探测函数
为：incr（）=-1，试写出依次插入:Bach,Dvorak,Beethoven,Debussy和Chopia后的HASH表内容及
平均比较长度
试分别采用Kruskal和Prim算法画出下图的最小生成树的生成过程(8分)
①
1 1
② 1 ③
2 3
④ 1 ⑤
1 1
⑥
2-3树的定义如下
2-3树是一搜索树，它或者为空，或者满足如下特性
1.其每一内部节点是一2-node或3-node，2-node有一个元素，而3-node有两个元素
2.设left_child和middle_child分别表示2-node的两个子女，data_1为该节点的元素,data_1.key是它
的关键字值，以left_child为根的2-3子树中所有元素的关键字值均小于data_1.key，而以middle_child
为根的子树中所有元素的关键字值均大于data_1.key
3.设left_child，middle_child和right_child分别表示3-node的三个子女，令data_1和data_r为该节点
的两个元素。则有data_1.key<data_r.key，以left_child为根的2-3子树中所有元素的关键字值得均小
于data_1.key，以middle_child为根的2-3子树中所有元素的关键字值均小于data_r.key且大
于data_1.key，而以right_child为根的2-3子树中所有元素的关键字值均大于data_r.key
4.所有的外部节点都在同一层上，
右图是2-3树的例子，试：画出在该2-3树中插入节点65和35后的新的2-3树（6分）
写出2-3树节点的结构类型定义（5分）
写出2在2-3树中插入新节点的算法（5分）
编写实现上述算法的Ｃ语言程序。（8分）
