湖南大学数据结构期末复习

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

2022年湖南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、已知有向图G=(V，E)，其中V={V1，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，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、下列关于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）简答题6题*5分=30分简要回答要点（2）分析题6题*5分=30分给出结果（3）设计题1题*10分=10分设计思想及结果（4）编程题1题*10分=10分完整代码（5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度}考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构）二、非线性表（集合-树-图）}2.抽象数据类型数据对象-数据关系-基本操作3.算法性质-要求（设计）-效率（度量）4.实例查找：高效查找算法排序：高效的排序算法分析题考试题目参考（1）1-2-3-4-5-6顺序建BBST（2）6-5-4-3-2-1顺序建BBST简答题实例设计题：（1）（2）数据结构试卷（一）三、计算题（每题 6 分，共24分）1. 在如下数组A 中存储了一个线性表，表头指针为A [0].next ，试写出该线性表。

A 0 1 2 3 4 5 6 7data 60 50 78 90 34 40 next357241线性表为：（78，50，40，60，34，90）⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0111010*******110101011102.请画出下图的邻接矩阵和邻接表。

3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

用克鲁斯卡尔算法得到的最小生成树为：(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。

湖南大学课程考试试卷课程名称：数字电路与逻辑设计；试卷编号：；考试时间：120分钟一、填空题（每空2分，共10分）1、(39.75 )10= ( )162、ASIC可分为（）,（）和可编程ASIC(Programmable ASIC).3、数字系统分为以下六个层次：系统级、（）、逻辑单元级、逻辑门级、（）、硅片级。

二、单选题（在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题末的括号内。

多选不给分。

每题2分，共10分）1、函数的最简式为（）。

① 1 ② 0 ③④2、一个四位二进制码减法计数器的起始值为1001，经过100个时钟脉冲作用之后的值为（）。

① 1100 ② 0100 ③ 1101 ④ 01013、下列各函数等式中无冒险现象的函数式有（）。

①②③④4、用四选一数据选择器实现函数Y= A1A0+A1’A0，应使（）。

①D0=D2=0，D1=D3=1 ②D0=D2=1，D1=D3=0③D0=D1=0，D2=D3=1 ④D0=D1=1，D2=D3=05、T触发器Q端的输出信号频率是输入信号频率的（）倍。

① 1 ② 1/2 ③ 2 ④ 1/4三、判断题（下列各题，你认为正确的，请在题末的括号内打“√”，错的打“×”，并更正。

每题2分，共10分）1、不用的CMOS输入端绝不能悬空。

（）2、对逻辑函数Y=A B’+A’B+B’C+B C’利用代入规则，令A=BC代入，得Y= BC B’+（BC）’B+B’C+B C’=B’C+B C’成立。

（）3、处于三态输出的高阻态，因输出没和电路连上，所以输出端没有电流。

（）4、由两个或非门构成的基本R S触发器，当R=S=0时，触发器的状态为不定。

（）5、优先编码器的编码输入信号是相互排斥的，不允许有多个编码信号同时有效。

（）四、简答题（任选2题，每题5分，共10分）:1、格雷码和奇偶校验码的特点分别是什么？为什么说它们是可靠性编码？2、简述双稳态元件的亚稳定性概念及特点。

《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。

答案：线性表2. 队列是一种先进先出（____）的数据结构。

答案：线性表3. 链表是一种____数据结构，由一系列节点组成。

答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。

答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。

答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。

（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。

（）答案：错误3. 图是一种线性结构。

（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。

（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。

（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。

答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。

队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。

2. 请简述链表的优缺点。

答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。

缺点包括占用内存空间较大、不如数组支持随机访问。

第一章概论1。

数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算2。

数据的逻辑结构是从具体问题抽象出来的数学模型,反映了事物的组成结构及事物之间的逻辑关系可以用一组数据（结点集合K）以及这些数据之间的一组二元关系(关系集合R）来表示：(K, R)结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系3.数据类型a。

基本数据类型整数类型（integer）、实数类型(real)、布尔类型（boolean）、字符类型（char）、指针类型（pointer）b。

复合数据类型复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型4.数据结构的分类：线性结构（一对一)、树型结构（一对多)、图结构（多对多)5。

四种基本存储映射方法：顺序、链接、索引、散列6。

算法的特性：通用性、有效性、确定性、有穷性7.算法分析:目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化8.渐进算法分析a．大Ο分析法：上限，表明最坏情况b．Ω分析法：下限，表明最好情况c．Θ分析法：当上限和下限相同时，表明平均情况第二章线性表1.线性结构的基本特征a.集合中必存在唯一的一个“第一元素”b。

集合中必存在唯一的一个“最后元素"c.除最后元素之外,均有唯一的后继d。

除第一元素之外,均有唯一的前驱2.线性结构的基本特点：均匀性、有序性3。

顺序表a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中,每一个元素唯一的索引值；使用常数作为向量长度b。

线性表中任意元素的存储位置：Loc（ki）= Loc(k0）+ i * L（设每个元素需占用L个存储单元）c. 线性表的优缺点:优点：逻辑结构与存储结构一致;属于随机存取方式，即查找每个元素所花时间基本一样缺点：空间难以扩充d.检索：ASL=【Ο（1）】e。

数据结构期末考试试题及答案一、选择题1. 以下哪种数据结构是线性存储结构？A. 树B. 图C. 链表D. 哈希表答案：C2. 在二叉搜索树中，若删除一个节点，则需要进行以下哪些操作？A. 仅删除操作B. 删除操作和调整树结构操作C. 插入操作D. 忽略操作答案：B3. 快速排序算法的时间复杂度在最坏情况下是：A. O(log n)B. O(n)C. O(n log n)D. O(n^2)答案：D4. 下面哪个排序算法适用于大数据量的排序？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：D5. 哈夫曼树是一种特殊的：A. 二叉树B. 多叉树C. 哈希表D. 图答案：A二、填空题1. 链表的基本操作包括__________、__________、__________和__________。

答案：创建、插入、删除、查找2. 栈是一种后进先出（LIFO）的数据结构，其添加元素的操作称为__________，移除元素的操作称为__________。

答案：push、pop3. 在图的遍历算法中，按照遍历方向的不同，可以分为__________和__________。

答案：深度优先遍历、广度优先遍历4. 红黑树是一种自平衡的__________。

答案：二叉搜索树4. 散列表（哈希表）的主要优点是__________。

答案：查找速度快三、简答题1. 请简述数组和链表的区别及各自的优缺点。

答案：数组是一种顺序存储结构，通过索引直接访问元素，访问速度快，但是插入和删除操作需要移动大量元素，效率较低。

链表是一种非顺序存储结构，通过指针连接元素，插入和删除操作只需要改变指针，效率较高，但是访问元素需要从头开始遍历，速度较慢。

2. 请解释二分查找法的工作原理及其适用条件。

答案：二分查找法是一种在有序数组中查找特定元素的算法。

工作原理是将数组分为两部分，判断目标值与中间元素的大小关系，然后在相应的一半中继续查找，重复此过程，直到找到目标值或范围缩小到无法再分。

期末考试重点复习资料二、考试重点内容第一章绪论1、时间复杂度和空间复杂度的计算。

要求能够计算出程序的执行次数。

2、各种概念：数据结构、数据项、数据元素第二章线性表1、单链表的各种操作，包括单链表的建立、插入、删除结点的操作语句序列2、单链表（带头结点、不带头结点、循环单链表）的逆置运算。

3、双链表的插入和删除操作语句序列。

4、单链表的直接插入排序运算。

5、静态单链表的插入和删除操作。

6、二个有序单链表的合并、一个单链表拆分为多个单链表第三章栈和队列1、栈的输入序列和输出序列、递归函数的输出结果2、循环队列的入队、出队操作以及有效元素个数的计算第四章串1、KMP算法中的next和nextval值的计算第五章数组和广义表1、二维数组任意元素地址的计算2、稀疏矩阵的转置算法3、广义表的两个操作函数：取表头和表尾第六章树和二叉树1、二叉树的性质（特别是完全二叉树的性质，例如求完全二叉树的深度等）2、二叉树的遍历（特别是中序和先序遍历，要求能够使用堆栈完成非递归遍历编程和递归算法编程，在遍历基础上的各种操作，例如求二叉树的叶子数、二叉树结点数等操作，包括有编程算法和编程填空题）3、线索二叉树（特别是中序线索化二叉树和中序线索化二叉树的中序遍历，包括编程算法和编程填空题，希望大家着重研究）4、哈夫曼编码（主要是应用题，包括哈夫曼的编码与解码，也包括哈夫曼树的特点）5、树与森林在转化成二叉树时，左右子树的结点数有何特点）6、树的层次遍历（使用队列完成、借助树的层次遍历可以判断二叉树是否为完全二叉树）、判断二叉树是否为排序二叉树等，可能有编程题或编程填空题）补充：二叉树的物理存储结构（链式和顺序存储）*第七章图1、图的两种物理存储方式（邻接矩阵与邻接表存储表示）2、图的生成树与最小生成树（生成树特点）、图的遍历3、求最小生成树的两种算法（重点是PRIM 算法，特别会写出用PRIM算法求最小生成树的过程）4、使用迪杰斯特拉算法求单源最短路径，写出求解过程5、拓扑排序6、求关键路径，要求写出事件和活动的最早和最晚开始时间，深刻理解关键路径的含义。

数据结构期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是（）。

A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一对关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是（）。

A. 只能在一端进行插入和删除操作B. 只能在一端进行插入操作，另一端进行删除操作C. 两端都可以进行插入和删除操作D. 只能在一端进行删除操作答案：B3. 在二叉树中，若某结点的左子树非空，则其左子树中任一结点的值（）。

A. 小于该结点的值B. 大于该结点的值C. 等于该结点的值D. 与该结点的值无关答案：A4. 哈希表的冲突解决方法中，开放定址法的基本思想是（）。

A. 将发生冲突的元素插入到表的末尾B. 将发生冲突的元素插入到表的首部C. 将发生冲突的元素插入到表的任意位置D. 将发生冲突的元素插入到表的下一个空位答案：D5. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(nlogn)B. O(n^2)C. O(n)D. O(1)答案：B6. 归并排序算法的时间复杂度是（）。

A. O(nlogn)B. O(n^2)C. O(n)D. O(1)答案：A7. 在图的遍历中，深度优先搜索（DFS）使用的是（）。

A. 队列B. 栈C. 链表D. 数组答案：B8. 广度优先搜索（BFS）使用的是（）。

A. 队列B. 栈C. 链表D. 数组答案：A9. 在图的表示方法中，邻接矩阵适用于表示（）。

A. 稀疏图B. 稠密图C. 无向图D. 有向图答案：B10. 最小生成树的Kruskal算法中，边的选取是基于（）。

A. 边的权重B. 边的编号C. 边的长度D. 边的类型答案：A二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的空间复杂度是指算法执行过程中需要的___________。

答案：存储空间的大小2. 顺序表的存储结构是使用___________连续的存储单元依次存储数据元素。

{ x=(a[j]/m)%r; //取a[j]的第i位排序码cnt[x]++;}for (j=1; j<r; j++) cnt[j]=cnt[j-1]+cnt[j];for (j=n-1; j>0; j--) b[ ]=a[j];for(j=0; j<n; j++) //将临时数组b 中的内容复制到a 中;m= ;}}三、应用题。

（35分）1、将两个栈存入一个数组V[n]中，如何存放比较合理？为什么？此时栈空和栈满的条件分别是什么？2、用序列（46，88，45，39，70，58，101，10，66，34）建立一个二叉查找树，画出该树，并求在等概率情况下查找成功的平均查找长度。

3、对于下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树。

4、设一个散列表包含13个表项,.其下标从0到12,采用线性探查法解决冲突（p（K，i)＝i），请按以下要求,将下列关键码按从左到右的顺序散列到表中。

10，100，32，45，58，126，3，29，200，400，0散列函数采用除留余数法,用%SIZE（对表长取余运算）将各关键码映像到表中.，请指出每一个产生冲突的关键码可能产生多少次冲突？5、一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗，为什么？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。

6、假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。

它们在电文中出现的幅度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04},为这7个字母统计哈夫曼编码，并计算其平均编码长度。

1.从执行程序的角度看，并行性等级从低到高分为那几级？从执行程序的角度看，并行性等级从低到高可分为：（1）指令内部并行：单条指令中各微操作之间的并行。

（2）指令级并行（Instruction Level Parallelism，ILP）：并行执行两条或两条以上的指令。

（3）线程级并行（Thread Level Parallelism，TLP）：并行执行两个或两个以上的线程，通常是以一个进程内派生的多个线程为调度单位。

（4）任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段），以子程序或进程为调度单元。

（5）作业或程序级并行：并行执行两个或两个以上的作业或程序。

2.计算机中提高并行性的技术途径有哪三种？（1）时间重叠。

多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。

（2）资源重复。

通过重复设置资源，尤其是硬件资源，大幅度提高计算机系统的性能。

（3）资源共享。

这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备3.从当前计算机技术来看，CISC结构有什么缺点？（1）CISC结构的指令系统中，各种指令的使用频率相差悬殊。

（2）CISC结构指令系统的复杂性带来了计算机系统结构的复杂性，这不仅增加了研制时间和成本，而且还容易造成设计错误。

（3）CISC结构指令系统的复杂性给VLSI设计增加了很大负担，不利于单片集成。

（4）CISC结构的指令系统中，许多复杂指令需要很复杂的操作，因而运行速度慢。

（5）在CISC结构的指令系统中，由于各条指令的功能不均衡性，不利于采用先进的计算机系统结构技术来提高系统的性能。

4.根据Amdahl定律，系统加速比有哪两个因素决定？系统加速比依赖于两个因素：（1）可改进比例：可改进部分在原系统计算时间中所占的比例。

（2）部件加速比：可改进部分改进以后的性能提高。

5.从处理数据角度，并行性等级由低到高分为哪几级？从处理数据的角度来看，并行性等级从低到高可分为：（1）字串位串：每次只对一个字的一位进行处理。

数据结构期末考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一的关系B. 元素之间存在一对多的关系C. 元素之间存在多对多的关系D. 元素之间存在一对一或多对多的关系2. 栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任一位置进行插入和删除操作B. 只能在表的首端进行插入和删除操作C. 只能在表的末端进行插入和删除操作D. 插入和删除操作没有特定的限制3. 以下哪个算法是排序算法？A. 快速排序B. 深度优先搜索C. 广度优先搜索D. 二分查找4. 哈希表解决冲突的常用方法不包括：A. 开放寻址法B. 链地址法C. 二分查找法D. 再散列法5. 在图的遍历算法中，深度优先搜索（DFS）使用的是：A. 栈B. 队列C. 链表D. 树...（此处省略其他选择题）二、简答题（每题10分，共30分）1. 请简述二叉树的三种遍历方法及其特点。

2. 什么是平衡二叉树？请说明它与普通二叉树的区别。

3. 解释什么是图的邻接矩阵表示法和邻接表表示法，并比较它们的优缺点。

三、计算题（每题15分，共30分）1. 给定一个数组A[1...n]，请写出一个时间复杂度为O(n)的算法，找出数组中的最大值和最小值。

2. 假设有一个链表，链表中的节点按照值递增的顺序排列，请设计一个算法删除链表中所有重复的节点。

四、编程题（每题20分，共20分）1. 编写一个函数，实现二叉搜索树的插入操作，并保证树的平衡。

数据结构期末考试答案一、选择题1. C2. B3. A4. C5. A...（此处省略其他选择题答案）二、简答题1. 二叉树的三种遍历方法包括前序遍历、中序遍历和后序遍历。

前序遍历首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

中序遍历首先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

后序遍历首先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

数据结构期末考试复习试题(整理完的) 数据结构与算法》复题一、选择题1.数据结构可以从逻辑上分为线性结构和非线性结构。

2.数据结构在计算机内存中的表示是指数据的存储结构。

3.在数据结构中，与所使用的计算机无关的是数据的逻辑结构。

4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储数据元素之间的关系。

5.在决定选取何种存储结构时，一般不考虑各节点的值如何。

6.一些表面上很不相同的数据可以有相同的逻辑结构。

7.算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空间复杂度和时间复杂度。

8.下面程序段的时间复杂度是O(n²)。

s = 0;for (i = 0.i < n。

i++)for (j = 0.j < n。

j++)s += B[i][j];sum = s;9.下面程序段的时间复杂度是O(n*m)。

for (i = 0.i < n。

i++)for (j = 0.j < m。

j++)A[i][j] = 0;10.下面程序段的时间复杂度是O(log3n)。

i = 1;while (i <= n)i = i * 3;11.二维数组是其数据元素为线性表的线性表。

12.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致。

13.链表不具备的特点是可随机访问任一结点。

14.不带头结点的单链表head为空的判定条件是head == NULL。

15.带头结点的单链表head为空的判定条件是head->next == NULL。

16.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用带头结点的双循环链表存储方式最节省运算时间。

17.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是静态链表。

18.非空的循环单链表head的尾结点（由p所指向）满足p->next == head。

《数据结构》复习提纲一、基础知识 (2)二、应用 (5)三、算法 (5)四、题型及样题 (6)一、基础知识第1章绪论1．什么是数据结构，分类2．抽象数据类型的形式定义3．逻辑结构、物理结构（存储结构）4．时间复杂度第2章线性表、5．线性表的定义和术语6．线性表的存储结构✓顺序表✓链式表：线性链表（单链表）、循环链表、双向链表✓静态链表第3章栈和队列7．栈✓顺序栈✓链式栈8．队列✓顺序队列：循环队列✓链式队列第5章数组和广义表9．数组的特点10．数组的顺序表示11．二维数组的两种存储方式✓以列序为主序✓以行序为主序12．矩阵的压缩存储✓特殊矩阵✓稀疏矩阵（三元组表）13．广义表的定义✓表头，表尾✓表长，深度第6章树14．树的定义和术语15．二叉树的定义和术语16．满二叉树与完全二叉树17．二叉树的性质18．二叉树的存储✓顺序✓链式：二叉链表19．遍历二叉树✓先序遍历✓中序遍历✓后序遍历✓层次遍历20．线索、线索二叉树、线索链表✓LTag和Rtag的作用21．树的存储结构✓双亲表示法✓孩子表示法✓孩子兄弟表示法22．树与二叉树之间的转换23．树的遍历✓先根（对应二叉树的先序）✓后根（对应二叉树的中序）✓层次24．树的带权路径长度25．哈夫曼树（最优二叉树）26．前缀编码、哈夫曼编码第7章图27．图的定义和术语28．图的存储结构✓邻接矩阵✓邻接表29．图的遍历✓深度优先搜索（DFS，类似树的先根遍历）✓广度优先搜索（BFS，类似树的层次遍历）30．最小生成树：✓Prim算法✓Kruskal算法31．有向无环图32．AOV网和AOE网33．拓扑排序问题34．关键路径问题35．最短路径问题✓单源最短路径－Dijkstra算法✓多源最短路径－Floyd算法第9章查找36．静态查找表和动态查找表37．关键字、主关键字、次关键字38．平均查找长度39．静态查找表✓顺序表的查找✓有序表的查找：折半查找、折半查找判定树40．动态查找表✓二叉排序树✓平衡二叉树✓B树和B+树41．哈希函数、哈希地址、哈希表、冲突、同义词42．哈希函数的构造43．地址冲突的处理44．装填因子第10章内部排序45．排序方法的稳定性和时间复杂度46．插入排序✓直接插入排序✓希尔排序47．交换排序✓冒泡排序✓快速排序48．选择排序✓简单选择排序✓堆排序49．归并排序✓2-路归并排序50．基数排序二、应用1.分析简单程序段的时间复杂度2.利用栈进行表达式求值3.根据下标计算数组元素的存储位置4.求字符串的next值和nextval值。

《数据结构》复习资料一单选题 (共48题，总分值0分 )1. 设用链表作为栈的存储结构，则退栈操作（0 分）A. 必须判别栈是否为满B. 必须判别栈是否为空C. 判别栈元素的类型D. 对栈不作任何判别2. 下面关于m阶B树说法正确的是（）。

①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。

（0 分）A. ①②③B. ②③C. ②③④D. ③3. 下列关于文件的说法，错误的是（）。

（0 分）A. 选择文件的组织方式时应考虑外存的性质和容量B. 不定长文件指的是总长度可变的文件C. 对文件的操作主要是维护和检索D. 文件的存储结构指的是文件在外存上的组织方式4. 设无向图的顶点个数为n，则该图最多有（）条边。

（0 分）A. n-1B. n(n-1)/2C. n(n+1)/2D. n25. 设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。

（0 分）A. bB. cC. (c)D. (c,d,e)6. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

（0 分）A. 688B. 678C. 692D. 6967. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（0 分）A. nB. eC. 2nD. 2e8. 广义表(a,(b,(),c))的深度为（）。

（0 分）A. 1B. 2C. 3D. 49. 设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（）。

（0 分）A. 4条B. 5条C. 6条D. 无法确定10. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（0 分）A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，311. 具有n个顶点的有向强连通图最少有（）条弧。

第一章绪论一、数据结构包括：逻辑结构、存储结构、运算（操作）三方面内容。

二、线性结构特点是一对一。

树特点是一对多图特点是多对多三、数据结构的四种存储结构：顺序存储、链式存储、索引存储、散列存储顺序存储结构和链式存储结构的区别？线性结构的顺序存储结构是一种随机存取的存储结构。

线性结构的链式存储是一种顺序存取的存储结构。

逻辑结构分类：集合线性树图，各自的特点。

或者分为线性结构和非线性结构。

四、算法的特征P13五、时间复杂度(1) i=1; k=0;while(i<n){ k=k+10*i;i++;}分析：i=1; //1k=0; //1while(i<n) //n{ k=k+10*i; //n-1i++; //n-1}由以上列出的各语句的频度，可得该程序段的时间消耗：T(n)=1+1+n+(n-1)+(n-1)=3n可表示为T(n)=O(n)六、数据项和数据元素的概念。

第二章线性表一、线性表有两种存储结构：顺序存储和链式存储，各自的优、缺点。

二、线性表的特点。

三、顺序表的插入、思想、时间复杂度o(n)、理解算法中每条语句的含义。

（1）插入的条件：不管是静态实现还是动态实现，插入的过程都是从最后一个元素往后挪动，腾位置。

静态是利用数组实现，动态是利用指针实现。

不管静态还是动态，在表中第i个位置插入，移动次数都是n-i+1。

四、顺序表的删除、思想、时间复杂度o(n)、理解算法中每条语句的含义。

（1）删除的条件：不管是静态实现还是动态实现，删除的过程都是从被删元素的下一位置向前挪动。

静态是利用数组实现，动态是利用指针实现。

不管静态还是动态，删除表中第i个元素，移动次数都是n-i。

五、顺序表的优缺点？为什么要引入链表？答：顺序表的优点是可以随机存取，缺点是前提必须开辟连续的存储空间且在第一位置做插入和删除操作时，数据的移动量特别大。

如果有一个作业是100k，但是内存最大的连续存储空间是99K，那么这个作业就不能采用顺序存储方式，必须采用链式存储方式。