下载文档原格式
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年攻读硕士学位研究生入学考试试题考试科目:计算机科学专业基础综合科目代码:874（试题共8页）（答案必须写在答题纸上，写在试题上不给分）数据结构与算法（65分）一、单项选择题（每小题2分，共17小题，共34分1.下面关于“算法”的描述，错误的是（）A.算法必须是正确的B.算法必须要能够结束C.一个问题可以有多种算法解决D.算法的某些步骤可以有二义性2.下面函数的时间复杂度是（）void func(int n){int sum＝0,i, j;for(i＝1; i<n; i++)for(j＝1; j<n; j*＝2)sum++;A.O(log2n)B.O(n2)C.(n log2n)D.O(n)3.下面关于线性表的叙述中，错误的是（）A.线性表采用顺序存储，必须占用一片连续的存储单元B.执行查找操作时，链式存储比顺序存储的查找效率更高。
C.线性表采用链式存储，不必占用一片连续的存储单元。
D.线性表采用链式存储，便于插入和删除操作。
4.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间A.单链表B.带头指针的单循环链表C.带尾指针的单循环链表D带头结点的双循环链表5.一个栈的输入序列为1，2，3，....，n，若输出序列的第一个元素是n，则输出的第i (1<=i<=n)个元素是（）A.不确定B.n-i+1C.iD.n-i6.若一棵完全二叉树有666个结点，则该二叉树中叶子结点的个数是（）A.156B.155C.333D.3347.对于下列关键字序列，不可能构成某二叉查找树中一条查找路径的序列是（）A.99，28，86，36，94，65B.97，18，89，34，76，42C.16，91，68，29，33，50D.21，27，80，76，29，398.下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）A.二叉查找树B.哈夫曼树C.AVL树D.堆9.在右图的AVL树中插入关键字18后得到一棵新AVL树，在新AVL树中，关键字11所在结点的左、右孩子结点中保存的关键字分别是（）A.7，16 C.9，26B.9，18 D.7，1810.将一棵树T1转化为对应的二叉树T2，则T1后序遍历序列是T2的（）序列A.前序遍历B.中序遍历C.后序追历D.层次遍历11.当各边上的权值（）时，BFS算法可用来解决单源最短路径问题A.均相等B.均互不相等C.较小D.以上都不对12.已知有向图G=(V,E)，其中V={V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>}，则G的一个拓扑序列（）A.V1，V3，V2，V6，V4，V5，V7B.V1，V3，V4，V6，V2，V5，V7C.V1，V3，V4，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V713.采用Kruskal算法求右图的最小生成树时，依次选择的边是（）A.(a,b)(b,c)(c,d)(d,f)(a,e)B.(d,f)(c,d)(b,c)(a,b)(a,e)C.(a,b)(b,c)(d,f)(c,d)(a,d)D.(a,b)(d,f)(b,c)(c,d)(a,e)14.设哈希表长为13，哈希函数是H（key）=key％13，表中已有关键字18，39，75，93共四个，现要将关键字为70的结点加到表中，用伪随机探测再散列法解决冲突，使用的伪随机序列为5，8，3，9，7，1，6，4，2，11，13，21则放入的位置是（A.8B.11C.7D.515.一棵高度为3的3阶B树，至少含有（）个关键字A.12B.10C.7D.都不是16.在下列排序算法中，哪一个算法的时间复杂度与数据的初始排列无关（）A.直接插入排序B.希尔排序C.快速排序D.基数排序17.数据表中有10000个元素，如果仅要求求出最大的3个元素，则采用（）算法最节省时间A.堆排序B.希尔排序C.快速排序D.直接选择排序二、综合应用题（18-20题，共31分18.（10分）对于一个字符集中具有不同权值的字符进行Huffman编码时，如果已知某个字符的Huffman 编码为0101，对于其他无字符的Huffman编码，请分析说明:（1）具有哪些特征的编码是不可能的（2）具有哪些特征的编码是一定会有的19.（10分）设有向图用邻接表表示，图有n个顶点，表示为0至n-1，试写一个算法求顶点k的入度（0＜＝k＜n）20.（11分）二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。
2018年广西桂林电子科技大学数据结构及操作系统考研真题Part Ⅰ：数据结构部分一、单选题（每小题2分，共10小题，合计20分）1.判定一个队列QU（最多元素为m0）为满队列的条件是（A）QU->rear － QU->front = = m0 （B）．QU->rear － QU->front －1= = m0 （C）．QU->front = = QU->rear （D）．QU->front = = QU->rear+12. 链表是一种采用（）存储结构存储的线性表（A）顺序（B）链式（C）星式（D）网状3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以4．线性表Ｌ在（）情况下适用于使用链式结构实现。
（A）需经常修改Ｌ中的结点值（B）需不断对Ｌ进行删除插入（C）Ｌ中含有大量的结点（D）Ｌ中结点结构复杂5. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）（A）i （B）n=i （C）n-i+1 （D）不确定6.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）（A) 单链表（B）双链表（C）仅有头指针的单循环链表（D）仅有尾指针的单循环链表7. 树中所有结点的度之和等于所有结点数（）（A) 加0 （B）加1 （C）减1 （D）加n8 在一棵具有 n 个结点的二叉链表中，所有结点的空域个数等于（）（A) n （B） n-1 （C） n+1 （D）2n9. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）（A）空或只有一个结点（B）任一结点无左孩子（C）高度等于其节点数（D）任一结点无右孩子10.有 10 个结点的二叉树中，度为 0 的结点数为4，则度为2 的结点数为（）。
2018年桂林电子科技大学硕士研究生入学考试试题科目代码:823科目名称:数据结构+操作系统注意：答案必须全部写在考点提供的答题纸上，写在试题上无效；答案要标注题号，答题纸要填写姓名和考号，并标注页码与总页数；交卷时，将答题纸与试题一起装入原试卷袋，用我校提供的密封条密封并签名。
PartⅠ：数据结构部分一、单选题（每小题2分，共10小题，合计20分）1.判定一个队列QU（最多元素为m0）为满队列的条件是（A）QU->rear－QU->front==m0（B）．QU->rear－QU->front－1==m0（C）．QU->front==QU->rear（D）．QU->front==QU->rear+12.链表是一种采用（）存储结构存储的线性表（A）顺序（B）链式（C）星式（D）网状3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以4．线性表Ｌ在（）情况下适用于使用链式结构实现。
（A）需经常修改Ｌ中的结点值（B）需不断对Ｌ进行删除插入（C）Ｌ中含有大量的结点（D）Ｌ中结点结构复杂5.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）（A）i（B）n=i（C）n-i+1（D）不确定6.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（）（A)单链表（B）双链表（C）仅有头指针的单循环链表（D）仅有尾指针的单循环链表7.树中所有结点的度之和等于所有结点数（）（A)加0（B）加1（C）减1（D）加n8在一棵具有n个结点的二叉链表中，所有结点的空域个数等于（）（A)n（B）n-1（C）n+1（D）2n9.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）（A）空或只有一个结点（B）任一结点无左孩子（C）高度等于其节点数（D）任一结点无右孩子10.有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（）。
桂林理工大学2021年硕士研究生入学考试试题考试科目代码：877考试科目名称：C语言程序设计（A卷）（总分150分，三小时答完）考生注意：1．请将答题写在答卷纸上，写在试卷上视为无效。
2．考试需带╳╳╳用具一、选择题（每小题2分，共30分）1．若变量已正确定义并赋值，符合C语言语法的表达式是（）。
A．a=20++ B．a=5,6,7 C．a=a+2=3 D．a=12.5%42．若有“int a=1,b=1;”，则循环语句“while(a<20) b++; a++;”的循环执行（）。
A．20次B．21次C．无限次D．19次3．在程序中可以用来作为变量名的合法标识符是（）。
A．switch B．stu_a C．2a1 D．buy?4．有以下代码，当输入数据的形式为10,20,30回车，正确的输出结果为（）。
#include <stdio.h>int main( ){int x,y,z;scanf("%d%d%d",&x,&y,&z );printf("%d" ,x+y+z);return 0;}A．60 B．10 C．30 D．不确定值5．C语言中函数返回值的类型是由（）决定的。
A．return语句中的表达式类型B．调用该函数的主调函数的类型C．调用函数时临时决定D．定义函数时所指定的函数类型6．以下说法正确的是（）。
A．char *a= "123456"; 等价于char *a; *a= "123456";B．char str[10]={ "123456"}; 等价于char str[10]; str[ ]={ "123456"};C．char *s= "123456"; 等价于char *s; s= "123456";D．char c[7]= "123456", d[7]= "123456"; 等价于char c[7]=d[7]= "123456";7．以下程序的输出结果是（）。
