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

一、填空题

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

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

置串 判串 返回联接

empty （st ） 判串空函数

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

注意：毎个空格只填一个语句。

为空串；

是否相等的函数；

之后的串；

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

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

【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11

）（12）

2． 模式串

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

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

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

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

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

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

的next 函数值序列为_____。

【答案】01122312

3． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

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

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

5． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

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

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

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

7． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

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

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，

这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

9． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，

元素个数为 一个元素时，此时堆的元素个数最少，元素个数为

10．高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

11．在循环队列中，队列长度为n ，存储位置从0到，

【答案】

12．设单链表的结点结构为

为指针域，已知指针px 指向单链表中data 为x 的结

编号，以rear 指示实际的队尾元素，现

要在此队列中插入一个新元素，新元素的位置是（ ）。

_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_____;

【答案】

13．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。