9.28 - 每日一题 - 408

数据结构

1 下列说法正确的是_____(河海大学)

A 已知一颗二叉树的前序遍历顺序和后序遍历顺序，可以唯一确定这棵二叉树

B 将一个递归算法改为非递归算法时，通常使用队列作为辅助结构

C 快速排序和堆排序都是不稳定排序

D 二分查找法，平均时间复杂度为O(n)

答案：C

解析：A：已知一颗二叉树的前序遍历顺序和后序遍历顺序不能唯一确定这棵二叉树，确定一颗二叉树必须知道这一颗二叉树的中序遍历，知道前序中序或者知道后序和中序才可以确定这颗二叉树；

B：递归算法改为非递归算法不是采用队列做辅助结构，而是栈；

D：二分查找平均时间复杂度是O(logn)，只有在最坏的情况下才是O(n)。

拓展：
对于一棵二叉树，我们可以前序、中序、后序地进行遍历。
前序/后序+中序——>唯一确定一棵二叉树；而前序+后序则不能唯一确定一棵二叉树；

前序：根-左-右
中序：左-根-右
后序：左-右-根

中序和后序确定的是父子间的关系，我们只能知道左-右为根的孩子，而不能确定左是否为根的左孩子，右是否为根的右孩子；而中序确定了左为左孩子，右为右孩子，但不能确定根是否为它们的父节点。所以，给定前序/后序+中序，我们就知道根为父节点，左为左孩子，右为右孩子，从而就能唯一的确定一棵二叉树。

计算机网络

2 某自治系统内采用 RIP 协议，若该自治系统内的路由器 R1 收到其邻居路由器 R2 的距离矢量中包含的信 息，则可能得出的结论是_____(杭州电子科技大学)

A.R1 不能通过R2到达net1

B.R1 可以通过R2到达net1，代价是17

C.R2 可以通过R1到达net1，代价是17

D.R2 可以到达net1，代价是16

答案：A

解析：对于RIP来说，一条代价超过了15跳的路径都被认为不可达。

拓展：
路由信息协议(RIP) 是一种距离矢量协议，这表示它根据跳数来判断到达目标的最佳路由。
RIP路由器每30秒广播一次更新消息，它还可以要求立即更新。像其他距离矢量协议一样，当网络处于平衡状态时，RIP工作效果最好。如果路由器的数量变得非常大，比较缓慢的路由表汇集就可能导致问题。出于这个原因，RIP设置了从第一台路由器到达目标的最大跳数限制，其值是15。这个规定限制了路由器的数量，但如果以层级方式组织路由器，15跳范围之内也可以组成大型网络。

操作系统

3 已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执 行时主存中没有页面。若只给作业分配2个物理块，当采用FIFO页面淘 汰算法时缺页率为_____(华东师范大学)

A 7/11

B 8/11

C 9/11

D 10/11

答案：C

解析：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下表所示：

计算机组成原理

4 若某计算机数据线、地址线均是8bit, 有一条相对寻址的无条件转移指令存千内存的20H单元中，指令给出的位移量D =00010101 B, 设该指令占用2个字节,则该指令执行结束时PC的内容为______(哈尔滨工业大学)

A 20H

B 35H

C 37H

D 22H

答案：C

解析：取该指令时， PC 的内容为20H 。

转移地址＝

PC+2+D=00100000+00000010+00010101=00110111B

该指令执行结束时PC的内容为00110111B(37H) 。

当前所有题目均来自@王道在线公众号，其中对部分题目解析进行了补充说明，
如有问题或错漏烦请评论告知，感谢支持