《江苏科技大学计算机科学与工程学院计算机综合历考研真题大全.pdf》由会员分享，可在线阅读，更多相关《江苏科技大学计算机科学与工程学院计算机综合历考研真题大全.pdf（107页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 目 录 第一部分 江苏科技大学计算机科学与工程学院 845 计算机基础综合历年考研真题汇编.2014年江苏科技大学计算机科学与工程学院845计算机基础综合考研真题.2013年江苏科技大学计算机科学与工程学院845计算机基础综合考研真题.1第二部分 全国硕士研究生入学统一考试 408 计算机学科专业基础综合历年真题及详解.22012 年全国硕士研究生入学统一考试 408 计算机学科专业基础综合真题.22012年全国硕士研究生入学统一考试 408计算机学科专业基础综合真题及详解.32011 年全国硕士研究生入学统一考试 408 计算机学科专业基础综合真题.52011年全国硕士研究生入学统一考试
2、408计算机学科专业基础综合真题及详解.62010 年全国硕士研究生入学统一考试 408 计算机学科专业基础综合真题.82010年全国硕士研究生入学统一考试 408计算机学科专业基础综合真题及详解.92009 年全国硕士研究生入学统一考试 408 计算机学科专业基础综合真题.102009年全国硕士研究生入学统一考试 408计算机学科专业基础综合真题及详解.11说明：江苏科技大学 2012 年之前参加全国统考 408 计算机学科专业基础综合，2013 年开始自主命题，科目改为 845 计算机基础综合，2015 年之后，科目名改为计算机综合。为帮助考生全面复习，特提供 20092012 年 408
3、 计算机学科专业基础综合真题及详解。江苏科技大学计算机科学与工程学院 845 计算机综合历年考研真题汇编 最新资料，WORD 格式，可编辑修改！第一部分 江苏科技大学计算机科学与工程学院 845计算机基础综合历年考研真题汇编 2014 年江苏科技大学计算机科学与工程学院 845 计算机基础综合考研真题 2013 年江苏科技大学计算机科学与工程学院 845 计算机基础综合考研真题 第二部分 全国硕士研究生入学统一考试 408计算机学科专业基础综合历年真题及详解 2012 年全国硕士研究生入学统一考试 408 计算机学科专业基础综合真题 一、单项选择题：l40 小题。每小题 2 分，共 80 分。
4、下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1求整数 n（n0）阶乘的算法如下，其时间复杂度是（）。AO（log2n）B0（n）CO（nlog2n）DO（n2）2已知操作符包括+、-、*、（和）。将中缀表达式 a+b-a*（c+d）e-f）+g 转换为等价的后缀表达式 ab+acd+ef-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。A5 B7 C8 D11 3若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点（）。A只有 e B有 e、b C有 e、
5、c D无法确定 4若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（）。A12 B20 C32 D33 5 对有 2 个顶点 e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。A0（n）B0（e）CO（n+e）DO（ne）6若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。A存在，且唯一 B存在，且不唯一不唯一 C存在，可能不唯一 D无法确定是否存在 7有向带权图如题 7 图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，
6、第 二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是（）。题 7 图有向带权图 Ad,e,f Be，d，f Cf，d，e Df，e，d 8下列关于最小生成树的叙述中，正确的是（）。最小生成树的代价唯一 所有权值最小的边一定会出现在所有的最小生成树中 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同 A仅 B仅 C仅、D仅、9设有一棵 3 阶 B 树，如题 9 图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是（）。题 9 图 3 二叉树图 A60 B60，62
7、C62，65 D65 10排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。简单选择排序 希尔排序 快速排序 堆排 V二路归并排序 A仅、B仅、C仅、D仅、11对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。A排序的总趟数 B元素的移动次数 C使用辅助空间的数量 D元素之间的比较次数 12假定基准程序 A 在某计算机上的运行时间为 l00 秒，其中 90 秒为 CPU时间，其余为 I/O 时间。若 CPU 速度提高 50，I/O 速度不变，则运行基准程序 A 所耗费的时间
8、是（）。A55 秒 B60 秒 C65 秒 D70 秒 13假定编译器规定 int 和 short 类型长度分别为 32 位和 16 位，执行下列 C 语言语句：unsigned short X65530；unsigned int yX：得到 y 的机器数为（）。A00007FFAH B0000FFFAH CFFFF7FFAH DFFFFFFFAH 14float 类型（即 IEEE754 单精度浮点数格式）能表示的最大正整数是（）。A2126-2103 B2127-2104 C2127-2103 D2128-2104 15某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int
9、 和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储。某 C语言程序段如下：若 record 变量的首地址为 0 xC008，则地址 0 xC008 中内容及 record.c 的地址分别为（）。A0 x00、0 xC00D B0 x00、0 xCOOE C0 x11、0 xC00D D0 x11、0 xC00E 16下列关于闪存（FlashMemory）的叙述中，错误的是（）。A信息可读可写，并且读、写速度一样快 B存储元由 MOS 管组成，是一种半导体存储器 C掉电后信息不丢失，是一种非易失性存储器 D采用随机访问方式，可替代计算机外部存储器 17假设某计算机按字编
10、址，Cache 有 4 个行，Cache 和主存之间交换的块大小为 l 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换算法，当访问的主存地址依次为 0，4，8，2，0，6，8，6，4，8 时，命中Cache 的次数是（）。A1 B2 C3 D4 18某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有（）。A5 位 B6 位 C15 位 D33 位 19某同步总线的时钟频率为 l00MHz，宽度为 32 位，地址数据线复用，每传
11、输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 l28 位数据所需要的时间至少是（）。）。A20ns B40ns C50ns D80ns 20下列关于 USB 总线特性的描述中，错误的是（）。A可实现外设的即插即用和热插拔 B可通过级联方式连接多台外设 C是一种通信总线，可连接不同外设 D同时可传输 2 位数据，数据传输率高 21下列选项中，在 IO 总线的数据线上传输的信息包括（）。IO 接口中的命令字 I0 接口中的状态字 中断类型号 A仅、B仅、C仅、D、22响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（）。开关中断
12、保存通用寄存器的内容 形成中断服务程序入口地址并送 PC A仅、B仅、C仅、D、23下列选项中，不可能在用户态发生的事件是（）。A系统调用 B外部中断 C进程切换 D缺页 24中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。A程序计数器 B程序状态字寄存器 C通用数据寄存器 D通用地址寄存器 25下列关于虚拟存储的叙述中，正确的是（）。A虚拟存储只能基于连续分配技术 B虚拟存储只能基于非连续分配技术 C虚拟存储容量只受外存容量的限制 D虚拟存储容量只受内存容量的限制 26 操作系统的 IO 子系统通常由四个层次组成，每一层明确定义了与邻近层次的
13、接口。其合理的层次组织排列顺序是（）。A用户级 IO 软件、设备无关软件、设备驱动程序、中断处理程序 B用户级 IO 软件、设备无关软件、中断处理程序、设备驱动程序 C用户级 IO 软件、设备驱动程序、设备无关软件、中断处理程序 D用户级 IO 软件、中断处理程序、设备无关软件、设备驱动程序 27假设 5 个进程 P0、Pl、P2、P3、P4 共享三类资源 Rl、R2、R3，这些资源总数分别为 l8、6、22。T0时刻的资源分配情况如题 27 表所示，此时存在的一个安全序列是（）。题 27 表资源分配情况表 已分配资源 资源最大需求 进程 R1 R2 R3 R1 R2 R3 PO 3 2 3
14、5 5 10 P1 4 O 3 5 3 6 P2 4 O 5 4 O 11 P3 2 O 4 4 2 5 P4 3 1 4 4 2 4 AP0，P2，P4，Pl，P3 BPl，P0，P3，P4，P2 CP2，Pl，P0，P3，P4 DP3，P4，P2，Pl，P0P0 28 若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）。若该文件的数据不在内存，则该进程进入睡眠等待状态；请求 read系统调用会导致 CPU 从用户态切换到核心态；read 系统调用的参数应包含文件的名称 A仅、B仅、C仅、D、和 29一个多道批处理系统中仅有 Pl 和 P2
15、 两个作业，P2 比 Pl 晚 5ms 到达。它们的计算和 I0 操作顺序如下：P1：计算 60ms，IO 80ms，计算 20ms；P2：计算 120ms，IO 40ms，计算 40ms 若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。A240ms B260ms C340ms D360ms 30若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。A在进程结束时能进行处理机调度 B创建新进程后能进行处理机调度 C在进程处于临界区时不能进行处理机调度 D在系统调用完成并返回用户态时能进行处理机调度 31下列关于进程和线程的叙述中，正确的是（）。A不管
16、系统是否支持线程，进程都是资源分配的基本单位 B线程是资源分配的基本单位，进程是调度的基本单位 C系统级线程和用户级线程的切换都需要内核的支持 D同一进程中的各个线程拥有各自不同的地址空间 32下列选项中，不能改善磁盘设备 IO 性能的是（）。A重排 I0 请求次序 B在一个磁盘上设置多个分区 C预读和滞后写 D优化文件物理块的分布 33在 TCPIP 体系结构中，直接为 ICMP 提供服务的协议是（）。APPP BIP CUDP DTCP 34在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（）。A机械特性 B功能特性 C过程特性 D电气特性 35以太网的 MAC 协议提供的是（）
17、。A无连接不可靠服务 B无连接可靠服务 C有连接不可靠服务 D有连接可靠服务 36两台主机之间的数据链路层采用后退 N 帧协议（GBN）传输数据，数据传输速率为 l6kbps，单向传播时延为 270ms，数据帧长度范围是 128512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（）。A5 B4 C3 D237 37下列关于 IP 路由器功能的描述中，正确的是（）。运行路由协议，设置路由表；监测到拥塞时，合理丢弃IP 分组；对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失；根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出
18、线路上。A仅、B仅、C仅、D、38ARP 协议的功能是（）。A根据 IP 地址查询 MAC 地址 B根据 MAC 地址查询 IP 地址 C根据域名查询 IP 地址 D根据 IP 地址查询域名 39某主机的 IP 地址为 180.80.77.55，子网掩码为 255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（）。A180.80.76.0 B180.80.76.255 C180.80.77.255 D180.80.79.255 40 若用户 l 与用户 2 之间发送和接收电子邮件的过程如题 40 图所示，则图中、阶段分别使用的应用层协议可以是（）。题 40 图电子邮件
19、发送接收示意图 ASMTP、SMTP、SMTP BPOP3、SMTP、POP3 CPOP3、SMTP、SMTP DSMTP、SMTP、POP3 二、综合应用题：41-47 小题。共 70 分。41（10 分）设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（1）给出完整的合并过程，并求出最坏情况下比较的总次数。（2）根据你的合并过程，描述 n（n2）个不等长升序表的合并策略，并说明理由。42（13
20、分）假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如题 42 图所示。题 42 图存储映像示意图 设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为data，next，请设计一个时间上尽可能高效的算法，找出由 strl 和 str2 所指的两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度。43（11 分）假
21、定某计算机的 CPU 主频为 80MHz，CPI 为 4，并且平均每条指令访存 1.5 次，主存与 Cache 之间交换的块大小为 168，Cache 的命中率为99，存储器总线宽度为 32 位。请回答下列问题。（1）该计算机的 MIPS 数是多少?平均每秒 Cache 缺失的次数是多少?在不考虑 DMA 传送的情况下，主存带宽至少达到多少才能满足 CPU 的访存要求?（2）假定在 Cache 缺失的情况下访问主存时，存在 0.0005的缺页率，则 CPU 平均每秒产生多少次缺页异常?若页面大小为 4KB，每次缺页都需要访问磁盘，访问磁盘时 DMA 传送采用周期挪用方式，磁盘 IO 接口的数据
22、缓冲寄存器为 32 位，则磁盘 IO 接口平均每秒发出的 DMA 请求次数至少是多少?（3）CPU 和 DMA 控制器同时要求使用存储器总线时，哪个优先级更高?为什么?（4）为了提高性能，主存采用 4 体交叉存储模式，工作时每 l/4 个存储周期启动一个体。若每个体的存储周期为 50ns，则该主存能提供的最大带宽是多少?44（12 分）某 16 位计算机中，带符号整数用补码表示，数据 Cache 和指令 Cache 分离。题 44 表给出了指令系统中部分指令格式，其中 Rs 和 Rd 表示寄存器，mem 表示存储单元地址，（X）表示寄存器 X 或存储单元 X 的内容。表 指令系统中部分指令格式
23、 名称 指令的汇编格式 指令功能 加法指令 ADD Rs，Rd（Rs）+（Rd）Rd 算术逻辑左移 SHLR d 2*（Rd）Rd 算术右移 SHRR d（Rd）2Rd 取数指令 LOAD RD，mem（mem）Rd 存数指令 STORE Rs，mem（Rs）mem 该计算机采用 5 段流水方式执行指令，各流水段分别是取指（IF）、译码读寄存器（ID）、执行计算有效地址（EX）、访问存储器（M）和结果写回寄存器（WB），流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。（1）若 int 型变量 x 的值为
24、-513，存放在寄存器 Rl 中，则执行指令“SHR Rl”后，Rl 的内容是多少?（用十六进制表示）（2）若某个时间段中，有连续的 4 条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这 4 条指令所需的时钟周期数为多少?（3）若高级语言程序中某赋值语句为 xa+b，x、a 和 b 均为 int 型变量，它们的存储单元地址分别表示为x、a和b。该语句对应的指令序列及其在指令流水线中的执行过程如题 44 图所示。则这 4 条指令执行过程中，I3的 ID段和 I4的 IF 段被阻塞的原因各是什么?（4）若高级语言程序中某赋值语句为 x2*x+a，x 和 a 均为 unsigned int
25、类型变量，它们的存储单元地址分别表示为x、a，则执行这条语句至少需要多少个时钟周期?要求模仿题 44 图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。45（7 分）某请求分页系统的局部页面置换策略如下：系统从 0 时刻开始扫描，每隔 5 个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为
26、 32、15、21、41。进程 P 依次访问的是：、。请回答下列问题。（1）访问时，对应的页框号是什么?（2）访问时，对应的页框号是什么?说明理由。（3）访问时，对应的页框号是什么?说明理由。（4）该策略是否适合于时间局部性好的程序?说明理由。46（8 分）某文件系统空间的最大容量为 4TB（1T240），以磁盘块为基本分配单位，磁盘块大小为 lKB。文件控制块（FCB）包含一个 512B 的索引表区。请回答下列问题。（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节?（2）假设索引表区采用如下结构：第 07
27、字节采用格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B，块数占 2B；剩余 504 字节采用直接索引结构，一个索引项占 6B，则可支持的单个文件最大长度是多少字节?为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。47（9 分）主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，服务器 S 的 IP 地址为 211.68.71.80。H 与 S 使用 TCP 通信时，在 H 上捕获的其中 5 个 IP 分组如题 47-a 表所示。题 47-a 表 编号 IP 分组的前 40 字节内容（十六进制）1 019b400
28、0 8006lde8 coa80008 d3444750 0bd91388 846b41c5 00000000 5db00000 2 00004000 31066e83 3d3444750 cOa80008 13880bd9 e0599fef 846b41c6 6701216d0 37e10000 3 019c4000 8006ldef cOa80008 d3444750 bd913888 46b41c6e 0599ff05 01043802 b320000 4 019d4000 80061dde cOa80008 d3444750 0bd91388 846b4lc6 e0599ff0 c65
29、50000 5 3106067a d3444750 cOa80008 13880bd9 e0599ff0 846b41d6 501016d0 57d20000 请回答下列问题。（1）题 47-a 表中的 IP 分组中，哪几个是由 H 发送的?哪几个完成了 TCP连接建立过程?哪几个在通过快速以太网传输时进行了填充?（2）根据题 47-a 表中的 IP 分组，分析 S 已经收到的应用层数据字节数是多少?（3）若题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所列，则该 IP 分组到达 H 时经过了多少个路由器?题 47-b 表 来自 S 发出的分组 4006e
30、Cad d3444750 ca760106 1388a108 e0599ff0 846b41d6 501016dO b7d60000 注：IP 分组头和 TCP 段头结构分别如题 47-a 图、题 47-b 图所示：版本 头部长度 服务类型（8-15）总长度（16-31）标识 标志 片偏移 生存时（TTL）协议 头部校验和 源 IP 地址 目的 IP 地址 题 47-a 图 IP 分组头结构 源端口（0-15）目的端口（16-31）序号（seq）确认号（ack）数据偏移 保留 URG ACK PSH RST SYN FIN 窗口 校验和 紧急指针 选项（长度可变）填充 题 47-b 图 TCP
31、 段头结构 2012 年全国硕士研究生入学统一考试 408 计算机学科专业基础综合真题及详解 一、单项选择题：l40 小题。每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1求整数 n（n0）阶乘的算法如下，其时间复杂度是（）。AO（log2n）B0（n）CO（nlog2n）DO（n2）【答案】B。【解析】设 fact（n）的运行时间函数是 T（n）。该函数中语句的运行时间是 0（1），语句的运行时间是 T（n-1）+O（1），其中 O（1）为乘法运算的时间。因此，当 n1 时，T（n）-0（1）；当 n1 时，T（n）T（n-1）+O（1）。则，T（n
32、）O（1）+T（n-1）2O（1）+T（n-2）（n-1）O（1）+T（1）n O（1）O（n）即 fact（n）的时间复杂度为 O（n）。2已知操作符包括+、-、*、（和）。将中缀表达式 a+b-a*（c+d）e-f）+g 转换为等价的后缀表达式ab+acd+e f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。A5 B7 C8 D11【答案】A。【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级
33、的运算符在栈中的先计算）。表达式 a+b-a*（c+d）e-f）+g 产生后缀表达式的过程如下表所列：当前字符 运算符栈内容 后缀表达式 说明 a +“+”进栈 b+ab -ab+“-”与栈顶元素“+”的优先级相同，则“+”出栈，“-”进栈 a-ab+a *-*ab+a“*”的优先级大于栈顶元素“-”，则“*”进栈（-*（ab+a“（”对它之前后的运算符起隔离作用（-*（ab+a“（”对它之前后的运算符起隔离作 用 -*（ab+ac +-*（+ab+ac“+”进栈 d-*（+ab+acd ）-*（ab+acd+与其配对的左括号及其前所有运算符出栈 -*（ab+acd+“”进栈 e-*（ab+a
34、cd+e -*（-ab+acd+e“-”的优先级小于栈顶元素“”，则“”出栈，“-”进栈 f-*（-ab+acd+ef ）-*ab+acd+ef-与其配对的左括号及其前所有运算符出栈+-ab+acd+ef-*“+”的优先级小于栈顶元素“*”，则“*”出栈 +ab+acd+ef-*-“+”与栈顶元素“-”的优先级相同，则“-”出栈，“+”进栈 g+ab+acd+ef-*-g ab+acd+ef-*-g+全部出栈 通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是 5。3若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点（）。A
35、只有 e B有 e、b C有 e、c D无法确定【答案】A。【解析】由题目可知，若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，其中 a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为 e，而后序遍历的倒数第二个结点为 e，说明 a 的孩子结点只有 e。4若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（）。A12 B20 C32 D33【答案】B。【解析】本题题目的实际问题是，具有 6 层结点的平衡二叉树含有最少的结点数是多少。Nh表示深度为 h 的平衡二叉树中含有的最少结点数，有 N00，N11，N22Nh
36、Nh-1+Nh-2+1 由此可得 N520。对应的平衡二叉树如下图所示。5 对有 2 个顶点 e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。A0（n）B0（e）CO（n+e）DO（ne）【答案】C。【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间为 O（n2），其中 n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为 0（e），其中 e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为 O
37、（n+e）。即可得出正确答案。6若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。A存在，且唯一 B存在，且不唯一不唯一 C存在，可能不唯一 D无法确定是否存在【答案】C。【解析】图的基本应用拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为，则存在两个拓扑序列。7有向带权图如题 7 图所示，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点
38、依次是（）。题 7 图有向带权图 Ad,e,f Be，d，f Cf，d，e Df，e，d【答案】C。【解析】本题主要考查 Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行 Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为 f,d,e。顶点 趟数 b c d e f 集合 S k1 2（a，b）5（a，c）（a，b）k2 （a，b，c）（a，b，d）a，b，c k3 （a，b，d）4（a，b，c，f）（a，b，c，e）a，b，c，f k4 （a，b，d）（a，b，c，e）a，b，c，f，d）k5 （a，b，d，e）a,b，c，f，d，e 8下列关
39、于最小生成树的叙述中，正确的是（）。最小生成树的代价唯一 所有权值最小的边一定会出现在所有的最小生成树中 使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同 A仅 B仅 C仅、D仅、【答案】A。【解析】当图中存在相同权值的边时，其最小生成树可能是不唯一的，但最小生成树的代价一定是相同的，所以说法正确。从 n 个顶点的连通图中选取 n-1 条权值最小的边可能构成回路，所以说法错误。当某个顶点有权值相同的边，使用普里姆（Prim）算法从不同顶点开始得到的最小生成树并不一定相同，所以说法错误。当最小生成树不唯一时
40、，使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树可能相同，也可能不同，所以说法错误。由此可得出正确答案。9设有一棵 3 阶 B 树，如题 9 图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是（）。题 9 图 3 二叉树图 A60 B60，62 C62，65 D65【答案】D。【解析】本题主要考查 B 树删除操作。即被删关键字所在的结点中的关键字个数等于m/2-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于m/2-1，则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关
41、键字所在结点中。题目中删除关键字 78 得到一棵新 B 树如下，其最右叶结点所含的关键字是 65。10排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。简单选择排序 希尔排序 快速排序 堆排 V二路归并排序 A仅、B仅、C仅、D仅、【答案】A。【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。11对同一待排序列分别进行折半插入排序和
42、直接插入排序，两者之间可能的不同之处是（）。A排序的总趟数 B元素的移动次数 C使用辅助空间的数量 D元素之间的比较次数 【答案】D。【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。折半插入排序的时间复杂度仍为 O（n2）,所以两者之间的不同只可能是元素之间的比较次数。12假定基准程序 A 在某计算机上的运行时间为 l00 秒，其中 90 秒为 CPU时间，其余为 I/O 时间。若 CPU 速度提高 50，I/O 速度不变，则运行基准程序 A 所耗费的时间是（）。A55 秒 B60 秒 C65 秒 D70 秒【
43、答案】D。【解析】CPU 速度提高 50，即 CPU 性能提高比为 l.5，改进之后的 CPU运行时间901.560 秒。I/O 速度不变，仍维持 l0 秒，所以运行基准程序A 所耗费的时间为 70 秒。13假定编译器规定 int 和 short 类型长度分别为 32 位和 16 位，执行下列 C 语言语句：unsigned short X65530；unsigned int yX：得到 y 的机器数为（）。A00007FFAH B0000FFFAH CFFFF7FFAH DFFFFFFFAH【答案】B。【解析】X 和 y 均为无符号数，其中 X 为 16 位，y 为 32 位，将 16 位无
44、符号数转化成 32 位无符号数，前面要补零。因为 X65530FFFAH，所以 y0000FFFAH。14float 类型（即 IEEE754 单精度浮点数格式）能表示的最大正整数是（）。A2126-2103 B2127-2104 C2127-2103 D2128-2104【答案】D。【解析】IEEE754 单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短浮点数的真值为：（-1）S1.f2（E-127）,S为符号位，E 的取值为 1254，f 为 23 位；故 float 类型能表示的最大整数是1.1111 2（254-127）2127（2-2-23）2128-2
45、104。15某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 和 short 型长度分别为 32 位和 16 位，并且数据按边界对齐存储。某 C语言程序段如下：若 record 变量的首地址为 0 xC008，则地址 0 xC008 中内容及 record.c 的地址分别为（）。A0 x00、0 xC00D B0 x00、0 xCOOE C0 x11、0 xC00D D0 x11、0 xC00E【答案】D。【解析】32 位整数 a 需要占 4 个字节，l6 位整数 c 需要占 2 个字节，而字符数据 b 占一个字节。a273,转换成十六进制是 111H，采用小端方式存放数
46、据，地址 0 xC008 中的内容为 11H。由于数据按边界对齐存储，地址 0 xC008OxCOOB 中存放 a，地址 0 xC00C 中存放 b，地址 0 xC00D 中空闲，地址 0 xC00E0 xC00F 中存放 c。16下列关于闪存（FlashMemory）的叙述中，错误的是（）。A信息可读可写，并且读、写速度一样快 B存储元由 MOS 管组成，是一种半导体存储器 C掉电后信息不丢失，是一种非易失性存储器 D采用随机访问方式，可替代计算机外部存储器【答案】A。【解析】考查闪存的特性，闪存是 EEPROM 的进一步发展，可读可写，用MOS 管的浮栅上有无电荷来存储信息，它依然是 RO
47、M 的一种，故写速度比读速度要慢不少。闪存是一种非易失性存储器，它采用随机访问方式，现在常见的SSD 固态硬盘就是由 flash 芯片组成的，故答案为 A。17假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块大小为 l 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换算法，当访问的主存地址依次为 0，4，8，2，0，6，8，6，4，8 时，命中Cache 的次数是（）。A1 B2 C3 D4 【答案】C。【解析】Cache 有 4 个行，2 路组相联，即 Cache 被分成 2 组，每组 2 行。主存地址为 01、45、89 可映射
48、到第 0 组 Cache 中，主存地址为 23、67 可映射到第 1 组 Cache 中。Cache 初始为空，采用 LRU 替换算法，当访问主存的 10 个地址依次为 0，4，8，2，0，6，8，6，4，8 时，命中 Cache 的次数共有 3 次，分别发生在第 7、8 和 10 步时。18某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有（）。A5 位 B6 位 C15 位 D33 位【答案】C。【解析】33 个微命令分成 5 个互斥类（即 5 个字段），
49、根据每个类中微命令的多少可以分别确定字段的长度为 3、2、4、3、3 位，又因为采用直接编码方式，所以它们之和 3+2+4+3+315 也就是操作控制字段的位数。19某同步总线的时钟频率为 l00MHz，宽度为 32 位，地址数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输 l28 位数据所需要的时间至少是（）。）。A20ns B40ns C50ns D80ns【答案】C。【解析】总线的时钟频率为 l00MHz，则时钟周期为 10ns。数据是 128 位，总线宽度是 32 位，所以需要 4 个时钟周期，而传输地址还需要一个周期，所
50、以传输一个 128 位的数据至少需要 5 个时钟周期，所以至少需要 10ns*550ns。20下列关于 USB 总线特性的描述中，错误的是（）。A可实现外设的即插即用和热插拔 B可通过级联方式连接多台外设 C是一种通信总线，可连接不同外设 D同时可传输 2 位数据，数据传输率高【答案】D。【解析】USB 总线即通用串行总线，它的特点有：（1）即插即用；（2）热插拔；（3）有很强的链接能力能将所有外设链接起来，且不损失带宽；（4）有很好的可扩展性；（5）高速传输，速度可达 480Mbps。所有 A，B，C 都符合USB 总线的特点。对于选项 D,USB 是串行总线，不能同时传输两位数据，所以答案