数据结构复习整理.docx
- 文档编号:3168459
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:22
- 大小:667.23KB
数据结构复习整理.docx
《数据结构复习整理.docx》由会员分享,可在线阅读,更多相关《数据结构复习整理.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构复习整理
第一章
1、数据是描述客观事物的数、字符及能输入计算机并能处理的符号的集合。
数据元素是数据的基本单位。
数据对象是具有相同性质的数据元素的集合。
是数据的一个子集。
数据结构是带有结构的灵气元素的集合。
2、数据结构与算法是相辅相成、缺一不可的两个方面。
3、数据存储结构:
顺序、链式、索引、散列。
逻辑结构:
线性和非线性。
4、线性结构特征:
存在一对一的关系,且结构中仅有一个开始结点和一个终端结点。
其余结点仅有一个直接前趋和一个直接后继。
非线性结构特征:
一对多或多对多关系,即一个结点可能有多个直接前趋和多个直接后继。
5、算法+数据结构=程序。
6、数据结构包括的内容:
逻辑结构、存储结构及运算。
7、数据类型:
是一个值的集合和定义在这个值集上的一组操作的总称。
分为原子型和结构类型两种。
8、算法五准则:
输入、输出、有穷性、确定性、可行性。
9、如何评算法优劣:
算法的正确性;时间复杂性;空间复杂性;算法易于理解、易于调试。
即可读性和可操作性。
第二章
1、线性表第i个元素的存储位置LOC(ai)=LOC(a1)+(i-1)*d
2、顺序表是一种随机存储结构。
3、顺序表中,要访总第i个结点,只需访问L.data[i-1]就可以了。
若需要置空表(初始化),仅需将表长置为0,即L.length=0。
4、SeqList*P,这里P为指针变量。
引用成员用->表示,若为SeqList*P,上用成员用”.”表示。
5、顺序表中在第i个元素前插入一个新元素。
需要进行n-i+1次移动。
等概率情况下,插入元素平均移次次数为n/2。
删除元素平均移动次数为n-1/2。
6、单链表两个域:
数据域和指针域。
7、建立单链表的两种方法:
头插法和尾插法。
8、将长度为n的单链表链接在长度为m的单链表后的算法时间复杂度为O(m)。
9、循环链表相对于单链表,单链表只能从i结点及i结点以后的结点进行查找。
不能找i结点以前的结点。
循环链表可以解决这个问题。
10、对于在表的首、尾两端进行插入的操作线性表,宜采用的存储结构为用尾指针表示的单循环链表。
第三章
1、栈的链式存储结构称为链栈,它是运算受限的单链表,其插入和删除操作限制在表头进行,因此不必设置头结点,将单链表的头指针head改为栈顶指针top即可。
2、判定栈满真题:
3、顺序栈的基本运算
(1)置栈空
voidInitStack(SeqStack*S){//将顺序栈置空S->top=-1;}
(2)判栈空
intStackEmpty(SeqStack*S){returnS->top==-1;}
(3)判栈满
intStackFull(SeqStack*SS){returnS->top==StackSize-1;}
(4)进栈
voidPush(S,x)
{if(StackFull(S))Error("Stackoverflow");//上溢,退出运行
S->data[++S->top]=x;//栈顶指针加1后将x入栈}
(5)退栈
DataTypePop(S)
{if(StackEmpty(S))Error("Stackunderflow");//下溢,退出运行
returnS->data[S->top--];//栈顶元素返回后将栈顶指针减1}
(6)取栈顶元素
DataTypeStackTop(S){if(StackEmpty(S))
Error("Stackisempty");returnS->data[S->top];}
4、链栈的运算
(1)置栈空VoidInitStack(LinkStack*S){S->top=NULL;}
(2)判栈空
intStackEmpty(LinkStack*S){returnS->top==NULL;}
(3)进栈
voidPush(LinkStack*S,DataTypex)
{//将元素x插入链栈头部
StackNode*p=(StackNode*)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//将新结点*p插入链栈头部
S->top=p;}
(4)退栈
DataTypePop(LinkStack*S)
{DataTypex;
StackNode*p=S->top;//保存栈顶指针
if(StackEmpty(S))
Error("Stackunderflow.");//下溢
x=p->data;//保存栈顶结点数据
S->top=p->next;//将栈顶结点从链上摘下
free(p);
returnx;}
(5)取栈顶元素
DataTypeStackTop(LinkStack*S)
{if(StackEmpty(S))
Error("Stackisempty.")
returnS->top->data;}
注意:
链栈中的结点是动态分配的,所以可以不考虑上溢,无须定义StackFull运算。
5、字符串回文判断(5个字符的话,前2个入栈,6个的话,前3个入栈)
6、把十进制数转换为d进制数
6.2递归:
一个直接调用自己或间接调用自己的函数,称为递归函数。
递归算法分为两步,第一步将规模较大的问题分解为一个或多个规模较小的子问题。
第二步确定一下或多个不需要分解、可直接求解的最小子问题。
第一步称为递归步骤,第二步称递归的终止条件。
7、求队列长度(两种情况)
7.1、队列是一种操作受限的线性表,允许插入的一端称队尾(real),允许删除的一端称为队头(front)。
队列的基本运算:
1)initqueue(q),置空队;2)queueempty(q),判队空; 3)queuefull(q),判队满; 4)enqueue(q,x),入队; 5)dequeue(q),出队; 6)queuefront(q),返回队头元素。
8、循环队列基本运算
9、链队列的基本运算
链队列的定义:
队列的链式存储结构简称为链队列。
它是限制仅在表头删除和表尾插入的单链表。
链队列的结构类型说明
注意:
增加指向链表上的最后一个结点的尾指针,便于在表尾做插入操作。
链队列示意图见上图,图中Q为LinkQueue型的指针。
(1)置空队:
voidInitQueue(LinkQueue*Q){Q->front=Q->rear=NULL;}
(2)判队空:
intQueueEmpty(LinkQueue*Q)
{returnQ->front==NULL&&Q->rear==Null;}
(3)入队
voidEnQueue(LinkQueue*Q,DataTypex)
{//将元素x插入链队列尾部
QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点
p->data=x;p->next=NULL;
If(QueueEmpty(Q))
Q->front=Q->rear=p;//将x插入空队列
Else{//x插入非空队列的尾
Q->rear->next=p;//*p链到原队尾结点后
Q->rear=p;//队尾指针指向新的尾}}
(4)出队
DataTypeDeQueue(LinkQueue*Q)
{DataTypex;QueueNode*p;
If(QueueEmpty(Q))
Error("Queueunderflow");//下溢
p=Q->front;//指向对头结点
x=p->data;//保存对头结点的数据
Q->front=p->next;//将对头结点从链上摘下
If(Q->rear==p)//原队中只有一个结点,删去后队列变空,此时队头指针已为空
Q->rear=NULL;
Free(p);//释放被删队头结点
returnx;//返回原队头数据}
(5)取队头元素
DataTypeQueueFront(LinkQueue*Q)
{if(QueueEmpty(Q))
Error("Queueifempty.");returnQ->front->data;}
注意:
①和链栈类似,无须考虑判队满的运算及上溢。
②在出队算法中,一般只需修改队头指针。
但当原队中只有一个结点时,该结点既是队头也是队尾,故删去此结点时亦需修改尾指针,且删去此结点后队列变空。
③以上讨论的是无头结点链队列的基本运算。
和单链表类似,为了简化边界条件的处理,在队头结点前也可附加一个头结点,
10、栈和队列进出排序
11、中缀表达琖转换为后缀表达式
12\12.如果一个栈的进栈序列是1,2,3,4且规定每个元素的进栈和退栈各一次,那么不可能得到的退栈序列_____。
A4,3,2,1B4,2,1,3C1,3,2,4D3,4,2,1
n参考答案B
12、阶乘公式:
当n=0,n!
=1;当n>0,n!
=n(n-1)!
第四章
1、稀疏矩阵一般压缩方法有两种:
三元组和十字链表。
2、完全二叉树根据孩子结点求父结点i-1/2。
一个二叉排序树,用中序遍历可以得到各结点递增序列。
3、在有向图的邻接表中,从一顶点出发的弧链接在同一链表中,邻接表中结点的个数恰为图中弧的数目,所以顶点入度之和为弧数和的一倍,若为无向图,同一条边有两个结点,分别出现在和它相关的两个顶点的链表中,因此无向图的邻接表中结点个数的边数的2倍。
3、任何一个无向连接图的最小生成树有一棵或多棵。
4、采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度,查找成功的asl是(n+1)/2;查找不成功的asl是(n-1)/2;
5、散列函数有一个共同性质,即函数值应当以同等概率取其值域的每个值。
1、二维数组W有8行(0..7)、4列(0..3),共32个元素。
每个元素占4个字节,共需要占128字节。
W[6,3]表示它是第7行第4列的元素(0..6,0..3),按行序存放的话,它的前面还有6个整行的数据外加该结点在最后一行还有3个元素在它之前,故在它之前二维数组的还有x个元素,其中
x=6*4+3=27
它的起始地址=数组起始地址+偏移量
=100+4*(6*4+3)
=100+108
=208
2、
3、11.设二维数组a[0…m-1][0…n-1]按列优先顺序存储在首地址为loc(a[0][0])的存储区域中,每个元素占d个单元,则a[i][j]的地址为________。
A.loc(a[0][0])+(j×n+i)×dB.loc(a[0][0])+(j×m+i)×d
C.loc(a[0][0])+((j-1)×n+i-1)×dD.loc(a[0][0])+((j-1)×m+i-1)×d
n参考答案B
第五章
*、树的三种存储结构:
孩子链表法、孩子兄弟链表法、双亲表示法。
1.1、度为h的二叉树上只有度为0和度为2的结点,则此二叉树中所包含的结点数至少为2h-1。
1.2(13)设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为___B___。
()
A.349
B.350
C.255
D.351
若设二叉树的高度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的节点都连续集中在最左边,这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。
对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
做这种题目你要知道二叉树的两个特点!
第k层的节点个数最多2^(k-1)个,高度为k层的二叉树,最多2^k-1个节点!
则在本题目中,共699个节点,因为是完全二叉树,2^10-1>699>2^9-1,所以高度为10,可以确定1到9层全满,节点总算为511,剩下的188个肯定为叶子节点!
第10层上的188个节点挂在第九层的188/2=94个节点上,则第九层剩下的2^(9-1)-94=162个也为叶子节点,最后总共188+162=350个叶子节点!
1,某二叉树的前根次序列遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为:
A、uwvtsB、vwutsC、wuvtsD、wutsv
请给出分析步骤,最好能把图画出来谢谢了
对于先序遍历stuwv,和中序遍历uwtvs可以这么分析:
规则:
1)先序遍历确定父节点
2)中序遍历确定左右子树
分析过程:
1、由前序遍历可知s为树的根
s
tuwv
2、结合中序遍历可知:
tuwv为s左子树的先序遍历,uwtv为s左子树的中序遍历
3、同理判断t为左子树的根,uw为t的左子树,v为t的右子树
s
t
uwv
4、递归判断t的左子树可知:
其先序遍历和中序遍历均为uw,判断u为子树的根节点,w为u的右孩子
s
/
t
/\
uv
\
w
由此可知其后序遍历为:
wuvts
2、已知在一段文字中共有A,B,C,D,E,F,G,H八种字,它们出现的次数分别是9,3,5,8,12,20,7,10,请画出哈夫曼树,并求出每个字符的哈夫曼编码
哈夫曼树 74
/ \
42 32
/ \ / \
23 19 12 20
/ \ / \
15 8 9 10
/ \
8 7
/ \
3 5
编码:
A(010)B(00000)C(00001)D(001)E(10)F(11)G(0001)H(011)
带权路径长度值为:
(3+5)*5+7*4+(8+9+10)*3+(12+20)*2=213
This is it!
!
!
求采纳
3、一棵哈夫曼树有19个节点,则其叶子结点的个数是个。
(N+1/2)。
4、有一个无向图的邻接表中,若表结点的个数是m,则图中边的条数是M/2。
第六章
1、一个具有N个顶点的有向图最多有n(n-1)条边。
2、一个具有N个顶点的无向图中,边的总数是N(N-1)/2。
第七章
*一、时间复杂度:
(1)直接插入、直接选择、冒泡排序算未能的时间复杂度为O(n2)。
冒泡排序若基本有序,时间复杂度为O(n)。
(2)快速、归并、堆排序算法时间复杂度为O(nlogn)。
平均比较次数最少的是快速排序。
二、稳定性:
(1)直接插入、冒泡、归并和基数排序算法是稳定的。
(2)直接选择、希尔、快速和堆排序算法是不稳定的。
三、辅助空间
(1)直接插入、直接选择、冒泡、希尔和堆排序算法要辅助空间为O
(1)。
(2)快速排序算法需要辅助空间为O(logn)。
(3)归并排序算法需要辅助空间为O(n)。
(若有1000个元素,希望快速找出N个最大值,最小值,用堆排序。
)
四、选取排序方法时考虑的主要因素:
(1)待排序的个数;
(2)记录本身的大小和存储结构;(3)关键字的分布;(4)对排序的稳定性要求;(5)时间和空间复杂度。
五、排序方法选取
(1)若排序的记录数目较小,可采用插入排序或选择排序。
(2)当N较大时,应采用快速排序、堆排序或归并排序。
(3)若待排序记录关键字基本有序,宜选用直接插入排序或冒泡排序。
(4)当N很大时,而且关键了较少时,采用链式基数排序较好。
(5)关键字比较次数记录的初始排列顺序无关的排序方法是选择排序。
*箱排序不需要比较关键字。
堆排序最坏的时间复杂度为nlgn。
如果N比较大时,最好不要选择直接插入排序。
*在线性表的顺序存储中,元素之间的逻辑关系是通过__相邻位置_决定的;在线性表的链接存储中,元素之间的逻辑关系是通过链接指针_决定的。
*多维数组和广义表是一种非常复杂的非线性结构,它们的逻辑特点是一个数据元素可能有多个直接前趋和多个直接后继。
*数组0[1……n]表示一个环形队列,设f的值为队列中第一个元素的位置,r的值为队列中
实际队尾元素的位置加1,并假定队列中至多只有n-1个元素,列中元素个数的公式为(n+r-f)modn
*内部排序的方法可以分为五类:
插入排序选择排序交换排序归并排序分配排序。
*拓朴排序的时间复杂度为(n+e).
1、插入排序
基本思想:
假设第一个关键字有序,从第二个开始与第一个比,i从2开始,i .算法描述 voidlnsertSort(SeqListR) {//对顺序表R中的记录R[1..n]按递增序进行插入排序 inti,j; for(i=2;i<=n;i++)//依次插入R[2],…,R[n] if(R[i].key //应在原有位置上 R[0]=R[i];j=i-1;//R[0]是哨兵,且是R[i]的副本 do{//从右向左在有序区R[1..i-1]中查找R[i]的插入位置 R[j+1]=R[j];//将关键字大于R[i].key的记录后移 j--; }while(R[0].key R[j+1]=R[0];//R[i]插入到正确的位置上 }//endif }//InsertSort 2、在选择排序、堆排序、快速排序和直接插入排序方法中,稳定的排序方法是: 直接插入排序。 3、分别采用堆排序、快速排序、直接插入排序和归并排序对初始状态为基本递增的有序的序列,按递增顺序排序,最省时间的排序方法是直接插入排序。 4在直接插入排序、希尔排序、直接选择排序、快速排序、堆排序、归并排序和基数排序中,不稳定的排序有直接选择排序、希尔排序、快速排序、堆排序。 平均比较次数最少的排序是快速排序。 需要内存空间最多的是基数排序。 5、对N个记录的排序文件进行起泡排序时,最少的比较次数是n-1。 6、在堆排序和快速排序中,若记录关键字基本正序(升序)或反序(降序),则选用堆排序。 若记录按关键字无序,则最好选用快速排序。 7、在所有的排序算法中,若初始记录关键字基本正序(升序),则选用直接插入排序。 若初始关键字基本反序(降序),则选用堆排序。 8、在快速排序、归并排序和堆排序等几种排序算法中,若仅从存储空间考虑,它们的优先顺序为堆排序、快速排序、归并排序。 9、对N个记录采用直接选择排序方法所执行的记录交换次数最多为N-1。 10、对N个记录进行堆排序,最坏情况下的执行时间为O(nlogN)。 11、快速排序基本思想: 设置两个指针i和j,它们初值分别为low和high,基准记录x=R[i],首先众j所指向的位置向前搜索第一个关键字小于基准x.key的记录存入当前i指向的位置上,i自增1,然后从i所指向的位置向后搜索,找到第一个关键字大于x.key的记录存入当前j所指向的位置上,j自减1,重复这两步,自至i等于j为止。 Eg: 5.一组记录的关键码为(46,79,56,38,40,84),则采用快速排序的方法,以第一个记录为基准得到的一次划分结果为。 快速排序为平均时间复杂度为nlogn。 最坏的情况为n^2 A.38,40,46,56,79,84B.40,38,46,79,56,84 C.40,38,46,56,79,84D.40,38,46,84,56,79参考答案C 40,79,56,38,84 40,56,38,79,84 40,38,56,79,84 40,38,46,56,79,84 12、14.任何一个基于“比较”的内部排序的算法,对6个元素进行排序,则在最坏情况下所需的比较次数至少为(A)。 A.10B.11C.21D.36 计算公式: (n-1)(n-2)/2 第八章 1、二分查找平均查找长度log2(n+1)-1。 Mid值计算(low+high)/2。 二分查找在查找失败时所需比较的关键字个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。 即为: 「lg(n+1)(取不小于lg(n+1)的整数的意思,右半边符号打不出) 2、散列存储处理冲突的方法: 当不可避免发生冲突时,就必须对冲突加以解决,使发生冲突的同义词能存储到表中。 通常有两类方法处理冲突: 开放定址法和拉链法。 前者是将所有结点均存放在散列表T[0..m-1]中,后者是将互为同义词的结点链成一个单链表,而将此链表的头指针放在散列表中。 开放定址法的一般形式为: hi=(h(key)+di)%m1≤i≤m-1 开放定址法处理冲突查找长度高于拉链法的查找长度,但它们都比其它方法的查找长度小。 一、.画出对长度为18的有序的顺序表进行二分查找的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 答: 等概率情况下,查找成功的平均查找长度为: ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时,最多的关键字比较次树不超过判定树的深度,此处为5. 二、二叉排序树求平均查找长度。 (按层查找计算) 三、B-树 一棵m(m≥3)阶的B-树是满足如下性质的m叉树: (1)每个结点至少包含下列数据域: (j,P0,Kl,P1,K2,…,Ki,Pi)其中: j为关键字总数Ki(1≤i≤j)是关键字,关键字序列递增有序: K1 Pi(0≤i≤j)是孩子指针。 对于叶结点,每个Pi为空指针。 (2)所有叶子是在同一层上,叶子的层数为树的高度h。 3、每个非根结点中所包含的关键字个数j满足: 4、(4)若树非空,则根至少有1个关键字,故若根不是叶子,则它至少有2棵子树。 根至多有m-1个关键字,故至多有m棵子树。 5、B树上的插入操作
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习 整理