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

一、填空题

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

initstack(S)置S 为空栈；

push(S，X) 元素X 入栈；

pop(S)出栈操作；

gettop(S)返回栈顶元素；

sempty(S)判栈空函数；

setnull(St)置串St 为空串；

length(st)返回串st 的长度；

equal(S1，S 2) 判串S 1并S 2是否相等的函数；

concat(S1，S 2) 返回联接S 1和S 2之后的串；

sub(S，i ，1) 返回S 中第i 个字符；

empty(st)判串空函数

FUNCinvert(pre:string ；V ARexp :string) :boolean ；

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

)

_____；_____；

_____THEN_____

IF_____THEN_____

(_____，_____)；

(_____，_____)；

_____

_____THEN

注意:每个空格只填一个语句。

【答案】(1)initstack(S)//栈s 初始化为空栈

(2)setnull(exp)//串exp 初始化为空串

(3)chinopset//判取出字符是否是操作符

(4)push(s，ch)//如ch 是运算符，则入操作符栈s

(5)sempty(s)//判栈s 是否为空

(6)succ:＝false//若读出ch 是操作数且栈为空，则按出错处理

(7)exp

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

(9)exp

(10)gettop(s)//取栈顶操作符

(11)pop(s)//操作符取出后，出栈

(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后

2． 完善算法:求KMP 算法.next 数组。

k :＝_____；next[1]:＝0；

k :＝_____；

END ；

【答案】0；next[k]

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

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；

4． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】

【解析】哈夫曼树只有度为0和2的节点。

5． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何边的权_____，矩阵的对角线元素全为0。

(2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素

成_____，若

【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边 置

6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

7． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。

8． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

9． 模式串的next 函数值序列为_____。

【答案】01122312

10．在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。

【答案】

二、判断题

11．AOE 网一定是有向无环图。（ ）

【答案】×

【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。

12．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）

【答案】×

【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。