资源描述：
《北京航空航天大学计算机学院961计算机学科专业基础综合历年考研真题汇编》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、目 录2014年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解52013年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解212012年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解362011年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解542010年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解722009年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解882008年北京航空航天大学计算机学院961计算机专业综合考研真题1042007年北京航空
2、航天大学计算机学院461计算机专业综合考研真题110说明：2007～2008的科目名称为“计算机专业综合”，代码分别为461和961；2009～2014年的科目代码与名称为“408计算机学科专业基础综合”；2015年起，科目代码与名称改为“961计算机学科专业基础综合”，本书书名以此为准。2014年北京航空航天大学计算机学院408计算机学科专业基础综合真题及详解一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。1．下列程常段的时间复杂度是（）count＝0;for（k＝1;k<＝n;k*2）for
3、（j＝1;j<＝n;j+1）count++;A．O（log2n）B．O（n）C．O（nlog2n）D．O（n2）【答案】C【解析】外部循环的退出条件是k>n，而对于k，每次循环都执行k＝k*2,所以循环次数为log2n；内部循环的退出条件是j>n,对于j，每次循环都执行j＝j+1，所以每次循环次数为n次。所以此程序段的时间复杂度为O（nlog2n），即选C。2．假设栈初始为空，将中缀表达式转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是（）A．B．C．D．【答案】B【解析】中缀表达式转后缀表达式遵循以下原则：（1）遇到操作数，直接输出；（2）
4、栈为空时，遇到运算符，入栈；（3）遇到左括号，将其入栈；（4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出；（5）遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈；（6）最终将栈中的元素依次出栈，输出。所以扫描到’/’，入栈‘描到’+’,由于’+’优先级比’/’低，所以将’/’弹出，’+’入栈；扫描到’*’,优先级比’+’高，入栈；扫描到’（‘,入栈;扫描到’-‘,将栈中优先级更高的’*’弹出，‘-’入栈;扫描到’*’,优先级比’-‘高，入栈。所以扫描到f的时候，
5、栈中元素为：3．循环两列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）A．队空：end1＝＝end2；队满：end1＝＝（end2+1）modMB．队空：end1＝＝end2;队满：end2＝＝（end1+1）mod（M-1）C．队空：end2＝＝（end1+1）modM;队满：end1＝＝（end2+1）modMD．队空：end1＝＝（end2+1）modM;队满：end2＝＝（end1+1）m
6、od（M-1）【答案】A【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。4．若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是（）A．e,cB．e,aC．d,cD．b,a【答案】D【解析】此二叉树的中序遍历序列为：debxac,由于节点x左右孩子都为空，所有进行中序线索化时，它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b和直接后继结点a，所以选D5．将森林F转换为对应的二叉树T，F中叶结点的个数等于（）A．T中叶结点的
7、个数B．T中度为1的结点个数C．T中左孩子指针为空的结点个数D．T中右孩子指针为空的结点个数【答案】C【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的，即左孩子指针指向当前节点的孩子节点，右孩子指针指向当前节点的兄弟节点，所以在T中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C6．5个字符有如下4种编码方案，不是前缀编码的是（）A．01,0000,0001,001,1B．011,000,001,010,1C．000,001,010,011,100D．0,100,110,1110,1100【答案】D【解析】在一个字符集中，任何一个字符的编
8、码都不是另一个字符编码的前缀。约定左分支表示字符‘0’，右分支表示字符‘1’，则
