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

一、填空题

1． 设广义表

则 是_____tail（L ）是_____；L 的长度是_____；深度是_____。

；；2；2 【答案】（ ）（（ ））

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

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

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

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

3． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____

，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

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

【答案】2（n-l ）

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

5． 在哈希函数中，P 值最好取_____。

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

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

6． 在n 个顶点的非空无向图中，最多有_____个连通分量。

【答案】n

【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。

7． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

8． 已知一循环队列的存储空间为环队列判满的条件是（ ） 【答案】

9． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

10．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。 【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

11．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

12．已

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

知

其中队头和队尾指针分别为front 和rear , 则此循

二、选择题

13．设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。

14．n 个结点的正则二叉树中有每个结点的度或者为0或者为2的二叉树称为正则二叉树。（ ）个叶子。

【答案】D

【解析】二叉树结点总数分别代表度为0，度为1，度为2的结点数）。又在非空二叉树中

：且本题所给树为正则二叉树

，所

以因

此

15．某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，

把一个磁盘块读人缓冲区的时间为

传送到用户区的时间是CPU 对一块数据进行分析的时间为

构下，读人并分析完该文件的时间分别是（ ）。 A. B. C. D.

【答案】B

【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读 出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作，但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入 缓冲区的时间，因此，CPU 会空闲。单缓冲区的总时间=（磁盘写入缓冲区时间+缓冲区读出时间

）处理最后一块数据的时

间

当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，

对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，

同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU 的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并 进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因

将缓冲区的数据，在单缓冲区和双缓冲区结