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

一、填空题

1． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】

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

所以

2． 中缀式对应的前缀式为_____，若则后缀式的运算结果为_____。 【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

3． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

4． 设数组数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是_____；

（2）存放数组的第8列的所有元素至少需要的单元数_____；

（3）数组按列存储时，元素

【答案】270; 27; 2204

【解析】数组的元素个数为

需要

第8列有9个元素，共占因为每个元素占内存48个二进制位，即6个字节。故总个单元数。个字节，因此至少需要个单元数。由题知，每个元素占3个字节，因为主内存字长为16位，即2个字节，所以至少需要的起始地址是_____。

个单元。按列存储时，的起始地址为

5． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

6． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶

head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。

void leafchain（BiTree Abt）

{p={BiTree）malloc （sizeof （BiTNode ））;

If （!p ）{print£（“OVERFLOW\n”; exit （1）; }

head=p; top=0;

if （bt ）

{top++; stack[top]=bt;

while （top ）

{t=stack[top]; top--;

if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; }

else {if（ （4） ）{top++; stack[top]= （5） ; }

if （ （6） ）{top++; stack[top]= （5） ; }

}

}

（8） ; （9） ; } }

【答案】

p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild:

p->Rchild=head:head->Lchild=p

7． 实现字符串拷贝的函数strcpy 为：

t->Lchild!=null: t->Lchild:

【答案】

8． 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】（Q ，A ，C ，S ，Q ，D ，F ，×，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）

【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

9．

给定一组数据

的值为_____。

【答案】5；96 以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

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

10．串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

二、判断题

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

【答案】×

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

12．树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）

【答案】√

【解析】树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之间的关系。

13．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（ ）

【答案】×

【解析】哈希文件是使用一个函数（算法）来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。

14．数组不适合作为任何二叉树的存储结构。（ ）

【答案】×

【解析】对于完全二叉树，因为其n 个结点的位置已经固定，所以用一维数组作为存储结构