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

1、北京航空航天大学计算机学院计算机学科专业基础综合历年考研真题汇编最新资料，WORD式，可编辑修改!目录2014年北京航空航天大学计算机学院2013年北京航空航天大学计算机学院2012年北京航空航天大学计算机学院2011年北京航空航天大学计算机学院2010年北京航空航天大学计算机学院2009年北京航空航天大学计算机学院2008年北京航空航天大学计算机学院2007年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解408计算机学科专业基础综合真题及详解408计算机学科专业基础综合真题及详解408计算机学科专业基础综合真题及详解408计算机学科专业基础综合真题及详解408计算机学科专业

2、基础综合真题及详解961计算机专业综合考研真题461计算机专业综合考研真题说明：20072008的科目名称为“计算机专业综合”，代码分别为461和961; 20092014年的科目代码与名称为“408计算机学科专业基础综合” ；2015年起，科目代码与名称改为“961 计算机学科专业基础综合”，本书书名以此为准。一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只 有一个选项是符合题目要求的。1下列程常段的时间复杂度是（）count =0;for （k = 1;kn,而对于k,每次循环都执行k=k*2,所以循环次数为10g 2n；内部循环的退出条件是jn,对于j ,每

3、次循环都执行j =j+1 ,所以每次循环次数为n次。所以此程序段的时间复杂度为O （nlogzn）,即选C。g转换为等价后缀表达式的2.假设栈初始为空，将中缀表达式a/b c d e f过程中，当扫描到f时，栈中的元素依次是()CD. /【答案】B【解析】中缀表达式转后缀表达式遵循以下原则：(1)遇到操作数，直接输出；(2)栈为空时，遇到运算符，入栈；(3)遇到左括号，将其入栈；(4)遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；(5)遇到其他运算符+-*/ 时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；6)最终将栈中的元素依次出栈，输

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

5、队空：end1= = end2; 队满：end2= (end1+1) mod (M-1)C.队空：end2= (end1+1) modM ; 队满：end1 = = ( end2+1) modMD.队空：end1= (end2+1) modM; 队满：end2= (end1+1) mod (M-1)【答案】A【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加 1 后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。4若对如下的二叉树进行中序线索化，则结点x 的左、右线索指向的结点分别是( )A e,cB e,aC d,cD b,a【答案】

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

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

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

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

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

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

12、C结果128超过了 8位定 点补码能表示的数的范围，会发生溢出14. float型整数据常用IEEE754单精度浮点格式表示，假设两个float型变量x和y分 别在32为寄存器f i和f2中，若(fi) =CC900000H, (f2)= B0C00000H则J x和y之间的关系 为：()xy且符号相同xy且符号相同xy且符号不同【答案】A【解析】两个数对应的IEEE754的标准形式为;浮点数S阶码尾数f111001 1001001 0000 0000 0000 0000 0000f210110 0001100 0000 0000 0000 0000 0000将IEEE754单精度形式的二进制

13、转化为浮点数公式为V= (-1) As*2A (E-Bias) *M由于f1 , f2的符号位都是1,所以f1 , f2符号相同，而阶码上f1f2 ,所以f1f2 ,所以f1的绝对值比f2大，而他们都是负数，所以f1f2 ,所以选A15.某容量为256M的存储器，由若干4M*8位的DRAM5片构成，该DRA就片的地址引脚和数据引脚总数是：（ ）A 19B 22C 30D 36【答案】 A【解析】DRAMft址线复用，4M为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为 19 根16.采用指令Cache与数据Cache分离的主要目的是（）A.减低Cache的缺失损失B.

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

15、的地址基址寄存器偏移量8441616位补码取值范围为-32768+32767,所以偏移量取值范围为-32768+32767 某计算机采用微程序控制器，共有 32 条指令， 公共的取指令微程序包含2 条微程序，各指令对应的微程序平均由 4 条微指令组成， 采用断定法 （下址字段法） 确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）A 5B 6C 8D 9【答案】 C【解析】32*4+2=130, 27= 128130left & !BT-right )return BT.weight * height;/ 如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WP6和

16、elsereturn CalcWPL ( BT-left, height+1 ) + CalcWPL( BT-right, height+1 ) ;（10分）某网络中的路由器运行 OSPF各由协议，题42表是路由器R1维护的主要链路状态信息（LSI）,题42图是根据题42表及R1的接口名构造出来的网络拓扑题42表R1所维护的LSIR1的LSIR2的LSIR3的LSIR4的LSI备注RouterID10.1.1.110.1.1.210.1.1.510.1.1.6标识路由器的IP地址LinklID10.1.1.210.1.1.110.1.1.610.1.1.5所连路由器的RounterIDIP10

17、.1.1.110.1.1.210.1.1.510.1.1.6Link1 的基本IP地址M etri c3366Link1 的费用Link2ID10.1.1.510.1.1.610.1.1.110.1.1.12所连路由器的RounterIDIP10.1.1.910.1.1.1310.1.1.1010.1.1.14Link2 基本IP地址Metic2424Link2 费用Net1P refi x192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/24直接网络Net1的网络前缀M etri c1111到达直连网络Net1的费用E0L01011210.1.1.2

18、1 mu o1一192.1.6.0/2410.1.1.134192.1.1.0/241|3J10.1.1.9210.1.1.1010.1.1.1410.1.1.6192.1.7.0/24题42图R1构造的网络拓扑请回答下列问题本题中的网络可抽象为数据结构中的哪种逻辑结构?针对题 42表中的内容， 设计合理的链式存储结构， 以保存题 42表中的链路状态信息 （LSI） 要求给出链式存储结构的数据类型定义，并画出对应题 42 表的链式存储结构示意图（示意图中可仅以 ID 标识节点）。按照迪杰斯特拉（Dijikstra ）算法的策略，依次给出R1到达题42图中子网192.1.x.x的最短路径及费用。

19、答： （ 1）图（ 2）使用图的邻接表存储结构进行存储，数据类型定义如下：typedef struct ArcNodeint adjvex; / 该弧指向路由器的位置， 0 为没有char *netid; / 该弧指向的网络的网络前缀, 空为没有char *linkip; / 路由的基础IP ，当 adjvex 不为 0 才有效struct ArcNode *nextarc; / 指向下一条弧的指针int metric; / 连接的权值ArcNode; / 表结点typedef struct RouterNodechar *routerid; 路由的 routeridArcNode *firs

20、tarc; / 第一个结点地址RouterNode,RouterNUM; / 头节点链式存储结构示意图如下图所示：(3)目标网络 192.1.1.0/24 记为 N1, 192.1.5.0/24 记为 N2,192.1.6.0/24 记为N3,192.1.7.0/24 记为N4,使用dijkstra算法找最短路径步骤如下表所示：步骤S集合U集合1选入R1,此时S= R1此时最短路径为R1-R1 0U=R2,R3,R4,N1,N2,N3,N4R1-R2= 3 R1-R3=2R1-N1 1 最短2选入N1,此时S= R1,N1最短路径为 R1-R1 0,R1-N1 1U= R2,R3,R4,N2,

21、N3,N4R1-R2= 3 R1-R3-2O3选入 R3,此时 S= R1,N1,R3U= R2,R4,N2,N3,N4最短路径 R1-R1 0,R1-N1 1,R1-R3=2R1-R2=3, R1-R3-N3 =3取短R1-R3-R4=84选入 N3,此时 S=R1,N1,R3,N2最短路径 R1-R1-0,R1-N1-1,R1-R3=2R1-R3-N3=3U=R2,R4,N2,N4R1-R2=3O, R1-R3-R4=85选入R2,此时S=R1,N1,R3,N2,R2最短路径 R1-R1-0,R1-N1-1,R1-R3=2R1-R3-N3=3,R1-R2=3U=R4,N2,N4R3-R4=

22、6, R1-R2-N2 =4取短6选入N2,此时S=R1,N1,R3,N2,R2,N2最短路径 R1-R1-0,R1-N1-1,R1-R3=2R1-R3-N3=3,R1-R2=3,U=R4,N4R1-R3-R4= 8,R1-R2-R47取短R1-R2-N2= 47选入R4,此时S=R1,N1,R3,N2,R2,N2,R4最短路径 R1-R1 0,R1-N1 1,R1-R3=2R1-R3-N3=3,R1-R2=3,R1-R2-N2= 4,R1-R2-R4= 7U= N4R1-R2-R4-N4=8R1-R3-R4-N4=98选入N4, S =R1,N1,R3,N2,R2,N2,R4,N4最短路径

23、R1-R10,R1-N1 1,R1-R3=2R1-R3-N3=3,R1-R2=3,R1-R2-N2= 4,R1-R2-R4= 7R1-R3-R4-N4=9U为空，查找结束所以R1到达子网192.1.1.0/24 最短路径为：R1-子网，费用为1R1到达子网192.1.6.0/24 的最短路径为：R1-R2-子网，费用为3R1到达子网192.1.5.0/24 的最短路径为：R1-R3-子网，费用为4R1到达子网192.1.7.0/24 的最短路径为R1-R2-R4-T网，费用为8(9分)请根据题42描述的网络，继续回答下列问题。(1)假设路由表结构如下表所示，请给出题 42图中R1的路由表，要求

24、包括到达题42 图中子网192.1.x.x的路由，且路由表中的路由项尽可能少。目的网络下一跳接口(2)当主机192.1.1.130向主机192.1.7.211发送一个TTL= 64的IP分组时，R1通过 哪个接口转发该IP分组？主机192.1.7.211收到的IP分组的TTL是多少？(3)若R1增加一条 Metric为10的链路链接Internet ,则题42表中R1的LSI需要增 加哪些信息？答：(1)目的网络下一跳口接192.1.1.0/24/0E192.1.5.0/24R31L192.1.6.0/24R20L192.1.7.0/24R20L(2)通过接口 L0转发该IP分组，由于要经过R

25、1,R2,R4三个路由器，所以主机192.1.7.211 收到的IP分组的TTL为64-3=61.(3)只需要在 R1的LSI中增加一项信息，prefix =目的internet , Metric =10.44. (11分)某程序中有如下循环代码段 p: “for (i =0;iN;i+ ) sum- Ai; 。假 设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中，数组A的首地 址在寄存器R3中，程序段P起始地址为0804 8100H,对应的汇编代码和机器代码如题 44表 所示编号地址机器代码汇编代码注释108048100H00022080HLoop: sllR4;R2

26、,2(R2)2f R4208048104H00083020HAdd R4;R4,R3(R4)+ ( R3) - R4308048108C8500Load R5;0(R4)+0) 一 R58H00H(R4)40804810CH00250820HAdd R1;R1,R5(R1) + ( R5) - R1508048110H2042000HAdd R2;R2,1(R2)+2 一 R4608048114H1446FFFAHBneR2;R2,loopif (R2)! = (R6) goto loop执行上述代码的计算机M采用32位定长指令字，其中分支指令Bne采用如下格式,3226 2521 2016

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

28、分 支指令的执行均引起3 个时钟周期阻塞， 则 P 中哪些指令的执行会由于数据相关而发生流水线阻塞？哪条指令的执行会发生控制冒险？为什么指令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 FFFAH1 卜6。由题可知Bn

29、e采用相对寻址方式，故有效地址 EA= （ P。+A= （ P。+OFFSET而PC的 值为当前Bne指令的地址即（P。=08048114而取完Bne指令后，（P。+4-PC,故（P。 = 0804 8118H。而要跳车$到指令1的地址08048100H两者相差了 18H也就是24个字节，而 OFFSET1-6,故转移目标地址计算公式为（PQ +OFFSET*（24/6） = （ PQ +OFFSET*4（4）由指令序列可知，指令1需写R4而指令2需读R4,故指令2会因为数据相关而发生阻塞，同理指令3、指令4 也会因为数据相关而发生阻塞；而指令6 为分支指令，故其存在控制冒险。 因为分支指令会

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

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

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

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

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

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

36、：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;( mutex2) ;( empty ;count =0;( available ) ;2013年北京航空航天大学计算机学院408计算机学科专业基础

37、综合真题及详解一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只 有一个选项符合试题要求。.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为 m+n的降序链表, 则最坏情况下的时间复杂度是()O (n)O (m*n)O (min (m,n)O (max (m,n)【答案】D【解析】m和n是两个升序链表 长度分别为m和n,在合并过程中最坏的情况是两个链 表中的元素依次进行比较，比较的次数是m和n中的最大值。. 一个栈的入栈序列为1,2,3,n,其出栈序列是Pi, a, P3Pno若，则P2= 3, 则P3可能取值的个数是()n-3n-2n-1D.无法确定【

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

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