数据结构复习题集与答案解析(12级)

数据结构复习题及答案一、选择题1. 在数据结构中，以下哪种数据结构允许在任何位置进行插入和删除操作？A. 栈B. 队列C. 链表D. 数组答案：C2. 以下哪个选项是二叉搜索树的特性？A. 所有左子树的节点值小于根节点值B. 所有右子树的节点值大于根节点值C. 所有左子树的节点值大于根节点值D. 所有右子树的节点值小于根节点值答案：A3. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构？A. 栈B. 队列C. 链表D. 数组答案：A二、填空题1. 在一个有n个节点的完全二叉树中，如果节点按层次从上到下、从左到右编号为1, 2, 3, ..., n，则第i个节点的左孩子节点的编号为____。

答案：2i2. 哈希表解决冲突的一种方法是使用链地址法，其中每个哈希表项是一个____。

答案：链表3. 在图的表示方法中，邻接矩阵适合表示____图，邻接表适合表示____图。

答案：稠密；稀疏三、简答题1. 描述什么是递归，并给出一个简单的递归算法的例子。

答案：递归是一种在算法中调用自身的方法，用于解决可以分解为相似子问题的问题。

一个简单的递归算法例子是计算阶乘：n! = n * (n-1)!，其中基本情况是0! = 1。

2. 解释什么是图的广度优先搜索（BFS）算法，并说明其在哪些情况下适用。

答案：广度优先搜索（BFS）是一种遍历或搜索树或图的算法，它从根节点开始，逐层遍历节点。

BFS适用于寻找最短路径或在层次结构中按层次顺序访问节点的情况。

四、编程题1. 给定一个单链表，请编写一个函数来反转该链表。

答案：（此处省略具体代码实现，只提供解题思路）要反转一个单链表，可以创建一个新的链表头节点，然后遍历原链表，将每个节点的next指针指向前一个节点，直到链表末尾。

最后，将新链表的头节点设置为原链表的最后一个节点的前驱节点。

（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。

1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。

假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。

3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。

现要求采⽤循环链表结构设计⼀个算法，模拟此过程。

4、编程实现单链表的就地逆置。

23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。

3、假设以I和O分别表⽰⼊栈和出栈操作。

栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。

（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。

若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。

5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（⼊栈满等）给出相应的信息。

设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。

北京师范大学2013-2014学年第1学期期末考试试卷（A卷）课程名称：数据结构任课教师姓名: 郑新肖永康卷面总分：100分考试时长：100分钟考试类别：闭卷0开卷口其他口院（系）：专业：年级：姓名：学号：阅卷教师（签字）： ______________________一、选择题（每小题2分，共20分）1.算法分析的目的是（）。

A.研究算法的输入与输出Z间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2.与双向链表相比较，单向链表的缺点之一是（）。

A.无法省略头结点指针B.插入和删除操作麻烦C.无法进行随机访问D.占用更大的存储空间3.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为：p->rlink=q; p->llink=q->llink; q->llink=p 和（）。

A. q->rlink=pB. q-Allink-ArlinkrpC・ p->llink->rlink=p D. p->rlink->rlink=p4.一个以整数为栈元素的栈，若元素的进栈顺序为1, 2, 3, 4, 5,出栈可以发生在任何时刻。

则下面的序列中，（）是可能的出栈序列。

A. 2,5,4,1,3B. 3丄4,2,5C. 5,4,3丄2D. 2,3,1,5,45.n个结点的线索二叉树上，含有的线索数为（）。

A・2n B・n・l C・n+1 D・n6.已知某非空二叉树采用顺序存储结构，树屮结点的数据信息依次存放在一个一维数组中，该二叉树的中序遍历系列为（）A. GDBAFHCEB. GBDAFHCEC. BDGAFHCED. BGDAFHCE7.以下序列不是堆的是( )oA.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)&导致图的遍历序列不唯一的因素有（）。

数据结构复习提纲（12级）数据结构复习提纲（12级）第一章绪论§1.1 数据结构1.什么是数据结构？包括哪三方面的内容？2.什么是数据类型？§1.2 算法及其描述1.算法具有哪5个特性？2.算法描述有哪些方式？§1.3 算法分析1.能分析小程序段的时间复杂度（习题1.5，1.6）2.时间复杂度T(n)=O(f(n))的含义是什么？(习题1.3)3.各种不同数量级的时间复杂度的增长率比较（P14）第二章线性表§2.1 线性表及其逻辑结构1.线性表的定义2.线性表有哪些基本运算？§2.2 线性表的顺序存储结构1.清楚顺序表的类型定义：SqList2.顺序表的各种基本算法。

3.算法（例2.3，例2.4，练习题2.2）§2.3 线性表的链式存储结构1.清楚单链表的类型定义：LinkList2.单链表的各种基本算法3.算法（例2.5，例2.6，练习题2.3 ）4.清楚双链表的类型定义：DLinkList5.双链表的算法（其各种基本算法，例2.7，习题2.4）6.循环链表的算法（例2.9，例2.10，习题2.5）§2.5 有序表例2.11第三章栈和队列§3.1 栈1.什么是栈？栈的特点是什么？栈有哪些基本运算？（例3.1、例3.2）2.栈的顺序存储结构---SqStack, 其基本运算的算法。

3.栈的链式存储结构（不考）4.练习题3.1，3.2，例3.4，例3.5§3.2 队列1. 什么是队列？队列的特点是什么？队列有哪些基本运算？（例3.6）2. 队列的顺序存储结构的定义---SqQueue。

3. 循环顺序队列的判断空队列和满队列的条件各是什么？如何求队列长度？4. 循环顺序队列的基本算法。

如：入队列算法enqueue，出队列算法dequeue，等，习题3.4，3.55. 队列的链式存储（不考）第四章串§4.1 串的基本概念1. 串的定义。

数据结构习题集（自编）第一章绪论一、选择题1．数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。

A．结构B．关系 C．运算 D．算法2．在数据结构中，从逻辑上可以把数据结构分成（）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．逻辑结构和存储结构3．线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。

A．正确B．不正确 C．无法确定 D．以上答案都不对4．算法分析的目的是（）。

A．找出算法的合理性 B．研究算法的输人与输出关系C．分析算法的有效性以求改进 D．分析算法的易懂性5. 算法的时间复杂度取决于（）A．问题的规模B待处理数据的初态 C. A和B6．一个算法应该是（）。

A．程序B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.7. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的8．以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈9．在下面的程序段中，对x的赋值语句的频度为（）for（i=0;i<n;i++）for(j=0;j<n;j++)x=x+1;nA． 2n B．n C．n2 D．log210．以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队列 D．栈11. 下列数据中，（）是线性数据结构。

A．哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈12．以下属于逻辑结构的是（）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表二、填空题1、_______是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，________是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。

（数据、数据）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)第⼀章绪论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 ）。

数据结构复习题及答案数据结构复习题及答案数据结构是计算机科学中的重要基础，它涉及到存储、组织和管理数据的方法和技术。

在学习数据结构的过程中，我们经常会遇到各种复习题，通过解答这些题目可以巩固对数据结构的理解和掌握。

本文将给出一些常见的数据结构复习题及其答案，希望对读者的学习有所帮助。

一、数组1. 给定一个整数数组，如何找到数组中的最大值和最小值？答案：可以使用遍历数组的方式，依次比较每个元素与当前的最大值和最小值，更新最大值和最小值即可。

2. 给定一个整数数组和一个目标值，如何判断数组中是否存在两个数的和等于目标值？答案：可以使用两层循环遍历数组，依次判断每两个数的和是否等于目标值。

二、链表1. 如何反转一个单链表？答案：可以使用三个指针prev、curr和next，分别表示当前节点的前一个节点、当前节点和当前节点的下一个节点。

通过遍历链表，每次将当前节点的next指针指向prev节点，然后更新prev、curr和next指针，直到遍历到链表的末尾。

2. 如何判断一个链表是否有环？答案：可以使用快慢指针的方法。

定义两个指针slow和fast，初始时都指向链表的头节点。

slow指针每次移动一步，fast指针每次移动两步。

如果链表中存在环，那么两个指针最终会相遇；如果链表中不存在环，那么fast指针会先到达链表的末尾。

三、栈和队列1. 如何使用栈实现队列？答案：可以使用两个栈来实现队列。

一个栈用来存储入队的元素，另一个栈用来存储出队的元素。

当需要入队时，直接将元素压入第一个栈；当需要出队时，如果第二个栈为空，则将第一个栈中的元素依次弹出并压入第二个栈，然后从第二个栈中弹出元素；如果第二个栈不为空，则直接从第二个栈中弹出元素。

2. 如何使用队列实现栈？答案：可以使用两个队列来实现栈。

一个队列用来存储元素，另一个队列用来辅助操作。

当需要入栈时，直接将元素入队；当需要出栈时，将队列中的元素依次出队并入辅助队列，直到队列中只剩下一个元素，然后将该元素出队；然后交换两个队列的角色，使得辅助队列成为主队列，主队列成为辅助队列。

数据结构复习题(附答案)数据结构复习题(附答案)数据结构是计算机科学中非常重要的一门课程，其涉及到对数据的组织、存储和管理方法的研究。

在学习数据结构的过程中，我们通常需要进行大量的练习和复习以加深对各种数据结构和算法的理解。

本文将为大家提供一些数据结构的复习题，并附有详细的答案解析。

一、栈和队列1. 给定一个字符串，判断其中的括号序列是否合法。

例如，"{([])}"是合法的括号序列，而"{[)]}"则是非法的。

答案：使用栈的数据结构可以很方便地解决这个问题。

遍历字符串，遇到左括号就将其入栈，遇到右括号就判断对应的左括号是否与栈顶元素相匹配，如果匹配则将栈顶元素出栈，继续比较下一个字符。

最后，栈为空则表示括号序列合法。

2. 设计一个队列，实现队列的基本操作：入队、出队、获取队头元素和判断队列是否为空。

答案：可以使用一个数组来实现队列，使用两个指针front和rear分别指示队头和队尾的位置。

入队操作时，将元素添加到rear指向的位置，并将rear后移一位；出队操作时，将front后移一位；获取队头元素时，返回front指向的位置的元素；判断队列是否为空可以通过比较front和rear来确定。

3. 反转一个单链表。

答案：使用三个指针prev、curr和next来实现链表的反转。

初始时，将prev指向null，curr指向头节点，next指向curr的下一个节点。

然后，将curr的next指向prev，将prev指向curr，将curr指向next，再将next指向next的下一个节点。

重复这个操作，直到链表反转完成。

4. 判断一个单链表中是否存在环。

答案：使用快慢指针的方法可以判断一个单链表中是否存在环。

如果存在环，那么快指针最终会追上慢指针；如果不存在环，那么快指针最终会达到链表的末尾。

三、树和图5. 给定一个二叉树，编写一个算法来判断它是否是平衡二叉树。

答案：平衡二叉树的定义是指二叉树的每个节点的左子树和右子树的高度差不超过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 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

一、选择题。

(每小题分，共分)() 计算机识别.存储和加工处理的对象被统称为。

.数据 .数据元素.数据结构 .数据类型() 数据结构通常是研究数据的及它们之间的联系。

.存储和逻辑结构 .存储和抽象.理想和抽象 .理想与逻辑() 不是数据的逻辑结构是。

.散列结构 .线性结构.树结构 .图结构() 数据结构被形式地定义为<>,其中是的有限集，是的有限集。

.算法 .数据元素.数据操作 .逻辑结构() 组成数据的基本单位是。

.数据项 .数据类型.数据元素 .数据变量() 设数据结构(，)，其中{，，，}，{}，{<，>，<，>，<，>，<，>}，则数据结构是。

.线性结构 .树型结构.图型结构 .集合() 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为。

.存储结构 .逻辑结构.顺序存储结构 .链式存储结构() 在数据结构的讨论中把数据结构从逻辑上分为。

.内部结构与外部结构 .静态结构与动态结构.线性结构与非线性结构 .紧凑结构与非紧凑结构() 对一个算法的评价，不包括如下方面的内容。

.健壮性和可读性 .并行性.正确性 .时空复杂度() 算法分析的两个方面是。

.空间复杂性和时间复杂性 .正确性和简明性.可读性和文档性 .数据复杂性和程序复杂性() 线性表是具有个的有限序列（≠)。

.表元素.字符.数据元素 .数据项() 线性表的存储结构是一种的存储结构。

.随机存取 .顺序存取.索引存取存取() 在一个长度为的顺序表中，向第个元素（≤≤＋１）之前插入一个新元素时，需要向后移动个元素。

() 链表是一种采用存储结构存储的线性表；.顺序 .链式.星式 .网状() 下面关于线性表的叙述错误的是。

.线性表采用顺序存储必须占用一片连续的存储空间.线性表采用链式存储不必占用一片连续的存储空间.线性表采用链式存储便于插入和删除操作的实现.线性表采用顺序存储便于插入和删除操作的实现() 设指针指向单链表中结点，指针指向单链表中结点的后继结点，指针指向被插入的结点，则在结点和结点之间插入结点的操作序列为。

一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

A.表元素B.字符C.数据元素D.数据项(12) 线性表的存储结构是一种____ B ____的存储结构。

北京师范大学2013-2014学年第1学期期末考试试卷（A卷）课程名称：数据结构任课教师姓名: 郑新肖永康卷面总分：100分考试时长：100分钟考试类别：闭卷0开卷口其他口院（系）：专业：年级：姓名：学号：阅卷教师（签字）： ______________________一、选择题（每小题2分，共20分）1.算法分析的目的是（）。

A.研究算法的输入与输出Z间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2.与双向链表相比较，单向链表的缺点之一是（）。

A.无法省略头结点指针B.插入和删除操作麻烦C.无法进行随机访问D.占用更大的存储空间3.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为：p->rlink=q; p->llink=q->llink; q->llink=p 和（）。

A. q->rlink=pB. q-Allink-ArlinkrpC・ p->llink->rlink=p D. p->rlink->rlink=p4.一个以整数为栈元素的栈，若元素的进栈顺序为1, 2, 3, 4, 5,出栈可以发生在任何时刻。

则下面的序列中，（）是可能的出栈序列。

A. 2,5,4,1,3B. 3丄4,2,5C. 5,4,3丄2D. 2,3,1,5,45.n个结点的线索二叉树上，含有的线索数为（）。

A・2n B・n・l C・n+1 D・n6.已知某非空二叉树采用顺序存储结构，树屮结点的数据信息依次存放在一个一维数组中，该二叉树的中序遍历系列为（）A. GDBAFHCEB. GBDAFHCEC. BDGAFHCED. BGDAFHCE7.以下序列不是堆的是( )oA.(100,85,98,77,80,60,82,40,20,10,66)B.(100,98,85,82,80,77,66,60,40,20,10)C.(10,20,40,60,66,77,80,82,85,98,100)D.(100,85,40,77,80,60,66,98,82,10,20)&导致图的遍历序列不唯一的因素有（）。

线 订 装数据结构与算法A卷答案12-13学年第一学期一、选择题：（本题共20小题，每题2分，共40分）1-5：AABDC 6-10：DDDBC 11-15：CBCDD 16-20：ABCAB二、分析运算题（本题共6小题，每题5分，共30 分）(1) 如果输入序列为1 2 3,先进入栈结构后进入队列结构，试写出所有的出队列序列。

输出序列1 2 3（1分）输出序列1 3 2（1分）输出序列2 1 3（1分）输出序列2 3 1（1分）输出序列3 2 1（1分）输出序列3 1 2（扣3分）(2) 假设一棵二叉树的前序(先序)遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。

①（3分）②后序遍历：DEBFCA （2分）(3) 用二叉树表示算术表达式如图1所示。

①按图画出对应的算术表达式②写出后序（后缀）表达式算术表达式：(a+b+c*(d+e)+f)*(g+h) （2分）后序表达式：ab+cde+*+f+gh+*（3分）(4) 请写出有向图2中顶点1-6的入度和出度1: 入度：3出度：02: 入度：2出度：23: 入度：1出度：24: 入度：1出度：35: 入度：2出度：16: 入度：2出度：3(入度2.5分，出度2.5分)(5) 给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman(赫夫曼) 树。

给定项及相应的权如下表：画出相应的huffman树。

(5分)(6)已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点1-6画出该图。

有向图（2分）三、程序填空题（本题共5空，每空2分，共10分）(1)：p!=NULL(2)：p = p->next;(3): Q.front= =Q.rear(4): Q.front->next=p->next;(5): Q.rear=Qfront;四、算法设计题（本题共2小题，共20分）1、（10分）算法如下：void move(sqlist L){int i=0,j=L.lenght-1,k; 1分int temp;while(i<j) 1分{while(L.elem[i]<=0) i++; 2分while(L.elem[j]>=0) j--; 2分if(i<j) 1分{temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp; 3分}}}注：算法执行次数（时间）比给定算法更多，不得超过6分。

国家二级公共基础知识（数据结构与算法）模拟试卷12(题后含答案及解析)题型有：1. 选择题选择题下列各题A、B、C、D四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上。

1．下列与队列结构有关联的是A．函数的递归调用B．数组元素的引用C．多重循环的执行D．先到先服务的作业调度正确答案：D解析：队列中最先插入的元素将最先被删除，最后插入的元素将最后被删除。

知识模块：数据结构与算法2．下列叙述中正确的是A．循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B．循环队列中的元素个数随队头指针的变化而动态变化C．循环队列中的元素个数随队尾指针的变化而动态变化D．循环队列中的元素个数不会变化正确答案：A解析：所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上，形成逻辑上的环状空间，循环使用。

在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向队头元素的前一个位置，因此，队列中的元素数等于从队头指针front指向的后一个位置与队尾指针rear指向位置之间的元素数量。

知识模块：数据结构与算法3．下列关于线性链表的叙述中，正确的是A．各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B．各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C．进行插入与删除时，不需要移动表中的元素D．以上都不正确正确答案：C解析：线性表的链式存储结构称为线性链表。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

知识模块：数据结构与算法4．下列叙述中正确的是A．线性表链式存储结构的存储空间一般要少于顺序存储结构B．线性表链式存储结构与顺序存储结构的存储空间都是连续的C．线性表链式存储结构的存储空间可以是连续的，也可以是不连续的D．以上都不正确正确答案：C解析：线性表的存储分为顺序存储和链式存储。

一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

A.表元素B.字符C.数据元素D.数据项(12) 线性表的存储结构是一种____ B ____的存储结构。

2013—2014学年第一学期闽江学院考试试卷《数据结构与算法》A 卷参考答案及评分标准一、选择题答案（每题2分） 30%二、填空题（每空 2分） 20% 1、p->nexts 2、53、1+n2+2n3+…+(k-1)nk4、n-1 n+15、CDBGFEA6、2n-17、A[7]、A[3]、A[5]、A[4] 8、2e三、判断题（每题1分） 10%四、应用题（5小题） 32 %1、（6分）画哈夫曼树（每个叶子结点位置正确得0.5分，总5分） 计算WPL 正确得1分WPL=(2+4)*5+(5+7+8)*4+(9+10+15+18)*3+22*2=30+80+156+44=3102、（8分）(1)二叉排序树 (每个结点在正确的位置正确得0.5分，总6分)(2)查找成功时的平均查找长度： （总2分） ASL=(1*1+2*2+4*3+5*4)/12 =37/12= 3.083、（5分）（每行正确得0.5分，总5分） 原始数据：（27），10，21，37，9，55，16，61，103，2 第一趟后:（10，27），21，37，9，55，16，61，103，2 第二趟后:（10，21，27），37，9，55，16，61，103，2 第三趟后:（10，21，27，37），9，55，16，61，103，2 第四趟后:（9，10，21，27，37），55，16，61，103，2第五趟后:（9，10，21，27，37，55），16，61，103，2 第六趟后:（9，10，16，21，27，37，55），61，103，2 第七趟后:（9，10，16，21，27，37，55，61），103，2 第八趟后:（9，10，16，21，27，37，55，61，103），2 第九趟后:（2，9，10，16，21，27，37，55，61，103） 4、（5分）哈希表，每个表结点在正确的位置得0.5分，计4分；查找成功时的平均查找长ASL 成功=（1*6+2*1+3*1）/8=11/8=1.3625 (1分) 5、（8分）得分标准：每个结点的邻接点均正确得0.5分（即每行0.5分）克鲁斯卡尔算法画出最小生成树的过程（4分）：（1） （2）（3）（4）（5）（6）（7）（8）得分标准：依次得出上面八张图，每张0.5分，计4分，其中第（4）、（5）张，第（6）、（7）张两权值相同的边顺序可调换。

算法是一组严谨地定义运算顺序地规则算法地基本要素一是对数据对象地运算和操作，二是算法地控制结构算法设计基本方法列举法、归纳法、递推、递归、减半递推算法地复杂度包括时间复杂度和空间复杂度时间复杂度执行算法所需地计算工作量空间复杂度执行算法所需地内存空间数据结构相互有关联地数据元素地集合.如春、夏、秋、冬；、、、、...；父亲、儿子、女儿等都是数据元素.前件数据元素之间地关系，如父亲是儿子和女儿地前件后件如儿子是父亲地后件结构指数据元素之间地前后件关系数据地逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中地存储位置无关数据地存储结构（物理结构）数据地逻辑结构在计算机存储空间中地存放形式，数据元素在计算机存储空间地位置关系可能与逻辑关系不同.根据数据结构中各数据元素之间前后件关系地复杂程度，可将数据结构分两类线性结构与非线性结构线性结构（线性表）满足下列两个条件（）有且只有一个根结点（）每一个结点最多有一个前件和后件.则称该数据结构为线性结构，否则为非线性结构.线性表是最简单、最常用地一种数据结构，其数据元素之间地相对位置是线性地，其存储方式为顺序存储地，如数组栈是限定在一端进行插入与删除地线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈地运算有入栈、退栈、读栈顶元素队列是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）地线性表，其操作规则是“先进先出”，其运算有入队和退队.树是一种简单地非线性结构，而且是层次结构，是倒立地大树，有根结点、父结点、子结点、叶子结点.根结点在第一层，一个结点所拥有地后件地个数称为该结点地度，所有结点中最大地度称为树地度，树地最大层次称为树地深度.二叉树（）非空二叉树只有一个根结点（）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式.二叉树性质（）层上最多有（）个结点（）深度为地二叉树最多有个结点（）度为地结点（叶子结点）比度为地结点多一个（）具有个结点地二叉树，其深度至少为[]，其中[]表示对取整满二叉树除最后一层外，其余层地结点都有两个子结点完全二叉树除最后一层外，每一层上地结点数均达到最大值，在最后一层上只缺少右边地若干结点，叶子结点只可能在层次最大地两层上出现.满二叉树是完全二叉树，而完全二叉树不是满二叉树.完全二叉树有两个性质：（）具有个结点地完全二叉树地深度为[]（）二叉树遍历不重复地访问各个结点.分为前序遍历(根左右)、中序遍历(左根右)和后序遍历（左右根）查找技术顺序查找——对于长度为地有序线性表，查找时需要比较次二分法查找——对于长度为地有序线性表，查找时需要比较次排序技术假设线性表地长度为，则冒泡排序和简单插入排序地比较次数（时间复杂度）为();希尔排序地比较次数为();简单选择排序地比较次数为();堆排序地比较次数为().习题算法地时间复杂度是指（），算法地空间复杂度是指（）；队列是（先进先出），栈是（先进后出）；下列二叉树地遍历结果：前序遍历（）、中序遍历（）、后续遍历（）；在深度为地满二叉树中，叶子结点地个数为（）；设树地度为，其中度为，，；线性表、栈、队列、线性链表是（线性结构），树是（非线性结构）；数据地存储结构是指（）；，地结点地个数分别为，，，.则中地叶子结点地个数为（）；对于长度为地有序线性表，顺序查找次数为（）,二分法查找次数为（）；一棵完全二叉树共有个结点，则在该二叉树中有（）个叶子结点；一棵二叉树地中序遍历结果为，前序遍历结果为，则后续遍历结果为（）；冒泡排序地时间复杂度为（()）;在一个容量为地循环队列中，若头指针,尾指针,则该循环队列中共有（）元素；。

数据结构试题及答案试题1.请说明数据结构的定义和作用。

2.请列举数据结构的分类，并简要描述每种分类的特点。

3.请解释什么是线性数据结构，并举例说明。

4.请解释什么是非线性数据结构，并举例说明。

5.请简述栈和队列的特点，并提供实际应用场景。

6.请说明二叉树的定义，并解释二叉树的遍历方式。

7.请解释什么是图数据结构，并提供图的应用场景。

8.请解释什么是散列表，并解释散列表的应用场景。

9.请说明堆数据结构的定义和特点。

10.请解释什么是哈希表，并提供哈希表的应用场景。

答案1.数据结构的定义和作用数据结构是一种组织和存储数据的方式，它定义了数据之间的关系和操作。

数据结构的作用是为了有效地管理和处理大量数据，并提高程序的执行效率和内存利用率。

2.数据结构的分类及特点–线性数据结构：线性数据结构是数据元素之间存在一对一的关系，数据元素之间只能以线性的方式连接。

例如：数组、链表、栈、队列等。

线性数据结构的特点是：数据元素之间具有顺序关系，可以实现快速的查找和插入，但插入和删除操作可能导致大量元素的移动。

–非线性数据结构：非线性数据结构是数据元素之间存在一对多或多对多的关系，数据元素之间可以以任意非线性连接方式组织。

例如：树、图等。

非线性数据结构的特点是：数据元素之间不存在固定的顺序关系，可以更灵活地表示数据之间的关系，但查找和插入的效率可能较低。

3.线性数据结构的例子线性数据结构的一个例子是数组。

数组是一种连续存储数据的结构，每个元素占据相同的大小。

数组的元素通过索引访问，索引从0开始。

例如，一个整型数组可以表示一组整数，可以通过索引快速访问和修改数组中的元素。

4.非线性数据结构的例子非线性数据结构的一个例子是树。

树是一种分层存储数据的结构，包含一个根节点和若干个子节点。

每个节点可以有多个子节点，但只能有一个父节点。

例如，二叉树是一种特殊的树，每个节点最多有两个子节点。

5.栈和队列的特点及应用场景–栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。

《数据结构》复习题及参考答案数据结构复习题及参考答案1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它涉及到数据的组织方式、存储方式、访问方式以及对数据进行操作的算法等。

数据结构的选择对于解决不同类型的问题非常重要。

2. 数据结构有哪些常见的分类？数据结构可以分为以下几类：(1) 线性结构：线性结构是一种有序排列的数据结构，其中数据元素之间存在着一对一的关系。

常见的线性结构有数组、链表、栈和队列等。

(2) 非线性结构：非线性结构是一种数据元素之间存在多对多关系的结构，常见的非线性结构有树和图等。

(3) 逻辑结构：逻辑结构是指数据元素之间的逻辑关系，主要包括集合结构、线性结构、树形结构和图形结构等。

(4) 物理结构：物理结构是指数据的逻辑结构在计算机存储中的表示方式，主要包括顺序存储结构和链式存储结构等。

3. 什么是算法？算法是解决特定问题的一系列步骤或操作的有限序列。

一个算法通常包括输入、输出、基本操作、控制结构和定义算法执行的约定等。

4. 数据结构和算法之间的关系是什么？数据结构是算法的基础，而算法又依赖于数据结构。

只有选择合适的数据结构，才能实现高效的算法。

同时，算法的设计也会对数据结构的选择产生影响。

5. 请解释什么是时间复杂度和空间复杂度？时间复杂度是衡量算法执行时间消耗的度量，表示算法的运行时间与问题规模之间的关系。

通常用大O符号来表示时间复杂度，如O(n)、O(nlogn)等。

空间复杂度是衡量算法执行所需存储空间的度量，表示算法所需的额外空间与问题规模之间的关系。

同样也使用大O符号来表示，如O(1)、O(n)等。

6. 请简要描述以下数据结构的特点及应用场景：(1) 数组：数组是一种连续存储数据元素的线性结构，具有随机访问性能。

适用于知道元素位置的查找和修改操作。

(2) 链表：链表是一种通过指针连接的数据结构，具有插入、删除元素方便的特点。

适用于频繁插入、删除操作以及不知道具体位置的查找操作。