2018 874

数据结构：

选择题

1.D 详解略

2.C

解析：外层循环每执行一次，内层循环执行logn次，又因为外层循环n次，因此总的次数应该是nlogn次

3.B

解析：因为顺序存储具有随机存取（随机查找）的优点，缺点是插入和删除需要移动大量元素，对链式存储来说，插入删除比较快，而对于查处需要遍历，因此链式不一定说比顺序存储块

4.D

解析：因为删除节点必须前一个结点，这个就可以排除单链表。于是abc排除，选D。（拓展一下看王道书题目）

5.B

解析：n第一个出栈，n前面已经入栈，栈内元素是1---n-1，出栈逆序，所以第i个元素就是n-i+1，可以举例第2个出应该是n-1，就是n-2+1

6.C

解析：n0+n1+n2=666,n0=n2+1;推出2n2+n1+1=666,完全二叉树为1结点数最多有一个。

所以n1=1，n2=332，n0=333

7.A

解析：排除法，对A显然36<86,94>86,不可能出现在86同一个分支里，故选A

8.D

解析:AC排除，因为AC只有中序排序有序，题目要求从任意节点到根节点，又因为哈夫曼树的非叶节点不是关键字。选D

9.D

10.B

解析：树的先序遍历序列与其对应的二叉树的先序遍历序列相同，书的后续遍历预期对应的二叉树的中序遍历相同

11.B

解析：因为BFS只能解决不带权的单源不带权最短路径问题，所以权值相同可以看成无权

12.B

解析：题目问题：没有,v6>。如下图，按照拓扑排序算法解决即可

13.A

解析：克鲁斯卡尔算法，依次将最小且不构成回路的边加入到集合中

14.A

解析：画出散列表，用除留余数法，算出各个地址，然后伪随机序列解决冲突，例如H0（70）=5，冲突；H1（70）=（70+5）%13=10，冲突；H2(70)=(70+8)%13=0,冲突；H3（70）=（70+3）%13=8，存入8

15.C

解析：直接用公式，n0=0，n1=1，n2=2, Nh=Nh-1+Nh-2+1,于是可以求出N3=4，所以总的结点数为7

16.D

解析：显然，基数排序和初始序列无关，因为基数排序不是基于比较的排序算法

17.A

解析：对于多元素排序选出前几个使用堆排序最佳

二、综合应用题

18.

如图所示，

（1）0，01，010三个编码以及以0101开头的是不可能有的

2）以1，00，011，0100开头的一定有。

19.

int count(AdjList g, int k) {

int count = 0;

for(i=0;i<=n-l;i++)

if(i!= k){

p = g[i]. firstarc;

while (p) {

If (p->adjvex == k)

count++;

p = p->next;

}

}

return count;

}

20.

解析：int deepesHeight(TreeNode node){

If(node==null) return 0;

Int lH = deepesHeight(node->lchild);

Int rH = deepesHeight(node-rchild);

return lH>rH ? lH+1 : rH+1;

}

int Balance(TreeNode node){

node->bf = deepesHeight(noed->lchild)- deepesHeight(node->rchild)

}

操作系统

1. B

解析：可重入代码是一种允许多个进程同时访问的代码，为了使各个进程所执行的代码完全相同，故不允许任何进程对其进行修改。

2. D

解析：在某进程中调用的阻塞原语，则必须在与之相合作的另一进程或其他相关进程中安排唤醒原语，以能唤醒阻塞进程。

3. B

解析：如图

4. A

解析：概念题，直接内存访问可以不需要cpu控制，进程可以直接读写一个外部设备。

5. D

解析： text段通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读(某些架构也允许代码段为可写，即允许修改程序)。data段通常是指用来存放程序中已初始化的全局变量的块内存区域。数据段属于静态内存分配。bss (Block Started by Symbol)段通常是指用来存放程序中未初始化的全局变量的一块内存区域。属于静态内存分配。 堆(heap)是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。

6.

解析：题目有歧义。假设原来没有快表，且2级页表

假设访问内存一次时间为t

原来：3t（无快表，访问3次内存）

现在：0.75t+0.25*3t=1.5t

d选项改为大约是原来0.5倍

7.D

解析：印刷错误，23分开块号应该为2和3，块大小75，55。地址为150和250。因为分配最大空闲块给进程p，因此为最差适应法。

8.A

解析：由题意，逻辑地址为32位，虚拟空间大小为2^32b，又因为每页大小为4kb(2^12)，所以总的页表项有2^（32-12）个。物理地址36位为干扰选项。

9.B

解析：A选项进程切换不会影响页跟块的映射关系，c选项访问权限项应该在pcb中，不应该在页表中。D页表

10.A

解析：时间片用完应降低降低进程优先权，然后换入优先权更高的进程进入就绪队列

11.B

解析：当前值为1表示可用资源为1，等待为0

12.B

解析：以行为主序，一页存50个数，存满一行缺一次页，就会产生50次缺页。

13.B

解析：题意意思是只能顺序访问磁块，所有只有链式结构符合题意

二．综合题

·1.

每块可以装的地址项：256/4=64

直接地址：4*256

一级间接索引：2*64*256二级简介索引：2*64*64*265

最后加起来等于2130944

2.每页表项数为4kb/4b=2^10，64虚地址共有2^64/4kb=2^52页，最高层页表占一项，所以最高层的页表项不超过2^10，5<52/10=5.2<6，所以就采用6层

3.

信号量s表示球筐内还可以放的球数，wb表示球筐内的白球数，bb表示球筐内的黑球数，m限制只有一个操作。

Semaphore S=2 wb=0，bb=0，m=1

计算机网络

一． 选择题

1. C

解析：ARPNET出现在web之前，c错误

2. D

解析：生成多项式位5位，所以在发送序列4个0，然后用模二运算除以11011，求出余数发到初始序列后，即为发送序列

3. B

解析：DF为1不允许分片，超过MTU丢弃分组，需要发送ICMP差错报文，即错误

4．D

解析：A类地址前8位为网络号，后24位为主机号，700+450<2^11=2048所以11位主机号就可以了，同时2^13-2=8190>4092满足题意，所以共需8+11=19位满足题意

5．C

解析：概念题解析略，TCP通过差错检测和纠正方法来保证可靠性

6. C

解析：当两个IP地址不在同一网络下，需要通过路由器进行通信。

因为子网掩码位144=10010000，因为子网掩码255.255.192.0,化为点分十进制位11111111.11111111.11000000.000000,所以前18位位网络号，所以只需要观察4个选项中前18位和题给的主机ip地址是否匹配即可

7. D

解析：因为题给 交换机是全双工的，需要乘2（算两个端口），所以24*100M*2+2*1000M*2 = 8.8G

8. D

概念题，解析略

9. A

解析：下层为上层提供服务

二、综合应用题

1.

2.解析

1）数据量=3000+200=3200bit

传输时延=3200bit/1Mbps=3.2ms

四个路由器加源主机传送有5次传输，传播时延=1ms*5=5ms（5段链路）

总时延=3.2*5+5=21ms

2）数据量：3000bit+100bit=3100bit

传输时延：3100bit/1Mbps=3.1ms，

四个路由器加源主机传送有5次传输，传播时延=1ms*5=5ms（5段链路）

虚电路建立时间：8ms

总时延=3.1*5+5ms+8ms=28.5ms

3） 数据量：3000bit+200bit = 3200bit

传输时延：3200bit/1Mbps = 33ms 四个路由器加源主机传送，5次传输

传播时延：1ms*5 = 5ms，有五段链路

电路建立时间：4ms

总时延：3.2ms*5+5ms+4ms = 25ms