2021 年四川大学874真题答案

1、2021 年四川大学874真题答案2021 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，就

2、是n-2+16.C解析：n0+n1+n2=666,n0=n2+1;推出2n2+n1+1=666,完全二叉树为1结点数最多有一个。所以n1=1，n2=332，n0=3337.A解析：排除法，对A显然368.D解析:AC排除，因为AC只有中序排序有序，题目要求从任意节点到根节点，又因为哈夫曼树的非叶节点不是关键字。选D9.D10.B解析：树的先序遍历序列与其对应的二叉树的先序遍历序列相同，书的后续遍历预期对应的二叉树的中序遍历相同11.B解析：因为BFS只能解决不带权的单源不带权最短路径问题，所以权值相同可以看成无权12.B解析：题目问题：没有。如下图，按照拓扑排序算法解决即可13.A解析：克鲁斯

3、卡尔算法，依次将最小且不构成回路的边加入到集合中14.A解析：画出散列表，用除留余数法，算出各个地址，然后伪随机序列解决冲突，例如H0（70）=5，冲突；H1（70）=（70+5）%13=10，冲突；H2(70)=(70+8)%13=0,冲突；H3（70）=（70+3）%13=8，存入815.C解析：直接用公式，n0=0，n1=1，n2=2, N h=N h-1+N h-2+1,于是可以求出N3=4，所以总的结点数为716.D解析：显然，基数排序和初始序列无关，因为基数排序不是基于比较的排序算法17.A解析：对于多元素排序选出前几个使用堆排序最佳二、综合应用题18.如图所示，（1）0，01，0

4、10三个编码以及以0101开头的是不可能有的2）以1，00，011，0100开头的一定有。19.int count(AdjList g, int k) int count = 0;for(i=0;iif(i!= k)p = gi. 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(

5、node-rchild);return lHrH ? 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控制，进程可以直接读写一个外部

6、设备。5. D解析：text段通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读(某些架构也允许代码段为可写，即允许修改程序)。data段通常是指用来存放程序中已初始化的全局变量的块内存区域。数据段属于静态内存分配。bss (Block Started by Symbol)段通常是指用来存放程序中未初始化的全局变量的一块内存区域。属于静态内存分配。堆(heap)是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。6.解析：题目有歧义。假设原来没有快表，且2级页表假设访问内存一次时间为t原来：3t（无快表，访问3次

7、内存）现在：0.75t+0.25*3t=1.5td选项改为大约是原来0.5倍7.D解析：印刷错误，23分开块号应该为2和3，块大小75，55。地址为150和250。因为分配最大空闲块给进程p，因此为最差适应法。8.A解析：由题意，逻辑地址为32位，虚拟空间大小为232b，又因为每页大小为4kb(212)，所以总的页表项有2（32-12）个。物理地址36位为干扰选项。9.B解析：A选项进程切换不会影响页跟块的映射关系，c选项访问权限项应该在pcb中，不应该在页表中。D页表10.A解析：时间片用完应降低降低进程优先权，然后换入优先权更高的进程进入就绪队列11.B解析：当前值为1表示可用资源为1，等

8、待为012.B解析：以行为主序，一页存50个数，存满一行缺一次页，就会产生50次缺页。13.B解析：题意意思是只能顺序访问磁块，所有只有链式结构符合题意二综合题1.每块可以装的地址项：256/4=64直接地址：4*256一级间接索引：2*64*256二级简介索引：2*64*64*265最后加起来等于21309442.每页表项数为4kb/4b=210，64虚地址共有264/4kb=252页，最高层页表占一项，所以最高层的页表项不超过210，53.信号量s表示球筐内还可以放的球数，wb表示球筐内的白球数，bb表示球筐内的黑球数，m限制只有一个操作。计算机网络一选择题1. C解析：ARPNET出现在

9、web之前，c错误2. D解析：生成多项式位5位，所以在发送序列4个0，然后用模二运算除以11011，求出余数发到初始序列后，即为发送序列3. B解析：DF为1不允许分片，超过MTU丢弃分组，需要发送ICMP差错报文，即错误4D解析：A类地址前8位为网络号，后24位为主机号，700+4505C解析：概念题解析略，TCP通过差错检测和纠正方法来保证可靠性6. C解析：当两个IP地址不在同一网络下，需要通过路由器进行通信。因为子网掩码位144=10010000，因为子网掩码,化为点分十进制位11111111.11111111.11000000.000000,所以前18位位

10、网络号，所以只需要观察4个选项中前18位和题给的主机ip地址是否匹配即可7. D解析：因为题给交换机是全双工的，需要乘2（算两个端口），所以24*100M*2+2*1000M*2 = 8.8G8. D概念题，解析略9. A解析：下层为上层提供服务二、综合应用题1.2.解析1）数据量=3000+200=3200bit传输时延=3200bit/1Mbps=3.2ms四个路由器加源主机传送有5次传输，传播时延=1ms*5=5ms（5段链路）总时延=3.2*5+5=21ms2）数据量：3000bit+100bit=3100bit传输时延：3100bit/1Mbps=3.1ms，四个路由器加源主机传送有5次传输，传播时延=1ms*5=5ms（5段链路）虚电路建立时