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

一、填空题

1． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m＋n)

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

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

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

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

【答案】单链表；双链表；(动态) 链表；静态链表

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

4． 栈是_____的线性表，其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出

5． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

6． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

二、单项选择题

7． 某计算机有五级中断

的顺序为

A.11110

B.01101

C.00011 , 则, 中断屏蔽字为表示对级中断进行

屏蔽。若中断响应优先级从高到低的顺序是, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。

D.01010

【答案】D

B

排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、

需要对开放, 所以相应位应该为“0”, 即为01010。

8． 假定不采用Cache 和指令预取技术, 且机器处于“开中断”状态, 则在下列有关指令执行的叙述中, 错误的是（ ）。.

A. 每个指令周期中CPU 都至少访问内存一次

B. 每个指令周期一定大于或等于一个CPU 时钟周期

C. 空操作指令的指令周期中任何寄存器的内容都不会被改变

D. 当前程序在每条指令执行结束时都可能被外部中断打断

【答案】C

【解析】本题涉及的概念比较多。首先, 如果不采用Cache 和指令预取技术, 每个指令周期中至少要访问内存一次, 即从内存中取指令。其次, 指令有的简单有的复杂, 每个指令周期总大于或等于一个CPU 时钟周期。第三, 即使是空操作指令, 在指令周期中程序计数器PC 的内容也会改变(PC值加“1”) , 为取下一条指令做准备。第四, 如果机器处于“开中断”状态, 在每条指令执行结束时都可能被新的更高级的中断请求所打断。所以应选择选项C 。

9． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。

A.1, 2, 3, 4

B.2, 3, 4, 1

C.3, 2, 4, 1

D.4, 3, 2, 1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右, 这8棵二叉树的中序序列分别为:

(1)4, 3, 2, 1,

(2)3, 4, 2, 1

(3)2, 4, 3, 1

(4)2, 3, 4, 1

(5)1, 4, 3, 2

(6)1, 3, 4, 2

(7)1, 2, 4, 3

(8)1, 2, 3, 4

显然选项C 的中序序列不会出现。

10．FTP 客户和服务器间传递FTP 命令时，使用的连接是（ ）。

A. 建立在TCP 之上的控制连接

B. 建立在TCP 之上的数据连接

C. 建立在UDP 之上的控制连接

D•建立在UDP 之上的数据连接

【答案】A

【解析】对于FTP , 为了保证可靠性，选择TCP 。FTP 应用需要建立两条TCP 连接:一条为控制连接，另一条为数据连接。FTP 服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII 形式表示的。

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

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

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

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

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

【答案】D 。

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

12．算法的计算量的大小称为计算的（ ）。

A. 效率

B. 复杂性

C. 现实性

D. 难度

【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。