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

一、单项选择题

1． 图中有关路径的定义正确的是（ ）。

A. 由顶点和相邻顶点构成的边所形成的序列

B. 由不同顶点所形成的序列

C. 由不同边所形成的序列

D. 上述定义都不是

【答案】A

【解析】顶点到顶点之间的一条路径是指顶点序列。路径上边的数目称为路径的长度。

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

A. 求子串

B. 判断是否相等

C. 模型匹配

D. 连接

【答案】C

【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。

3． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。

A. 存在, 且唯一

B. 存在, 且不唯一不唯一

C. 存在, 可能不唯一

D. 无法确定是否存在

【答案】C 。

【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,

如图的邻接矩阵为

在两个拓扑序列。

第 2 页，共 54 页 , 则存

4． 已知三叉树T 中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T 的带权(外部) 路径长度最小是 （ ）

A.27

B.46

C.54

D.56

【答案】B

【解析】利用三叉树的6个叶子结点的权构建最小带权生成树, 最小的带权路径长度为

5． 假定一台计算机的显示存储器用DRAM 芯片实现, 若要求显示分辨率为1600x1200, 颜色深度

为24位, 帧频为85Hz , 显存总带宽的50%用来刷新屏幕, 则需要的显存总带宽至少约为（ ）。

A.245Mbps

B.979Mbps

C.1958Mbps

D.7834Mbps

【答案】D

【解析】显存的容量＝分辨率×色深，带宽＝分辨率×色深×帧频，考虑到的时间用来刷新屏幕，故显存总带宽应加倍. 所以需要的显存总带宽至少约为:1600×l200×24×85×2＝7834Mbps.

6． 已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.

【答案】D

m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】

元素依次进行比较, 比较的次数是m 和n 中的最大值。

7． 若需在的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C

【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、堆排序、shell 排序。时间复杂度平均为

的有:归并排序、堆排序、shell 排序、快速排序。

第 3 页，共 54 页

8． 假定变量i 、f 和d 的数据类型分为int 、float 和double(int用补码表示, float 和double 分别用IEEE754单精度和双精度浮点数格式表示) , 已知

器中执行下列关系表达式, 则结果为“真”的是（ ）。

(Ⅰ)

(Ⅱ)

(Ⅲ)

(Ⅳ)

A. 仅Ⅰ和Ⅱ

B. 仅Ⅰ和Ⅲ

C. 仅Ⅱ和Ⅲ

D. 仅Ⅲ和Ⅳ

【答案】B

【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。Ⅱ中, f 的数据类型从float 转换为int 时, 小数点后面4位会丢失, 故Ⅱ的结果不为真; Ⅳ中, d+f时需要对阶, 对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故Ⅳ的结果也不为真。

Ⅰ和Ⅱ进行数据类型的转换的时候并没有改变其值。

9． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）

A.1和5

B.2和4

C.4和2

D.5和1

【答案】B

【解析】入队操作的主要步骤:rear ＝(rear+1)%6，加入一个后，rear ＝(0+1)%6＝1，再加入一个后，rear ＝(1+1)%6＝2。出队操作的主要步骤:front ＝(front+1)%6。删除一个后，front ＝(3+1)%6＝4。

10．设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。

A.BA+141

B.BA+180

C.BA+222

D.BA+225

【答案】B

【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储

第 4 页，共 54 页 。若在32位机