2017年华南师范大学计算机学院925数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． 建立索引文件的目的是_____。
【答案】提高查找速度
2． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树 3．
【答案】5
4． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
5． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
6． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
7． 模式串
的next 函数值序列为_____。
=_____
【答案】01122312
8． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
9． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
已包括进生成树，就把矩阵元素A （i ，j ）置成
（3）算法结束时，相邻矩阵中。
【答案】（1）边上的权值；都大的数；（2）1; 负值；（3）为负；边
10．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
二、算法设计题
11．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。
例如：
第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：
1，4，7……第一个数组
9，12，28，29，45……第二个数组 【答案】算法如下：
12．设在4地
之间架设有6座桥，如图所示。
图
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 （1）试就以上图形说明：此问题有解的条件是什么？ （2）设图中的顶点数为n ，试用C 或一个算法，找出满足要求的一条回路。
【答案】
（1）只有所有的顶点的度都是偶数，才能有解。 （2）算法如下:
修改常规访问标志数组该边尚未访问。
13．若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下：
语言描述与求解此问题有关的数据结构并编写
的含义：当元素值为1时表示该边已访问；当元素值为0时表示