408计算机专业基础综合试题及答案_408计算机专业基础综合考试练习题P56-新东方在线职业题库

5.若森林F有15条边、25个结点，则F包含树的个数是
A.8
B.9
C.10
D.11

47.（7分）某公司网络如题47图所示。IP地址空间192.168.1.0/24 被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP 地址，销售部子网的 MTU=1500B，技术部子网的 MTU=800B。
请回答下列问题。
（1）销售部子网的广播地址是什么?技术部子网的子网地址是什么?若每个主机仅分配一个IP 地址，则技术部子网还可以连接多少台主机?
（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口 F1转发该IP 分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP 分片封装数据的字节数是多少?至少需要分为几个分片?每个分片的片偏移量是多少?

6.下列选项中，不是下图深度优先搜索序列的是
A.V1,V5,V4,V3,V2
B.V1,V3,V2,V5,V4
C.V1,V2,V5,V4,V3
D.V1,V2,V3,V4,V5

41.（13分）设线性表L=（a1，a2，a3…，an-2，an-1，an）采用带头结点的单链表保存，链表中的结点定义如下：
typedef struct node
{ int data;
struct node*next;
}NODE;
请设计一个空间复杂度为O（1）且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=（a1，an，a2，an-1，a3，an-2，...）。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。

7. 若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n×e)

42.（10分）请设计一个队列，要求满足∶①初始时队列为空;②入队时，允许增加队列占用空间;③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减;④入队操作和出队操作的时间复杂度始终保持为O（1）。请回答下列问题：
（1）该队列是应选择链式存储结构，还是应选择顺序存储结构?
（2）画出队列的初始状态，并给出判断队空和队满的条件。
（3）画出第一个元素入队后的队列状态。
（4）给出入队操作和出队操作的基本过程。

8. 使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是
A.5,2,3,4,6
B.5,2,3,6,4
C.5,2,4,3,6
D.5,2,6,3,4

43.（8分）有n（n≥3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m≥1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，日止出现死锁现象。请使用信号量的 P、V 操作[wait()、signal()操作]描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

9.在有n（n>1000）个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。
k=-0;
while（kif（kelse if（k-1else if（k-2else查找失败;
本算法与折半查找算法相比，有可能具有更少比较次数的情形是
A.当x不在数组中
B.当x接近数组开头处
C.当x接近数组结尾处
D.当x位于数组中间位置

44.（7分）某计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有 200 个扇区，扇区大小为512B。文件系统的每个簇包含2个扇区。请回答下列问题：
（1）磁盘的容量是多少?
（2）假设磁头在 85号柱面上，此时有 4个磁盘访问请求，簇号分别为100260、60 005、101660和110560。若采用最短寻道时间优先（SSTF）调度算法，则系统访问簇的先后次序是什么?
（3）第 100 530簇在磁盘上的物理地址是什么?将簇号转换成磁盘物理地址的过程是由I/O 系统的什么程序完成的?

快速查题-408计算机专业基础综合试题