#include<iostream>

#include<string>

#include<stack>

usingnamespacestd;

///////交换函数

bool swap(int *a,int *b)

{

int c=*a;

*a=*b;

*b=c;

return 1;

}

//////直接插入排序//////////////////

boolDerictSearchSort(int a[],intf,int e)

{

int* first=a+f;

int* end=a+e;

int n=e-f+1;

int temp;

int *temp_p;

for(inti=0;i<n;i++)

{

temp=*(first+i);

temp_p=first+i-1;

while(temp_p>=first&&temp<*temp_p)

{

int c=*temp_p;

*temp_p=*(temp_p+1);

*(temp_p+1)=c;

temp_p--;

}

}

return 1;

}

//////折半插入排序//////////////////

boolBinarySearchSort(int a[],intf,int e)

{

int* first=a+f;

int* end=a+e;

int n=e-f+1;

int temp;

int *temp_p;

for(inti=1;i<n;i++)

{

int* head=first;

int* tail=first+i-1;

int* p;

while(1)

{

if(head>=tail-1)break;

if(*(head+(tail-head)/2)>*(first+i))tail=(head+(tail-head)/2)-1;

elseif(*(head+(tail-head)/2)<*(first+i))head=(head+(tail-head)/2)+1; } if(*tail<*(first+i)){p=tail+1;} elseif(*head>*(first+i)){p=head;} else p=tail; while(p!=first+i) { int c=*p; *p=*(p+1); *(p+1)=c; } } return 1; } /////希尔排序//////////////////// boolShellSort(int a[],intf,int e) { int* head=a+f; int* tail=a+e; int n=e-f+1; int g=2;//每个序列的长度 while(g<=n) { int d=n/g;//起点的个数，步长 //// for(inti=0;i<d;i++) { int* first=head+i; int* end=tail; int temp; int *temp_p; temp_p=first+d; temp=*(temp_p+d); while(temp_p>=first&&tail>temp_p+d&&temp<*temp_p) { int c=*temp_p; *temp_p=*(temp_p+d); *(temp_p+d)=c; temp_p=temp_p-d; } } /// g=g*2; } return 1; } //////冒泡排序//////////////////// boolBubbleSort(int a[],intf,int e) { int* first=a+f;

int* end=a+e;

for(int* head=first;head<end;end--)

for(int* p=head;p<end;p++)

if(*p>*(p+1)){int c=*p;*p=*(p+1);*(p+1)=c;}

return 1;

}

//////快速排序//////////////////

boolFastSort(int a[],intf,int e)

{

if(f>=e)return 1;

int* first=a+f;

int* end=a+e;

int* tag=first;

while(first!=end)

{

if(first==tag&&*end<*first){swap(end,first);tag=end;first++;} elseif(first==tag&&*end>=*first){end--;}

}

FastSort(a,f,tag-a-1);

FastSort(a,tag-a+1,e);

return 1;

}

//////直接选择排序////////////

boolDerictChooseSort(int a[],intf,int e)

{

int* first=a+f;

int* end=a+e;

int n=e-f+1;

while(n!=1)

{

int *p=first;

int *tag=p;

while(p!=end+1)

{

if(*p<*tag)tag=p;

p=p+1;

}

int c=*first;

*first=*tag;

*tag=c;

n--;

first++;

}

return 1;

}

int main()

{

int a[10]={0,2,5,7,4,6,8,1,9,3};

DerictSearchSort(a,0,9);

for(inti=0;i<10;i++)cout<<" "<<a[i];

cout<<"\n";

} BinarySearchSort(a,0,9); for(inti=0;i<10;i++)cout<<" "<<a[i]; cout<<"\n"; ShellSort(a,0,9); for(inti=0;i<10;i++)cout<<" "<<a[i]; cout<<"\n"; BubbleSort(a,0,9); for(inti=0;i<10;i++)cout<<" "<<a[i]; cout<<"\n"; FastSort(a,0,9); for(inti=0;i<10;i++)cout<<" "<<a[i]; cout<<"\n"; DerictChooseSort(a,0,9); for(inti=0;i<10;i++)cout<<" "<<a[i]; cout<<"\n";

第二篇：数据结构重点整理

考点

1 算法的时间复杂度 (不会出简单的for循环)

例题.1下面程序段的时间复杂度为 D O(n*log2n) for (k=1;k<=j;k++)

｛ int i=1; while (i<=n)

i=i*2; ｝

O(1)初始化线性表 检查线性表是否为空

O(n)删除线性表中的所有元素；得到线性表的长度；得到线性表中指定序号为pos的元素；遍历一个线性表；从线性表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向线性表中按给定条件插入一个元素；从线性表中删除符合给定条件的第一个元素

O(n^2)对线性表进行排序 2几种数据结构 （数据结构定义：具有结构的数据元素的集合 ）

逻辑结构：集合、线性结构（线性表、广义表、堆栈和队列）非线性结构（树、图） 存储结构：顺序存储结构、链式存储结构、索引结构、散列结构等

集合和线性结构：1 ：1 树形结构：1 ：N 图形结构：N : N 3 线性表顺序存储和链接存储的特点

顺序存储：随机存取，预先定义表长；插入删除时有大量元素的移动（当下标为1开始的实话移动n-i+1，当下标为0开始的实话移动n-i），查找方便。

链式存储：非随机存取，表长不需要预先定义是动态分配，插入删除不需要大量的元素移动，查找时从第一个元素开始查找。

4 根据线性表的常用操作，选择最合适的存储方式

顺序表和链表的比较：

空间方面：a当表长难估较大时，选择链式存储b当表长较小时，选择顺序存储 时间方面：a插入与删除较多时选择链式存储b查找方面较多时用顺序存储

语言方面：当语言没有指针，选用链式存储时选用静态链表（静态链表需要预先设定空间）

某线性链表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点, 用仅有尾指针的单循环链表存储方式实现这两种操作

6 链表的特点

例题：链表不具有的特点是（A）。

A、可随机访问任意元素 B、插入删除不需要移动元素

C、不必事先估计存储空间 D、所需空间与线性表长度成正比

7 链表的插入删除

8 链表各操作的时间复杂度

O(1)初始化链表 检查链表是否为空

O(n)删除链表中的所有元素；得到链表的长度；得到链表中指定序号为pos的元素；遍历一个链表；从链表中查找具有给定值的第一个元素；更新线性表中具有给定值的第一个元素；向链表中按给定条件插入一个元素；从链表中删除符合给定条件的第一个元素 O(n2)对链表进行排序

例题：在一个长度为n单链表；在表头插入元素的时间复杂度为 O(1) ；在表尾插入元素的时间复杂度为O(n)。

9 栈的特点：先进后出，后进先出。

10 栈的顺序存储、链式存储的出栈入栈时间复杂度：O(1)

13 根据给定递归算法和输入 求输出

（读递归程序）

14 数组上的循环队列 的进队出队操作 （参考期中考试最后大题）

判空：rear == front 满：(rear+1)%MaxSize == front 进队操作：rear = (rear+1)%MaxSize; Q(rear)=x 出队操作：front = (front+1)%MaxSize; X=Q(front)

入队时需先修改入队指针（队尾指针）rear = = (rear +1)% QueueMaxSize 出队时需要修改队头指针front == (front +1)% QueueMaxSize 15 链队的插入O(1)

void EnQueue (LinkQueue& HQ,const ElemType& item) { LNode* newptr=new LNode; if (newptr ==NULL) { cerr<<“Memory alocation failure."<<endl; exit(1); } newptr->data=item; newptr->next =NULL; if (HQ.rear==NULL) HQ.front=HQ.rear=newptr; else HQ.rear=HQ.rear->next=newptr; }

17 稀疏矩阵的定义：其非零元素的个数远远小于零元素的个数。

稀疏矩阵的严格定义： 稀疏因子?=非零元素/所有元素个数 通常认为 ? ? 0.3 的矩阵为稀疏矩阵

三元组表示形式： ( i, j, value ) i为第i行， j为第j列，value为非0元素的值 18 广义表的特点

规定：大写字母表示广义表名称，小写字母表示原子，广义表非空时：a是广义表的表头head。其余元素组成表尾tail；

广义表中的数据元素有相对次序;广义表的长度定义为所含元素的个数;

广义表的深度定义为括号嵌套的最大次数;注意:“空表”的深度为 1 ; 广义表可以共享; 广义表可以是一个递归的表;递归表的深度是无穷值，长度是有限值。 例：D=(E, F) E=(a, (b, c), D) , F=(d, (e)) D的长度为2，深度为无穷 19 求广义表的长度 深度

广义表的深度=Max {子表的深度} +1；空表的深度 = 1；仅由单元素组成的表的深度 = 1 例LS=((),(e),(a,(b,c,d)))长度为3深度为3； LD=(((a),((),b),(c)))长度1深度4 20 树的性质1

树中结点个数等于所有结点的度数加1 21 二叉树的性质4 P185

书中性质4：

若对具有n个结点的完全二叉树按照层次从上到下,每层从

左到右的顺序进行编号, 则编号为i 的结点具有以下性质:

(1) 若编号为i的结点有左孩子,则左孩子结点的编号为2i;若编号为i的结点有右孩子,则右孩子结点的编号为2i+1.

(2) 除树根结点外,若一个结点的标号为i,则它的双亲结点的编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子,当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子. (3) 若i≦|_n/2_|,即2i ≦n,则编号为i的结点为分支结点,否则为叶子结点.

(4) 若n为奇数,则每个分支结点都既有左孩子,又有右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)只有左孩子,没有右孩子,其余分支结点左、右孩子都有.

22 给定权值 构造哈夫曼树 求带权路径长度（参考作业题）

例题1：如右图：

WPL=7*1+5*2+2*3+4*3=35

23 哈夫曼树的特点

又称最优树，是一种带权路径长度WPL最 小的二叉树。

由0和1组成，用哈夫曼编码传送的电文长度；传输速率最快。 叶子结点的度为零；除叶子结点外的所有结点的度都为2

24 二叉排序树求平均查找长度:

K为层数，n表示最大层数，m（k）表示第k层有m结点个数， M表示所有结点个数。

/（M）

25 有向图边数和顶点入度 出度关系

在有向图的邻接表中，从一顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以顶点入度之和为弧数和的一倍；在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的1倍；无向图的邻接表中结点个数的边数的2倍。 向图边数=所有度之和/2

26 无向图 顶点数和最小生成树的边数关系

无向图 顶点数n：最小生成树的边数n-1 27 图的邻接表P258

邻接表:是图的一种链式存储结构。在邻接表中，对图中每个顶点建一个单链表，第i个单链表中的结点表示依附于顶

点vi的边（对于有向图是以顶点vi为尾的弧）。 图的邻接表是存放什么的：

无权无向图：列存放所有节点，横向为结点对应邻接结点和指针指向结点对应的下一邻接点

带权有向图：列存放所有节点，横向为结点的出度的所有邻接点，其中第一项为结点名称，第二项为与该结点名称对应的权值，第三项为指针指向结点对应的下一出度邻接点。

28 求最短路径长度P281

两个顶点间可能存在多条路径，其中有一条是长度最短的路径，即最短路径

若带权值要i到j中所经过边权值之和最小的路径称为最短路径，其权值称为最短路径长度。

29 图的边数与顶点数的关系

（以下是网上找的小题）

30 1） 布里姆算法

依次在G中选择一条一个顶点仅在V中,另一个顶点在U中,并且权值最小的边加入集合TE,同时将该边仅在V 中的那个顶点加入集合U. 重复上述过程n-1次,使得U=V,此时T为G的最小生成树.

2） 克鲁斯卡尔算法

将图Ｇ中的边按权值从小到大的顺序依次选取，若选取的边使生成树Ｔ形成回路，则将其舍弃，如此进行下去，直到TE中包含有n-1条边为止,此时T为G的最小生成树.

31 顺序查找的平均查找长度:（1+2+3……n）/N 32 构造二叉排序树 求平均查找长度

平均查找长度为：（1*1+2*2+3*4+4*1）/8=21/8

33二分查找 给定有序表和待查元素 求依次与哪些元素进行比较

将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一维数组A[0..9]中，然后采用二分查找方法查找元素12，被比较过的数组元素的下标依次为 4，7，5 _。 34冒泡排序 每趟需要进行的比较次数，最多进行多少趟 n-1趟 35 快速排序 第一次划分结果

快速排序（Quick Sorting），又称划分排序.是目前所有排序方法中速度最快的一种（从排序区间选取一个元素为基准,从区间两端向中间顺序进行比较和交换,使得前面单元只保留比基准小的元素,后面单元保留比基准大的元素.然后把基准放到前后两部分之间.）

36 各排序算法空间复杂度

排序方法 时间复杂度

平均情况 最坏情况 最好情况

直接插入 O(n2)

空间复杂稳定性 复杂性 度 O(1)

稳定 简单 不稳定 较复杂 稳定 简单

O(n2) O(n)

希尔排序 O(n*n1/2) O(n2) 冒泡排序 O(n2)

O(nlog2n) O(1) O(n)

O(1)

O(n2)

快速排序 O(nlog2n) O(n2) 直接选择 O(n2)

O(nlog2n) O(log2n) 不稳定 较复杂 O(n2)

O(1)

不稳定 简单 不稳定 较复杂 稳定 较复杂 稳定 较复杂

O(n2)

堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n)

基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd)

37 二叉排序树的特点

二叉排序树的中序是有序的；左孩子比根小，右孩子大于等于根

38 顺序查找适合的存储结构

顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。

39排序算法时间复杂度 (见36知识点图) 40 双循环链表 （老师忘记出什么样的了） 41 图连通需要的边数

在n个顶点的无向图中，若边数>=n-1，则该图必是连通图。 42 排序的稳定性(见36知识点图)

稳定的有：直接插入 、归并排序、基数排序、冒泡排序 不稳定的有：快速排序、希尔排序、直接选择、堆排序

43 树的性质3

课件：性质3 深度为h的k叉树中至多有(k-1)/(k-1) 结点。

h

满k叉树：结点个数等于(k-1)/(k-1) 的k叉树。

递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。

h

44 二叉树的定义：二叉树为度为2的有序树。

45 二分查找 最多需要比较次数：N个元素最多比较n/2次 46树的深度的定义：树中所有结点层次的最大值，也称高度。

每次调整至少能排除一半的个数(从x到其x-1层,x层得个数应该是所有个数的一半+1),所以复杂度是log级别

比如有32个元素(为了方便取一个2的幂), 第一次排除 ,16,第二次,8,第三次4,... 2,1. 以这种规律排除几次才能完呢?

比如要排除a次,那么 第一次 2^(a-1) ,第二次2^(a-2)... 第三次2^(a-3) ....第a次2^0=1

是不是 总的个数-1= 1+2+4+...2^(a-1) =2^a-1 那么总的个数=2^a 所以: a=log2 (总的个数)

对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_________ 2n ____个，其中_____ n-1__________个用于指向孩子，____________ n+1_____个指针是空闲的。

若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为____2i+1____,右孩子元素为____ 2i+2 ___________，双亲元素为____(i-1)/2________。

6. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。答： ASL=(1*1+2*2+3*4)/7=17/7

2.从一个长度为n的顺序表中删除第i个元素(0≤i≤n-1)时，需向前移动n-i+1个元素。 [ n-i-1 ]

（×）

1．在一个长度为n的顺序表中删除第i个元素时，需向前移动 n－i－1 个元素。插入i位置，移动 n－i个元素。

8．在一棵二叉树中，度为零的结点的个数为n0，度为2 的结点的个数为n2，则有

9．一棵有n个叶子结点的哈夫曼树共有__2n－1_个结点。

3、顺序查找查找成功时的最坏比较次数为（n-1）和查找失败时的比较次数为（n）。

4、设有64个元素，用折半查找方法进行查找时，最大比较次数是（7），最小比较次数是（1）。

只有非空的广义表的表尾永远是广义表 表头可以是原子也可以是子表

3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（对 ） 一个n个顶点的无向连通图最多有n(n-1) /2 条边，最少有 n-1 条边。

8、用邻接表表示图进行广度优先遍历时，通常是采用（B队列） 来实现算法的。 9、用邻接表表示图进行深度优先遍历时，通常是采用 (A、栈) 来实现算法的。

6.在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率的情况下，查找成功时的平均查找长度为____________。

A n B n/2 C (n+1)/2 D (n-1)/2

9．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是 D 。 A、i<n B、2*i<=n C、2*i+1>n D、2*i>n

5.下面程序段的时间复杂度为____________。

int i=1; while (i<=n) i=i*2; A O(n)

14. 对于长度为N的线性表,在最坏情况下,下列各种排序所对应的比较次数中正确的是______________。 A 冒泡顺序为N/2

B 冒泡顺序为N

B O(n1/2) C O(log2n) D O(n2)

C 快速排列为N D 快速排序为N(N+1)/2

.快速排序的时间复杂度为O(log2n) ×

.结点最少的树为只有一个结点的树 ×

.顺序存储的线形表可以随机存取 √