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

一、填空题

1．

给定一组数据WPL 的值为_____。

【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树:

以它构造一棵哈夫曼树，则树高为_____，带权路径长度

2． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。

【答案】top ﹣1

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。

3． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

4． 已知二维数组

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4 5． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____

【答案】FEGHDCB ；BEF

中每个元素占4个单元，在按行优先方式将其存储到起始地址

为1000的连续存储区域时，A[5，9]的地址是: _____。

【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。

6． 设有N 个结点的完全二叉树顺序存放在向量

【答案】

中，其下标值最大的分支结点为_____。

【解析】最大的分支结点是最后一个叶子结点的父结点。

7． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。

【答案】比较；移动

8． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

9． 已知如下程序段:

语句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。

10．对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

二、判断题

11．二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点(X)的值；其右子树根结点的值大于等于该结点(X)的值，则此二叉树一定是二叉排序树。（ ）

【答案】×

【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点; 其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。

12．二叉树是一般树的特殊情形。（ ）

【答案】×

【解析】树与二叉树是两种不同的树形结构，二叉树中的孩子结点有着严格左右之分的。

13．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）

【答案】×

【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。

14．文件系统采用索引结构是为了节省存储空间。（ ）

【答案】×

【解析】是为了缩短查找的时间，牺牲了一部分存储空间。

15．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）

【答案】×

【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

16．归并排序辅助存储为O(1)（ ）

【答案】×

【解析】归并排序的辅助存储是O Cn)o

17．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）

【答案】×

【解析】伙伴系统的伙伴不一定是位置相邻的内存块。

起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下:

只要符合公式的内存块都是伙伴。