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

一、单项选择题

1． 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A. B. C. D.

【答案】C

【解析】快速排序将数据划分成两部分，其中一部分关键字比另一部分关键字小。

2． 已知字符串S 为“abaabaabacacaabaabcc ”, 模式串t 为“abaabc ”, 采用KMP 算法进行匹配, 第一次出现“失配”(

A.i=l, j=0

B.i=5, j=0

C.i=5, j=2

D.i=6, j=2

【答案】C

【解析】模式匹配(KMP)算法对普通的暴力匹配的改进在于:每当匹配过程中匹配失败时, 主串(本题为S) 的指针(i)不需要回溯, 而是利用已经得到的“部分匹配”的结果将模式串(t)向右“滑动”尽可能远的一段距离后, 继续进行比较。模式串“滑动”的距离是由模式串(t)本身决定的, 即t

的子串

中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”, 其相等且最长的前后缀为“ab”, 一次下一个j=2。

3． 已知广义表LS ＝((a，b ，c) ，(d，e ，f)) ， 用head 和tail 数取出LS 中原子e 的运算是（ ）。

A.head(tail(LS))

B.tail(head(LS))

C.head(tail(head(tail(LS)))

D.head(tail(tail(head(LS))))

【答案】C

【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。tail(LS)得到((d，e ，f)) ，head(tail(LS))得到(d，e ，f)tail(head(tail(LS)))得到(e，f) ，head(tail(head(tail(LS))) 得到e 。

) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是（ ）。

4． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双链表

D. 仅有尾指针的单循环链表

【答案】D

【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。

5． 在无噪声情况下，若某通信链路的带宽为3kHz ，采用4个相位，每个相位具有4种振幅的QAM 调制技术，则该通信链路的最大数据传输速率是（ ）.

A.12kbps

B.24kbps

C.48kbps

D.96kbps

【答案】B

【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理. 解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率＝2×3×log2(4×4) ＝6×4＝24kbps.

6． 当字符序列 作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。

A.4个

B.5个

C.3个

D.6个

图

【答案】C

【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ，有两种结果

和，若首字符为，

则只有一种结果

因此总共有3种结果。

7． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A.(2，5，12，16)26(60，32，72)

B.(5，16，2，12)28(60，32，72)

C.(2，16，12，5)28(60，32，72)

D.(5，16，2，12)28(32，60，72)

【答案】B

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

第一次比较:28比72小，不交换;

第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;

第三次比较:16比28小，不交换；

第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;

第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;

第六次比较:28比12大，不交换；

第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;

一次划分结束。

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

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

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

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

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

【答案】C

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

9． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。

A. 对称矩阵

B. 稀疏矩阵

C. 三角矩阵

D. —般矩阵

【答案】C

【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图

中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。