南开大学812计算机综合基础2019年考研专业课真题试卷

文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持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 ． main()->S(0)->S(1)D ． S(1)->S(0)->main()2． 先序序列为 a,b,c,d 的不同二叉树的个数是 A ． 13B ．14C ．15D ．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是序序列。

下列关于该平衡二叉树的叙述中，正确的是5. 设有向图 G=(V,E)，顶点集 V={V o ,V i ,V 2,V 3}，边集 E={<v 0,v i >,<v 0,v 2>,<v o ,v 3>,<v i ,v 3>}, 若从顶点 V 0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A. 2 B . 3C . 4D . 56.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(kruskal )算法第二次选 中但不是普里姆( Prim )算法(从 V 4开始)第 2 次选中的边是A. (V1,V3)B . (V1,V4)C . (V2,V3)D . (V3,V4)A ． 24， 10， 5 和 24，10，7 C ．24，10，10 和 24， 14，114．现在有一颗无重复关键字的平衡二叉树B ．24，10，5 和 24， 12，7 D ．24，10，5 和 24，14，6( AVL 树) ,对其进行中序遍历可得到一个降A .根节点的度一定为 2 C .最后插入的元素一定是叶节点B .树中最小元素一定是叶节点 D .树中最大元素一定是无左子树文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持7. 下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，450&已知字符串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. 1B. 2C. 3D. 411.希尔排序的组内排序采用的是()A .直接插入排序B .折半插入排序C .快速排序D .归并排序12.计算机硬件能够直接执行的是()I.机器语言程序n.汇编语言程序川.硬件描述语言程序A. 仅I B .仅I n C .仅I 川D. In出13.由 3 个“ 1 ”和5 个“ 0”组成的8位二进制补码, 能表示的最小整数是()A.-126 B . -125C. -32D. -314.下列有关浮点数加减运算的叙述中, 正确的是()I.对阶操作不会引起阶码上溢或下溢n.右规和尾数舍入都可能引起阶码上溢川.左规时可能引起阶码下溢I V 尾数溢出时结果不一定溢出A.仅n 川 B .仅inv C .仅I川V D. In川V15.假定主存地址为32 位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4 个字，每字32位，采用回写( Write Back )方式，则能存放4K 字数据的Cache 的总容量的位数至少是()A. 146kB. 147KC. 148KD. 158K16.假定编译器将赋值语句“x=x+3;转换为指令” add xaddt, 3,其'中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持且Cache使用直写(Write Through )方式，则完成该指令功能需要访问主存的次数至少是()文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持A ． 0B ．1C ．2D ．317．下列存储器中，在工作期间需要周期性刷新的是() A ． SRAMB ．SDRAMC ．ROMD ．FLASH18．某计算机使用 4 体交叉存储器，假定在存储器总线上出现的主存地址(十进制)序 列为 8005， 8006，8007， 8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲 突的地址对是()B ．8002、8007C ．8001、 8008D ．8000、8004 19．下列有关总线定时的叙述中，错误的是()A •异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制20. 若磁盘转速为 7200转/分，平均寻道时间为 8ms,每个磁道包含1000个扇区，则访 问一个扇区的平均存取时间大约是 ( )A. 8.1ms B . 12.2msC . 16.3msD . 20.5ms21. 在采用中断I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的I/O 端口之 间交换的信息不可能是 ( )A .打印字符B .主存地址C .设备状态D .控制命令22. 内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

2019年全国硕士研究生统一入学考试计算机学科专业基础综合模拟试题3(总分：150.00，做题时间：150分钟)一、单项选择题(总题数：40，分数：80.00)1.在链式存储结构中，体现数据之间关系的是（）。

A.数据在内存的相对位置B.指示数据元素的指针√C.数据的存储地址D.指针链式存储结构是线性表数据结构在计算机中的体现，而线性表中的数据关系主要是数据元素的前后次序关系，这个关系是通过指向数据元素的指针实现的。

2.对于线性链表，在 p 所指的结点后插入由 q 指向的新结点的语句序列是（）。

A.p->next＝q； q->next＝p->next；B.q＝p->next； p->next＝q；C.q->next＝p->next； p->next＝q；√D.p＝p->next； q->next＝p；在单链表中进行插入运算时需特别注意指针修改顺序。

选项 A 的顺序是错误的。

3.向一个栈顶指针为h 的带头结点链栈中插入指针s 所指的结点时，应执行的语句序列是（）。

A.h->next＝s；B.s->next＝h；C.s->next＝h； h＝h->next；D.s->next＝h->next； h->next＝s；√相当于在普通链表的头结点后插入一个结点。

需要注意的是带头结点的链栈与不带头结点的链栈的区别。

4.由 3 个结点可以构造出（）种不同形态的二叉树。

A.3B.4C.5 √D.6由 3 个结点可以构造出有 5 种不同形态的二叉树，如图 1 所示。

图1 3个结点构造出的二叉树5.二叉树的先序遍历和中序遍历如下：先序遍历： EFHIGJK；中序遍历： HFIEJKG。

该二叉树根的右子树的根是（）。

A.EB.FC.G √D.H先序遍历是“根-左子树-右子树”，中序遍历是“左子树-根-右子树”。

由先序遍历的节点序列可知E为树根节点，再结合中序遍历节点序列可知右子树的组成节点(E后面的节点)为JKG，而这3个节点在先序遍历中G为第1个节点，即右子树根节点。

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

南开大学计算机科学与技术考研真题资料（含考研参考书信息） 想要在备考南开大学计算机科学与技术考研专业课的时候能够命中关键点，那么这就意味着需要先弄清楚命题人的出题思路。

同学们在备考的过程中，只看参考教材是远远不够的，考生个人无法从厚厚的基本参考书目中准确的找到命题老师侧重考察的章节知识点。

一套编写合理、内容齐全的考研资料可以帮助大家缩短专业课复习时间，还能准备找到重难点范围。

下面小编就为大家介绍一下南开大学计算机科学与技术专业考研真题资料和参考书经验信息。

《南开大学计算机综合基础考研红宝书》是由天津考研网组织多名一线大学老师及过去几年在南开大学计算机科学与技术专业研究生初试中专业课取得高分的考生共同编写及整理的一套复习材料。

本套材料对考研指定教材中的考点内容进行深入提炼和总结，同时辅以科学合理的复习规划，使得同学们只要使用这套材料便可以掌握南开大学计算机综合基础考试科目几乎全部的考点、帮助同学用最短的时间实现全面而有深度的复习。

需要特别为同学们介绍一下，南开大学计算机与控制工程学院计算机科学与技术专业2005年前各科分开考，2005年开始合并为计算机软硬件基础，2008年改为计算机综合基础，2009年全国统考至2012年且科目名称为计算机学科专业基础综合，自2013年开始又转为学校自主命题，科目名称改为计算机综合基础。

《南开大学计算机综合基础考研红宝书》包含南开大学809计算机综合基础2005-2008、2013年考研真题及答案解析，数据结构与算法97、98、00—04年考研试题、计算机原理97—03年考研真题，以前各科单考，仍具有重要参考价值。

多年的试题就是一个小题库，所以历年试题一定要仔细研究，通过多年试卷可总结出出题重点及思路在备考时，经过一段时间的专业课复习以后，考生可以研究一下历年的考研真题，对真题中的关键考点要着重分析。

研究专业课的真题，重点是要训练自己解答分析题的能力，做完以后，考生一定要将自己的答案和参考答案进行比较，得出之间的差别，然后对参考答案的答题角度进行分析，最终总结出自己的解答方法。

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

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

1.设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0 ；while ( n>= ( x+l ) * ( x+l ))；x=x+l1/22)O( n)B. O( n D. C. A. O( log n)O( n)BT 若将一棵树 T 转化为对应的二又树，则下列对 BT 的遍历中，其遍历序列与T 的后根遍历序列相同的2.是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历115 个结点，则 n 的值是对 n 个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有3.A. 56B. 57C. 58D. 60中，删除某结点T 形成之后形成平衡二又树v T树 ) T插入，再将 w 在任意一棵非空平衡二又树( AVL4.221与 T 的叙述中，正确的是 T T 。

下列关于平衡二又树331 I. 若 v 是 T 的叶结点，则 T 与 T 可能不相同311的叶结点，则T 与 T 一定不相同 T不是Ⅱ .若 v 311T 与 T一定相31的叶结点，则同 T若 v 不是Ⅲ .1D. 仅I、ⅡI、ⅢA. 仅I B. 仅II C. 仅网表示一项包含个活动的工程。

活动下图所示的 AOE 8 d5.的最早开始时间和最迟开始时间分别是A.3和7B.12和12C. 12和14D.15和15用有向无环图描述表达式 ( x+y ) *(( x+y ) /x) ，需要的顶点个数6.至少是 A.5B.6C.8D.97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是算法的稳定性Ⅲ .数据的规模Ⅱ .数据的存储方式I. 数据的初始状态V. 、Ⅱ、Ⅲ、ⅣIIV D. 仅Ⅲ仅 I、Ⅱ仅Ⅱ、Ⅲ、)，采用线性探查H( key) =key%7 现有长度为 11 8.且初始为空的散列表HT ，散列函数是线性探测再散列( 查找失败的平均查找 HT 98，20 依次插入到 HT 后，87法解决冲突将关键字序列，40， 30，6， 11，22，长度是6C. A. 4B. 5.256.29D.算法进行模式匹配，到匹配成功时为止，，模”式串 S=“ abaabc9.”，采用 KMP 设主串 T=“ abaabaabcabaabc在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一不可能是快速排序”。

南开大学2019年考研812计算机综合基础考试大纲
812计算机综合基础考试大纲
081200计算机科学与技术专业
一、考试目的
本考试是全日制计算机科学与技术学术学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。

各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的性质与范围
本考试是测试考生计算机科学基础知识的水平考试。

考试范围包括本大纲规定的C++语言程序设计、数据结构和计算机组成原理基础知识。

三、考试基本要求
1. 具备扎实的C++语言程序设计基本功。

2. 具备设计数据结构和算法求解问题的基本能力。

3. 具备设计和计算硬件系统中理论和实际问题的基本能力。

四、考试形式
本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生设计数据结构和算法并编程实现来求解问题的能力，以及利用计算机系统层次结构的基本概念及其硬件组成知识来设计和计算硬件系统中理论和实际问题的能力。

五、考试内容
本考试包括三个部分：C++程序设计、数据结构、计算机组成原理。

总分150分。

I. C++程序设计。

《大学计算机基础》1、计算机网络最本质的功能是实现资源共享和数据通信物联网是利用局部网络或互联网等通信技术把传感器、控制器、机器、人员和物品等通过新的方式联一起，形成人与物、物与物相联,实现信息化、远程管理控制和智能化的网络。

2、简单说明原码威码和码的计算公式及它们之间的关系。

3、内存储器分为哪几种?有什么区别?正确答案:内存从读写功能上分，可分为随机存储器(RAM)，又称读写存储器;只读存储器(ROM)。

(1)在制造ROM的时候，信息(数据或程序)就被存入并永久保存。

这些信息只能读出,一般不能写入，即使机器停电，这些数据也不会丢失。

(2)随机存储器(RAM)表示既可以从中读取数据，也可以写入数据。

当机器电源关闭时，存于其中的数据就会丢失。

(3)Cache(高速缓冲存储器)位于CPU 与内存之间，能够提高读写速度。

从基本结构上来讲，电脑可以分为五大部分:运算器、控制器、存储器、输入设备和输出设备。

关系数据库中，两表之间相互关联是依靠主表（父表)中的主键和子表的外键建立的。

一、客观部分：（单项选择、多项选择、不定项选择、判断）（一）、选择部分1. 世界公认的第一台电子计算机是（ C ）。

A.Mark-IB.EDVACC.ENIACD.MARK-II2.自动化生产过程属于计算机的哪种应用（ B ）。

A.数据处理B.过程控制C.辅助系统D.科学计算3.下面哪位科学家首次系统定义了计算思维（ B ）。

A.姚期智B.周以真C.潘建伟D.比尔·盖茨4 关于计算思维本质的说法不正确的是（ C ）。

A.计算思维的本质是抽象和自动化B.计算思维的抽象不同于数学和物理学科，它是更复杂的符号化过程C.计算思维的自动化是指只需要将问题描述发送给计算机，计算机就能自动执行D.计算思维的自动化就是让计算机自动执行抽象得到的算法，对抽象的数据结构进行计算或处理，从而得到问题的结果5. 利用计算机求解问题的过程是（ A ）。

2019 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题： 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. 56 B. 57 C. 58 D. 604.在任意一棵非空平衡二又树( AVL 树 ) T1中，删除某结点v 之后形成平衡二又树T 2，再将 w 插入 T2形成平衡二又树 T 3。

下列关于 T 1与 T3的叙述中，正确的是I. 若 v 是 T 1的叶结点，则 T1与 T3可能不相同Ⅱ .若 v 不是 T1的叶结点，则T1与 T 3一定不相同Ⅲ .若 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. 数据的初始状态仅Ⅲ仅 I、Ⅱ仅Ⅱ、Ⅲ、 IV D. 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. 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

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

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

1. 设n 是描述问题规模的非负整数，下列程序段的时间复杂度是x=0 ；while ( n>= ( x+l ) * ( x+l )) ；x=x+l1/22 )O( n) B. O( nD. C. A. O( log n)O( n)BT 若将一棵树T 转化为对应的二又树，则下列对BT 的遍历中，其遍历序列与T 的后根遍历序列相同的 2.是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历115 个结点，则n 的值是对n 个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有 3.A. 56B. 57C. 58D. 60中，删除某结点T 形成之后形成平衡二又树v T 树) T 插入，再将w 在任意一棵非空平衡二又树( AVL 4.221与T 的叙述中，正确的是T T 。

下列关于平衡二又树331I. 若v 是T 的叶结点，则T 与T 可能不相同311的叶结点，贝V T与T 一定不相同T不是H .若v 311T与T 一定相31的叶结点，则同T若v不是山.1D.仅I、口I、山A.仅IB.仅II C.仅网表示一项包含个活动的工程。

活动下图所示的AOE 8 d 5.的最早开始时间和最迟开始时间分别是A.3和7B.12和12C. 12和14D.15和15 用有向无环图描述表达式(x+y ) *(( x+y ) /x) ，需要的顶点个数6.至少是 A.5B.6C.8D.97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是算法的稳定性山.数据的规模H .数据的存储方式I.数据的初始状态V. 、口、山、W IIV D.仅山仅I、□仅口、山、)，采用线性探查H( key) =key%7现有长度为11 8.且初始为空的散列表HT ,散列函数是线性探测再散列(查找失败的平均查找HT 98 , 20依次插入到HT后，87法解决冲突将关键字序列，40, 30 , 6, 11 , 22, 长度是6C. A. 4B. 5.256.29 D.算法进行模式匹配，到匹配成功时为止，，模”式串S=“ abaabc9. ”，采用KMP 设主串T= “ abaabaabcabaabc 在匹配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对尚未确定最终位置的所有兀素进行一遍处理称为一不可能是快速排序”。

2019年考研计算机学科专业基础综合真题及答案解析(1/40)单项选择题第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/40)单项选择题第2题若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历上一题下一题(3/40)单项选择题第3题对n个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有115个结点，则n的值是A.56B.57C.58D.60上一题下一题(4/40)单项选择题第4题在任意一棵非空平衡二又树(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/40)单项选择题第5题下图所示的AOE网表示一项包含8个活动的工程。

活动d的最早开始时间和最迟开始时间图片A.3和7B.12和12C.12和14D.15和15上一题下一题(6/40)单项选择题第6题用有向无环图描述表达式(x+y)*((x+y)/x)，需要的顶点个数至少是A.5B.6C.8D.9上一题下一题(7/40)单项选择题第7题选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态A.仅ⅢB.仅I、ⅡC.仅Ⅱ、Ⅲ、IVD.I、Ⅱ、Ⅲ、Ⅳ上一题下一题(8/40)单项选择题第8题现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是A.4B.5.25C.6D.6.29上一题下一题(9/40)单项选择题第9题设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A.9B.10C.12上一题下一题(10/40)单项选择题第10题排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。

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

下列每题给出的四个选项中，只有一个选项最符合试题要求）2．若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是。

A．先序遍历B．中序遍历C．后序遍历D．按层遍历3．对n个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有115个结点，则n的值是。

A．56B．57C．58D．604．在任意一棵非空平衡二叉树（AVL树）T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。

下列关于T1与T3的叙述中，正确的是。

I．若v是T1的叶结点，则T1与T3可能不相同II．若v不是T1的叶结点，则T1与T3一定不相同III．若v不是T1的叶结点，则T1与T3一定相同A．仅I B．仅II C．仅I、II D．仅I、III5．下图所示的AOE网表示一项包含8个活动的工程。

活动d的最早开始时间和最迟开始时间分别是。

A．3和7B．12和12C．12和14D．15和156．用有向无环图描述表达式()(()/)x y x y x++，需要的顶点个数至少是。

A．5B．6C．8D．97．选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是。

I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态A．仅III B．仅I、IIC．仅II、III、IV D．I、II、III、IV·2·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 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是。

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

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

下列每题给出的四个选项中，只有一个选项最符合试题要求）2．若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是。

A．先序遍历B．中序遍历C．后序遍历D．按层遍历3．对n个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有115个结点，则n的值是。

A．56B．57C．58D．604．在任意一棵非空平衡二叉树（AVL树）T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。

下列关于T1与T3的叙述中，正确的是。

I．若v是T1的叶结点，则T1与T3可能不相同II．若v不是T1的叶结点，则T1与T3一定不相同III．若v不是T1的叶结点，则T1与T3一定相同A．仅I B．仅II C．仅I、II D．仅I、III5．下图所示的AOE网表示一项包含8个活动的工程。

活动d的最早开始时间和最迟开始时间分别是。

A．3和7B．12和12C．12和14D．15和156．用有向无环图描述表达式()(()/)x y x y x++，需要的顶点个数至少是。

A．5B．6C．8D．97．选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是。

I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态A．仅III B．仅I、IIC．仅II、III、IV D．I、II、III、IV·2·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 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是。

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

下列每题给出的四个选项中，只有一个选项最符合试题要求）2．若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是。

A．先序遍历B．中序遍历C．后序遍历D．按层遍历3．对n个互不相同的符号进行哈夫曼编码。

若生成的哈夫曼树共有115个结点，则n的值是。

A．56B．57C．58D．604．在任意一棵非空平衡二叉树（AVL树）T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。

下列关于T1与T3的叙述中，正确的是。

I．若v是T1的叶结点，则T1与T3可能不相同II．若v不是T1的叶结点，则T1与T3一定不相同III．若v不是T1的叶结点，则T1与T3一定相同A．仅I B．仅II C．仅I、II D．仅I、III5．下图所示的AOE网表示一项包含8个活动的工程。

活动d的最早开始时间和最迟开始时间分别是。

A．3和7B．12和12C．12和14D．15和156．用有向无环图描述表达式()(()/)x y x y x++，需要的顶点个数至少是。

A．5B．6C．8D．97．选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是。

I．数据的规模II．数据的存储方式III．算法的稳定性IV．数据的初始状态A．仅III B．仅I、IIC．仅II、III、IV D．I、II、III、IV·2·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 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是。