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

一、填空题

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

【答案】11

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

2． 试利用下列栈和串的基本操作完成下述填空题。

initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；

置串 判串 返回联接

empty （st ） 判串空函数

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）

第 2 页，共 57 页

为空串；

是否相等的函数；

之后的串；

length （st ） 返回串st 的长度；

sub （S , i , 1） 返回S 中第i 个字符；

注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11

）（12）

取栈顶操作符 操作符取出后，出栈

将pre 的最后一个字符（操作数）加入到中缀式exp 的最后

若ch 是操作数且栈非空，则形成部分中缀表达式

栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符

如ch 是运算符，则入操作符栈s 判栈8是否为空

若读出ch 是操作数且栈为空，则按出错处理

3． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

4． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储 5．

【答案】5

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

【答案】

7． 建立索引文件的目的是_____。

【答案】提高查找速度

8． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

第 3 页，共 57 页

=_____

9． 在二叉树中，指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。 10

．

已

求REPLACE （S ，V , m ）=_____。

【答案】

知

二、判断题

11．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）

【答案】×

【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。

12．设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度均为

【答案】

【解析】入队和出队操作分别在队尾和队头进行，设有尾指针的循环链表对头和尾元素的操 作的时间复杂度是

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

【答案】√

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

14．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

【答案】×

【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。

15．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）

【答案】

【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。

16．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）

【答案】√

第 4 页，共 57 页

（ ）。