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

一、填空题

1． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。

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

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

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

4． 表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】(表达式中的点(.)是数分隔符，如是三个数)

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

【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因

. 。 为每条边重复出现两次，所有无向完全图的边数为

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

【答案】线性表

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

二、单项选择题

7．

参考模型的网络层提供的是（ ）。

A. 无连接不可靠的数据报服务

B. 无连接可靠的数据报服务

C. 有连接不可靠的虚电路服务

D. 有连接可靠的虚电路服务

【答案】A

【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。

8． 下列关于虚拟存储的叙述中, 正确的是（ ）。

A. 虚拟存储只能基于连续分配技术

B. 虚拟存储只能基于非连续分配技术

C. 虚拟存储容量只受外存容量的限制

D. 虚拟存储容量只受内存容量的限制

【答案】D 。

【解析】所谓虚拟存储, 是指运行的进程不必全部装入内存, 只需要部分装入便可以开始运行的一种技术, 在运行过程中, 当所需要的代码部分不在内存时, 通过一种技术(例如缺页中断技术) , 将所需要的页面调入内存, 从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配, 虚拟存储器和外存大小没有关系, 所以选项中的A , B , C 都是错误的, 所以答案是D 项。

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

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

B. 队列

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

D. 栈

【答案】D

【解析】用栈更合适，如果是左括号，进栈；如果是右括号，看栈顶是不是左括号，如果是，则左括号出栈；否则不配对(可以直接结束算法) 。处理完所有符号号，如果栈为空则配对成功。

10．直接插入排序在最好情况下的时间复杂度为（ ）。 A.

B.O(n) C. 2D.O(n)

【答案】B

【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。

11．—组记录的关键码为(46，79，56，38，40，84) ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A.(38，40，46，56，79，84)

B.(40，38，46，79，56，84)

C.(40，38，46，56，79，84)

D.(40，38，46，84，56，79)

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:46比84小，不交换；

第二次比较:40比46小，交换，此时为(40，79，56，38，46，84) ;

第三次比较:46比79小，交换，此时为(40，46，56，38，79，84) ;

第四次比较:38比46小，交换，此时为(40，38，56，46，79，84) ;

第五次比较:56比46大，交换，此时为(40，38，46，56，79，84) ;

一次划分结束。

12．设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）.

A.33KB

B.519KB

C.1057KB

D.16513KB

【答案】C

【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B ＝lKB ，一级间接地址索引可以索引256/4＝64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B ＝32KB ，二级间接地址索引为256/4×256/4＝4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B ＝1024KB ，共计1KB ＋32KB ＋1024KB ＝1057KB.

13．程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）.

A. 逻辑设备名

B. 物理设备名

C. 主设备号

D. 从设备号

【答案】A

【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等. 而操作系统内部管理设备使用的是设备编号.

14．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。

A. 求子串