2012~2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详

中国科学院大学2015年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机学科综合(专业)考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．下列数据结构中，（）是非线性数据结构。

A．栈 B.队列 C.二叉树 D.堆2．在非空双向循环链表中q所指的结点后插入一个由p所指的链结点的过程依次为：rlink(p)<-rlink(q); rlink(q)<-p; llink(p)<-q; ( )A. rlink(q)<-pB. rlink(llink(p))<-pC. llink(rlink(p))<-pD. rlink(rlink(p))<-p3. 若一个栈以向量V[1…n]存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是（）。

A．top=top+1; V[top]=x B. V[top]=x; top=top+1C. top=top-1; V[top]=xD. V[top]=x; top=top-14. 若6行5列的数组以行序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是（）。

A. 1040B. 1042C. 1026D. 以上答案都不对5．A[N,N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i(i-1)/2+jB. j(j-1)/2+iC. i(j-i)/2+1D. j(i-1)/2+16. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。

A．CABDEFG B. ABCDEFG C. DACEFBG D. ADCFEGB7. 有n(n>0)个分支结点的满二叉树的深度是（）。

2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解一、单项选择题：1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（）。

A．main（）->S（1）->S（0）B．S（0）->S（1）->main（）C．main（）->S（0）->S（1）D．S（1）->S（0）->main（）【答案】A【解析】函数S（int n）是一个递归函数：①当实际参数小于等于零时则返回0，并终止递归；②当实际参数大于零时则递归调用S（n－1），并将S（n－1）的结果加上n作为返回值。

程序从main（）函数开始，首先调用main（）函数；在main（）函数中调用S （1）函数时，将main（）函数的上下文保存到栈中，并进入函数S（1）；由于函数S（1）的实际参数大于零，需要调用S（0），故将S（1）函数的上下文保存到栈中，进入S（0）；在S（0）中，实际参数小于等于零，递归终止。

2．先序序列为a，b，c，d的不同二叉树的个数是（）。

A．13B．14C．15D．16【答案】B【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。

本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树；③bc为左子树，d为右子树；④bcd为左子树，右子树为空。

然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有：a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。

按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。

2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：int s(int n){ return (n<=0) ? 0 : s(n-1) +n; }void main(){ cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main()C．m ain()->S(0)->S(1) D．S(1)->S(0)->main()【参考答案】D【考查知识点】栈的基本概念和函数调用的原理。

2．先序序列为a,b,c,d的不同二叉树的个数是A．13 B．14 C．15 D．16【参考答案】C【考查知识点】二叉树的基本概念。

3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7 B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，6【参考答案】C【考查知识点】哈夫曼树的原理。

4．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2 B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【考查知识点】树的中序遍历和A VL树的基本概念。

5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D．5【参考答案】D【考查知识点】图的深度优先遍历。

5.2 典型题（含历年真题）详解一、单项选择题1．设有向图G＝（V，E），顶点集V＝{V0，V1，V2，V3}，边集E＝{<V0，V1>，<V0，V2>，<V0，V3>，<V1，V3>}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是（）。

[2015年联考真题]A．2B．3C．4D．5【答案】D【解析】根据题意知有向图的结构如图所示。

深度优先遍历的特点是尽可能先对纵深方向进行搜索，所以可能得到的不同遍历序列分别是：①V0→V2→V1→V3；②V0→V2→V3→V1；③V0→V1→V3→V2；④V0→V3→V2→V1；⑤V0→V3→V1→V2。

2．对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。

[2014年联考真题] A．3，1，2，4，5，6B．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。

所以选D3．设图的邻接矩阵A如下所示，各顶点的度依次是（）。

[2013年联考真题]A．1，2，1，2B．2，2，1，1C．3，4，2，3D．4，4，2，2【答案】C【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

4．下列AOE网表示一项包含8个活动的工程。

通过同时加快若干进度可以缩短整个工程的工期。

下列选项中，加快其进度就可以缩短工程工期的是（）。

[2013年联考真题]A．c和eB．d和eC．f和dD．f和h【答案】C【解析】根据AOE网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。

第3部分模拟试题全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合模拟试题及详解（一）一、单项选择题（1～40小题，每小题2分，共80分。

）1．下面关于算法说法正确的是（）。

A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的【答案】D【解析】A项，计算机程序只是实现算法的一种手段，手工也可以完成；B项，算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，程序是为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。

两者显然是不同的概念；C项，明显错误，可行性是指算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。

2．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）。

A．O（1）B．O（n）C．O（m）D．O（m＋n）【答案】C【解析】将长度为n的单链表接到长度为m的单链表之后只需要定位到m链表的末尾，然后将末尾元素的指针指向n链表，故时间复杂度为O（m）。

3．若某线性表最常用的操作是存取任一指定序号的元素并在表尾进行插入和删除运算，则利用（）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表【答案】A【解析】只有顺序表才能存取任一指定序号的元素，其他存储方式都需要遍历才能访问相应元素。

顺序表在表尾进行插入和删除运算的时间复杂度也为O（1）。

4．执行以下（）操作时，需要使用队列作为辅助存储空间。

A．散列表的查找B．图的广度优先遍历C．二叉树的先序遍历D．图的深度优先遍历【答案】B【解析】A项，散列表的查找不需要额外的空间；C、D项，二叉树的先序遍历和图的深度优先遍历使用堆栈而不使用队列作为辅助存储空间；B项，在图的广度优先遍历中，如果结点v i在v k之前被访问，则v i的所有未被访问的邻接点应在v k的所有未被访问的邻接点之前访问，需要使用队列作为辅助存储空间。

中国科学院大学攻读硕士学位研究生入学统一考试试题科目名称：计算机专业综合考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3．试卷共16道大题，每题15分，共240分，考生可以任意选择其中10道大题回答，并在答题纸的该题答案前标明“选做本题”。

4．如果选做的题目多于10道，则判卷将按照所选做试题的题号顺序选择前10道大题计分，后续所做视为无效考试内容。

第一部分：《数据结构》第一题，简答题，共15分（1）请给出下列程序的时间复杂度（n>0）。

（2分）void func(int n) {int i,j;for(i=1,j=0; j<=n; j=j+i) i++;}（2）现有一个线性表的应用，线性表的元素总数不确定，其主要的操作是插入元素、删除表尾元素、查找表尾结点和查找指定结点的前驱结点，那么请问用怎样的数据结构比较好？请给出理由和该数据结构的C语言定义。

（3分）（3）若循环队列存储在数组A[0..m]，头指针Front指向当前队头元素，尾指针Rear指向当前队尾元素的下一个位置，那么当前实际存储有多少队列元素？现有元素x需要入队，请写出元素入队的语句。

（3分）科目名称：计算机专业综合第1页共6页（4）用如下数据结构存储广义表：typedef enum {ATOM, LIST} ElemTag;typedef struct GLNode {ElemTag tag;union {AtomType atom;struct {struct GLNode *hp, *tp;} ptr;}} *Glist;那么，对于广义表X=(A,((),(B,C)),(D,E))，给出其存储结构图，并利用Head、Tail 操作分离出元素E。

（3分）（5）现在需要从5000个元素组成的序列中，用最快的速度挑出前10个最大的元素。

请在插入排序、快速排序、堆排序、归并排序、基数排序中选择一个最合适的排序方法，并说明理由。

2012年全国硕士研究生入学统一考试计算机专业基础综合考试预测数据结构1. 线性表的存储结构对比问题：链式存储和顺序存储的优缺点对比，各使用于那种应用场合2. 二叉树的构造与遍历问题：给定二叉树，能给出相应的前中后序遍历序列；给定一个中序遍历序列，再给出一个前序或后序遍历序列，构造出二叉树3. 树、二叉树和森林的相互转换问题：树<->二叉树<->森林之间的转换问题，注意树的左孩子右兄弟表示法4. Huffman树的构造与Huffman编码：节点的权值，根到叶子节点的路径长度；给定一组数据的出现频率，构造相应的Huffman码5. 图相关的定义问题：有向图，无向图，连同，强连通等概念的对比6. 图的关键路径问题：给定一个图，能求出相应的关键路径，并且能给出求关键路径所需的中间表格7. 图的最小生成树问题：Prim算法和Kruskal算法的具体步骤，给定一个图，能使用给定的算法构造相应的最小生成树8. 二分查找算法的基本方法：给定一组数据和需要查找的关键字，能够给出二分查找经过的节点序列9. 排序算法的特征问题：给定一组数据的初始状态和经过若干论排序后的状态，能推断出所使用的排序算法10. 算法复杂度分析问题：能够给出特定算法用大O表示的时间或空间复杂度计算机组成原理1. 计算机硬件性能指标计算问题：访问速率，存储容量，访问周期等指标的计算2. 奇偶校验码与循环冗余校验码：给定条件下奇偶校验码与循环冗余校验码的计算3. ROM与RAM的对比问题：存储特性，成本，速率等4. 主存储器的字位扩展问题：存储器的设计5. 段页式虚存的工作原理：段表，页表的构建，更新与访问，虚存访问的过程6. 指令的基本格式问题：操作码，地址码7. 指令系统设计问题：指令长度，操作码，地址码长度等问题8. 硬布线控制器与微程序控制器对比：设计复杂性，成本，效率，产生控制信号的方式等9. I/O设备编址：统一编址与单独编址方式的对比10. 中断：相关的概念，执行过程，用到的硬件等操作系统1. 经典同步问题：生产者消费者问题，读者写者问题，哲学家问题，以及应用PV操作解决经典同步问题的衍生或变形的问题2. 文件的共享与保护问题：不同共享与保护方法的对比3. 死锁的检测与解除：资源分配图法，死锁解除方法4. 缓存技术：缓解外设与CPU计算速率矛盾的方法5. 虚存的特征问题6. 进程状态转移问题：进程的创建，就绪，运行，阻塞，挂起等状态及其相互转换发生的条件7. 作业调度问题：不同的作业调度算法的对比8. 抖动与Belady现象：由于存储管理方式选用不当带来的系统效率下降问题9. 文件的存储方式：连续，链接，索引方式10. 磁盘调度问题：电梯算法，扫描算法等调度方法相关的计算问题11. 文件的逻辑结构计算机网络1. 数据链路层中的流量控制与可靠传输机制2. 有关物理层的数据传输率计算3. 电路交换、报文交换与分组交换4. OSI参考模型的分层结构5. 多帧华东窗口与后退N帧协议（GBN）6. 数据链路层介质访问控制协议7. 网际协议；IPv4ICMP协议8. 应用层DNS系统9. TCP可靠传输10. 电路交换、报文交换和分组交换11. 网络层的子网划分和路由协议12. 层的数据传输率计算13. 网络层的功能14. 信源跟信宿的概念15. 等待协议和退N帧协议希望通过预测，帮助广大考生在最后的关键时刻，梳理知识体系，准确把握命题点，直击命题要害，进而做好最终的考前冲刺。

2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是。

int fact(int n){if (n<=1) return 1;return n*fact(n-1);}A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)2．已知操作符包括…+‟、…-‟、…*‟、…/‟、…(‟和…)‟。

将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是。

A．5 B．7 C．8 D．113．若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点。

A. 只有eB. 有e、bC. 有e、cD. 无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为。

A. 10B. 20C. 32D. 335．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是。

A．O(n) B．O(e) C．O(n+e) D．O(n*e)6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是。

A．存在，且唯一B．存在，且不唯一C．存在，可能不唯一D．无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是。

A．d,e,f B．e,d,f C．f,d,e D．f,e,d8．下列关于最小生成树的叙述中，正确的是。

2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项符合题目要求。

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：int s(int n){ return (n<=0) ? 0 : s(n-1) +n; }void main(){ cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是A．main()->S(1)->S(0) B．S(0)->S(1)->main()C．m ain()->S(0)->S(1) D．S(1)->S(0)->main()2．先序序列为a,b,c,d的不同二叉树的个数是A．13 B．14 C．15 D．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和24，10，7 B．24，10，5和24，12，7C．24，10，10和24，14，11 D．24，10，5和24，14，64．现在有一颗无重复关键字的平衡二叉树（A VL树）,对其进行中序遍历可得到一个降序序列。

下列关于该平衡二叉树的叙述中，正确的是A．根节点的度一定为2 B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树5．设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A．2 B．3 C．4 D．56．求下面带权图的最小（代价）生成树时，可能是克鲁斯卡（kruskal）算法第二次选中但不是普里姆（Prim）算法（从V4开始）第2次选中的边是A．(V1,V3) B．(V1,V4) C．(V2,V3) D．(V3,V4)7．下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508．已知字符串S为“abaabaabacacaabaabcc”. 模式串t为“abaabc”, 采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5,则下次开始匹配时，i和j的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A．直接插入排序B．起泡排序C．基数排序D．快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A．1 B．2 C．3 D．411．希尔排序的组内排序采用的是（）A．直接插入排序B．折半插入排序 C．快速排序D．归并排序12．计算机硬件能够直接执行的是（）Ⅰ．机器语言程序Ⅱ．汇编语言程序Ⅲ．硬件描述语言程序A．仅ⅠB．仅ⅠⅡC．仅ⅠⅢD．ⅠⅡⅢ13．由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（）A．-126 B．-125 C．-32 D．-314．下列有关浮点数加减运算的叙述中，正确的是（）Ⅰ. 对阶操作不会引起阶码上溢或下溢Ⅱ. 右规和尾数舍入都可能引起阶码上溢Ⅲ. 左规时可能引起阶码下溢Ⅳ. 尾数溢出时结果不一定溢出A．仅ⅡⅢB．仅ⅠⅡⅣC．仅ⅠⅢⅣD．ⅠⅡⅢⅣ15．假定主存地址为32位，按字节编址，主存和Cache之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（Write Back）方式，则能存放4K字数据的Cache 的总容量的位数至少是（）A．146k B．147K C．148K D．158K16．假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt, 3”，其中xaddt是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB，且Cache使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（）A．0 B．1 C．2 D．317．下列存储器中，在工作期间需要周期性刷新的是（）A．SRAM B．SDRAM C．ROM D．FLASH18．某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲突的地址对是（）A．8004、8008 B．8002、8007 C．8001、8008 D．8000、800419．下列有关总线定时的叙述中，错误的是（）A．异步通信方式中，全互锁协议最慢B．异步通信方式中，非互锁协议的可靠性最差C．同步通信方式中，同步时钟信号可由多设备提供D．半同步通信方式中，握手信号的采样由同步时钟控制20．若磁盘转速为7200转/分，平均寻道时间为8ms,每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是( )A．B．C．D．21．在采用中断I/O方式控制打印输出的情况下，CPU和打印控制接口中的I/O端口之间交换的信息不可能是( )A．打印字符B．主存地址C．设备状态D．控制命令22．内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合模拟试题及详解（一）一、单项选择题（1～40小题，每小题2分，共80分。

）1．以下算法的时间复杂度是（）。

A．O（n）B．O（n3）C．O（nlog2n）D．O（n2）【答案】D【解析】该算法的基本运算是语句x＋＋，设其执行时间为T（n），则有：2．设栈的初始状态为空，当字符序列n1_作为栈的输入时，输出长度为3的且可用作C语言标识符的序列有（）个。

A．3B．4C．5D．6【答案】A【解析】本题主要考查的内容有两个：C语言关于标识符的规定和栈的先进后出的特性。

标识符的第一个字符必须是大小写英文字符或者下划线，而不能是数字。

按照上述规定n1_三个字符符合规定的标识符有n1_，n_1，_1n，_n1四种形式。

字符按照n1_的顺序进栈，根据栈的先进后出的特性，输出的顺序只能出现前三种形式：①输出n1_的实现：n进栈再出栈，1进栈再出栈，_进栈再出栈；②输出n_1的实现：n进栈再出栈，1进栈_进栈，_出栈1出栈；③输出_1n的实现：n进栈1进栈_进栈，_出栈1出栈n出栈。

而输出_n1的情况不可能实现。

3．设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是（）。

A．872B．860C．868D．864【答案】B【解析】由二维数组按行优先寻址计算公式LOC（a ij）＝LOC（a00）＋（i×n＋j）×d 可知，LOC（a[3][5]）＝LOC（a[0][0]）＋（3×10＋5）×4＝1000，计算可求出LOC（a[0][0]）＝860。

4．下面叙述中正确的是（）。

A．若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列中的最后一个结点B．若有一个结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列中的最后一个结点C．若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的先序遍历结果序列中的最后一个结点D．若有一个叶子结点是二叉树中某个子树的先序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列中的最后一个结点【答案】C【解析】中序遍历和先序遍历都是最后遍历右子树，要想中序遍历的最后一个结点是叶子结点，则该结点一定是根结点的右子树的最右下结点（该结点无左孩子），在这种情况下，中序遍历和先序遍历的遍历序列的最后一个结点是一样的。

2012年全国硕士研究生入学统一考试计算机专业基础综合考试预测临近考研，考研专业课教研中心，深入研究2012年考研统考专业课考试大纲，结合统考专业课的命题趋势、规律及特点，经过反复推敲锤炼之后，分析提炼各层级知识核心要点，从而对本年的考研命题进行预测，帮助学员把握出题重点。

数据结构1. 二叉树的存储结构2. 关键路径3. 哈夫曼（Huffman）树4. 快速排序5. 冒泡排序6. 平衡二叉树的概念、性质与构造7. 二叉树、树、森林的遍历8. 树、森林与二叉树的转换9. 树的概念与性质以及相关计算10. 顺序查找法与折半查找法11. 特殊矩阵的压缩存储12. 拓扑排序13. 无向连通图特性14. 线索二叉树的概念及线索二叉树的遍历15. 线性表中单链表相关算法设计与实现16. 栈和队列的应用17. 最小生成树计算机组成原理1. Cache结构及编址2. DMA方式3. RISC和CISC的基本概念4. TLB（快表）5. 程序中断方式6. 存储器的分类及层次化结构7. 定点数、浮点数的表示与运算8. 机器指令与微指令的关系9. 计算机系统层次结构10. 计算机相关工作过程的理解11. 数制与编码12. 微命令、微操作、微指令和微程序13. 硬布线控制器和微程序控制器的特点14. 与程序中断方式和DMA方式相关的计算15. 指令格式及其寻址方式16. 总线的性能指标计算、仲裁方式操作系统1. 存储的分区问题：静态分区，动态分区，不同分区方法的优劣2. 进程调度问题：先来先服务，优先级调度，分时轮转等3. I/O设备定义及相关问题：I/O设备的分类等4. 死锁的产生与预防：死锁的定义，死锁产生的必要条件，通过克服死锁产生的必要条件而预防死锁5. 操作系统的发展历程与相关的基本概念问题：多道系统，分时系统，实时系统等的特征，现代操作系统的四大特性6. 请求段页式存储分配问题7. 文件与目录的定义问题：相关的概念作出判读8. 索引文件系统管理：计算文件系统支持的最大文件大小，给出文件访问时需要访问的磁盘块数9. 文件的逻辑结构10. 设备的分配与回收：不同的分配方法，回收方法以及相应的过程11. 进程的同步与互斥问题：临界区，临界段，硬件实现的互斥访问计算机网络1. CIDR技术：变长掩码，子网设计，IP地址分配2. ISOOSI/RM参考模型与TCP/IP模型：两种模型各层的功能与对应关系3. 局域网相关特性：MAC地址，使用的硬件设备，帧结构等4. IP头部个字段的含义5. 信源与信宿的概念6. 应用层基本概念7. UDP头部：UDP头部结构，端口的概念，常用端口号8. TCP可靠传输机制：TCP重传机制，TCP头部序列号9. 路由算法：链路状态算法，最短路径算法10. FTP协议：工作方式11. 数据链路层成帧问题：三种主要的成帧方法希望通过预测，帮助广大考生在最后的关键时刻，梳理知识体系，准确把握命题点，直击命题要害，进而做好最终的考前冲刺。

2012 全国硕士研究生入学统一测试计算机学科专业基础综合试题模拟题三一、单项选择题：第1~40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1. 在具有n 个结点的顺序表，算法的时间复杂度是O(1)的操作是A. 访问第i 个结点(1≤i≤n)和求第i 个结点的直接前驱(2≤i≤n)B．在第i 个结点后插入一个新结点(1≤i≤n)C．删除第i 个结点(1≤i≤n)D．将n 个结点从大到小排序2. 使用双链表存储线性表，其优点是I 提高查找速度II 更方便数据的插入和删除III 节约存储空间IV 很快回收存储空间A．I、II B．I、IV C．仅II D．II、III、IV3. 若进栈序列为a,b,c，则通过出栈操作可能得到a,b,c 的不同排列个数为A.4B.5C.6D.74. 若对n 阶对称矩阵A[1..n，1..n]以行序为主序方式下将其下三角的元素（包括主对角线上的所有元素）依次存放于一维数组B[1..n(n+1)/2]中，则在 B 中确定aij (i<j)的位置k 的关系是A．i(i-1)/2+j B．j(j-1)/2+iC．i(i+1)/2+j D．j(j+1)/2+i5. 在线索化二叉树中，t 所指结点没有左子树的充要条件是A．t->left=NULLC. t->ltag=1 且t->left=NULL B. t->ltag=1D. 以上都不对6. 若采用邻接矩阵来存储简单有向图，则其某一个顶点i 的入度等于该矩阵A．第i 行中值为1 的元素个数B. 所有值为1 的元素个数C．第i 行及第i 列中值为1 的元素总个数D．第i 列中值为1 的元素个数7. 在有11 个元素的有序表A[1..11]中进行折半查找，查找元素A[11]时，被比较的元素的下标依次是A.6,8,10,11B. 6,9,10,11C. 6,7,9,11D. 6,8,9,118. 设散列表表长m=14，散列函数H(k)=k MOD 11，表中已有15,38,61,84 四个元素，如果用线性探测法处理冲突，则元素49 的存储地址是A．8 B．3 C．5 D．99. 以下关于查找方法的说法正确的是I 顺序查找法只能在顺序存储结构上进行。