2018年北京市培养单位生物物理研究所862计算机学科综合(非专业)之数据结构考研核心题库.doc

2018年北京市培养单位生物物理研究所862计算机学科综合(非专业)之数据结构考研核心题库一、算法设计题1 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。【答案】算法如下: /串用一维数组s 存储，本算法求最长重复子串，返回其长度 /index记最长的串在s 串中的开始位置，max记其长度/length记局部重复子串长度，i 为字符数组下标 /上一个重复子串结束 /当前重复子串长度大，则更新max/初始化下一重复子串的起始位置和长度 (”最长重复子串的长度为 ./算法结束，在串中的位置，max ，index) ； 时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。 2 编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于X 的数据元素。要求你的算法的时间复杂度为【答案】算法如下: 从大到小输出二叉排序树bst 中所有关键字不小于x 的数据元素 ) 是大根堆。) 调整为大根堆；第 2 页，共 36 页，其中，2为排序树中所含结点数，m 为输出的关键字个数。 3 已知关键字序列(试写出一算法将(利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下: 假设 是大堆，本算法把 (2) 4 设计将数组An中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为(n)。【答案】算法如下: /n个整数存于数组A 中，本算法将数组中所有偶数排在奇数之前 /用类C 语言编写，数组下标从0开始 /交换Ai与Aj /算法Arrange 结束 5 给定(已生成) 一个带表头结点的单链表，设head 为头指针，结点的结构为(data，next) ，data 为整型元素，next 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求:不允许使用数组作辅助空间) 。【答案】算法如下: /head是带头结点的单链表的头指针/本算法按递增顺序输出单链表各结点的值，并释放结点所占的存储空间 /循环到仅剩头结点 /pre为元素最小值结点的前驱结点的指针 /P为工作指针 /记住当前最小值结点的前驱 /输出元素最小值结点的数据第 3 页，共 36 页调成大堆 /删除元素值最小的结点，释放结点空间 /释放头结点 二、应用题6 证明:在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求每步论断都指出根据。【答案】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。7 三维数组的每个元素的长度为4个字节，试问该数组要占多少个字节0，的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A5，7的存储首地址。【答案】数组占的存储字节数10*9*7*42520；A5，0，7的存储地址1004*9*72*75*411848 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。(2)因为归并的趟数，其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换一选择排序减少m ，来提高外部排序的效率。9 证明:具有n 个顶点和多于n 1条边的无向连通图G 定不是树。【答案】证明:具有n 个顶点n 1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n 1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。10设二叉树BT 的存储结构如表:表 二叉树BT 的存储结构 其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分别为结点的左、右孩子指针域data第 4 页，共 36 页 一、算法设计题考研试题