2014年计算机考研专业课408统考真题模拟考试

科目组合

数据结构 、计算机组成原理 、操作系统 、计算机网络

: :
题目数量 13
第1题 数据结构 单选题

下列程序段的时间复杂度是( )。

count =0;
for(k = 1; k <= n; k *= 2)
        for(j = 1; j <= n; j++)
            count++;

A. O(log⁡n)

B. O(n)

C. O(nlog⁡n)

D. O(n^2)


第2题 数据结构 单选题

假设栈初始为空,将中缀表达式 a/b+(c∗d−e∗f)/g 转换为等价的后缀表达式的过程中,当扫描到 f 时,栈中的元素依次是( )。

A. +(∗−

B. +(−∗

C. /+(∗−∗

D. /+−∗


第3题 数据结构 单选题

循环队列放在一维数组 A[0..M-1] 中,end1指向队头元素,end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳 M-1 个元素。初始时为空。下列判断队空和队满的条件中,正确的是( )。

A. 队空:end1 == end2; 队满:end1 == (end2 + 1) mod M

B. 队空:end1 == end2; 队满:end2 == (end1 + 1) mod (M - 1)

C. 队空:end1 == (end1 + 1) mod M; 队满:end1 == (end2 + 1) mod M

D. 队空:end1 == (end2 + 1) mod M; 队满:end2 == (end1 + 1) mod (M - 1)


第4题 数据结构 单选题

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

A. e、c

B. e、a

C. d、c

D. b、a


第5题 数据结构 单选题

将森林F转换为对应的二叉树T,F中叶子的个数等于( )。

A. T中叶结点的个数

B. T中度为1的结点个数

C. T中左孩子指针为空的结点个数

D. T中右孩子指针为空的结点个数


第6题 数据结构 单选题

5个字符有如下4种编码方案,不是前缀编码的是( )。

A. 01, 0000, 0001, 001, 1

B. 011, 000, 001, 010, 1

C. 000, 001, 010, 011, 100

D. 0, 100, 110, 1110, 1100


第7题 数据结构 单选题

对如下所示的有向图进行拓扑排序,得到的拓扑序列可能是()

A.3,1,2,4,5,6

B.3,1,2,4,6,5

C.3,1,4,2,5,6

D.3,1,4,2,6,5


第8题 数据结构 单选题

用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象,下列选项中, 会受堆积现象直接影响的是()

A.存储效率

B.散列函数

C.装填(装载)因子

D.平均查找长度


第9题 数据结构 单选题

在一棵具有 15 个关键字的 4 阶 B 树中,含关键字的结点个数最多是()

A.5

B.6

C.10

D.15


第10题 数据结构 单选题

用希尔排序方法对一个数据序列进行排序时,若第1趟排序结果为9,1,4,13,7,8,20,23,15,则该趟排序采用的增量(间隔)可能是()

A.2

B.3

C.4

D.5


第11题 数据结构 单选题

下列选项中,不可能是快速排序第2趟排序结果的是()

A.2,3,5,4,6,7,9

B.2,7,5,6,4,3,9

C.3,2,5,4,7,6,9

D.4,2,3,5,7,6,9


第12题 数据结构 综合题

二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为:

其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法,要求:

⑴ 给出算法的基本设计思想;

⑵ 使用C或C++语言,给出二叉树结点的数据类型定义;

⑶ 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。


第13题 数据结构 综合题

某网络中的路由器运行OSPF路由协议,题42表是路由器R1维护的主要链路状态信息(LSI),题42图是根据题42表的接口名构造出来的网络拓扑。

请回答下列问题。

⑴ 本题中的网络可抽象为数据结构中的哪种结构?

⑵ 针对题42表中的内容,设计合理的链式存储结构,以保存题42表中的链路状态信息(LSI)。要求给出链式存储结构的数据定义,并画出对应题42表的链式存储结构示意图(示意图中仅以ID标识结点)。

⑶ 按照迪杰斯特拉(Dijkstra)算法的策略,依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。