计算机综合2021年真题.pdf

更新时间 2022-06-25 16:30:122021年真题408计算机学科专业基础研 P D F:Y a nP D F.C O M注：【】内为本题同类知识点历年考频信息一、选择题 本大题共40小题，共80分1.1 J已知头指针h指向一个带头结点的非空单循环链表，结点结构为如下图，其中ne xt是指向直接后继结点的指针，P是尾指针，q是临时指针现耍删除该链表的第一个元素，正确的语句序列是-OdatanextA.h-ne xt=h-ne xt-ne xt;q=h-ne xt;f re e(q);B.q=h-ne xt；h-ne xt=h-ne xt-ne xt；f re e(q)；C.q=h-ne xt；h-ne xt=q-ne xt；i f(p!=q)p=h；f re e(q)；D.q=h-ne xt;h-ne xt=q-ne xt;i f(p=q)p=h;f re e(q);2.2 已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作若Q的入队序列是1、2、3、4、5,则不能得到的出队序列是一 oA.5,4,3,1,2 B.5,3,1,2,4 C.4,2,1,3,5 D.4,1,3,2,53.4 已知二维数组A按行优先方式存储，每个元素占用1个存储单元。

若元素A 0 0 的存储地址是1 0 0,A 3 3 的存储地址是2 2 0,则元素A 5 5 的存储地址是 一A.2 95 B.3 0 0 C.3 0 1 D.3 0 64.3 某森林F对应的二叉树为T,若T的先序遍历序列是a,b,d,c,e,g,f,中序遍历序列是b,d,a,e,g,c,f,则F中树的棵数是一A.1 B.2 C.3 D.45.9若某二叉树有5个叶结点，其权值分别为1 0,1 2,1 6,2 1,3 0则其最小的带权路径长度(W P L)是一A.89 B.2 0 0 C.2 0 8 D.2 896.7 给定平衡二叉树如下图所示，插入关键字2 3后，根中的关键字是A.1 6 B.2 0 C.2 3 D.2 57.7 给定如下有向图，该图的拓扑有序序列的个数是第1页 共10页更新时间 2022-06-25 16:30:12A.1B.2C.3D.48.5 使用Dijkstra算法求下图中从顶点1 到其余各顶点的最短路径，将当前找到的从顶点1到顶点2,3,4,5 的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新 为 一A.26,3,14,6 B,25,3,14,6 C,21,3,14,6 D,15,3,14,69.8 在一棵高度为3 的 3 阶B树中，根为第1层，若第2 层中有4 个关键字，则该树的结点个数最多是。

A.11 B.10 C.9 D.810.4 设数组S=93,946,372,9,146,151,301,485,236,327,43,892）,采用最低位优先（LSD）基数排序将S 排列成升序序列第 1趟分配、收集后，元素372之前、之后紧邻的元素分别是A.43,892 B,236,301 C,301,892 D,485,30111.1 9 将关键字6,9,1,5,8,4,7依次插入到初始为空的大根堆H 中，得到的H是A.9,8,7,6,5,4,1 B.9,8,7,5,6,1,4C.9,8,7,5,6,4,1 D.9,6,7,5,8,4,112.3 2017年公布的全球超级计算机TOP 500排名中，我 国“神威太湖之光”超级计算机蝉联第一，其浮点运算速度为93.0146 PFLOPS,说明该计算机每秒钟内完成的浮点操作次数约为A.9.3x1013 次 B.9.3x1015 次 C.9.3 千万亿次 D.9.3 亿亿次13.已知带符号整数用补码表示，变量x,y,z 的机器数分别为FFFDH,FFDFH,7FFCH下列结论中,正确的是一A.若x,y 和 z 为无符号整数，则B.若x,y 和z 为无符号整数，则C.若x,y 和z 为带符号整数，则/D.若 x,y 和z 为带符号整数，则g 2 0,当 G 中度为奇数的顶点个数为不大于2 的偶数时，G 存在包含所有边且长度为|E|的 路 径(称 为 EL路径)。

设 图 G 采用邻接矩阵存储，类型定义如下：typedef struct /图的定义int numvertices,numEdges；/图中实际的项点数和边数char VerticesList MAXV;/顶点表MAXV 为已定义常量int Edge MAXV MAXV;/邻接矩阵MGraph；请设计算法intlsExistEL(MGraphG),判 断 G 是否存在EL路径，若存在，则返回1,否则返回0 o 要求：(1)给出算法的基本设计思想2)根据设计思想，采 用 C 或 C+语言描述算法，关键之处给出注释3)说明你所设计算法的时间复杂度和空间复杂度42.【8】(8 分)已知某排序算法如下：void cmpCountSort(int a ,int b ,int n)int i,j ,*count；count=(int*)malloc(sizeof(int)*n);/C+语言：count=new int n;for(i=0;in;i+)counti=0;for(i=0;in-l;i+)for(j=i+l;jn;j+)if(aiaj)countj+；else counti+;for(i=0;in;i+)bcounti-ai;free(count);/C+语言：delete count;请回答下列问题。

若有int a =25,-10,25,10,11,19),b6；则调用 cmpCountSort(a,b,6)后数组b 中的内容是外么？(2)若 a 中含有n 个元素，则算法执行过程中，元素之间的比较次数是多少？(3)该算法是稳定的吗？若是，则阐述理由；否则，修改为稳定排序算法43.1 6(15分)假定计算机M 字长为16位，按字节编址，连 接 CPU和主存的系统总线中地址线为 20位、数据线为8 位，采 用 16位定长指令字，指令格式及其说明如下：第6 页共10页更新时间 2022-06-25 16:30:12格式6位2位2位2位4位指令功能或指令类型说明R型000000rsrtrdoplRrd-Rrsopl RrtI型op2rsrtimm含ALU运算、条件转移和访存操作3类指令J型op3targetPC 的低 10 位 J target其中，oplop3为操作码，rs,rt和rd为通用寄存器编号，Rr表示寄存器r 的内容，imm为立即数，target为转移目标的形式地址请回答下列问题l)ALU的宽度是多少位？可寻址主存空间大小为多少字节？指令寄存器、主存地址寄存器(MAR)和主存数据寄存器(MDR)分别应有多少位？(2)R型格式最多可定义多少种操作？I 型和J 型格式总共最多可定义多少种操作？通用寄存器最多有多少个？(3)假定。

p l为 0010和0011时，分别表示带符号整数减法和带符号整数乘法指令，则指令01B2H的功能是什么(参考上述指令功能说明的格式进行描述)？若 1,2,3号通用寄存器当前内容分别为B052H,0008H,0020H,则分别执行指令01B2H和 01B3H后，3 号通用寄存器内容各是什么？各自结果是否溢出？若采用I型格式的访存指令中imm(偏移量)为带符号整数，则地址计算时应对imm进行零扩展还是符号扩展？(5)无条件转移指令可以采用上述哪种指令格式？44.2 7(8 分)假设计算机M 的主存地址为24位，按字节编址；采用分页存储管理方式，虚拟地址为30位，页大小为4KB；TLB采用2路组相联方式和LRU替换策略，共8 组请回答下列问题1)虚拟地址中哪几位表示虚页号？哪几位表示页内地址？(2)已知访问TLB时虚页号高位部分用作TLB标记，低位部分用作TLB组号，M 的虚拟地址中哪几位是TLB标记？哪几位是TLB组号？(3)假设TLB初始时为空，访问的虚页号依次为10,12,16,7,26,4,12和 2 0,在此过程中,哪一个虚页号对应的TLB表项被替换？说明理由4)若将M 中的虚拟地址位数增加到32位，则TLB表项的位数增加几位？45.9(7分)下表给出了整型信号量S 的wait。

和signal操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法第7页 共10页更新时间 2022-06-25 16:30:12功能描述方 法 1方法2semaphore S;semaphore S;semaphore S;wait(S)wait(S)wait(S)while(S=0);关中断；关中断；S=S-1;while(S=0);while(S=0)S=S-1;开中断；开中断；关中断；signal(S)S=S+1;S=S-1;)signal(S)开中断；关中断；)S=S+1;signal(S)开中断；关中断；)S=S+1;开中断；请回答下列问题1)为什么在waitQ和signalQ操作中对信号量S的访问必须互斥执行？(2)分别说明方法1和方法2是否正确若不正确，请说明理由3 用户程序能否使用开/关中断指令实现临界区互斥？为什么？46.(8分)某计算机用硬盘作为启动盘，硬盘第一个扇区存放主引导记录，其中包含磁盘引导程序和分区表磁盘引导程序用于选择要引导哪个分区的操作系统，分区表记录硬盘上各分区的位置等描述信息硬盘被划分成若干个分区，每个分区的第一个扇区存放分区引导程序，用于引导该分区中的操作系统。

系统采用多阶段引导方式，除了执行磁盘引导程序和分区引导程序外，还需要执行ROM中的引导程序请回答下列问题1)系统启动过程中操作系统的初始化程序、分区引导程序、ROM中的引导程序、磁盘引导程序的执行顺序是什么？(2)把硬盘制作为启动盘时，需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区，执行这4个操作的正确顺序是什么？(3)磁盘扇区的划分和文件系统根目录的建立分别是在第(2)问的哪个操作中完成的？47.2 0(9分)某网络拓扑如题47图所示，以太网交换机S通过路由器R与Internet互联路由器部分接口、本地域名服务器、H l、H2的IP地址和MAC地址如图中所示在 时 亥UH1的ARP表 和S的交换表均为空，H1在此刻利用浏览器通过域名请求访问Web服务器，在力时 刻 缶 io)S第一次收到了封装HTTP请求报文的以太网帧，假设从打到协期间网络未发生任何与此次Web访问无关的网络通信第8页 共10页更新时间 2022-06-25 16:30:12题47图请回答下列问题1)从打到f i期间，H1除了 HTTP之外还运行了哪个应用层协议？从应用层到数据链路层，该应用层协议报文是通过哪些协议进行逐层封装的？若S的交换表结构为,则h时亥ij S交换表的内容是什么？从t0到h期间，H2至少会接收到几个与此次Web访问相关的帧？接收到的是什么帧？帧的目的MAC地址是什么？第9页 共10页408计算机学科专业基础2021年真题（答案速查）、单项选择题1.D2.D3.B4.C5.B6.D7.A8.C9.A10.C11.B12.D13.D14.A15.C16.A17.D18.C19.C20.A21.B22.A23.B24.B25.C26.C27.D28.C29.B30.A31.C32.C33.B34.A35.A36.B37.D38.B39.D40.C二、其他略。