目录

2017年安徽理工大学软件工程841数据结构考研导师圈点必考题汇编（一） (2)

2017年安徽理工大学软件工程841数据结构考研导师圈点必考题汇编（二） (15)

2017年安徽理工大学软件工程841数据结构考研导师圈点必考题汇编（三） (29)

2017年安徽理工大学软件工程841数据结构考研导师圈点必考题汇编（四） (42)

2017年安徽理工大学软件工程841数据结构考研导师圈点必考题汇编（五） (55)

第1 页，共68 页

第 2 页，共 68 页 2017年安徽理工大学软件工程841数据结构考研导师圈点必考题汇编（一） 说明：①本资料为VIP 学员内部使用，整理汇编了历届导师圈点的重点试题及常考试题。

——————————————————————————————————————————

一、选择题

1． 就平均性能而言，目前最好的内排序方法是（ ）排序法。

A.起泡

B.希尔插入

C.交换

D.快速

【答案】D

【解析】快速排序的平均时间复杂度是所需要的辅助存储为虽然堆排序的时间复杂度也是所需要的辅助存储为

看似堆排序比快速排序的性能好，

但是需要注意仅仅表示的是一个量级，

比如

和

的量级都为之所以说快排最好，是在综合考虑的情况下。

2． 主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1

个大小为

的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该

报文传输所需的总时间分别为（ ）

A.800ms> 1600ms

B.801ms 、1600ms

C.1600ms 、800ms

D.1600ms 、801ms

【答案】D

【解析】不进行分组时，发送一个报文的时延是

在接收端接收此报文件的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是

接收一个报文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801 ms 。

3． 下列关于银行家算法的叙述中，正确的是（ ）

A.银行家算法可以预防死锁

B.当系统处于安全状态时，系统中一定无死锁进程

C.当系统处于不安全状态时，系统中一定会出现死锁进程

D.银行家算法破坏了死锁必要条件中的“请求和保持”条件

【答案】B

【解析】银行家算法是避免死锁的方法。利用银行家算法，系统处于安全状态时没有死锁进

第 3 页，共 68 页 程，故答案选B 。

4． TCP/IP 参考模型的网络层提供的是（ ）。

A.无连接不可靠的数据报服务

B.无连接可靠的数据报服务

C.有连接不可靠的虚电路服务

D.有连接可靠的虚电路服务

【答案】A

【解析】TCP/IP 的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务，因此答案是A 。

5． 现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。

A.根节点的度一定为2

B.树中最小元素一定是叶节点

C.最后插入的元素一定是叶节点

D.树中最大元素一定是无左子树

【答案】D

【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：①中序遍历左子树；②访问根节点；③中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。

6． 某数采用IEEE754单精度浮点数格式表示为C640 0000H ,则该数的值是（ ）

A.

B.

C.

D.

【答案】A

【解析】

IEEE754单精度浮点数格式为C640 0000H 表示为二进制格式为1100 0110 0100 0000 0000 0000 0000 0000,转换为标准的格式为：

因此，浮点数的值为

.

第 4 页，共 68 页 7． 采用简单选择排序，比较次数与移动次数分别为（ ）。

【答案】C

【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比较的次数为

8．

对

个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是

（ ）。

A.该树一定是一棵完全二叉树

B.树中一定没有度为1的结点

C.树中两个权值最小的结点一定是兄弟结点

D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于下一层任一结点的权值。

9． 以太网交换机进行转发决策时使用的PDU 地址是（ ）。

A.目的物理地址

B.目的IP 地址

C.源物理地址

D.源IP 地址

【答案】A

【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息（源结点的MAC 地址、目的结点的MAC 地址）,就会得到与每个端口所连接结点的MAC 地址,并在交换机的内部建立一个“端口-MAC 地址”映射表。建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为A 。