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

一、填空题

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

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

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

【答案】线性表

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

3． 已知t) ，LEN(t)＋1))

:

【答案】 ；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。

4． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。

【答案】O(1)；O(n)；O(1)；O(1)

【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。

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

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 的最后

6． 在哈希函数中，p 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

7． 数据结构中评价算法的两个重要指标是_____。

【答案】算法的时间复杂度和空间复杂度

8． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

9． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】if(top!＝n)data[++top]＝x ；

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

10．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有

检索和_____检索。 【答案】关键字；记录号；记录号；顺序；直接

二、判断题

11．二元查找树的任何结点的左右子树都是二元查找树。（ ）

【答案】√

【解析】二元查找树也称作二元排序树。二元查找树的性质:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。

12．静态链表就是一直不发生变化的链表。（ ）

【答案】 ×

【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。

13．对于有n 个结点的二叉树，其高度为log 2n 。（ ）

【答案】 ×

【解析】例如n 结点的单枝树，高度就为n 。