贵州大学831程序设计与数据结构考研真题试题2013—2016年

贵州大学计算机考研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符号表述，不包括这个函数的低阶项和首项系数。

数据结构排序历年考研练习题库试卷及答案数据结构排序历年考研练习题库试卷及答案一、冒泡排序冒泡排序是一种基本的排序算法，它通过重复地交换相邻两个元素的位置来实现排序。

算法的基本思想是从待排序的元素中比较相邻的两个元素大小，并根据需要交换它们的位置，直到整个序列有序为止。

冒泡排序的原理如下：首先从序列的第一个元素开始，比较相邻的两个元素的大小，若前面的元素大于后面的元素，则交换它们的位置；否则，继续比较下一对相邻元素，直到比较到序列的最后一个元素。

这样一趟比较下来，序列中最大的元素就会被交换到最后一个位置。

接着，对序列中剩下的 n-1 个元素重复上述过程，执行 n-1 趟比较，直到整个序列有序。

在实践中，冒泡排序的时间复杂度为 O(n^2)，其中 n 为待排序序列的长度。

尽管冒泡排序存在其它更好的排序算法，但它具有编码简单、实现容易以及对小规模数据排序的优势。

二、选择排序选择排序也是一种简单直观的排序算法，它的思想是将待排序序列分为已排好序的部分和未排序的部分，每次选取未排序部分中最小（或最大）的元素，将其放置在已排好序的部分的末尾。

重复此过程，直到整个序列有序。

选择排序的具体步骤如下：首先从待排序序列中找到最小（或最大）的元素，然后将其与序列的第一个元素交换位置，将该元素视为已排序部分；接着，在剩下的未排序部分中找到最小（或最大）的元素，将其与第二个元素交换位置，将该元素视为已排序部分的最后一个元素；以此类推，每次选择序列中最小（或最大）的元素，并将该元素放置在已排序部分的末尾。

最终完成排序。

选择排序的时间复杂度同样为 O(n^2)，其中 n 为待排序序列的长度。

相比于冒泡排序，选择排序的交换操作较少，因此在实际应用中，选择排序的性能要优于冒泡排序。

三、插入排序插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素逐个插入已排好序的部分中，直到整个序列有序。

与冒泡排序和选择排序不同，插入排序是一种原地排序算法。

注意事项：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树的概念，冲刺课查找排序章节有讲。

数据结构考研真题及其答案_研究生入学考试_高等教育_教育专区数据结结考研真题及其答案据结构是计算机科学中重要的一门课程，它研究的是如何组织和管理数据的方式。

对于计算机专业的研究生来说，数据结构是必修课程，考研真题的复习和备考对于学生来说是非常重要的。

在本文中，我们将介绍一些数据结构考研真题及其答案，帮助学生更好地复习和备考。

第一题：给出以下数据结构中各个操作的时间复杂度：数组、链表、堆、栈、队列。

答案：数组的插入和删除操作的时间复杂度为O(n)，查找操作的时间复杂度为O(1)；链表的插入和删除操作的时间复杂度为O(1)，查找操作的时间复杂度为O(n)；堆的插入、删除和查找操作的时间复杂度都为O(logn)；栈的插入、删除和查找操作的时间复杂度都为O(1)；队列的插入、删除和查找操作的时间复杂度都为O(1)。

第二题：给出以下数据结构的特点：栈、队列、堆、二叉树、图。

答案：栈是一种后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作；队列是一种先进先出（FIFO）的数据结构，插入操作在一端进行，删除操作在另一端进行；堆是一种完全二叉树，具有父节点的值大于等于子节点的值（大顶堆）或父节点的值小于等于子节点的值（小顶堆）的性质；二叉树是一种每个节点最多有两个子节点的树；图是由节点和连接节点的边组成的数据结构。

第三题：给定一个有序数组，要求在其中查找一个元素的位置并返回，如果找不到则返回-1，设计一个算法实现上述功能。

答案：可以使用二分查找算法来实现上述功能。

首先，将要查找的元素与有序数组的中间元素进行比较，如果相等，则返回中间元素的位置；如果要查找的元素小于中间元素，则在数组的前半部分继续进行二分查找；如果要查找的元素大于中间元素，则在数组的后半部分继续进行二分查找。

重复这个过程，直到找到要查找的元素或者确定元素不存在为止。

第四题：给出以下排序算法的时间复杂度：冒泡排序、插入排序、选择排序、快速排序、归并排序。

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

数据结构考研真题及其答案数据结构是计算机科学与技术专业考研中的重要科目之一，它对于培养学生的程序设计和算法分析能力具有关键作用。

以下将为大家呈现一些典型的数据结构考研真题，并提供详细的答案解析。

一、选择题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)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。

贵州大学2014-2015学年第一学期考试试卷 A数据结构与算法注意事项：1. 请考生按要求在试卷装订线内填写姓名．学号和年级专业。

2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。

3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。

4. 满分100分，考试时间为120分钟。

一．单项选择题（共10分,每题1分）1. 顺序存储结构的优势是（ ）。

(A)．利于插入操作 (B)．利于删除操作 (C)．利于顺序访问 (D)．利于随机访问2．算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，为了使得算法中的每一条指令有确切的含义，算法应该具有（ ）。

(A)．有穷性 (B)．可行性 (C)．确定性 (D)．正确性3．在长度为n 的线性表中插入一个元素，假定在线性表的任何位置上插入元素是等概率的，则插入一个元素大约需要移动线性表中元素的个数是（ ）。

(A)．(n-1)/2 (B)．n/2 (C)．(n+1)/2 (D)．n+14．在下列单链表中，已知p 为单链表存储结构中指向结点a 的指针，q 为单链表存储结构中指向结点x 的指针，删除结点x 的操作为（ ）。

p（A ）．p->next=q->next; q=p->next; e=q->data; free(q); （B ）．q=p->next; p->next=q->next; free(q); e=q->data; （C ）．e=q->data; q=p->next; p->next=q->next; free(q); （D ）．q=p->next; p->next=q->next; e=q->data; free(q);5．假设栈S=(a 1,a 2,…,a n )，其中a 1为栈底元素，a n 为栈顶元素，那么出栈序列中第i 个元素是（ ）。

贵州大学2014-2015学年第一学期考试试卷 B数据结构与算法评分标准及参考答案一、选择题（共15分，每题1分）1、C2、D3、B4、B5、B6、C7、D8、B9、A 10、D二、填空题（共14分，每空1分）1. 特殊、栈顶2. 有序序列、后缀表达式3. 894. n(n-1)/2、n-15. 队尾、队头6. 2i+2、2i+3、i+17. ALBECDWX、ALCBERWX8. 2三、应用题（共56分）1.（10分）(1) 哈夫曼树如下，每画对一个叶子，给0.5分，结构1分，共5分F G DEA BHC（2）WPL=0.02*5+ 0.04*5+0.06*4+0.08*4+0.1*4+0.3*2+0.4*1=2.26（1分）（3）A: 1000 B:1001 C:11 D:001 E:01 F:0000 G:0001 H:101（每个0.5分，共4分）2.（9分）（1）Hash表（2分）（2）0123456789101112(3)查找成功的平均查找长度：（2分） （5*1+2*2+1*3+1*7）/9=19/9查找不成功的平均查找长度：（2分）（3+2+1+1+1+1+10+9+8+7+6+5+4）/13=58/13 3.（9分） （1）、构造（3分）(2)、10 14 15 19 20 21 22 56（3分） （3）、折半查找过程的判定树（3分）4.（10分）(1) 邻接矩阵：（4分）⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞6020105053010010401V 2V 5V 3V 4V 6V 1V 2V 3V 4V 5V 6V(2) 求最短路径过程：（6分）则从顶点V 0到其余各顶点的最短路径为：534120V V V V V V →→→→→（1分） 5.(9分)(1)A →C →B →D →E →F 或A →C →B →E →D →F (1分) (2) 工程的工期为43天（1分）(3) 每个事件的最早开始时间ve[i]、最迟开始时间vl[i]，以及每个活动最早开始时间e[k]、最迟开始时间l[k]如下表（5分）则关键活动为：15、4、19、5 （1分） 关键活动图为：（1分）6.（8分）(1) （写一行0.5分，共4分）{46,58,45,15,35,90,24,62} {46,58,45,15,35,90,24,62} {45,46,58,15,35,90,24,62} {15,45,46,58, 35,90,24,62} {15,35,45,46,58, 90,24,62} {15,35,45,46,58, 90,24,62} {15, 24,35,45,46,58,90,62} {15,24,35,45,46,58 ,62,90}（2）二叉排序树如下（写一个结点0.5分，共4分）4645153524589062四、 算法设计（共20分）1.（12分）Status ListInsert_L(LinkList &L , int i, ElemType e) { //在带头结点的单链表L 中第i 个位置之前插入元素e p=L ;j=0;while(p&&j<i-1) //寻找第i-1个结点{p=p->next;++j;}if(!p||j>i-1) return ERROR; //i小于1或者大于表长加1s=(LinkList)malloc(siazeof(LNode)); //生成新结点s->data=e;s->next=p->next;p->next=s;return OK;} …………………………………………………………………………………………….6分.Status ListDelete_L(LinkList &L, int i, ElemType &e){//在带头结点的单链表L中，删除第i个元素，并用e返回其值p=L;j=0;while(p->next&&j<i-1) //寻找第i个结点，并令p指向其前前驱{p=p->next;++j;}if(!(p->next)&&j<i-1) return ERROR; //删除位置不合理q=p->next; p->next=q->next; //删除并释放结点e=q->data;free(q);return OK;} …………………………………………………………………………………………….6分.2.（8分）Status DispLeaf2(Bitree T) {//输出二叉树的所有度为1的结点if (T!=NULL) {if (T->lchild！=NULL && T->rchild！=NULL)printf("%c ",T->data);else {DispLeaf(T->lchild);DispLeaf(T->rchild);}}} …………………………………………………………………………………………….8分.。