2018年河北师范大学911计算机专业基础(数据结构)[专业硕士]之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。
【答案】算法如下:
按递减次序输出二叉排序树结点的值
是元素为二叉树结点指针的栈，容量足够大
沿右子树向下
结束
2． 已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
3． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 调成大堆 ) 是大根堆。 ) 调整为大根堆； 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 4． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。 【答案】算法如下: 在二叉树t 中査找结点值等于x 的结 点 结束 统计以t 为根结点的子树的叶结点数 n0 . 叶结点 输出并计数 结束 : 5． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。 【答案】算法如下: //串用一维数组s 存储，本算法求最长重复子串，返回其长度 //index记最长的串在s 串中的开始位置，max 记其长度 //length记局部重复子串长度，i 为字符数组下标 //上一个重复子串结束 //当前重复子串长 度大，则更新 max //初始化下一重复子串的起始位置和长度 (”最长重复子串的长度为 .//算法结束 ，在串中的位置 ，max ，index) ； 时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。 二、应用题 6． 在一棵表示有序集S 的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S 分为3部分:在该路径左边结点中的元素组成的集合S1; 在该路径上的结点中的元素组成的集合S2; 在该路径右边结点中的元素组成的集合S3; 有 ？为什么？ 【答案】该结论不成立。例如，本题中对于任一f 的左子树上。对于从a 到根结点路径上的所有均有a 7． 设LS 是一个线性表， ，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在。若对于任意的 是否总 b 的右子树上，这时a>b，因此a ，若采用顺序存储结构，则在等概率的前提下， 之间 的概率为 插入一个元素需要平均移动的元素个数是多少? 若元素插在 与 【答案】需要分两种情况讨论: (1)等概率(后插) ，插入位置0..n ，则平均移动个数为n/2。 (2)若不等概率，则平均移动的元素个数为 8． 设散列表为函数分别为: » 注: ％是求佘数运算 中，函数REV(X)表示颠倒十进制数x 的各位，如码序列为(2，8，31，20，19，18，53，27) 。 (1)试画出插入这8个关键码后的哈希表； (2)计算搜索成功的平均搜索长度ASL 。 【答案】(1)插入这8个关键码后的哈希表如表所示: ，则插入一个元素需要平均移动的元素个数又是多少？ ，即表的大小为m=13。现采用双散列法解决冲突。散列函数和再哈希 其 等。若插入的关键
相关内容
相关标签