1、计算机专业（基础综合）模拟试卷 9 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在一个双链表中，删除 p 结点之后的一个结点的操作是( )。（A）p- next=p-next-next ；p-next-next-prior=p；（B） p-next-prior=p；p-next=p-next-next；（C） p-next=p- next-next；p- next-prior=p；（D）p- next-next=p-next ；p-next-prior=p；2 设二维数组 A610，每个数组元素占用 4
2、个存储单元，若按行优先顺序存放的数组元素，a0O 的存储地址为 860，则 a35的存储地址为( )。（A）1000（B） 860（C） 1140（D）12003 如果二叉树 T2 是由有序树 T1 转换而来的二叉树，那么 T1 中结点的先序就是T2 中结点的( )。（A）先序（B）中序（C）后序（D）层次序4 在由 4 棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根结点的左子树中结点个数为( )。（A）20（B） 29（C） 30（D）355 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点在 A，并已
3、知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则应进行( )型调整以使其平衡。（A）LL（B） LR（C） RL（D）RR6 高度为 5(除叶子层之外)的三阶 B-树至少有( ) 个结点。（A）30（B） 31（C） 32（D）337 8 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（A）堆排序（B）冒泡排序（C）快速排序（D）直接插入排序9 下列排序算法中，时间复杂度不受数据初始状态影响恒为 O(nlog n)的是( )。（A）堆排序（B）冒泡排序（C）快速排序（D）直接插入排序10 指出在顺序表 F=(2，5，7，10，14，15，18，23，35
4、，41，52中，用二分查找法查找 12 需要进行多少次比较( )。（A）2（B） 3（C） 4（D）511 冯.诺依曼计算机的最根本特征是( )。（A）以存储器为中心（B）采用存储程序原理（C）存储器按地址访问（D）数据以二进制编码，并采用二进制运算12 8 位二进制无符号整数可表示的数值范围是( )。（A）0255（B） -128+127（C） -127+127（D）125613 浮点加减运算结果满足( )时，应作“ 机器零”处理。（A）尾数为“ 全 0”（B）阶码上溢（C）阶码下溢（D）A 或者 C14 某计算机主存容量为 64 KB，其中 ROM 区为 4 KB，其余为 RAM 区，按字
5、节编址。现要用 2 K8 位的 ROM 芯片和 4 K4 位的 RAM 芯片来设计该存储器，则需要上述规格的 ROM 芯片数和 RAM 芯片数分别是( )。（A）1、15（B） 2、15（C） 1、30（D）2、3015 动态 ROM 的刷新以( )为单位。（A）位（B）字节（C）行（D）整个 ROM16 对某一给定的程序，具有最高命中率的 Cache 替换算法是( )。（A）先进先出替换算法（B）最近最少使用替换算法（C）随机替换算法（D）无法确定17 某机字长 32 位，其主存储器容量为 64 MB，按字节编址，则该计算机的主存地址寄存器和主存数据寄存器的位数分别为( )。（A）26，32
6、（B） 26，8（C） 22，32（D）无法确定18 指令系统中设置多种不同的寻址方式，可以( )。（A）缩短指令字长（B）扩大寻址空间（C）提高编程灵活性（D）以上都包括19 某机器字长 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动加 1。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为06H，则该转移指令成功转移以后的目标地址是( )。（A）2006H（B） 2007H（C） 2008H（D）2009H20 微程序存放在 CPU 的哪个部件中( )。（A）主存储器（B）存
7、储器控制器（C）控制存储器（D）辅助存储器21 下列关于并行微程序控制器的说法正确的是( )。（A）现行微指令的执行与取下一条微指令的操作并行（B）现行微指令的执行与取下一条微指令的操作串行（C）两条或更多微指令的执行在时间上并行（D）两条或更多微指令的取微指令操作在时间上并行22 CPU 响应中断时需要保护断点，断点指的是( )。（A）中断服务程序的入口地址（B）程序计数器 PC 的内容（C） CPU 内各寄存器的内容（D）指令寄存器 IR 的内容23 为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是，( )不是一定需要。（A）向操作系统预定运行时间（B）将程序装入内存
8、（C）确定起始地址，并从这个地址开始执行指令（D）用控制台监控程序执行过程24 我们知道，有些 CPU 指令只能授权给操作系统内核运行，不允许普通用户程序使用，但是，以下操作中，( )可以不必具有此种特权。（A）设置定时器初值（B）触发 trap 指令（C）内存单元复位（D）关闭中断允许位25 下面关于虚拟存储管理的论述中，正确的是( )。（A）为了能让更多的进程同时运行，可以只装入 1030的进程映像，即启动运行（B）最佳页面置换算法是实现页式虚拟存储管理的常用算法（C）即使在多用户环境下，用户也可以运用机器指令访问任一合法的物理地址（D）为了提高内存保护的灵活性，内存保护通常由软件完成26
9、 下列关于进程的叙述，( )是最不符合操作系统对进程的理解。（A）进程是在多程序并行环境中的完整的程序（B）进程可以由程序、数据和进程控制块描述（C）线程 (THREAD)是一种特殊的进程（D）进程是程序在一个数据集合上运行的过程，是系统进行资源管理的一个独立单位27 两个合作进程无法利用( )交换数据。（A）数据库（B）消息传递系统（C）共享内存（D）高级语言程序设计中的全局变量28 页面置换算法( ) 可能会产生 Belady 异常现象。（A）先进先出算法 FIFO（B）最近最少使用算法 LRU（C）利用 reference bit 的近似的 LRU（D）最优算法 optimal29 下列
10、文件物理结构中，适合随机访问且易于文件扩展的是( )。（A）连续结构（B）索引结构（C）链式结构且磁盘块定长（D）链式结构且磁盘块变长30 一个文件的绝对路径名是从( )开始，逐步沿着每一级目录向下追溯，最好到指定文件的整个通路上所有子目录组成的一个有序组合。（A）当前目录（B）根目录（C）家目录(home directory)（D）磁盘驱动器编号31 操作系统为了管理文件，设计了文件控制块(FCB)。FCB 是执行系统调用( )时建立的。（A）create（B） open（C） read（D）write32 下面关于设备属性的论述中，正确的是( )。（A）字符设备的基本特征是可寻址到字节，即
11、能指定输入的源地址或输出的目标地址（B）共享设备必须是可寻址和可随机访问的设备（C）共享设备是同一时间内允许多个进程同时访问的设备（D）在分配共享设备和独占设备时都可能引起进程死锁33 在 OSI 参考模型中，会话层使用( )层的服务来完成自己的功能。（A）物理层（B）数据链路层（C）网络层（D）传输层34 （A）二进制编码（B）曼彻斯特编码（C）差分曼彻斯特编码（D）归零编码35 两个站点之间的距离是 10 000 km，信号在媒体上的传播速率为 2108ms ，线路的带宽是 10 kbps，现在发送一个 3 kb 的数据包，那么需要 ( )时间使得接收方收到数据。（A）035 s（B） 0
12、45 s（C） 085 s（D）135 s36 要发送的数据是 1101 0110 11，采用 CRC 校验，生成多项式是 10011，那么最终发送的数据应该是( ) 。（A）1101 0110 1110 10（B） 1101 0110 1101 10（C） 1101 0110 1111 10（D）1111 0011 0111 0037 一个以太网的帧数据长度为 20 字节，那么它的填充域长度是( )。（A）O 字节（B） 23 字节（C） 45 字节（D）26 字节38 主机甲和主机乙间已建立一个 TCP 连接，主机甲向主机乙发送了两个连续的TCP 段，分别包含 300 字节和 500 字节
13、的有效载荷，第一个段的序列号为 200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是( )。（A）500（B） 700（C） 800（D）1 00039 在 TELNET 协议中，用户发送的命令采用 TCP 传输到服务器，在 TCP 的数据包中，需要把( ) 符号位置移位，从而使服务器尽快响应命令。（A）SYN（B） URG（C） PSH（D）RST40 现在可以使用( ) 来编写 Web 页面。（A）HTTP（B） HTML（C） MIME（D）XML二、综合应用题41-47 小题，共 70 分。41 已知二叉树采用二叉链表方式存放，要求返回二叉树 T 的后序遍历访问的第一个结点，是
14、否可不用递归且不用栈来完成?请简述原因。42 设有一个双向链表 h，每个结点中除有 prior，data 和 next 三个域外，还有一个访问频度域 freq，在链表被起用之前，每个结点中的 freq 域都被初始化为零。每当进行 LocateNode(h，x)运算时，令元素值为 x 的结点中 freq 域中的值加一，并调整表中结点的次序，使其按访问频度的递减序列排序，以便使被频繁访问的结点总靠近表头，试写一符合上述要求的 LocateNode 运算的算法。43 写出单总线结构计算机中指令 MOVE R1，R2(含义是将寄存器 R1 中内容写入寄存器 R2 中)的操作步骤。44 某计算机系统的内
15、存储器由 Cache 和主存构成，Cache 的存取周期为 45 纳秒，主存的存取周期为 200 纳秒。已知在一段给定的时间内，CPU 共访问内存 4 500 次，其中 340 次访问主存。问：(1)Cache 的命中率是多少?(2)CPU 访问内存的平均时间是多少纳秒?(3)Cache-主存系统的效率是多少 ?(4)如果 Cache 为 8 行，主存 16 块，分别采用三种方式映射主存的第 9 块到 Cache中什么位置(写出 tag 值)?45 用 P-V 操作实现写优先读者-写者问题。46 某系统有三个进程 P1，P2 ，P3 并发工作，其中 P1 执行过程中需要使用资源S3，S1；P2
16、 需要使用资源 S1，S2；P3 需要使用资源 S2，S3。(1)如果进程推进过程中对资源分配不加以限制，会导致什么结果，为什么?(2)如何避免这种后果，列出所有可能的方法。47 描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退 N 帧协议，多帧滑动窗口与选择重传协议的区别。计算机专业（基础综合）模拟试卷 9 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 (1)p 结点的后继结点指向 p 结点原来后继结点的后继结点，(2)更新后的 p 结点的后继结点的前驱结点指向
17、 p。2 【正确答案】 A【试题解析】 860+(3*10+5)*4=1 000。3 【正确答案】 A【试题解析】 一般树中一个结点的孩子是无序的，所谓有序树是指树中任一结点的孩子是有序的。由树转换成二叉树的过程可知本题答案为 A。4 【正确答案】 B5 【正确答案】 B【试题解析】 由题意可知，A 的平衡因子为 1，又由于 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，由此可知，A 的左孩子上仅有右孩子，A 的右孩子上无左右孩子，在平衡二叉树中插入一个结点后造成不平衡，说明插入结点只能插在A 的左孩子的右孩子上，这种情形属于在左子树的右子树上插入结点的情形，即LR 型。6 【正确答案
18、】 B【试题解析】 由 m 阶 B-树性质可知，根结点至少有两棵子树，根结点之外的所有非终端结点至少有 m2 棵子树：则三阶 B-树的形状至少类似于一棵满二叉树，也即高度为 5 的三阶 B-树至少有(2 5-1=)31 个结点。7 【正确答案】 D8 【正确答案】 D【试题解析】 直接插入排序在已经排序好的序列的适当位置上插入关键字，因此可能需要移动元素。9 【正确答案】 A【试题解析】 只有 A 和 C 是 O(nlog n)的复杂度，但是快速排序在“最坏”的情况下蜕化为冒泡排序，其时间复杂度为 O(n2)。10 【正确答案】 C11 【正确答案】 B【试题解析】 存储程序原理是冯.诺依曼计
19、算机的基础，也是最根本特征。12 【正确答案】 A【试题解析】 8 位二进制无符号整数可表示的数值范围为 02 8-1，即 0255。13 【正确答案】 D【试题解析】 当尾数为“全 O”时，不论阶码为何值，该浮点数真值都为 0，应作“机器零”处理；当阶码下溢时，说明浮点数的真值小于该机可以表示的最小值，也应作“机器零”处理，故选 D。14 【正确答案】 D【试题解析】 根据题意可知，该机主存由 4 K8 位 ROM 和 60 K8 位 RAM 组成；又现有 ROM 芯片为 2 K8 位，故 ROM 需进行字扩展，用 2 片 2 K8 位ROM 串联组成 4 K8 位 ROM；RAM 芯片为
20、4 K4 位，故 RAM 需进行位字扩展，用 2 片 4 K4 位 RAM 并联构成 4 K8 位 RAM，再用 15 片 4 K8 位 RAM串联组成 60 K8 位 RAM，即共需 215=30 片 4 K4 位的 RAM 芯片。15 【正确答案】 C【试题解析】 动态 ROM 的刷新以行为单位。16 【正确答案】 D【试题解析】 选项中三种替换算法，平均来说 LRU 替换算法命中率最高，但对于某一个特定的程序，无法确定哪种替换算法命中率最高。17 【正确答案】 B【试题解析】 主存按字节编址，64 MB=2 268 位，故主存地址寄存器为 26 位，主存数据寄存器为 8 位。18 【正确
21、答案】 D【试题解析】 指令中设置多种寻址方式可以使程序员编程更加灵活，采用寄存器寻址等方式可以缩短指令字长，采用间址寻址等可以扩大指令寻址空间，故A、B、C 选项的内容都正确，选 D。19 【正确答案】 C【试题解析】 相对寻址通过将形式地址与程序计数器 PC 的内容相加得到有效地址，即 EA=(PC)+A；又机器字长 16 位，主存按字节编址，故该转移指令取出后的PC 值为 2000H+2=2002H；所以该转移指令成功后的目标地址为06H+2002H=2008H，选 C。20 【正确答案】 C【试题解析】 微程序存放在控制存储器中，选 C。注意区别存控与控存的区别，控存用来存放微程序，而
22、存控是用来管理协调 CPU、DMA 控制器等对主存储器访问的部件。21 【正确答案】 A【试题解析】 并行微程序控制器中，在执行现行微指令的同时，取下一条微指令，A 选项的描述正确。22 【正确答案】 B【试题解析】 CPU 在一条指令执行结束时响应中断，断点指的是程序计数器 PC的内容，也就是现行程序下一条将要执行指令的地址。23 【正确答案】 A【试题解析】 实时系统才需要预定 CPU 时间。24 【正确答案】 B【试题解析】 trap 命令的一种常见用途是在脚本程序被中断时完成清理工作。25 【正确答案】 A【试题解析】 B：最佳页面置换不是页式虚拟存储管理的常用算法，实现的代价较大；C
23、：在多用户环境下，系统应该对用户各自的数据和指令加以保护；D：内存保护通常由硬件完成，基址寄存器和界限寄存器等。26 【正确答案】 A【试题解析】 A 的说法片面。27 【正确答案】 D【试题解析】 两个进程各自拥有自己的程序段和数据段，即有各自的全局变量，所以不可能通过全局变量交换数据。28 【正确答案】 A【试题解析】 先进先出算法会出现 Belady 异常。29 【正确答案】 B【试题解析】 索引结构适合随机访问且易于文件扩展。30 【正确答案】 B【试题解析】 本题考查文件路径的概念。31 【正确答案】 B【试题解析】 文件控制块是调用 OPEN 时建立的。32 【正确答案】 B【试题
24、解析】 可寻址是块设备的基本特征，故 A 不对。共享设备是指一段时间内允许多个进程同时访问的设备，在同一时间内，即对某一时刻共享设备仍然只允许一个进程访问，故 C 不正确。分配共享设备是不会引起进程死锁的，故 D 不正确。33 【正确答案】 D【试题解析】 在 OSI 参考模型中，每一层使用它下层的服务来完成自己的功能，在会话层下面是传输层，所以会话层采用传输层的服务来完成自己的功能。34 【正确答案】 B【试题解析】 曼彻斯特编码每一周期分为两个相等的间隔。二进制“1”位在发送时，在第一个间隔中为高电压，在第二个间隔中为低电压。二进制“0”正好相反。35 【正确答案】 A【试题解析】 数据发
25、送分为发送延时和传输延时。在题目中发送延时为 3 00010 000=03 s 。传播延时为 10 000200 000 000=005 s ，所以总共需要035 s 来传输该数据包。36 【正确答案】 C【试题解析】 根据给出的除数，用 1101 0110 1100 00 除以 10011，得到的冗余码为 1110，添加在原来数据的最后发送出去。37 【正确答案】 D【试题解析】 以太网要求帧的最小长度是 64 字节，源地址、目标地址、类型和校验及域占用了 18 个字节，那么一个有 20 字节数据的以太网帧的长度就是 38 字节，还需要填充 26 字节。38 【正确答案】 D【试题解析】 总
26、共发送了 1 000 个字节，所以主机乙发送给主机甲的确认序号应该是 1 000。39 【正确答案】 C【试题解析】 PSH 位表示带有 PUSH 标志的数据，接收方在收到数据后应该立即请求将数据递交给应用程序，而不是将它缓存起来。40 【正确答案】 B【试题解析】 HTML(超文本标记语言)是用来描述格式化文档的语言，用来编写Web 页面。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 可以。原因：后序遍历的顺序是“左子树右子树根结点” 。因此，二叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设 p 是二叉树根结点的指针)。if(p!=null)whi
27、le(p-lchild!=nunll ll p-rchild!=null)while(p-lchild!=null)p=p-lchild；if(p-rehild!=null)p=p-rchild；return(p)； 返回后序序列第一个结点的指针42 【正确答案】 在 DLinkList 类型的定义中添加 freq 域(int 类型)，给该域初始化为 0。在每次查找到一个结点*p 时，使其 freq 域增 1，再在*p 结点的前面找到一个结点*q，它或是头结点或是满足 q-freq=p-freq，然后删除*p 结点，使其插入到*q 结点之后。算法描述如下：int LocateNode(DLin
28、kList*h，ElemType x)DLinkList *p=h-next，*q；while(p!=NULL&p-data!=x)p=p-next ； 找 data 域值为 x 的结点*pif(p=NULL) 未找到这样的结点return 0：else 找到这样的结点*pp- freq+； 频度增 1q=q-prior； *q 为*p 前驱结点if(q!=h) 若p 为第一个数据结点，则不移动while(q!=h&q-freq p-freq) 找到*q 结点，使 q-freq=p-freqq=q-prior；p- prior-next=p- next； 先删除*p 结点if(p-next!=
29、NULL)p- next-prior=p- prior；p- next=q-next； 将*p 结点插入到*q 结点之后if(q-next!=NULL)q- next-prior=p；q- next=p；p- prior=q；return 1；43 【正确答案】 操作步骤如下：第一步，送指令地址。将 PC 的值送 MAR。PCMAR第二步，计算下一条指令的地址。PC 加 1 送回 PC。PC+1PC第三步，读入指令。把存储器中读出来的指令经过 MDR 送入 IR 中。DBUSMDRIR第四步，送数据。R1R244 【正确答案】 (1)Cache 的命中率 h=Nc(Nc+Nm)=(4 500-
30、340)4 500=0 92=92(2)CPU 访存的平均时间 Ta=h*Tc+(1 一 h)*Tm=09245+(1-092)200=574ns(3)Cache主存系统的效率 e=TcTa=45574=078=78(4)全相联方式： 8 行中的任意行，tag=1 001直接方式：8 行中的第 1 行，tag=1组相联方式：第 1 组的任意行，tag=1045 【正确答案】 Semaphore mutex=1 ； 读文件计数的互斥Semaphore write=1； 写互斥Semaphore s=1； 用于实现“写优先”int count=0；Reader()while(1)p(s)；p(mu
31、tex)；if(count=0)p(write)；当第一个读者读文件时，阻止写者写count：v(mutex)；v(s)；读文件；p(mutex)；Count-：if(count=0)v(write)；当最后一个读者读完文件时，允许写者写v(mutex)；Writer()while(1)p(s)；p(write)；写文件；v(write)；v(s)； 46 【正确答案】 (1)可能会发生死锁。例如，进程 P1，P2 和 P3 分别占有了资源 S3， S1 和 S2，若各进程再申请资源会导致循环等待，即发生了死锁。(2)可以采用静态分配、按序分配、分配前检测、强行剥夺资源或采用银行家算法等方法消
32、除死锁。47 【正确答案】 滑动窗口是数据链路控制的一个重要机制，滑动窗口协议的基本原理就是在任意时刻，发送方都维持了一个连续的允许发送的帧的序号，称为发送窗口；同时，接收方也维持了一个连续的允许接收的帧的序号，称为接收窗口。发送方窗口内的序列号代表了那些已经被发送，但是还没有被确认的帧，或者是那些可以被发送的帧。滑动窗口机制在发送方和接收方分别设置发送窗口和接收窗口，在数据传输过程中受控地向前滑动，控制数据传输的过程。发送窗口用来对发方进行流量控制，其大小指明在收到对方 ACK 之前发送方最多可以发送多少个数据帧，只有序号在窗口覆盖范围内的数据帧是可以连续发送的。接收窗口控制哪些数据帧可以接
33、收，只有到达的数据帧的序号落在接收窗口之内时才可以被接收，否则将被丢弃。一般，当收方收到一个有序且无差错的帧后，接收窗口向前滑动，准备接收下一帧，并向发送方发出一个确认。为了提高效率，收方可以采用累计确认或捎带确认。当发方收到收方的确认后，发送窗口才能向前滑动，滑动的长度取决于收方确认的序号。向前滑动后，又有新的帧落入发送窗口，可以被发送。滑动后被确认正确收到的帧落在窗口的后边。停止一等待协议：当发送窗口和接收窗口的大小固定为 1 时，滑动窗口协议退化为停等协议。该协议规定发送方每发送一帧后就要停下来，等待接收方已正确接收的确认返回后才能继续发送下一帧。由于接收方需要判断接收到的帧是新发的帧还是重新发送的帧，因此发送方要为每一个帧加一个一比特位的序号。多帧滑动窗口与后退 N 帧协议：发送方连续发送若干个数据帧，不停下来等待应答帧。发送方在每发送完一个数据帧时都要设置超时定时器。只要在额定时间内仍未收到确认帧，就要重发相应的数据帧及其后的全部帧。多帧滑动窗口与选择重传协议：当接收方发现某帧出错后，其后继续送来的正确的帧接收方存放在一个缓冲区中，同时要求发送方重新传送出错的那一帧。一旦收到重新传来的帧后，就可以和原已存于缓冲区中的其余帧一并按正确的顺序递交高层。
