考研计算机学科专业基础综合-24

重庆理工大学硕士研究生试题专用纸重庆理工大学2019年攻读硕士学位研究生入学考试试题学院名称：计算机科学与工程学科、专业名称：计算机科学与技术考试科目(代码)：计算机学科基础综合(816)A (试题共 6 页)注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。

2.试题附在考卷内交回。

一、选择题(50分，25小题，每小题2分)1.数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的( )和运算的学科。

A.结构B.关系C.数值D.算法2.线性表是一个可在( )位置对数据元素进行插入、删除操作的序列容器。

A.仅表头B.仅表尾C.任意D.都是3.将长度为n的单链表连接在长度为m的仅带头指针的单链表后面，其算法的时间复杂度为( )。

A.O(1)B.O(n)C.O(m)D.O(m + n)4.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是( )。

A.front== rearB.front!= rearC.front==rear+ 1D.front==(rear+1)% maxSize5.下面关于串的叙述中，不正确的是( )。

A.串是字符的有限序列B.空串是空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6.对特殊矩阵采用压缩存储的目的主要是为了( )。

A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中的多于元素D.减少不必要的存储空间7.对一棵满二叉树，有A个叶结点、B个结点、深度为C，则( )。

A.B=C+1B.C+A=2BC.A=C-1D.B=-18.任意一棵二叉树，其叶结点在先根遍历、中根遍历和后根遍历序列中的相对次序( )。

A.保持不变B.先根遍历和中根遍历有变化，后根遍历无变化C.先根遍历和后根遍历有编号，中根遍历无变化第12页。

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

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

1．若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算 b op a；（4）将运算结果压人S1中。

假定S1中的操作数依次是5, 8, 3, 2（2在栈顶），S2中的运算符依次是*, - , +（+在栈顶）。

调用3次F()后，S1栈顶保存的值是。

A. -15B. 15C. -20D. 202. 现有队列Q与栈S，初始时Q中的元素依次是1, 2, 3, 4, 5, 6（1在队头），S为空。

若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素人栈；③出栈并输出出栈元素，则不能得到的输出序列是。

A. 1, 2, 5, 6, 4, 3B. 2, 3, 4, 5, 6, 1C. 3, 4, 5, 6, 1, 2D. 6, 5, 4, 3, 2, 1）按行优先存人C3. 设有一个12×12的对称矩阵M，将其上三角部分的元素m i, j（1≤i≤j≤12语言的一维数组N中，元素m6, 6在N中的下标是。

A. 50B. 51C. 55D. 664. 设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。

若T有k个叶结点，则T的结点总数是。

A. 2k-1B. 2kC. k2D. 2k-15. 已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是。

A. 00, 1011, 01, 1010, 11, 100B. 00, 100, 110, 000, 0010, 01C. 10, 1011, 11, 0011, 00, 010D. 0011, 10, 11, 0010, 01, 0006. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。

2024年考研408大纲
2024年考研408大纲主要包括以下几个部分：
1. 考试性质：计算机学科专业基础综合考试是为全国硕士研究生招生考试而设置的具有选拔性质的全国统一考试科目。

2. 考试要求：
熟练掌握数据结构的基本概念和术语；
具备设计和实现数据结构的能力；
掌握计算机组成原理的基本概念和原理；
熟悉操作系统的基本概念和工作原理；
理解计算机网络的基本概念和工作原理。

3. 考试形式和试卷结构：
考试形式：闭卷、笔试；
考试时间：180分钟；
试卷满分：150分；
题型比例：选择题、填空题、分析题等。

总之，考研408大纲是为了确保考试的公正性和统一性而制定的，它明确了考试的范围、要求和形式，是考生备考的重要依据。

考生应该仔细阅读大纲，了解考试内容和要求，有针对性地进行复习。

计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：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.C. 6D.9.设主串T=“abaabaabcabaabc”，模式串S=“abaab c”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

考研计算机学科专业基础综合-47(总分150,考试时间90分钟)一、单项选择题1. 设有一个递归算法如下int X(int n){if(n＜=3) return 1;else return X(n-2)+X(n-4)+1;试问计算X(X(5))时需要调用______次x函数。

A. 2B. 3C. 4D. 52. 设有一个10阶对称矩阵A，采用压缩存储方式，以行序为主存储，a1，1为第一个元素，其存储地址为1，每个元素占一个地址空间，则a8，5的地址可能是______。

A. 13B. 33C. 18D. 403. 若一棵深度为6的完全二叉树的第6层有3个叶子结点，则该二叉树共有______个叶子结点。

A. 17B. 18C. 19D. 204. 在一棵非空二叉树的中序遍历序列中，根结点的右边______。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的部分结点D. 只有左子树上的所有结点5. 如图所示为一棵平衡二叉树(字母不是关键字)，在结点D的右子树上插入结点F后，会导致该平衡二叉树失去平衡，则调整后的平衡二叉树中平衡因子的绝对值为1的分支结点数为______。

A. 0B. 1C. 2D. 36. 下列说法中，正确的是______。

A. 对于有n个结点的二叉树，其高度为[log2n]B. 完全二叉树中，若一个结点没有左孩子，则它必是叶结点C. 高度为h(h＞0)的完全二叉树对应的森林所含的树的个数一定是hD. 一棵树中的叶子数一定等于其对应的二叉树的叶子数7. 以下关于图的叙述中，正确的是______。

A．强连通有向图的任何顶点到其他所有顶点都有弧B．图与树的区别在于图的边数大于或等于顶点数C．无向图的连通分量指无向图中的极大连通子图D．假设有图G={V，{E}}，顶点集，则V"和{E"}构成G的子图8. 如图所示，在下面的5个序列中，符合深度优先遍历的序列有多少个______。

考研计算机学科专业基础综合模拟试题及答案解析（8）(1/40)单项选择题第1题下面关于卫星通信的说法，错误的是______。

A.卫星通信的距离长，覆盖的范围广B.使用卫星通信易于实现广播通信和多址通信C.卫星通信的好处在于不受气候的影响，误码率很低D.通信费用高、延时较大是卫星通信的不足之处下一题(2/40)单项选择题第2题某网络在物理层规定，信号的电平用+10V～+15V表示二进制0，用-10V～-15V表示二进制1，电线长度限于15m以内，这体现了物理层接口的______。

A.机械特性B.功能特性C.电气特性D.规程特性上一题下一题(3/40)单项选择题第3题当描述一个物理层接口引脚处于高电平时的含义时，该描述属于______。

A.机械特性B.电气特性C.功能特性D.规程特性上一题下一题(4/40)单项选择题第4题在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是______。

A.机械特性B.功能特性C.过程特性D.电气特性上一题下一题(5/40)单项选择题第5题下列关于物理层设备的叙述中错误的是______。

A.中继器仅作用于信号的电气部分B.利用中继器来扩大网络传输距离的原理是它将衰减的信号进行了放大C.集线器实质上相当于一个多端口的中继器D.物理层设备连接起来的几个网段仍然是一个局域网，且不能连接具有不同数据链路层协议的网段上一题下一题(6/40)单项选择题转发器的作用是______。

A.放大信号B.转发帧C.存储帧D.寻址上一题下一题(7/40)单项选择题第7题两个网段在物理层进行互联时要求______。

A.数据传输率和数据链路层协议都可以不相同B.数据传输率和数据链路层协议都要相同C.数据传输率要相同，但数据链路层协议可以不相同D.数据传输率可以不相同，但数据链路层协议要相同上一题下一题(8/40)单项选择题第8题为了使数字信号传输的更远，可采用的设备是______。

A.中继器B.放大器C.网桥D.路由器上一题下一题(9/40)单项选择题第9题以太网遵循IEEE 802.3标准，用粗缆组网时每段不能大于500m，超过500m长度时就要分段，段间相连是利用______。

沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编附答案最新资料，WORD格式，可编辑修改！目录第一部分沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编....................................................................2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题........................................................................2013年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题........................................................................ 第二部分全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解........2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题 .................2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解 ...........2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题 .................2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解 ...........2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题 .................2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解 ...........2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题 .................2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解 ...........说明：沈阳师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为867计算机学科专业基础综合（数据结构、操作系统），2015年科目代码改为862。

2020年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题——参考答案一、单项选择题1． C 2． D 3． A 4． C 5． B 6． B 7． A8． B9． C 10． B 11． A 12． B 13．A14． D 15． D 16． A17． B 18． A 19． C 20． C 21．B22． C 23．B24．A25． D 26． D 27． B 28． D 29．B30． D 31． B 32． C33． C 34． B 35． C 36． D 37．A38． D 39．C40． D1.【参考答案】C【解析】按上三角存储，m7,2对应的是m2,7，在它之前有：第1列：1第2列：2……第6列：6第7列：1前面一共1+2+3+4+5+6+1个元素，共22个元素，数组下标从0开始，故下标为m2,7的数组下标为22。

2.【参考答案】D【解析】第一个Pop栈中状态为a,b，Pop出栈元素为b，第二个Pop栈中状态为a,c，Pop出栈元素为c，第三个Pop栈中状态为a,d,e，Pop出栈元素为e，把序列连起来就是b,c,e。

3.【参考答案】A【解析】由于题目明确说明只存储结点数据信息，所以采用顺序存储时要用数组的下标保存结点的父子关系，所以对于这棵二叉树存储的结果就是存储了一棵五层的满二叉树，五层的满二叉树结点个数为1+2+4+8+16=31，所以至少需要31个存储单元。

4.【参考答案】C【解析】森林的先根遍历对应它自己转化后二叉树的先序遍历，森林的后根遍历对应它自己转化后二叉树的中序遍历，所以先根和后根可以唯一确定森林转化后的二叉树，如下：后序遍历为：b,f,e,d,c,a5.【参考答案】B【解析】在4，5，1，2，3中由于1先插入，所以1会成为4的左孩子，2会成为1的右孩子，不能生成图中二叉树，故选B。

6.【参考答案】B【解析】题目已经限定有向无环图图，假设从a结点出发开始深度遍历，那么这一次递归到最大深度，必然终止于某结点(记为h结点)，h结点必然没有出度。

考研计算机学科专业基础综合-48(总分151,考试时间90分钟)一、单项选择题1. 已知一个栈的进栈序列是1、2、3、…、n，其输出序列为p1、p2、p3、…、pn，若p1=3，则p2为______。

A. 2或4、5、…、n都有可能B. 可能是1C. 一定是2D. 只可能是2或42. 利用栈求表达式的值时，设立运算数栈OPEN。

假设OPEN只有两个存储单元，则在下列表达式中，不会发生溢出的是______。

A. A-B*(C-D)B. (A-B)*C-DC. (A-B*C)-DD. (A-B)*(C-D)3. 已知A[1...N]是一棵顺序存储的完全二叉树，9号结点和11号结点共同的祖先是______。

A. 4B. 6C. 2D. 84. 在常用的描述二叉排序树的存储结构中，关键字值最大的结点是______。

A. 左指针一定为空B. 右指针一定为空C. 左、右指针均为空D. 左、右指针均不为空5. 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是______。

A. (100，80，90，60，120，110，130)B. (100，120，110，130，80，60，90)C. (100，60，80，90，120，110，130)D. (100，80，60，90，120，130，110)6. 设无向图G=(V，E)和G"=(V"，E")，如果G"是G的生成树，则下面说法错误的是______。

A. G"是G的子图B. G"是G的连通分量C. G"是G的极小连通子图且V=V"，D. G"是G的一个无环子图7. 若G是一个具有36条边的非连通无向简单图，则图G的结点数至少是______。

A. 11B. 10C. 9D. 88. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是______。

重庆理工大学计算机科学与工程学院813计算机学科专业基础综合历年考研真题汇编最新资料，WORD格式，可编辑修改！目录说明：重庆理工大学计算机学科专业基础综合的科目代码每年都不同，2015年改为813。

说明：重庆理工大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为810计算机学科专业基础综合。

为帮助考生全面复习，特提供2009～2012年408计算机学科专业基础综合真题及详解。

第一部分重庆理工大学计算机科学与工程学院810计算机学科专业基础综合历年考研真题汇编2014年重庆理工大学计算机科学与工程学院810计算机学科专业基础综合考研真题学院名称：计算机科学与工程学院学科、专业名称：计算机科学与技术考试科目（代码）：计算机学科专业基础综合（810）A卷一、单选题（每题2分，共50分）1．顺序表的第1个元素存储地址是100，每个元素占用2个存储单元，则该顺序表的第4个元素地址是（）A．110B．108C．112D．1062．一个具有n个顶点的无向完全图的边数为（）A．n（n+1）/2B．n（n-1）/2C．n（n-1）D．n（n+1）3．深度为2（根结点的层次为1）的满二叉树的叶子节点个数为（）A．2B．4C．6D．84．双向链表中每个结点的指针域的个数为（）A．0B．1C．2D．35．完全二叉树，按层次序列对每个结点编号（根结点编号为1），则编号为7的结点的双亲编号为（）A．1B．2C．3D．46．下列属于线性结构的是（）A．线性表B．树C．查找D．图7．在一个无向图中，所有顶点的度数之和等于所有边数的（）A．1倍B．2倍C．4倍D．8倍8．栈的特点是（）A．先进后出B．先进先出C．后进后出D．前出前进9．深度为3（根的层次号为1）的满二叉树结点个数为（）A．4B．6C．7D．810．不带头结点的单链表head为空的判定条件是（）A．head==NULLB．head->next==NULLC．head!=NULLD．head->next!=NULL11．有一个有序表为{2，3，8，10，30}，当折半查找到8时，需要的比较次数为（）A．1B．2C．3D．412．栈的插入与删除操作在（）A．栈顶B．栈底C．队头D．队尾13．一个栈的入栈顺序是a,b,c，则该栈的不可能的输出序列是（）A．abcB．cbaC．acbD．cab14．设先序遍历某二叉树的序列为ABC，中序遍历该二叉树的序列为BAC，则后序遍历该二叉树的序列为（）A．ABCB．CBAC．ACBD．BCA15．设一组初始记录关键字序列（5，2，6，3），以第一个记录关键字5为基准进行一趟快速排序的结果为（）A．2，3，5，6B．5，2，3，6C．3，2，5，6D．2，3，6，516．在计算机中配置操作系统的主要目的是（）A．增强计算机的功能B．提高系统资源的利用率C．提高系统的运行速度D．合理组织系统的工作流程17．从静态角度讲，进程由程序段、数据段和（）组成，它是进程存在的唯一标志。