科目组合

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

下列程序段的时间复杂度是（ ）。

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)

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

A. +(∗−

B. +(−∗

C. /+(∗−∗

D. /+−∗

循环队列放在一维数组 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)

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

A. e、c

B. e、a

C. d、c

D. b、a

将森林F转换为对应的二叉树T，F中叶子的个数等于（ ）。

A. T中叶结点的个数

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

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

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

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

对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）

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

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

A．存储效率

B．散列函数

C．装填(装载)因子

D．平均查找长度

在一棵具有 15 个关键字的 4 阶 B 树中，含关键字的结点个数最多是（）

A．5

B．6

C．10

D．15

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

A．2

B．3

C．4

D．5

下列选项中，不可能是快速排序第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

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

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

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

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

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

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

请回答下列问题。

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

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

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