2018年北京师范大学教育学部894程序设计与数据结构之数据结构考研强化五套模拟题
● 摘要
一、填空题
1．
给定一组数据WPL 的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树:
以它构造一棵哈夫曼树，则树高为_____，带权路径长度
2． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)
【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。
3． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
4． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
5． 已知t) ，LEN(t)＋1))
:
【答案】
；
；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。
6． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
。当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为。
7． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。
【答案】
在B
【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少
8． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
9． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
11．阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
12．建立索引文件的目的是_____。
【答案】提高查找速度
二、判断题
13．设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为O(i)。（ ）
【答案】 ×
【解析】由于该栈采用顺序存储结构，时间复杂度应该为O(1)。
14．在初始数据表已经有序时，快速排序算法的时间复杂度为
【答案】×
【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为。
15．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
16．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
。（ ）
相关内容
相关标签