[考研类试卷]计算机专业（基础综合）模拟试卷18及答案与解析.doc

1、计算机专业（基础综合）模拟试卷 18 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。（A）单链表（B）带有头指针的单循环链表（C）双链表（D）带有尾指针的单循环链表2 循环队列用数组 A0m1存放其元素值，已知其头尾指针分别为 front 和rear，则当前元素个数为 ( )。（A）(rear-front+m)MOD m（B） rear-front+1（C） rear-front+1（D）rea

2、r-front3 二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0，1，8，列下标 j=1，2 ，10。设每个字符占一个字节。若 A 按行先存储，元素 A8，5的起始地址与当 A 按列先存储时起始地址相同的元素是 ( )。（A）A8 ，5（B） A3，1 0（C） A5，8（D）A0 ，94 已知某二叉树的中序、层序序列为 DBAFCE、FDEBCA，则该二叉树的后序序列为( )。（A）BCDEAF（B） ABDCEF（C） DBACEF（D）DABECF5 在平衡二叉树中，下面叙述正确的是( )。（A）任意结点的左、右子树结点数目相同（B）任意结点的左、右子树高度相同（C）

3、任意结点的左、右子树高度之差的绝对值不大于 1（D）不存在度为 1 的结点6 在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，采用顺序存储更节省空间的情况是( ) 。（A）d12n(k-n)（B） d12n(k-n)（C） d12n(k+n)（D）d12n(k+n)7 二叉树若用顺序方法存储，则下列 4 种算法中运算时间复杂度最小的是( )。（A）先序遍历二

4、叉树（B）判断两个指定位置的结点是否在同一层上（C）层次遍历二叉树（D）根据结点的值查找其存储位置8 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。（A）求关键路径的方法（B）求最短路径的迪杰斯特拉方法（C）深度优先遍历算法（D）广度优先遍历算法9 有一个有序表为1，3， 9，12，32，41，45，62，75，77，82，95，99 ，当折半查找值为 82 的结点时，查找成功的比较次数是( )。（A）1（B） 2（C） 4（D）810 下面关于 B-树和 B+树的叙述中，不正确的是( )。（A）B-树和 B+树都是平衡的多分树（B） B-树和 B+树都可用于文件的

5、索引结构（C） B-树和 B+树都能有效地支持随机检索（D）B-树和 B+树都能有效地支持顺序检索11 最好情况下的算法时间复杂度为 O(n)的是( )。（A）插入排序（B）归并排序（C）快速排序（D）堆排序12 对汇编语言程序员来说，以下部件中不透明的是( )。I指令缓冲器； 移位器； 通用寄存器；中断字寄存器； V乘法器； 先行进位链；（A）I、和（B） 、V 和（C） 和（D）I、V、13 已知定点小数 x 的补码为 1x 1x2x3，且 x一 075，则必有( )。（A）x 1=1，x 2=0，x 3=1（B） x1=1（C） x1=0，且 x2，x 3 不全为 1（D）x 1=0，x

6、 2=0，x 3=014 已知 X=一 08752 1，Y=06252 2，设浮点数格式为阶符 1 位，阶码 2 位，数符 1 位，尾数 3 位，通过补码求出 Z=X-Y 的二进制浮点数规格化结果是( )。（A）1011011（B） 0111011（C） 1001011（D）以上都不是15 地址总线为 A15(?葛位)-A0(低位)，若用 1 K4 的存储芯片组成 4K 字节存储器，并且以地址总线的高位做片选，则加在各存储芯片上的地址线是( )。（A）A15-A0（B） A11-A0（C） A9A0（D）A8-A016 设机器字长为 32 位，一个容量为 16MB 的存储器，CPU 按半字寻址

7、，其可寻址的单元数是( ) 。（A）2 24（B） 223（C） 222（D）2 2117 8086 的堆栈采取向下生长的方式，在压入时的操作是( )。（A）SP 先减，再压入数据（B）先压入数据，SP 再减（C） SP 先加，再压入数据（D）先压入数据，SP 再加18 若某条指令的操作数的地址就包含在指令中，则这条指令的寻址方式是( )。（A）直接寻址（B）立即寻址（C）寄存器寻址（D）间接寻址19 以下叙述中，不符合 RISC 指令系统特点的是( )。（A）指令长度固定，指令种类少（B）寻址方式种类丰富，指令功能尽量增强（C）设置大量通用寄存器，访问存储器指令简单（D）选取使用频率较高的一

8、些简单指令20 某数在计算机中用 8421 码表示为 011110001001，其真值是( )。（A）789（B） 789H（C） 1929（D）11110001001B21 传输一幅分辨率为 640480，65 万色的照片(图像)，假设采用数据传输速度为 56kbs，大约需要的时间是( )。（A）3482s（B） 4286s（C） 8571 s（D）8777s22 对输入输出系统产生决定性影响的基本要求是( )。I异步性；同步性；分时性；实时性；V设备相关性；设备无关性；（A），V（B） I，（C） ，（D） I，V23 操作系统可以为用户提供多种功能，而操作系统必须提供但是又不作为资源管理

9、的是( ) 。（A）编译程序（B）内外存分配（C）处理中断（D）使用处理机24 进程处于下列哪个等待状态时，它是处于非阻塞状态( )。（A）等待从键盘输入数据（B）等待协作进程的一个信号（C）等待操作系统分配 CPU 时间（D）等待网络数据进入内存25 有两个并发进程如下面所示，对于这段程序的运行，正确的说法是( )。PARBEGINvar x：integer；process P1 process P2var y，z： integer； var t，u：integer；BEGIN BEGINx：=1 ； x：=0 ；y：=0 ； t： =0；if x=1 then y：=y+1； if xke

10、y2keyn)； (3)奇数关键字顺序有序，偶数关键字顺序有序(key13，key 24212m，key m+1keym+2keyn，m 为中间位置)。42 设计一个算法，求无向图 G(采用邻接表存储)的连通分量个数。43 问：下列 IEEE 单精度浮点数所表示的十进制数分别是多少?(1)1011 1101 0100 0000 0000 000 0000 0000(2)0101 0101 0110 0000 0000 0000 0000 0000(3)1100 0001 1111 0000 0000 0000 0000 0000(4)0011 1010 1000 0000 0000 0000

11、0000 0000(5)0000 0000 0000 0000 0000 0000 0000 000044 某机主存容量为 1MB，两路组相连方式 (每组仅有两块 )的 Cache 容量为 64KB，每个数据块为 256 字节。CPU 要顺序访问的地址为 20124H、58100H 、60140H 和60138H 等 4 个主存字节单元中的数。已知访问开始前第 2 组(组号为 1)的地址阵列内容如下图所示，Cache 采用 LRU 替换策略。 说明Cache 的结构 (即分多少组、组内分多少块)，给出主存及 Cache 的地址格式。上述4 个数能否直接从 Cache 中读取，若能，请给出实际访

12、问的 Cache 地址。第 4 个数访问结束时，上图的内容如何变化。45 假设在一台单处理机上执行如下表所示的进程，且假定这些进程在时刻 0 以1，2，3，4，5 的顺序创建。时间单位为时间片，优先级以数值大者为优。 (1)请说明分别使用 FCFS、RR(时间片=1)、SPF 以及非抢夺式优先级调度算法时，这些进程的执行情况。 (2)争对上述每种调度算法，给出平均周转时间和平均带权周转时间。46 大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为 512B，有一个文件，包含了 590 个逻辑记录，每个记录占 255B；其中，为检索方便，采用成组法存储，在每个物理块上只存

13、放 2 个记录。，文件 A 在该文件目录中的位置如下图所示。 此树形文件目录结构由根目录结点和作为文件中间的目录结点以及作为信息文件的叶结点组成，每个目录项占 127B，每个物理块存放 4 个目录项。根目录的内容常驻内存。 (1)若文件采用隐式链接文件结构，设每块的连接字占 4B，存放在每个物理块的尾部。如果要将文件 A 读入内存，至少要读取几次硬盘?为什么? (2)若文件采用连续文件结构，如果要将文件 A 的逻辑记录号为 480 的记录读入内存，至少要读取几次硬盘 ?为什么?47 设有 A，B，C ，D 4 台主机都处在同一个物理网络中，A 主机的 IP 地址是1921552811 2，B

14、主机的 IP 地址是 1 921 5528120，C 主机的 IP 地址是 1 921 5528135，D 主机的 IP 地址是 19215528202。共同的子网掩码是 2552552 55224，请回答如下问题：(1)A，B ，C，D 4 台主机之间哪些可以直接通信?哪些需要通过设置网关(或路由器)才能通信 ?请画出网络连接示意图，并注明各个主机的子网地址和主机地址。(2)若要加入第 5 台主机 E，使它能与 D 直接通信，其 IP 地址的设定范围应是多少?(3)不改变 A 主机的物理位置，将其 IP 改为 1 9215528168，试问它的直接广播地址和本地广播地址各是多少?若使用本地广

15、播地址发送信息，请问哪些主机能够收到?(4)若要使主机 A，B ，C，D 在这个网上都能够直接通信，可采取什么办法?计算机专业（基础综合）模拟试卷 18 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，单链表、带有头指针的单循环链表、双链表都不合适，考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是 O(1)，所以，答案是 D。2 【正确答案】 A【试题解析】 少用一个元素的空间以区分队空和队满，求循环队列中元素的

16、个数的方法是 (rearfront+m)MOD m。3 【正确答案】 B【试题解析】 元素 A8，5的起始地址与当 A 按列先存储时的 Ai，j元素的起始地址相同，即 810+51=(j 一 1)9+i，将四个备选答案代入，可得正确答案。4 【正确答案】 B【试题解析】 按照遍历左子树要在遍历右子树之前进行的原则，根据访问根结点位置的不同，可得到二叉树的先序、中序和后序 3 种遍历方法。层序遍历时从根结点(第 1 层)出发，首先访问第 1 层的树根结点，然后从左到右依次访问第 2 层上的结点，其次是第 3 层上的结点，依次类推，自上而下、自左向右逐层访问各层上的结点。由层序序列可得：F 是树根

17、结点，D、E 是第 2 层结点；结合中序序列 DBA 构成 F 的左子树，CE 构成 F 的右子树，进一步有 C 是 E 的左结点、E 无右结点；这样 A 是第 4 层结点，据 DBA 序列有 B 是 D 的右结点，A 是 B 的右结点。易知后序序列为：ABDCEF。5 【正确答案】 C【试题解析】 平衡二叉树又称 AVL。它或者是一棵空树，或者是具有下列性质的二叉树：(1)左子树和右子树都是平衡二叉树；(2)左子树和右子树的深度之差的绝对值不超过 1。二叉树上结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度。可见，平衡二叉树上所有结点的平衡因子只可能是一 1，0，1。只要二叉树上

18、有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。6 【正确答案】 A【试题解析】 顺序存储所需空间为：kd ，三叉链表每个结点需要 3 个指针空间和1 个数据空间，即存储所需空间为：n(d+4*3) ，当 kd 时，顺序存储更节省空间。对完全二叉树，k 等于 n，显然不论 d 值多大多小，顺序存储更省空间。7 【正确答案】 B【试题解析】 选项 A、C、D 运算的时间复杂度都是 O(n)，而选项 B 的运算的时间复杂度为 O(1)，因为对于指定位置 p 和 q 的两个结点，判断是否在同一层上，只需判断两者是否成立。8 【正确答案】 C【试题解析】 当有向图中无回路时，从某顶点出发

19、进行深度优先遍历时，出栈的顺序(退出 DFSTraverse 算法)即为逆向的拓扑序列。9 【正确答案】 C【试题解析】 构造相应的判定树如下图所示，先找中间结点 45。再找 77，95，最后找到 82，经过 4 次比较。 10 【正确答案】 D【试题解析】 因为 B+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接，所以支持从根结点的随机检索和直接从叶子结点开始的顺序检索，但是 B 一树不具有这种结构特性，所以只支持从根结点的随机检索，而不支持直接从叶子结点开始的顺序检索。11 【正确答案】 A【试题解析】 直接插入排序在

20、最好情况下，即待排序列已按关键码有序，每趟操作只需 1 次比较，不需移动。总比较次数=n 一 1 次。所以时间复杂度为 0(n)。归并排序和堆排序在平均情况和最好情况下的时间复杂度为 0(nlogn)。快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为O(nz)。12 【正确答案】 C【试题解析】 汇编语言程序员在编程时，不需要考虑指令缓冲器、移位器、乘法器和先行进位链等部件，所以它们是“透明”的。13 【正确答案】 C【试题解析】 对于定点小数而言，当 x一 075，意味着一 1=1 then y：=y+1 ；4) z：=y ；5) x：=0；6) t：=0；7)

21、 if xadjlistvfirstarc ； p 指向顶点 v 的第一条边的终结点while(p!=NULL)if(visitedp 一adjvex=0) 若 p 一adjvex 顶点未访问，递归访问它DFS(G，P 一adjvex)；p=pnextarc； p 指向顶点 v 的下一条边的终结点int ConnNuml(ALGraph G) 求图 G 的连通分量int i，num=0 ；for(i=0；in；i+)visitedi=0；for(i=0；in；i+)if(visitedi=0)DFS(G，i)； 调用 DFS 算法num+；return(num)；解法二：采用广度优先遍历方法。

22、算法如下：void BFS(ALGraph G，int v)ArcNode*p；int QuMAX VERTEX_NUM，front=0，rear=0； 定义循环队列并初始化int w，i；for(i=0；in；i+) visitedi=0； 访问标志数组初始化prinf(”2d”，v)； 输出被访问顶点的编号visitedv=1； 置已访问标记rear=(rear+1)MAx_VERTEX NUM；Qurear=v； v 入队while(front!=rear) 若队列不空时循环front=(front+1)MAX_VERTEX_NUM ；w=Qufront； 出队并赋予 wP=G 一adj

23、listwfirstarc； 找与顶点 W 邻接的第一个顶点while(p!=NULL)if(visitedp 一adjvex：=0) 若当前邻接顶点未被访问printf(”2d”，P 一adjvex)； 访问相邻顶点visitedp 一adjvex=1 ； 置该顶点已被访问的标志rear=(rear+1)MAx_VERTEX_NUM ； 该顶点入队Qu rear=Padjvex；p=p-nextarc； 找下一个邻接顶点printf(”n”)；int ConnNum2(ALGraph G) 求图 G 的连通分量int i，num=0 ；for(i=0；in；i+)visitedi=0；for

24、(i=0；in；i+)if(visitedi=0)BFS(G，i)； 调用 BFS 算法num+：return(num)；【试题解析】 本题主要考查图的遍历的应用。对于无向图来说，深度优先遍历或者是广度优先遍历，若无向图是连通图，则一次遍历能够访问到图中的所有顶点，但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点，分别进行遍历，才能够访问到图中的所有顶点。因为在选择初始点的同时加上计数器，最后计数器的值即为连通分量个数。43 【正确答案】 (1)符号位为 1，表示这是一个负数。阶码字段=011 1 1

25、010B=122D，阶码真值=122 127=-5，尾数字段=100 0000 0000 0000 0000 0000B。所以十进制数值为：-(11) 22-5=-0046875。 (2)符号位为 0，表示这是一个正数。阶码字段=1 0101010B=1 70D，阶码真值 =170127=43，尾数字段=110 0000 0000 0000 0000 0000B。十进制数值为：(111) 2243 一 153910 13(表示为 4位有效数字形式)。 (3)符号位为 1，表示这是一个负数。阶码字段=10000011B-=131D，阶码真值=131 127=4，尾数字段=11 1 0000 00

26、00 0000 0000 0000。十进制数值为：-(1 11 1)224=-30 (4)符号位为 0，表示这是一个正数。阶码字段=01110101B=11 7D，阶码真值=117127=-10，尾数字段=000 0000 0000 0000 0000 0000。十进制数值为：(10) 22-10=00009766(表示为 4 位有效数字形式)。 (5)由于符号位为 0，阶码字段和尾数字段均为全 0，所以它表示机器零。【试题解析】 IEEE754 浮点数的格式如模拟试题二参考答案中第 15 题图所示，根据 IEEE754 标准，首先将 32 位的二进制数分为数符、阶码和尾数三部分，然后分别求出

27、阶码和尾数的真值，再加上数符。注意尾数用原码表示，且采用隐含尾数最高数位的方法。44 【正确答案】 Cache 分为 1 28 组，组内分成 2 块，主存和 Cache 的地址格式如下图所示。 CPU 要顺序访问的4 个数的地址写出二进制，可以发现： 20124H=00100 0000001 00100100B，组号为1，是第 2 组的块，根据第 44 题图可知，现在 Cache 内有这个块，第 1 次访问命中，实际访问的 Cache 地址为 0124H。 58100H=01011 0000001 00000000B，组号为 1，是第 2 组的块，根据第 44 题图可知，现在 Cache 内有

28、这个块。第 2 次访问命中，实际访问的 Cache 地址为 0100H。 60140H=01100 0000001 01000000B，组号为 1，是第 2 组的块，但 Cache 中没有这个块，第 3 次访问不命中，根据 LRU 算法，替换掉第 0 块位置上的数据块，变化后的地址阵列如下图所示。 60138H=01100 0000001 00111000B，组号为 1，是第 2 组的块，与上一个地址处于同一个块，此时这个块已调入 Cache 中，所以第 4 次访问命中，实际访问的 Cache 地址为0138 H。第 4 个数访问结束时，地址阵列的内容与刚才相同。 【试题解析】 主存容量为 1

29、MB，Cache 容量为 64KB，分成大小相等的数据块。设每个数据块为 256 字节，则主存共有 4098 块，Cache 共有 256 块，两路组相连方式(即每组仅有两块) ，所以 Cache 中共有 128 组，64K(2256)=128 组。45 【正确答案】 (1)对 FCFs，因在时刻 0 按 1，2，3，4，5 次序创建，因此，调度的次序为 1，2，3，4，5。对于 RR，按给定的时间片(为 1)，按先来先服务，其调度次序为 1，2，3，4，5，1，3，5，1，5，1，5，1，5，1，1，1，1，1。SPF算法调度的次序为 2，4，3，5，1。对于高优先级优先算法，其调度次序为4

30、，1，3，5，2。(2)计算平均周转时间和平均带权周转时间如下：FIFO 算法： 平均周转时间 =(10+11+1 3+14+1 9)5=134。平均带权周转时间=(1010+111+1 32+141+1 95)5=726RR 算法： 平均周转时间=(19+2+7+4+14)5=92。平均带权周转时间=(1 910+21+72+41+145)5=284SPF 算法： 平均周转时间=(19+1+4+2+9)5=7。平均带权周转时间=(1 910+11+42+21+95)5=174优先级算法： 平均周转时间=(11+1 9+1 3+1+18)5=1 24。平均带权周转时间=(1110+1 91+1

31、32+11+185)5=624【试题解析】 本题是一个简单的进程调度的计算题。预先告知了进程创建的时间，进程预计运行时间和进程的优先级。为便于计算，考虑进程的执行时间时，不考虑其 IO 的活动状况。由于基本计算比较简单，因此计算的数量稍多。对于 FIFO，即先来先服务，简单地按顺序进行运行即可；对于 RR，即时间片轮转，按时间片为 1 进行轮转即可；对于 SPF，即短进程优先，只需查看进程的预计运行时间即可，当预计运行时间相同时，按先来先服务处理；对于高优先级优先调度算法，按优先级调度即可，优先级相同按先来先服务调度，注意优先级表示法，有的情况下优先数越大优先级越高，有的反之，优先数越小优先级

32、越高。周转时间的计算按下式：周转时间一运行时间+等待时间。平均周转时间=周转时间进程数。带权周转时间=周转时间运行时间。(注意：实际这已经不是时间单位了，只是保留这种称呼)平均带权周转时间=带权周转时间进程数。46 【正确答案】 (1)当文件采用隐式链接文件结构时，首先计算找到文件 A 的读盘次数。从根目录 root 起，第一次读硬盘得到 bin，dev，home 等的信息和目录mary 的盘块地址。第二次读硬盘得到 doc 的地址，第三次读硬盘得到文件 A 的地址，第四次开始读文件 A 的内容。再计算把文件 A 读入内存的次数，所需读盘次数为 5 902=295 次。所以，为把文件 A 读入

33、内存需读盘次数 =295+3=298 次。(2)当文件为连续结构时，第三次就能读硬盘得到文件 A 的地址，而知道了文件A 的地址，通过计算，只需要 1 次读盘就可读出第 480 个逻辑记录。即共需要读取4 次硬盘，就能将文件 A 的逻辑记录号为 480 的记录读入内存。【试题解析】 隐式链接结构文件是将文件存放在外存上的非连续区域中，实质上就是一个链表，前一个物理块的最末端存放的是下一个物理块的指针，文件的结尾是结束标志“一 1”。而连续文件结构将文件存放在外存上的一个连续区域中，这两个存储形式的最大区别是隐式链接文件结构不能随机存取，必须先一次存取前面的记录才能够找到所需的记录。而连续文件结

34、构则可通过计算方式一次存取数据。(1)当文件采用隐式链接文件结构时，由题意知：磁盘物理块的大小为 512B，每个物理块存放 2 个记录，而文件 A 包含 590 个逻辑记录，每个记录占 255B，则要把文件 A 读入内存，所需读盘次数=5902：295 次。此外，还需计算找到文件 A的读盘次数。由于根目录在内存，所以从根目录 root 查起，不需要读硬盘，得到第一级目录 bin，dev，home 等的磁盘位置，第一次读硬盘将 horne 的目录内容读入，查到 mary 的盘块地址指针。根据该指针，第二次读硬盘得到 mary 目录的信息，找到 doc 的盘块地址指针，依此，第三次读硬盘得到 do

35、c 的信息，从中找到文件 A 的链表的起始指针。以后就读入文件 A 的内容。所以，把文件 A 读入内存需读盘次数为=295+3=298 次。(2)当文件为连续结构时，由于第一次读盘可获取 horne 的信息内容，据此，第二次读硬盘得到 mary 的内容，第三次读硬盘得到 doc 的内容，从中找到文件 A 的起始地址，通过计算，第 480 条逻辑记录在第 4802=240 号磁盘块中，只需要将文件 A 的起始地址加上 240 的偏移量，1 次读盘就可读出第 479 和第 480 号的逻辑记录。即共需要读取 4 次硬盘，就将文件 A 的逻辑记录号为 480 的记录读入内存。47 【正确答案】 (1

36、)只有 A 和 B 之间可以直接通信，c 和 D，以及它们同 A 和 B的通信必须经过路由器。 A 主机地址19215528112 子网地址 1921552896 B 主机地址 19215528120子网地址 1921552896 C 主机地址 19215528135 子网地址 19215528128 D 主机地址 19215528202 子网地址 19215528192 (2)地址范围是 19215528193 到 19215528222，注意要除掉19215528202。 (3)主机 A 的直接广播地址 19215528191，本地广播地址是 255255255255，若使用本地广播地址发送信息，所有主机都能够收到。(4)若希望 4 台主机直接通信，可以修改掩码为 25525525 50，这样 4 台主机就处于一个网络中，可以直接通信。