一、填空题
1、栈的特点是先进后出(或后进先出)，队列的特点是先进先出。
2、顺序表中逻辑上相邻的元素物理位置也相邻，单链表中逻辑上相邻的元素物理位置不相邻。
3、算法的5个重要特性是__________、__________、_________、___________、___________。
4、线性表、栈、队列都是线性结构，可以在线性表的任何位置插入和删除元素，对于栈只能在栈顶位置插入和删除元素，对于队列只能在队尾位置插入和只能在队头删除元素。
5、下面树的先序、中序、后续遍历的结果依次为_________、___________、__________
6、当数据量特别大需借助外部存储器对数据进行排序时，则这种排序称为外部排序。
7、在堆排序、快速排序和归并排序中，若从节省存储空间的角度考虑，则应首先选取堆排序方法；若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序的速度来考虑，则应选取快速排序方法。
二、选择题
1、算法分析的两个主要方面是（）。
A. 时间复杂度和空间复杂度
B. 正确性和简明性
C. 可读性和文档性
D. 健壮性和科学性
2、对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间。
A. 顺序表
B. 带头结点的双循环链表
C. 单链表
D. 带尾结点的单循环链表
5、循环队列在进行删除运算时（）
A. 仅修改头指针
B. 修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改
6、栈和队列的共同点是（）。
A．都是先进后出B．都是先进先出
C．只允许在端点处插入和删除元素D．没有共同点
7、树最适合用来表示（）
A．有序数据元素 B. 无序数据元素
C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据
8、如果结点A有3个兄弟，而且B是A的双亲，则B的度是（）
A. 4
B. 5
C. 1
D. 3
9、有关二叉树下列说法正确的是（）
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
10、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）
A. 250
B. 500
C. 505
D. 以上答案都不对
11、静态查找表与动态查找表二者的根本差别在于（B）
A. 它们的逻辑结构不一样
B. 施加在其上的操作不同
C. 所包含的数据元素的类型不一样
D. 存储实现不一样
12、顺序查找法适合于存储结构为（B）的线性表。
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
13、下面描述不正确的是（D）
A. 顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。
B. 静态查找表中关键字有序时，可用二分查找。
C. 分块查找也是一种静态查找表。
D. 经常进行插入和删除操作时可以采用二分查找。
14、分块查找时确定块的查找可以用顺序查找，也可以用（），而在块中只能是（A）
A. 二分查找，顺序查找
B. 静态查找，顺序查找
C. 二分查找，二分查找
D. 散列查找，顺序查找
15、从末排序的序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在排序序列的合适位置，该排序方法称为（A）排序法
A. 插入
B. 选择
C. 希尔
D. 二路归并
16、快速排序方法在（C）情况下最不利于发挥其长处。
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序
D. 要排序的数据个数为奇数
17、下述几种排序方法中，要求内存量最大的是（D）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
20、使用顺序存储结构对二叉进行存储时，一个深度为k的二叉树需要（）个存储空间。
A. 2k
B. 2k
C. 2k+1
D. 2k-1
三、判断
1、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。()
2、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。()
3、栈和队列都是运算受限的线性表，只允许在表端点处进行操作。（）
4、若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。（）
5、树的度是树内各结点的度之和。（）
6、一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。（）
7、二叉树就是结点度为2的树。()
8、二分查找只适用于有序表，包括有序的顺序表和有序的链表。（）
9、若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则该二叉树一定是二叉查找树。（）
10、内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。（）
五、简答题
1、简述栈和队列之间的相同点和不同点。
2、请简述顺序表的特点。
3、请简述二叉树的遍历有哪几种，每种遍历的特点是什么。
4、简述二分查找的基本原理。
5、什么是内排序? 什么是外排序?
六、分析题
请将下面的森林转换为二叉树，绘图并说明整个转换过程。
1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 11. 队列是一种（ B ）的线性表。 A．先进后出B．先进先出 C．只能插入D．只能删除 12．采用开放定址法处理散列表的冲突时，其平均查找长度（ C ）。
第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 （补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。） 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。） 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。 （2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1) 2.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n) 3.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 《数据结构》复习资料1 一、选择题 1. 一棵二叉树中第６层上最多有（）个结点。 A. ２ B. 31 C. 32 D. 64 2. 顺序表中数据元素的存取方式为（）。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 连续存取 3. 设有无向图G=(V,E)，其中顶点集合V={a,b,c,d,e,f}，边集合E={(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}。对G进行深度优先遍历，正确的遍历序列是（）。 A. a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b 4. 在待排元素序列基本有序的前提下，效率最高的排序方法是（）。 A. 插入 B. 选择 C. 快速 D. 归并 5. 设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（）。 A. 50 B. 25 C. 10 D. 7 6. 设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存 放地址应为（）。 A. 2 B. 3 C. 4 D. 7 E. 8 F. 以上都不对 7. 设对下图从顶点a出发进行深度优先遍历，则（）是可能得到的遍历序列。 A. acfgdeb B. abcdefg C. acdgbef D. abefgcd 8. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 9. 设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（）。 A. 79,46,56,38,40,84 B. 84,79,56,38,40,46 C. 84,79,56,46,40,38 D. 84,56,79,40,46,38 10. 设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。 A. b B. c C. (c) 一、在数据结构中，从逻辑上可以把数据结构的的分类。P10 1、分类： 线性结构：K中每个结点最多只有一个前驱和一个后继。没有前驱的结点称为开始结点，没有后继的结点称为终端结点。 树形结构：K中每个结点最多只有一个前驱，但可以有多个后继的结构。 复杂结构：K 中结点的前驱、后继结点的个数都不作限制的结构。 2、特殊的还有集合结构：当R为空集时，K中结点间没有约束关系。 3、各种逻辑结构具有以下包含关系： 集合结构?线性结构?树形结构?复杂结构 二、数据结构主要研究对象P13 研究的是结点之间的逻辑结构、储存结构和各种行为的具体表现。 三、算法的特点P17 1、定义：算法是由有穷规则构成的为解决某一问题的运算序列（方法或过程）。 2、算法特点有三个： 有穷性：一个算法必须在执行了有穷步之后结束 确定性：算法的每一步必须有确切的定义 可行性：算法是可行的，意味着算法中的每个动作，原则上都是能够由机器或人准确完成的。 3、算法的正确性：如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且终止时得到满足要求的（输出）结果。 4、算法设计的方法：贪心法、分治法、回溯法、动态规划法、分枝界限法。 四、线性表概念P29，顺序表存储特点，链表的类型及存储特点。单链表的插 入、删除、查找操作算法描述 1、线性表：线性表简称表，是零个或多个元素的有穷序列。通常表示为： K= (k0,k1,.......k n-1) , K中所含元素的个数称为表的长度。 线性表可采用顺序储存和链式储存。 2、顺序表存储特点：将线性表中的元素一个接一个地存储在一片相邻的存储区域中。 3、链表的类型有及存储特点： （1）单链表：用一组可以是不连续的存储单元，存储线性表的各个元素，每 个元素存储了自身的信息，还存储了其后继的信息（即后继元素的存储位 置）。 数据域指针域 （2）双链表： llink info rlink 其中，llink域指向其前驱结点，称为左指针域；rlink域指向其后继结点，称为右指针域；info域存放结点本身的信息，特点是找到结点的前驱和后继。（3）循环双链表：双链表的头一个结点和最后一个结点链接起来，并将链表的头尾存放在头结点之中。 （4）单链表的插入：在带头结点的单链表llist中 下标为p的结点后插入值为x的新结点 int insertPost_link (LinkList llist, PNode p, DataType x) { PNode q=(PNode)malloc(sizeof(Struct Node)); /*申请新结点*/ if (q==NULL) { printf( Out of Space!\n ) ; return 0; } else { q->info =x; q->link=p->link; p->link=q; return 1; } } （5）单链表的删除：在带头结点的单链表llist中,删除第一个元素值为x 的结点（这里要求DataType 可以用!=比较） int deleteV_link(LinkList llist, DataType x) { PNode p, q; p = llist; if(p==NULL) return 0 ; while( p->link != NULL && p->link->info != x ) p = p->link; /*找值为x的结点的前驱结点的存储位置*/ 数据结构复习题及参考答案 （抽考其中50%） 一、单选题(每小题1分) 1．下列程序段的时间复杂度为（A ）。 for(i=0； i 第一章绪论 一、数据结构包括：逻辑结构、存储结构、运算（操作）三方面内容。 二、线性结构特点是一对一。 树特点是一对多 图特点是多对多 三、数据结构的四种存储结构：顺序存储、链式存储、索引存储、散列存储 顺序存储结构和链式存储结构的区别？ 线性结构的顺序存储结构是一种随机存取的存储结构。 线性结构的链式存储是一种顺序存取的存储结构。 逻辑结构分类：集合线性树图，各自的特点。或者分为线性结构和非线性结构。 四、算法的特征P13 五、时间复杂度 (1) i=1; k=0; while(i 二、线性表的特点。 三、顺序表的插入、思想、时间复杂度o(n)、理解算法中每条语句的含义。 （1）插入的条件：不管是静态实现还是动态实现，插入的过程都是从最后一个元素往后挪动，腾位置。静态是利用数组实现，动态是利用指针实现。不管静态还是动态，在表中第i个位置插入，移动次数都是n-i+1。 四、顺序表的删除、思想、时间复杂度o(n)、理解算法中每条语句的含义。 （1）删除的条件：不管是静态实现还是动态实现，删除的过程都是从被删元素的下一位置向前挪动。静态是利用数组实现，动态是利用指针实现。不管静态还是动态，删除表中第i个元素，移动次数都是n-i。 五、顺序表的优缺点？为什么要引入链表？ 答：顺序表的优点是可以随机存取，缺点是前提必须开辟连续的存储 一、填空题 1、栈的特点是先进后出(或后进先出)，队列的特点是先进先出。 2、顺序表中逻辑上相邻的元素物理位置也相邻，单链表中逻辑上相邻的元素物理位置不相邻。 3、算法的5个重要特性是__________、__________、_________、___________、___________。 4、线性表、栈、队列都是线性结构，可以在线性表的任何位置插入和删除元素，对于栈只能在栈顶位置插入和删除元素，对于队列只能在队尾位置插入和只能在队头删除元素。 5、下面树的先序、中序、后续遍历的结果依次为_________、___________、__________ 6、当数据量特别大需借助外部存储器对数据进行排序时，则这种排序称为外部排序。 7、在堆排序、快速排序和归并排序中，若从节省存储空间的角度考虑，则应首先选取堆排序方法；若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序的速度来考虑，则应选取快速排序方法。 二、选择题 1、算法分析的两个主要方面是（）。 A. 时间复杂度和空间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 健壮性和科学性 2、对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间。 A. 顺序表 B. 带头结点的双循环链表 C. 单链表 D. 带尾结点的单循环链表 5、循环队列在进行删除运算时（） A. 仅修改头指针 B. 修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 6、栈和队列的共同点是（）。 A．都是先进后出B．都是先进先出 C．只允许在端点处插入和删除元素D．没有共同点 7、树最适合用来表示（） A．有序数据元素 B. 无序数据元素 C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 8、如果结点A有3个兄弟，而且B是A的双亲，则B的度是（） A. 4 B. 5 C. 1 D. 3 9、有关二叉树下列说法正确的是（） A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 10、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A. 250 B. 500 C. 505 D. 以上答案都不对 11、静态查找表与动态查找表二者的根本差别在于（B） 数据结构复习资料(亲自整理) 1、链表是一种存储数据的链式结构，每个数据之间都是相关联的。 2、线性结构是一个有序数据元素的集合，包括线性表、栈、队列、双队列、数组和串。 3、树是由n（n>=1）个有限节点组成一个具有层次关系的集合，而二叉树是每个结点最多有两个子树的有序树。二叉树与树的主要差别在于，二叉树结点的最大度数为2，而树中结点的最大度数没有限制；二叉树的结点有左、右之分，而树的结点无左、右之分。 4、堆是一种可以被看做一棵树的数组对象，总是满足某个节点的值总是不大于或不小于其父节点的值，且堆总是一棵完全二叉树。 5、二叉排序树是一种满足以下递归定义的二叉树：若左子树非空，则左子树所有节点的值均小于它的根节点；若右子树非空，则右子树所有节点的值均大于于它的根节点；左右子树也分别为二叉排序树。 1、在已知前序遍历和中序遍历的情况下，可以通过画树 的方法求得后序遍历。具体步骤如下：首先根据前序遍历的特点，确定根节点；然后观察中序遍历，将左子树和右子树分别确定下来；接着对左子树和右子树分别进行递归，直到遍历完所有节点，最后得到后序遍历。 2、树和二叉树之间可以相互转换。将树转换为二叉树的 方法是：对于每个节点，将其第一个孩子作为其左孩子，将其兄弟作为其右孩子。将二叉树转换为树的方法是：对于每个节点，将其右孩子作为其兄弟。 3、二叉树线索化是将二叉树中的空指针指向该节点在中 序遍历中的前驱或后继节点的过程。在线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1. 4、邻接表是图的一种链式存储结构，用于表示图中每个 节点的邻居节点。每个节点都有一个链表，存储着与该节点相邻的节点。 邻接表是一种图的存储结构，对于每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图是以该顶点为尾的弧）。 邻接表中的表结点和头结点分别表示边和顶点，包含信息如下：表结点adjvex（邻接点）。nextarc（指向下一个表结点） 数据结构复习提纲 复习内容： 基本概念掌握：数据结构，逻辑结构，存储结构；数据类型；算法;T（n）,S（n）的理解。 要学习的数据结构定义形式： n（n〉=0）个数据元素的有限集合. 将约束:1、数据元素本身.2、数据元素之间的关系。3、操作子集。 大多有两种存储（表示、实现）方式：1、顺序存储。2、链式存储. 一、线性结构： 1、线性表：n(n〉=0)个相同属性的数据元素的有限序列。12种基本操作. 顺序表：9种基本操作算法实现.单链表：11种基本操作算法实现。(重点:插入、删除) 顺序表与单链表之时间性能、空间性能比较. 循环链表：类型定义与单链表同。算法实现只体现在循环终止的条件不同。 双向链表：重点插入、删除算法。 2、操作受限的线性表有：栈、队列。 栈：顺序栈；链栈（注意结点的指针域指向）。(取栈顶元素、入栈、出栈) 队列：循环队列(三个问题的提出及解决）;链队列（注意头结点的作用）.（取队头元素、入队、出队。链队列中最后一个元素出队） 3、数据元素受限的线性表有：串、数组、广义表。 串：定长顺序存储；堆分配存储.块链存储（操作不方便） 数组:顺序存储。特殊矩阵的压缩存储；稀疏矩阵（三元组表示、十字链表) 广义表：长度、深度.取表头（可以是原子也可以是子表)；取表尾（肯定是子表）。链式存储。 二、树型结构： 1、树：n（n>=0）个数据元素的有限集合.这些数据元素具有以下关系：……。（另有递归定义。） 术语；存储(双亲表示、孩子表示、孩子双亲表示、孩子兄弟表示）。 2、二叉树：n(n〉=0）个数据元素的有限集合。这些数据元素具有以下关系:……。（另有递归定义） 5个性质（理解、证明;拓展）。遍历二叉树（定义、序列给出、递归算法、非递归算法)；遍历二叉树应用：表达式之前序表达式、后序表达式、中序表达式转换。 线索二叉树（中序线索二叉树）。树森林与二叉树的转换。树与森林的遍历. 赫夫曼树及其应用：定义、构造、赫夫曼编码。 三、图形结构：n(n〉=0)个数据元素的有限集合。这些数据元素具有以下关系：……。 术语掌握. 存储结构（数组表示法、邻接表；无向图的邻接多重表）。 图的遍历及应用：无向图的最小生成树（普里姆算法、克鲁斯卡尔算法）;拓扑排序、关键路径。 四、查找（查找表）：相关概念掌握。 静态查找表:顺序表的查找;有序表的查找； 动态查找表：二叉排序树、AVL树的定义及调整。 哈希表:定义及概念；HASH函数； 五、内部排序：概念掌握。 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序:起泡排序、快速排序 选择排序：冒泡、简单选择排序 归并排序（外部排序基础) 基数排序（链式基数排序） 要求：1、排序算法.2、各种排序算法的O(n）、稳定性. 模拟卷 一、填空题 1、在用于表示有向图的邻接矩阵中，对第i行的元素进行累加, 可得到第i 个顶点的（出)度, 而对第j列的元素进行累加，可得到第j个顶点的（入)度. 数据结构复习重点 谁让我找到你们了. 第一章 1.数据是信息的载体,它能够被计算机识别、存储和加工处理。 2.数据元素是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录。 3.数据结构指的是数据之间的相互关系，即数据的组织形式。一 般包括三个方面的内容：①数据元素之间的逻辑关系，也称为数据的逻辑结构； ②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；③数据 的运算，即对数据施加的操作。 4.数据类型是一个值的集合以及在这些值上定义的一组操作的总称。按"值"是否可分解，可将数据类型划分为两类：①原子类型，其值不可分解；②结构类型，其值可分解为若干个成分。 5.抽象数据类型是指抽象数据的组织和与之相关的操作。可以看作是数据 的逻辑结构及其在逻辑结构上定义的操作。 6.数据的逻辑结构简称为数据结构。数据的逻辑结构可分为两大类：①线 性结构(~的逻辑特征是若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且所有结点都最多只有一个直接前趋和一个直接后继)；②非线性结构(~的逻辑特征是一个结点可能有多个直接前趋和直接后继)。 7.数据存储结构可用四种基本的存储方法表示：①顺序存储方法(该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系 由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构)；②链接存储方法(该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构)；③索引存储方法(该方法通常是在存储结点信息的同时，还建立附加的索引表)； ④散列存储方法(该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址)。 8.非形式地说，算法是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值为输出。因此，一个算法是一系列将输入转换为输出的计算步骤。 9.求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢? 选用的算法首先应该是"正确"的。此外，主要考虑三点：①执行算法所耗费的时间；②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；③算法应易于理解，易于编码，易于调试等等。 10.性结构反映结点的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是多对多的。 11.数据的运算最常用的五种，分别是查找、插入、删除、更新、和排序。 12.一个算法的效率可分为时间效率和空间效率。 第二章线性表 1.线性表是由n(n≥0)个数据元素(结点)a1,a2,an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0是称为空表，常常将非空的线性表(n 0)记作：(a1,a2,an)。 2.按顺序存储方法存储的线性表称为顺序表，按链式存储的线性表称为链表。 3.顺序表上实现的基本运算有：插入、删除。在顺序表做插入运算，平均要移动表中的一半结点。当表长n较大时，算法的效率相当低。虽然EIS(n)中的n的系数较小，但就数量级而言，它仍然是线性阶的，因此算法的平均时间复杂度是0(n)；在顺序表做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是0(n)。 数据结构期末复习重点知识点总结 一、数据结构概述 数据结构是计算机科学中一门关于数据组织、存储和管理的学科。 它涉及到各种数据类型和它们之间的关系，以及对这些数据类型进行 有效操作和处理的算法。 二、基本数据结构 1. 数组 - 数组是一种线性数据结构，用于存储相同类型的数据元素。 - 数组的特点是随机访问和连续存储。 - 数组的插入和删除操作需要移动其他元素，时间复杂度为O(n)。 2. 链表 - 链表是一种线性数据结构，通过节点之间的指针链接来组织数据。 - 链表的特点是插入和删除操作简单，时间复杂度为O(1)。 - 链表分为单链表、双向链表和循环链表等不同类型。 3. 栈 - 栈是一种具有后进先出（LIFO）特性的数据结构。 - 栈的操作主要包括压栈（Push）和弹栈（Pop）两个操作。 - 栈常用于表达式求值、递归算法的实现等场景。 4. 队列 - 队列是一种具有先进先出（FIFO）特性的数据结构。 - 队列的操作主要包括入队（Enqueue）和出队（Dequeue）两个 操作。 - 队列常用于实现缓冲区、消息队列等场景。 5. 树 - 树是一种非线性的数据结构，由节点和边组成。 - 树的节点具有层级关系，由根节点、子节点和叶节点等组成。 - 常见的树结构有二叉树、红黑树、B树等。 6. 图 - 图是一种非线性的数据结构，由节点和边组成。 - 图的节点之间可以有多对多的关系。 - 图的遍历方式有深度优先搜索（DFS）和广度优先搜索（BFS）。 三、常见的数据结构算法 1. 排序算法 - 冒泡排序、插入排序、选择排序等简单但效率较低的排序算法。 - 快速排序、归并排序、堆排序等高效的排序算法。 第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理; 2.数据元素：数据的基本单位,可由若干个数据项组成,数据项是具有独立含义的最小标识单位; 3.数据结构：数据之间的相互关系,即数据的组织形式; 它包括：1数据的逻辑结构,从逻辑关系上描述数据,与数据存储无关,独立于计算机； 2数据的存储结构,是逻辑结构用计算机语言的实现,依赖于计算机语言; 3数据的运算,定义在逻辑结构上,每种逻辑结构都有一个运算集合;常用的运算：检索/插入/删除/更新/排序; 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型;数据的存储结构是逻辑结构用计算机语言的实现; 5.数据类型：一个值的集合及在值上定义的一组操作的总称;分为：原子类型和结构类型; 6.抽象数据类型：抽象数据的组织和与之相关的操作;优点：将数据和操作封装在一起实现了信息隐藏; 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象类的实例解决问题; 8.数据的逻辑结构,简称为数据结构,有： 1线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继; 2非线性结构,一个结点可能有多个直接前趋和后继; 9.数据的存储结构有： 1顺序存储,把逻辑相邻的结点存储在物理上相邻的存储单元内; 2链接存储,结点间的逻辑关系由附加指针字段表示; 3索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引; 4散列存储,按结点的关键字直接计算出存储地址; 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间辅助存储空间；易于理解、编码、调试; A—熟练掌握B—理解C—了解 第一章：绪论 1. 基本概念： 包括数据的逻辑结构、数据的存储结构和数据的相关运算。C 四类数据组织结构：集合、线性表、树形、图状结构C 数据的存储方式：顺序存储和链式存储。B 2.算法和分析 算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B 本章重点：分析算法时间复杂度 例1. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 D 例2. 以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 A． 例3.．求下段程序的时间复杂度： void mergesort(int i, int j){ int m; if(i!=j){ m=(i+j)/2; mergesort(i,m); mergesort(m+1,j); merge(i,j,m);} } 其中mergesort()用于对数组a[n]归并排序，调用方式为mergesort(0,n-1);，merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为。 解：分析得到的时间复杂度的递归关系： 为merge（）所需的时间，设为cn（c为常量）。因此 令，有 有 第二章：线性表 1.线性表的基本运算：….. C 2.线性表的顺序存储（利用静态数组或动态内存分配）。相应的表示与操作 A 3.线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。 A 4.顺序存储与链式存储的比较：基于时间的考虑--分别适用于静态的和动态的操作：比如静态查找和插入删除）；基于空间的考虑-- ……. B 这也适用于后面用两种方式存储的其他数据结构。 ★本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。 例4．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 void Union(LinkList la, LinkList lb) ∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。 { pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针 la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。 while(pa!=null && pb!=null) ∥当两链表未访问结束 if(pa->data<=pb->data) { q=pa->next; ∥将pa 的后继结点暂存于q。 pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=q; ∥恢复pa为当前待比较结点。 } else{ q=pb->next;∥将pb 的后继结点暂存于q。 pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=q; ∥恢复pb为当前待比较结点。 } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {q=pa->next; pa->next=la->next; la->next=pa; pa=q; } while(pb!=null) {q =pb->next; pb->next=la->next; la->next=pb; pb=q; } }∥算法Union结束。 注意： （1）此处q用作暂存后继结点，操作后pa或pb还回原指向位置；这与我们原来不改变pa或pb的指向， 数据构造复习资料 一、填空题 1. 数据构造是一门研究非数值计算旳程序设计问题中计算机旳操作对象以及它们之间旳关系 和运算等旳学科。 2. 数据构造被形式地定义为(Ｄ, R)，其中D是数据元素旳有限集合,R是D上旳关系有限集合。 3. 数据构造包括数据旳逻辑构造、数据旳存储构造和数据旳运算这三个方面旳内容。 ４. 数据构造按逻辑构造可分为两大类,它们分别是线性构造和非线性构造。 ５. 线性构造中元素之间存在一对一关系,树形构造中元素之间存在一对多关系，图形构造中元素之间存在多对多关系。 6. 在线性构造中,第一种结点没有前驱结点，其他每个结点有且只有1个前驱结点；最终一种结点没有后续结点，其他每个结点有且只有1个后续结点。 ７. 在树形构造中，树根结点没有前驱结点,其他每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其他每个结点旳后续结点数可以任意多种。 ８. 在图形构造中，每个结点旳前驱结点数和后续结点数可以任意多种。 9．数据旳存储构造可用四种基本旳存储措施表达,它们分别是次序、链式、索引和散列。 １0. 数据旳运算最常用旳有5种,它们分别是插入、删除、修改、查找、排序。 1１. 一种算法旳效率可分为时间效率和空间效率。 12．在次序表中插入或删除一种元素,需要平均移动表中二分之一元素,详细移动旳元素个数与表长和该元素在表中旳位置有关。 13. 线性表中结点旳集合是有限旳,结点间旳关系是一对一旳。 14. 向一种长度为n旳向量旳第ｉ个元素(1≤i≤n+１)之前插入一种元素时，需向后移动ｎ-i＋１个元素。1５．向一种长度为ｎ旳向量中删除第i个元素(1≤ｉ≤n)时,需向前移动ｎ-i 个元素。 16. 在次序表中访问任意一结点旳时间复杂度均为 O(１），因此,次序表也称为随机存取旳数据构造。17．次序表中逻辑上相邻旳元素旳物理位置必然相邻。单链表中逻辑上相邻旳元素旳物理位置不一定相邻。 18.在单链表中,除了首元结点外,任一结点旳存储位置由其直接前驱结点旳链域旳值指示。 １9．在n个结点旳单链表中要删除已知结点*p,需找到它旳前驱结点旳地址，其时间复杂度为O（n)。 ２0. 向量、栈和队列都是线性构造,可以在向量旳任何位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素。 21. 栈是一种特殊旳线性表，容许插入和删除运算旳一端称为栈顶。不容许插入和删除运算旳一端称为栈底。 2２. 队列是被限定为只能在表旳一端进行插入运算，在表旳另一端进行删除运算旳线性表。 23. 不包括任何字符（长度为0)旳串称为空串；由一种或多种空格(仅由空格符)构成旳串称为空白串。 24. 子串旳定位运算称为串旳模式匹配;被匹配旳主串称为目旳串，子串称为模式。 25. 假设有二维数组A6×8，每个元素用相邻旳6个字节存储,存储器按字节编址。已知A旳起始存储位置（基地址)为10０0，则数组Ａ旳体积(存储量)为 28８ B ；末尾元素A57旳第一种字节地址为１282 ;若按行存储时,元素A14旳第一种字节地址为 (8＋4)×6+1000=１07２;若按列存储时，元素A4７旳第一种字节地址为 (6×7＋4）×６＋100０）＝１276 。 ２6．由３个结点所构成旳二叉树有５种形态。 27．一棵深度为６旳满二叉树有 n1＋n2=０+ ｎ2= ｎ０-１=31 个分支结点和 26-1＝32 个叶子。 注:满二叉树没有度为1旳结点，因此分支结点数就是二度结点数。 一、简答题 1、链表：链表就是一串存储数据的链式构造。链式的优点在于，每个数据之间都是相关联的。 2、线性构造： 线性构造是一个有序数据元素的集合。常用的线性构造有：线性表，栈，队列，双队列，数组，串。 3、树及二叉树 二叉树是每个结点最多有两个子树的有序树； 树是由n〔n>=1〕个有限节点组成一个具有层次关系的集合。 树和二叉树的2个主要差异： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。 4、堆 堆通常是一个可以被看做一棵树的数组对象。堆总是满足以下性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。 5、二叉排序树 二叉排序数的〔递归〕定义：1、假设左子树非空，那么左子树所有节点的值均小于它的根节点； 2、假设右子树非空，那么右子树所有节点的值均大于于它的根节点； 3、左右子树也分别为二叉 排序树。 二、应用题 1、树及二叉树 ①前中后序遍历序列 一、前序、中序遍历，求后序遍历 例：前序遍历: GDAFEMHZ中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。 在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树， 并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点 就是右子树的根节点。 ②树及二叉树的转换 树转换为二叉树： 二叉树转换为树： ③二叉树线索化 注意： 图中的实线表示指针，虚线表示线索。 结点C的左线索为空，表示C是中序序列的开场结点，无前趋； 结点E的右线索为空，表示E是中序序列的终端结点，无后继。 线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。 一、单选题（共20题，40分） 1、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素 个数为（）。（2.0） A、 8 B、 63.5 C、 63 D、 7 正确答案： B 2、在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）。 （2.0） A、 O(1) B、 O(n) C、O(n²) D、 O(log₂n) 正确答案： B 3、根据一组关键字(56, 42, 50, 64, 48)依次插入结点生成一棵AVL树，当插入到值为0的结点时需要进行旋转调整。（2.0） A、 42 B、 50 C、 64 D、 48 正确答案： B 4、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。（2.0） A、 n B、 n+1 C、 (n-1)/2 D、 (n+1)/2 正确答案： D 5、在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。 （2.0） A、 n-i B、 n-i+l C、 n-i-1 D、 i 正确答案： A 6、稀疏矩阵一般的压缩存储方法有两种，即（）。（2.0） A、二维数组和三维数组 B、三元组和散列 C、三元组和十字链表 D、散列和十字链表 正确答案： C 7、以下关于线性表的说法不正确的是______。（2.0） A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。 正确答案： C 8、在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个结点从小到大排序 正确答案： A 9、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相同，则该二叉树一定满足（）。 （2.0） A、所有的结点均无左孩子 B、所有的结点均无右孩子 C、只有一个叶子结点 D、是任意一棵二叉树 正确答案： C 10、如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（）。（2.0） A、中序 B、前序 C、后序 D、层次序 正确答案： B 第一章概论自测题答案 一、填空题 1. 数据构造是一门探讨非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和运算等的学科。 2. 数据构造被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据构造包括数据的逻辑构造、数据的存储构造和数据的运算这三个方面的内容。 4. 数据构造按逻辑构造可分为两大类，它们分别是线性构造和非线性构造。 5. 线性构造中元素之间存在一对一关系，树形构造中元素之间存在一对多关系，图形构造中元素之间存在多对多关系。 6．在线性构造中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最终一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形构造中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以随意多个。 8. 在图形构造中，每个结点的前驱结点数和后续结点数可以随意多个。9．数据的存储构造可用四种根本的存储方法表示，它们分别是依次、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （ B ）1. 非线性构造是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一 关系 （ C ）2. 数据构造中，及所运用的计算机无关的是数据的 构造； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （ C ）3. 算法分析的目的是： A) 找出数据构造的合理性 B) 探讨算法中的输入和输出的关系 C) 分析算法的效率以求改良 D) 分析算法的易懂性和文档性 （ A ）4. 算法分析的两个主要方面是： A) 空间困难性和时间困难性 B) 正确性和简明性 C) 可读性和文档性 D) 数据困难性和程序困难性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （ B ）6. 计算机算法必需具备输入、输出和 等5个特性。 A) 可行性、可移植性和可扩大性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和平安性 三、简答题 1. 简述线性构造及非线性构造的不同点。 答：线性构造反映结点间的逻辑关系是 一对一的，非线性构造反映结点间的逻辑关系是多对多的。 2．数据构造的常见的四种存储方式。 答：依次 、 链式 、 索引 和 散列 。 3. 数据构造的逻辑构造主要有哪两大类，详细是什么？ 答：主要分为线性构造和非线性构造，其中线性构造反映结点间的逻辑关系是 一对一的，非线性构造反映结点间的逻辑关系是多对多的。非线性构造又包含树构造和图构造 四、分析下面各程序段的时间困难度 2. s=0; for i=0; i《数据结构》复习资料
数据结构复习
数据结构复习资料(题目和参考答案)
数据结构期末复习重点知识点总结
数据结构复习资料
数据结构复习资料(亲自整理)
(完整word版)数据结构复习提纲
数据结构 复习重点
数据结构期末复习重点知识点总结
数据结构复习笔记
数据结构复习要点
2023年数据结构C语言版知识点复习资料
数据结构复习资料(亲自整理)
数据结构复习材料
数据结构期末复习章节试题附复习资料
相关主题
文本预览