数据结构（c语言版）复习资料

数据结构复习资料 由 其直接前驱结点的链域的值 指示。

19． 在n个结点的单链表中要删除已知结点*p，

需找到它的前驱结点的地址，其时间复杂度为O（n）。 1. 数据结构是一门研究非数值计算的程序设计问

20.栈只能在 栈顶 插入和删除元素；对于队列题中计算机的 操作对象 以及它们之间的 关

只能在 队尾 插入和 队首 删除元素。 系 和运算等的学科。

21. 栈是一种特殊的线性表，允许插入和删除运算2. 数据结构被形式地定义为（D, R），其中D是 数的一端称为 栈顶 。不允许插入和删除运算据元素 的有限集合，R是D上的 关系 有限

的一端称为 栈底 。 集合。

22. 队列 是被限定为只能在表的一端进行插3. 数据结构包括数据的 逻辑结构 、数据的 存储

入运算，在表的另一端进行删除运算的线性表。 结构 和数据的 运算 这三个方面的内容。

4. 数据结构按逻辑结构可分为两大类，它们分别是 26． 由３个结点所构成的二叉

树有 5 种形态。 线性结构 和 非线性结构 。

27. 一棵深度为6的满二叉树有 n1+n2=0+ n2= 5. 线性结构中元素之间存在一对一关系，树形结构6-1n-1=31 个分支结点和 2 =32 个叶子。 0中元素之间存在一对多关系，图形结构中元素之间

注：满二叉树没有度为1的结点，所以分支结点数存在多对多关系。

就是二度结点数。 6． 在线性结构中，第一个结点 没有 前驱结点，28． 一棵具有２５７个结点的完全二叉树，它的其余每个结点有且只有 1个前驱结点；最后一个结

深度为 9 。 点 没有 后续结点，其余每个结点有且只有1

（ 注：用? log2(n) ?+1= ? 8.xx ?+1=9 个后续结点。

29．设一棵完全二叉树有700个结点，则共有 350 7. 在树形结构中，树根结点没有 前驱 结点，其个叶子结点。 余每个结点有且只有 1 个前驱结点；叶子结

答：最快方法：用叶子数＝[n/2]＝350 点没有 后续 结点，其余每个结点的后续结点

数可以任意多个 。

30． 设一棵完全二叉树具有1000个结点，则此完

8. 在图形结构中，每个结点的前驱结点数和后续结

全二叉树有 500 个叶子结点，有 499 个度为

点数可以 任意多个 。

2的结点，有 1 个结点只有非空左子树，有 0

9．数据的存储结构可用四种基本的存储方法表示，

个结点只有非空右子树。

它们分别是顺序 、 链式 、 索引 和 散列 。

答：最快方法：用叶子数＝[n/2]＝500 ，

10. 数据的运算最常用的有5种，它们分别是插入 、

n2=n0-1=499。 另外，最后一结点为2i属于左叶子，

删除、修改、 查找 、排序。

右叶子是空的，所以有1个非空左子树。完全二叉

11. 一个算法的效率可分为 时间 效率和 空

树的特点决定不可能有左空右不空的情况，所以非

间 效率。

空右子树数＝0.

12. 在顺序表中插入或删除一个元素，需要平均移

31．在数据的存放无规律而言的线性表中进行检索

动 表中一半元素，具体移动的元素个数与 表长和

的最佳方法是 顺序查找（线性查找） 。 该元素在表中的位置 有关。

13. 线性表中结点的集合是 有限 的，结点间的32. 线性有序表（a1，a2，a3，…，a256)是从小到大关系是 一对一 的。 排列的，对一个给定的值k，用二分法检索表中与14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)k相等的元素，在查找不成功的情况下，最多需要之前插入一个元素时，需向后移动 n-i+1 个元素。 检索 8 次。设有100个结点，用二分法查找时，15. 向一个长度为n的向量中删除第i个元素(1≤i最大比较次数是 7 。 ≤n)时，需向前移动 n-i 个元素。 33. 假设在有序线性表a[20]上进行折半查找，则比16. 在顺序表中访问任意一结点的时间复杂度均为 较一次查找成功的结点数为1；比较两次查找成功

O(1) ，因此，顺序表也称为 随机存取 的数据的结点数为 2 ；比较四次查找成功的结点数为 结构。

17. 顺序表中逻辑上相邻的元素的物理位置 必定8 ；平均查找长度为 3.7 。

5相邻。单链表中逻辑上相邻的元素的物理位置 不解：显然，平均查找长度＝O（log2n）<5次（2）。

一定 相邻。 但具体是多少次，则不应当按照公式 18．在单链表中，除了首元结点外，任一结点的存储位置

一、填空题

1

ASL?n?1log2(n?1)来计算（即（21×log221）/20nm

元素。

＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！ 34．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 35. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 决定数据的存储地址。

（ × ）7. 线性表在物理存储空间中也一定是连

续的。

错，线性表有两种存储方式，顺序存

储和链式存储。后者不要求连续存放。

（ × ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。

（ × ）9. 顺序存储方式只能用于存储线性结构。

错误。顺序存储方式不仅能用于存储线性结构，还可

以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）

36. 散列法存储的基本思想是由 关键字的值 （ × ）10. 线性表的逻辑顺序与存储顺序总是一

致的。

错，理由同7。链式存储就无需一致。

二、判断正误（在正确的说法后面打勾，反之打叉）

（ × ）1. 链表的每个结点中都恰好包含一个指针。

答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（ × ）11. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）12. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（ × ）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。

（ × ）3. 链表的删除算法很简单，因为当删除

链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。

（ × ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链

表也是线性表！且即使是顺序表，也能存放记录型数据。

（ √ ）13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）14. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ）15. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

（ × ）16. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。顺序表才适合随机

存取，链表恰恰适于“顺藤摸瓜”

（ × ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据

（ √ ）17. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ √ ）18. 两个栈共享一片连续内存空间时，为

提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内

存空间的两端。

（ × ）19. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。

（ × ）20. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

错，有可能。

（ √ ）21. 若二叉树用二叉链表作存贮结构，则

2

在n个结点的二叉树链表中只有n—1个非空指针域。 （ × ）22.二叉树中每个结点的两棵子树的高度差等于1。

（ √ ）23.二叉树中每个结点的两棵子树是有序的。 （ × ）24.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ × ）25.二叉树中每个结点的关键字值大于其左

非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （应当是二叉排序树的特点）

（ × ）26.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1）

（ × ）27.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（ × ）28.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）

（ √ ）29.用二叉链表法（link-rlink）存储包含n

个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（ √ ）30.具有12个结点的完全二叉树有5个度为2的结点。

A) 可行性、可移植性和可扩充性

B) 可行性、确定性和有穷性

C) 确定性、有穷性和稳定性

D) 易读性、稳定性和安全性

（ C ）7．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：

（A）存储结构 （B）逻辑结

构 （C）顺序存储结构 （D）链式存储结构

（ A ）9. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：

（A） 访问第i个结点（1≤i≤n）和

求第i个结点的直接前驱（2≤i≤n）

（B） 在第i个结点后插入一个新结

点（1≤i≤n）

（C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序

（ B ）10. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素

（A）8 （B）63.5 （C）

63 （D）7

（ A ）11. 链接存储的存储结构所占存储空间：

（A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 三、单项选择题

（B） 只有一部分，存放结点值 （ B ）1. 非线性结构是数据元素之间存在一

(C） 只有一部分，存储表示结点间关种：

系的指针 A）一对多关系 B）多对多

（D） 分两部分，一部分存放结点值，关系 C）多对一关系 D）一对一关系

另一部分存放结点所占单元数 （ C ）2. 数据结构中，与所使用的计算机无关

B ）12. 链表是一种采用 存储结构存的是数据的 结构；

储的线性表； A) 存储 B) 物理 C)

（A）顺序 （B）链式 （C）逻辑 D) 物理和存储

星式 （D）网状 （ C ）3. 算法分析的目的是：

A) 找出数据结构的合理性 B) （ D ）13. 线性表若采用链式存储结构时，要

求内存中可用存储单元的地址: 研究算法中的输入和输出的关系

（A）必须是连续的 （B）部分C) 分析算法的效率以求改进 D)

地址必须是连续的 分析算法的易懂性和文档性

（C）一定是不连续的 （D）连续（ A ）4. 算法分析的两个主要方面是：

或不连续都可以 A) 空间复杂性和时间复杂性

（ B ）14． 线性表Ｌ在 情况下适用于B) 正确性和简明性

使用链式结构实现。 C) 可读性和文档性

（Ａ）需经常修改Ｌ中的结点值 D) 数据复杂性和程序复杂性

（Ｂ）需不断对Ｌ进行删除插入 （ C ）5. 计算机算法指的是：

（Ｃ）Ｌ中含有大量的结点 A) 计算方法 B) 排序方法

（Ｄ）Ｌ中结点结构复杂 C) 解决问题的有限运算序列 D) 调度方法

（（ B ）6. 计算机算法必须具备输入、输出和 B ）15.栈中元素的进出原则是

Ａ．先进先出 Ｂ．后进先出 等5个特性。

3

Ｃ．栈空则进 Ｄ．栈满则出

(2.) x=0; （ C ）16. 若已知一个栈的入栈序列是1，2，

for(i=1; i

x++; Ａ．i Ｂ．n=i Ｃ．n-i+1 x++共执行了n-1+n-2+……＋1= 解：因为2Ｄ．不确定 n(n-1)/2 ，所以执行时间为O（n） （ B ）17. 判定一个栈ST（最多元素为m0） 为空的条件是

Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0

（ B ）22．在表长为ｎ的链表中进行线性查找，

4.设有编号为1，2，3，4的四辆列车，顺序进入一

它的平均查找长度为

个栈式结构的车站，具体写出这四辆列车开出车站

Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳ

的所有可能的顺序。

Ｌ＝（ｎ＋１）／２;

Ｃ. ＡＳＬ＝n＋１; Ｄ. Ａ

ＳＬ≈ｌｏｇ２（ｎ＋１）－１

（ A ）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。

A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50

刘答：至少有14种。

① 全进之后再出情况，只有1种：4，3，2，1 ② 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 ③ 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4

④ 进1个之后再出的情况，有5种，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3

5.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。 （ C ）24．对22个记录的有序表作折半查找，

解：由前序先确定root，由中序可确定root当查找失败时，至少需要比较 方法是：

的左、右子树。然后由其左子树的元素集合和右子次关键字。

树的集合对应前序遍历序列中的元素集合，可继续A．3 B．4 C．5

确定root的左右孩子。将他们分别作为新的root，D． 6

不断递归，则所有元素都将被唯一确定，问题得解。

（ A ）25. 链表适用于 查找

A．顺序 B．二分法 D C．顺序，也能二分法 D．随机

A

C F 四、简答题

1.数据结构和数据类型两个概念之间有区别吗？

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

E G B H I

6. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A

数据结构的概念：数据之间的内在联系。要了解3种数据结构的概念：逻辑结构；物理结构；基本操作。

例如：栈和队的逻辑结构都是线性的，但她们的基

2. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。

3、分析下面各程序段的时间复杂度

1.(1.) for (i=0; i

4

本操作不同，就是不同的数据结构。

常见的数据结构的分类：线性关系；集合关系；一对多；多对多（图）；

什么事物理结构（应该有印象）。

算法设计时要用类PASCAL,类C，不要用C++. 算法分析的常用方法：事前分析；事后统计。 时间/空间复杂度的概念。空间是算法运行时资源占用情况。

时间复杂度：最坏，最好，平均。 例如：归并排序都是O（n*logn），最好，最怀，平均都是一样的

插入排序：最好为O(n) ,最坏为O（n2）

线性表：逻辑关系，各种基本操作，两个有序表的归并。

线性表的顺序存储：线性表的操作在顺序表中的实现。

例如：1。插入与删除和插入的位置与表长有关。 2．在一个长为n的表中插入一个元素的平均复杂度，要有插入位置的概率分布表达式，即给出此表达式，算平均复杂度。

线性表的链式存储：链表的基本操作：2个有序表的归并。

例如：1。把链表就地逆置：一个指针P指向当前逆置好的一系列节点的最后一个节点，取P的NEXT插入队头。

2．三色问题：节点红黄蓝在链表上无序排列，把他们按红黄蓝的顺序排好。要求只能从头到尾搜索一遍。设当前指针P，头指针S，S.NEXT为Q，S后接红节点。若P为红，插入S后。若P为黄，插入Q后。若P为兰，不动。然后P向后移，求下个。

注：要了解单链表的插入，删除在什么位置操作。 静态链表（数组表示）：不能象单链表那样不受限增加节点。

循环链表：如果表示队列，用它最好。P指向队尾。好处：用于优先队列中。

双向链表：单链表中只有P指向当前节点，不能删除P。因为无法找到P 的前驱。而双向链表可以。注意指针变化情况。

栈：后进先出。基本操作：出入栈，取栈顶。在顺序表和链表上的实现；出栈序列是否合理？ 例如：入栈序列是1，2，，，n，则出栈序列有几种？（即n个节点的二叉树的个数。因为树的先序是1，2，，，n）。

栈与递归：见我给你寄过去的手写体。 队列：先进现出。链队列，循环队列。 例如：1。把从队头开始的第i个元素删除：队列 只有出队入队，不能直接删除。要先将前i-1个出队，入队尾；i出队；i+1以后的出队入队尾。 2．队列逆置（队头与队尾交互）：出队入栈；后出栈入队。

注意：这些结构的基本操作有什么，不能混。 循环队列：队头指针和队尾指针。记住队空和满的标志。见手写版。

串：1。KMP算法，求NEXT函数值等。时间：O(n+m)。其中，模式匹配为O（n）；预处理为O（m）,要会证明她们。简略证明见手写版。

2．求两串的最长公共子串，时间为O（n）是不行的，至少要O（n2）。具体证明估计不会考。 17．数组：存储位置与下标对应。特殊数组（对称，上三角等）。

三元组，稀疏矩阵（求逆）。计数技术，在设计算法中的应用。 十字链表不考。

广义表：基本概念，存储结构（二叉链表）。应用不考。

广义表递归算法了解。 二叉树的性质（熟）。

存储结构：二叉链表，三叉链表。

遍历：中，先，后。 按层遍历：用辅助队列。例如求K层有多少节点。

线索二叉树：中序（先后序不考）。线索中的插入删除不考。

树与森林的遍历：树的先根与后根（分别对应相应二叉树的先序，中序）。森林的先序和后序（分别对应相应二叉树的先序，中序）。 树与二叉树一一对应。

由先序中序可以唯一确定二叉树。而由先序后序不能。例子见手写版。

二叉树可以为空，树不能为空（树为有根有序树）。 树与等价：例如：判断一个元素是否属于一个特定的集合，可看这个节点是否在此树上。看两个节点是否在一个强联通分量，看他们是否在一棵树上。求KRUSCAL算法（最小生成树集合）。

哈夫曼：前缀码。它是加权外部路径长度最小的二叉树。它是严格二叉树，无度为1的点。节点个数＝2×叶节点－1。 构造，编码。

扩展：用0，1，2三进制编码：元素个数为奇。N个元素K进制：K-1整除N-1。否则增加概率为零的元素。

注意11。6节的最佳归并。 树的计数：记结论。 N个操作符或N个括号，为操作符加括号的情况数目。

N＋2个顶点的凸多边形，他的不同三角剖分的个数。

a1,a2,,,an, ai=1/-1,任意前k个ai之和大于等于0， 动态查找：二叉排序树：中序遍历有序，先序无序。

5

给出先（或后）序的次序，写出此树（因为中序是顺序的，已知）。他的插入和删除（删除不一定考）。给定树，求平均查找长度。 查找长度的量级。

平衡二叉树：一定是二叉排序树。树的所有子树都是平衡二叉树。反之不成立。若要执行4种旋转，至少7个节点。

M阶B树：关键字个数的上下限。N个关键字构成树的节点数目层数。 B＋树的概念。 键树。

哈希表：解决冲突的方法。只有链地址法可以解决二次聚集。不是同义词不会竞争同一位置。链地址法是顺序结构和链结构的完美结合。

查找长度：1。探测次数（包括最后一次比较为空的次数）。

数据结构复习资料1 2010-01-06 10:43

2．关键字比较次数（不包括最后一次为空的）。

37．内部排序：简单插入排序（稳定）；折半（不稳定）；希尔（不稳定）；冒泡（稳定）；快速（不稳定）；选择（不稳定）；堆（不稳定）；归并（稳定）。要记住她们的时间复杂度（最好，平均，最坏）。

基数排序：给定N个数，范围在（0，n2-1），以O(n)时间排序。记ni=ai*n+bi，按(ai,bi)先以bi为基数排序，再以ai 排。

基数排序利用关键字本身的值，而其他基于比较。 找最大和最小值的时间[3/2n]-2。见手写版。两两比较，小的方一个数组，大的放一个数组，再找。 找最大和次大值：可以调整堆，也可以记下比较

一、名词解释：

1. 数据结构——数据结构就是数据的组织形式，也可看成是包含数据结构的数据表，说明数据之间存在着一定的相互关系或约束。

2. 逻辑结构——我们把只表现元素之间逻辑关系，而不涉及它们在计算机中的表示，只是理论的、反映在纸面上的东西，这种抽象的数据结构称为逻辑结构。

3. 物理结构——抽象的数据结构在计算机内的表示，也就是映射在存储空间上的、具体的数据结构在计算机内表示，也就是映射在存储空间上的、具体的数据结构。 二、问答题：

2. 说明对程序进行评价时，“时间”与“空间”之间的关系。

答：时间性和空间性是程序的效率问题。

时间效率决定于：源程序转换为目标程序的时间和目标程序执行的时间。时间效率与编译质量有关，与算法的简化程度有关，还与用户对语言的熟练程度有关，其中，算法的效率起主要作用。 空间效率一般指程序花费的内存空间的问题。

对于同等复杂程度的程序：一般时间效率越高的程序，占用的内存就越大，空间效率就越低；一般时间效率越低的程序，占用的内存就越小，空间效率就越高。两者具有一定的矛盾性。但是随着内存容量的不断增大，往往会牺牲空间性来提高时间性。

五、将二叉树的左右孩子交换的算法：

algorithm swap( Tree *b ) {

Tree *t;

if( b == null ) return; else {

t = b->lchild;

b->lchild = b->rchild; b->rchild = t; swap( b->lchild ); swap( b->rchild ); }

}

六、用两个栈模拟一个队列：

algorithm 用两个栈模拟一个队列

{

stack s1, s2; // 容量都为n。 void 元素入队

6

{

int x;

if( s1->top == n )

printf( \队列上溢\ else

push( s1, x ); }

void 元素出队 {

int x;

s2->top = 0;

while( !Empty( s1 ) ) push( s2, pop( s1 ) ); pop( s2, x );

while( !Empty( s2 ) ) push( s1, pop( s2 ) ); }

void 判断队列是否为空 {

if( isEmpty( s1 ) ) return( 1 ); else

return( 0 ); } }

7

本文来源：https://www.bwwdw.com/article/6qdw.html