简答题

编程题

应用题

数据结构冲刺题

简答题

Q01 ：数据结构的定义？数据结构三要素是什么？

Q02 ：逻辑结构的定义？存储结构的定义？

Q03 ：逻辑结构的分类和示意图？存储结构的分类？

Q04 ：顺序存储结构、链式存储结构的定义和优缺点？

Q05 ：什么是算法？算法有哪些特性？

Q07 ：时间复杂度的定义？时间复杂度和什么相关？

Q08 ：空间复杂度的定义？

Q09 ：什么是算法原地工作？

Q10 ：栈的定义和应用？

Q11 ：队列的定义和应用？

Q12 ：循环队列判空、判满的条件？

Q13 ：栈结构判空判满的条件？

Q14 ：什么是满二叉树？满二叉树第K层有多少节点？

Q15 ：什么是完全二叉树？完全二叉树第k层最多有几个节点？

Q16 ：什么是二叉排序树？

Q17 ：什么是平衡二叉树？

Q18 ：非空二叉树第k层最多几个节点？高度为H的二叉树最多几个节点、最少几个节点？

Q19 ：二叉树有n个节点，树高最少是多少？（相当于：n个节点的完全二叉树的高度是多少？）

Q20 ：什么是哈夫曼树（最优二叉树）？

Q21 ：什么是查找？

Q22 ：什么是平均查找长度？

Q22 ：二叉排序树的删除的三种情况。

Q23 ：平衡二叉树的插入调整RR、LL、LR、RL

Q24 ：什么是算法的稳定性？稳定的算法有哪些？不稳定的算法有哪些？

Q25 ：什么是内部排序？什么是外部排序？内部排序有哪些？外部排序有哪些？

顺序表

链表

矩阵

队列

排序算法

二叉树

图

最小生成树

哈夫曼树

二叉排序树

排序

最短路径

散列表

AOE网

标签：结点数据结构 int 冲刺算法二叉树排序节点

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构三要素：逻辑结构、存储结构、数据运算

逻辑结构是指数据元素之间的逻辑关系，与数据存储无关，是独立于计算机的。

存储结构是指数据结构在计算机中的表示，又称物理结构。

逻辑结构分为线性结构、集合、树结构、图状结构或网状结构。

存储结构分为==顺序存储、链式存储、索引存储、散列存储

顺序存储的定义：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系体现。优点：随机存取缺点：占用大片连续存储空间，产生大量碎片。

链式存储结构的定义：逻辑上相邻的元素存储在物理位置上时不一定也连续，借助指示元素存储的存储地址的指针来表示元素之间的逻辑关系。优点：不占用连续的存储空间，减少碎片化缺点：顺序存取，占用额外空间存储地址。

算法是对特定问题求解步骤的一种描述。

算法特性：有穷性、确定性、可行性、输入、输出

时间复杂度是问题规模与时间开销之间的关系。

时间复杂度与问题规模和待处理序列的初始状态有关。

空间复杂度是问题规模的函数，表示该算法耗费的存储空间。

算法原地工作是指该算法所耗费的空间复杂度为常数级O(1)

栈是一种线性存储结构，具有两个特点，1.栈中的数据元素遵循“先进后出”的原则 2. 限定在栈顶插入和删除元素。

栈的应用：括号匹配、进制转换、表达式求值、递归

栈是一种线性存储结构，具有两个特点1.栈中的元素遵循“先进先出”的原则 2.只允许在队头插入元素，在队尾删除元素。

队列应用：缓冲区、图的层次遍历

判空：Q->rear == Q->front 或 Q.rear == Q.front

判满：Q->front->next == Q->rear 或( Q.rear + 1 ) % maxSize == Q.front

判空： S.top == -1

判满：S.top == MaxSize-1

满二叉树：一棵高为H且含有2^H-1个节点的二叉树称为满二叉树。

满二叉树第K层有2^h-1个结点

高度为h，有n个节点的二叉树，当且仅当其每个节点都与高度为h的满二叉树中编号为1~n的节点一一对应时，称为完全二叉树。

完全二叉树第K层最多有2^h-1个结点

左子树上所有结点的关键字都小于根节点的关键字，右子树上的所有节点均大于根节点的关键字，左子树和右子树也是二叉排序树。

树上任意节点的左子树和右子树的深度之差不超过1

2^k-1 、 2^h-1 、 h

Log 2(n+1)向上取整或 log 2 (n)向下取整+1

在含有N个带权叶结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。

在数据集合中寻找满足某种条件的数据元素的过程称为查找。

在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度是指所有查找过程中进行关键字比较次数的平均值。

LL旋转**

找到“最低失衡根结点”，上图是结点5，二叉树失衡的原因是因为结点1的存在，而结点1位于结点5“左子树的左子树”，所以要使用LL旋转来调节，只需一次旋转即可达到平衡。具体的方法是：LL旋转的对象是“最低失衡根结点”，也就是结点5，找到5的左孩子3，将3的右孩子4变成5的左孩子，最后将5变成3的右孩子*

RR旋转**

“最低失衡根结点”是结点2，二叉树的失衡是结点6导致的，而结点6位于结点2“右子树的右子树”，所以要使用RR旋转来调节，只需一次旋转即可达到平衡。方法：旋转的对象是“最低失衡根结点”，这里是结点2，找到2的右孩子4，将4的左孩子3变成2的右孩子，最后将2变成4的右孩子

LR旋转

“最低失衡根结点”为结点5，二叉树失衡是因为结点3的存在，结点3位于结点5“左子树的右子树”，所以使用LR旋转来调节。方法：（1）先对最低失衡根结点的左孩子（结点2）进行RR旋转；（2）再对最低失衡根结点（结点5）进行LL旋转。

RL旋转

旋转步骤：（1）先对最低失衡结点右孩子（结点5）LL旋转；（2）在对最低失衡结点（结点2）RR旋转。

若待排序表中有两个元素Ri和Rj，其对应的关键字相同即：Keyi = Keyj 且在排序前，Ri排在Rj之前，若使用某一算法后，Ri仍在Rj之前，则称此排序算法是稳定的，否则是不稳定的。

稳定的算法：直接插入排序、冒泡排序、二路归并、基数排序

不稳定的算法：简单选择排序、希尔排序、快速排序、堆排序

内部排序是指排序期间元素全部存放在内存中的排序，外部排序是指在排序期间元素无法完全同时存放在内存中，根据要求不断在内外存之间移动的排序。

内部排序有：直接插入排序、冒泡排序、选择排序、希尔排序、快速排序、堆排序、2路归并、基数排序外部排序有：多路归并

附

排序算法		时间复杂度		空间复杂度	稳定性
	最好	平均	最坏
直接插入排序	O(n)	O(n2）	O(n2）	O(1)	√
冒泡排序	O(n)	O(n2）	O(n2）	O(1)	√
选择排序	O(n2）	O(n2）	O(n2）	O(1)	×
希尔排序	-	-	-	O(1)	×
快速排序	O(nlog2n)	O(nlog2n)	O(n2)	O(log2n)	×
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	×
2路归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	√
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	√

在顺序表中实现折半查找的算法

int Binary_Search(SeqList L, ElemType x) {
	int low = 0, high = L.length-1, mid;
	while(low <= high) {
		mid =  (low + high) / 2;
	  	if(key < L.data[mid]) {	   
          	high = mid - 1;//从前半部分找
	 	 }else if(key >L.data[mid]) {
	   		low = mid + 1; //从后半部分找
  		}else return mid; //查找成功返回所在位置
 	}
	 return -1;//查找失败返回返回-1
}

设顺序表L单增有序，编写算法用二分法确定插入位置，将X插入L中，使L保持有序。

void InsertValue(SeqList &L , int n,int x){
    //设顺序表L单增有序，
    //编写算法用二分法确定插入位置，将X插入L中，使L保持有序。
   int low=0,high=n-1,mid;
	while(low<high){
 		mid=(low+high)/2;
     	if(L.data[mid]==x){
     		//相等
      		move(L,mid,end);
      		L.data[mid]=x;
     	}
     	if(L.data[mid]<x){
      		low=mid+1;
     	}
     	if(L.data[mid]>x){
    	  	high=mid-1;
     	}
    }
    //low>high 的情况从low到n-1往后挪一位
    move(L,low,n);
    L.data[low]=x;
   }

void move(SeqList &L , int start,int end ){
    for(int i=end;i>=start;--i){
   	 L.data[i]=L.data[i-1];
    }
}

用顺序表表示集合，设计一个算法实现集合的求并集运算

void Union(SeqList A,SeqList B, SeqList &C){
   int i ,j,k;
   for(i=0;i<A.length;i++)//将A中元素复制到C中
    	C.data[i]=A.data[i];
   K=A.length;
   for(i=0;i<B.length;i++){//遍历B
    	j=0;
   	while(j<A.length&&B.data[i]!=A.data[j])
      	j++;	
   	if(j==A.length)//表示B.data[i]不在A中，将其放到C中
      		C.data[k++]=B.data[i];
    }
    C.length=k;
}

删除线性表最小元素（唯一）

void DelMin(SeqList &L){
//删除线性表最小元素
int i,min=L.data[0],tag=0;
for(i=1;i<L.length;i++){
 if(L.data[i]<min){
  min = L.data;
  tag = i;
 }
}
for(i=tag;i<L.length;i++){
 L.data[i] = L.data[i+1];
}
L.length--;
}

删除单链表一个节点

判断单链表是否递增

设计一个算法删除单链表L中值为X节点的直接前驱节点

递增有序单链表去重（叙述思想、给出实现、分析复杂度）

将单链表升序

已知两个递增有序单链表L1、L2 将两个链表合并且保持有序，然后逆置输出空间复杂度O（1）

系数矩阵A、B采用三元组表示，设计一个算法C=A+B C使用三元组表示

将元素X加入循环队列的算法

循环队列置空、入队、出队的算法

循环队列求最大值

写出冒泡法算法

void BubbleSort(ElemType A[] , int n){
    for(i = 0 ; i<n-1 ; i++){
        flag = false;  //标志本趟冒泡是否发生交换
        for(j=n-1;j>i;j--) //一趟冒泡
            if(A[j-1]>A[j]){ //若是逆序
                swap(A[j-1],A[j]);
                flag = true;
            }
        if(flag == flase)
            return;      //本趟冒泡没有发生交换，表示已经有序
    }
}

冒泡排序
A[ ]	0	1	2	3	4
初始序列	20	15	68	3	66
第一趟	3	20	15	68	66
第二趟	3	15	20	66	68
第三趟	3	15	20	66	68

写出快速排序算法

void QuickSort(ElemType A[],int n){
   if(low<high){//跳出递归的条件
       //Partition()划分操作，将表A 划分为满足条件的两个子表
       int pivotpos = Partition(A,low,high);//划分
       QuickSort(A,low,pivotpos-1);
       QuickSort(A,pivotpos+1,high);
   }
}
int Partition(ElemType A[],int low ,int high){//一趟划分
   ElemType pivot = A[low];  //当前表中第一个元素设为枢纽，对表划分
   while(low<high){  //循环跳出条件
       while(low<high&&A[high]>=pivot)--high;
       A[low]=A[high];   //将比枢轴元素小的元素移动到左端
       while(low<high&&A[low]<=pivot)++low;
       A[high]=A[low];   //将比枢轴元素打的移动到右端
   }
   A[low] = pivot;  //枢轴元素最终存储位置
   return low;   //返回存储位置
   
}

写出希尔排序算法

void ShellSort(ElemType A[] , int n){
    for(dk = n/2;dk>=1;dk=dk/2)     //步长变化
        for(i=dk+1;i<=n;++i)     
            if(A[i]<A[i-dk]){     //需要将A[i]插入有序增量子表
                A[0] = A[i];     //暂存A[0]
                for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
                	A[j+dk]=A[j];      //记录后移，查找插入位置
                A[j+dk]=A[0];     //插入该位置
            }
}

写出直接插入排序算法

void InsertSort(ElemType A[] , int n){
    for(int i=2 ; i<=n; i++) //依次将A[2....n]插入到前面的有序数列
        if(A[i]<A[i-1]){          //如果A[i]小于前驱 就将A[i]插入有序数列，否则不用移动
            A[0] = A[i];           //哨兵，存储需要移动的数的值
            for (int j=i-1; A[0]<A[j]; --j) //从后往前找插入位置
                A[j+1] = A[j];                   //向后挪位置
            A[j+1] = A[0];                      //将哨兵的值赋到找到的位置
        }
}

直接插入排序
A[ ]	0	1	2	3	4
初始序列	哨兵	15	68	3	66
第一趟	3	3	15	68	66
第二趟	66	3	15	66	68

写出折半插入排序算法

void InsertSort(ElemType A[] , int n){
//折半插入排序    
   int i,j,high,low,mid;
   for(i=2;i<=n;i++){
       if(A[i]<A[i-1]){
           A[0] = A[i];      //哨兵
           low = 1,high=i-1;     //折半查找范围
           while(low<=high){     //折半查找
               mid = (low+high)/2;
               if(A[mid]>A[0])high =mid-1;
               else low = mid+1;
           }
           for(j=i-1;j>high+1;--j)    //后移
               A[j+1]=A[j];
           A[high+1]=A[0];      //将元素放入指定位置
       }
   }
}

写出简单选择排序算法

void SelectSort(ElemType A[] , int n){
    for(i=0;i<n-1;i++){   //一共进行n-1趟
        min = j;    //记录最小元素位置
        for(j=i+1;j<n;j++)  //在A[i...n-1]中选择最小元素
            if(A[j]<A[min])min=j;//更新最小元素位置
        if(min!=i)swap(A[i],A[min]);//最小的元素跟第i个交换
    }
}

简单选择排序
A[ ]	0	1	2	3	4
初始序列	20	15	68	3	66
第一趟	3	15	68	20	66
第二趟	3	15	68	20	66
第三趟	3	15	20	68	66
第四趟	3	15	20	66	68

写出堆排序算法

void BuildMaxHeap(ElemType A[],int len){
   //大根堆的建立
   for(int i = len/2;i>0;i--)
       HeadAdjust(A,i,len);
}
Void HeadAdjust(ElemType A[],int k, int len){
   //对以元素k为根的子树进行调整
   A[0]=A[k];    //A[0]暂存子树的根节点
   for(i=2*k;i<=len;i*=2){ //沿key较大的子节点向下筛选
       if(i<len&&A[i]<A[i+1])
           i++;            //取key较大的子节点的下标
       if(A[0]>=A[i])break;  //筛选结束
       else{
           A[k]=A[i];     //将A[i]调整到双亲节点
           k=i;           //修改K值以便于继续筛选
       }
   }
   A[k]=A[0];   //被筛选节点的值放入最终位置
}
void HeapSort(ElemType A[] ,int len){
   BuildMaxHeap(A,len);//初始堆的建立
   for(i=len;i>1;i--){ //N-1趟交换和建堆的过程
       Swap(A[i],A[1]);//输出堆顶元素（和堆底元素交换）
       HeadAdjust(A,1,i-1);//调整，将剩余元素整理成堆
   }
}

归并排序

归并排序
A[ ]	0	1	2	3	4
初始序列	20	15	68	3	66
第一趟	15	20	3	68	66
第二趟	3	15	20	68	66
第三趟	3	15	20	66	68

在链式存储结构上统计二叉树中的节点个数

int CountNode(BiTreeNode *root){
//统计二叉树中的节点个数
   if (root==Null)//递归终止条件
   	return 0;
   if(root->l==Null&&root->r==Null)
       return 0;
   return 1+CountNode(root->r)+CountNode(root->l);
}

二叉树采用链式存储，求中序遍历中第一个节点的值

```c++

void FindValue(BiTreeNode* root){
//二叉树中序遍历第一个元素的值
BiTreeNode *p;
while(p!=Null&&p->l!=Null){
if (p->l==Null)
return p->value;
else
p=p->l;
}
}
```

层次输出二叉树所有节点（同一层从左到右）给出思想、实现方法、分析复杂度

void levelOrder(BiTree T){
//层序遍历二叉树所有节点
   InitQueue(Q);  //初始化队列
   BiTree p;   //临时存储出队元素
   EnQueue(Q,T); //头结点入队
   while(!IsEmpty(Q)){  
   	DeQueue(Q,p);  
   	print("%d",p->value); //输出节点值
   	if(p->l!=Null)
           EnQueue(Q,p->l);   //左孩子入队
       if(p->r!=Null)
   		EnQueue(Q,p->r); //右孩子入队
   }
}

计算平衡二叉树的高度

int Depth(BiTree T){
//计算平衡二叉树的高度
   if(!T)
   	return 0;
   else if(!T->lchild&&!T->rchild)
   	return 1;
   int h1 = Depth(T->lchild);
   int h2 = Depth(T->rchild);
   return 1+(h1>=h2?h1:h2);
}

递归求二叉树高度

int Depth(BiTree T){
//计算平衡二叉树的高度
   if(!T)
   	return 0;
   else if(!T->lchild&&!T->rchild)
   	return 1;
   int h1 = Depth(T->lchild);
   int h2 = Depth(T->rchild);
   return 1+(h1>=h2?h1:h2);
}

先序遍历二叉树

void PreOrder(BiTree T){
//先序遍历递归法
if(T!=Null){
 Visit(T);
 PreOrder(T->l);
 PreOrder(T->r);
}
void PreOrder(BiTree T){
//先序遍历非递归法
InitStack(S);BiTree p=T; //初始化栈S,p是遍历指针
while(p||!IsEmpty(S)){//栈不空或p不空循环
 if(p){    //一路向左
  Visit(p);Push(S,p);//访问节点并入栈
  p=p->l;   //左孩子不空就一直左走
 }else{
  Pop(S,p);  //出栈
  p=p->r;   //向右子树走
 }
}
}

中序遍历二叉树

判断一个图是否是连通图

设计算法求逆波兰式的值（例如输入 34 34+2/$ $表示结束）

**
**

用Prim算法给无向图构造

Kruskal****算法求最小生成树

画出无向图的邻接表和最小生成树

给设计哈夫曼树、编码并求所需要的字节

A:2% B:28% C:12% D:15% E:20% F:23%;

哈夫曼树转森林，哈夫曼树有N个非叶子节点，求总共多少节点

十二个月份开头字母 Jan Feb Mar Apr Jun Jul Aug Sep Oct Nov Dec

按照所给序列构造二叉排序树，删除Feb节点，画出删除后的二叉排序树，再加上Feb，写出前序、中序、后序遍历序列，画出二叉排序树、折半查找树、平衡二叉树的图，并求ASL成功

EBACDFHG是某二叉排序树的前序遍历序列（节点值大小按照字母顺序），画出此二叉排序树,画出二叉树对应的森林

根据后序DGHEBJIFCA、中序遍历DBGEHAFJIC序列画出二叉树写出前序，画出后序线索二叉树，根据二叉排序树判断大小

建立大根堆、小根堆的步骤，输出最小（大）值后，输出次小（大）值的结果图

用Dijkstra算法求定点到其他点的最短路径

V2
V3
V4
V5
V6
Vj

线性探测法、二次线性探测法且求ASL（成功）

设哈希表的地址范围是0-16 哈希函数为H（key） = key % 17分两次用线性探测法和二次线性探测法处理冲突，输入关键字序列（11,24，30,17,45,29,48,50,40,52,4）构造哈希表

\1. 画出两个哈希表示意图

线性探测法

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
数据
次数

二次线性探测法

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
数据
次数

\2. 若查找关键字45 需要依次和哪些关键字比较？

\3. 若查找关键字29 需要依次和哪些关键字比较？

\4. 假定每个关键字的查找概率相等，求查找成功和失败时的平均查找长度

求事件、活动的最早、最迟发生时间，求关键路径、关键活动

ABCDEFG的AOE网的邻接矩阵如图所示

\1. 画出有向无环图，标出活动

\2. 事件活动的最早最晚发生时间

事件	A	B	C	D	E	F	G
最早发生时间
最晚发生时间

活动	a	b	c	d	e	f	g	h
最早发生时间
最晚发生时间

\3. 关键路径、关键活动

标签：结点,数据结构,int,冲刺,算法,二叉树,排序,节点
From： https://www.cnblogs.com/smk110/p/16991809.html

第二趟是直接插入排序