2017年重庆理工大学计算机学科基础综合考研真题A卷

重庆理工大学硕士研究生试题专用纸重庆理工大学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年重庆理工大学计算机学科基础综合考研真题A卷一、单选题（每小题2分，共40分）1．算法分析的目的是（）。

A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 D．分析算法的易懂性和稳定性2．设某算法完成对n个元素进行处理所需的时间是：T(n) = 200log2n + 1000n(log2n + 100) + 100000，则该算法的时间复杂度是（）。

A．O(1) B．O(n) C．O(nlog2n) D．O(nlog2n+log2n)3．若某链表最常用的操作是在最后一个结点之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。

A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表4．在中缀表达式转化为后缀表达式与后缀表达式求值算法中，都需要用到哪种特殊的数据结构（）。

A．栈 B．队列 C．二叉树 D．堆5．一个队列的入队序列是1，2，3，4，则队列的出队序列只能是（）。

A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，16．将含有100个结点的完全二叉树从根结点开始编号，根为0号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为（）。

A．42 B．40 C．21 D．207．如果在某二叉树的前序序列、中序序列和后序序列中，结点b都在结点a的后面（即形如…a…b…），则最有可能的情况是（）。

A．a和b是兄弟 B．a是b的双亲C．a是b的左孩子 D．a是b的右孩子8．某二叉树的后序遍历序列是dabec，中序遍历序列是debac，其前序遍历序列是（）。

A．acbed B．decab C．deabc D．cedba9．下述编码中，哪一个不是前缀码（）。

A．(0,10,110,111) B．(11,10,001,101,000)C．(00,010,011,1) D．(1,01,000,001)10．一个有 n 个顶点的无向图最多有（）条边。

重庆理工大学 2011 年攻读硕士学位研究生入学考试试题学院名称：计算机科学与工程学院学科、专业名称：085211计算机技术（专业学位）（试题共4页）一．单选题（每小题 2 分，共 80 分）1. 世界上第一台计算机于1946年诞生在________。

A.美国B.日本C.中国D.英国2．________是计算机最早的应用领域。

A.信息管理B.数据处理C.科学计算D.计算机网络3．以下软件中，________不是操作系统软件。

A．WINDOWS XP B．UNIX C．MICROSOFT OFFICE D.DOS4．计算机问世至今已经历四代，而划分成四代的主要依据则是计算机的________。

A．规模B．功能 C.性能D．构成元件5．计算机的内存容量也可能不同，而计算容量的基本单位是________。

A．字B．页C．字节D．位6．能够将高级语言源程序加工为目标程序的系统软件是________。

A．机器程序B．汇编程序C．编译程序D．编辑程序7．微处理机芯片的位数即指________。

A．速度B．字长C．主频D．周期8．十进制数124转换为二进制数为________。

A．1111100 B．111100 C．111110 D．1111110 9．十六进制数A0.8转换成二进制数为________。

A．1010000.1 B．10100000.01 C．10100000.1 D．1010000.01 10．数值数据在计算机内表示时，其正负号用________表示。

A．+B．-C．0或1D．0111．计算机中，一个浮点数由两部分组成，它们是________。

A．阶码和尾数B．基数和尾数C．阶码和基数D．整数和小数12．ASCII码是一种对________进行编码的计算机代码。

A．汉字B．字符C．图像D．声音13．利用大规模集成电路技术，将运算器和控制器集成在一块芯片上，该芯片称为________。

A. 单片机B. 单板机C.中央处理器D.输入/输出接口14．在Windows中，如果想同时改变窗口的高度和宽度，可以通过拖放________实现。

2018年重庆理工大学计算机基础综合考研真题A卷2018年重庆理工大学计算机基础综合考研真题A卷一、单项选择题（每小题3分，总共72分）1、下列叙述中，错误的是。

A．计算机系统由硬件系统和软件系统组成B．计算机软件由各类应用软件组成C．CPU主要由运算器和控制器组成D．计算机主要由CPU和内存储器组成2、以下语言本身不能作为网页开发语言的是。

A．C++ B.ASPC.JSPD.HTML3、数码相机里的照片可以利用计算机软件进行处理，计算机的这种应用属于。

A．图像处理 B.实时控制C．嵌入式系统 D.辅助设计4、编译程序将高级语言程序翻译成与之等价的机器语言程序，该机器语言程序称为。

A．工作程序 B.机器程序C．临时程序 D.目标程序5、声音与视频信息在计算机内的表现形式是。

A.二进制数字B.调制C．模拟 D.模拟或数字6、计算机有多种技术指标，其中主频是指。

A．内存的时钟频率 B.CPU内核工作的时钟频率C.系统时钟频率，也叫外频D.总线频率7、除硬盘容量大小外，下列也属于硬盘技术指标的是。

A.转速B.平均访问时间C.传输速率D.以上全部8、以下名称是手机中的常用软件，属于系统软件的是。

A.手机QQB.androidC.skypeD.微信9、下面不能作为结构化方法软件需求分析工具的是。

A.系统结构图B.数据字典（DD）C.数据流程图（DFD图）D.判定表10、若实体A和B是一对多的联系，实体B和C是一对一的联系，则实体A和C的联系是。

A.一对一B.一对多C．多对一 D.多对多11、下面不属于软件测试实施步骤的是。

A.集成测试B.回归测试C.确认测试D.单元测试12、下面属于白盒测试方法的是。

A．等价类划分法 B.逻辑覆盖C．边界值分析法 D.错误推测法13、下面对象概念描述正确的是。

A．对象间的通信靠消息传递B．对象是名字和方法的封装体C．任何对象必须有继承性D．对象的多态性是指一个对象有多个操作14、下列有关数据库的描述，正确的是。

2016考研计算机学科专业基础综合真题及答案一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。

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

)1. 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x=2;while(xx=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)解答：A。

程序中，执行频率最高的语句为“x=2*x”。

设该语句执行了t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。

2. 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3B.4C.5D.6解答：B。

出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。

3. 已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是A.0,0B.0，n-1C.n-1,0D.n-1，n-1解答：B。

插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。

4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A.257B.258C.384D.385解答：C。

叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1(总结点数为偶数)，故而即2n=768。

5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1解答：C。

由前序和后序遍历序列可知3为根结点，故(1,2)为左子树，(4)为右子树，C不可能。

6.解析：哈夫曼编码是前缀编码，各个编码的前缀各不相同，因此直接拿编码序列与哈夫曼编码一一比对即可。

序列可分割为0100011 001 001 011 11 0101, 译码结果是a fee f g d, 选项D正确。

7.解析：无向图边数的两倍等于各顶点度数的总和。

由于其他顶点的度均小于3,可以设它们的度都为2,设它们的数量是X,可列出方程4x3+ 3x4 + 2x = 16x2, 解得x=3。

4+ 3 + 3 = 11, B 正确。

8.解析：折半查找判定树实际上是一棵二叉排序树，它的中序序列是一个有序序列。

可以在树结点上依次填上相应的元素，符合折半查找规则的树即是所求。

B选项4、5相加除2向上取整，7、8相加除2向下取整，矛盾。

C选项，3、4相加除2向上取整，6、7相加除2向下取整，矛盾。

D选项，I、10相加除2向下取整，6、7相加除2向上取整，矛盾。

A符合折半查找规则，因此正确。

A {6) Bc 10D2II9.解析：B+树是应文件系统所需而产生的B-树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。

编译器中的词法分析使用有穷自动机和语法树。

网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。

系统一般使用空闲空间链表管理磁盘空闲块。

所以B正确。

10.解析：归并排序代码比选择插入排序更复杂，前者空间复杂度是O(n),后者是0(1)。

但是前者时间复杂度是O(nlogn),后者是O(n2)。

所以B正确。

11.解析：插入排序、选择排序、起泡排序原本时间复杂度是O(n2),更换为链式存储后的时间复杂度还是O(n2)。

希尔排序和堆排序都利用了顺序存储的随机访问特性，而链式存储不支持这种性质，所以时间复杂度会增加，因此选D。

12.解析：运行时间＝指令数xCPI/主频。

Ml的时间＝指令数x2/1.5,M2的时间＝指令数xl/1.2,两者之比为(2/1.5):(1/1.2)= 1.6。

重庆理工大学计算机科学与工程学院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．从静态角度讲，进程由程序段、数据段和（）组成，它是进程存在的唯一标志。

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

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

一．单选题(每题2分，共50分)
1．数据元素之间的存储结构，除了链式存储结构，另外一种存储结构是（）
A．线性存储结构 B．树形存储结构 C．顺序存储结构
D．图形存储结构
2．图形结构之间是（　）
A．一对多关系 B．一对一关系 C．多对多关系 D．一对二关系3．算法有5个特性，下列哪项不是算法的特性（）
A．有穷性 B．输入 C．可行性 D．队列
4．带头结点的单链表H为空的条件是（）
A．H==NULL B．H->next==NULL C．H!=NULL D．H-
>next!=NULL
5．完全二叉树，按层次序列对每个结点编号（根结点编号为1），则编号为8的结点的双亲编号为（）
A．3 B．4 C．5 D．6
6．下列属于线性结构的是（）
A．栈 B．树 C．查找 D．图
7．顺序表的第1个元素存储地址是700，每个元素占用3个存储单元，则该顺序表的第4个元素地址是（）
A．703 B．706 C．709 D．712
8．8个顶点连通图的最小生成树中边的数目是（）
A．4 B．5 C．6 D．7
9．深度为5（根的层次号为1）的满二叉树结点个数为（）
A．15 B．16 C．31 D．32
第1页。

2021年重庆理工大学计算机学科专业根底综合考研真题A卷一、选择题1.深度为2〔根结点的层次号为1〕的满二叉树的叶子结点个数为〔〕2. 栈的特点是〔〕3.双向链表的指针域的个数为〔〕4.完全二叉树，按层次序列编号〔根结点编号为1〕，那么编号为2的结点的左孩子的编号为〔〕5.具有 m个顶点的无向完全图的边的数目为〔〕A.m(m+1)/2B.m(m-1)/2C.m(m-1)D.m(m+1)6.顺序表的第1个元素存储地址是100，每个元素占用2个存储单元，那么该顺序表的第3个元素地址是〔〕7.数据的存储构造可分为链式存储构造和〔〕A.顺序存储构造B.哈希存储构造8.数据元素之间有四种根本逻辑构造，以下描述中是逻辑构造的是〔〕9.以下不属于线性构造的是〔〕10.满二叉树，按层次序列编号〔根结点编号为1〕，那么编号为3的结点的双亲编号为〔〕11. 第二代计算机是以〔〕为主要器件的。

A．电子管 B.晶体管 C. 二极管 D. 触发器12. 动态RAM根本电路单元是靠〔〕来存放信息的。

A．电阻 B.电容 C. 二极管 D. 晶体管13.主机、外设串行工作的方式是〔〕。

A．程序查询 B. 程序中断 C. DMA D. I/O处理机14. 以下有关运算器的表达，正确的选项是〔〕。

A．只做加法运算 B.只做算术运算C. 既做算术运算又做逻辑运算D. 只做逻辑运算15. 指令周期是指〔〕。

A．CPU从主存取出一条指令的时间B. CPU从主存取出一条指令加上执行指令的时间C. 节拍周期时间D. 时钟周期时间16. 某存储器芯片规格为8K×1位，那么它的地址线和数据线共有〔〕根。

A．15 B. 14 C. 13 D. 1217. Cache是为解决CPU与〔〕之间速度不匹配而采用的一项技术。

A．硬盘 B.光盘 C.总线 D. 内存18. 计算机系统I/O接口是〔〕之间的交接界面。

A.CPU与存储器B.主机与外设19.DMA用于高速数据块的传送，直接在〔〕和外设之间进展数据传送。