北京航空航天大学计算机学院计算机学科专业基础综合历年考研真题汇编(1)

1、北京航空航天大学计算机学院计算机学科专业基础综合历年考研真题汇编最新资料，WORM式，可编辑修改!目录说明：20072008的科目名称为“计算机专业综合”，代码分别为 461和961; 20092014年的科目代码与名称为“ 408计算机学科专业基础综合”； 2015年 起，科目代码与名称改为“961计算机学科专业基础综合”，本书书名以此为准。2014年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四 个选项中，只有一个选项是符合题目要求的。1 下列程常段的时间复杂度是()count = 0;O (log 2n)

2、 0(n)O (nlog 2n)0(n2)for ( k= 1;k< = n; k*2 ) for (j = 1;j< = n;j+1 ) coun t+;A.B.C.D.【答案】C【解析】外部循环的退出条件是 k>n,而对于k,每次循环都执行k = k*2, 所以循环次数为log 2n;内部循环的退出条件是j>n,对于j，每次循环都执行j =j+1 ,所以每次循环次数为n次。所以此程序段的时间复杂度为 O(nlog 2n), 即选Cof /g转换为等价后2.假设栈初始为空，将中缀表达式a/b c d e缀表达式的过程中，当扫描到f时，栈中的元素依次是(A.B.C. /

3、D. / 【答案】B【解析】中缀表达式转后缀表达式遵循以下原则：(1)(2)(3)(4) 左括号，遇到操作数，直接输出； 栈为空时，遇到运算符，入栈;将其入栈；执行出栈操作，遇到左括号, 遇到右括号,并将出栈的元素输出,直到弹出栈的是左括号不输出；(5) 遇到其他运算符'+''-''*''/'符的栈顶 元素，然后将该运算符入栈；(6) 最终将栈中的元素依次出栈， 所以扫描到/',入栈描到时，弹出所有优先级大于或等于该运算输出。+',由于+'优先级比/'低，所以 (,将/'弹出，+'入

4、栈；扫描到* ',优先级比+'高，入栈；扫描到'入栈; 扫描到' -, 将栈中优先级更高的' *'弹出， -' 入栈 ; 扫描到' *', 优先级比' -高，入栈。所以扫描到 f 的时候，栈中元素为:A. 队空:B. 队空:C. 队空:D. 队空:【答案】 【解析】3. 循环两列放在一维数组 A0M-1中，end1指向队头元素，end2指向队 尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能 容纳 M-1 个元素。初始时为空， 下列判断队空和队满的条件中， 正确的是( )end1 = = end

5、2;队满：end1 = =( end2+1) modMend1 = = end2;队满：end2=( end1+1) mod ( M-1)end2=( end1+1) modM ; 队满：end1 = =( end2+1) modM end1 = = (end2+1) modM; 队满：end2= (end1+1) mod( M-1) A在循环队列中，在少用一个元素空间的前提下，可约定入队前， 测试尾指针在循环意义下加 1 后是否等于头指针，若相等，则队满。而队空的 条件还是首尾指针是否相等。分别是()A. e,cB. e,aC. d,cD. b,a【答案】D【解析】此二叉树的中序遍历序列为：

6、4. 若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点debxac, 由于节点 x 左右孩子都为空， 所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接 前驱结点b和直接后继结点a,所以选D5. 将森林F转换为对应的二叉树 T, F中叶结点的个数等于(A. T 中叶结点的个数B. T 中度为 1 的结点个数C. T 中左孩子指针为空的结点个数D. T 中右孩子指针为空的结点个数 【答案】 C【解析】 森林转化为对应的二叉树是孩子 - 兄弟'存储的,即左孩子指针 指向当前节点的孩子节点，右孩子指针指向当前节点的兄弟节点，所以在T中左孩子指针为空则代表它在

7、森林中并没有孩子即为叶结点。所以选6. 5 个字符有如下 4 种编码方案，不是前缀编码的是(01,0000,0001,001,1011,000,001,010,1000,001,010,011,1000,100,110,1110,1100A.B.C.D.【答案】 D 【解析】 在一个字符集中，任何一个字符的编码都不是另一个字符编码的 前缀。约定左分支表示字符 0'，右分支表示字符 1'，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编 码必是前缀编码。D选项中，编码110是编码1100的前缀，故不符合前缀编码 的定义。7对如下所示的有向图进行

8、拓扑排序，得到的拓扑序列可能是（A.B.3,1,2,4,5,63.1.2.4.6.53.1.4.2.5.6C.【解析】拓扑排序方法如下:（1） 从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它;（2）从图中删去该顶点，并且删去从该顶点发出的全部有向边；3,1,4,6,2,5 和 3,1,4,2,6,5（3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。 对于此有向图进行拓扑排序所有序列为：时可能出现堆积（聚集）现象, ）以选D8.用哈希（散列）方法处理冲突（碰撞） 下列选项中，会受堆积现象直接影响的是（A. 存储效率B. 数列函数C. 装填（装载）因子D. 平均查找长度【答案

9、】D【解析】哈希方法冲突会使在查找冲突的关键字时，还要根据冲突处理办 法多次比较关键字，则直接影响了平均查找长度。9 .在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是（561015A.B.C.D.【答案】D【解析】m阶B树非根结点含关键字个数厂m/2n - 1 < = j < = m -4阶B树非根结点含关键字13个，所以要使关键字结点数量最多，那么 每个结点只有一个关键字，一共有15个关键字那么最多有15个含有关键字的结点10用希尔排序方法对一个数据序列进行排序时，若第1 趟排序结果为9,1,4,13,7,8,20,23,15 ，则该趟排序采用的增量（间隔）可能是（）

10、ABC2345【答案】 【解析】 所以 A 错误对于 C， 对于 D，B对于A,增量为增量为 4，那么增量为 5，那么所以D也错误。对于B,分为 所以B正确11 A B C D2，那么 9,4,7,20,15 是一组，而它们是无序的，9,7,15是一组，而它们是无序的，所以C错误9,8 是一组,降序, 1,20 是一组,而它们是升序, 3组：9,13,20 ；1,7,23 ；4,8,15 都是升序有序，下列选项中，不可能是快速排序第 2 趟排序结果的是（2.3.5.4.6.7.92.7.5.6.4.3.93.2.5.4.7.6.94.2.3.5.7.6.9【答案】 C【解析】 对于快速排序，每

11、一趟都会使一个元素位于有序时的位置，而有 序序列为2,3,4,5,6,7,9 ，与C进行对比，只有9位于它有序的时候的位置，显 然不是第二趟快速排序的结果12 .程序P在机器M上的执行时间是20秒，编译优化后，P执行的指令数 减少到原来的 70%，而 CPI 增加到原来的倍，则A.秒BPC14 秒D.秒【答案】 D【解析】20* =13 .若x = 103,y = -25,则下列表达式采用 生溢出的是（A.B.C.D.P在M上的执行时间是（8 位定点补码运算实现时，会发x+y -x+y x-y -x-yC8 位定点补码能表示的数的范围为：78，B结果为-128，D结果为-78都在此范围内，只有

12、 C结果128【答案】 【解析】A结果为超过了 8 位定点补码能表示的数的范围，会发生溢出-128 127D14. float型整数据常用IEEE754单精度浮点格式表示， 假设两个float型则x和y之1间的关系为:A.x<y且符号相同B.x<y且符号不同C.x>y且符号相同D.x>y且符号不同变量x和y分别在32为寄存器f1和f2中，若(f1)= CC900000H, (f2)= BOCOOOOOH, )【答案】A【解析】两个数对应的IEEE754的标准形式为;浮点数S阶码尾数f111001 1001001 0000 0000 0000 0000 0000f2101

13、10 0001100 0000 0000 0000 0000 0000将IEEE754单精度形式的二进制转化为浮点数公式为V=( -1 ) 8*2八(E-Bias)*M由于f1，f2的符号位都是1,所以f1，f2符号相同，而阶码上f1>f2，所 以f1>f2，所以f1的绝对值比f2大，而他们都是负数，所以 f1vf2，所以选A15.某容量为256M的存储器，由若干 4M*8位的DRAM芯片构成，该 DRAM 芯片的地址引脚和数据引脚总数是：()A.19B.22C.30D.36【答案】A【解析】DRAMfe址线复用，4M为2的22次方，因此除2为11根，数据线 8根。因此地址引脚和数

14、据引脚总数为 19根16.采用指令Cache与数据Cache分离的主要目的是(减低Cache的缺失损失提高Cache的命中率减低CPU平均访问时间减少指令流水线资源冲突A.B.C.D.【答案】D【解析】指令流水线不会断流，预取过来的都是指令17 .某计算机有16个通用寄存器，采用32位定长指令字操作码字段(含 寻址方式位)为8位，Store指令的源操作数和目的操作数分别采用寄存器直接 寻址和基址寻址方式，若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则Store指令中偏移量的取值范围是A. -32768 -+32767B. -32767 -+32768C. -65536 -+65535

15、D. -65535 -+65536【答案】A)【解析】寄存器个数16= 24,偏移量有32-8-4-4 = 16位 指令编址方式如下所示：操作码源地址寄存器目的地址基址寄存器偏移量84416所以偏移量取值范围为-3276816位补码取值范围为-32768+32767，+3276732条指令，公共的取指令微程序包4条微指令组成，采用断定法（下（ ）18.某计算机采用微程序控制器，共有 含2条微程序，各指令对应的微程序平均由 址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：5689A.B.C.D.【答案】C78【解析】32*4+2 = 130, 2 = 128<130<

16、2= 256,所以至少需要8位才能表示 完130个地址。19 .某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，132MB/S264MB/S528MB/S 1056MB/S总线时钟频率为66MHZ每个时钟同期传送两次数据。 （上升沿和下降沿各传送 一次数据）该总线的最大数据传输率是（总线带宽）：（）A.B.C.D.【答案】C【解析】总线带宽=总线工作频率x（总线宽度 /8 ），由于地址线与数据 线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为66*8 = 528，所以选C20 .一次总线事物中，主设备只需给出一个首地址，从设备就能从首地址幵始的若干连续单元格

17、读出或写入的个数，这种总线事务方式称为（）A. 并行传输B. 串行传输C. 突发D. 同步【答案】C【解析】猝发数据传输方式：在一个总线周期内传输存储地址连续的多个 数据字的总线传输方式21 .下列有关I/O接口的叙述中错误的是：（）A. 状态端口和控制端口可以合用同一寄存器B. I/O接口中CPU可访问寄存器，称为I/O端口 ？C.采用独立编址方式时，I/O端口地址和主存地址可能相同D. 采用统一编址方式时，CPU不能用访存指令访问I/O端口【答案】 D【解析】 采用统一编码方式，存储器和 I/O 端口共用统一的地址空间，不 需要专用的 I/O 指令，任何对存储器数据进行操作的指令都可用于

18、I/O 端口的 数据操作。所以D错误A.%B.25%C.%D.50%100ns，每400ns发出一次中断请50ns,则在该设备持续工作过程中CPUI/O时间占整个CPU时间百分比至少是（）答案】 解析】22.某设备中断请求的相应和处理时间为 求，中断相应所容许的最长延迟时间为 用于该设备的B每400ns响应一次中断并且用 100ns进行处理，所以该设备的I/O 时间占用CPU时间百分比为100/400 = 25%，中断响应容许的延迟时间对此没有影 响，属于干扰条件23 A B C D下列调整中，不可能导致饥饿现象的是（ 时间片转移 静态优先及调度 非抢占式作业优先 抢占式短作业优先【答案】 A

19、【解析】 时间片转移方法能在一个周期内使每个进程都得到一个时间片的 CPU使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。24.某系统有 n 台互斥使用的同类设备， 3 个并发进程需要 3,4,5 台设备， 可确保系统不发生死锁的设备数n最小为（）A.9B.10C.11D.12【答案】B【解析】2+3+4+1 = 1025.下列指令中，不能在用户态执行的是A.trap指令B.跳转指令C.后栈指令D.关中断指令【答案】 D【解析】 关中断指令必须在和心态才能执行， trap 指令可以在用户态下执 行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。26.一个进程的读磁区操作完

20、成后，操作系统针对该进程必做的是（A. 修改进程状态为就绪态B. 降低进程优先级C. 进程分配用户内存空间D. 增加进程的时间片大小【答案】 A【解析】 进程等待的 I/O 操作完成便会从等待状态转移到就绪状态。即用一位（ bit ）27 .现有容量为10GB的磁盘分区，磁盘空间以簇（cluster ）为单位进行 分配，簇的大小为4KB,若采用位图法管理该分区的空闲空间， 标识一个簇是否被分配，则存放该位图所需簇的个数为（【解析】磁盘的簇的个数为：10GB/4K吐*220个 而一个簇的位示图能管理的簇的个数为： 所以需要簇的个数为*220/32K = 80个28. 下列措施中，能加快虚实地址转

21、换的是1 增大快表 驻内存 3增大交换区（ ）A. 仅B. 仅C. 仅D. 仅4KB*8= 32KTLB）2 让页表常121,22,3A.80B.320C.80KD.320K【答案】 A【答案】 C【解析】 加大快表能增加快表的命中率，即减少了访问内存的次数；让页 表常驻内存能够使 cpu 不用访问内存找页表，从也加快了虚实地址转换。而增 大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响29. 在一个文件被用户进程首次打开的过程中，操作系统需做的是（将文件内容读到内存中 将文件控制块读到内存中 修改文件控制块中的读写权限 将文件的数据缓冲区首指针返回给用户进程A.B.C.D.【答案】

22、B【解析】 概念30. 在页式存储管理系统中，采用某些页面置换算法，会出现 Belady 异常 现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列 算法中，可能出现 Belady 异常现象的是（ ）m. OPT算I. LRU算法n. FIFO算法法A. 仅nB. 仅inc.仅irnD. 仅n m【答案】 A【解析】 Belady 现象只有 FIFO 算法才会出现31. 下列关于管道（ Pipe ）通信的叙述中，正确的是（一个管道可实现双向数据传输 管道的容量仅受磁盘容量大小限制 进程对管道进行读操作和写操作都可以被阻塞 一个管道只能有一个读写进程或一个写进程对其操作【答案】

23、CA.B.C.D.C正确）【解析】 只有写进程才能对管道写入数据，读进程对管道进行读取数据， 只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而 如果有写操作对管道进行写的话那就要堵塞了。那么32下列选项中，属于多级页表优点的是（加快地址变换速度减少缺页中断次数 减少页表项所占字节数 减少页表所占的连续内存空间【答案】 DABC【解析】 多级页表避免了把所有的页表一直保存在内存中 33在 OSI 参考模型中，直接为会话层提供服务的是（ A BCDD应用层表示层传输层网络层【答案】 C【解析】 OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传 输层。34. 某以太

24、网拓扑及交换机当前转发表如下图所示，主机00-e1-d5-00-23-a1 向主机 00-e1-d5-00-23-c1 发送 1 个数据帧，主机 00-e1-d5-00-23-c1 收到该帧后，向主机 00-e1-d5-00-23-a1 发送一个确认帧， 交换机对这两个帧的转发端口分别是（ ）A.3和1B.2,3 和 1C.2,3 和 1,2D.1,2,3 和 100-e1-d5-00-23-b11L12交换机3目的地址端口00-e1-d5-00-23-b12信噪比 频率宽带 调制速率 信号传播速度50ms,则甲可以达到的最大平均数据传输速率约为(10 Mb ps20 Mb ps80 Mb p

25、s100 Mb psA.000B.101C.110D.111【答案】B)00-e1-d5-00-23-c100-a1-d5-00-23-a1【答案】B【解析】第一次交换机没有00-e1-d5-00-23-c1的信息，只能选择从其他 端口全部发送，同时记录这个数据报源MAC地址的信息00-e1-d5-00-23-a1,确认帧发送时已经有00-e1-d5-00-23-a1的信息了所以只用从1端口转发。35. 下列因素中，不会影响信道数据传输速率的是()A.B.C.D.【答案】D【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。36.主机甲与主机乙之间使用后退 N帧协议(GBN传输数据，甲

26、的发送窗 口尺寸为1000,数据帧长为1000字节，信道宽带为100Mbps乙每收到一个数 据帧立即利用一个短帧(忽略其传输延迟)进行确认，若甲乙之间的单向传播 延迟是A.B.C.D.【答案】C【解析】1000B*1000/ (50*2ms)= 10MA 80Mbps.37 .站点A、B、C通过CDMA共享链路，A、B、C的码片序列(chipping sequenee)分别是(1,1,1,1 )、( 1, -1,1 , -1 )和(1, 1,-1 , -1 )，若 C从 链路上收到的序列是(2,020,0 , -2,0 , -2,020,2 )，贝U C收到A发送的数 据是(【解析】用A的码片

27、与信息做内积运算38.主机甲和乙已建立了 TCP连接，甲始终以MS& 1KB大小的段发送数据， 并一直有数据发送；乙每收到一个数据段都会发出一个接收窗口为10KB的确认情况下，经过1A. 10KBB.12KBC.14KBD.15KB【答案】A段。若甲在t时刻发生超时时拥塞窗口为 8KB,则从t时刻起，不再发生超时的 个RTT后，甲的发送窗口是()【解析】发送窗口是接受窗口和拥塞窗口的最小值，这里接收窗口总是 10KB拥塞窗口到那个时候是大于 10KB的，取最小值39 .下列关于UDP协议的叙述中，正确的是(In出A.B.C.D.提供无连接服务提供复用/分用服务通过差错校验，保障可靠数据

28、传输仅I仅i、n仅n、川i、n、川【答案】B【解析】UDP无连接创建，提供多路复用服务。虽然有差错检验，但是不能 保证可靠数据传输，所以川错误。40 .使用浏览器访问某大学 Web网站主页时，不可能使用的协议是(【解析】SMTP是简单邮件传输协议，访问主页时并不涉及邮件相关协议。 二、综合应用题：4147小题，共70分。41 .(10分)二叉树的带权路径长度(WPL是二叉树中所有叶结点的带权 路径长度之和，给定一棵二叉树 T，采用二叉链表存储，其中叶节点的 非负权值。设root为指 设计求T的WP啲算法。(1)(2)(3) 答：le ftweightright节点结构为：weight域保存该结

29、点的 向T的根节点的指针， 要求：给出算法的基本设计思想；使用C或C+吾言，给出二叉树结点的数据类型定义；根据设计思想，采用 C或C+吾言描述算法，关键之处给出注释。(1)算法的基本思路是利用利用递归的思想来求解二叉树的带权路径A.PPPB.ARPC.UDPD.SMT P【答案】D长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的 形参，那么递归调用孩子节点时只需要将这个形参加一即可。(2) typedef struct BiNodeint weight;192.160/2410.1.1.1010.1.1.1

30、4192.1.5.0/24610.1.1.510.1.1.6R3192.1.7.0/24（3）,Metric3226 2521 20OPRs16 15 RdOFFSET=10.44.（11分）某程序中有如下循环代码段 P： “for （i = 0;ivN;i+ ） sum+ =Ai; ”。假设编译时变量 sum和i分别分配在寄存器 R1和R2中。常量N在 寄存器R6 中,数组A的首地址在寄存器 R3中,程序段P起始地址为0804 8100H, 对应的汇编代码和机器代码如题 44表所示编号地址机器代码汇编代码注释10H080481000022080HLoop: sllR4;R2,2(R2) vv

31、2t R424H080481000083020HAddR4;R4,R3(R4) +(R3)T R438H08048108C850000HLoad R5;0 (R4)(R4)+0)fR54CH080481000250820HAddR1;R1,R5(R1) +(R5)T R150H08048112042000HAdd R2;R2,1(R2) +2f R464H08048111446FFFAHBneR2;R2,loo pif (R2) go to loop! =( R6)执行上述代码的计算机 M采用32位定长指令字，其中分支指令 Bne采用如 下格式，Op为操作码：Rs和Rd为寄存器编号：OFFSE

32、TS偏移量，用补码表示。请 回答下列问题，并说明理由。（1）M的存储器编址单位是什么？（2）已知sll指令实现左移功能，数组 A中每个元素占多少位？（3）题44表中bne指令的OFFSE存段的值是多少？已知 bne指令采用相 对寻址方式，当前PC内容为bne指令地址，通过分析题44表中指令地址和bne 指令内容，推断出bne指令的转移目标地址计算公式。（4）若M采用如下“按序发射、按序完成”的5级指令流水线：IF（取指）、ID （译码及取数）、EXE（执行）、MEM（访存）、WB（写回寄存器），且硬件 不采取任何转发措施，分支指令的执行均引起3个时钟周期阻塞，则 P中哪些 指令的执行会由于数据

33、相关而发生流水线阻塞？哪条指令的执行会发生控制冒 险？为什么指令 1的执行不会因为与指令 5 的数据相关而发生阻塞？答： (1)由题可知，指令为 32为即 4 个字节，而程序执行时是以 4为间 隔逐条取指令的，故可知 M的存储器是采用字节编址。(2)32 位，因为 sl1 中实现左移，而( R2)<<2 R4 即左移两位就是乘以4, 所以是4*8 = 32位(3) 由Bne的指令格式可知其 OFFSETS指令的后16位，而Bne的机器码 码为 1446 FFFAH,所以 Bne 的 OFFSETS FFFAH即-6。由题可知Bne采用相对寻址方式，故有效地址 EA= (PC)+A=

34、 ( PC)+OFFSET 而PC的值为当前Bne指令的地址即(PC = 08048114H,而取完Bne指令后，(PQ +4f PC,故(PQ = 0804 8118H。而要跳转到指令 1 的地址 08048100H, 两者相差了 18H也就是24个字节，而OFFSETS-6，故转移目标地址计算公式 为(PC +OFFSET*(24/6 ) = ( PC +OFFSET*4(4) 由指令序列可知，指令 1需写R4而指令2需读R4,故指令2会因为 数据相关而发生阻塞，同理指令 3、指令 4 也会因为数据相关而发生阻塞；而指 令 6 为分支指令，故其存在控制冒险。因为分支指令会有 3个时钟周期的

35、阻塞， 故指令 1 的执行不会因为指令 5 的数据相关而发生阻塞。45. ( 10分)假设对于44题中的计算机M和程序P的机器代码，M采用页 式虚拟存储管理。P幵始执行时，(R1)=(R2)= 0.(R6)= 1000，其机器代码已调入主存但不在 Cache中；数组A未调入主存，其所有数组元素在同一 页，并存储在磁盘同一个扇区，请回答下列问题，并说明理由。(1) P执行结束时，R2的内容是多少？(2) M的指令Cache和数据Cache分离，若 Cache共有16行，Cache和主 存交换的块大小为32字节，则其数据区的容量是多少？若仅考虑程序段 P的执 行，贝y指令Cache的命中率为多少？

36、(3) P在执行过程中，哪条指令的执行可能发生溢出异常？哪条指令的执 行可能产生缺页异常？对于数组 A的访问，需要读磁和 TLB至少各多少次？答：(1) R2是保存变量i的内容，当P执行完即ivN不满足，故i = N=(R6= 1000。(2) Cache共有16行，每行大小为32B,而本段指令大小为 6*4B = 24B, 故指令占一行 Cache，所以数据Cache的大小为15*32B = 160B。由题可知N= 1000,故循环了 1000次，所以共执行了 1000*6 = 6000条指令， 而只有第一次循环执行指令 1时指令不在Cache中，故指令Cache命中率=(6000-1 )

37、/6000 = %(3) 指令4有可能发生溢出，该指令是统计数组 A0Ai的和，而数组 A的各元素的值未知，故该指令是可能发生溢出的。第一次执行指令2时需要访问数组A,而数组A未在内存中，故会发生缺页 异常。由题可知数组 A的所有元素在同一页，并存储在磁盘同一个扇区，故经 过一次便将该页调入内存，所以以后访问便不会发生缺页中断，故只需读一次 磁盘， 999 次 TLB。46. (9分)文件F由200条记录组成，记录从1幵始编号，用户打幵文件 后，欲将内存中的一条记录插入文件 F中，作为其第30条记录，请回答下列问 题，并说明理由。(1) 若文件系统为顺序分配方式，每个存储块存放一条记录，文件F

38、的存 储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？ F的文件控制区内容会有哪些改变？( 2)若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要访问多少存储块？若每个存储块大小为1KB,其中 4 个字节存放指针，则该系统支撑文件的最大长度是多少？ 答：(1)因为要最少访问，所以选择将前 29块前移一个存储块单元，然 后将要写入的记录写入到当前的第 30 条的位置上。由于前移都要先访问原存储 块将数据读出，再访问目标存储块将数据写入，所以最少需要访问29*2+1 = 59块存储块F 的文件区的文件长度加 1，起始块号减 1(2) 采

39、用链接方式则需要顺序访问前29块存储块，然后将新纪录的存储块插入链中即可，把新的块存入磁盘要 1 次访存，然后修改第 29块的链接地址 存回磁盘又一次访存。一共就是29+1+1= 31次。4 个字节的指针的地址范围为 232。所以此系统支撑文件的最大长度为232*(1KB-4B)= 4080GB47. (11 分)系统中有多个生产者进程和消费者进程，共享用一个可以存1000个产品的缓冲区(初始为空)，当缓冲区为未满时，生产者进程可以放入 一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件 产品，否则等待。要求一个消费者进程从缓冲区连续取出 10件产品后，其他消 费者进程才可以

40、取产品，请用信号量P， V(wait ， signed )操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值1000 表示缓冲区是否为满，初值为 0 生产者之间的互斥信号，初值为 1 消费者之间的互斥信号，初值为 1 当前消费者能否访问缓冲区，初值为 1 in,out 分别为生产者和消费者进程所要使用的指针，指向下一个MaxNum 1000为缓冲区的大小，count标志当前消费者已答：设置 5个信号量empty:表示缓冲区是否为空，初值为full ：mutex1 : mutex2:available: 定义变量可用的缓冲区单元， 经取的产品的数量，初值为 0生产者进程

41、:while ( true ) 生产一个产品； P( empty) ;P( mutex1 ) ;产品送入 buffer ( in ) ;in =( in+1 ) mod MaxNum;V( mutex1 );V( full ) ; 消费者进程 P( available );while (count ! = 10 )P( full ) ;P( mutex2);取出产品 buffer ( out ) ;count+out =( out+1 ) mod MaxNum; V( mutex2);V( empty);count = 0;V( available );2013年北京航空航天大学计算机学院40

42、8计算机学科专业基础综合真题及详解一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一 个选项符合试题要求。1.已知两个长度分别为 m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则(n)(m*n )(min ( m,n) (max (m,n)最坏情况下的时间复杂度是（）OOOOA.B.C.D.【答案】D【解析】m和n是两个升序链表长度分别为 m和n,在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m和n中的最大值。2个栈的入栈序列为 1,2,3,，n,其出栈序列是 P1, P2, P3Pn。若，贝y P2= 3，则P3 可能取值的个

43、数是（）A. n-3B. n-2C. n-1D .无法确定【答案】C【解析】除了 3本身以外,其他的值均可以取到，因此可能取值的个数为 n-1。3.若将关键字1, 2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是（）0123A.B.C.D.【答案】D，由图可知【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示 平衡因子为0的分支结点为3个叶子结点，故答案为 D。4. 已知三叉树T中6个叶结点的权分别是2, 3, 4, 5, 6, 7, T的带权（外 部）路径长度最小是（）27465456A.B.C.D.【答案】B【解

44、析】利用三叉树的6个叶子结点的权构建最小带权生成树，最小的带权路径长度为（2+3） *3+ （4+5） *2+ （6+7） *1 = 465. 若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y,则X的右线索指向的是（）A. X的父结点B. 以Y为根的子树的最左下结点C. X的左兄弟结点YD. 以Y为根的子树的最右下结点【答案】A【解析】 根据后续线索二叉树的定义 ,X 结点为叶子结点且有左兄弟 ,那么这个结点为右孩子结 点 ,利用后续遍历的方式可知 X 结点的后继是其父结点 ,即其右线索指向的是父结点。6 .在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2,再将v插入T2

45、形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是 （）I .若v是T1的叶结点，贝y T1与T3不同II .若 v 是 T1 的叶结点，则 T1 与 T3 相同III .若v不是T1的叶结点，贝y T1与T3不同 若v不是T1的叶结点，贝y T1与T3相同IIIIVIIIIVIVA .仅B .仅C.仅D .仅【答案】 C【解析】 在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点那么在插入结点后， 后来的二叉排序树与删除结点之前相同。 如果删除的结点不是叶 子结点，那么再插入这个结点后，后来的二叉树可能发生变化，不完全相同。7.设图的邻接矩阵 A 如

46、下所示 ,各顶点的度依次是（）A.B.C.D.I、 I、 II、 II、1，2，3，4， 【答案】 C 【解析】当图用邻接矩阵存储时， 各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。 8若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（）2，2，4，4，1，1，2，2，2132Ah，c，a， b，d，e， g， fBe，a，f， g，b，h， c， dCd，b，c， a，h，e， f， gDa，b，c， d，h，e， f， g【答案】 D【解析】 根据广度优先遍历的定义，可知选项A、B、C 都为广度优先遍历，而选项 D 是深度优先遍历而不是广度优先遍历，故答案为 D。9.

47、下列 AOE 网表示一项包含 8 个活动的工程。 通过同时加快若干进度可以缩短整个工程的工 期。下列选项中，加快其进度就可以缩短工程工期的是（）A. c 和 eB. d 和 eCf 和Df 和【答案】【解析】10在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（ABCD【答案】【解析】B 树最少有（dhC根据 AOE 网的定义可知， 同时缩短几条关键路径上的活动时间， 可以缩短整个工期。）57814A根据B树的定义可知，跟结点最少含有 max （ 2, （ m-1）个关键字，高度为 2的阶 5-1） +1 = 5个关键字，其中根节点含有（5-1）个关键字，第2层结点含有1关键字。

48、A. 007,110,119,114,911 ,120,122B. 007,110,119,114,911 ,122,120C. 007,110,911,114,119,120,122D . 110,120,911,122,114,007,119【答案】C)【解析】进行排序的，故答案是C选项。12. 某计算机主频为 该机的Ml PS数是（A.B.C.D.100200400600【答案】C【解析】基准程序的为 1200/3 = 400。13. 某数采用IEEE754单精度浮点数格式表示为 C640 0000H，则该数的值是（A.B.C.D.XXXX213212213212CP 1 = 2*+3*

49、+4*+5* = 3。计算机的主频为，为1200MHz，该机器的 MIPS11.对给定的关键字序列 110, 119, 007, 911 , 114, 120, 122进行基数排序，则第 2趟分配 收集后得到的关键字序列是基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小，其指令分为4类，它们在基准程序中所占比例及CPI如下表所示。）【答案】A【解析】IEEE754单精度浮点数格式为 C640 0000H表示为二进制格式为 1100 0110 010000000000 0000 0000 0000，转换为标准的格式为：因此，浮点数的值为*213。14.某字长为8位的计算

50、机中，已知整型变量x、y的机器数分别为变量z = 2*x+y/2，则z的机器数为（）A.B. 00100100C .D.溢出 【答案】A【解析】将x左移一位,y右移一位，两个数的补码相加的机器数为115 .用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，A .B .C .D .X补=,y补=。若整型1000000,故答案选择A。则校验位数至少为（）2345S阶码尾数11000 1100100 0000 0000 0000 0000 0000C设校验位的位数为 k,数据位的位数为n,根据海明码编码k和n应满足下述关系。n=8,当k= 4时，24=（ 16）8 4 1（ 13），符合要求

51、，校验位至少是4位，故答案2k为【答案】【解析】n k 1。Co16 .某计算机主存地址空间大小为256MB，按字节编址。虚拟地空间大小为4GB,采用页式存储管理，页面大小为 4KB , TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。则对虚拟地址03FFF180H进行虚实地址变换的结果是（）A0153180HB0035180HCTLBD .缺页【答案】【解析】缺失A虚拟地址为03FF F180H，其中页号为03FFFH，页内地址为180H，根据题目中给出 的页表项可知页标记为 03FFFH所对应的页框号为 0153H，页框号与页内地址之和即为物理地址 015 3180H 。17

52、. 假设变址寄存器 R的内容为1000H，指令中的形式地址为 2000H ;地址1000H中的内容 为2000H，地址2000H中的内容为 3000H，地址3000H中的内容为 4000H，则变址寻方式下访问 到的操作数是（ ）A.B.C.D.1000H2000H3000H4000H【答案】 D【解析】根据变址寻址的EA =（ IX ） +A,变址寄存器的内容与形式地址的内容相加之后得到 操作数的实际地址，由题可知EA = 1000H+2000H = 3000H，根据实际地址访问内存，获取操作数 4000H。18. 某 CPU 主频为,采用 4级指令流水线,每个段的执行需要 1 个时钟周期。假定 CPU 执行了 100 条指令,在其执行过程中没有发生任何流水线阻塞,此时流水线的吞吐率为（）A.B.C.D.XXXX109条指令 /秒109条指令 /秒109