【考研类试卷】考研计算机学科专业基础综合-8-1及答案解析.doc

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

1、考研计算机学科专业基础综合-8-1 及答案解析(总分：147.99，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.在双链表中 p 所指的结点之前插入一个结点 q 的操作为_。 A.pprior=q;qnext=p;ppriornext=q;qprior=pprior; B.qprior=pprior;ppriornext=q;qnext=p;pprior=qnext; C.qnext=p;pnext=q;qpriOrnext=q;qnext=p; D.ppriornext=q;qnext=p;qprior=pprior;pprior=q;（分数：2.00）A.

2、B.C.D.2.下列关于链式栈的叙述中，错误的是_。链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取因为链式栈没有栈满问题，所以进行进栈操作，不需要判断任何条件在链式队列的出队操作中，需要修改尾指针的情况发生在空队列的时候 A.仅 B.仅、 C.仅 D.、（分数：2.00）A.B.C.D.3.设有一个二维数组 Amn在存储中按行优先存放(数组的每一个元素占一个空间)，假设 A00存放位置在 780(10)，A46存放位置在 1146(10)，则 A620在_位置(其中 (10)表明用十进制数表示)。 A.1342(10) B.1336(10) C.1338(10) D.1340(10)

3、（分数：2.00）A.B.C.D.4.一棵二叉树的前序遍历序列为 1234567，则它的中序遍历序列不可能是_。3124567 12345674135627 1436572 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.5.宽度为 27，高度为 4 的满 N 叉树总共有_个结点。 A.27 B.40 C.85 D.97（分数：2.00）A.B.C.D.6.对于一棵具有 n 个结点、度为 4 的树来说(树的层数从 1 开始)，以下说法正确的是_。树的高度至多为 n-3至少在某一层上正好有 4 个结点第 i 层上至多有 4(i-1)个结点 A.仅 B.仅、 C.仅 D.仅

4、、（分数：2.00）A.B.C.D.7.以下有关拓扑排序的说法中，错误的是_。如果某有向图存在环路，则该有向图一定不存在拓扑排序在拓扑排序算法中，既可以使用栈，也可以使用队列若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1 A.仅、 B.仅、 C.仅 D.仅（分数：2.00）A.B.C.D.8.无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有_个顶点。 A.11 B.12 C.15 D.16（分数：2.00）A.B.C.D.9.下图是一棵_。（分数：2.00）A.B.C.D.10.如果一台计算机具有多

5、个可并行运行的 CPU，就可以同时执行相互独立的任务。归并排序的各个归并段的归并也可并行执行，因此称归并排序是可并行执行的。那么以下的排序方法不可以并行执行的有_。基数排序 快速排序起泡排序 堆排序 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.11.假设有 5 个初始归并段，每个归并段有 20 个记录，采用 5 路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过_。 A.20 B.300 C.396 D.500（分数：2.00）A.B.C.D.12.已知定点整数 x 的原码为 1xn-1xn-2xn-3x0，且 x-2 n-1，则必有_。 A.xn-1=0

6、 B.xn-1=1 C.xn-1=0，且 x0x n-2不全为 0 D.xn-1=1，且 x0x n-2不全为 0（分数：2.00）A.B.C.D.13.在原码一位乘中，当乘数 Yi为 1 时，_。 A.被乘数连同符号位与原部分积相加后，右移一位 B.被乘数绝对值与原部分积相加后，右移一位 C.被乘数连同符号位右移一位后，再与原部分积相加 D.被乘数绝对值右移一位后，再与原部分积相加（分数：2.00）A.B.C.D.14.假定主存按字节编址，Cache 共有 64 行，采用 4 路组相联映射方式，主存块大小为 32 字节，所有编号都从 0 开始，则主存第 3000 号单元所在主存块对应的 Ca

7、che 组号是_。 A.1 B.5 C.13 D.29（分数：2.00）A.B.C.D.15.如图所示，若低位地址(A 0A 11)接在主存芯片地址引脚上，高位地址(A 12A 19)进行片选译码(其中 A14和 A16没有参加译码)，且片选信号低电平有效，则对如图所示的译码器，不属于其译码空间的地址为_。（分数：2.00）A.B.C.D.16.在计算机体系结构中，CPU 内部包括程序计数器(PC)、存储器数据寄存器(MDR)、指令寄存器(IR)和存储器地址寄存器(MAR)等。若 CPU 要执行的指令为 MOV X，#10(即将数值 10 传送到寄存器 x 中)，则 CPU首先要完成的操作是_

8、。 A.100R0 B.100MDR C.PCMAR D.PCIR（分数：2.00）A.B.C.D.17.假设某计算机的指令长度为 20 位，具有双操作数、单操作数和无操作数三种指令形式，每个操作数地址规定用 6 位表示，若操作码字段不固定，现已给出 m 条双操作数指令，n 条无操作数指令。在此情况下，这台计算机最多可以设计出_条单操作数指令。 A.28-m-n B.212-m-n C.(28-m)212-n D.(28-m)212-n/26（分数：2.00）A.B.C.D.18.流水线中有 3 类数据相关冲突：写后读相关、读后写相关、写后写相关。那么下列 3 组指令中存在读后写相关的是_。：

9、I1 SUB R1,R2,R3; (R2)-(R3)R1I2 ADD R4,R5,R1; (R5)+(R1)R4：I1 STA M,R2; (R2)M,M 为主存单元I2 ADD R2,R4,R5; (R4)+(R5)R2：I1 MUL R3,R2,R1; (R2)(R1)R3I2 SUB R3,R4,R5; (R4)-(R5)R3 A.仅、 B.仅 C.仅、 D.、（分数：2.00）A.B.C.D.19.某计算机采用 4 级中断，优先级从高到低分别为 1、2、3、4。若将优先级的顺序修改为 3、1、2、4，则此时 1、2、3、4 级的中断屏蔽字分别为多少?_。 A.1111、0111、001

10、1、0001 B.1101、0101、1111、0001 C.1101、0101、1011、0001 D.1101、1010、1111、0001（分数：2.00）A.B.C.D.20.下列属于微指令结构设计的目标是_。提高微程序的执行速度 缩短微指令的长度增大控制存储器的容量 A.仅、 B.仅、 C.仅、 D.、（分数：2.00）A.B.C.D.21.下列说法中，正确的是_。 A.CPU 通过控制单元 CU 来识别信息是地址还是数据 B.间接寻址第一次访问内存所得到的信息经过系统总线的地址总线传送到 CPU C.单总线结构中，可以不使用 I/O 指令 D.在异步总线中，传送操作由设备控制器控制

11、（分数：2.00）A.B.C.D.22.下列关于程序中断方式和 DMA 方式的叙述中，错误的是_。DMA 的优先级比程序中断的优先级要高程序中断方式需要保护现场，DMA 方式不需要保护现场程序中断方式的中断请求是为了报告 CPU 数据的传输结束，而 DMA 方式的中断请求完全是为了传送数据 A.仅 B.仅、 C.仅 D.仅、（分数：2.00）A.B.C.D.23.下列关于系统调用说法中，正确的是_。当操作系统完成用户请求的“系统调用”功能后，应使 CPU 从内核态转到用户态工作用户程序设计时，使用系统调用命令，该命令经过编译后，形成若干参数和屏蔽中断指令用户在编写程序时计划读取某个数据文件中的

12、 20 个数据块记录，需使用操作系统提供的系统调用接口用户程序创建一个新进程，需使用操作系统提供的系统调用接口 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.24.下列关于线程的叙述中，正确的是_。在采用轮转调度算法时，一进程拥有 10 个用户级线程，则在系统调度执行时间上占用 10 个时间片属于同一个进程的各个线程共享栈空间同一进程中的线程可以并发执行，但不同进程内的线程不可以并发执行线程的切换，不会引起进程的切换 A.仅、 B.仅、 C.仪、 D.全错（分数：2.00）A.B.C.D.25.在一单道批处理系统中，一组作业的提交时间和运行时间如下表所示。请问 3 种

13、作业调度算法的平均周转时间是_。 B作业提交时间和运行时间表/B作业 提交时间 运行时间1 8.0 1.02 8.5 0.53 9.0 0.24 9.1 0.1(1)先来先服务(2)短作业优先(3)响应比高者优先 A.0.5、0.875、0.825 B.0.85、0.875、0.625 C.0.85、0.675、0.825 D.0.5、0.675、0.625（分数：2.00）A.B.C.D.26.设有 10 个进程共享 n 个资源，每次允许 3 个进程同时使用该资源。试问：信号量的变化范围是_。 A.3n-10，3n B.n-10，n C.n-10/3，n D.3n-10，n（分数：2.00）

14、A.B.C.D.27.如果对经典的分页式存储管理策略的页表做细微改造，允许不同页表的页表项指向同一物理页帧，可能的结果有_。实现对可重入代码的共享只需要修改页表项，就能实现内存“复制”操作容易发生越界访问实现进程间通信 A.仅、 B.仅、 C.仅、 D.仅（分数：2.00）A.B.C.D.28.作业在执行中发生缺页中断，经操作系统处理后，应让其执行的指令是_。 A.被中断的前一条 B.被中断的那一条 C.被中断的后一条 D.启动时的第一条（分数：2.00）A.B.C.D.29.在一个请求分页系统中，采用 LRU 页面置换算法时，假如一个作业的页面走向为：1、3、2、1、1、3、5、1、3、2、

15、1、5。当分配给该作业的物理块数分别为 3 和 4 时，试计算在访问过程中所发生的缺页率是_。 A.35%，25% B.35%，50% C.50%，33% D.50%，25%（分数：2.00）A.B.C.D.30.下面关于目录检索的论述中，正确的叙述是_。 A.由于 Hash 法具有较快的检索速度，故现代操作系统中都用它来替代传统的顺序检索方法 B.在利用顺序检索法时，对树形目录应采用文件的路径名，且应从根目录开始逐级检索 C.在利用顺序检索法时，只要路径名的一个分量名未找到，便应停止查找 D.在顺序检索法时的查找完成后，即可得到文件的物理地址（分数：2.00）A.B.C.D.31.假设磁头的

16、当前位置是 100 磁道，磁头正向磁道号增加的方向移动，磁道号从最小的 0 号到最大的199 号。现有一个磁盘读写请求队列：98、183、37、122、10、124、65、67。若采用扫描算法，则平均寻道长度是_。 A.29 B.32 C.36 D.40（分数：2.00）A.B.C.D.32.下列几种类型的系统中，适合采用忙等待 I/O 的有_。专门用来控制单 I/O 设备的系统运行一个多任务操作系统的个人计算机作为一个负载很大的网络服务器的工作站 A.仅 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.33.一个信道每 1/8s 采样一次，传输信号共有 8 种变化状态，则最大的

17、数据传输率是_。 A.16bit/s B.24bit/s C.32bit/s D.48bit/s（分数：2.00）A.B.C.D.34.下列协议中，不会发生碰撞的是_。TDM ALOHACSMA CDMA A.仅 B.仅、 C.仅、 D.都有可能（分数：2.00）A.B.C.D.35.在二进制指数后退算法中，在 16 次碰撞之后，那么站点会在 0_之间选择一个随机数。 A.1023 B.215-1 C.216-1 D.以上都错误（分数：2.00）A.B.C.D.36.一个主机有两个 IP 地址，一个地址是 192.168.11.25，另一个地址可能是_。192168112 192.168.12

18、.251921681325 lV1921681425 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C.D.37.一个信道的数据率为 8000bit/s，单向传播时延为 20ms，要是停止一等待协议的信道利用率达到50%，则帧长至少是_。 A.80bit B.160bit C.240bit D.320bit（分数：2.00）A.B.C.D.38.IPv6 地址以 16 进制表示，每 4 个 16 进制数为一组，组之间用冒号分隔，下面的 IPv6 地址ADBF:0000:FEEA:0000:0000:00EA:00AC:DEED 的简化写法是_。 A.ADBF:0:FEEA:0

19、0:EA:AC:DEED B.ADBF:0:FEEA:EA:AC:DEED C.ADBF:0:FEEA:EA:AC:DEED D.ADBF:FEEA:EA:AC:DEED（分数：2.00）A.B.C.D.39.一个 TCP 连接下面使用 128kbit/s 的链路，其端到端时延为 32ms。经测试，发现吞吐率只有60kbit/s。则其发送窗口是_。 A.904B B.906B C.452B D.454B（分数：2.00）A.B.C.D.40.域名系统 DNS 的组成包括_。域名空间 分布式数据库域名服务器 从内部 IP 地址到外部 IP 地址的翻译程序 A.仅、 B.仅、 C.仅、 D.、（分

20、数：2.00）A.B.C.D.二、B综合应用题/B(总题数：6，分数：68.00)求解下面有向图的有关问题。（分数：9.99）(1).判断此有向图是否有强连通分量?若有请画出。（分数：3.33）_(2).画出此图的十字链表存储结构。（分数：3.33）_(3).简述基于图的深度优先搜索策略，并判别一个以邻接表存储的有向图是否存在顶点 vi到顶点 vj的路径的基本步骤。（分数：3.33）_假设有一带头结点的循环双链表表示的线性表 L=(a1，a 2，a n-1，a n)。设计在时间和空间上都尽可能高效的算法，将线性表 L 改造成L=(a1，a 3，a n，a 4，a 2)。要求：（分数：12.99

21、）(1).给出算法的基本设计思想。（分数：4.33）_(2).根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：4.33）_(3).说明你所设计算法的时间复杂度与空间复杂度。（分数：4.33）_假设某计算机所有指令都可用两个总线周期完成，一个总线周期用来取指令，另一个总线周期用来存取数据。假定总线宽度为 8 位，每个总线周期为250ns，因而每条指令的执行时间为 500ns，若该计算机中配置的磁盘每个磁道有 16 个 512 字节的扇区，磁盘旋转一圈的时间是 8.192ms。请回答下列问题：（分数：11.01）(1).在磁盘不工作时，主存频带空闲百分比是多少

22、?（分数：3.67）_(2).若采用周期挪用法进行 DMA 传送，则该计算机执行指令的速度由于 DMA 传送而降低了多少?（分数：3.67）_(3).若采用周期挪用法进行 DMA 传送，总线宽度为 16 位，则该计算机执行指令的速度由于 DMA 传送而降低了多少?（分数：3.67）_某双总线模型机如图所示。双总线分别记为 B1 和 B2；图中连线的方向标明数据通路及流向，并注有相应的控制信号(微命令)；A、B、C、D 为 4 个通用寄存器；X 为暂存器；M 为多路选择器，用于选择进入暂存器 x 的数据，存储器为双端口，分别面向总线 B1 和 B2。（分数：20.00）(1).写出该模型机的取指

23、令周期流程。（分数：4.00）_(2).分别指出指令 ADD(A)，(B)中源操作数和目的操作数的寻址方式，并写出该指令的执行流程。（分数：4.00）_(3).分别指出指令 ADD(A)，#N 中源操作数的寻址方式，并写出该指令的执行流程。（分数：4.00）_(4).写出指令 JMP Label(该指令完成(PC)+N(PC)，其中 N 为指令提供的位移量)的执行流程。（分数：4.00）_(5).给出一个单车道的简易桥，如图所示。 （分数：4.00）_设正在处理器上执行一个进程的页表如下表所示。表中的虚页号和物理块号是十进制数，起始页号(块号)均为 0。所有的地址均是存储器字节地址。页的大小为

24、 1024B。若发生缺页中断，使用 LRU 页面置换算法将缺页调入再进行地址变换，页表中访问字段记录本页最近已有多长时间未被访问。 B一个进程的页表/B页号 状态位 访问字段 修改位 物理块号012341010110203100007-2-0（分数：7.00）(1).详述在设有快表的请求分页存储器管理系统中，一个虚地址转换成物理内存地址的过程。（分数：3.50）_(2).根据给出的某进程的页表，系统给该进程分配的最大内存物理块数为 3，进程先后使用下面两个虚地址访问内存，其对应的物理内存地址分别是多少?请详述整个地址变换过程，并参照给出的页表，画出每次操作后的页表。(注：访问字段表示的是该页最

25、近已有多长时间未被访问) a)4475(写操作) b)1197(读操作)（分数：3.50）_设有 4 台主机 A、B、C 和 D 都处在同一物理网络中，它们的 IP 地址分别为192.155.28.112、192.155.28.120、192.155.28.135 和 192.155.28.202，子网掩码都是 255.255.255.224，请回答：（分数：7.00）(1).该网络的 4 台主机中哪些可以直接通信?哪些需要通过设置路由器才能通信?请画出网络连接示意图，并注明各个主机的子网地址和主机地址。（分数：1.75）_(2).若要加入第 5 台主机 E，使它能与主机 D 直接通信，则其

26、IP 地址的范围是多少?（分数：1.75）_(3).若不改变主机 A 的物理位置，而将其 IP 改为 192.155.28.168，则它的直接广播地址和本地广播地址各是多少?若使用本地广播地址发送信息，请问哪些主机能够收到?（分数：1.75）_(4).若要使该网络中的 4 台主机都能够直接通信，可采取什么办法?（分数：1.75）_考研计算机学科专业基础综合-8-1 答案解析(总分：147.99，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.在双链表中 p 所指的结点之前插入一个结点 q 的操作为_。 A.pprior=q;qnext=p;ppriornext=

27、q;qprior=pprior; B.qprior=pprior;ppriornext=q;qnext=p;pprior=qnext; C.qnext=p;pnext=q;qpriOrnext=q;qnext=p; D.ppriornext=q;qnext=p;qprior=pprior;pprior=q;（分数：2.00）A.B.C.D. 解析：解析 这种题目其实大部分考生都见过，解题步骤都是固定的。先画图，将选项给出的代码一个个进行检查，看看是否存在断链或者赋值错误的情况。但是这种题型有一种万能的解法，可以应对算法题。如果此题是算法题，考生可将此题的答案按照下面所给的解题技巧轻松地写出，完

28、全不必担心是否步骤会发生错误。2.下列关于链式栈的叙述中，错误的是_。链式栈只能顺序存取，而顺序栈不但能顺序存取，还能直接存取因为链式栈没有栈满问题，所以进行进栈操作，不需要判断任何条件在链式队列的出队操作中，需要修改尾指针的情况发生在空队列的时候 A.仅 B.仅、 C.仅 D.、（分数：2.00）A.B.C.D. 解析：解析 ：栈要求只能在表的一端(栈顶)访问、插入和删除，这决定了栈无论采用何种存储方法表示，只能顺序访问，不能直接存取，故错误。：每创建新的栈结点时还要判断是否动态分配成功，若不成功，则进栈操作失败。StackNode *s=new StackNode;if(s=NULL)pr

29、intf(“结点存储分配失败!/n“);故错误。：首先要清楚链式队列需要两个指针，即头指针和尾指针。当链队列需要插入元素时，在链式队列尾部插入一个新的结点，并且修改尾指针；当链队列需要删除元素时，在链式队列头部删除一个结点，并且修改头指针。所以当链式队列需要进行入队操作时，应该只需修改尾指针即可。但是有一种特殊情况(考生务必记住，因为不少考生在写链式队列出队的算法时，并没有考虑到去判断这种情况)，就是当此时只有一个元素时，不妨设此时链式队列有头结点，那么当唯一一个元素出队时，应该将头指针指向头结点，并且此时尾指针也是指向该唯一的元素，所以此时需要修改尾指针，并且使尾指针指向头结点，故错误。3.

30、设有一个二维数组 Amn在存储中按行优先存放(数组的每一个元素占一个空间)，假设 A00存放位置在 780(10)，A46存放位置在 1146(10)，则 A620在_位置(其中 (10)表明用十进制数表示)。 A.1342(10) B.1336(10) C.1338(10) D.1340(10)（分数：2.00）A.B.C.D. 解析：解析 由 Loc(4，6)=Loc(0，0)+(4n+6)1=780+(4n+6)=1146，n=(1146-780-6)/4=90，则可计算 Loc(6，20)=Loc(0，0)+(690+20)1=780+560=1340。4.一棵二叉树的前序遍历序列为

31、1234567，则它的中序遍历序列不可能是_。3124567 12345674135627 1436572 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C. D.解析：解析 由二叉树的前序遍历为 1234567 可知，该二叉树的根为结点 1，并且 2 为 1 的孩子结点。 ：假如 3124567 是该二叉树的中序遍历，那么 3 必然是 1 的左孩子，前序遍历的序列一定是 13，而前序遍历并没有以 13 开头，所以不可能是中序序列。 ：首先需要来证明一个知识点，什么情况下前序遍历和中序遍历是一样的。前序遍历是 tlr(根左右)，中序遍历是 ltr(左根右)，下面就从 tlr

32、和 ltr 着手。 (1)当没有左子树时，前序遍历变成了 tr，中序遍历也变成了 tr，故前序遍历和中序遍历一样。 (2)当没有右子树时，前序遍历变成 tl，中序遍历却变成了 lt，故前序遍历和中序遍历不一样。 综上分析，只要该二叉树没有左子树都能够满足前序遍历和中序遍历是一样的，故是可能的。 ：和的情况一样的分析，前序应该是以 14 开头，所以不可能是中序序列。 ：构造的二叉树如图所示。 * 因此，、不可能。5.宽度为 27，高度为 4 的满 N 叉树总共有_个结点。 A.27 B.40 C.85 D.97（分数：2.00）A.B. C.D.解析：解析 宽度是指树中每一层结点个数的最大值。满

33、 N 叉树的宽度为 27，即最底层的叶结点有 27个，该层结点最多。高度为 4，根据 N 叉树的性质，第 4 层有结点 N4-1=27，N=3。该满 3 叉树的结点个数为(3 4-1)/(3-1)=(81-1)/2=40。6.对于一棵具有 n 个结点、度为 4 的树来说(树的层数从 1 开始)，以下说法正确的是_。树的高度至多为 n-3至少在某一层上正好有 4 个结点第 i 层上至多有 4(i-1)个结点 A.仅 B.仅、 C.仅 D.仅、（分数：2.00）A. B.C.D.解析：解析 ：树中各结点的度的最大值称为树的度，所以对于度为 4 的树，必须存在某个结点有 4个分支结点。那么树最高的情

34、况应该类似于图 1，故正确。：这个不一定，比如图 2 所示，故错误。：就拿树的第三层来说，可以有 16 个结点，正确的答案应该是第 i 层上至多有 4i-1个结点，故错误。*图 1 树最高的情况*图 2 树的另外一种情况7.以下有关拓扑排序的说法中，错误的是_。如果某有向图存在环路，则该有向图一定不存在拓扑排序在拓扑排序算法中，既可以使用栈，也可以使用队列若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1 A.仅、 B.仅、 C.仅 D.仅（分数：2.00）A.B.C.D. 解析：解析 ：如果一个有向图存在环路，则肯定不会存在拓扑排序，因为该环路找不到入度为 0 的结点，拓扑排序

35、自然也就进行不下去了，故正确。 ：使用栈来表示拓扑排序的序列，最后的出栈序列是逆拓扑排序，只需逆转过来即可，只是效率比较低；使用队列时，出队序列就是拓扑排序序列，故使用栈和队列都是可以的，只是效率不等而已，故正确。 ：一个反例如图所示。该图的拓扑有序序列是唯一的，但各个顶点的入度和出度可以超出 1，故错误。 *8.无向图 G 有 23 条边，度为 4 的顶点有 5 个，度为 3 的顶点有 4 个，其余都是度为 2 的顶点，则图 G 最多有_个顶点。 A.11 B.12 C.15 D.16（分数：2.00）A.B.C.D. 解析：解析 顶点的度是指与此顶点相关联的边数，而每条边与两个顶点相关联。

36、23 条边最多有 46 个顶点(不排除多条边共享一个顶点)，设图 G 中有 n 个顶点，则有 45+34+(n-5-4)2232，解得n16。9.下图是一棵_。（分数：2.00）A. B.C.D.解析：解析 首先很明显不是 B+树，因为 B+树叶子结点本身依关键字的大小自小而大顺序链接，故排除B、D 选项。另外，B-树有一个性质为：m 阶 B-树的结点关键字数量最多为 m-1 个，但是图中有个结点有3 个关键字，也就是说此 B-树不可能是 3 阶，故选 A 选项。10.如果一台计算机具有多个可并行运行的 CPU，就可以同时执行相互独立的任务。归并排序的各个归并段的归并也可并行执行，因此称归并排

37、序是可并行执行的。那么以下的排序方法不可以并行执行的有_。基数排序 快速排序起泡排序 堆排序 A.仅、 B.仅、 C.仅、 D.仅、（分数：2.00）A.B.C. D.解析：解析 此题解题的关键是要知道哪种内部排序算法在执行的过程中，不能划分出子序列来进行并行的排序，快速排序在一趟划分了两个子序列后，各子序列又可并行执行排序。而其他 3 种排序不能划分成子序列来并行执行排序，故 4 个选项中，只有快速排序可以并行执行，故选 C 选项。11.假设有 5 个初始归并段，每个归并段有 20 个记录，采用 5 路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过_。 A.20 B.300 C.

38、396 D.500（分数：2.00）A.B. C.D.解析：解析 假设采用 k 路平衡归并排序算法，则败者树的高度为*。且在每次调整后，找下一个具有最小排序码记录时，最多做*次排序码比较。由题意可知，总共有 100 个记录，所以总的比较次数不超过*。 注意：采用败者树进行 k 路平衡归并的外部排序算法，其总的归并效率与 k 无关。12.已知定点整数 x 的原码为 1xn-1xn-2xn-3x0，且 x-2 n-1，则必有_。 A.xn-1=0 B.xn-1=1 C.xn-1=0，且 x0x n-2不全为 0 D.xn-1=1，且 x0x n-2不全为 0（分数：2.00）A. B.C.D.解析

39、：解析 由于 x 的符号位为 1，可知 x 为负数。又因为 x-2 n-1，可以得到 x 的绝对值必须小于 2n-1，所以 xn-1必须为 0。13.在原码一位乘中，当乘数 Yi为 1 时，_。 A.被乘数连同符号位与原部分积相加后，右移一位 B.被乘数绝对值与原部分积相加后，右移一位 C.被乘数连同符号位右移一位后，再与原部分积相加 D.被乘数绝对值右移一位后，再与原部分积相加（分数：2.00）A.B. C.D.解析：解析 具体请参看下表。 B原码、补码的乘法与除法/B运算符号大致种类位处理规则原码乘法符号位异或乘数Yi为1时，被乘数绝对值与原部分积相加后，右移一位；乘数Yi为0时，直接右移一位补码乘法不单独处(1)被乘理 数x符号任意，乘数y为正：同原码一位乘(2)被乘数x符号任意，乘数y为负：先将y补去掉符号位，进行原码一位乘操作，得到的结果进行+-x补校正(3)Booth算法：乘数连同符号位一同加入运算，并且增加一位附加位yn+1，其初始值为0。每一次计算时，需要查看yiyi+1：00和11时，部分积右移一位；01时，部分积加x补 ，再右移一位；10时，部分积加-x补 ，再右移一位。(注意：Booth算法在最后一步是不移位的，即如果出现00和11则计算结束；若出现10或01，则部