2017年中国民航大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 如果两个串含有相等的字符，能否说它们相等？
【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。
2．
设与记录
对应的关键字分别是
成立，试证明经过一趟起泡后，一定有记录与值。由题假设知中包括
在
之前且
则
即说明
和
进行交换。
之前全部记录
（其
的关键字一定
如果存在
和
使得
且
【答案】起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到极
是反序；设对于
）中关键字最大为
，故经过起泡排序前i-2次比较后，
为又因故和Rf 为反序，由此可知和必定交换，证毕。
3． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH ， 试画出该二叉树。
【答案】该二叉树如图所示：
图
4． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度，并简要说明理由。 为T （m ，n ）。估算最优的T （m , n ）
【答案】最优的T （m ，n ）是D （n ）。串S2是串S1的子串，且在S1中的位置是1。开始求 出最大公共子串的长度恰是串S2的长度。一般情况下，
5． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。
【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元
素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。 6． 三个进程P1、P2, P3互斥使用一个包含N P1每次用produce （N ＞0）个单元的缓冲区。（ ）生成一个正整数并用put （ ）送入缓冲区某一空单元中；P2每次用getodd （ ）从该缓冲区中取出一个奇数并用countodd （ ）统计奇数个数；P3每次用geteven （ ）从该缓冲区中取出一个偶数并用counteven （ ）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。
【答案】定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty 控制生产者与消费者之间的同步；mutex 控制进程间互斥使用缓冲区，程序如下：
7． 线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？
【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。
（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。
8． 在改进了的（无回溯）字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。
{在模式P 中求nextval 数组的值
}
算法中第4行有
第六行中也有
两处比较语句相同。请分析说明此两处比较
语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？
【答案】第4行的
语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则
语句的意义是，当第J 个字符在模式匹配中失
指针J 和K 均増加1，继续比较。第6行的
配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K
个字符失配时的下一个（即
）。该算法在最坏情况下的时间复杂度
二、算法设计题
9． 写出按后序序列遍历中序线索树的算法。
【答案】算法如下：
//求结点
//求结点
t 最左子孙的左线索
//沿左分支向下
t 最右子孙的右线索
//沿右分支向下