1、中国科学院软件研究所 1999 年研究生入学考试 数据结构与 C 语言试题1 （5 分） 判断正误： 中序遍历一棵二叉排序树的节点就可得到排好序的节点序列。 顺序存储方式只能用于存储线性结构。 负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。 顺序查找法适用于存储结构为顺序或链接存储的线性表。 栈和队列都是限制存取点的线性结构。2 （5 分） 选择填空： 图 1 中给出由 7 个顶点组成的无向图。从顶点 1 出发，对它进行深度优先遍历得到的顶点序列是（1）；而进行广度优先遍历得到的顶点序列是（2）。（1） A 1354267 （2） A 1534267B 1347625 B
2、 1726453C 1534276 C 1354276D 1247653 D 1247653E 以上答案均不正确 E 以上答案均不正确图 1 题 2.1 图 从临接矩阵 A 可以看出，改图共有（1）个顶点。如果是有向图，该图共有（2）条弧；如果是无向图，则共有（3）条边。（1） A 9 B 3 C 6 D 1 E 以上答案均不正确（2） A 5 B 4 C 3 D 2 E 以上答案均不正确（3） A 5 B 4 C 3 D 2 E 以上答案均不正确3 （15 分） 算法设计（建议用类 PASCAL 语言写出算法） 二叉排序树采用二叉链表存储。些一个算法，删除节点值是 X 的节点。要求删除改节点
3、后，此树仍然是一棵二叉排序树，并且高度没有增长。（注：可不考虑被删除的节点是根的情况）。已知关键字序列（K 1，K 2 ，K 3 ，K n-1）是大根堆。（1）试写一算法将（K 1，K 2 ，K 3 ，K n-1 ，K n）调整为大根堆；（2）利用（1）的算法写一个建大根堆的算法。4 （5 分） 以下是对 C 语言的一些描述，请选择正确答案。 在 C 语言中,数组名作为参数传递给函数 ,作为实在参数的数组名被处理为（ ）。A该数组的长度B该数组的元素个数C该数组中各元素的值D该数组的首地址E以上答案均不对 以下程序段的输出是（ ）#include void fun()static int a=5;a+;printf(“a=%dn”,a);main()for(int i=0;i=1)的值，输出最后留在圈子里的人的编号。有一磁盘文件“gstudent”内存放研究生（研究生数500）的数据包括：姓名，学号，性别，年龄，住址，健康状况，专业。用 C 语言编写程序，完成下列功能：（1）要求将学号，专业信息单独抽出来另建一个简明的研究生专业文件。（2）从上题的简明“研究生专业”文件中删去一个学号是“9311S009”的研究生的专业数据。
