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

一、单项选择题

1． 假设栈初始为空, 将中缀表达式

当扫描到f 时, 栈中的元素依次是（ ） A.

B.

C.

D.

【答案】B

【解析】中缀表达式转后缀表达式遵循以下原则:

(1)遇到操作数, 直接输出;

(2)栈为空时, 遇到运算符, 入栈;

(3)遇到左括号, 将其入栈;

(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出;

(5)遇到其他运算符

符入栈;

(6)最终将栈中的元素依次出桟, 输出。

所以扫描到’/’, 入栈‘描到’+’, 由于’+’优先级比’/'低, 所以将’/’弹出, ’+’入栈; 扫描到’*,, 优先级比’+’高, 入栈; 扫描到’(‘, 入栈; 扫描到’一‘, 将栈中优先级更高的’*’弹出, ‘一, 入栈; 扫描到’*’, 优先级比’一‘高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*

2． 在下面的排序方法中，辅助空间为O(n)的是（ ）。

A. 希尔排序

B. 堆排序

C. 选择排序

D. 归并排序

【答案】D

3． 程序段

与对换；

第 2 页，共 52 页 转换为等价后缀表达式的过程中, 时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算

其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。

A.D(n)

B.O(nlogn)

C.O(n3)

D.O(n2)

【答案】D

【解析】这个是冒泡排序，最坏的情况下需要进行l ＋2＋... ＋n ﹣l 次交换，即时间复杂度是0(n2) 。

4． 计算机开后, 操作系统最终被加载到（ ）

A.BIOS

B.ROM

C.EPROM

D.RAM

【答案】D

【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区, 这段区城是RAM , 故答案选D 。

5． 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。

A.60

B.66

C.18000

D.33

【答案】B

【解析】如果是全部，则是需要100*90*2个字节；但是用三元组表示的话，只需要记录非零数据的X 坐标，Y 坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即2*3＝6字节，10个非零整数则是2*3*10＝60字节；如果问有效元素占的空间大小，则选A 项，但是如果从整体来看，应该多一个用来记录矩阵宽(100)、高(90)、默认值(0)的元素，所以还应该多算6个字节。所以全部为66字节，选B 项。

6． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A.0(n)

B.0(n+e) C. D.

【答案】B

【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)

7． 用邻接表存储图所用的空间大小（ ）。

A. 与图的顶点数和边数都有关

第 3 页，共 52 页

B. 只与图的边数有关

C. 只与图的顶点数有关

D. 与边数的平方有关

【答案】A

【解析】邻接表就是对图G 中的每个顶点建立一个单链表，第i 个单链表中的结点表示依附于顶点的边，这个单链表就称为顶点的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。

8． 主机甲通过1个路由器个路由器(存储转发方式) 与主机乙互联, 两段链路的数据传输速率均为10Mbps , 主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为8Mb(1M=106)的报文。若忽略链路传播延迟、分组头开销和拆装时间, 则两种交换方式完成该报文传输所需的总时间分别为（ ）

A.800ms>1600ms

B.801ms 、1600ms

C.1600ms 、800ms

D.1600ms 、801ms

【答案】D

【解析】不进行分组时, 发送一个报文的时延是

的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是

总时间为801ms 。

9． 数组通常具有的两种基本操作是（ ）。

A. 查找和修改

B. 查找和索引

C. 索引和修改

D. 建立和删除

【答案】A

【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。

10．假定主存地址为32位, 按字节编址, 主存和Cache 之间采用直接映射方式, 主存块大小为4个字, 每字32位, 采用回写(Write Back) 方式, 则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。

A.146k

B.147K

第 4 页，共 52 页 , 在接收端接收此报文件, 接收一个报文的时延也是1ms , 但是在发送第二个报文时, 第一个报文已经开始接收。共计有800个分组,