1、计算机专业（基础综合）模拟试卷 12 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 栈 S 最多只能容纳 4 个元素，现在 6 个元素按 A，B，C，D ，E，F 的顺序进栈，下列哪一个序列是可能的出栈序列( )?（A）EDCBAF（B） BCEFAD（C） CBEDAF（D）ADFEBC2 有 A，B，C ，D ，E 5 个元素按次序入栈，在各种可能的出栈次序中，以元素C，D 最先出栈的序列中，下列正确的一组是( )。（A）CDBAE CDABE（B） CDEBA CDBEA（C） CDEAB CDABE
2、（D）CEBAE CDAEB3 已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则完全二叉树的结点个数最多是( ) 。（A）39（B） 52（C） 111（D）1194 将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是( )。父子关系兄弟关系u 的父结点与 v 的父结点是兄弟关系A只有B 和C和D 、 和（A）只有（B） 和（C） 和（D）、和5 线索化的二叉树中，某结点*p 没有孩子的充要条件是( )。（A）p- lchild=NULL（B） p-ltag=1&p- rtag=1（C） p-lt
3、ag=0（D）p- lchild=NULL&p-ltag=16 设二叉排序树中关键字由 11 000 的整数构成，现要查找关键字为 363 的结点，下列关键字序列不可能是在二叉排序树上查找到的序列是( )。（A）2，252，401，398，330，344，397，363（B） 924，220，911，244，898，258，362，363（C） 925，202，911，240，912，245，363（D）2，399，387，219，266，382，381，278， 3637 在下列查找的方法中，平均查找长度与结点个数 n 无关的查找方法是( )。（A）顺序查找（B）二分法（C）利用二叉搜索树（
4、D）利用哈希(hash)表8 （A）14（B） 19（C） 21（D）269 将两个长度为 N 的有序表归并到一个长度为 2N 的有序表，最少需要比较的次数是( )，最多需要比较的次数是( ) 。（A）N，2N-1（B） N-1，2N（C） N，2N（D）N-1 ，2N-110 用直接插入排序方法对下列 4 个表进行(由小到大)的排序，比较次数最少的是( )。（A）94，32，40，90，80，46，21，69（B） 21，32，46，40，80，69，90，94（C） 32，40，2l，46，69，94，90，80（D）90，69，80，46，21，32，94，4011 CPU 中决定指令执
5、行顺序的是( )。（A）指令寄存器 IR（B）程序计数器 PC（C）程序状态字寄存器 PSWR（D）主存地址寄存器 MAR12 一个 C 语言程序在一台 32 位机器上运行。程序中定义了三个变量 x、y 和 z，其中 x 和 z 是 int 型，y 为 short 型。当 x=127，y=-9 时，执行赋值语句 z=x+y 后，x、y 和 z 的值分别是 ( )。（A）x=0000007FH，y=FFF9H，z=00000076H（B） x=0000007FH，y=FFF9H ，z=FFFF0076H（C） x=0000007FH，y=FFF7H ，z=FFFF0076H（D）x=000000
6、7FH，y=FFF7H，z=00000076H13 原码两位乘中，符号位单独处理，参加操作的数是( )。（A）原码（B）补码（C）绝对值的原码（D）绝对值的补码14 在 Cache 和主存构成的两级存储系统中，Cache 的存取时间为 100 ns，主存的存取时间为 1s，Cache 访问失败后 CPU 才开始访存。如果希望 Cache-主存系统的平均存取时间不超过 Cache 存取时间的 15，则 Cache 的命中率至少应为( )。（A）95（B） 98（C） 985（D）99515 双端口存储器之所以能高速读写是因为( )。（A）采用了两套独立的存储体（B）采用了两套相互独立的读写电路（
7、C）采用了新型的器件（D）两套读写电路分时使用存储体16 某机主存容量 64 KB，按字节编址。主存地址 0100H 处有一条相对转移指令，指令字长 16 位，其中，第一个字节为操作码，第二个字节为相对位移量(用补码表示)，则该指令执行结束后，后继指令的地址范围可能是( )。（A）0000HFFFFH（B） 0080H017FH（C） 0082H0181H（D）0080H01FFH17 下列哪个选项不是 RISC 的特点( )。（A）只有取数和存数指令访问存储器，其余指令都在寄存器之间进行（B）由使用频率高的简单指令和很有用且不复杂的指令组成（C）使用 RISC 技术后，指令系统又回到了计算机
8、发展早期的比较简单的情况（D）使用优化的编译程序18 下列微指令的编码方式中，执行速度最快的是( )。（A）直接编码（B）字段直接编码（C）字段间接编码（D）无法判断19 相对于微程序控制器，硬布线控制器的特点是( )。（A）指令执行速度慢，指令功能的修改和扩展容易（B）指令执行速度慢，指令功能的修改和扩展难（C）指令执行速度快，指令功能的修改和扩展容易（D）指令执行速度快，指令功能的修改和扩展难20 某机采用计数器定时查询方式来进行总线判优控制，共有 4 个主设备竞争总线使用权，当计数器初值恒为 102 时，4 个主设备的优先级顺序为( )。（A）设备 0设备 1设备 2设备 3（B）设备
9、2设备 1设备 0设备 3（C）设备 2设备 3设备 0设备 1（D）设备 2=设备 3=设备 0=设备 121 下列通道中，以字节为单位进行数据传送的是( )。（A）字节多路通道（B）选择通道（C）数组多路通道（D）以上都是22 下列选项中，能引起外部中断的事件是( )。（A）键盘输入（B）除数为 0（C）浮点运算下溢（D）访存缺页23 单处理机系统中，可并行的是( )。进程与进程 处理机与设备 处理机与通道 设备与设备（A）、和（B） 、和（C） 、和（D）、和24 下列进程调度算法中，综合考虑进程等待时间和执行时间的是( )。（A）时间片轮转调度算法（B）短进程优先调度算法（C）先来先服
10、务调度算法（D）高响应比优先调度算法25 某计算机系统中有 8 台打印机，有 K 个进程竞争使用，每个进程最多需要 3 台打印机。该系统可能会发生死锁的 K 的最小值是( )。（A）2（B） 3（C） 4（D）526 在虚拟存储系统中，若进程在内存中占 3 位(开始时为空)，采用先进先出页面淘汰算法，当执行访问页号序列为 1，2，3，4，1，2，5，1，2，3，4，5，6 时，将产生( ) 次缺页中断。（A）7（B） 8（C） 9（D）1027 拿内存加上外存容量之和与虚拟存储空间相比，其大小关系是( )。（A）前者比后者大（B）前者比后者小（C）二者相等（D）不一定28 位示图可用于磁盘空间
11、的管理。设某系统磁盘共有 500 块，块号从 0 到 499；第 0 字的第 0 位表示第 0 块，第 0 字的第 1 位表示第 1 块，依次类推。若用位示图法管理这 500 块的盘空间，当字长为 32 位时，第 i 个第 j 位对应的块号是( )。（A）32i+j（B） 32i+j-1（C） 32i+j-32（D）32i+j-32-129 考虑一文件存放在 100 个数据块中，文件控制块、索引块或索引信息都驻留内存。那么，如果( ) ，不需要做任何磁盘 IO 操作。（A）采用 contiguous allocation 策略，将最后一个数据块搬到文件头部（B）采用 single level
12、indexed allocation 策略，将最后一个数据块插入文件头部（C）采用 linked allocation 策略，将最后一个数据块插入文件头部（D）采用 linked allocation 策略，将第一个数据块插入文件尾部30 文件系统中，设立打开文件系统功能调用的基本操作是( )。（A）把文件信息从辅存读到内存（B）把文件的控制管理信息从辅存读到内存（C）把文件的 FAT 表信息从辅存读到内存（D）把磁盘的超级块从辅存读到内存31 文件系统采用树形目录结构后，对于不同用户的文件，其文件名( )。（A）应该不同（B）由操作系统类型决定（C）可以相同也可以不同（D）受系统约束32 对
13、于硬盘上存放的信息，物理上读写的最小单位是一个( )。（A）二进制（B）字节（C）物理块（D）逻辑记录33 IEEE 的 802 委员会已经标准化了很多种类的 LAN，其中无线 LAN 标准是( )。（A）IEEE8023（B） IEEE8025（C） IEEE80211（D）IEEE8021734 有一条无噪声的 8 KHz 信道，每个信号包含 8 级，每秒采样 24 K 次，那么可以获得的最大传输速率是( )。（A）24 Kbps（B） 32 Kbps（C） 48 Kbps（D）72 Kbps35 （A）115 200 bps（B） 57 600 bps（C） 28 800 bps（D）2
14、30 400 bps36 在 Internet 的几种路由协议中，( )采用了链路状态路由算法。（A）RIP（B） BGP（C） OSPF（D）NAT37 一个 3 200 bit 上的 TCP 报文传到 IP 层，数据链路层可以发送的最长数据帧中的数据部分只有 1 200 bit。IP 层需要向数据链路层发送( ) 。（A）3 200 bit（B） 3 400 bit（C） 5 400 bit（D）3 680 bit38 某公司获得了一个 IP 地址段，在不分子网的情况下，最多可以容纳 65 534 个主机，那么这个地址属于( )。（A）A 类地址（B） B 类地址（C） C 类地址（D）D
15、 类地址39 在 TCP IP 模型中，主机采用 ( )标识，运行在主机上的应用程序采用 ( )标识。（A）端口号，主机地址（B）主机地址，IP 地址（C） IP 地址，主机地址（D）IP 地址，端口号40 下面( ) 协议中，客户端和服务器之间采用面向无连接的协议进行通信。（A）FTP（B） SMTP（C） TELNET（D）DHCP二、综合应用题41-47 小题，共 70 分。41 设有一个由正整数组成的无序(后向)单链表，编写能够完成下列功能的算法：(1)找出最小值结点，且打印该数值。(2)若该数值为奇数，则将其与直接后继结点的数值交换。(3)若该数值为偶数，则将其直接后继结点删除。42
16、 给定序列3，5，7，9 ，11，13，15，17)，(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树，并求其在等概率情况下查找成功的平均查找长度。43 已知 4 位有效信息为 1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式 G(x)=1011。44 某机字长 32 位，采用定长操作码，单字长指令，共有机器指令 100 条，CPU内部有通用寄存器 32 个，可作变址寄存器用，存储
17、器按字节编址，指令拟用直接寻址、间接寻址、变址寻址和相对寻址等 4 种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字段指出时的指令格式。(2)当指令寻址方式由操作码指出时，直接和间接寻址可寻址的主存空间大小为多少?(3)写出 4 种寻址方式下，有效地址 EA 的表达式。45 分页存储管理中，页表的功能是什么?当系统中的地址空间变得非常大时(如 32位地址空间)，会给页表的设计带来什么样的新问题?请给出一种解决方法，分析它的优点和缺点。46 有一个仓库，可以存放 A 和 B 两种产品，但要求：(1)每次只能存入一种产品(A 或 B)；(2)-NA 产品的数量-B 产品的数量M。其
18、中，N 和 M 是正整数。试用 P，V操作描述产品 A 与产品 B 的入库过程。47 某公司的局域网设置如下所示，两个局域网通过路由器连接到 NAT、服务器上，并且通过 NAT 服务器连接到 Internet 上。局域网 1 的掩码是19216814025，局域网 2 的掩码是 1921681412825，NAT 服务器的内部 IP 地址为 1921681325，外部 IP 地址为 2021578569，在 NAT服务器中有如下的表项：请问：(1)地址是19216814175 的主机和地址为 1921681448 的主机分别属于哪个局域网?(2)按照题目的配置，路由器的路由表项应该含有哪几项?
19、(3)现在有一个目的地址为 201256899，源地址为 19216814175，TCP 端口为 652 的 IP 分组到达 NAT、服务器，问 NAT 服务器是否转发该分组?如果转发，分组的 IP 号和端口号分别是多少?(4)当 NAT 服务器收到一个目的地址是 2021578569，端口号是 4325 的 TCP 数据后，它将转发给哪个主机?计算机专业（基础综合）模拟试卷 12 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 由于栈只能容纳 4 个元素，所以一次进栈最多 4 个
20、，即 ABCD 同时在栈中，则 EDCBAF 不可能，E 和 F 还没有进栈就已经出栈， B 中的 D 元素不可能出栈在 A 的后面。D 中最后两个元素出栈顺序也有误。2 【正确答案】 B【试题解析】 要使得 CD 作为第一、二个元素出栈，应是 A、B 、C 先入栈，C出栈，D 入栈，D 出栈；接着就剩下 A、B 在栈中，E 未入栈，共 3 个元素，此三者序列为 BAE，BEA ，EBA。3 【正确答案】 C4 【正确答案】 B5 【正确答案】 B6 【正确答案】 C【试题解析】 可以把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现，C 序列形成的不是一条路径，而是有分支的，可见它
21、是不可能在查找过程中访问到的序列。7 【正确答案】 D8 【正确答案】 C9 【正确答案】 A10 【正确答案】 C11 【正确答案】 B【试题解析】 CPU 中用程序计数器 PC 来跟踪下一条将要执行的指令的地址，即通过程序计数器 PC 来决定指令执行顺序。12 【正确答案】 D【试题解析】 结合题干及选项可知，int 为 32 位，short 为 16 位；又 C 语言的整型数据在内存中为补码形式，故 x、y 的机器数写为十六进制为0000007FH、FFF7H ；执行 z=x+y 时，由于 x 为 int 型，y 为 short 型，故需将 y的类型强制转换为 int，在机器中通过符号位
22、扩展实现，由于 y 的符号位为 1，故在 y 的前面添加 16 个 1，即可将 y 强制转换为 int 型，其十六进制形式为FFFFFFF7H；然后执行加法，即 0000007FH+FFFFFFF7H=00000076H(最高位的进位 1 自然丢弃)。故选 D。13 【正确答案】 D【试题解析】 原码两位乘中，符号位单独处理，但运算过程中可能需要进行“减被乘数绝对值”的操作，计算机中减法一般通过补码加法来实现，故原码两位乘运算过程中参加操作的数是绝对值的补码。14 【正确答案】 C【试题解析】 设 Cache-主存系统的平均存取时间为 Cache 存取时间的 115 倍时 Cache 命中率为
23、 p，则有 100+1 000(1-p)=115，解之得， p=0985=98 5。15 【正确答案】 B【试题解析】 双端口存储器采用了两套相互独立的读写电路，两套读写电路可以同时访问共同的存储体，故可以高速读写。16 【正确答案】 C【试题解析】 该指令取指结束后，PC 值自动加 2，即(PC)一 0102H；相对位移量用 8 位补码表示，故其范围为 80H7FH，扩展到 16 位为 FF80H007FH，与PC 值相加就可得后继指令的地址范围为 0082H 0181H。17 【正确答案】 C【试题解析】 早期的指令系统简单是由设计水平和器件水平决定的，而且RIS(二技术不是简单地精简了指
24、令系统，而是在合理选择简单指令的基础上采取了很多优化措施，如缩短机器周期，采用流水线技术，使用优化的编译程序等等，两者不可等同。18 【正确答案】 A【试题解析】 直接编码方式下，微指令操作控制字段中的每一位代表一个微操作命令，微操作命令的发出不需要通过译码，故执行速度最快。19 【正确答案】 D【试题解析】 硬布线控制器采用硬连线逻辑，故一旦构成，除非在物理上进行重新布线，否则指令功能无法修改和扩展；微程序控制器采用存储逻辑，当需要对指令功能进行修改和扩展时，只要重新设计微代码的码点，并将其注入控制存储器中即可；但是由于采用存储逻辑，相比硬布线控制器多了从控制存储器中读出码点的过程，故其执行
25、速度较慢。综合上述分析，可知 D 正确。20 【正确答案】 C【试题解析】 计数器初值为 10z，故设备 2 的优先级最高，计数器值会递增然后返回到 O，故优先级顺序为设备 2设备 3设备 0设备 1。21 【正确答案】 A【试题解析】 选择通道和数组多路通道都是以数据块为单位进行数据传送。22 【正确答案】 A【试题解析】 浮点数下溢一般做“机器零“处理，不引起中断；除数为 0、访存缺页会引出内部中断；只有键盘输入能引起外部中断，故选 A。23 【正确答案】 D【试题解析】 进程和进程是不能并行的，因为只有一个 CPU。24 【正确答案】 D【试题解析】 响应比一(等待时间+执行时间)要求服
26、务的时间。25 【正确答案】 C【试题解析】 每个进程都占有 2 台打印机时，发生死锁。26 【正确答案】 D27 【正确答案】 D【试题解析】 虚拟存储空间是由地址的位数决定的，可能比内存加上外存大，也可能小。28 【正确答案】 A【试题解析】 因为从 0 开始编号，所以选 A。29 【正确答案】 B【试题解析】 采用索引分配：将最后一个数据块插入文件头部，只需修改索引表就行，不需要移动数据。30 【正确答案】 B31 【正确答案】 C【试题解析】 树形目录的引入提高了检索的效率，解决了文件的重名问题，即允许不同的用户使用相同的文件名。因此，对于不同用户文件而言其文件名既可以相同也可以不同。
27、32 【正确答案】 C【试题解析】 硬盘的读取是以块为单位的。33 【正确答案】 C【试题解析】 IEEE80211 是无线 LAN 的标准。34 【正确答案】 C【试题解析】 无噪声的信号应该满足尼奎斯特定理，即最大数据传输率=2 Hlog2V(位秒) 。将题目中的数据带入，得到答案是 48 kHz。注意题目中给出的每秒采样 24 kHz 是无意义的，因为超过了 2H，所以 D 是错误答案。35 【正确答案】 B36 【正确答案】 C【试题解析】 OSPF(开放的最短路径优先)内部网关路由协议采用了链路状态路由算法。37 【正确答案】 D【试题解析】 在题目给出的情况中，必须要对 IP 包进
28、行分片，需要分 3 2001 200=3 片。那么共需要添加 3 个 IP 首部，每个 IP 首部的长度是 160 bit，那么总共需要发送 3 200+1603=3 680 bit 数据。38 【正确答案】 B【试题解析】 B 类地址的主机号的长度是 16 位，再去点全“0”和全“1”两个地址，还可以分配 65 534 个主机。39 【正确答案】 D【试题解析】 在 TCPIP 模型中，IP 地址用来标识主机，使用 IP 地址来完成数据包的路由。而端口号则存在于传输层的头部中，用来标识主机上的不同进程。40 【正确答案】 D【试题解析】 DHCP 采用 UDP 来发送数据，所以 D 是采用面
29、向无连接的协议的。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 算法的思想是：采用从前向后扫描单链表的方法，边扫描边测试，根据测试结点执行相应的操作。算法描述如下：int Function(LinkList*la)int temp；LinkNode*p=L-next；单链表为空时返回LinkNode*q=p；if(p=NULL)return 0；*找到最小值结点*while(p!=NULL)if(p-dataq-data)q=p；p=p-next ；*打印最小值结点*printf(“Min：dn“，p-data)；*功能点：若该数值为奇数，则将其与直接后继结点的数值交换*i
30、f(q-data2=1)temp=q- data；if(q-next=NULL)不存在直接后继结点return 0；q- data=q-next-data；q- next-data=temp；*功能点：若该数值为偶数，则将其直接后继结点删除*elseif(q-next=NULL)return 0；p=p-next ；q- next=p-next；free(p)；return 1；42 【正确答案】 43 【正确答案】 44 【正确答案】 45 【正确答案】 在分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，为能保证进程的正常运行，系统建立了页表。在进程地址空间内的所有页，依次在页
31、表中有一页表项，其中记录了相应页在内存中的对应物理块号，进程执行时通过查找页表，即可找到每页在内存中的位置，即页表的作业是实现页号到物理块号的地址映射。当地址空间变得非常大时，页表也将变得非常大，将占用相当大的内存空间。对于一个具有 32 位地址空间的分页系统，规定页面大小为 4 KB，则在每个进程页表中的页表项可达到 1 MB，又因为每个页表项占用 4 B，故仅每个进程的页表项就要占用 4 MB 的内存空间，而且要求是连续的，这显然是不现实的。可以从以下两个方面来解决这个问题。(1)对页表所需的空间采用离散分配。(2)只将当前所需的一部分页表项调入内存，其余表项仍驻留在外存中，仅当必须时才调
32、入内存。具体的实现方案是采用两级页表。在用户逻辑地址原来的划分基础上，将页表部分再分为页表索引项和页表两部分，也就是说对页表也进行分页。对于投入运行的程序，将其页表索引调入内存，而对其页表仅调入少量的项。程序运行时如找不到相应的页表，则产生一个中断，请求操作系统将该页表调入内存。两级页表适应了大地址空间的需要，实现了虚拟存储系统，但增加了地址变换的开销和操作系统管理上的复杂性。46 【正确答案】 首先设置一个初值为 1 的互斥信号量 mutex，以保证每次只存入一种产品。为了保证“-NA 产品的数量 -B 产品的数量M”，还需设置信号量 SA，保证目前可再存放的 A 产品数量，其初值为 M-1
33、；SB，表示目前还可以再存放的 B 产品数量，其初值为 N-1。A 产品入库的过程可描述为：while(true)P(SA)；还可再存放一个 A 产品吗?P(mutex)；将 A 产品放入仓库；V(mutex)；V(SB)；可存放的 B 产品数量增 1B 产品入库的过程可描述为：while(true)P(SB)；还可再存放一个 B 产品吗?P(mutex)；将 B 产品放入仓库；V(mutex)：V(SA)；可存放的 A 产品数量增 147 【正确答案】 (1)地址为 19216814175 的主机属于局域网 2，地址为1921681448 的主机属于局域网 1。 (2)路由器的表项如下：(3)NAT 服务器会将该分组转发到 Internet 上，转发后的 IP 地址为 2021578569，端口号为 5898。 (4)它会被转发给 1921681448。
