十套数据结构试题及答案55426知识讲解
十套数据结构试题及答案55426
数据结构试卷（一）
一、单选题（每题 2 分，共20分）
1.栈和队列的共同特点是( a )。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2.用链接方式存储的队列，在进行插入运算时( d ).
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D.头、尾指针可能都要修改
3.以下数据结构中哪一个是非线性结构？( d )
A. 队列
B. 栈
C. 线性表
D. 二叉树
4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放
位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。c
A．688 B．678 C．692 D．696
5.树最适合用来表示( c )。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
6.二叉树的第k层的结点数最多为( d ).
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]
中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d )
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 c
n） D. O
A. O（1）
B. O（n）
C. O（1og
2
（n2）
9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选
用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）
个，
A．1 B．2 C．3 D．4
10.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通
图。
A.5
B.6
C.7
D.8
二、填空题（每空1分，共26分）
1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_
易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___3 0（n）
_____。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中
所含的结点数为_____9_____个，树的深度为_____3______，树的度为
____2_____。
4.后缀算式9 2 3 +- 10 2 / -的值为____3__-1____。中缀算式（3+4X）-2Y/3对
应的后缀算式为______3 4X* + 2Y* / -_________________________。5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右
孩子的两个指针。在这种存储结构中，n个结点的二叉树共有____n_2n___个指针域，其中有_____n-1___个指针域是存放了地址，有
________3__n+1______个指针是空指针。
6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，
所含边结点分别有___e+1_e___个和____e+1__2e__个。
7.AOV网是一种________有向无回路___________的图。
8.在一个具有n个顶点的无向完全图中，包含有____n-1_n(n-1)/2___条边，在
一个具有n个顶点的有向完全图中，包含有____n-1___n(n-1)_条边。
9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同
一余数的元素成为一个子表，则得到的四个子表分别为
___________(12,40)_________________、_______(23,63,55)________、
_______(74)________________和_________( )_________________。
10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原
树的高度______增加1____。
1.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为
___0（n/2）___ O(log2n)__，整个堆排序过程的时间复杂度为
__0（1）__ O(nlog2n)____。
11.在快速排序、堆排序、归并排序中，____堆排序__归并排序___排序是稳定
的。
三、计算题（每题 6 分，共24分）
1.在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该
线性表。
data 60 50 78 90 34 40
next 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）
2.请画出下图的邻接矩阵和邻接表。
1.邻接矩阵：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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)20
4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。
四、阅读算法（每题7分，共14分）
1.LinkList mynote(LinkList L)
{//L是不带头结点的单链表的头指针
if(L&&L->next){
q=L；L=L－>next；p=L；
S1： while(p－>next) p=p－>next；
S2： p－>next=q；q－>next=NULL；
}
return L；
}
请回答下列问题：
（1）说明语句S1的功能；判断p的下一节点是否为空，如不为空p则指向下一节点查询链表的尾节点
（2）说明语句组S2的功能；使P的下一节点赋值给q，并令q的下一节点为空指针。将第一个节点链接到链表的尾部，作为新的尾节点（3）设链表表示的线性表为（a1,a2, …,a n）,写出算法执行后的返回值所表示的线性表。a2,a3,…an,a1
2.void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout<
}
}
该算法的功能是：判断是否为满二叉树递归的后序遍历链式存储的二叉树五、算法填空（共8分）
二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return ____item__true_____;}
else if(item
return Find(______BST->data____BST-
>left____,item);
else return Find(_______item____BST->right____,item);
}//if
}
六、编写算法（共8分）
统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x){
int count;
node *head,*p;
head = HL;
p=head->next;
if(head->data!=null)
{
while(p->next)
{
if(p->data==x)count++;
}
}
}
Struct node HL
{
elemtype data;
Struct node *next;
}node;
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i为计数器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循环时i中的值即为x结点个数
return i;
}//CountX
数据结构试卷（一）参考答案
一、选择题（每题2分，共20分）
1.A
2.D
3.D
4.C
5.C
6.D
7.D
8.C
9.D 10.A
二、填空题（每空1分，共26分）
1.正确性易读性强壮性高效率
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7.有向无回路
8.n(n-1)/2 n(n-1)
9.（12，40）（）（74）（23,55，63）
10.增加1
11.O(log
2n) O(nlog
2
n)
12.归并
三、计算题（每题6分，共24分）
2.线性表为：（78，50，40，60，34，90）
3.邻接矩阵：
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
邻接表如图11所示：
图11
4.用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
5. 见图12
四、 读算法（每题7分，共14分）
1.
（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a 2,a 3,…
,a n ,a 1）
2. 递归地后序遍历链式存储的二叉树。
五、 法填空（每空2分，共8 分）
true BST->left BST->right
六、 编写算法（8分）
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i 为计数器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循环时i 中的值即为x 结点个数
return i;
}//CountX
数据结构试卷（二）
一、选择题(24分)
1．下面关于线性表的叙述错误的是（ ）。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
2．设哈夫曼树中的叶子结点总数为m ，若用二叉链表作为存储结构，则该哈夫曼树中总共
有（ ）个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m
3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F 和R ，头指针F 总是指向队头元
素的前一位置，尾指针R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。
(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M
4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-1
6．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
(A) 9 (B) 10 (C) 11 (D) 12
7．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
(A) n-1 (B) n (C) n+1 (D) 2n-1
8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
(A) 2，3，5，8，6 (B) 3，2，5，8，6
(C) 3，2，5，6，8 (D) 2，3，6，5，8
二、填空题(24分)
1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和
__________________________。
2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack;
void push(sqstack &stack,int x)
{
if (stack.top==m-1) printf(“overflow”);
else {____________________;_________________;}
}
3.中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。
4.快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数
为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。
6.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。
7.设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建
立的初始堆为___________________________。
8．已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是
，BFS遍历的输出序列是
三、应用题(36分)
1．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
3．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
4．设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。
6．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
四、算法设计题(16分)
1．设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。
2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
数据结构试卷（二）参考答案
一、选择题
1.D
2.B
3.C
4.A
5.A
6.C
7.B 8.C
二、填空题
1.构造一个好的HASH函数，确定解决冲突的方法
2.stack.top++，stack.s[stack.top]=x
3.有序
4.O(n2)，O(nlog2n)
5.N0-1，2N0+N1
6.d/2
7.(31，38，54，56，75，80，55，63)
8.(1，3，4，5，2)，(1，3，2，4，5)
三、应用题
1.(22，40，45，48，80，78)，(40，45，48，80，22，78)
2.q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;
3.2,ASL=91*1+2*2+3*4+4*2)=25/9
4.树的链式存储结构略，二叉树略
5.E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}
6.略
四、算法设计题
1.设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的
时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i while (i while (i } r[i]=x; } 2.设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用 链式存储结构表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 数据结构试卷（三） 一、选择题(每题1分，共20分) 1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是（）。 (A) 线性结构(B) 树型结构(C) 物理结构(D) 图型结构 2．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4) 数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 第一章数据结构概述 基本概念与术语 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、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结点的直接后继结点。头指针是它的充分必要的信息。单链表是一种单向的结构。 *15、双链表：每个结点中增加了一个prior，用来指向该点的直接前趋结点。它是一种双向、对称的结构。 *16、循环链表：是一种首尾相接的链表。单循环链表形成一个next链环，而双循环链表形成next链环和prior链环。 *17、存储密度：是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。顺序表的存储密度为1，而链表的存储密度小于1。 *18、栈：只允许在一端进行插入、删除运算的线性表，称为“栈”（stack）。 *19、LIFO表：即后进先出表，修改操作按后进先出的原则进行。譬如栈就是一种LIFO 表。 *20、顺序栈：采用顺序存储结构的栈，称为顺序栈。 *21、链栈：采用链式存储结构的栈，称为链栈。 *22、队列：只允许在一端进行插入、另一端进行删除运算的线性表，称为“队列”（queue）。*23、FIFO表：即先进先出表。譬如队列就是一种FIFO表。 *24、顺序队列：采用顺序存储结构的队列，称为顺序队列。 *25、循环队列：为克服顺序队列中假上溢现象，将向量空间想象为一个首尾相接的圆环， 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结 第一章概论 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.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1 数据结构基本知识 数据（Data） 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。随着计算机应用领域的扩大，数据的范畴包括： 整数、实数、字符串、图像和声音等。 数据元素（Data Element） 数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。 数据项是具有独立含义的最小标识单位。 数据结构（Data Structure） 数据结构指的是数据之间的相互关系，即数据的组织形式。 1．数据结构一般包括以下三方面内容： ①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）； 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。 ③数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的 检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。 所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。 为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。 【例1．1】学生成绩表，见下表。 注意：在表中指出数据元素、数据项、开始结点和终端结点等概念 （1）逻辑结构 表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。 表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数值、字符等）的集合。 数据元素（数据成员）是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等 数据对象具有相同性质的数据元素（数据成员）的集合 数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure = {D, R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 数据类型是指一种类型，以及定义在这个值集合上的一组操作的总称。 判断一个算法的优劣主要标准：正确性、可使用性、可读性、效率、健壮性、简单性。 算法效率的衡量方法：后期测试，事前估计 算法分析是算法的渐进分析简称 数据结构包括“逻辑结构”和“物理结构”两个方面(层次): 逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构” 线性表的定义：n（≥ 0）个表项的有限序列L =（a1, a2, …, an）ai是表项，n是表长度。第一个表项是表头，最后一个是表尾。 线性表的特点：表中元素的数据类型相同；线性表中，结点和结点间的关系是一对一的，有序表和无序表线性表的存储方式。一，顺序存储方式，二，链表存储方式。 顺序表的存储表示有2种方式：静态方式和动态方式。 顺序表的定义是：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。 顺序表的特点：用地址连续的一块存储空间顺序存放各表项，各表项的逻辑顺序与物理顺序一致，对各个表项可以顺序访问，也可以随机访问。 单链表是一种最简单的链表表示，也叫线性链表，用她来表示线性表时，用指针表示结点间的逻辑关系。特点：是长度可以很方便地进行扩充。 连续存储方式（顺序表）特点：存储利用率高，存取速度快缺点：插入、删除等操作时需要移动大量数据： 链式存储方式（链表）特点：适应表的动态增长和删除。缺点：需要额外的指针存储空间 单链表的类定义：多个类表达一个概念(单链表)。分为：链表结点(ListNode)类，链表(List)类。 循环链表的概念：是另一种形式的表示线性表的链表，它的结点结构与单链表相同，与单链表不同的是链表中表尾结点的LINK域中不是NULL，而是存放了一个指向链表开始结点的指针，这样，只要知道表中任何一个结点的地址，就能遍历表中其他任何一结点。 双向链表的概念：在双向链表的没饿结点中应有两个链接指针作为它的数据成员：1LINK指示它的前驱结点，RLINK 指示它的后继结点，因此，双向链表的每个结点至少有3个域：1LINK(前驱指针) DADA（数据）RLINK（后继指针）。栈：定义为只允许在表的末端进行插入和删除的线性表。特点是：后进先出。 递归的定义：若一个对象部分地包含它自己，或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。以下三种情况常常用到递归方法一。定义是递归的二。数据结构是递归的三问题的解法是递归的。 队列：队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头，允许插入的一端叫做队尾。特性：先进先出。 优先级队列：是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维数组的推广。 多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界，因此它比其他复杂的非线性结构简单。 字符串是n ( ≥ 0 ) 个字符的有限序列，记作S : “c1c2c3…cn”其中，S 是串名字c1c2c3…cn”是串值ci 是串中字符n 是串的长度，n = 0 称为空串。 广义表是n ( ≥0 ) 个表元素组成的有限序列，记作LS (a1, a2, a3, …, an)，LS 是表名，ai 是表元素，可以是表（称为子表），可以是数据元素（称为原子）。n为表的长度。n = 0 的广义表为空表。n > 0时，表的第一个表元素称为广义表的表头（head），除此之外，其它表元素组成的表称为广义表的表尾（tail 有根树：一棵有根树T，简称为树，它是n (n≥0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树，记作T={ 空集n=0 {r,T1,T2….Tn},n>0数据结构与算法基础知识总结
(完整版)非常实用的数据结构知识点总结
数据结构复习要点整理版
数据结构基础知识大全
2021年自考02331数据结构重点总结最终修订
数据结构基础知识整理
大学数据结构期末知识点重点总结
数据结构基本知识.
数据结构知识点整理