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

2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素a，b，c，d，e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。
A.b,a,c,d,e
B.d,b,a,c, e
C.d,b, c, a, e
D.e, c,b, a,d

45.（8分）某银行提供 1个服务窗口和 10个供顾客等待的座位。顾客到达银行时，若有空应位。川取号村 上领取—一个号。等待叫号。取号村每次仅允译—一行顾客使用。当马营员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下∶
Cobegin
{
Proccss 顾客 i
{
从取号机获取一个号码;
等待叫号;
获取服务;
}
Process营业员
{
While(TRUE)
{
叫号;
为顾客服务;
}
}
} coend
请添加必要的信号量和P、V（或 wait（）、signal（））操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

4.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。
A.13、48
B.24、48
C.24、53
D.24、90

46.（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题∶
（1）在连续、链式、素引二种文件的数据块组织方式中。 哪种更合活? 要求说明理由。为定位文件数据块，需要在 FCB中设计哪些相关描述字段?
（2）为快速找到文件，对于 FCB，是集中存储好，还是与对应的文件数据块连续存储好?要求说明理由。

5.在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ）。
A.41
B.82
C.113
D.122

47.（9分）某主机的 MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100（私有地址）。题47a 图是网络拓扑，题47b 图是该主机进行Web请求的一个以太网数据帧前80字节的十六进制及ASCII码内容。
请参考图中的数据回答以下问题∶
（1）Web服务器的 IP地址是什么?该主机的默认网关的MAC地址是什么?
（2） 该主机在构造题 47b 图的数据帧时，使用什么协议确定目的 MIAC地址? 封装该协议请求报文的以太网帧的目的MAC地址是什么?
（3）假设 HTTP/1.1协议以持续的非流水线方式工作，一次请求-响应时间为RTT，rfc.Html 页面引用了5个 JPEG 小图像，则从发出题47b 图中的Web 请求开始到浏览器收到全部内容为上，需要经过多少个RTT?
（4）该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段?注∶以太网数据帧结构和IP分组头结构分别如题47c 图、题47d图所示。

6.对n（n≥2）个权值均不相同的字符构成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是（ ）。
A.该树一定是一棵完全二叉树
B.树中一定没有度为1的结点
C.树中两个权值最小的结点一定是兄弟结点
D.树中任一非叶结点的权值一定不小于下一层任一结点的权值

41.设有6个有序表 A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
1）给出完整的合并过程，并求出最坏情况下比较的总次数。
2）根据你的合并过程，描述N（N≥2）个不等长升序表的合并策略，并说明理由。

7.若无向图G=（V，E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。
A.6
B.15
C.16
D.21

42.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如，"loading"和"being"的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为Data、next，请设计一个时间上尽可能高效的算法，找出由 str1和 str2所指向两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求∶
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++或 Java 语言描述算法，关键之处给出注释。
3）说明你所设计算法的时间复杂度。