算法與資料結構應知應會知識點
1、順序存儲結構的特點是什麼？
順序存儲時，相鄰資料元素的存放位址也相鄰（邏輯與實體的統一）；要求内容中可用存儲單元的位址必須是連續的。存儲密度大（=1），存儲空間使用率高，但是插入或删除元素時不友善。
2、鍊式存儲結構的特點是什麼？
鍊式存儲時，相鄰資料元素可随意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。
插入或删除元素時很友善，使用靈活。但是存儲密度小（<1），存儲空間使用率低。
3、順序隊列的“假溢出”是怎樣産生的？
一般的一維數組隊列的尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還有空位置，這就叫做“假溢出”。采用循環隊列是解決假溢出的途徑。
4、如何知道循環隊列是空還是滿？
解決隊滿隊空的辦法有三：
①設定一個布爾變量以差別隊滿還是隊空；
②浪費一個元素的空間，用于差別隊滿還是隊空；
我們常采用法②，即隊頭指針、隊尾指針中有一個指向實元素，另一個指向空閑元素。
③使用一個計數器記錄隊列中元素的個數（即隊列長度）；
判斷循環隊列的空标志是：f=rear 隊滿的标志是 f=(rear+1)%N
5、常用的五種資料結構運算？
插入、删除、查找、修改、排序。
6、線索化二叉連結清單的基本操作函數
**二：線索二叉樹
-
線索二叉樹的定義：n個結點的二叉連結清單中含有n+1[2n-(n-1)=n+1]個空指針域。利用二叉連結清單中的空指針域，存放指向結點在某種周遊次序下的前驅和後繼結點的指針（這種附加的指針稱為"線索"）。
因為n個節點有2n個指針
又因為n個節點中有n-1條邊（除了頭結點沒有邊，其餘節點都有一個父節點，相當于都有1條邊，共n-1條）
剩下的空鍊域就是2n-(n-1)=n+1，即n+1個空指針
2.線索二叉樹結構實作：線索化的實質就是将二叉連結清單中的空指針改為指指向前驅和後繼的線索，這種過程在周遊二叉樹時進行**
作用：線索化的作用是将樹可以像連結清單一樣周遊每一個節點 ，而不是用棧或遞歸的方法周遊
注：不同的線索化方式對應不同的線索化的周遊(并且一棵樹隻能線索化一次)
前序線索化-----前序線索化周遊 （根左右）
中序線索化-----中序線索化周遊 （左根右）
後序線索化-----後序線索化周遊 （左右根）
void preVisted(BitTree *root)
{
if(rootNULL) return ;
printf("%d ",root->data);
preVisted(root->lchild);
preVisted(root->rchild);
}
void nonPreVisted(BitTree *root)
{
if(rootNULL) return ;
Stack s;
init(&s);
push(&s,root);
while(!isEmpty(&s))
{
root=pop(&s);
printf("%d ",root->data);
if(root->rchild!=NULL) push(&s,root->rchild);
if(root->lchild!=NULL) push(&s,root->lchild);
}
}
7、無向圖中的節點數量與邊的關系函數是什麼？
無向完全圖 節點數為n，則有n(n-1)/2條邊。（有向完全圖有n(n-1)條邊。
8、稀疏矩陣的基本存儲方式，三類特殊矩陣的存儲方式。
①三元組表、十字連結清單。
②對稱矩陣：aij=aji，對稱矩陣中的元素關于主對角線對稱，故存儲矩陣中上三角或下三角中的元素，每兩個對稱的元素共享一個存儲空間。這樣，能節約近一半的存儲空間。一般情況下，按行優先順序存儲主對角線（包括對角線）以下的元素。
三角矩陣：以主對角線劃分，三角矩陣有上三角和下三角兩種。右上左下。
三角矩陣中的重複元素c可共享一個存儲空間，其餘元素正好有n(n-1)/2個，是以，三角矩陣可壓縮存儲到向量sa[nx(n-1)/2+1]中，其中c存放在向量的最後一個分量中。
對角矩陣: 對角矩陣中，所有非零元素都集中在以對角線為中心的帶狀區域中，即除主對角線和主對角線鄰近的上、下方，其他元素均為0.
對角矩陣可按行優先順序或對角線的順序，将其壓縮存儲到一個向量中，并且也能找到每個非零元素與向量下标的對應關系。
9、冒泡排序、希爾排序、快速排序的實作過程
希爾排序：縮小增量排序，
思想：首先，取一個小于n的整數d1作為第一個增量，把所需的所有資料分成d1個組，所有元素位置的距離為d1的整數倍放在同一數組中，在各組内進行直接插入排序；然後取第二個增量d2<d1，重複上述分組和排序，直至所取的增量d1=1，即把所有檔案放在同一組中進行直接插入排序為止。
我們選擇增量gap=length/2，縮小增量繼續以gap = gap/2的方式，這種增量選擇我們可以用一個序列來表示，{n/2,(n/2)/2…1}，稱為增量序列。
代碼：
void shellSort(int a[],int n)
{
int temp,i;
for(i=n/2;i>=1;i--)
{//增量序列i由n/2一次遞減直至i=1
for(int j=0;j<n-i;j++)
{//資料各組進行交換
if(a[i]>a[j+i];
a[i]=a[j+i];
a[j+i]=temp;
}
}
}
冒泡排序
它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
void bubbleSort(int data[],int n)
{
int i,j,t;
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
if(data[j]>data[j+1])
{
t=data[j];
data[j]=data[j+1];
data[j+1]=t;
}
}
//快速排序（老師）
快速排序又稱劃分交換排序。其基本思想：從一組待排的序列中，選一個“哨兵”，把所有
小于标兵的放在它的前面，大于标兵的放在它的後面。
通過這樣一次劃分，就把原來的序列劃分成兩個序列，然後再對左右兩邊的序列做同樣的快速排序，直至劃分後的序列隻有一個元素，整個排序結束。
int quickOne(int a[],int low,int high)
{
int temp=a[low];//預設第一個為哨兵，存到一個臨時空間
while(low<high)
{//從high向左掃描，找到第一個小于哨兵的數
while(low<=high&&temp<=a[high]) high--;
a[low]=a[high];//把它存入low所指的位置；a[high]位置空間空餘
while(low<high&&temp>a[low]) low++;//從low向右掃描，找出第一個大于哨兵的元素。
a[high]=a[low];//把它存入high所指的位置；a[low]位置空間空餘
}
a[low]=temp;//基準temp已被最後定位，此時low=high;
return low;
}
void quickSort(int a[],int low,int high)
{
int i=quickOne(a,low,high);
if(low<i-1)quickSort(a,low,i-1);//遞歸初一左邊的資料
if(high>i+1)quickSort(a,i+1,high);//遞歸處理右邊的資料
}
10、常用查找的平均查找長度計算公式，如二分查找、二叉排序樹查找、線性探查法、拉鍊法
順序查找法：ASL=（n+1）/2
二分查找：每一次最多查2(n-1)個，ASL=（1*1+2*2+3*4+4*8+···+i*(n-2(i-1)）)/n
n是總數，次數每次查找的個數，最後一次不一定是2^(次數-1）個，是剩下的個數。别忘了除以總數。
二叉排序樹查找：ASL=（第一次（層）查找個數+第二層查找個數+···第i層查找個數）/總數
線性探查法、拉鍊法
11、二叉連結清單算法
BitTree *createBitTree()
{
BitTree *root=NULL;
int m;
scanf("%d",&m);
if(m>0)
{
root=(BitTree*)malloc(sizeof(BitTree));
root->data=m;
root->lchild=createBitTree();
root->rchild=createBitTree();
}
return root;
}
12、雙向連結清單的基本操作
雙連結清單，在雙連結清單中的每個結點除資料域外還有兩個指針域：一個指向其前驅結點；另一個指向其後繼結點。
13、插入排序的基本查找次數如何計算
答案：B
//插入排序
void InsertSort(int a[],int n)
{
int i,j,temp;
for(i=1;i<n;i++)
{
temp=a[i];
j=i-1;
while(j>=0&&temp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
-------------------------）
14、堆棧的基本操作
棧是一種特殊的線性表，允許插入和删除運算的一算稱為棧頂，不允許插入和删除運算的一算稱為棧底。
/*
棧的定義：
棧是限定在表位插入和删除操作的線性表
允許插入和删除的一端稱為棧頂（top），另一端稱為棧底（bottom）
不含任何資料元素的棧稱為空棧。
棧的特點：
先進後出
後進先出（Last In First Out) 簡稱LIFO結構
棧的插入操作稱為進棧，也稱為壓棧、入棧（push）
*/
/*鍊棧的結點*/
typedef struct StackNode
{
ElementType data;//節點中儲存的元素
struct StackNode* next;//指向下一個結點的指針
}StackNode;
/*鍊棧結構*/
typedef struct LinkedStack
{
StackNode*top;//棧頂指針
int length;//鍊棧的長度（元素個數）
}LinkedStack;
/*鍊棧的初始化*/
void InitLinkStack(LinkedStack*linkedStack)
{
//1.棧頂指針指向空
linkedStack->top=NULL;
//2.長度為0
linkedStack->length=0;
}
/*壓棧并傳回結果*/
int PushLinkedStack(LinkedStack*linkedStack,ElementType element)
{
//1.建立一個新結點
StackNode*newNode=(StackNode*)malloc(sizeof(StackNode));
newNode->data=element;
//新結點的next域指向目前的棧頂
newNode->next=linkedStack->top;
linkedStack->top=newNode;
linkedStack->length++;
return TRUE;
}
/*出棧并傳回出棧的元素*/
int PopLinkedStacked(LinkedStack*linkedStack,ElementType*element)
{
if(linkedStack->top==NULL)
{
printf("這是一個空棧，出棧操作失敗！\n");
return FALSE;
}
//傳回棧頂元素
*element=linkedStack->top->data;
StackNode*node=linkedStack->top;
//棧頂指針下移一位
linkedStack->top=linkedStack->top->next;
//釋放原棧頂空間
free(node);
linkedStack->length--;
return TRUE;
}
15、廣義表的原子操作
廣義表表示
（1）廣義表常用表示
① E=()
E是一個空表，其長度為0。
② L=(a，b)
L是長度為2的廣義表，它的兩個元素都是原子，是以它是一個線性表
③ A=(x，L)=(x，(a，b))
A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。
④ B=(A，y)=((x，(a，b))，y)
B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。
⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
C的長度為2，兩個元素都是子表。
⑥ D=(a，D)=(a，(a，(a，(…))))
D的長度為2，第一個元素是原子，第二個元素是D自身，展開後它是一個無限的廣義表。
（2）廣義表的深度
一個表的"深度"是指表展開後所含括号的層數。
【例】表L、A、B、C的深度為分别為1、2、3、4，表D的深度為∞。
（3）帶名字的廣義表表示
如果規定任何表都是有名字的，為了既表明每個表的名字，又說明它的組成，則可以在每個表的前面冠以該表的名字，于是上例中的各表又可以寫成：
①E()
②L(a，b)
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))
注意:
廣義表()和(())不同。前者是長度為0的空表，對其不能做求表頭和表尾的運算；而後者是長度為l的非空表(隻不過該表中惟一的一個元素是空表)，對其可進行分解，得到的表頭和表尾均是空表()。
16、樹的層次與節點計算的2種算法
17、二叉樹的三種周遊算法，根據其中2種周遊結果推算出第3中周遊結果；中序周遊線索圖的繪制過程。
（在另一個試卷中）
18、大根堆和小根堆如何建構
Heap是一種資料結構具有以下的特點：
1）完全二叉樹；
2）heap中存儲的值是偏序；
Min-heap: 父節點的值小于或等于子節點的值；
Max-heap: 父節點的值大于或等于子節點的值；
堆的存儲：
一般都用數組來表示堆，i結點的父結點下标就為(i–1)/2。它的左右子結點下标分别為2 * i + 1和2 * i + 2。如第0個結點左右子結點下标分别為1和2。
19、哈夫曼編碼和WPL計算
（筆記2）
20、無向圖的鄰接矩陣及其對應的順序表，從頂點A出發的深度DFS周遊序列和廣度WFS周遊序列
（筆記2）
21、普裡姆（Prim）算法和魯斯卡爾算法求其最小生成樹
普裡姆（Prim）算法
從指定頂點開始将它加入集合中,然後将集合内的頂點與集合外的頂點所構成的所有邊中選取權值最小的一條邊作為生成樹的邊,
并将集合外的那個頂點加入到集合中,表示該頂點已連通.
再用集合内的頂點與集合外的頂點構成的邊中找最小的邊,并将相應的頂點加入集合中,如此下去直到全部頂點都加入到集合中,即得最小生成樹.
魯斯卡爾算法
方法:将圖中邊按其權值由小到大的次序順序選取,若選邊後不形成回路,則保留作為一條邊,若形成回路則除去.依次選夠(n-1)條邊,即得最小生成樹.(n為頂點數)
步驟：
第一步:由邊集數組選第一條邊，即權值為1的邊；
第二步:選第二條邊,即權值為2的邊；
第三步:選第三條邊,即權值為3的邊；
第四步:選第四條邊,即權值為4的邊；
第五步:選第五條邊。
22、有向圖G如下圖所示，将其看成AOE網給出關鍵路徑和關鍵路徑長度
帶權有向圖，頂點表示事件，弧表示活動。弧上的權值表示活動持續時間，此有向圖稱為AOE網，在建築學也稱為關鍵路線。AOE網常用于估算工程完成時間。
ve(j)
【含義】 事件（頂點）最早發生的時間
【解釋】這個事件（這個工作，這個工程）最早什麼時候能開始
【定性來談】ve(j)=從源點到頂點j的最長路徑長度
彙點（終點）的【最早發生時間】：即為整個工程能夠【最早完成的時間】
【解釋】中途不拖拉，一個工作完成，下一個工作立刻動手。整個工程保質保量的幹下來（效率最高），最早能夠完成的時間。我們記為plan_time，後面要用到
計算技巧：
(1)從前向後，取大值：直接前驅結點的Ｖe(j)＋到達邊（指向頂點的邊）的權值，有多個值的取較大者
(2)首結點Ve(j)已知，為0
vl(k)
【含義】事件（頂點）的最遲發生時間vl(k)
【解釋】上面談到plan_time，與這個有關。假設，我們要在plan_time的時間内把整個工作做完，每個小工作最遲開始的時間稱之為【最遲發生時間】。也就是說，【小工程】最遲什麼時候開始，它不會影響總工程的按時的完成
【定性來談】vl(k)=從頂點k到彙點（終點）的最短路徑長度
最遲發生時間：Ø l(i): 若活動ai由弧<vk,vj>表示，則ai的最晚開始時間要保證事件vj的最遲發生時間不拖後。 因而有：l[i]=vl[j]-len<vk,vj>1（為邊（活動）的到達頂點的最晚發生時間減去邊的權值）
計算技巧： (1)從後向前，取小值：直接後繼結點的Ｖl(j) –發出邊（從頂點發出的邊）的權值，有多個值的取較小者;
(2)終結點Vl(j)已知，等于它的Ve(j)
23、二維數組的行優先和列優先的存儲位址的計算
**行優先順序：将數組元素按行向量排列，第i+1個行向量緊接在第i行向量之後，以二維數組為例，按行優先順序存儲的線性序列為：
a11,a12,
,a1n,a21,a22,
,a2n,
am1,am2,amn 列優先順序：将數組元素按列向量排列，第j+1個列向量緊接在第j個列向量之後，A的m*n個元素按列優先順序存儲的線性序列為： a11,a21,
,am1,a12,a22,
,am2,
,a1n,a2n,amn
二維數組A[4][5]按行優先順序存儲,若每個元素占2個存儲單元,且第一個元素A[0][0]的存儲位址為1000
則數組元素A[3][2]存儲位址為?求詳解 請給詳細過程和思路解答 這種題該怎麼做?
A[i][j]的首位址 =
數組的在記憶體中的基位址（=1000）
- i * 列數（=5）* 每個元素占單元數（=2）
-
j * 每個元素占單元數（=2）
代入得：
A[3][2] 首位址 = 1000 + 3 * 5 2 + 2 * 2 = 1034*
24、采用堆棧實作二叉樹的深度算法
int Getdepth(BTree*T)
{ int ld,rd;
if(!=T) return 0;
else{
ld=Getdepth(T->lchild);
rd=Getdepth(T->rchild);
return ld>rd?(ld+1):(rd+1);
}
}
25、時間複雜度計算方法
1、常數階
首先順序結構的時間複雜度。
這個算法的運作次數函數是f (n) =3。 根據我們推導大0階的方法，第一步就是把常數項3 改為1。在保留最高階項時發現，它根本沒有最高階項，是以這個算法的時間複雜度為0(1)。
*另外，我們試想一下，如果這個算法當中的語句 sum = (1+n)n/2; 有10 句，則與示例給出的代碼就是3次和12次的差異。這種與問題的大小無關（n的多少），執行時間恒定的算法，我們稱之為具有O(1)的時間複雜度，又叫常數階。對于分支結構而言，無論是真，還是假，執行的次數都是恒定的，不會随着n 的變大而發生變化，是以單純的分支結構(不包含在循環結構中)，其時間複雜度也是0(1)。
2、線性階
線性階的循環結構會複雜很多
3、對數階
如下代碼：
由于每次count乘以2之後，就距離n更近了一分。 也就是說，有多少個2相乘後大于n，則會退出循環。 由2^x=n 得到x=logn。 是以這個循環的時間複雜度為O(logn)。
4、平方階
下面例子是一個循環嵌套，它的内循環剛才我們已經分析過，時間複雜度為O(n)。
而對于外層的循環，不過是内部這個時間複雜度為O(n)的語句，再循環n次。 是以這段代碼的時間複雜度為O(n^2)。
如果外循環的循環次數改為了m，時間複雜度就變為O(mXn)。
這裡循環了(12+22+32+……+n2) = n(n+1)(2n+1)/6次，按照上述大O階推導方法，時間複雜度為O(n^3)。
26、資料結構的表達表示方法
?
27、帶頭結點和無頭結點的單連結清單L的判空條件
帶頭結點的單連結清單的L指向頭結點
則L->nextNULL
不帶頭結點的單連結清單的L指向第一個結點
則LNULL
28、堆棧的基本操作算法
/*
棧的定義：
棧是限定在表位插入和删除操作的線性表
允許插入和删除的一端稱為棧頂（top），另一端稱為棧底（bottom）
不含任何資料元素的棧稱為空棧。
棧的特點：
先進後出
後進先出（Last In First Out) 簡稱LIFO結構
棧的插入操作稱為進棧，也稱為壓棧、入棧（push）
*/
//定義資料元素
typedef struct
{
int x;
int y;
int type;
}ElementType;
/*鍊棧的結點*/
typedef struct StackNode
{
ElementType data;//節點中儲存的元素
struct StackNode* next;//指向下一個結點的指針
}StackNode;
/*鍊棧結構*/
typedef struct LinkedStack
{
StackNode*top;//棧頂指針
int length;//鍊棧的長度（元素個數）
}LinkedStack;
/*鍊棧的初始化*/
void InitLinkStack(LinkedStack*linkedStack)
{
//1.棧頂指針指向空
linkedStack->top=NULL;
//2.長度為0
linkedStack->length=0;
}
/*壓棧并傳回結果*/
int PushLinkedStack(LinkedStack*linkedStack,ElementType element)
{
//1.建立一個新結點
StackNode*newNode=(StackNode*)malloc(sizeof(StackNode));
newNode->data=element;
//新結點的next域指向目前的棧頂
newNode->next=linkedStack->top;
linkedStack->top=newNode;
linkedStack->length++;
return TRUE;
}
/*出棧并傳回出棧的元素*/
int PopLinkedStacked(LinkedStack*linkedStack,ElementType*element)
{
if(linkedStack->top==NULL)
{
printf("這是一個空棧，出棧操作失敗！\n");
return FALSE;
}
//傳回棧頂元素
*element=linkedStack->top->data;
StackNode*node=linkedStack->top;
//棧頂指針下移一位
linkedStack->top=linkedStack->top->next;
//釋放原棧頂空間
free(node);
linkedStack->length--;
return TRUE;
}
29、散列法存儲存在幾種沖突，常用的沖突處理方法有？
線上性表的散列存儲中，處理沖突的常用方法有（）和（）兩種。
開放定址法；連結法
30、共享棧的基本概念和操作
共享棧，即是兩個棧使用同一段存儲空間。
第一個棧從數組頭開始存儲，第二個棧從數組尾開始，兩個棧向中間拓展。
當top1+1top2或者top1top2-1時，即staock overflow!.
與普通棧一樣，共享棧出棧入棧的時間複雜度仍為O(1).
31、KMP算法的特點
KMP算法最大的特點就是訓示主串的指針不需要回溯，是以指針不可能變小
32、鄰接表是一種結合了順序存儲與鍊式存儲的存儲格式，在那些結構中被使用
圖的存儲結構
33、Dijkstra方法計算有向圖G的最短路徑生成和計算
我記得這個方法好像有問題，我有點忘記了，但是其他的方法在另一個筆記中。過了好幾個月了，我基本上都還回去了。
給自己講的：我記得了，試卷别丢啊，這個是一個同學院同學給我的複習題裡面的，在那個裡面手寫了這個比較好算的方法可能。我真的是越來越健忘了，救救孩子吧。