2018年长沙理工大学850数据结构考研真题试题试卷

长沙理工大学数据结构模拟试卷2一、填空题（每空1分，共10分）1．顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

2．非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

3．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。

4．（）可作为实现递归函数调用的一种数据结构。

5．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。

6．设S="I_ am_ a_ teacther"，其长度为（）。

7．稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

8．分块有序是指将文件划分为若干块，（）无序，（）有序。

二、判断题（你认为正确的请打对，错误的打错。

每题2分，共10分）1．线性表的顺序存储结构优于链接存储结构。

2．B—树是一种动态索引结构，它既适用于随机查找，也适用于顺序查找。

3．在线索二叉树中，任一结点均有指向其前趋和后继的线索。

4．用一维数组存储二叉树时，总是以前序遍历存储结点。

5．在索引顺序表上采用分块查找，在等概率情况下，其平均查找长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。

三、单选题（请把你认为正确的答案填入括号内，每小题1分，共10分）1．假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

A 树B 图C 线性表D 集合2．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。

A 栈B队列 C 数组D线性表3．若某线性表经常的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。

A 顺序表B 单链表C 双链表D 单循环链表4．广义表(a, b, (c, (d)))的表尾是（）。

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题及答案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.已知二叉排序树如下图所示，元素之间应满足的大小关系是。

长沙理工大学数据结构模拟试卷3一、填空题（每空1分，共10分）1.（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2.已知线性表A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。

3.数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。

4.设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

5.已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。

6.设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。

7.某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。

8.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。

9.快速排序在（）情况下最不利于发挥其长处。

二、选择题（每题1分，共10分）1.算法指的是（）。

A对特定问题求解步骤的一种描述，是指令的有限序列。

B计算机程序C解决问题的计算方法D数据处理2.链表不具有的特点是（）。

A可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比3.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。

A6B4C3D24.设二叉树有n个结点，则其深度为（）。

A n-1B nC log2n+1D不能确定5.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。

A n=h+mB h+m=2nC m=h-1D n=2m-16.下面关于工程计划的AOE网的叙述中，不正确的是（）。

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. 已知二叉排序树如下图所示，元素之间应满足的大小关系是。

《数据结构》考研真题及解答目录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 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

2022年长沙理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341565、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

A.107B.108C.214D.2159、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

2018年湖南大学866数据结构考研真题（回忆版）
一、选择题（每个1分，共10分）
很简单
二、问答题（每个5分，共15分）
1．给出一段代码求时间复杂度
2．判断一个单链表是否存在回路
3．是判断出栈是否合理
三、分析题（每个15分，共75分）
1．给出一个组序列，判断是什么排序，然后说出归并排序的思想，根据原始序列进行排序直到序列有序，最后是增加一个数字，以第一个为驱值，说出快速排序的思想，根据原始序列进行排序直到序列有序。

2．给出一个图，写出邻接表的形式，利用prim算法画出最小生成树，写出拓扑排序。

3．给出一组数，是二叉排序数告诉前序排序，画出这棵树，写出后序排序。

4．哈夫曼编码，等长编码，比较平均码长。

5．不记得了，已经不难
四、程序设计（共50分）
1．首先定义ADT规范式，给出算法的设计思想，以及伪代码，关键步骤给出注释（10分）
2．给出算法的设计思想，以及伪代码，关键步骤给出注释（10分）
3．一个有向图以邻接表的形式存储，删除给出的任意一条边（15分）
4．设计一个时间复杂度优于O(n2)的算法，给定两个数组A，B以及K，要求a∈A，b∈B，且a＋b＝K。

（15分）。