【考研类试卷】计算机专业（基础综合）模拟试卷105及答案解析.doc

《【考研类试卷】计算机专业（基础综合）模拟试卷105及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】计算机专业（基础综合）模拟试卷105及答案解析.doc（22页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业（基础综合）模拟试卷 105 及答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.关于线性表的顺序存储结构和链式存储结构的描述正确的是( )。线性表的顺序存储结构优于其链式存储结构链式存储结构比顺序存储结构可更方便地表示各种逻辑结构如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构顺序存储结构和链式存储结构都可以进行顺序存储（分数：2.00）A.仅、B.仅、C.仅、D.仅、3.相对于单向链表，使用双向链表存储线性

2、表，其优点是( )。提高查找速度节约存储空间数据的插入和删除更快速（分数：2.00）A.仅B.仅、C.仅D.仅、4.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，且深度为 h，则下列等式中正确的是( )。 n=h+m h+m=2 n m=2 h-1 n=2 h -1（分数：2.00）A.、B.、C.、D.、5.设一棵二叉树是由森林转换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点个数为( )。（分数：2.00）A.n-1B.nC.n+1D.n+26.若某完全二叉树的结点个数为 100，则第 60 个结点的度为( )（分数：2.00）A.0B.1C.2D.不确定7.下列关

3、于二叉树的说法中，错误的是( )。（分数：2.00）A.在二叉树的后序序列中最后一个结点一定是二叉树的根结点B.在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点C.在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点D.在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点8.已知一棵 5 阶 B 树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。（分数：2.00）A.3B.4C.5D.69.设图 G=(V，E)，其中： V=V 0 ，V 1 ，V 2 ，V 3 E=(V 0 ，V 1 )，(V 0 ，V 2 )，(V 0 ，V 3 )，(V 1 ，V

4、 3 ) 则从顶点 V 0 开始对图 G 的深度优先遍历序列总共有( )种。（分数：2.00）A.3B.4C.5D.210.下列说法中正确的是( )。对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为50顺序查找法只适合于顺序存储结构，不适合于链式存储结构折半查找过程所对应判定树是一棵完全二叉树理想情况下，散列表的平均比较次数可达到 1 次（分数：2.00）A.、B.、C.、D.、11.用某种排序方法对线性表24，88，21，48，15，27，69，35，20进行排序时，元素序列的变化情况如下：(1)24， 88， 21， 48， 15， 27， 69， 35， 20(2)2

5、0， 15， 21， 24， 48， 27， 69， 35， 88(3)15， 20， 21， 24， 35， 27， 48， 69， 88(4)15， 20， 21， 24， 27， 35， 48， 69， 88 所采用的排序方法是：（分数：2.00）A.快速排序B.选择排序C.希尔排序D.归并排序12.假设在磁盘上存放有 375000 个记录，做 5 路平衡归并排序，内存工作区能容纳 600 个记录，为把所有记录都排好序，需要做( )趟归并排序。（分数：2.00）A.3B.4C.5D.613.假定有两个带符号整数 x、y 用 8 位补码表示，x=63，y=-31，则 x-y 的机器数及其相

6、应的溢出标志 OF分别是( )。（分数：2.00）A.5DH、0B.5EH、0C.5DH、1D.5EH、114.十进制数-5 基于单精度浮点数 IEEE 754 标准的编码是( )。(注：单精度浮点数 IEEE 754 格式为符号位 1 位、尾数 23 位、阶码 8 位，且阶码用移码表示)（分数：2.00）A.(COA00000) 16B.(81D00000) 16C.(41500000) 16D.(01D00000) 1615.设机器数字长 16 位，有一个 C 语言程序段如下：int n=0xA1B6;unsigned int m=n;m=m1; m右移一位则在执行完该段程序后，m 的值为

7、( )（分数：2.00）A.50DBHB.FFB6HC.A186HD.DODBH16.地址总线为 A 15 (高位)A 0 (低位)，若用 1K4 位的存储芯片组成 4KB 的存储器，地址总线的高位做片选信号，则以下说法正确的是( )。 加在各存储芯片上的地址线是 A 11 A 0 加在各存储芯片上的地址线是 A 9 A 0 一共需要使用 8 片 1K4 位的存储芯片 一共需要使用 4 片 1K4位的存储芯片（分数：2.00）A.、B.、C.、D.、17.假设某计算机采用小端方式存储，按字节编址。一维数组 a 有 100 个元素，其类型为 float，存放在地址 C000 1000H 开始的连

8、续区域中，则最后一个数组元素的最高有效位(MSB)所在的地址应为( )。（分数：2.00）A.C000 1396HB.C000 1399HC.C000 118CHD.C000 118FH18.某机器中有 16 个寄存器，假设机器字长为 12 位，下列( )指令可以使用单字长指令来实现。 4条三寄存器指令 255 条单寄存器指令 16 条 0 寄存器指令（分数：2.00）A.仅、B.仅、C.仅、D.仅19.假设某条指令的一个操作数采用变址寻址方式，变址寄存器的内容为 8H，指令中给出的形式地址为1200H，地址为 1200H 的内存单元中的内容为 12FCH，地址为 12FCH 的内存单元的内容

9、为 3888H，则该操作数的有效地址为( )。（分数：2.00）A.1200HB.12FCHC.1208HD.3888H20.下列关于多核处理器说法中，正确的是( )。 多核表明一个处理器拥有多个芯片 维持 Cache一致性为其主要技术之一 多核之间共享一个统一地址空间（分数：2.00）A.仅、B.仅、C.仅、D.、和21.假设计算机系统中软盘以中断方式与 CPU 进行数据交换，主频为 50MHz，传输单位为 16 位，软盘的数据传输率为 50kBs。若每次数据传输的开销(包括中断响应和中断处理)为 100 个时钟周期，则软盘工作时 CPU 用于软盘数据传输的时间占整个 CPU 时间的百分比是

10、( )。（分数：2.00）A.0B.5C.15D.1522.某计算机有 8 个主设备竞争总线使用权，使用链式请求方式进行总线判优控制，则该机为实现总线判优控制需要的控制线数为( )。（分数：2.00）A.3B.16C.5D.无法确定23.下列说法中，错误的是( )。程序中断过程是由硬件和中断服务程序共同完成的每条指令的执行过程中，每个总线周期要检查一次有无中断请求检测有无 DMA 请求，一般安排在一条指令执行过程的末尾中断服务程序的最后指令是无条件转移指令（分数：2.00）A.仅、B.仅、C.仅、D.、24.下列说法中，正确的有( )。清除内存、设置时钟都是特权指令，只能在内核态(系统态、管态

11、)下执行用零作除数将产生中断用户态到内核态的转换是由硬件完成的在中断发生后，进入中断处理的程序可能是操作系统程序，也可能是应用程序（分数：2.00）A.仅、B.仅、C.仅、D.、25.并发进程执行的相对速度是( )。（分数：2.00）A.由进程的程序结构决定的B.由进程自己来控制的C.与进程调度策略有关的D.在进程被创建时确定的26.下列( )调度算法不适合交互式操作系统。（分数：2.00）A.高响应比优先B.高优先级优先C.时间片轮转D.先来先服务27.关于临界问题的一个算法(假设只有进程 P 0 和 P 1 可能会进入该临界区)如下(i 为 0 或 1)： repeat retry： if

12、(turn!=-1)turn=i； if(turn!=i)go to retry； turn=-1； 临界区； turn=0； 其他区域； unti1false； 该算法( )。（分数：2.00）A.不能保持进程互斥进入临界区，会出现“饥饿”B.不能保持进程互斥进入临界区，不会出现“饥饿”C.保证进程互斥进入临界区，会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”28.设 m 为同类资源数，n 为系统中并发进程数。当 n 个进程共享 m 个百斥资源时，每个进程最大需求为w，则下列情况会出现系统死锁的是( )。（分数：2.00）A.m=2，n=1，w=2B.m=2，n=2，w=1C.m

13、=4，n=3，w=2D.m=4，n=2，w=329.用外存加上内存之和与虚拟内存空间相比，其大小关系是( )。（分数：2.00）A.前者比后者大B.前者比后者小C.二者相等D.不一定30.有一个矩阵为 100200，即 a100200。在一个虚拟系统中，采用 LRU 算法。系统分给该进程 5 个页面来存储数据(不包含程序)，设每页可存放 200 个整数，该程序要对整个数组初始化，数组存储时是按行存放的。试计算下列两个程序各自的缺页次数(假定所有页都以请求方式调入)。 程序：for(i=0；i=99；i+) for(j=0；j=199；j+) A(ij：i*j；程序二：for(j=0；j=199

14、；j+) for(i=0；i=99；i+) Aij=i*j；（分数：2.00）A.100，200B.100，20 000C.200，100D.20 000，10031.当数据 (1)很少修改并且以随机顺序频繁地访问时(变长记录文件) (2)频繁地修改并且相对频繁地访问文件整体时(变长记录文件) (3)频繁顺序地访问文件元素(定长记录文件) 依次从访问速度、存储空间的使用和易于更新(添加删除修改)这几个方面考虑(访问速度最优先考虑，其次是存储开销，再次是易于更新)，为了达到最大效率，你将分别选择( )文件组织。（分数：2.00）A.、B.、C.、D.、32.某文件系统采用多级索引的方式组织文件的

15、数据存放，假定在文件的 i_node 中设有 13 个地址项，其中直接索引 10 项，一次间接索引项 1 项，二次间接索引项 1 项，三次间接索引项 1 项。数据块大小为4KB，磁盘地址用 4B 表示，请问这个文件系统允许的最大文件长度约为( )。（分数：2.00）A.1TB.2TC.3TD.4T33.下列有关通道技术的叙述中，不正确的是( )。通道可视为一种软件，其作用是提高了 CPU 的利用率编制好的通道程序是存放在主存储器中的通道又称 IO 处理机，它用于实现 CPU 与 IO 设备之间的信息传输通道程序是由一系列通道指令组成的（分数：2.00）A.仅、B.仅、C.仅、D.仅、34.通过

16、 IEEE 8023 局域网传送 ASCII 码信息“Good moming!”，若封装成一个 MAC 帧，则该帧的数据字段的有效字节为( )，需要填充( )个字节。（分数：2.00）A.12、34B.13、34C.13、33D.12、3335.在异步通信中，每个字符包含 1 位起始位、7 位数据位、1 位奇偶位和 2 位终止位，若每秒传送 100 个字符，采用 4 相位调制，则码元速率为( )。（分数：2.00）A.50 波特sB.500 波特sC.550 波特sD.1100 波特s36.假设有一个 12 位的海明码(采用偶校验编码，且最多只有 1 位发生错误)，其十六进制的值为 ACFH，

17、请问原来的值是( )。（分数：2.00）A.EFHB.AFHC.4FHD.BFH37.下列说法中，错误的是( )。0000 不能作为目的 IP 地址100255255255 不能作为源 IP 地址255255255255 可作为目的 IP 地址127001 既可以作为目的 IP 地址，也可以作为源 IP 电址（分数：2.00）A.仅B.仅、C.仅、D.仅、38.设有下面 4 条路由：17218129024、17218130024、17218132024 和17218133024，如果进行路由聚合，能覆盖这 4 条路由的地址是( )。（分数：2.00）A.17218128021B.1721812

18、8022C.17218130022D.1721813202339.在下列地址中，属于子网 86320012 的地址是( )。8633224123867965126866865216（分数：2.00）A.仅B.仅、C.仅、D.仅40.下列说法中，错误的是( )。TCP 不支持广播服务如果用户程序使用 UDP 协议，则应用层必须承担数据传输的可靠性UDP 数据报首部包含 UDP 源端口、UDP 目的端口、UDP 数据报首部长度和校验和TCP 协议采用的滑动窗口协议能够解决拥塞控制问题（分数：2.00）A.仅、B.仅、C.仅、D.仅、41.一个万维网网点有 1 千万个页面，平均每个页面有 10 个链

19、接。读取一个页面平均要 100ms。问要检索整个网点需要的时间最少为( )。（分数：2.00）A.10 3 sB.10 4 sC.10 5 sD.10 6 s二、综合应用题(总题数：8，分数：48.00)42.综合应用题 41-47 小题。_有如图 3-4 所示的带权有向图 G，试回答以下问题。 （分数：10.00）(1).给出图 G 的邻接表。（分数：2.00）_(2).给出从顶点 1 出发的深度优先遍历序列和广度优先遍历序列。（分数：2.00）_(3).给出 G 的一个拓扑序列。（分数：2.00）_(4).判断该图是否为强连通图。（分数：2.00）_(5).若用三元组存储邻接矩阵的数据，每

20、个三元组占 3 个字节，求共需多大空间?若用邻接矩阵存储时每个元素占 1 个字节，试比较哪种存储更省空间。（分数：2.00）_设二叉排序树用二叉链表表示，结点结构为(1child，data，rchild)，其中，data 为整形，指针 1child和 rchild 分别指向左右孩子。（分数：6.00）(1).试写出二叉链表的结点类型和指针类型的定义。（分数：2.00）_(2).给定一棵递增有序的二叉排序树(前序遍历得递增有序序列)，根指针为 root，试写出算法：将该二叉排序树转变为递减有序的二叉排序树(前序遍历得递减有序序列)，返回根指针。（分数：2.00）_(3).分析你所设计算法的时间复

21、杂度。（分数：2.00）_有 5 个中断源 D1、D2、D3、D4 和 D5，它们的中断优先级从高到低分别是 1 级、2 级、3 级、4 级和 5 级。这些中断源的中断优先级，正常情况下的中断屏蔽码和改变后的中断屏蔽码如表 3-4 所示。每个中断源有5 位中断屏蔽码，“0”表示该中断开放，“1”表示该中断被屏蔽。 （分数：8.00）(1).当使用正常的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么?实际的中断处理顺序是什么?（分数：2.00）_(2).当使用改变后的中断屏蔽码时，处理机响应各中断源的中断服务请求的顺序是什么?实际的中断处理顺序是什么?（分数：2.00）_(3).当

22、D1、D2、D3、D4、D5 这 5 个中断源同时发出中断请求时(采用改变后的中断屏蔽码)，试画出处理机响应中断源的中断服务请求和实际运行中断服务过程的示意图。（分数：2.00）_(4).假设从处理机响应中断源的中断服务请求开始，到运行中断服务程序中第一次开中断所用的时间为 1个单位时间，处理机运行中断服务程序的其他部分所用的时间为 4 个单位时间。当处理机在执行主程序时，中断源 D3、D4 和 D5 同时发出中断服务请求，经过 3 个单位时间后，中断源 D1 和 D2 同时发出中断服务请求。采用改变后的中断屏蔽码，画出处理机响应各中断源的中断服务请求和实际运行中断服务程序过程的示意图。（分数

23、：2.00）_某 16 位机器所使用的指令格式和寻址方式如图 3-5 所示，该机有两个 20 位基址寄存器，4 个 16 位变址寄存器，16 个 16 位通用寄存器。指令汇编格式中的 S(源)、D(目标)都是通用寄存器，M 是主存的一个单元。3 种指令的操作码分别是 MOV(OP)=(A)H，STA(OP)=(1B)H，LDA(OP)=(3C)H。MOV 是传送指令，STA 为写数指令，LDA 为读数指令。 （分数：6.00）(1).试分析 3 种指令的指令格式和寻址方式特点。（分数：2.00）_(2).处理机完成哪一种操作所花时间最短?哪一种操作所花时间最长?第二种指令的执行时间有时会等于第

24、三种指令的执行时间吗?（分数：2.00）_(3).下列情况中，每个十六进制指令字分别代表什么操作?并且描述此指令的作用。其中有些编码不正确，如何改正才能成为合法指令? FOF1H、3CD2H 2856H 6FD6H（分数：2.00）_假设有一个进程拥有两个线程(编号为 0 和 1)需要去访问同一个共享资源，为了避免竞争状态的问题，必须实现一种互斥机制，使得在任何时候只能有一个线程在访问这个资源。假设有如下的一段代码：int flag2； *flag 数组，初始化为 FALSE*Enter_Critica1_Section(int my_thread_id)，int other_thread_i

25、d) while (flag other_thread_id=TRUE)；*空循环语句* flagmy_thread_id=TRUE；Exit_Critica1_Section(int my_thread_id)，int other_thread_id) flagmy_thread_id=FALSE； 当一个线程想要访问临界资源时，就调用上述的这两个函数。比如，线程 0 的代码可能是这样的：Enter_Critica1_Section(0，1)；使用这个资源Exit_Critica1_Section(0，1)；做其他的事情 试问：（分数：6.00）(1).该共享资源可以是？（分数：2.00）_

26、(2).以上的这种机制能够实现资源互斥访问吗?为什么?（分数：2.00）_(3).如果把 Enter Critical Section()函数中的两条语句互换一下位置，结果会如何?（分数：2.00）_设一作业共有 5 页(04)，其中程序占 3 页(02 页)，常数占 1 页(第 3 页)，工作单元占 1 页(第 4 页)，它们依次放在外存的 45、46 页和 98、99、100 页。现程序段已分配在内存的 7、10、19 页，而常数区和工作区尚未获得内存。请回答下述问题：（分数：4.00）(1).页表应包含哪些项目?填写此页表。若工作区分配到内存的第 9 页，则页表如何变化?（分数：2.00

27、）_(2).在运行中，因需要使用常数而发生中断，假定此时内存无空闲页面，需要把第 9 页淘汰，操作系统应如何处理?页表又发生什么变化?（分数：2.00）_某单位局域网通过 ISP 提供的宽带线路与 Internet 相连，ISP 分配的公网 IP 地址为202117123229，局域网中一部分计算机通过代理服务器访问 Internet，而另一部分计算机不通过代理服务器直接访问 Internet，网络结构如图 3-6 所示。 （分数：8.00）(1).区域 A、B 的网络地址、子网掩码和默认网关是什么?（分数：2.00）_(2).如果该单位有一台需对外发布公共信息的 Web 服务器，应将其接入哪

28、个区域?在接入因特网时，哪个区域的计算机安全性更好?（分数：2.00）_(3).IP 地址为 192168036 和 2021171236 的计算机发送报文到 Internet 上，分别给出 IP 数据包的源 IP 地址。（分数：2.00）_(4).如果电信部门分配的公网 IP 地址为 202117123230，则网络连接应如何改动?（分数：2.00）_计算机专业（基础综合）模拟试卷 105 答案解析(总分：130.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.0

29、0）_解析：2.关于线性表的顺序存储结构和链式存储结构的描述正确的是( )。线性表的顺序存储结构优于其链式存储结构链式存储结构比顺序存储结构可更方便地表示各种逻辑结构如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构顺序存储结构和链式存储结构都可以进行顺序存储（分数：2.00）A.仅、B.仅、 C.仅、D.仅、解析：解析：线性表的两种存储结构各有优缺点，顺序存储结构支持随机存储，对于表内任意元素的存取具有较高的效率，这一点优于链式存储结构；链式存储结构不需要一次性分配所有空间给线性表，即支持动态存储，这一点优于顺序存储结构，故错误。 ：比如树和图等逻辑结构一般都是使用链式存储结构更为

30、方便，故正确。 ：链式存储应该更适合频繁使用插入和删除操作的线性表，因为不需要移动元素，仅需要修改指针即可；而线性存储可能需要大量移动元素，故错误。 ：顺序存储结构既可以随机存储也能顺序存储；链式存储结构只能顺序存储。 综上所述，、正确。3.相对于单向链表，使用双向链表存储线性表，其优点是( )。提高查找速度节约存储空间数据的插入和删除更快速（分数：2.00）A.仅B.仅、C.仅 D.仅、解析：解析：在双向链表中的查找仍然是顺序查找，故查找速度并没有提高；双向链表中有两个指针域，所以不但不能节约存储空间，相比单链表，还增加了空间；既然增加了空间，那必须是以空间来换取时间，导致的结果就是数据的插

31、入和删除将会更快速。4.对于一个满二叉树，共有 n 个结点和 m 个叶子结点，且深度为 h，则下列等式中正确的是( )。 n=h+m h+m=2 n m=2 h-1 n=2 h -1（分数：2.00）A.、B.、C.、D.、 解析：解析：对于深度为 h 的满二叉树，n=2 0 +2 1 +2 h-1 =2 h -1；另外，根据满二叉树的性质可知，m=2 h-1 ，故、正确；而、举反例很容易被排除。5.设一棵二叉树是由森林转换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点个数为( )。（分数：2.00）A.n-1B.nC.n+1 D.n+2解析：解析：首先，对于一棵树来讲，每个非

32、终端结点(除了树的根结点)转换成二叉树后都对应一个无右孩子的结点，因为一个非终端结点至少有一个孩子结点，其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点?因为根结点比较特殊，树转换成二叉树之后，根结点本身也将会没有右孩子。所以对于一棵具有 n 个非终端结点的树来讲，将其转换成二叉树之后，二叉树中无右孩子的结点个数为n+1 个。其实，此时已经可以选出答案了，因为一棵树也可以算是一个森林。 如果一个森林有多棵树(假设有 x 棵)，我们先把所有树的根结点拿出来。除根结点之外的非终端结点(n-x 个)转换成二叉树之后都是对应一个无右孩子的结点，可得到 n-x 个无右孩子的结点。但是，

33、x 个根结点是不足就对应 2x 个无右孩子的结点?显然不是，因为下一棵数将会成为上一棵树根结点的右孩子(见图 5-3)，所以只有森林的最后一棵树的根结点才会变成无右孩子的结点，故 x 个根结点将会得到 x+1 个无右孩子的根结点，所以一共可以得到 n-x+(x+1)=n+1 个无右孩子的根结点。6.若某完全二叉树的结点个数为 100，则第 60 个结点的度为( )（分数：2.00）A.0 B.1C.2D.不确定解析：解析：完全二叉树的结点个数为偶数，说明有 1 个度为 1 的结点。设 ni 为度是 i 的结点的个数，那么就有：n0+n2+1=100，n0=n2-1，解得：n0=55，n2=54

34、；又因为完全二叉树的编号是先度为 2 的结点，然后度为 1 的结点，最后才是叶子结点，即 154 是度为 2 的结点，55 是度为 1 的结点，56100 是度为0 的结点。因此，第 60 个结点为度为 0 的结点。7.下列关于二叉树的说法中，错误的是( )。（分数：2.00）A.在二叉树的后序序列中最后一个结点一定是二叉树的根结点B.在二叉树的中序序列中最后一个结点一定是二叉树的一个叶结点 C.在二叉树的前序序列中最后一个结点一定是二叉树的一个叶结点D.在二叉树的层序序列中最后一个结点一定是二叉树的一个叶结点解析：解析：A：后序遍历遵循 LRT，所以最后的一个结点肯定是该二叉树的根结点，故

35、A 选项正确。 B：中序遍历遵循 LTR，所以如果该根结点是右子女为空指针的话，就有可能最后访问的结点不是叶结点，例如：8.已知一棵 5 阶 B 树有 53 个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。（分数：2.00）A.3B.4C.5 D.6解析：解析：根据 B 树定义，m 阶 B 树除根之外所有的非终端结点至少有m2个结点，即 3 个，而根结点最少有两个结点，在每个结点的关键字是最少状态时，5 层的满树结点的关键字为2+32+323+323353，而 4 层满树结点关键字为 2+32+32353，故深度为 5。9.设图 G=(V，E)，其中： V=V 0 ，V 1

36、，V 2 ，V 3 E=(V 0 ，V 1 )，(V 0 ，V 2 )，(V 0 ，V 3 )，(V 1 ，V 3 ) 则从顶点 V 0 开始对图 G 的深度优先遍历序列总共有( )种。（分数：2.00）A.3B.4 C.5D.2解析：解析：此题的图为： 深度优先谝历的序列有 4 个：10.下列说法中正确的是( )。对有 2500 个记录的索引顺序表(分块表)进行查找，最理想的块长为50顺序查找法只适合于顺序存储结构，不适合于链式存储结构折半查找过程所对应判定树是一棵完全二叉树理想情况下，散列表的平均比较次数可达到 1 次（分数：2.00）A.、 B.、C.、D.、解析：解析：分块查找的平均查

37、找长度不仅和表的总长度 n 有关，而且和所分的子表个数有关，对于n 给定的情况下，s 取 时，平均查长度取得最小值11.用某种排序方法对线性表24，88，21，48，15，27，69，35，20进行排序时，元素序列的变化情况如下：(1)24， 88， 21， 48， 15， 27， 69， 35， 20(2)20， 15， 21， 24， 48， 27， 69， 35， 88(3)15， 20， 21， 24， 35， 27， 48， 69， 88(4)15， 20， 21， 24， 27， 35， 48， 69， 88 所采用的排序方法是：（分数：2.00）A.快速排序 B.选择排序C.希尔

38、排序D.归并排序解析：解析：本题我们不容易一次就确定到底采用哪种排序方法，那么就可以采用排除法，按照四个选项当中的算法去模拟一遍。如果是选择排序，则在 4 轮排序过程中无法得到最后的排序结构，因为选择排序每次只能确定一个元素的位置；如果是希尔排序不可能在第一步将 20 换到第一位。同理也不是归并排序。这 4 次过程中是子序列同时进行的快速排序。12.假设在磁盘上存放有 375000 个记录，做 5 路平衡归并排序，内存工作区能容纳 600 个记录，为把所有记录都排好序，需要做( )趟归并排序。（分数：2.00）A.3B.4 C.5D.6解析：解析：假设做 m 路平衡归并排序，且有 n 个初始归

39、并段，则归并趟数为log m n。所以此题只需求出初始归并段 n 即可，n=375000600=625。故归并趟数为log 5 625=4。13.假定有两个带符号整数 x、y 用 8 位补码表示，x=63，y=-31，则 x-y 的机器数及其相应的溢出标志 OF分别是( )。（分数：2.00）A.5DH、0B.5EH、0 C.5DH、1D.5EH、1解析：解析：因为 x=63，y=-31，则 x-y=94，而带符号的 8 位整数补码所能表示的范围是-128127，所以 94 在其范围之内，没有溢出，即 OF 标志为 0，将结果转化为机器数为 5EH。 此种题型在 2009 年，2014 年的统

40、考卷当中已经出现，现在对于这种在选择题当中出现补码加减运算或者是涉及浮点数加减计算的情况，总结如下： (1)涉及浮点数计算或者是复杂的补码的计算，不要立刻去按照补码的规则和浮点数加减规则去运算，不要关注题干给你的一些无用信息(比如浮点数的各运算步骤之类的)。 (2)观察题干给你的两个数，可以试着加加看，或者减减看，看结果到底为多少，然后看这个结果是否在寄存器所能表示的数(一般是补码)的范围之内。如果不能表示，那一定是溢出了，如果能表示，再把这个结果化为二进制或者十六进制。14.十进制数-5 基于单精度浮点数 IEEE 754 标准的编码是( )。(注：单精度浮点数 IEEE 754 格式为符号位 1 位、尾数 23 位、阶码 8 位，且阶码用移码表示)（分数：2.00）A.(COA00000) 16 B.(81D000