当前位置：问答库＞考研试题

一、填空题

1． 在下面的程序段中，对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次。

2． 模式串的next 函数值序列为_____。

【答案】01122312

3． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。

【答案】操作系统文件；数据库

4． 求最短路径的Dijkstra 算法的时间复杂度为_____。

【答案】

5． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

6． 在哈希函数

中，p 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

7． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。

8． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)

【答案】93

【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。

9． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，

请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:

left 指向其左孩子，

【答案】

left 指向其前驱；，

right 指向其后继。

，

right 指向其右孩子，，

，

在B

10．设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。

11．从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

12．已知如下程序段:

语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。

【答案】(1)n＋1 (2)n

(3)n(n＋3)/2 (4)n(n＋l)/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n(n＋l)/2。

13．设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

14．—个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

15．属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

二、单项选择题