下载文档原格式
2018年全国硕士研究生入学统一考试计算机学科专业基础综合试卷一、单项选择题：140小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合题目要求。
请在答题卡上将所选项的字母涂黑。
b5E2RGbCAP 1．已知程序如下：ints(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(>p1EanqFDPwC．main(>->S(0>->S(1> D．S(1>->S(0>->main(>DXDiTa9E3d【参考答案】 D【考查知识点】栈的基本概念和函数调用的原理。
2．先序序列为a,b,c,d的不同二叉树的个数是A．13B．14C．15D．16【参考答案】 C【考查知识点】二叉树的基本概念。
3．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是A．24，10，5和 24，10，7B．24，10，5和24，12，7C．24，10，10和 24，14，11 D．24，10，5和 24，14，6【参考答案】 C【考查知识点】哈夫曼树的原理。
4．现在有一颗无重复关键字的平衡二叉树<AVL树）,对其进行中序遍历可得到一个降序序列。
下列关于该平衡二叉树的叙述中，正确的是RTCrpUDGiTA．根节点的度一定为2B．树中最小元素一定是叶节点C．最后插入的元素一定是叶节点D．树中最大元素一定是无左子树【参考答案】 B【考查知识点】树的中序遍历和AVL树的基本概念。
5．设有向图G=(V,E>，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若从顶点V0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是5PCzVD7HxAA．2 B．3 C．4 D．5【参考答案】 D【考查知识点】图的深度优先遍历。
考研计算机学科专业基础综合-3-1(总分150,考试时间90分钟)一、单项选择题1. 字长16位的补码定点小数的表示范围是( )。
A. 0～1-2-15B. -(1-2-15)～1-2-15C. -1～1-2-15D. -1～12. 当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于( )，则必须分裂成两个结点，当向一棵m阶的B-树做删除操作时，若一个结点中的关键字个数等于( )，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。
A. m，m/2-2B. m-1，m/2-1C. m+l，m/2D. m/2，m/2+13. 设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有( )个结点。
A. 13B. 12C. 26D. 254. 数据链路层采用了后退N帧(GBN)协议，发送方已经发送了编号为0～7的帧。
当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是( )。
A. 2B. 3C. 4D. 55. 一个C类地址，采用了255.255.255.240作为子网掩码，那么这个C类地址可以划分为( )个子网。
A. 16B. 32C. 64D. 1286. 测得一个以太网数据的波特率是40Mbps，那么其数据率是( )。
A. 10MbpsB. 20MbpsC. 40MbpsD. 80Mbps7. 同步通信比异步通信数据传输率高的原因是( )。
A. 同步通信不需要应答信号B. 同步通信使用公共时钟进行同步C. 同步通信中，通信双方的速度相近D. 以上都包括8. 传输线上的位流信号同步，应该属于下列OSI的( )层处理。
A. 物理层B. 数据链路层C. 网络层D. 传输层9. 补码定点小数除法中，被除数和除数应满足( )。
A. 0≤|被除数|≤|除数|B. 0＜|被除数|≤|除数|C. 0＜|除数|≤|被除数|D. 0＜|被除数|＜|除数|10. IEEE754标准浮点数的尾数采用( )机器数形式。
2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回忆版）数据结构部分一、选择题（共10道，一个2分，共20分）1．数据结构的逻辑结构分类是哪两种？2．给定一颗完全二叉树的结点数，求其中的叶节点个数3．一个有n个结点的图构成一个邻接矩阵几乘几的矩阵4～10暂缺二、简答题（共5道题，前四个15分，最后一个10分，今年没有编程题，也就是都是算法和推演，不用写代码，都是根据要求写结果和原理）1．给了8个左右的数字的一个集合，比如{75，63，43…}，要求一次读取一个，输出成一个二叉排序树，写出结果，并且求等概率情况下的平均查找长度。
2．给了一个包含有ABCDEFGH这几个点的二叉树的先序和中序排列，要求画出原二叉树。
3．一个指令集合{I1，I2，I3…}，对应给出了每个指令对应的发生概率大小{0.03，0.03，0.15，0.15，0.3，0.4}（这个数字印象比较深基本差不多），让求出用此集合构成的哈夫曼树。
求出他们的一个组织，并且求出每个指令的哈夫曼编码。
4．给出了一个由ABCDEFGHLM点组成的的无向带权图，让求出最小生成树（这里题干没有写用哪种算法）。
5．给定了一个树，转化成对应的二叉树，大概有8个点左右。
计算机网络部分一、选择题（共10道，一个1分，共10分）1．IPV4和IPV6的特征对比，选出一个错误的2．TCP拥塞控制中慢开始算法的特征，选出一个错误的3～10暂缺二、填空题（共10道，一个1分，共10分）1．IEEE802.11用的协议是_____2．CDMA2000采用的编码方式是_____3．移动IP的基本工作过程（给了其中3个步骤，填另一个）4．信道划分的三种方式（给了其中2个，填另一个）5～10暂缺三、简答题（共7道，共40分）1．主机A向主机B先后发两个报文，给出了每个报文的字节数，然后分别问了第一个先到的情况下和第二个报文先到的情况下各自的确认号，源，目的。
考研计算机学科专业基础综合-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的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是______。
考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔,确保硕士研究生的招生质量。
II考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。
要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
III考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。
二、答题方式答题方式为闭卷、笔试。
三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题,每小题2分)综合应用题70分IV考查内容数据结构【考查目标】1。
掌握数据结构的基本概念、基本原理和基本方法。
2。
掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解,具备采用C或C++语言设计与实现算法的能力.一、线性表（一)线性表的定义和基本操作(二）线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组（一)栈和队列的基本概念（二)栈和队列的顺序存储结构(三）栈和队列的链式存储结构(四）栈和队列的应用（五)特殊矩阵的压缩存储三、树与二叉树(一)树的基本概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3。
二叉树的遍历4.线索二叉树的基本概念和构造（三）树、森林1.树的存储结构2。
2018年华中科技大学834计算机专业基础综合复习八套卷一（版）一．填空题（20分，每题2分）1. 在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动个元素。
2. 栈是的线性表，其运算遵循的原则3. 表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是。
4. 己知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为。
5. 对矩阵压缩是为了。
6. 在哈希函数H（key）=key%p中，p值最好取。
7. IP地址21.12.240.17的网络类别是类，主机号是。
8. 100BASE-T标准规定的信号是，网络速率是。
9. 信息传输速率的单位是，码元传输速率的单位是。
10. 在TCP/IP网络中，TCP协议工作在，FTP协议工作在。
二．判断题（20分，每个2分）No. 1 2 3 4 5 6 7 8 9 10 Answer1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
（）2. 数据的物理结构是指数据在计算机内的实际存储形式。
（）3. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
（）4. 数组不适合作为任何二叉树的存储结构。
（）5. B-树中所有结点的平衡因子都为零。
（）6. 对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
（）7. 在OSI 参考模型中，最上层是物理层。
（）8. 在TCP 段头中，窗口数的大小由发送方决定。
（）9. 带宽的基本单位是bps,吞吐量的基本单位是Mbps。
（）10. 一个IPv4 地址表示193.168.125.0/30，其中，30 表示主机的位数。
（）三．选择题（30分，每个3分）No. 1 2 3 4 5 6 7 8 9 10 Answer1. int frog｛if(n==0)return 1;elsereturn （n+frog（n-1）/2）; ｝上述算法时间复杂度是多少（）A. lognB.nC. nlognD. (n)`22. 连续存储设计时，存储单元的地址（）。
考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。
II考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。
要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
III考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟。
二、答题方式答题方式为闭卷、笔试。
三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分(40小题，每小题2分)综合应用题70分IV考查内容数据结构【考查目标】1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
一、线性表(一)线性表的定义和基本操作(二)线性表的实现1.顺序存储2.链式存储3.线性表的应用二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储三、树与二叉树(一)树的基本概念(二)二叉树1.二叉树的定义及其主要特征2.二叉树的顺序存储结构和链式存储结构3.二叉树的遍历4.线索二叉树的基本概念和构造(三)树、森林1.树的存储结构2.森林与二叉树的转换3.树和森林的遍历(四)树与二叉树的应用1.二叉排序树2.平衡二叉树3.哈夫曼(Huffman)树和哈夫曼编码四、图(一)图的基本概念(二)图的存储及基本操作1.邻接矩阵法2.邻接表法3.邻接多重表、十字链表(三)图的遍历1.深度优先搜索2.广度优先搜索(四)图的基本应用1.最小(代价)生成树2.最短路径3.拓扑排序4.关键路径五、查找(一)查找的基本概念(二)顺序查找法(三)分块查找法(四)折半查找法(五)B树及其基本操作、B+树的基本概念(六)散列(Hash)表(七)字符串模式匹配(八)查找算法的分析及应用六、排序(一)排序的基本概念(二)插入排序1.直接插入排序2.折半插入排序(三)起泡排序(BubbleSort)(四)简单选择排序(五)希尔排序(ShellSort)(六)快速排序(七)堆排序(八)二路归并排序(MergeSort)(九)基数排序(十)外部排序(十一)各种排序算法的比较(十二)排序算法的应用计算机组成原理【考查目标】1.理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。
2015年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解一、单项选择题：1～40小题，每小题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．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，右子树为空。
2018年计算机学科专业基础综合试题参考答案一、单项选择题1．B2．C3．A4．A5．A6．C7．D8．B9．C10．D11．A12．D13．C14．A15．A16．B17．C18．B19．A20．D21．B22．C23．C24．D25．B26．A27．C28．D29．D30．A31．D32．C33．B 34．C 35．D 36．D 37．D 38．C 39．B 40．D二、综合应用题41．解析：1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。
分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。
由于A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n时返回n+1。
当数组A中出现了小于等于0或者大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。
经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令B[A[i]-1]=1；否则不做操作。
对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1~n之间。
若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。
int findMissMin(int A[],int n){int i,*B; //标记数组B=(int *)malloc(sizeof(int)*n); //分配空间memset(B,0,sizeof(int)*n); //赋初值为0for(i=0;i<n;i++)if(A[i]>0&&A[i]<=n) //若A[i]的值介于1~n，则标记数组BB[A[i]-1]=1;for(i=0;i<n;i++) //扫描数组B，找到目标值if (B[i]==0) break;return i+1; //返回结果}3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。
