廣東專升本數據結構知識點總結①數據結構(邏輯結構)其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時的操作序列為：s->next=p->next；2)p->next=s；3)t=p->data；p->data=s->data；5)s->data=t；?設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列雙向循環鏈表存儲方式最節省運算時間。?如果只是插入元素，單向循環列表就可以了；?如果還需要刪除元素，就要雙向循環列表，可以最快的找到尾節點的前一個節點。?有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=“BeijingandNanjing”，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+N2+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，?，Kn)，則用篩選法建初始堆必須從第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）=（key2+2）MOD9,并采用鏈表處理沖突，請畫出元素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)modM⑥一個棧的入棧序列為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且順序存儲的線性表，在任何位置上操作都是等概率的情況下，插入一個元素需要平均移動表中的元素個數；刪除一個元素平均需要移動表中元素。⑨在一個不帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置上插入或刪除其操作過程不