下载文档原格式
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 页（共 2 页）数据结构试卷中南大学考试试卷2012 -- 2013学年 1学期时间 100 分钟 2013年 1 月 14 日数据结构课程 48 学时 3 学分 考试形式： 闭 卷专业年级：通信工程 11 级总分 100 分，占总评成绩 70 %注：此页不作答题纸，请将答案写在答题纸上一、线性结构题（ 5 个小题，每个小题 8 分，共计 40 分）1. 在一个单链表中，若p 所指结点不是最后结点， s 指向已生成的新结点，则在p 之后插入s 所指结点的正确操作是如何表达？（8 分）2. 设有字符串为 3*-y ，试利用栈写出将其转换为 3y-* 的操作步骤。
假定用X 代表扫描该字符串过程中顺序取一个字符进栈的操作，用 S 代表从栈中取出一字符加入到新字符串尾的出栈操作。
例如，ABC 变为 BCA 的操作步骤 XXSXSS 。
（ 8 分）3. 若 front 和 rear 分别表示循环队列 Q 的头指针和尾指针， m0表示该队列的最大容量，则循环队列为空的条件是什么？循环队列为满的条件是什么？（8 分）4. 二维数组 A[20][20] 采用按行为主序的存储方式，每个元素占4 个字节的存储单元，若A[0][0] 的存储地址为 300，则 [A][10][10] 的地址是多少？（ 8 分 ）5．用二分查找法对一个长度为10 的有序表 {8,12,15,17,19,23,24,26,29,33}进行查找，填写查找每一元素需要的比较次数。
（ 8 分）二、非线性结构题（ 5 个小题，每个小题 8 分，共计 40 分）1.现有某二叉树，按先根遍历的序列为 ABDEFCG ，H 按中根遍历的序列为 DEFBGHC ，A 试画出此二叉树。
（ 8 分）2.已知无向图 G 的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从 V 0 开始的深度优先搜索的序列。
（ 8 分）V 0 0 1 1 0 0V 1 1 0 1 1 1 V 2 1 1 0 1 1 V 3 0 1 1 0 1 V 40 v 0 v 1 1 1 v 2 v 1 3 0v 4110100230 3 50 10 60520第4 题图43．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），求利用堆排序的方法建立的初始堆。
中南大学计算机数据结构2013试题参考答案中南大学考试试卷2015--2016学年上学期期末考试试题时间100分钟数据结构课程56学时3.5学分考试形式：闭卷专业年级：计算机科学与技术10级总分100分，占总评成绩70%姓名班级学号（本试卷共四道大题，答案全部做在答题纸上！）一、选择题(每题2分，共24分)1.以下数据结构中，属于线性结构的是（）A．图B．栈C．二分查找树D．森林2.用二分法查找表(a0,a1,a2,a3,……a16)，需要比较2次才能找到的元素是（）A．a7和a16 B．a11和a13C．a1和a14 D．a3和a123.用概率查找改进查找效率，是经过多次查找以后使得（）A．查找次数越少的元素查找速度越快B．查找次数越少的元素越往前存放C．查找次数越多的元素越往后存放D．查找次数越多的元素查找速度越快4.二分查找要求元素( )A.有序、顺序存储B.有序、链式存储C.无序、顺序存储D.无序、链式存储5.已知pPre为指向链表中某结点的指针，pNew是指向新结点的指针，以下哪段伪码算法是将一个新结点插入到链表中pPre所指向结点的后面？（）A．pPre->link = pNew; pNew = null;B．pPre->link = pNew->link; pNew->link = null;C．pNew->link = pPre->link; pPre->link = pNew;D．pNew->link = pPre->link; pPre->link = null;6.在递归算法执行过程中，计算机系统必定会用到的数据结构是（）A．队列B．链表C．栈D．二叉树7.一个队列的入列序为ABCD，则队列的可能输出序列为（）A．DCBA B．ABCDC．ADCB D．CBDA8.具有10个叶子结点的二叉树中有（）个度为2的结点A．8 B．9C．10 D．119.若A=10，B=4，C=6，D=4，E=15则后缀表达式“AB*CD+-E+”的值为( )。
2018年华中科技大学834计算机专业基础综合（数据结构、计算机网络）考研真题（回忆版）数据结构部分一、选择题（共10道，一个2分，共20分）1．数据结构的逻辑结构分类是哪两种？2．给定一颗完全二叉树的结点数，求其中的叶节点个数3．一个有n个结点的图构成一个邻接矩阵几乘几的矩阵4～10暂缺二、简答题（共5道题，前四个15分，最后一个10分，今年没有编程题，也就是都是算法和推演，不用写代码，都是根据要求写结果和原理）1．给了8个左右的数字的一个集合，比如{75，63，43…}，要求一次读取一个，输出成一个二叉排序树，写出结果，并且求等概率情况下的平均查找长度。
2．给了一个包含有ABCDEFGH这几个点的二叉树的先序和中序排列，要求画出原二叉树。
3．一个指令集合{I1，I2，I3…}，对应给出了每个指令对应的发生概率大小{0.03，0.03，0.15，0.15，0.3，0.4}（这个数字印象比较深基本差不多），让求出用此集合构成的哈夫曼树。
求出他们的一个组织，并且求出每个指令的哈夫曼编码。
4．给出了一个由ABCDEFGHLM点组成的的无向带权图，让求出最小生成树（这里题干没有写用哪种算法）。
5．给定了一个树，转化成对应的二叉树，大概有8个点左右。
计算机网络部分一、选择题（共10道，一个1分，共10分）1．IPV4和IPV6的特征对比，选出一个错误的2．TCP拥塞控制中慢开始算法的特征，选出一个错误的3～10暂缺二、填空题（共10道，一个1分，共10分）1．IEEE802.11用的协议是_____2．CDMA2000采用的编码方式是_____3．移动IP的基本工作过程（给了其中3个步骤，填另一个）4．信道划分的三种方式（给了其中2个，填另一个）5～10暂缺三、简答题（共7道，共40分）1．主机A向主机B先后发两个报文，给出了每个报文的字节数，然后分别问了第一个先到的情况下和第二个报文先到的情况下各自的确认号，源，目的。
计算机专业基础综合数据结构（集合）历年真题试卷汇编9(总分：70.00，做题时间：90分钟)一、单项选择题(总题数：20，分数：40.00)1.下列二叉排序树中查找效率最高的是( )。
【中南大学2003二、11(1分)】（分数：2.00）A.平衡二叉树√B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树解析：2.构造一棵具有n个结点的二叉排序树，最理想情况下的深度为( )。
【华中科技大学2007一、14(2分)】（分数：2.00）A.n／2B.nC.[log 2 (n+1)]D.[log 2 (n+1)] √解析：3.设二叉排序中关键字由1到1000的整数构成，现要查找关键字为363的结点，下述关键字序列中，不可能是在二叉排序树上查找的序列的是( )。
【北京交通大学2005一、1(2分)】（分数：2.00）A.2，252．401，398，330，344，397，363B.924，220，911，244，898，258，363C.925，202，911，240，912，245，363 √D.2，399，387，219，266，382，381，278，363解析：4.分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是( )。
【合肥工业大学2000一、4(2分)】（分数：2.00）A.(100，80，90，60，120，1 10，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，20，110，130) √D.(100，80，60，90，120，130，110)解析：5.分别以下列序列构造二叉排序树，与众不同的是( )。
【中国科学技术大学2004】（分数：2.00）A.100，80，60，85，110，120，150 √B.100，80，60，85，120，110，150C.100，80，85，60，120，110，150D.100，80，60，85，120，150，110解析：6.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作( ) 型调整以使其平衡。
中南大学十套数据结构试题及答案数据结构试卷(1)................1数据结构试卷(2)................4数据结构试卷(3)................6数据结构试卷(4)................8数据结构试卷(5)................11数据结构试卷(6)................14数据结构试卷(7)................16数据结构试卷(8)................18数据结构试卷(9)................20数据结构试卷(10)................2 3数据结构试卷(1)参考答案.........26数据结构试卷(2)参考答案 (27)数据结构试卷(3)参考答案.........28数据结构试卷(4)参考答案 (30)数据结构试卷(5)参考答案.........32数据结构试卷(6)参考答案 (33)数据结构试卷(7)参考答案.........36数据结构试卷(8)参考答案...37数据结构试卷(9)参考答案.........38数据结构试卷(10)参考答案 (39)数据结构试卷(1)1，单项题(每题2分，共20分)1。
堆栈和队列的共同特征是()A.仅允许在端点b插入和删除元素。
所有元素都是先进先出。
所有元素都是先进先出。
没有公共基础2。
以链接方式存储的队列。
在插入操作过程中()。
A .只应修改头部指针b。
头指针和尾指针都应该修改c .只有尾指针d .头指针和尾指针都应该修改3。
下列哪种数据结构是非线性结构？()队列b堆栈c线性表d二叉树4。
有一个二维数组[m][n]。
假设[0][0]存储在644(10)中，[2][2]存储在676(10)中。
每个元素占据一个空间。
问一问[3][3)(10)它储存在哪里？脚注(10)用十进制表示a . 688b . 678c . 692d . 6965。
这棵树最适合用来代表()a .有序数据元素b .无序数据元素c .元素之间具有分支层次关系的数据d .元素之间没有连接的数据6。
《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。
若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。
设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。
若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。
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. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。
数据结构考研真题及其答案数据结构是计算机科学与技术专业考研中的重要科目之一，它对于培养学生的程序设计和算法分析能力具有关键作用。
以下将为大家呈现一些典型的数据结构考研真题，并提供详细的答案解析。
一、选择题1、若一个栈的输入序列为 1, 2, 3, 4, 5，不可能得到的输出序列是（）A 2, 3, 4, 1, 5B 5, 4, 3, 2, 1C 1, 5, 4, 3, 2D 3, 4, 2, 5, 1答案：C解析：栈的特点是“后进先出”。
对于选项 C，先输出 1，意味着 2、3、4、5 都已入栈，此时栈顶元素为 5，不可能接着输出 5 之后就输出4。
2、已知一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，则其后序遍历序列为（）A CDBAFGEB CDBGFEAC CDBAGFED BCDAFGE答案：B解析：先根据先序和中序遍历序列构建二叉树。
先序遍历中第一个节点 A 为根节点，在中序遍历中找到 A，其左边的 CBD 为左子树，右边的 EGF 为右子树。
同样的方法确定左子树和右子树的结构。
然后按照“左子树右子树根节点”的顺序得到后序遍历序列 CDBGFEA。
3、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的非零元素个数为（）A n(n 1) ／ 2B n(n ＋ 1) ／ 2C n(n 1)D n(n ＋ 1)答案：A解析：无向图的邻接矩阵是对称的。
对于顶点 i 和 j（i ≠ j），若它们之间有边，则矩阵中对应位置为 1，共有 n(n 1) ／ 2 对不同的顶点对，所以非零元素个数为 n(n 1) ／ 2 。
二、简答题1、简述冒泡排序的基本思想，并分析其时间复杂度和空间复杂度。
答案：冒泡排序的基本思想是通过相邻元素的两两比较和交换，将最大（或最小）的元素逐步“浮”到数组的一端。
时间复杂度：在最坏情况下，即数组完全逆序，需要进行 n 1 轮比较，每轮比较 n i 次（i 为轮数，从 1 到 n 1），所以总的比较次数为n(n 1) ／ 2，时间复杂度为 O(n^2)。
数据结构试卷（一） .................. 1 数据结构试卷（二） .................. 4 数据结构试卷（三） .................. 6 数据结构试卷（四） .................. 8 数据结构试卷（五） .................. 11 数据结构试卷（六） .................. 14 数据结构试卷（七） .................. 16 数据结构试卷（八） .................. 18 数据结构试卷（九） (20)数据结构试卷（一）参考答案 ........... 26 数据结构试卷（二）参考答案 ........... 27 数据结构试卷（三）参考答案 ........... 28 数据结构试卷（四）参考答案 ........... 30 数据结构试卷（五）参考答案 ........... 32 数据结构试卷（六）参考答案 ........... 33 数据结构试卷（七）参考答案 ........... 36 数据结构试卷（八）参考答案 ........... 37 数据结构试卷（九）参考答案 .. (38)数据结构试卷（一）、单选题（每题 2 分，共 20 分）1. 栈和队列的共同特点是 （ ）。
A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D. 头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？ （ ）A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组 A[m][ n]，假设 A[0][0]存放位置在 644（io ），A[2][2]存放位置在676（10），每个元素占一个空间， 问 A[3][3] （10）存放在什么位置？脚注 （10）表示用 10 进制 表示。
