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

一、填空题

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

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

2． 从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶

个关键码。

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

3． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法

，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）

中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ）

{ if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/

{ （2） ;

if （node->rflag）（3）;

else {do t=*x；;

while （*x==node ）;

*x=t;

}

}

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

树每个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

4．

每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是

中序序列是

前庁序列是_____。 【答案】

前序是。

5． 顺序栈用

【答案】 .

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

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

6． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。

7． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2；4；3

【解析】二分法查找元素次数列表

查

找100是找到115就停止了。

8． 组成串的数据元素只能是_____。

【答案】字符

9． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称

增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

10．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；（动态）链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链

表的指针指向下一个元素的物理位置。

11．已

知

求REPLACE （S ，V , m ）=_____。 【答案】

12．在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】

【解析】叶子节点的左右孩子都不存在。

二、选择题

13．设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。

A. 线性表的顺序存储结构

B. 队列

C. 线性表的链式存储结构

D. 栈

【答案】D

【解析】用栈更合适，如果是左括号，进找；如果是右括号，看栈顶是不是左括号，如果是，

则左括号出栈；否则不配对（可以直接结束算法）。处理完所有符号号，如果栈为空则配对成功。

14．用户程序发出磁盘I/O请求后，系统的正确处理流程是（ ）。

A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序

B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序

C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序

D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序

【答案】B

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程 序中发起一次系统调用，操作系统的内核接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备， 即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，正确的顺序应该是用户到系统调用到驱动到中断处理。中断处理处于最底层。