中国科学院软件研究所1999年研究生入学考试数据结构与C语言试题
1（5分） 判断正误： ①中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。 ②顺序存储方式只能用于存储线性结构。 ③负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。 ④顺序查找法适用于存储结构为顺序或链接存储的线性表。 ⑤栈和队列都是限制存取点的线性结构。 2（5分） 选择填空： ①图1中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的顶点序列是（1）；而进行广度优先遍历得到的顶点序列是（2）。 （1）A1354267（2）A1534267 B1347625B1726453 C1534276C1354276 D1247653D1247653 E以上答案均不正确E以上答案均不正确 图1题2.1图 ②从临接矩阵A＝可以看出，改图共有（1）个顶点。如果是有向图，该图共有（2）条弧；如果是无向图，则共有（3）条边。 （1）A9B3C6D1E以上答案均不正确 （2）A5B4C3D2E以上答案均不正确 （3）A5B4C3D2E以上答案均不正确 3（15分） 算法设计（建议用类PASCAL语言写出算法） ①二叉排序树采用二叉链表存储。些一个算法，删除节点值是X的节点。要求删除改节点后，此树仍然是一棵二叉排序树，并且高度没有增长。（注：可不考虑被删除的节点是根的情况）。 ②已知关键字序列（K1，K2，K3，…，Kn-1）是大根堆。 （1）试写一算法将（K1，K2，K3，…，Kn-1，Kn）调整为大根堆； （2）利用（1）的算法写一个建大根堆的算法。 4（5分） 以下是对C语言的一些描述，请选择正确答案。 ①在C语言中,数组名作为参数传递给函数,作为实在参数的数组名被处理为（）。 A．该数组的长度 B．该数组的元素个数 C．该数组中各元素的值 D．该数组的首地址 E．以上答案均不对 ②以下程序段的输出是（） #include<stdio.h> voidfun() { staticinta=5; a ; printf(“a=%d\n”,a); } main() { for(inti=0;i<2;i ) fun(); } A.a=6Ba=5Ca=1Da=5E以上答案均不正确 a=7a=6a=1a=5 ③C语言命令行参数很有特点，其一般表达形式是（）。 Amain(intargc,intargv) Bmain(intargc,charargv[]) Cmain(intargc,char*argv) Dmain(intargc,char*argv[]); E以上答案均不正确 ④类型定义： charS[3]=”AB” char*P; 在执行了语句P＝S之后，*（P＋2）的值是（）。 A‘B’ B‘\0’ C不确定 D字符’B’的地址 E以上答案均不正确 ⑤第一个主要采用C语言编写的操作系统是（）。 AMS_DOS BMS_WINDOWS CIBM370 DUNIX E以上答案均不正确 5（20分） ①有15个人围成一圈，顺序从1到15编号。从第一个人开始报数，凡报到n的人退出圈子。用C语言写出程序，输入n(n>=1)的值，输出最后留在圈子里的人的编号。 ②有一磁盘文件“gstudent”内存放研究生（研究生数<500）的数据包括：姓名，学号，性别，年龄，住址，健康状况，专业。用C语言编写程序，完成下列功能： （1）要求将学号，专业信息单独抽出来另建一个简明的研究生专业文件。 （2）从上题的简明“研究生专业”文件中删去一个学号是“9311S009”的研究生的专业数据。页:
[1]