2013年全国硕士研究生统一入学考试自命题试题（副卷）
******************************************************************************************** 学科与专业名称：计算机系统结构、计算机软件与理论、计算机应用技术、软件工程
考试科目代码与名称：834 计算机学科与技术基础综合
考试科目：计算机学科与技术基础综合共6 页，第1 页
考试科目：计算机学科与技术基础综合共6 页，第2 页
考试科目：计算机学科与技术基础综合共6 页，第3 页
考试科目：计算机学科与技术基础综合共6 页，第4 页
考试科目：计算机学科与技术基础综合共6 页，第5 页
考试科目：计算机学科与技术基础综合共6 页，第6 页。
2022考研计算机学科专业根底综合真题及答案一、单项选择题：1~40小题，每题2分，共80分。
以下每题给出的四个选项中，只有一个选项符合试题要求。
1.设n是描绘问题规模的非负整数，以下程序段的时间复杂度是x=0；while(n>=(x+l)*(x+l))x=x+l；A. O(log n)B. O(n1/2)C. O(n)D. O(n2)2.假设将一棵树T转化为对应的二又树BT，那么以下对BT的遍历中，其遍历序列与T的后根遍历序列一样的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3.对n个互不一样的符号进展哈夫曼编码。
假设生成的哈夫曼树共有115个结点，那么n的值是A. 56B. 57C. 58D. 604.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
以下关于T1与T3的表达中，正确的选项是I.假设v是T1的叶结点，那么T1与T3可能不一样Ⅱ.假设v不是T1的叶结点，那么T1与T3一定不一样Ⅲ.假设v不是T1的叶结点，那么T1与T3一定一样A. 仅IB. 仅IIC. 仅I、ⅡD. 仅I、Ⅲ5.以下列图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间分别是A. 3和7B. 12和12C. 12和14D. 15和156.用有向无环图描绘表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，以下因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性 V.数据的初始状态A. 仅ⅢB. 仅I、ⅡC. 仅Ⅱ、Ⅲ、IVD. I、Ⅱ、Ⅲ、Ⅳ8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A. 4B. 5.25C. 6D. 6.299.设主串T=“abaabaabcabaabc〞，形式串S=“abaabc〞，采用KMP算法进展形式匹配，到匹配成功时为止，在匹配过程中进展的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进展一遍处理称为一“趟〞。
考研计算机学科专业基础综合-28(总分146,考试时间90分钟)一、单项选择题在每小题给出的四个选项中，请选出一项最符合题目要求的。
1. 若一个栈的输入序列为1，2，3，…，n，输出序列的第一个元素是i，则第j个输出元素是______。
A．i-j-1 B．i-j C．j-i+1 D．不确定2. 若循环队列以数组Q[0..m-1]作为其存储结构，变量rear表示循环队列中的队尾元素的实际位置，其移动按rear=(rear+1)MOD m进行，变量length表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是______。
A．rear-length B．(rear-length+m) MOD mC．(1+rear+m-length) MOD m D．m-length3. 已知有一维数组A[0..m*n-1]，若要对应为m行、n列的矩阵，将元素A[k](O≤k＜m*n)表示成矩阵的第i行、第j列的元素(0≤i＜m，0≤j＜n)，则下面的对应关系是______。
A．i=k/n，j=k%m B．i=k/m，j=k%mC．i=k/n，j=k%n D．i=k/m，j=k%n4. 由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是______。
A．27 B．38 C．51 D．755. 设结点x和y是二叉树中任意的两个结点，在该二叉树的先序遍历序列中x在y之前，而在其后序遍历序列中x在y之后，则x和y的关系是______。
A．x是y的左兄弟 B．x是y的右兄弟C．x是y的祖先 D．x是y的后裔6. 在一棵完全二叉树中，其根的序号为1，下列可判定序号为p和q的两个结点是否在同一层的正确选项是______。
7. 若G是一个具有36条边的非连通无向图(不含自回路和多重边)，则图G的结点数至少是______。
A．11 B．10 C．9 D．88. 有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是______。
考研计算机学科专业基础综合真题汇编及答案解析（2）(1/14)单项选择题第1题设n是描述问题规模的非负整数，下面程序片段的时间复杂度是_______。
x=2；while(x＜n ／2)x=2*x；A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )下一题(2/14)单项选择题第2题知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是_______。
A.O(n)B.O(m×n)C.O(min(m，n))D.O(max(m，n))上一题下一题(3/14)单项选择题第3题求整数n(n＞0)阶乘的算法如下，其时间复杂度是_______。
int fact(int n){if(n＜=1)return 1；return n*fact(n-1)，}A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )上一题下一题(4/14)单项选择题第4题下列程序段的时间复杂度是_______。
count=0；for(k=1，k＜=n；k*=2)for(j=1，j＜=n，j++)count++；A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n 2 )上一题下一题(5/14)单项选择题第5题若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是_______。
A.dcebfaB.cbdaefC.bcaefdD.afedcb。
考研计算机学科专业基础综合-33(总分80,考试时间90分钟)一、单项选择题在每小题给出的四个选项中，请选出一项最符合题目要求的。
1. 若已知一个栈的入栈序列是1，2，3．…n，其输出序列为p1，p2，p3，…pn，若p1=n，则pi是( )。
A．i B．n—i C．n—i+1 D．不确定2. 将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A66,65(即该元素下标i=66，j=65)，在B数组中的位置k为( )。
A．198 B．195 C．197 D．1963. 查找效率最高的二叉排序树是( )。
A．所有结点的左子树都为空的二叉排序树B．所有结点的右子树都为空的二叉排序树C．平衡二叉树D．没有左子树的二叉排序树4. 一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树的结点数是( )。
A．2k-1-1 B．2k-1 C．2k-1+1 D．2k-15. 判断以下叙述的正确性Ⅰ对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图Ⅱ连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点Ⅲ图的深度优先搜索中一般要采用栈来暂存访问过的顶点A．Ⅰ、Ⅱ B．Ⅱ、Ⅲ C．Ⅰ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ6. 一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中零元素的个数是( )。
A．e B．2e C．n2-e D．n2-2e7. 从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是( )。
A．二叉排序树 B．大顶堆 C．小顶堆 D．平衡二叉树8. 顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块。
若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为( )。
A．21 B．23 C．41 D．629. 在下列存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系的是( )。
