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

一、单项选择题

1． 程序段

与对换；

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

A.D(n)

B.O(nlogn)

C.O(n3)

D.O(n2)

【答案】D

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

2． 若对如下的二叉树进行中序线索化, 则结点x 的左、右线索指向的结点分别是（ ）

A.e , c

B.e , a

C.d , c

D.b , a

【答案】D

【解析】此二叉树的中序遍历序列为:debxac , 由于节点x 左右孩子都为空, 所有进行中序线索化时, 它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D

3． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。

A.O(1)

B.O(N)

C.O(N2) D.

【答案】B

【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定

关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。

4． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4

B.5

C.6

D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为

或》

5． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）

A.007.110.119.114.911.120.122

B.007, 110, 119, 114, 911, 122, 120

C.007, 110, 911, 114, 119, 120, 122

D.110, 120, 911, 122, 114, 007, 119

【答案】C

【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。

6． 在OSI 参考摸型中, 下列功能需由应用层的相邻层实现的是（ ）

A. 对话管理

B. 数据格式转换

C. 路由选择

D. 可靠数据传输

【答案】B

【解析】应用层的相邻层即为表示层, 表示层负责管理数据的压缩、加密与解密、格式装换等, 故答案为B 。

7． 以太网的MAC 协议提供的是（ ）。

A. 无连接不可靠服务

B. 无连接可靠服务

C. 有连接不可靠服务

D. 有连接可靠服务

【答案】A 。

【解析】考查以太网MAC 协议, 考虑到局域网信道质量好, 以太网采取了两项重要的措施以使通信更简洁:

①采用无连接的工作方式;

②不对发送的数据帧进行编号, 也不要求对方发回确认。

因此, 以太网提供的服务是不可靠的服务, 即尽最大努力交付, 差错的纠正由高层完成。

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

A.4个

B.5个

C.3个

D.6个

图

【答案】C

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

因此总共有3种结果。

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

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

B.

C.

D.

和，若首字符为，

则只有一种结果转换为等价后缀表达式的过程中,