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

一、填空题

1． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ； 2． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2

而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

3． 已知；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，

t) ，LEN(t)＋1))

:

【答案】

，求REPLACE(S，V ，m) ＝_____。

4． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

5． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

6． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。

【答案】逻辑结构；物理结构；操作(运算) ；算法

7． 在哈希函数

中，p 值最好取_____。

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

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

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

【答案】快速

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

9． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

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

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

left 指向其左孩子，

【答案】

left 指向其前驱；，

right 指向其后继。

，

right 指向其右孩子，，

，

二、单项选择题

11．在下图所示的平衡二叉树中, 插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。

A.13、48 B.24、48 C.24、53 D.24、90 【答案】C

【解析】题目中, 插入48以后, 树根结点的平衡因子由-1变为-2, 失去平衡。这属于RL(先右后左) 型平衡旋转, 需做两次(先右旋后左旋转) 旋转操作。过程如下图所示:

显然, 在调整后的新平衡二叉树中, 关键字37所在结点的左、右子结点中保存的关键字分别是24, 53。

12．从堆中删除一个元素的时间复杂度为（ ）。

A.O(1) B. C.O(n) D. 【答案】B

【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为。

13．float 型整数据常用IEEE754单精度浮点格式表示, 假设两个float 型变量x 和Y 分别在32为寄存器f 1和f 2中, 若(f1) =CC900000H, (f2) =BOCOOOOOH, 则x 和y 之间的关系为:（ ）

A. xy且符号相同 D. x>y且符号不同 【答案】A

【解析】两个数对应的IEEE754的标准形式为;

将IEEE754单精度形式的二进制转化为浮点数公式为

由于f1, f2的符号位都是1, 所以f1, f2符号相同, 而阶码上f1>f2, 所以f1>f2, 所以f1的绝对