数据结构复习资料
一．单项选择题
1．算法指的是（ ）。
A ．计算方法
B ．排序方法
C ．特定问题求解步骤的描述
D ．调度方法 2．下列数据结构中，（ ）是非线性结构。
A ．栈
B ．队列
C ．完全二叉树
D ．堆
3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储
方式最节省时间。
A ．顺序表
B ．双向链表
C ．单循环链表
D ．带头结点的双循环链表 4．队列的操作原则是（ ）
A ．先进先出
B ．后进先出
C ．先进后出
D ．不分顺序 5．栈和队列的共同特点是（ ）。
A ．都是先进先出
B ．都是先进后出
C ．都是只允许在端点处插入和删除
D ．没有共同点 6．在一棵高度为k 的满二叉树中，结点总数为（ ）。 A ．2k-1 B ．2k C ．2k -1 D ．
⎣⎦12log +k
7．在下列存储形式中，哪一个不是树的存储形式？（ ）
A ．双亲链表表示法
B ．孩子链表表示法
C ．孩子兄弟链表表示法
D ．顺序存储表示法 8．n 个结点的完全有向图含有边的数目为（ ）。
A ．n*n
B ．n*(n+1)
C ．n/2
D ．n*(n-1） 9．n 个顶点的强连通图至少有（ ）条边。
A ．n
B ．n-1
C ．n+1
D ．n(n-1) 10、高度为k 的二叉树的最大结点数为（ ）。
A 、2k
B 、2k-1
C 、2k –1
D 、2k-1–1 11、下列哪一种图的邻接矩阵是对称矩阵？（ ）
A 、有向图
B 、无向图
C 、AOV 网
D 、AO
E 网 12、在下列存储形式中，哪一个不是树的存储形式？（ ） A 、双亲表示法 B 、孩子表示法
C 、孩子兄弟表示法
D 、顺序存储表示法 13、下面哪一方法可以判断出一个有向图是否有环。（ ） A 、深度优先遍历 B 、拓扑排序
C 、求最短路径
D 、广度优先遍历 14．适用于折半查找的表的存储方式及元素排列要求为（ ）。 A ．链接方式存储，元素无序 B ．链接方式存储，元素有序
C ．顺序方式存储，元素无序
D ．顺序方式存储，元素有序 15、一个算法应该是（ ）。
A 、程序
B 、特定问题求解步骤的描述
C 、要满足五个基本特性
D 、A 和C 16、算法分析的两个主要方面是（ ）。
A 、空间复杂度和时间复杂度
B 、正确性和简明性
C 、可读性和文档性
D 、数据复杂性和程序复杂性 17、以下数据结构中，（ ）是非线性数据结构。
A 、树
B 、字符串
C 、队
D 、栈
18．下列算法中（）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A．快速排序B．希尔排序C．堆排序D．冒泡排序
19．采用顺序查找法查找长度为n的线性表，查找成功的平均查找长度为（）A．n B．n/2 C．(n-1)/2 D．(n+1)/2
20．设广义表L = （（a, b, （x, y））, （a, b, （x, y））），则head（head（tail（L）））为（）A．a B．（x, y）C．（a, b, （x, y））D．L
21、最小生成树指的是（）
A、由连通网所得到的边数最少的生成树
B、由连通网所得到的顶点相对较少的生成树
C、连通网中所有生成树中权值之和为最小的树
D、连通网的极小连通子图
22、对线性表进行折半查找时，要求线性表必须（）。
A、以顺序方式存储
B、以顺序方式存储，且数据元素有序
C、以链接方式存储
D、以链接方式存储，且数据元素有序
23．下面关于串的叙述中，正确的是（）
A．一个串的字符个数即为该串的长度B．一个串的长度至少为1
C．空串是一个由空格字符组成的串D．两个串s1和s2若长度相同，则这两个串相等24．排序的算法很多，若按排序的稳定性和不稳定性分类，则（）是不稳定排序。
A、冒泡排序
B、归并排序
C、直接插入排序
D、希尔排序
25．线性表是具有n个（）的有限序列。
A．表元素B．字符C．数据元素D．数据项
26．栈的操作原则是（）
A．先进先出B．后进先出C．后进后出D．不分顺序
27．下列排序算法中，在待排数据已有序时，花费时间反而最多的是（）排序。
A．冒泡排序B．希尔排序C．快速排序D．堆排序
28．设无向图的顶点个数为n，则该图最多有（）条边
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n2
29．队列的操作原则是（）
A．先进先出B．后进先出C．先进后出D．不分顺序
30．以下（）不是队列的基本运算。
A．从队尾插入一个新元素B．读取队头元素的值
C．判断一个队列是否为空D．从队列中删除第i个元素
31、（）是数据不可分割的最小单位。
A、数据结构
B、数据对象
C、数据元素
D、数据项
32、线性表采用链式存储时，其地址（）。
A、必须是连续的
B、一定是不连续的
C、部分地址必须是连续的
D、连续与否均可以
33、带头结点的单链表（头指针为head）为空的判定条件是（）。
A、head==NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
34．对线性表，在下列（）情况下应当采用链表表示。
A．经常需要随机地存取元素B．经常需要插入和删除操作
C．表中元素需要占据一片连续的存储空间D．表中元素的个数不变
35．将含有100个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为1，编号为71的结点的双亲的编号为（）。
A．34 B．35 C．36 D．无法确定
36．按照二叉树的定义，具有3个结点的二叉树有（）种。
A．3 B．4 C．5 D．6
37．在数据结构中，从逻辑上可以把数据结构分成（）
A．动态结构和静态结构B．紧凑结构和非紧凑结构
C．线性结构和非线性结构D．内部结构和外部结构
38．下面关于串的叙述中，正确的是（）
A．一个串的字符个数即为该串的长度B．一个串的长度至少为1
C．空串是一个由空格字符组成的串D．两个串s1和s2若长度相同，则这两个串相等
39．下列广义表是线性表的是（）
A．L = （x, （x, y）, x）B．L = （a, （a, b））
C．L = （x, y , z）D．L = （x, L, y）
40．n个顶点的强连通图至少有（）条边。
A．n B．n-1 C．n+1 D．n(n-1)
41．当初始序列已经按键值有序，用直接插入算法对其进行排序，需要比较的次数为（）A．n-1 B．n C．log2n D．nlog2n
42、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A、单链表
B、仅有头指针的单循环链表
C、双向链表
D、仅有尾指针的单循环链表
43、常对数组进行的两种基本的操作是（）。
A、建立与删除
B、索引和修改
C、查找和修改
D、查找和索引
44．下列广义表是线性表的是（）
A、L = （x, （x, y）, x）
B、L = （a, （a, b））
C、L = （x, y , z）
D、L = （x, L, y）
45．采用顺序查找法查找长度为n的线性表，查找成功的平均查找长度为（）
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
二．判断题
1．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。（）
2．在单链表中要访问某个结点，只要知道该结点的指针即可，因此，单链表是一种随机存取结构。（）3．栈和队列都是线性表，只是在插入和删除时受到了一些限制。（）
4．串是一种数据对象和操作都特殊的线性表。（）
5．广义表是线性表的推广，是一类线性数据结构。（）
6．二叉树中不存在度大于2的结点，当某个结点只有一棵子树时，没有左右子树之分。（）
7．将一棵树转化为二叉树后，根结点没有左子树。（）
8．有回路的图不能进行拓扑排序。（）
9．装填因子是散列表的一个重要参数，它反映散列表的装满程度。（）
10．内部排序中的快速排序方法，在任何情况下均可得到最快的排序效果。（）
三．填空题
1．顺序存储结构是通过表示元素之间的关系的。
2．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是。
3．一个字符串中称为该串的子串。
4．求图的最小生成树有两种算法，算法适合于求边稀疏的网的最小生成树，算法适
合于求边稠密的网的最小生成树。
5．栈的特点是，队列的特点是，栈和队列都是操作受限的线性表。6．对矩阵采用压缩存储的目的是为了。
7．深度为8的完全二叉树至少有个结点。
8．一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
9．按照所涉及的存储设备的不同，排序分为和两大类。10．一个算法的效率可分为效率和效率。
11．在有向图G中，若任意两个顶点V i和V j都连通，即从V i到V j和从V j到V i都存在路径，则称该图
为。
12．在各种查找方法中，其平均查找长度与结点个数n无关的查找方法是
13．在单链表p结点之后插入s结点的操作是和。
14．顺序存储结构是通过表示元素之间的关系的。
15．链式存储结构是通过表示元素之间的关系的。
16．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的和记录的。
17．分别采用堆排序、快速排序、冒泡排序和归并排序，对初始状态为有序的表，则最省时间的是算法。
18．空格串是指，其长度等于。
19．有n个叶子结点的哈夫曼树的结点总数为。
20．在哈希表中，装填因子的值越大，则发生的可能性越大。
21．仅允许在表的同一端进行插入和删除运算的线性表被称为。
四．解答题
1．已知一棵二叉树如图所示，分别写出它的先序遍历序列、中序遍历序列和后序遍历序列。
2．已知二叉树的后序序列为：HGAEBFC，中序序列为：HBGEACF，要求画出该二叉树。
3、已知完全二叉树的第七层有10个叶子结点，则整棵二叉树的结点数最多是多少？
4．列出下图中从顶点1开始的所有拓扑排序序列。
5、已知无向带权图，
（1）写出它的邻接矩阵。
（2）从顶点A出发，求它的深度优先搜索遍历的顶点序列。
（3）从顶点A出发，求它的广度优先搜索遍历的顶点序列。
6．下面的邻接表表示一个给定的无向图，请根据邻接表：
（1）画出该无向图的图形。
（2）给出以顶点V1为起点的深度优先遍历的顶点序列及对应的生成树。
7．下面的邻接表表示一个给定的无向图，请根据邻接表：
（1）画出该无向图的图形。
（2）列出从顶点1出发的深度优先搜索遍历该图所得的顶点序列。
（3）列出从顶点1出发的广度优先搜索遍历该图所得的顶点序列。
8、根据下面所示的无向图，要求（1）画出无向图对应的邻接表；（2）根据无向图，列出从顶点1出发的
深度优先和广度优先搜索遍历该图所得的顶点序列。
9．设无向网如下图所示，按克鲁斯卡尔算法求网的最小生成树，要求画出执行过程。
10．假定对长度为11的有序表进行折半查找：
（1）画出描述折半查找过程的判定树。
（2）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
11、假定对有序表（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。
（1）画出描述折半查找过程的判定树
（2) 假定每个元素的查找概率相等，求查找成功时的平均查找长度
12．判断下列序列是否为堆，若不是堆，则把它调整为堆。
（1）（100，86，48，73，35，39，42，57，66，21）
（2）（5，56，20，23，40，38，29，61，35，76，28，100）
13．使用哈希函数H(key) = key mod 11，把一个整数值转换成哈希表下标，现要把数据{1，13，12，34，38，33，27，22}插入到哈希表中，表的长度为11，用线性探查法解决冲突，要求构造哈希表，并求出在等概率情况下，查找成功时的平均查找长度。
14．待排序的数据元素序列为{49，38，65，97，76，13，27，，55，4}，设希尔增量分别为5，3，1，画出用希尔排序法进行排序的过程。
15．判断序列（12，70，33，65，24，56，48，92，86，33）是否为堆，若不是堆，则把它调整为堆。
16、待排序的数据元素序列为{49，38，65，97，76，13，27，49，55，4}，设希尔增量分别为5，3，1，画出用希尔排序法进行排序的过程。
五、阅读题
1．简述算法的功能（栈和队列的元素类型均为整型）。
void algo（Queue ＆Q）
{
Stack S；int d；
InitStack（S）；
while（！QueueEmpty（Q））
{
DeQueue（Q，d）；Push（S，d）；
}
while（！StackEmpty（S））
{
Pop（S，d）；EnQueue（Q，d）；
}
}
2．算法f6的功能是什么？
V oid f6(Statck &S1, Statck &S2)
{
Statck temp;
DataType x;
InitStack(&temp);
while(!StackEmpty(S1))
{
x = Pop(&S1);
Push(&temp, x);
}
while(!StackEmpty(S2))
{
x = Pop(&S2);
Push(&S1, x);
}
while(!StackEmpty(temp))
{
x = Pop(&temp);
Push(&S2, x);
}
}
3．以下算法的功能是实现冒泡排序，请在下面画线处填入适当的内容，以使该算法在发现有序时能及时停止。
#define MAXSIZE 100
typedef struct pnode {
int key；
int oth；/* 其它域，根据需要设定*/
}pnode；
void bubblesort(pnode r[MAXSIZE], int n)
{
i=1；
do{
tag=0；
for(j=n；j>i；j--)
if (r[j].key { x=r[j]；r[j]=r[j-1]； r[j-1]=x；（1）； } （2）； }while（tag==1 && （3）） 4．已知链串的存储结构描述如下： #define NodeSize 4 typedef struct Node { char data [NodeSize]; struct Node * next; } * LinkStr; 阅读算法f7，并回答问题： （1）s1和s2的串值分别为″Student″和″Studying″时，写出f7 (t1,t2)的返回值；（2）简述函数f7的功能。 int f7(LinkStr s1, LinkStr s2) {//串值以′′为结束符 while (1) { for (i=0;i { if(s1->data[i]==" && s2->data[i]== ") return 0; if(s1->data[i]== ")) return –1; if(s2->data[i]== ")) return 1; if(s1->data[i]>s2->data[i]) return 1; if(s1->data[i] return –1; } s1=s1->next; s2=s2->next; } } 5、已知链串的存储结构描述如下： #define NodeSize 4 typedef struct Node { char data [NodeSize]; struct Node * next; } * LinkStr; 阅读算法f3，简述f3的功能。 int f3 (LinkStr s1, LinkStr s2) { //串值以′\0′为结束符 while (1) { for (i=0;i { if(s1->data[i]== ′\0′&& s2->data[i]== ′\0′) return 0; if(s1->data[i]== ′\0′) return –1; if(s2->data[i]== ′\0′) return 1; if(s1->data[i]>s2->data[i]) return 1; if(s1->data[i] return –1; } } 6．算法f1是中序遍历二叉树，完整算法中的空缺。 void f1BiTree T) { InitStack(&S); P = T; while(p||!StackEmpty(s)) { if(P) { Push(&S, P); ① } else { Pop(&S, P); visit(P->data); //visit为访问结点P的数据 ② } } } ① ② 7、已知二叉排序树以二叉链表做存储结构，其根结点指针为t, p为二叉排序树中的指定结点。阅读算法， 并简述算法的功能 typedef struct BiTNode{ TElemType data； Struct BiTNode *lchild，*rchild； }BiTNode，*BiTree； int count（BiTree p，BiTree t）{ h=0；t1=t； if（t1==NULL）return 0； else{ h=h+1； while（t1—>data！=p—>data） { if（t1—>data else t1=t1—>lchild； h=h+1； } } return h； } 8、简述算法f2的功能（栈和队列的元素类型均为整型） void f2（Queue ＆Q）{ Stack S；int d； InitStack（S）； while（！QueueEmpty（Q））{ DeQueue（Q，d）；Push（S，d）； } while（！StackEmpty（S））{ Pop（S，d）；EnQueue（Q，d）； } } 9．说明算法f6的功能。 void f6(Queue *Q) { DataType x; Stack S; InitSatck(&S); while(!QueueEmpty(Q)) { x = DeQueue(Q); Push(&S, x); } While(!StackEmpty(&S)) { x = Pop(&S); EnQueue(Q, x); } } 10、简述算法f1的功能（栈的元素类型SElemType为int） void f1（Stack S, int e） { Stack T； int d; InitStack（T）； while（！StackEmpty（S））{ Pop（S，d）； if ( d!=e) Push（T，d）； } while（！StackEmpty（T））{ Pop（T，d）； Push（S，d）； } } 11．指出下面函数f7的功能及返回值的含义。 int f7(char s1[],char s2[]) { int i=0, j=0; while(s1[i]&&s2[j]) { if(s1[i]>s2[j]) return 1; else if(s1[i] return -1; else { i++; j++; } } if(s1[i]) return 1; else if(s2[j]) return -1; else return 0; } 六．算法设计题 1、假设带头结点的单链表表示线性表，单链表的类型定义如下： typedef struct node { int data； struct node *next； } LinkNode，*LinkList； 逆位序输入线性表的n个数据元素，编写建立带头结点的单链表的算法 2、假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node { int data； struct node*next； } LinkNode，*LinkList； 已知线性表L中的元素以值非递减有序排列，并以上述结构作为存储结构（带头结点），设计算法删除表中所有值相同的多余元素（使操作后的线性表中的所有元素的值均不相同），同时释放被删结点空间。 3、带头结点的单链表（head为头指针）中的数据元素非递减有序，单链表的类型定义如下： typedef struct node { int data； struct node *next； } LNode，*LinkList； 要求编写算法将数据元素x插入到单链表中的适当位置，插入后仍保持单链表非递减有序。 4、设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node { int data； struct node*next； } LinkNode，*LinkList； 已知线性表L的数据元素是无序的，以上述结构（带头结点）作为存储结构。编写算法，删除表中所有值大于min且小于max的元素（若表中存在这样的元素），同时释放被删结点空间。 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.1基本概念和术语 1.数据是对客观事物的符号表示；数据元素是数据的基本单位，一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位；数据对象是性质相同的数据元素的集合，是数据的一个子集。 2.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 3. A.数据结构的三要素：①数据的逻辑结构②数据的存储结构③数据的运算（算法） B.任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构 4.数据的逻辑结构:①集合②线性结构③树型结构④图状结构或网状结构 1.2算法和算法分析 1.算法的五个特性：①有穷性②确定性③可行性④输入⑤输出 2.时间复杂度：时间复杂度是指执行算法所需要的计算工作量 空间复杂度：空间复杂度是指执行这个算法所需要的内存空间 第二章线性表 2.1线性表的顺序表示和实现 1.线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 2.优点：线性表的顺序存储结构是一种随机存取的存储结构 3.顺序线性表插入： 顺序线性表删除： 4.线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(可连续，可不连续) 5.对数据元素来说，除了存储其自身的信息之外，还需存储一个指示其直接后继的信息(存储位置)，这两部分信息组成数据元素的存储映像，称为结点。他包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或域。N个结点链结成一个链表，即为线性表的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。 6.链表的插入与删除 7.双向链表的插入与删除 第三章栈和队列 3.1 栈 1．栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应的，表头端称为栈底。不含元素的空表称为空栈。 2.栈又称为后进先出的线性表 3.栈的进栈与出栈操作 数据结构复习题及参考答案 （抽考其中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、以下说法正确的是（B ）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 2、在数据结构中，从逻辑上可以把数据结构分成（C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．以上三个选项都是不是 3、以下数据结构中，（A ）是非线性数据结构 A．树B．字符串C．队D．栈 4. 对于int *pa[5]的描述，（ D ）是正确的。 A．pa是一个指向数组的指针，所指向的数组是5个int型元素 B．pa是一个指向某数组中的第5个元素的指针，该元素是int型变量C．pa[5]表示某个数组的第5个元素的值 D．pa是一个具有5个元素的指针数组，每个元素是一个int型指针 5、在int a[][3]={{1},{3,2},{4,5,6},{0}}中，a[2][2]的值是( C )。 A.3 B. 2 C.6 D.4 1. 栈和队列的共同特点是( A )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 用链接方式存储的队列，在进行插入运算时( D ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 算法分析的目的是：（ C ） A．找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 4. 算法分析的两个主要方面是：（ A ） A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 5. 计算机算法指的是：（ C ） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 6．循环链表的主要优点是( B ) 。 A.不在需要头指针了 B.已知某个结点的位置后，能够容易找到他的直接前趋 C.在进行插入、删除运算时，能更好的保证链表不断开 D.从表中的任意结点出发都能扫描到整个链表 7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ B ）。 A. head==0 B. head->next==0 C. head->next==head D. head!=0 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ B ）。 A. abedfc B. acfebd C. aebdfc D. aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（ C ）。 数据结构期末复习重点知识点总结 一、数据结构概述 数据结构是计算机科学中一门关于数据组织、存储和管理的学科。 它涉及到各种数据类型和它们之间的关系，以及对这些数据类型进行 有效操作和处理的算法。 二、基本数据结构 1. 数组 - 数组是一种线性数据结构，用于存储相同类型的数据元素。 - 数组的特点是随机访问和连续存储。 - 数组的插入和删除操作需要移动其他元素，时间复杂度为O(n)。 2. 链表 - 链表是一种线性数据结构，通过节点之间的指针链接来组织数据。 - 链表的特点是插入和删除操作简单，时间复杂度为O(1)。 - 链表分为单链表、双向链表和循环链表等不同类型。 3. 栈 - 栈是一种具有后进先出（LIFO）特性的数据结构。 - 栈的操作主要包括压栈（Push）和弹栈（Pop）两个操作。 - 栈常用于表达式求值、递归算法的实现等场景。 4. 队列 - 队列是一种具有先进先出（FIFO）特性的数据结构。 - 队列的操作主要包括入队（Enqueue）和出队（Dequeue）两个 操作。 - 队列常用于实现缓冲区、消息队列等场景。 5. 树 - 树是一种非线性的数据结构，由节点和边组成。 - 树的节点具有层级关系，由根节点、子节点和叶节点等组成。 - 常见的树结构有二叉树、红黑树、B树等。 6. 图 - 图是一种非线性的数据结构，由节点和边组成。 - 图的节点之间可以有多对多的关系。 - 图的遍历方式有深度优先搜索（DFS）和广度优先搜索（BFS）。 三、常见的数据结构算法 1. 排序算法 - 冒泡排序、插入排序、选择排序等简单但效率较低的排序算法。 - 快速排序、归并排序、堆排序等高效的排序算法。 数据结构复习资料(亲自整理) 1、链表是一种存储数据的链式结构，每个数据之间都是相关联的。 2、线性结构是一个有序数据元素的集合，包括线性表、栈、队列、双队列、数组和串。 3、树是由n（n>=1）个有限节点组成一个具有层次关系的集合，而二叉树是每个结点最多有两个子树的有序树。二叉树与树的主要差别在于，二叉树结点的最大度数为2，而树中结点的最大度数没有限制；二叉树的结点有左、右之分，而树的结点无左、右之分。 4、堆是一种可以被看做一棵树的数组对象，总是满足某个节点的值总是不大于或不小于其父节点的值，且堆总是一棵完全二叉树。 5、二叉排序树是一种满足以下递归定义的二叉树：若左子树非空，则左子树所有节点的值均小于它的根节点；若右子树非空，则右子树所有节点的值均大于于它的根节点；左右子树也分别为二叉排序树。 1、在已知前序遍历和中序遍历的情况下，可以通过画树 的方法求得后序遍历。具体步骤如下：首先根据前序遍历的特点，确定根节点；然后观察中序遍历，将左子树和右子树分别确定下来；接着对左子树和右子树分别进行递归，直到遍历完所有节点，最后得到后序遍历。 2、树和二叉树之间可以相互转换。将树转换为二叉树的 方法是：对于每个节点，将其第一个孩子作为其左孩子，将其兄弟作为其右孩子。将二叉树转换为树的方法是：对于每个节点，将其右孩子作为其兄弟。 3、二叉树线索化是将二叉树中的空指针指向该节点在中 序遍历中的前驱或后继节点的过程。在线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1. 4、邻接表是图的一种链式存储结构，用于表示图中每个 节点的邻居节点。每个节点都有一个链表，存储着与该节点相邻的节点。 邻接表是一种图的存储结构，对于每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图是以该顶点为尾的弧）。 邻接表中的表结点和头结点分别表示边和顶点，包含信息如下：表结点adjvex（邻接点）。nextarc（指向下一个表结点） 数据结构期末考试复习题资料 一．单项选择题 1.算法指的是（）。 A．计算方法B．排序方法C．特定问题求解步骤的描述D．调度方法 2．下列数据结构中，（）是非线性结构。 A．栈B．队列C．完全二叉树D．堆 3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储 方式最节省时间。 A．顺序表B．双向链表C．单循环链表D．带头结点的双循环链表 4．队列的操作原则是（） A．先进先出B．后进先出C．先进后出D．不分顺序 5．栈和队列的共同特点是（）。 A．都是先进先出B．都是先进后出C．都是只允许在端点处插入和删除D．没有共同点6．在一棵高度为k 的满二叉树中，结点总数为（）。 A．2k-1 B．2k C．2k-1 D．⎣log 2 k ⎦+ 1 7.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲链表表示法B．孩子链表表示法C．孩子兄弟链表表示法D．顺序存储表示法8．n 个结点的完全有向图含有边的数目为（）。 A．n*n B．n*(n+1) C．n/2 D．n*(n-1） 9．n 个顶点的强连通图至少有（）条边。 A．n B．n-1 C．n+1 D．n(n-1) 10、高度为k 的二叉树的最大结点数为（）。 A、2k B、2k-1 C、2k–1 D、2k-1–1 11、下列哪一种图的邻接矩阵是对称矩阵？（） A、有向图 B、无向图 C、AOV 网 D、AOE 网 12、在下列存储形式中，哪一个不是树的存储形式？（） A、双亲表示法 B、孩子表示法 C、孩子兄弟表示法 D、顺序存储表示法 13、下面哪一方法可以判断出一个有向图是否有环。（） A、深度优先遍历 B、拓扑排序 C、求最短路径 D、广度优先遍历 14.适用于折半查找的表的存储方式及元素排列要求为（）。 A．链接方式存储，元素无序B．链接方式存储，元素有序 C．顺序方式存储，元素无序D．顺序方式存储，元素有序 15、一个算法应该是（）。 A、程序 B、特定问题求解步骤的描述 C、要满足五个基本特性 D、A 和C 16、算法分析的两个主要方面是（）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 17、以下数据结构中，（）是非线性数据结构。 A、树 B、字符串 C、队 D、栈 数据结构复习提纲 复习内容： 基本概念掌握：数据结构，逻辑结构，存储结构；数据类型；算法;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．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 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++ 时间复杂度的大小比较： 一、简答题 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。 第一章概论自测题答案 一、填空题 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 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.数据元素：是数据旳基本单位,在程序中作为一种整体而加以考虑和处理 3.数据项:又叫字段或域,它是数据旳不可分割旳最小标识单位。 4.逻辑构造需要注意旳几点： ①逻辑构造与数据元素自身旳内容无关 ②逻辑构造与数据元素相对位置无关 ③逻辑构造与所有结点旳个数无关 5.数据元素间逻辑关系是指数据元素之间旳关联方式或称“领接关系”。 6.四类基本逻辑构造(集合、线性构造、树形构造和图形构造)旳不一样特点? 答:集合中任何两个结点之间都没有逻辑关系,组织形式松散； 线性构造中结点按逻辑关系依次排列形成一条“锁链”； 树形构造具有分支、层次特性，其形态有点像自然界中旳树; 图状构造最复杂,其中旳各个结点按逻辑关系互相缠绕,任何两个结点都可以领接。 7.运算是在逻辑构造层次上对处理功能旳抽象 ８.基本运算旳含义？ 答:假如Γ是S上旳某些运算旳集合，∆是Γ旳一种子集,使得Γ中每一运算都可以“归约”为∆中旳一种或多种运算，而∆中任一运算不可归约为别旳运算，则称∆中运算为基本运算 9．数据构造是指由一种逻辑构造Ｓ和Ｓ上旳一种基本运算集∆构成旳整体（S ,∆）。10.数据构造波及数据表达和数据处理两个方面 1１．存储构造旳含义和四种基本存储方式旳基本思想？ 答:存储构造是指按照逻辑构造旳规定建立旳数据旳机内表达称为存储构造。 一种存储构造应包括三个重要旳部分：存储结点、机内表达和附加设施。 存储构造包括四种存储方式，次序存储方式、链式存储方式、索引存储方式和散列存储方式。 12.运算实现与运算旳联络与区别? 答：运算指旳是数据在逻辑构造Ｓ上旳某种操作,运算只描述处理功能，不包括处理环节和措施;而运算实现是指一种完毕该运算功能旳程序，运算实现旳关键是处理环节旳规定，即算法设计。 13．算法旳概念和分类? 答：算法是指规定了求解给定类型问题所需旳所有“处理环节”及其执行次序,使得给定类型旳任何问题能在有限时间内被机械地求解。 算法旳类型有：运行终止旳程序可执行部分、伪语言算法和非形式算法（根据描述算法语言不一样) 14.算法在给定输入下旳计算量旳含义和估算旳措施? 答：算法在给定输入下旳计算量是指根据该类问题旳特点合理地选择一种或几种操作作为“原则操作”,确定每个算法在给定输入下共执行多少次原则操作，并将本次数规定为该算法在给定输入下旳计算量。估算旳措施有：最坏时间复杂度和平均时间复杂度。 第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理; 2.数据元素：数据的基本单位,可由若干个数据项组成,数据项是具有独立含义的最小标识单位; 3.数据结构：数据之间的相互关系,即数据的组织形式; 它包括：1数据的逻辑结构,从逻辑关系上描述数据,与数据存储无关,独立于计算机； 2数据的存储结构,是逻辑结构用计算机语言的实现,依赖于计算机语言; 3数据的运算,定义在逻辑结构上,每种逻辑结构都有一个运算集合;常用的运算：检索/插入/删除/更新/排序; 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型;数据的存储结构是逻辑结构用计算机语言的实现; 5.数据类型：一个值的集合及在值上定义的一组操作的总称;分为：原子类型和结构类型; 6.抽象数据类型：抽象数据的组织和与之相关的操作;优点：将数据和操作封装在一起实现了信息隐藏; 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象类的实例解决问题; 8.数据的逻辑结构,简称为数据结构,有： 1线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继; 2非线性结构,一个结点可能有多个直接前趋和后继; 9.数据的存储结构有： 1顺序存储,把逻辑相邻的结点存储在物理上相邻的存储单元内; 2链接存储,结点间的逻辑关系由附加指针字段表示; 3索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引; 4散列存储,按结点的关键字直接计算出存储地址; 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间辅助存储空间；易于理解、编码、调试;数据结构-复习资料
数据结构期末复习资料
数据结构复习资料(题目和参考答案)
数据结构期末复习重点知识点总结
数据结构复习资料
数据结构复习资料
数据结构期末复习重点知识点总结
数据结构复习资料(亲自整理)
数据结构期末考试复习题资料
(完整word版)数据结构复习提纲
数据结构 复习重点
数据结构复习要点(整理版)
数据结构复习资料(亲自整理)
数据结构期末复习章节试题附复习资料
数据结构复习要点
2023年自考数据结构导论复习资料
数据结构复习笔记
相关主题
文本预览