1、计算机专业（基础综合）模拟试卷 7 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 线性表的静态链表存储结构与顺序存储结构相比优点是( )。（A）所有的操作算法实现简单（B）便于随机存取（C）便于插入与删除（D）便于利用零散的存储器空间2 为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。（A）栈（B）队列（C）树（D）图3 用 P 代表人栈， O 代表出栈。栈的初始状态和最终状态都为空
2、，则下列栈操作正确的是( )。（A）POOPOOPP（B） POPOPOOP（C） PPPOOOPP（D）PPPOOPOO4 按照二叉树的定义，具有 3 个结点的二叉树有( )种。（A）3（B） 4（C） 5（D）65 根据使用频率为 5 个字符的哈夫曼编码不可能的是( )。（A）111，110，10，01，00（B） 000，001，010，011，1（C） 100，11，10，1，0（D）001，000，01，11，106 某高度为 k 的完全二叉树中，所含叶子结点的个数最少为( )。（A）2k（B） k（C） 2k-2（D）2 k-17 下列叙述正确的个数是( )。1)向二叉排序树中插入
3、一个结点，所需比较的次数可能大于此二叉排序树的高度。2)对 B-树中任一非叶子结点中的某关键字 K，比 K 小的最大关键字和比 K 大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值不大于 1 的二叉树。4)删除二叉排序树中的一个结点，再重新插入，一定能得到原来的二叉排序树。（A）4（B） 3（C） 2（D）18 求最短路径常用的算法有( )。（A）Prim 算法和 Kruskal 算法（B）深度优先遍历算法和广度优先遍历算法（C） Dijkstra 算法和 Floyd 算法。（D）拓扑排序算法9 若一组记录的排序码序列 F=50，80，30，40，70，60)
4、，利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为( )。（A）30，40，50，60，70，80（B） 40，30，50，80，70，60（C） 50，30，40，70，60，80（D）40，50，30，70，60，8010 在下列排序方法中不需要对排序码进行比较就能进行排序的是( )。（A）基数排序（B）快速排序（C）直接插入排序（D）堆排序11 计算机硬件系统中“ 主机 ”是指( )。（A）主机箱及其内部硬件设备（B）运算器和控制器（C） CPU 和主存储器（D）CPU 、主存和输入输出设备12 x补 =1x 1x2x4)，则当满足( )时，x-12 成立。（A）x 2 必
5、为 0，x 2x 4 至少有一个为 1（B） x1 必为 0，x 2x 4 任意（C） x1 必为 1，x 2x 2 至少有一个为 1（D）x 1 必为 1，x 2x 4 任意13 某浮点机字长 16 位，其中，阶码 5 位(含 1 位阶符)，采用补码表示，基数为4；尾数 11 位(含 1 位数符)，采用补码表示，且为规格化形式，则其可以表示的最小正数是( )。（A）2 -17（B） 2-26（C） 2-34（D）2 -4214 下列有关存储器的说法错误的是( )。（A）访问存储器的请求是由 CPU 发出的（B） Cache 与主存统一编址，即主存空间的某一部分属于 Cache（C） Cach
6、e 的功能全由硬件实现（D）Cache 主存层次主要为了解决存储系统的速度问题15 一个四体并行的低位交叉编址存储器，每个存储体的存取周期为 200 ns，总线传输周期为 50 ns，则连续读取 10 个存储字需时( )。（A）2000 ns（B） 600 ns（C） 650 ns（D）300 ns16 下列哪种寻址方式下，操作数在主存储器( )。（A）直接寻址（B）寄存器直接寻址（C）立即数寻址（D）以上都不对17 下列关于 RISC 机的说法中错误的是 ( )。（A）指令长度固定，指令格式种类少，寻址方式种类少（B）配备大量通用寄存器（C）强调采用流水线技术进行优化（D）较少使用硬布线逻辑
7、实现18 下列关于指令周期的说法中正确的是( )。（A）指令周期即时钟周期（B）指令周期是指 CPU 执行一条指令的时间（C）指令周期是指 CPU 取出一条指令并执行该指令的时间（D）以上说法都不对19 在单发射、按序流动的普通流水线中，可能出现下列哪种数据相关问题?( )。（A）写后读相关 RAW（B）读后写相关 WAR（C）写后写相关 WAW（D）以上都有可能20 某计算机系统中，各个主设备得到总线使用权的机会基本相等，则该系统采用的总线判优控制方式一定不是( )。（A）链式查询方式（B）计数器定时查询方式（C）独立请求方式（D）以上选项都不正确21 计算机的外围设备是指( )。（A）主存
8、储器（B）外存储器（C）除主机外的其他设备（D）除 CPU 外的其他设备22 某字节多路通道的最大数据传输率为 1 000 Bs，它有 5 个子通道，则每个子通道的最大数据传输率为( )。（A）200 Bs（B） 1 000 Bs（C）介于 A、B 之间（D）以都不对23 下面关于进程的叙述中，正确的是( )。（A）进程获得 CPU 运行是通过调度得到的（B）优先级是进程调度的重要依据，一旦确定就不能改变（C）在单 CPU 的系统中，任意时刻都有一个进程处于运行状态（D）进程申请 CPU 得不到满足时，其状态变为阻塞24 在请求分页存储管理中，若采用 FIFO 的页面淘汰算法，当分配的页面数增
9、加时，缺页中断的次数( ) 。（A）减少（B）增加（C）无影响（D）可能增加也可能减少25 3 个进程共享 4 个同类资源，这些资源的分配与释放只能一次一个。已知每一个进程最多占有两个该类资源，则该系统( )。（A）有某进程可能用于得不到该类资源（B）必然有死锁（C）进程请求该类资源立刻能得到（D）必然无死锁26 在读写文件的操作中，通常使用“块高速缓存”，以减少访问磁盘的次数，但为了保证系统的( ) ，关键块必须尽早写盘。（A）一致性（B）安全性（C）性能（D）可扩性27 ( )进程调度算法综合考虑到了 CPU 密集型进程和 IO 密集型进程。（A）时间轮转（B）优先级（C）多重队列（D）F
10、IFO28 设有 3 个作业，其运行时间分别为 2 小时、5 小时、3 小时，假定它们同时到达，并在同一台处理机上以单道运行方式运行，则平均周转时间最小的执行顺序是( )。（A）J1，J2，J3（B） J3，J2，J1（C） J2，J1，J3（D）J1，J3，J229 分页系统中的页面是为( )。（A）用户所感知的（B）操作系统所感知的（C）编译系统所感知的（D）连接装配系统程序所感知的30 程序员利用系统调用打开 IO 设备时，通常使用的设备标识是( )。（A）逻辑设备名（B）物理设备名（C）主设备号（D）从设备号31 中断向量的地址是( )。（A）子程序入口地址（B）中断服务例行程序入口地
11、址（C）中断服务例行程序入口地址的地址（D）例行程序入口地址32 操作系统采用页式存储管理方法，要求( )。（A）每个进程拥有一张页表，且进程的页表驻留在内存中（B）每个进程拥有一张页表，但只要执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中（C）所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中（D）所有进程共享一张页表，只有页表当前使用的页面必须驻留在内存中，以最大限度地节约有限的内存空间33 在 OSI 的层次模型中，( )是控制对等实体间进行通信的规则的集合。（A）协议（B）服务（C）接口（D）原语34 在无噪声情况下，若某通信链路的带宽为 3 kHz，采用
12、4 个相位，每个相位具有 4 种振幅的 QAM 调制技术，则该通信链路的最大数据传输速率是( )。（A）12 kbps（B） 24 kbps（C） 48 kbps（D）96 kbps35 数据链路层采用了后退 N 帧的(GBN)协议，如果发送窗口的大小是 32，那么至少需要( ) 位的序列号才能保证协议不出错。（A）4 位（B） 5 位（C） 6 位（D）7 位36 以太网地址是由( ) 个字节组成的。（A）3（B） 4（C） 5（D）637 TCP 使用三次握手协议来建立连接，假设甲乙双方发送报文的初始序列号分别为 X 和 Y，甲方发送 SYN=1，序号=X 的报文给乙方，乙方接收报文后发送
13、( )的报文给甲方，然后甲方发送一个确认报文给乙方便建立了连接。（A）SYN=0 ，序号=Y；ACK=1，确认序号=X+1（B） SYN=1，序号=Y；ACK=0，确认序号=X+1（C） SYN=1，序号=Y；ACK=1，确认序号=X+1（D）SYN 一 1，序号=Y；ACK=1，确认序号=X38 假设一个应用每秒产生 60 bytes 的数据块，每个数据块被封装在一个 TCP 报文中，然后再封装到一个 IP 数据报中。那么最后每个数据报所含有的应用数据所占的百分比是( ) 。（A）20（B） 40（C） 60（D）8039 有一条 TCP 连接，它的最大报文段长度是 2 kB，TCP 拥塞窗
14、口为 24 kB，这时候发生了超时事件，那么该拥塞窗口变成了( )。（A）1 kB（B） 2 kB（C） 5 kB（D）7 kB40 在 DNS 的递归查询中，由( )给客户端返回地址。（A）最开始连接的服务器（B）最后连接的服务器（C）目的地址所在的服务器（D）不确定二、综合应用题41-47 小题，共 70 分。41 设一段正文由字符集A，B，C ，D，E ，F) 中的字母组成，这 6 个字母在正文中出现的次数分别为12， 18，26，6，4，34)。(1)为这 6 个编码设计哈夫曼编码。(2)设每个字节由 8 位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字节。(3)若这段正
15、文开始部分的二进制编码序列为：0110001001011010100，请按 1 的哈夫曼编码将其译为正文。42 荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为 O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。43 一个由高速缓冲存储器 Cache 与主存储器组成的二级存储系统。已知主存容量为 1 MB，按字节编址，缓存容量为 32 KB，采用组相联方式进行地址映射与变换，主存与缓存的每一块为 64 B，缓存共分 8 组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)。(2)假定 Cache 的存取周期为 20s，命中率为
16、095，希望采用 Cache 后的加速比大于 10。那么主存储器的存取速度应大于多少(访存时 CPU 同时访问 Cache 和主存，如 Cache 命中则中断主存访问)?44 指令系统字长 16 位，每个地址码为 6 位，采用扩展操作码的方式，试设计 14条二地址指令，100 条一地址指令，100 条零地址指令。 (1)画出操作码的扩展形式。(2)下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的译码逻辑。(3)计算操作码的平均长度。45 假定在一个处理机上执行的操作如下：作业 估计服务时间片 优先数A 10 3B 1 1C 2 3D 1 4E 5 2这些作
17、业假定按 A、B、C、D、E 次序先后几乎同时 (时间差相对时间片大小忽略不计)到达。(1)给定相应的图示来说明分别用 FCFS、RR(时间片=1)、SJF 和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情况。(2)分别给出采用上述调度算法时每个作业的周转时间和平均周转时间。46 一个 SPOOUNG 系统由输入进程 I、用户进程 P、输出进程 O、输入缓冲区、输出缓冲区组成。进程 I 通过输入缓冲区为进程 P 输入数据，进程 P 的处理结果通过输出缓冲区交给进程 O 输出。进程间数据交换以等长度的数据块为单位，这些数据块均存储在同一个磁盘上，因此，SPOOLING 系统的数据块
18、通信原语保证始终满足：I+Omax 其中，max 为磁盘容量(以该数据块为单位)，I 为磁盘上输入数据块总数，O 为磁盘上输出数据总数。该 SPOOLING 系统运行时：(1)只要有输入数据，进程 I 终究会将它放入输入缓冲区；(2)只要输入缓冲区有数据块，进程 P 终究会输入、处理并产生结果数据写到输出缓冲区；(3)只要输出缓冲区有数据块，进程 O 终究会输出它。请说明该 SPOOLING 系统在什么情况下死锁，请说明如何修正约束条件(1)避免死锁，同时仍允许输入数据块和输出数据块存储在同一个磁盘上。47 一个客户机利用 FTP 协议从服务器上下载文件，如下图所示为整个过程中协议交换的过程，
19、请回答如下问题： (1)该协议层图中第四层协议是什么? (2)如果 FTP客户端采用了 LIST 命令来获得 FTP 服务器上的文件列表，该列表采用什么端口传输? (3)如果一个 TCP 数据包的数据部分长度为 5 000 字节，那么在 IP 层需要分片吗? (4)如果需要分片请说明需要分成几片，每片长度为多少? 如果不需要分片，请说明原因。计算机专业（基础综合）模拟试卷 7 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 静态链表具有链表的插入和删除方便的优点，也不需要移动较多的
20、元素。2 【正确答案】 B3 【正确答案】 D【试题解析】 A，B 会出现下溢，即出栈时栈为空。 C 中出现最终状态不为空。4 【正确答案】 C5 【正确答案】 C【试题解析】 C 中 100 和 10 冲突，即一个结点既是叶子结点又是内部结点，哈夫曼树中不可能出现这种情况。6 【正确答案】 C【试题解析】 完全二叉树只有高度最大的那一层可能不满，k-1 层应都是满的。7 【正确答案】 D8 【正确答案】 C【试题解析】 A 是最小生成树的算法，B 是图的遍历算法， D 中的回溯法是求解递归过程的一种重要方法。9 【正确答案】 B10 【正确答案】 A11 【正确答案】 C【试题解析】 CPU
21、 和主存储器合称主机。12 【正确答案】 C【试题解析】 可采用排除法，10001 符合 A、 B 选项的要求，其值-15 16-12，排除 A、B；11000 符合 D 选项的要求，其值=-1 2，排除 D；故选 C。13 【正确答案】 C【试题解析】 根据题意，该机可以表示的正数的机器数形式为：10000；00100000000，其真值为 4-16(14-1)=4-17=2-34，选 C。本题要注意基数为 4 时尾数的规格化形式。14 【正确答案】 B【试题解析】 Cache 中字块保存的是主存中相应字块的副本，Cache 是一种缓冲，而不是与主存处于同等地位的存储器，故不需要占用主存空间
22、，B 选项错误。15 【正确答案】 C【试题解析】 四体并行的低位交叉存储器连续读取 10 个存储字时，读第一个存储字需要一个完整的存取周期，即 200 ns，接下来每个存储字的读取只需一个总线传输周期 50 ns，故共需时 200+50(10-1)=650 ns。16 【正确答案】 A【试题解析】 直接寻址时，形式地址 A 为有效地址，即操作数在主存储器的地址，也就是说操作数在主存储器。17 【正确答案】 D【试题解析】 RISC 机由于结构较简单，故常采用速度较陕的硬布线逻辑来实现，D 选项错误。18 【正确答案】 C【试题解析】 指令周期即 CPtJ 从主存取出一条指令并执行该指令的时间
23、，C 选项为正确选项。19 【正确答案】 A【试题解析】 指令取操作数的动作一定在写回结果之前，故在按序流动的单发射(普通标量) 普通流水线中，先进人流水线的指令的取操作数和写回结果的动作一定位于后续指令写回结果的动作之前，故不可能出现 WAR 和 WAW；唯一可能的数据相关问题是后续指令在前一指令写回结果之前读相关的操作数，即 RAW，写后读相关。而在非按序流动的流水线中，允许后进入流水线的指令超过先进入流水线的指令而先流出流水线，故三种数据相关问题都可能出现。20 【正确答案】 A【试题解析】 链式查询方式下，越靠近总线仲裁机构的主设备优先级越高，且其优先级顺序不可改变，故不可能出现各主设
24、备得到总线使用权机会基本相等的情况。21 【正确答案】 C【试题解析】 外围设备是相对主机而言，即除 CPU 和主存储器外的其他设备。22 【正确答案】 A【试题解析】 字节多路通道轮流对各个子通道进行传送，每次连接一个子通道只传送一个字节便转向下一个子通道，故字节多路通道的最大数据传输率为各个子通道最大数据传输率之和，即每个子通道的最大数据传输率为 1 0005=200 Bs 。23 【正确答案】 A【试题解析】 B.错误优先级是可以动态改变的。C. 错误没进程的时候，系统可以空闲。D.错误变为就绪态。24 【正确答案】 D【试题解析】 因为 FIFO 算法存在 Belady 现象，所以可能
25、增加也可能减少。25 【正确答案】 D【试题解析】 根据题意，则任意时刻总有一个进程可以获得其所有资源，从而能在有限的时间内运行完毕，所以系统那个必然无死锁。26 【正确答案】 A【试题解析】 为了保证数据一致性，必须保证先写后读。27 【正确答案】 C【试题解析】 多重队列通过将进程分类，在系统中设置若干队列进行进程调度，综合考虑到了 CPU 密集型进程和 IO 密集型进程。28 【正确答案】 D【试题解析】 本题考查平均周转时间的概念，周转时间=等待时间+ 运行时间，平均运行时间=总周转时间n。29 【正确答案】 B【试题解析】 页面信息是由操作系统管理的。30 【正确答案】 A【试题解析
26、】 程序员所看到的是设备的逻辑设备名。31 【正确答案】 C【试题解析】 中断向量包括两个字，一个是中断处理程序的入口地址，另一个是中断处理程序的程序状态字。那么显然，中断向量地址就是中断处理程序的入口地址的地址了。32 【正确答案】 A【试题解析】 在分页系统中为每个进程都配置一张页表，进程逻辑地址空间中的每一页在页表中都有一个页表项。33 【正确答案】 A34 【正确答案】 B【试题解析】 采用四个相位每个相位有 4 种振幅的 QAM 调制技术后，每个信号可以有 16 种变化，传输 4 bit 的数据。而链路带宽为 3 kHz，根据奈奎斯特定理，可以用 6 kHz 的频率对信道采样，所以最
27、大传输速率是 24 kbps。35 【正确答案】 C【试题解析】 在后退 N 帧的协议中，序列号个数 =MAX_SEQ+1，在题目中发送窗口的大小是 32，那么序列号个数最少应该是 33 个。所以最少需要 6 位的序列号才能达到要求。36 【正确答案】 D【试题解析】 以太网地址由 48 比特组成，常用 6 个字节表示。而 IPv4 的地址由32 比特组成，常使用 4 个字节表示。37 【正确答案】 C【试题解析】 本题考查 TCP 协议建立的三次握手，乙方接受到甲方的建立连接请求后再发送一个 SYN=1 的报文请求建立本方连接。而题目中说明甲方再回复一个确认报文就可以建立连接，说明了乙方在报
28、文中捎带了确认即 ACK=1。确认号是 X+1，所以答案是 C。38 【正确答案】 C【试题解析】 一个 TCP 的头部长度是 20 字节，一个 IP 头部的长度是 20 字节，再加上 60 字节的数据，一个 IP 数据报的总长度为 100 字节，其中数据占 60。39 【正确答案】 B【试题解析】 在 TCP 中，当发生超时事件，阀值被设置成当前拥塞窗口的一半，而拥塞窗口被设为一个最大报文段。40 【正确答案】 A【试题解析】 在递归查询中，每台不包含被请求信息的服务器都转到别的地方去查找，然后它再往回发送结果。所以客户端最开始连接的服务器最终将返回给它正确的信息。二、综合应用题41-47
29、小题，共 70 分。41 【正确答案】 42 【正确答案】 在算法中设立三个指针，其中，j 表示当前元素，i 以前的元素全部为红色，k 以后的元素全部为蓝色，这样就可以根据 j 的颜色，把其交换到序列的前部或者后部。算法如下：typedef enumRED，WHITE，BLUE)color；三种颜色void ColorAErange(color a，int n)*把由三种颜色组成的序列重排为按照红、白、蓝顺序排序*int i=0；int j=0；int k=n-1：while(j=k)switch(aj)case RED：Swap(ai， aj)；交换 ai，aji+；j+；break；cas
30、e WHITE；j+；case BLUE；Swap(aj， ak)；交换 ak，ajk-这里没有 j+，防止交换后 aj仍然是蓝色43 【正确答案】 44 【正确答案】 45 【正确答案】 46 【正确答案】 i+o=Max当 i=max，p 的输出数据无处存放，i 的输入数据占满磁盘时，死锁。应该增加约束：i+o=max，设输出数据块长度 00。47 【正确答案】 (1)FTP 协议使用了 TCP 作为传输层协议，所以第四层协议应该为 TCP。(2)FTP 协议的控制连接端口是 21，数据连接端口是 20。而列表信息是通过数据传输端口传送的，所以通过了 20 端口传送。(3)以太网的最大数据长度是 1 500，而该 TCP 包的长度为 5 000，再加上 20 字节的 TCP 头和 20 字节的 IP 头，最后成帧的长度为 5 040 字节，不能通过以太网直接发送，必须要在 IP 层分片。(4)每片都带有一个 IP 头，还有 1 480 字节可以用来传输数据，计算得需要分 4片传送，前 3 片的长度为 1 500 字节，最后一片长度为 600 字节。
