数据结构总复习

∑∑∑====n 1i n 1j 3n 1k n 162)1)(n n(n 21)n(n 2161)1)(2n n(n 21 i 21i 2121)i(i j 1n 1i n1i n 1i 2n 1i i 1j n 1i i 1j j 1k ++=++++==+=⎪⎭⎫ ⎝⎛+==∑∑∑∑∑∑∑∑========第一章 综合练习2.什么是数据结构? 有关数据结构的讨论涉及哪三个方面?【解答】数据结构是指数据以及相互之间的关系。

记为：数据结构 = { D, R }。

其中，D 是某一数据对象，R 是该对象中所有数据成员之间的关系的有限集合。

有关数据结构的讨论一般涉及以下三方面的内容：① 数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ② 数据成员及其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；③ 施加于该数据结构上的操作。

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。

因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。

数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。

数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。

例如搜索、插入、删除、更新、排序等。

5.设n 为正整数, 分析下列各程序段中加下划线的语句的程序步数。

(1) for (int i=1;i<=n ;i++)for (int j=1;j<=n ;j++){ c[i][j]=0.0;for (int k=1;k<=n ;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}(2) x=0; y=0;for (i=1;i<=n ;i++)for (j=1;j<=i ;j++)for (k=1;k<=j ;k++)x=x+y ;(3) i=1; j=1;while (i<=n&&j<=n){ i=i+1; j=j+i ; }(4) i=1;do {for (j=1;j<=n ;j++) i=i+j ;} while (i<100+n);【解答】(1) (2)n j 1n j 1n(n 1)x 1 i 1j 12n(n 1)n(n 1)n(n 1)n(n 1)x 2 i 1j 1122222==+==+=+++++⎛⎫⎛⎫⎛⎫==++=++=+ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭∑∑次数时，时，n j 1n(n 1)n(n 1)x 3, i 12j 1322=⎛+⎫+⎛⎫⎛⎫==++=+ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭∑时(3) i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1，i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4，……i = k 时，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，解出满足上述不等式的k 值，即为语句i = i + 1的程序步数。

数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

（）5．如果两个串含有相同的字符，则这两个串相等。

（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。

（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

（）9．一个广义表的表尾总是一个广义表。

（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

（）13．直接选择排序是一种稳定的排序方法。

（）14．闭散列法通常比开散列法时间效率更高。

（）15．有n个结点的不同的二叉树有n!棵。

（）16．直接选择排序是一种不稳定的排序方法。

（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

数据结构复习资料复习提纲知识要点归纳数据结构复习资料：复习提纲知识要点归纳一、数据结构概述1. 数据结构的定义和作用2. 常见的数据结构类型3. 数据结构与算法的关系二、线性结构1. 数组的概念及其特点2. 链表的概念及其分类3. 栈的定义和基本操作4. 队列的定义和基本操作三、树结构1. 树的基本概念及定义2. 二叉树的性质和遍历方式3. 平衡二叉树的概念及应用4. 堆的定义和基本操作四、图结构1. 图的基本概念及表示方法2. 图的遍历算法：深度优先搜索和广度优先搜索3. 最短路径算法及其应用4. 最小生成树算法及其应用五、查找与排序1. 查找算法的分类及其特点2. 顺序查找和二分查找算法3. 哈希查找算法及其应用4. 常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序六、高级数据结构1. 图的高级算法：拓扑排序和关键路径2. 并查集的定义和操作3. 线段树的概念及其应用4. Trie树的概念及其应用七、应用案例1. 使用数据结构解决实际问题的案例介绍2. 如何选择适合的数据结构和算法八、复杂度分析1. 时间复杂度和空间复杂度的定义2. 如何进行复杂度分析3. 常见算法的复杂度比较九、常见问题及解决方法1. 数据结构相关的常见问题解答2. 如何优化算法的性能十、总结与展望1. 数据结构学习的重要性和难点2. 对未来数据结构的发展趋势的展望以上是数据结构复习资料的复习提纲知识要点归纳。

希望能够帮助你进行复习和回顾，加深对数据结构的理解和掌握。

在学习过程中，要注重理论与实践相结合，多进行编程练习和实际应用，提高数据结构的实际运用能力。

祝你复习顺利，取得好成绩！。

一、单选题（共20题，40分）1、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

（2.0）A、 8B、 63.5C、 63D、 7正确答案： B2、在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）。

（2.0）A、 O(1)B、 O(n)C、O(n²)D、 O(log₂n)正确答案： B3、根据一组关键字(56, 42, 50, 64, 48)依次插入结点生成一棵AVL树，当插入到值为0的结点时需要进行旋转调整。

（2.0）A、 42B、 50C、 64D、 48正确答案： B4、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。

（2.0）A、 nB、 n+1C、 (n-1)/2D、 (n+1)/2正确答案： D5、在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。

（2.0）A、 n-iB、 n-i+lC、 n-i-1D、 i正确答案： A6、稀疏矩阵一般的压缩存储方法有两种，即（）。

（2.0）A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表正确答案： C7、以下关于线性表的说法不正确的是______。

（2.0）A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

正确答案： C8、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

（2.0）A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B、在第i个结点后插入一个新结点（1≤i≤n）C、删除第i个结点（1≤i≤n）D、将n个结点从小到大排序正确答案： A9、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相同，则该二叉树一定满足（）。

第1章绪论1.数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。

包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。

2.数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点顶点、记录）；数据元素是数据的基本单位。

3.数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。

一个数据元素可由若干个数据项组成。

4.数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

如字符集合C ={A,B,C,…} 。

数据(Data) ：是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。

包括数值数据和非数值数据（字符串、图形、图像、音频、视频）。

数据元素(Data Element) ：表示一个事物的一组数据称为一个数据元素（结点、顶点、记录）；数据元素是数据的基本单位。

数据项（Data Item）：是数据元素中有独立含义的、不可分割的最小标识单位（字段、域、属性）。

一个数据元素可由若干个数据项组成。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

如字符集合C ={A,B,C,…} 。

●数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示。

●四种逻辑结构：集合、线性结构、树型结构、图状结构。

●数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。

例1：设数据逻辑结构B=（K，R）K={k1, k2, …, k9}R={ <k1, k3>，<k1, k8>，<k2, k3>，<k2, k4>，<k2, k5>，<k3, k9>，<k5, k6>，<k8, k9>，<k9, k7>，<k4, k7>，<k4, k6>有时候关系图不唯一（一般是无向图）●数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。

（完整版）数据结构复习题（附答案）⼀、算法设计题（每题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。

数据结构第一章1、数据是描述客观事物的数和字符的集合2、数据项：是具有独立含义的数据最小单位，也称为字段或域3、数据对象：指性质相同的数据元数的集合，是数据的一个子集4、数据结构：指所有数据元素以及数据元素之间的关系5、数据的逻辑结构：由数据元素之间的逻辑关系构成6、数据的存储结构：数据元素及其关系在计算机存储器中的存储表示，称为物理结构逻辑结构的表达方式：1、图表表示：采用表格或图形直接描述数据的逻辑关系。

2、二元组表示：通用的数据逻辑结构表示方式：R={r},r={<010,021>,<021,027>,<027,029>}逻辑结构的类型：1、集合：指数据元素之间除了“同属于一个集合”的关系以外别无其他关系。

2、线性结构：一对一关系，只有一个前驱和一个后继元素。

3、树形结构：多对多关系，除了开始元素以外，都只有一个前驱和多个后继元素。

什么是算法：是问题求解步骤的描述，是指令的有限序列。

1、有穷性：执行有穷步后结束2、确定性：不能有二义性3、可行性：算法可以通过有限次的操作完成其功能，能够被重复地执行4、有输入：一个算法有0个或多个输入5、有输出：一个算法有一个或多个输出算法设计的目标：正确性(算法能正确执行)、可使用性(方便地使用)、可读性(算法易于理解)、健壮性(有好的容错性，不会异常中断或死机)、高效率与低存储量需求(算法的执行时间和存储空间)算法时间性分析方法：事后统计法(缺点:必须执行、存在很多因素掩盖算法本质)、事前估算法(仅考虑算法本身的效率高低、只依赖于问题的规模)第二章线性表：具有相同特性的数据元素的一个有限序列有序表：指线性表中的所有元素按递增或剃减方式有序排列顺序表：线性表的顺序存储结构简称为顺序表(下标从0开始)，从逻辑上相邻的元素对应的物理存储位置也相邻，当进行插入或删除的操作时要平均移动半个表的元素，相当费时。

链表：线性表的链式存储结构称为链表，拥有唯一的标识头指针(head pointer),相应的指向开始结点(first pointer)，指向尾结点的称为尾指针(tail pointer)。

数据结构复习题一、填空1. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。

2. 线性表中结点的集合是 有限 的，结点间的关系是 一对一的。

3. 向一个长度为n 的线性表的第i 个元素(1≤i ≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

4. 向一个长度为n 的线性表中删除第i 个元素(1≤i ≤n)时，需向前移动 n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。

6. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。

单链表中逻辑上相邻的元素的物理位置 不一定 相邻。

７. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。

不允许插入和删除运算的一端称为 栈底 。

８. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

９. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）组成的串 称为空白串。

10. 设S=“A:/document/Mary.doc ”，则strlen(s)= 20 , “/”的字符定位的位置为 3 。

11. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。

12．由３个结点所构成的二叉树有 5 种形态。

13. 一棵深度为6的满二叉树有 n 1+n 2=0+ n 2= n 0-1=31 个分支结点和 26-1 =32 个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

14．一棵具有２５７个结点的完全二叉树，它的深度为 9 。

（ 注：用⎣ log 2(n) ⎦+1= ⎣ 8.xx ⎦+1=915. 设一棵完全二叉树有700个结点，则共有 350 个叶子结点。

答：最快方法：用叶子数＝[n/2]＝35016. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。

一、选择题1．下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（ C ）的有限序列（n>0）。

A．表元素B．字符C．数据元素D．数据项E．信息项2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表4. 静态链表中指针表示的是（ C ）.A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址5. 链表不具有的特点是（ B ）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比1. 对于栈操作数据的原则是（B ）。

A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ A ）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 41 5 63. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。

A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，1. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，求A[6，8]的地址。

13402. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，求A[5，9]的地址。

数据结构复习题及答案数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。

2.线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。

3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。

4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。

5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。

6.查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。

7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。

一、填空题1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。

算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。

2.数据的基本单元是__数据元素__，数据的最小单元是__数据项_。

3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。

4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。

5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。

6.算法机能的阐发和怀抱，能够从算法的工夫庞大度和空间庞大度来评判算法的好坏。

7.数据的逻辑布局包孕调集布局、线性布局、树形布局和图型布局四品种型。

8.数据布局在计较机中的表示称为数据的物理布局，它能够采用__按次存储___或__链式存储_两种存储方法。

9.线性表有两种存储布局，划分为按次存储和链式存储。