2018年贵州大学831计算机考研真题

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【考查知识点】图的深度优先遍历。

1历年编程题
1.1递归阶乘
1.2结构体编程-求成绩高于平均成绩的学生学号
1.3打印杨辉三角
1.4统计单链表中等于给定值的结点数
1.5链式存储方法构建二叉树
1.6链表实现A交B
因为是回忆版，不确定题目是不是有序列表，或者题目有没有要求释放空间，或者不破坏原链表的结构，这些在做题时都需要注意，会影响到算法的实现。

无序求交集的写法。

1.7邻接矩阵转邻接表
1.8结构体编程-求工资最少的职工姓名
1.9一个不超过5位的正整数，编程实现数有多少位以及逆序输出这个数
1.10双向冒泡排序算法
1.11编程实现给定一个有向无环图，求图的最长路径，并估计时间复杂度。

贵州大学计算机考研831历年简答题名词解释题及答案目录1 名词解释 (1)1.1 算法 (1)1.2 数据结构 (2)1.3 队列 (2)1.4 栈 (3)1.5 二叉树 (3)1.6 串 (4)1.7 堆排序 (4)1.8 有向图 (4)1.9 拓扑排序 (5)1.10 邻接矩阵 (5)1.11 关键路径 (5)1.12 强连通图 (6)1.13 哈夫曼树 (6)1.14 最小生成树 (7)2 简答题 (7)2.1 数据元素之间的关系在计算机中有几种表示方法？各有什么特点。

(7)2.2 顺序表和链表的特点 (8)2.3 什么是递归程序，递归程序的优缺点。

(8)2.4 常见哈希函数的构造方法有哪些？ (9)2.5 常见的哈希处理冲突的方法有哪些？ (9)2.6 什么是归并排序，归并排序的时间复杂度和空间复杂度是多少？ (10)2.7 什么是逆序数，逆序数的求法。

(10)2.8 线性结构的操作方法有哪些？ (11)2.9 深度优先遍历/广度优先遍历以及辅助结构。

(12)2.10 求前序中序后序序列，基于前序中序求后序 (13)2.11 入栈顺序出栈顺序相关的题 (13)2.12 二叉树/树相关结点数考题 (13)2.13 哈夫曼树，求WPL (14)1名词解释（注意：重要性依次排序，先回答最基本的，再扩展回答）1.1算法（1）定义：算法是指解题方案的准确且完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法要求能够对一定规范的输入，在有限时间内获得所要求的输出，因此一个算法也经常被封装为一个函数，用来实现特定的功能。

（2）算法优劣的衡量标准：不同的算法可能用不同的时间、空间或效率来完成同样的任务。

一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的时间复杂度是一个函数，它定性描述该算法的运行时间。

这是一个代表算法输入值的字符串的长度的函数。

时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

注意事项：1、请勿使用书籍、Ｕ盘、光盘等任何资料。

2、考试时间：2小时。

3、文件一定要保存在Ｅ盘，其余盘重新启动后会还原。

程序设计，用C语言完成（75分）1、从键盘上输入一个字符串，将该串分为数字、字母、其他字符三个部分输出，例如：输入：Thdad29#@12aH;77输出：ThdadaH291277#@;2、对任意正整数N，求XN，，要求运算的时间复杂度为O(logN)。

例如X30，有X30=X15*X15，X15=X7*X7*X，X7=X3*X3*X，X3=X*X*X，共7次乘法运算完毕。

3、有N个小朋友围成一圈玩击鼓传花游戏，将小朋友编号为1~N，从1号开始传花，每次传3个，拿到花的小朋友表演节目后退出，任给N，问最后一个表演的小朋友编号是多少。

例如：5个小朋友，从1号开始传花，第一个表演的是3号，第二个表演的是1号，第三个表演的是5号，第四个表演的是2号，最后一个表演的是4号。

数据库（25分）4、设某物流系统有如下表：仓库表（仓库号，仓库名，地点）货物表（货物号，货物名，单价）出入库表（仓库号，货物号，出入库数量，时间）要求：（1）使用SQL语句建立以上三张表（需要主键、外键）（2）使用SQL语句查询：单价高于100元的货物名、出入库总次数、总数量注：不需要在电脑上建表，仅需要写出SQL语句，保存到文本文件中即可2016年的：程序设计，可使用C、C++、Java或C#完成（75分）1、从键盘输入一个字符串（可能含数字、字母、其他可见字符），输出出现频率最高的英文字母及次数，忽略字母的大小写（如大写A 和小写a均视为a）。

例如：输入：There are 10,000 soldiers in the town.输出：e 54、某学院管理系统有如下表：课程表（课程号，课程名，任课老师姓名，学时数）学生表（学号，学生姓名，性别，年级）选课表（课程号，学号，成绩）要求：（1）使用SQL语句建立以上三张表（需要主键、外键）（2）建立视图：对于每门课程，列出课程号，课程名以及不及格学生人数注：不需要在电脑上建表，仅需要写出SQL语句，保存到文本文件中即可1.视图的作用是什么？2.关系数据库的作用？3.数据库设计的基本步骤？4.数据库安全性的常用方法和常用技术？贵大数据库笔试：选择题都比较简单，知识面比较杂，一般的复习题的知识能复习到就行。

2016-2018年贵大831真题答案特别说明：1、本文档是贵州大学2014年度计算机考研831考题的参考答案整理，原试题在网络上可以搜索到，答案也是经过仔细斟酌，对一些难点进行了解释，备考中的考生可使用此文档作为参考答案，节约整理的时间。

2、本参考答案旺旺考研享有著作权，同时我们尊重原创，尊重知识，如果有使用者发现答案中有任何不解或纰漏，随时可以和我们练习，我们会第一时间处理。

12016年1.1选择题1.D2.D考察二叉树结点数。

满二叉树的情况下，结点数最多。

深度为6的二叉树，最多有2^k – 1个结点。

3.A在二叉排序树树形状为每层一个结点时，此时查找比较次数最对。

4.C5.C6.D这个题目考察的不够严谨，因为冒泡排序可能是优化的也可能是不优化的。

相对来说D项最佳。

下面是每个排序的解释：直接插入排序很明显，在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置，因此直接插入与初始序列有关。

希尔排序是基于直接插入的，所以关键字比较的次数与记录的初始排列次序有关。

选择排序是指扫描整个线性表，从中选出最小的元素，将它交换到表的前面。

然后对剩下的字表采用同样的办法，所以关键字比较的次数与记录的初始排列次序无关。

折半插入排序，比较次数是固定的，与初始排序无关。

快速排序，初始序列不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分的次数，所以会影响总的比较次数，有关；归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关。

冒泡排序如果加入了优化，比如加入了本趟排序是否有数据进行交换的判断，如果上次循环没有交换数组中的两个值则说明数组已经有序，直接退出冒泡排序过程。

因此冒泡排序与初始序列有关。

堆排序和选择排序的排序次数与初始状态无关，即最好情况和最坏情况都一样。

元素的移动次数与关键字的初始排序无关的是：归并排序、基数排序元素的比较次数与初始序列无关的是：选择排序、基数排序、堆排序、折半插入算法的时间复杂度与初始序列无关的是：堆排序、归并排序、简单选择排序、基数排序7.D考察B树的概念，冲刺课查找排序章节有讲。

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，右子树为空。

贵州大学研究生入学考试模拟卷（A）（所有答案必须答在专用答题纸上，否则答案无效）考试科目名称：程序设计与数据结构考试科目代码：840一、选择题（单项选择，25个小题，每题2分，共50分）1、关于函数，下列叙述正确的是＿＿＿。

A．函数必须要有return语句B．一个函数中可以定义其它的函数C．main()函数可以被所在程序的其他函数调用D．一个C程序只能有一个main()函数2、设有 float a=12.5，则表达式（a+1/2）的值是_____。

A. 13.0B. 13C. 12.5D. 13.53、能正确地用逻辑关系表示: 10<a<15 的C语言表达式是______。

A. 10<A<15B. 10<a && a<15C. 10<a||a< 15D. 10<=a && a<=154、假设变量已定义，下面正确的赋值语句是______。

A．j++ B．x=y=1; C．x=4*y=2; D．x=float m;5、执行以下程序段后的b的值是＿＿＿。

int a=5,b=6,c=1,x=2,y=3,z=4;c=(a=c>x)&&(b=y>z);A．0 B．1 C．6 D．56、对于 int i,a[7]={5,3,1,8,3,5,6};，能正确访问所有数组元素的for循环是：A. for(i=0;i>=7;i--) printf("%d\n",a[6-i]);B. for(i=0;i>7;i++) printf("%d\n",a[6-i]);C. for(i=0;i<=7;i++) printf("%d\n",a[6-i]);D. for(i=0;i<7;i++) printf("%d\n",a[6-i]);7、已知i=1，sum=0，执行以下程序段后sum的值为＿＿＿。

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)。

2018年研究生全国统考计算机试题——操作系统部分试题解析一、单项选择题23. 下列关于多任务操作系统的叙述中，正确的是____。

Ⅰ．具有并发和并行的特点Ⅱ．需要实现对共享资源的保护Ⅲ. 需要运行在多CPU的硬件平台上A. 仅ⅠB. 仅ⅡC. 仅Ⅰ、ⅡD. Ⅰ、Ⅱ、Ⅲ答案C，多CPU并非是多任务操作系统的必备硬件，但CPU也可运行多任务。

24. 某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1μs。

在T时刻就绪队列中有3个进程P1、P2和P3，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。

若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，则系统的平均周转时间为A. 54μsB. 73μsC. 74μsD. 75μs答案D，进程运行的顺序为P2、P3、P1，P2的周转时间为15μs+1μs+24μs=40μs，P3的周转时间为(18+1+24+1+36)μs=80μs，P1的周转时间为(30+1+24+1+36+1+12)μs=105μs，系统的平均周转时间为75μs。

25. 属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。

thread1和thread2实现对全局变量x加1的机器级代码描述如下。

在所有可能的指令执行序列中，使x的值为2的序列个数是A. 1B. 2C. 3D. 4答案B，thread1和thread2互斥执行对x的共享。

26. 假设系统中有4个同类资源，进程P1、P2和P3需要的资源数分别为 4、3和1，P1、P2和P3已申请到的资源数分别为2、1和0，则执行安全性检测算法的结果是( )。

A. 不存在安全序列，系统处于不安全状态B. 存在多个安全序列，系统处于安全状态C. 存在唯一的安全序列P3、P1、P2，系统处于安全状态D. 存在唯一安全备列P3、P2、P1，系统处于安全状态答案A，此刻可用资源数为1 ，即使P3可以获得并运行，但P1和P2无法获得足够资源而永远等待。

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, 13. 设有一个12×12的对称矩阵M，将其上三角部分的元素m i, j（1≤i≤j≤12）按行优先存人C 语言的一维数组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. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。

2018年全国硕士研究生统一入学考试自命题试题（A卷)*＊＊*＊*＊**＊＊＊*＊**＊＊＊＊＊＊＊***＊**********＊*＊＊＊＊＊**＊*****＊*＊**＊****＊＊＊***＊***＊***＊*＊＊＊＊***＊＊＊＊＊*＊学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位) 085211考试科目名称及代码:数据结构830考生注意：所有答案必须写在答题纸（卷)上，写在本试题上一律不给分。

考试科目：数据结构共5页，第1 页考试科目：数据结构共5 页，第2 页图12。

一棵二叉树，若根结点的左右子树均有三个结点，其左子树的先序序列与中序序列相同,右子树的中序序列与后子序序列相同，试构造该二叉树。

(7分）3。

已知序列（12,18,4,3，6,13,2,9，19，8).请给出采用希尔排序对该序列作升序排序的每一趟结果（步长分别为5，3，2，1）.（8分）4. 设有一组关键字（33,41,20,24,30，13，01,67)，采用散列函数H（key)=(3＊key) 11，采用线性探测再散列解决冲突，H i=（H（key)+d i）%11,其中d i=1，2,…，10. 试在0～10散列地址空间中对该关键字序列（按从左到右的次序）构造散列表，并计算在查找概率相等的前提下查找成功时的平均查找长度。

（10分)5.已知图2所示的有向图。

设其顶点a，b，c,d,e表示一个乡的5个村庄，弧上的权值表示为两村之间的距离。

乡内要建立一所学校，问学校设在哪个村庄才能使从各村出发到学校的距离总和最小.（要求回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果)。

（10分）图2考试科目: 数据结构共5 页，第3 页五、算法填空(共2小题，每空2分，共20分）1。