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

一、填空题

1． 中缀式运算结果为_____。

【答案】

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

2． 一个字符串中_____称为该串的子串。

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

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

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_____

第 2 页，共 54 页

(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的

(_____，_____)；

(_____，_____)；

_____

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

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

【答案】

5． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

第 3 页，共 54 页

a 中存放待排序的关键字

【答案】

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

6． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】

；边稀疏

7． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。

【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

8． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

9． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;

10．索引顺序文件既可以顺序存取，也可以 _____存取。

【答案】随机

第 4 页，共 54 页

；2；k