专升本数据结构复习
數據結構知識點總匯
主要參考書目：
推薦視頻：西北大學 數據結構-耿國華老師
說明：這是本人專升本上岸一年后寫的，本篇包含知識點和例題總結。因為是當時自己手碼的，所以知識點有冗余和順序錯位。如果發現有錯誤之處，歡迎評論區留言，看到后及時改正，謝謝！最后祝大家好好學習，積極向上，早日上岸！
① 數據結構(邏輯結構)其4類基本結構：集合、線性結構、樹形結構、圖狀結構 和 網狀結構。
② 物理結構(存儲結構)其4種存儲結構：順序存儲結構、鏈式存儲結構、索引存儲結構 和 散列存儲結構。
③ 算法5個重要特性：有窮性、確定性、可行性、輸入 和 輸出。
?? 通常從四個方面評價算法的質量：正確性、易讀性、強壯性 和 高效率。
④ 線性表是由n≥0個數據元素組成的 有限序列。其特點為邏輯關系上相鄰的兩個元素在物理位置上也相鄰。
⑤ 在順序表中實現的基本運算：
??插入：平均移動結點次數為 n/2；平均時間復雜度均為O（n）。
??刪除：平均移動結點次數為 （n-1）/2；平均時間復雜度均為O（n）。
⑥ 存儲位置計算：每個元素需占用L個存儲單元第一個單元的存儲地址作為數據元素的存儲位置線性表的第i個數據元素ai的存儲位置為LOC(ai)=LOC(a1)+(i-1)*L ，a1的存儲位置，通常稱做線性表的起始位置或基地址。
⑦ 線性表的鏈式存儲結構：數據元素ai的存儲映像稱為結點，包括2個域：存數據的 數據域、存后繼存儲位置的 指針域。
⑧ 線性鏈表(單鏈表)特點：每個結點只包含1個指針域。在單鏈表的第一個結點之前附設的一個結點，稱之為 頭結點。
⑨ 假設L是LinkList型變量，則L為單鏈表的頭指針，它指向表中第一個結點。
??L->next 為第一個結點地址，L->next=NULL為 空表。
??回收結點：free(q)。
⑩ 棧：是限定僅在 棧頂(表尾)進行插入或刪除操作 的線性表。表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為 后進先出 的線性表。
? 隊列：是一種 先進先出 的線性表，它只允許在表的一端進行插入，而另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端則稱為隊頭。
? 鏈隊列：用鏈表示的隊列。一個隊列需要頭指針和尾指針才能確定唯一。
⑩ 棧：是限定僅在 棧頂(表尾)進行插入或刪除操作 的線性表。表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為 后進先出 的線性表。
? 隊列：是一種 先進先出 的線性表，它只允許在表的一端進行插入，而另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端則稱為隊頭。
? 鏈隊列：用鏈表示的隊列。一個隊列需要頭指針和尾指針才能確定唯一。
? 循環隊列：兩個指針front指示隊列頭元素和rear指示隊列尾元素的位置。初始化建空隊列時，令front = rear = 0，每當插入新的隊列尾元素時，“尾指針增1”；每當刪除隊列頭元素時，“頭指針增1”。
? 串：是由零個或多個字符組成的有限序列。
? 數組的存儲位置計算：假設每個數據元素需占用L個存儲單元，則二維數組A中任一元素A[ij]的存儲位置可由下式確定：
??以行序為主序的存儲結構：LOC(i,j)=LOC(0,0)+(n*i+j)*L;(n為行數)
??以列序為主序的存儲結構：LOC(i,j)=LOC(0,0)+(n*j+i)*L;(n為列數)
? 廣義表：是線性表的推廣，在廣義表的定義中，ai可以是單個元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。
? 二叉樹的性質：
??性質1：在二叉樹的第K層上至多有 2k-1 個結點(K≥1)。
??性質2：深度為k的二叉樹至多 2k-1 個結點(k≥1)。
??????深度為k的二叉樹至少有k個結點(k≥1)。
??????深度為k的完全二叉樹至少有 2k-1 個結點(k≥1)。
??性質3：對任何一棵二叉樹T，如果其終端結點數為N0，度為2的結點數為N2，則 N0=N2+1。總結點個數 N=N0+N1+N2。
??性質4：具有n個結點的完全二叉樹的深度為 [log2n]+1。
? 滿二叉樹：一顆深度為k且有 2的k次方減1個結點的二叉樹。
? 完全二叉樹：深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應。
? 樹轉換成二叉樹：連兄弟，留長子，刪孩子。
??注意：由于樹根沒有兄弟結點，固樹轉換為二叉樹后，二叉樹根結點的右子樹必為空。
① 森林轉換成二叉樹：連樹根及兄弟，留長子，刪孩子。
② 二叉樹轉換成樹：連左孩子的右孩子及其右孩子…，刪原樹右孩子。
③ 赫夫曼樹：又稱最優樹，是一類帶權路徑長度最短的樹。
WPL=23+43+52+71=35
④ 赫夫曼編碼：在赫夫曼樹上，左分支代表0，右分支代表1。由根結點到指定結點的路徑(從上到下把0、1連起來)，就是該結點的赫夫曼編碼；如上圖(d)中a為0，b為10，c為110，d為111。
⑤無向完全圖：有 n(n-1)/2 條邊的無向圖。
?有向完全圖：有 n(n-1) 條邊的有向圖。
⑥鄰接矩陣：無向圖的鄰接矩陣關于主對角線對稱，在整個矩陣中非零元素的個數等于邊個數的2倍，第i行和第i列中非零元素的個數等于該結點的度。
⑦ 鄰接表：無向圖的鄰接矩陣關于主對角線對稱，在整個矩陣中非零元素的個數等于邊個數的2倍，第i行和第i列中非零元素的個數等于該結點的度。
⑧ 深度優先遍歷：
⑨ 廣度優先遍歷：
⑩ 最小生成樹：
普里姆算法（Prim）：連相鄰權值最小的。
克魯斯卡爾算法（Kruskal）：先連權值最小的，再依次連。
? 拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序的操作。
?順序查找法平均查找長度：ASL=(n+1)/2。
?折半查找法（二分查找法）平均查找長度：ASL=(n+1)/n*log2(n+1)-1
?索引順序表查找法（分塊查找法）平均查找長度：ASL≈log2(n/s+1)+s/2。
? 直接插入排序：將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表。
? 冒泡排序：首先將一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關鍵字。以此類推，直至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。
? 快速排序：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
① 順序表是隨機存儲結構，當線性表的操作 主要是查找時，宜采用以插入和刪除操作為主的線性表宜采用 鏈表 做存儲結構。若 插入和刪除主要發生在表的首尾兩端，則宜采用尾指針表示的單循環鏈表。
② 在順序棧中有“上溢”和“下溢”的現象，“上溢”是棧頂指針指出棧的外面是出錯狀態，“下溢”可以表示棧為空棧，因此用來作為控制轉移的條件。
③ 隊列 是一種運算受限的線性表，允許刪除的一端稱為隊頭（front），允許插入的一端稱為隊尾（rear） ，隊列的操作原則是先進先出的，又稱作FIFO表。隊列也有順序存儲和鏈式存儲兩種存儲結構。
④循環隊列：判定循環隊列是空還是滿，方法有三種：
?一種是另設一個布爾變量來判斷；
?第二種是少用一個元素空間，入隊時先測試（（rear+1）%m = front）？ 滿：空；
?第三種就是用一個計數器記錄隊列中的元素的總數。
⑤ 隊列的鏈式存儲結構稱為鏈隊列，為了便于在表尾進行插入（入隊）的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。
在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。
⑥ 串是零個或多個字符組成的有限序列。
?空串：是指長度為零的串，也就是串中不包含任何字符（結點）
?空白串：指串中包含一個或多個空格字符的串。
⑦ 子串在主串中的序號就是指子串在主串中首次出現的位置。空串是任意串的子串，任意串是自身的子串。
⑧ 串的基本運算有：
?求串長strlen（char*s） 串復制strcpy（char*to，char*from）
?字符定位strchr（char*s，charc） 串聯接strcat（char*to，char*from）
?串比較charcmp（char*s1，char*s2）
⑨地址的計算方法：
?按行優先順序排列的數組：LOCa（ij）=LOCa（11）+（（i-1）*n+（j-1））*d
?按列優先順序排列的數組：LOCa（ij）=LOCa（11）+（（j-1）*n+（i-1））*d
⑩圖的存儲結構：
?鄰接矩陣表示法：用一個n階方陣來表示圖的結構是唯一的；無向圖中鄰接矩陣是對稱的；有向圖中行是出度，列是入度。
?鄰接表表示法：用頂點表和鄰接表構成不是唯一的；頂點表結構 vertex | firstedge，指針域存放鄰接表頭指針；鄰接表是用頭指針確定。
?圖的遍歷：
?深度優先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結點。
?廣度優先遍歷：借助于鄰接矩陣的行。使用隊列保存已訪問結點。
? 直接插入排序：
? 直接選擇排序：
? 冒泡排序：
? 快速排序：
① n個結點的二叉樹共有 2n 個指針域，其中有 n-1 個指針域是存放了地址，有 n+1 個指針是空指針。
② 在一個具有n個頂點的無向完全圖中，包含有 e 條邊，在一個具有n個頂點的有向完全圖中，包含有 2e 條邊。
③ 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為 O(log2n)，整個堆排序過程的時間復雜度為 O(nlog2n)。
④ AOV網是一種 有向無回路 的圖。
⑤ 設哈夫曼樹中的葉子結點總數為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有 2m 個空指針域。（m個葉子節點的哈夫曼樹總共有2m-1個節點）
⑥ 設順序循環隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環隊列中的元素個數為 (R-F+M)％M。
⑦ 快速排序的最壞時間復雜度為 O(n2)，平均時間復雜度為 O(nlog2n)。
⑧ 數據的物理結構主要包括 順序存儲結構 和 鏈式存儲結構 兩種情況。
⑨ 二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度 不超過 二叉判定樹的高度 1+log2n。
⑩ 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為 O(n2)，快速排序的平均時間復雜度為 O(nlog2n)。
? 設指針變量p指向雙向循環鏈表中的結點X，則刪除結點X需要執行的語句序列為 p>llink->rlink=p->rlink ; p->rlink->llink=p->rlink（設結點中的兩個指針域分別為llink和rlink）。
? 設有一個順序循環隊列中有M個存儲單元，則該循環隊列中最多能夠存儲 m-1 個隊列元素；當前實際存儲 (R-F+M)%M 個隊列元素（設頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。
? 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是 A[i][j]=1。
? 數據項是不可分割的構成數據元素的最小單位；數據元素是數據的基本單位。
? 設一個有序的單鏈表中有n個結點，現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為 O(n)。
兩方面：一是插入時間復雜度O(1)；二是保持有序時間復雜度O(n)
? 設一棵m叉樹中度數為0的結點數為N0，度數為1的結點數為Nl，……，度數為m的結點數為Nm，則N0= l+N2+2N3+3N4+……+(m-1)Nm。
【注解】由2叉樹的性質引申出，對于任何一顆樹T，如果其終端結點樹為n0 度為i的結點數為ni，則n0=1+n2+2n3+···+(i-1)ni
? 設有一個順序共享棧S[0：n-1]，其中第一個棧項指針top1的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是 top1+1=top2。
? 在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是 可以隨機訪問到任一個頂點的簡單鏈表。
?設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是 head==0。
?不帶頭結點是 head==NULL，帶頭結點是 head->next==NULL
?設帶有頭結點的單向循環鏈表的頭指針變量為head，則其判空條件是 head->next==head。
? 設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是 只有一個孩子節點(或 高度等于其結點數)。
① 設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為 rear->next=s ；rear=s。（注意：入隊要從隊尾入）
② 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的新結點X，則進行插入操作的語句序列為 s->next=p->next ; p->next=s（設結點的指針域為next）。
③ 設F和R分別表示順序循環隊列的頭指針和尾指針，則判斷該循環隊列為空的條件為 F==R
④ 設二叉樹中結點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結點為葉子結點的條件是
p->lchild==NULL && p->rchild==NULL。
⑤ 散列表中解決沖突的兩種方法是 開放定址法 和 鏈地址法。
⑥ 設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為 top=top->next；
?若指針變量top指向當前順序棧的棧頂，則刪除棧頂元素的操作序列為 top=top-1
⑦ 設指針變量p指向雙向鏈表中的結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為
s->left=p；s->right=p->right；p->right=s； p->right->left=s；
（設結點中的兩個指針域分別為left和right）。
⑧ 解決散列表沖突的兩種方法是 開放定址法 和 鏈地址法。
⑨ 設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X需要執行的語句序列：s->next=p->next ; p->next=s 。
⑩ 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量p和指針變量head之間的關系是p=head->rlink 和head=p->llink（設結點中的兩個指針域分別為llink和rlink）。
? 設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為
s->left=p；s->right=p->right；p->right->left=s； p->right=s；。
? 設散列表中有m個存儲單元，散列函數H(key)= key % p，則p最好選擇 小于等于m的最大素數。
?設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為 6.5。
?設分塊查找中將長為 n 的表分成均等的 b 個塊,每塊 s 個元素,則 b = (n / s)上取整。
?如果索引表中采用順序查找,則ASL=(b+1)/2+(s+1)/2;
?如果索引表中采用折半查找,則ASL=(s+1)/2+log2(b+1)-1;
? 設指針p指向單鏈表中結點A，指針s指向被插入的結點X，則在結點A的前面插入結點X時的操作序列為：
?設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列 雙向循環鏈表 存儲方式最節省運算時間。
?如果只是插入元素，單向循環列表就可以了；
?如果還需要刪除元素，就要雙向循環列表，可以最快的找到尾節點的前一個節點。
? 有N個關鍵字排序，各排序最大最小情況如下：
? 快速排序算法的平均時間復雜度為 O(nlog2n)，直接插入排序算法的平均時間復雜度為 O(n^2)。
? 設一棵m叉樹脂的結點數為n，用多重鏈表表示其存儲結構，則該樹中有 n(m-1)+1 個空指針域。
【注解】m叉樹n個結點，得出總的指針域為m*n，不為空的指針域就等于分枝數，根結點沒有分支指向它，推出非空指針域為n-1，總指針域減非空指針域就等于空的指針域即m*n-（n-1）
? 設指針變量p指向單鏈表中結點A，則刪除結點A的語句序列為：
q=p->next；p->data=q->data；p->next= q->next；feee(q)；
① 數據結構從邏輯上劃分為三種基本類型：線性結構，樹型結構 和 圖型結構。
② 設無向圖G中有n個頂點e條邊：則用鄰接矩陣作為圖的存儲結構進行深度優先或廣度優先遍歷時的時間復雜度為 O(n^2)；
?用鄰接表作為圖的存儲結構進行深度優先或廣度優先遍歷的時間復雜度為 O(n+e)。
③ 鄰接表是圖的一種 鏈式存儲結構。
④ 樹最適合用來表示 元素之間具有分支層次關系的數據。
⑤ 在一個單鏈表中，若要刪除由指針q所指向結點的后繼結點（若存在），則執行 p=q->next；q->next=p->next 操作。
⑥ 常對數組進行的兩種基本操作是 索引 和 修改。
⑦ 在一個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在q和p之 間插入s所指結點，則執行 q->next=s;?s->next=p 操作。
⑧ 設有兩個串p和q，求q在p中首次出現的位置的運算稱作 模式匹配。
⑨ 一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，則有
n=2m-1 成立。
⑩ 實現圖的廣度優先搜索遍歷算法需要使用 隊列，深度優先搜索遍歷算法需要使用 棧。
? 順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。
? 樹的先序對應二叉樹的先序，樹的后序對應二叉樹的中序。
? 在?n(n>0)?個元素的順序棧中刪除1個元素的時間復雜度為：?O(1)。
?
?設?SQ?為循環隊列，存儲在數組?d[m]?中，則?SQ?出隊操作對其隊頭指針?front?的 修改是?front?=?(front+1)%m??。
?對于一個以順序實現的循環隊列Q[0…m-1]，隊頭、隊尾指針分別為f、r，其判空的條件是?r=f，判滿的條件是 (r+1)%m=f。
① 設計一個判別表達式中括號是否匹配出現的算法，采用 棧 的數據結構最佳。
② 設廣義表L=((a,b,c)),則L的長度為1，深度為2。
③ 衡量查找算法效率的主要標準是 平均查找長度。
④ 棧和隊列都是 限制存取點的線性結構。
⑤ 在稀疏矩陣的三元組順序表中，每個三元組表示 矩陣中非零元素的行號、列號和數據值。
⑥ 順序結構邏輯上相鄰的結點物理上也是相鄰的。因此，其存儲密度大，存儲空間利用串高。
⑦ 含有n個結點的二叉樹采用二叉鏈表存儲時，空指針域的個數為 n+1，非空指針個數為 n-1。
⑧ 在數據結構中，從存儲結構上可以將之分為 順序存儲和非順序存儲；從邏輯結構上可以將之分為 線性結構和非線性結構。
⑨ 深度優先遍歷類似二叉樹的 先序遍歷；廣度優先遍歷類似二叉樹的 層次遍歷。
⑩ n個頂點的有向圖最多有 n(n-1)條邊；無向圖最多有 n(n-1)/2 條邊。
? 如果要求用線性表既能較快地查找,又能適應動態變化的要求,則可采用 分塊查找。
? 任意一棵二叉樹的葉子結點在其先序、中序和后序序列中的相對位置 不發生變化。
? 在單鏈表指針為p的結點之后插入指針為s的結點,正確的操作是 s->next=p->next;p->next=s。
? 某算法的時間復雜度是O(n^2)，表明該算法的 執行時間與n^2成正比。
? 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為 n,占用的存儲空間為 2e。
? 對于順序表，訪問某結點的時間復雜度為 O(1)，刪除某結點的時間復雜度為 O(n)。
? 以數據集{4,5,6,7,10,12,18}為結點權值，畫出構造的哈弗曼樹，并計算其帶權路徑長度。
?廣義表(a,(b,c),d,e)的表頭為 a。
?已知廣義表L=(a,(b,(c,(d)), e), f )，則：
?L1=Tail(L)=((b,(c,(d)), e), f )
?L2=Head(L1)= (b,(c,(d)), e)
?L3=Tail(L2)=((c,(d)), e)
?L4=Head(L3)=(c,(d))
?L5=Head(L4)= c
? 樹最適合用來表示的結構是 元素間具有分支層次關系的結構。
? 圖G是一個非連通無向圖，共有28條邊，則該圖至少有 9 個頂點。
① 棧的特點是 一個線性結構，數據先進后出，且只能在棧頂進行增刪操作。
② 與數據元素本身的形式、內容、相對位置、個數無關的是數據的 邏輯結構。
③ 數據結構被形式定義為（D, R），其中D是 數據元素 的有限集合，R是D上的 關系 有限集合。
④ 當利用大小為N的數組順序存儲一個棧時，假定用top= =N表示棧空，則向這個棧插入一個元素時，首先應執行 top-- 語句修改top指針。
⑤ 設有一個字符串S=“abcdefgh”，問該串的最大子串個數為 37。
⑥ 若StrIndex(S,T)表示求T在S中的位置的操作，則對于S=“Beijing and Nanjing”，T=“jing”，StrIndex(S,T)的結果為4。
⑦ 字符串按存儲方式可以分為：順序存儲、鏈接存儲和 堆分配存儲。
⑧ 在C語言中，以字符 \0表示串值的終結。
⑨ A[N, N]是對稱矩陣，將下三角（含對角線）以行序存儲到一維數組arr[N(N+1)/2]中，則對任一上三角元素arr[i, j]對應arr[k]的下標k是：解析如下
⑩ 有一個100*90的稀疏矩陣，非零元素有10個，設每個整型數占2個字節，則用三元組表示該矩陣時，所需的字節數是 66。
? 已知廣義表LS=（（a, b, c）,（d, e, f）），對其運用Head和Tail運算，取出其中原子e的運算是 Head(Tail(Head(Tail(LS))))
? 畫出廣義表（（（（a），b）），（（（）， d），（e，f）））的鏈式存儲結構圖示。
? 引入二叉線索樹的目的是 加快查找結點的前驅或后繼的速度。
? 利用二叉鏈表存儲一般樹，則根結點的右指針是 空；因為左孩子右兄弟，根節點無兄弟。
? 深度優先遍歷類似于二叉樹的 先序遍歷；廣度優先遍歷類似于二叉樹的 層次遍歷。
? 用鄰接表表示圖進行廣度優先遍歷時，通常借助 隊列 來實現算法。
用鄰接表表示圖進行深度優先遍歷時，通常借助 棧 來實現算法。
? 拓撲排序 方法可以判斷出一個有向圖是否有環。
? 圖中的一條路徑長度為k，該路徑所含的頂點數為 K+1。
? 數據的最小單位是 數據項。
? 設一個有序的單鏈表中有 n 個結點， 現要求插入一個新結點后使得單鏈表仍然保持有序， 則該操作的時間復雜度為 O(n)。
① 在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是 可以隨機訪問到任意點的簡單鏈表。
② 設一棵 m叉樹中度數為 0 的結點數為 N0，度數為 1 的結點數為 Nl，……，度數為 m的結 點數為 Nm，則 N0= l+N 2+2N3+3N4+…… +(m-1)Nm 。
③ 設有一個 n 階的下三角矩陣 A，如果按照行的順序將下三角矩陣中的元素（包括對角線 上元素）存放在 n(n+1) 個連續的存儲單元中，則 A[i][j] 與 A[0][0] 之間有 i*(i+1)/2+j -1或i*(i+1)/2+i個數據元素。
④設一條單鏈表的頭指針變量為 head且該鏈表沒有頭結點，則其判空條件是 head==0。
head為指向表頭結點的指針，分別寫出帶有頭結點的單鏈表、單項循環鏈表和雙向循環鏈表判空的條件：
單鏈表 NULL==head->next
單向循環 head==head->next
雙向循環 head==head->next&&head==head->prior
⑤ head為指向表頭結點的指針，分別寫出不帶有頭結點的單鏈表、單項循環鏈表和雙向循環鏈表判空的條件：
單鏈表 NULL==head
單向循環 head==head->next
雙向循環 head==head->next&&head==head->prior
⑥ 設F和R分別表示順序循環隊列的頭指針和尾指針，則判斷該循環隊列為空的條件為F==R。
⑦ 散列表中解決沖突的兩種方法是 開放地址法 和 鏈接法。
⑧ 設指針變量 top 指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為 top=top->next。
⑨ 設關鍵字序列為 (Kl ，K2，?， K n) ，則用篩選法建初始堆必須從第 n/2 個元素開始進行篩選。
⑩ 建立一個長度為 n 的有序單鏈表的時間復雜度為 O(n^2)。
? 設順序表的長度為 n，則順序查找的平均比較次數為 (n+1)/2。
? 設順序線性表的長度為 30，分成 5 塊，每塊 6 個元素，如果采用分塊查找，則其平均查 找長度為 6.5。
? 在堆排序中，對n個記錄建立初始堆需要調用 n/2 次調整算法。
? 已知一棵完全二叉樹中共有768結點，則該樹中共有 384 個葉子結點。
? 一個一維數組a[10]中存儲著有序表(15,26,34,39,45,56,58,63,74,76)，根據折半搜索所對應的判定樹，寫出該判定樹中度為1的結點個數，并求出在等概率情況下進行成功搜索時的平均搜索長度。度為1的結點個數：3；平均搜索長度：29/10。
? 一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為 O(1)。
解析：數組是隨機訪問的數據結構,平均時間復雜度為O(1)
? 含n個頂點的無向連通圖中至少含有 n-1 條邊。
? 順序表中,邏輯上相鄰的元素,其物理位置也相鄰,在鏈表中,邏輯上相鄰的元素,其物理位置不一定相鄰。
? 利用三元組表存放稀疏矩陣中的非零元素，則在三元組表中每個三元組元素對應一個非零元素的行號、列號和 值。
? 數據的邏輯結構是從邏輯關系上描述數據，它與數據的 存儲(或存儲結構) 無關，是獨立于計算機的。
① 區分循環隊列的滿與空，有三種方法，它們是 少用一個存儲單元、設置一個標志位 和 設置一個計數器。
② 根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成 單鏈表和雙鏈表。
③ 數據結構中評價算法的兩個重要指標是 時間復雜度 和 空間復雜度。
④ 最大容量為n的循環隊列，隊尾指針是rear，隊頭是front，則隊空的條件是 rear==front；隊滿條件是 （rear+1）%n==front；當前隊列中的元素個數為 (rear-front+n)%n。
⑤ 一個遞歸算法必須包括 終止條件和遞歸部分。
⑥ 循環隊列存儲在數組A[0…m]中，則入隊時的操作為 rear=(rear+1) mod (m+1)。
⑦ 設計一個判別表達式中左，右括號是否配對出現的算法，采用 棧 數據結構最佳。
⑧元素的移動次數與關鍵字的初始排列次序無關的是：基數排序
?元素的比較次數與初始序列無關是：選擇排序
?算法的時間復雜度與初始序列無關的是：直接選擇排序
⑨ 若一個棧以向量V[1…n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是：top=top-1; V[top]=x。
⑩ 利用帶頭結點的二叉鏈表存儲樹，則根結點的右指針是 空。二叉鏈表：左孩子右兄弟，根節點沒有兄弟，所以為空 。
? 設二叉排序樹的高度為h，則在該樹中查找關鍵字key最多需要比較 h次。
? 入棧操作和入隊列操作在鏈式存儲結構上實現時不需要考慮棧溢出的情況。正確，鏈式存儲結構是動態分配空間的。
? 用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數有關。圖的鄰接矩陣存儲所占用空間大小只與頂點個數有關，更準確地說，設頂點n個，則與n^2成正比
? 設一維數組中有n個數組元素，則讀取第i個數組元素的平均時間復雜度為 O(1)。
? 堆是完全二叉樹，完全二叉樹不一定是堆。
? 不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)。
? 設一組初始記錄關鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為 ki<=k2i && ki<=k2i+1。
? 設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數排序需要進行3趟的分配和回收才能使得初始關鍵字序列變成有序序列。
? 設有序順序表中有n個數據元素，則利用二分查找法查找數據元素X的最多比較次數不超過 log2n+1。
? 畫出廣義表LS=(( ) , (e) , (a , (b , c , d )))的頭尾鏈表存儲結構。
21 設散列表的地址范圍是[ 0…9 ]，散列函數為H（key）= （key 2 +2）MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結構。
H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6
① 二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+log2n。
② 設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列 雙向循環鏈表 存儲方式最節省運算時間。
③ 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是n次，最多2n-1次。
④循環隊列存儲在數組A[0…m]中，則入隊時的操作為 rear=(rear+1)%(m+1)。
?入隊是：rear=(rear+1)%(m+1) //m+1 代表有m+1個空間 。。它是0到m的數組
?出隊是： front =（front+1）%（m+1）
⑤ 循環隊列放在一維數組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M-1個元素。初始時為空。則 隊空：end1==end2；隊滿：end1==(end2+1)mod M
⑥ 一個棧的入棧序列為1，2，3，…，n，其出棧序列是p1，p2，p3…，pn。若p2=3，則p3可能取值的個數是 n-1；
⑦ 圖的BFS生成樹的樹高小或相等DFS生成樹的樹高。
【例題】線性 表( a1, a2,…, an)采用順序存儲結構。試問：
（1） 在等 概率 的 前提下， 平均 每 插入 一個 元素 需要 移動 的 元素 個數 為 多少？
（2） 若 元素 插在 ai 與 ai+ 1 之間（ 0 ≤ i ≤ n- 1） 的 概率 為， 則 平均 每 插入 一個 元素 所要 移動 的 元素 個數 又是 多少？
① 線性表的順序存儲結構是一種 隨機存取 的存儲結構，線性結構的鏈式存儲是一種 順序存取 的存儲結構。
② 數據結構是一門研究非數值計算的 操作對象 以及它們之間的 關系 和運算等的學科。
③ 一個數據結構在計算機 存儲器內的表示 稱為存儲結構。
④ 鏈棧和順序棧相比較，有一個較為明顯的優點是 通常不會出現棧滿的情況。
⑤ 引入循環隊列的目的是為了克服 “假溢出”現象。
⑥ 區分循環隊列的滿與空，只有兩種方法，它們是 犧牲一個存儲單元 和 設標記。
⑦ 設循環隊列存放在向量data[0…M]中，則隊頭指針front 在循環意義下的出隊操作可表示為 front=(front+1)%(M+1)，若用犧牲一個單元的辦法來區分隊滿和隊空（設隊尾指針rear），則隊滿的條件為 front==(rear+1)%(M+1)。
⑧ 對于長度為n且順序存儲的線性表，在任何位置上操作都是等概率的情況下，插入一個元素需要平均移動表中的元素個數 ；刪除一個元素平均需要移動表中元素 。
⑨ 在一個不帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置上插入或刪除其操作過程 不相同。
⑩ 在線性表的順序存儲中，元素之間的邏輯關系是通過 存儲位置 決定的；在線性表的鏈式存儲中，元素之間的邏輯關系是通過 指針 決定的。
? 單鏈表表示法的基本思想是用 指針 表示結點的邏輯關系。
? 數據的邏輯結構是指數據元素間的邏輯關系，數據的存儲結構是數據在計算機中的表示（又稱映像）方法，是數據的邏輯結構在計算機中的存儲實現。
? 數據的物理結構包括 數據元素 的表示和數據元素間關系的表示。
? 程序=數據結構+算法。
?線性表L=(a1, a2, …, an)用數組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的 (n-1)/2；
?線性表L=(a1, a2, …, an)用數組表示，假定刪除表中任一元素的概率相同，則插入一個元素平均需要移動元素的 n/2。
? 一個字符串中 任意個連續的字符組成的子序列 稱為該串的子串。
? 設T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為 模式匹配，又稱P為 模式串。
? 串是一種特殊的線性表，其特殊性表現在 其數據元素都是字符；
? 串的兩種最基本的存儲方式是 順序存儲、鏈式存儲；
? 兩個串相等的充分必要條件是 兩串的長度相等且兩串中對應位置的字符也相等。
① 若度為m的哈夫曼樹中，其葉結點個數為n，則非葉結點的個數為 [(n-1)/(m-1)]（向上取整）
② 樹的后根遍歷序列等同于該樹對應的二叉樹的 中序序列。
③ 若二叉樹采用二叉鏈表存儲結構，要交換其所有分支結點左、右子樹的位置，利用 后序 遍歷方法最合適。
④ 一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足 只有一個葉子結點。
⑤ 某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是 高度等于其結點數 的二叉樹。
⑥ 線索二叉樹是一種 物理或存儲 結構。
⑦ n個結點的線索二叉樹上含有的線索數為 n＋l（即空指針域個數）。
⑧ 中序線索樹 的遍歷仍需要棧的支持。
⑨ 設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有 n+1 個。
⑩ 個有n個結點的圖，最少有 1個連通分量，最多有 n個連通分量。
? 用有向無環圖描述表達式(A+B)*（（A+B）/A），至少需要頂點的數目為 5。
? 如果含n個頂點的圖形形成一個環，則它有 n 棵生成樹。
? 對稀疏圖最好用 克魯斯卡爾(Kruskal) 算法求最小生成樹，對稠密圖最好用 普里姆(Prim) 算法求最小生成樹。
? 判斷一個無向圖是一棵樹的條件是 n個頂點，n-1條邊的無向連通圖。
? 有向圖G的強連通分量是指 有向圖的極大強連通子圖。
? N個頂點的無向連通圖至少有N-1條邊，則鄰接矩陣中至少有2（N-1）個非零元素。
? 在AOE網中，從源點到匯點路徑上各活動時間總和最長的路徑稱為 關鍵路徑。
? AOV網中，結點表示 活動，邊表示 活動間的優先關系；AOE網中，結點表示 事件，邊表示 活動邊上的權代表活動持續時間。
? 二叉查找樹的查找效率與二叉樹的 樹型 有關, 在 呈單枝樹 時其查找效率最低，
? 堆排序是 選擇 類排序，堆排序平均執行的時間復雜度 O（nlog2n） ；需要附加的存儲空間復雜度分是O（1）
① 設一維數組中有 n 個數組元素，則讀取第 i 個數組元素的平均時間復雜度為 O（1）
② 在二叉排序樹中插入一個結點的時間復雜度為 O(n)
③ 設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是 高度等于其結點數。
總結
- 上一篇： C# 中的占位符本质
- 下一篇： Android学习按键事件监听与Comm