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

一、填空题

1． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

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

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 为运算符的集合。

)

_____；_____；

第 2 页，共 63 页

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

3． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。

【答案】完全；只有一个叶结点的二叉树

4． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。

【答案】2(n－1)

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。

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

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

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

第 3 页，共 63 页

6． 已知二维数组

【答案】1196 中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是: _____。

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

7． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

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

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

9． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。

【答案】0；n+1；top[l]+l＝top[2]

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。

10．克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏

11．在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

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

【答案】11

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

二、单项选择题

13．单级中断系统中, 中断服务程序内的执行顺序是（ ）。

Ⅰ保护现场; Ⅱ开中断; Ⅲ关中断; Ⅳ保存断点; Ⅴ中断事件处理; Ⅵ恢复现场; Ⅶ中断返回 A. B. C. D.

第 4 页，共 63 页