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

一、单项选择题

1． 设栈S 和队列Q 的初始状态均为空，元素a ，b ，c ，d ，e ，f ，g 依次进入栈S. 若每个元素出

d ，c ，f ，e ，a ，g ，. 栈后立即进入队列Q ，且7个元素出队的顺序是b ，则找S 的容量至少是（ ）

A.1

B.2

C.3

D.4

【答案】C

【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序.. 在本题中，每个元素出栈S 后立即进入队列Q ，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序. 根据出桟顺序可以分析各个元素进出栈的过程：第一个出栈元素为b ，表明栈内还有元素a ，b 出栈前的深度为2；第二个出栈元素为d ，栈内元素为a 和c ，d 出栈前的深度为3；c 出栈后，剩余元素为a ，c 出栈前的深度为2；f 出栈后，剩余元素为a 和e ，f 出栈前的深度为3；e 出栈后，剩余元素为a ，e 出栈前的深度为2；a 出栈后，无剩余元素，a 出栈前的深度为1；g 出栈后，无剩余元素，g 出栈前的深度为1. 所以栈容量至少是3.

2． 广义表A ＝(a，b ，(c，d) ，(e，(f，g))) ， 则式子Head(Tail(Head(Tail(Tail(A)))))的值为（ ）。

A.(g)

B.(d)

C.c

D.d

【答案】D

【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。也就是tail 得到的元素需要在外层再加一个（ ）。

3． 若无向图中含7个顶点, 则保证图G 在任何情况下都是连通的, 则需要的边数最少是（ ）。

A.6

B.15

C.16

D.21

【答案】C

【解析】要保证无向图G 在任何情况下都是连通的, 即任意变动图G 中的边, G 始终保持连通。首先需要图G 的任意6个结点构成完全连通子图

再添加一条边将第7个结点与, 需条边, 然后连接起来, 共需16条边。本题非常容易错误地选择选项A , 主要原

因是对“保证图G 在任何情况下都是连通的”的理解, 分析选项A , 在图G 中, 具有7个顶点6条边并不能保证其一定是连通图, 即有n-1条边的图不一定是连通图。分析选项D , 图G 有7个顶点21条边, 那么图G 一定是无向完全图, 无向完全图能保证其在任何情况下都是连通的, 但是这不符合题目中所需边数最少的要求。

4． 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中, 不属于偏移寻址方式的是（ ）。

A. 间接寻址

B. 基址寻址

C. 相对寻址

D. 变址寻址

【答案】A

【解析】在四种不同的寻址方式中, 间接寻址按指令的形式地址从主存中取出操作数的有效地址, 然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。

5． 在采用中断方式控制打印输出的情况下, CPU 和打印控制接口中的端口之间交换的信息不可能是（ ）。

A. 打印字符

B. 主存地址

C. 设备状态

D. 控制命令

【答案】B 【解析】接口的功能包括:①选址功能; ②传送命令功能; ③传送数据功能; ④反映

要的, 因此, 它不可能是CPU 和打印控制接口中的

6． 假定有4个整数用8位补码分别表示为端口之间交换的信息。 。若将运算结果存设备工作状态功能。A 项为数据, C 项为设备状态, D 项为命令。B 项, 主存地址在中断方式控制下是不需放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。 A. B. C. D.

【答案】B

【解析】用补码表示时8位寄存器所能表示的整数范围为

数

,

都未超过127, 不发生溢出

。现在4个整数都是负, 结果溢出, 其余3个算式结果, 在4个选项中, 只有

7． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 A. B. | C. D.

【答案】C

【解析】因为该序列中的结点己经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O(N)。对于采用归并法，它是一种稳定的排序方法，它的时间复杂度为。对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为。

8． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C. 算法的排序性能与被排序元素的数量关系不大

D. 算法的排序性能与被排序元素的数量关系密切

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=tj，且ri 在ij 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

9． 主机甲向主机乙发送一个(SYN一1, seq 一11220) 的TCP 段, 期望与主机乙建立TCP 连接, 若主机乙接受该连接请求, 则主机乙向主机甲发送的正确的TCP 段可能是（ ）。 A. B. C. D.

【答案】C

TCP 是面向连接的, 所谓面向连接, 就是当计算机双方通信时必需先建立连接, 然后数【解析】

据传送, 最后拆除三个过程, 也就是客户主动打开TCP 传输, 服务器被动打开。

第一次握手:客户发送

第二次握手:服务器发送

ack=x+1, 自己选择的序号seq=y。

第三次握手:

客户发送

器给出确认, 其ACK=1, 确认号ack=y+1。

给服务器, 即客户的TCP 向服务器发出连接请求报文段, 给客户, 即服务器的TCP 收到连其首部中的同步位SYN=1, 并选择序号seq=x, 表明传送数据时的第一个数据字节的序号是X 。 接请求报文段后, 如同意则发回确认。服务器在确认报文段中应使SYN=1, 使ACK=1, 其确认号给服务器, 即客户收到此报文段后向服务