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

一、单项选择题

1． 下列关于最小生成树的叙述中, 正确的是（ ）。

Ⅰ. 最小生成树的代价唯一

Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同

IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅳ

【答案】A 。

【解析】当图中存在相同权值的边时, 其最小生成树可能是不唯一的, 但最小生成树的代价一定是相同的, 所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路, 所以说法Ⅱ错误。

当某个顶点有权值相同的边, 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同, 所以说法Ⅲ错误。当最小生成树不唯一时, 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树可能相同, 也可能不同, 所以说法Ⅳ错误。由此可得出正确答案。

2． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）.

A. 时间片轮转调度算法

B. 短进程优先调度算法

C. 先来先服务调度算法

D. 高响应比优先调度算法

【答案】D

【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间. 最高响应比优先调度算法是最先执行响应比最高的进程(响应比＝1＋等待时间/估计运行时间). 该算法综合了先来先服务(FCFS)和短作业优先(SJF)算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短.SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间.

3． 用邻接表存储图所用的空间大小（ ）。

A. 与图的顶点数和边数都有关

B. 只与图的边数有关

C. 只与图的顶点数有关

D. 与边数的平方有关

【答案】A

【解析】邻接表就是对图G 中的每个顶点建立一个单链表，第i 个单链表中的结点表示依附于顶点的边，这个单链表就称为顶点的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。

4． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。

A.CSMA

B.CDMA C. D.

【答案】D

【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。

5． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。

A. 串

B. 树

C. 广义表

D. 栈

【答案】C

【解析】串、树、桟中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。

6． float 型整数据常用IEEE754单精度浮点格式表示, 假设两个float 型变量x 和Y 分别在32为寄存器f 1和f 2中, 若(f1) =CC900000H, (f2) =BOCOOOOOH, 则x 和y 之间的关系为:（ ）

A. x

B. x

C. x>y且符号相同

D. x>y且符号不同

【答案】A

【解析】两个数对应的IEEE754的标准形式为;

将IEEE754单精度形式的二进制转化为浮点数公式为

由于f1, f2的符号位都是1, 所以f1, f2符号相同, 而阶码上f1>f2, 所以f1>f2, 所以f1的绝对值比f2大, 而他们都是负数, 所以f1

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

A. 队空:endl==end2; 队满:endl==(end2+l)modM

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

C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM

D. 队空:

【答案】A

【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。

8． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。

A.24, 10, 5和24, 10, 7

B.24, 10, 5和24, 12, 7

C.24, 10, 10和24, 14, 11

D.24, 10, 5和24, 14, 6

【答案】D

【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。

9． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A.

B.O(1)

C.O(n) D.

队满: