廣東專升本數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)

廣東專升本數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)①數(shù)據(jù)結(jié)構(gòu)(邏輯結(jié)構(gòu))其4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。②物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))其4種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)。③算法5個(gè)重要特性：有窮性、確定性、可行性、輸入和輸出。??通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：正確性、易讀性、強(qiáng)壯性和高效率。④線性表是由n≥0個(gè)數(shù)據(jù)元素組成的有限序列。其特點(diǎn)為邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰。⑤在順序表中實(shí)現(xiàn)的基本運(yùn)算：??插入：平均移動(dòng)結(jié)點(diǎn)次數(shù)為n/2；平均時(shí)間復(fù)雜度均為O（n）。??刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為（n-1）/2；平均時(shí)間復(fù)雜度均為O（n）。⑥存儲(chǔ)位置計(jì)算：每個(gè)元素需占用L個(gè)存儲(chǔ)單元第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為L(zhǎng)OC(ai)=LOC(a1)+(i-1)*L，a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。⑦線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：數(shù)據(jù)元素ai的存儲(chǔ)映像稱為結(jié)點(diǎn)，包括2個(gè)域：存數(shù)據(jù)的數(shù)據(jù)域、存后繼存儲(chǔ)位置的指針域。⑧線性鏈表(單鏈表)特點(diǎn)：每個(gè)結(jié)點(diǎn)只包含1個(gè)指針域。在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。⑨假設(shè)L是LinkList型變量，則L為單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)。??L->next為第一個(gè)結(jié)點(diǎn)地址，L->next=NULL為空表。??回收結(jié)點(diǎn)：free(q)。⑩棧：是限定僅在棧頂(表尾)進(jìn)行插入或刪除操作的線性表。表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為后進(jìn)先出的線性表。?隊(duì)列：是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而另一端刪除元素。允許插入的一端叫做隊(duì)尾，允許刪除的一端則稱為隊(duì)頭。?鏈隊(duì)列：用鏈表示的隊(duì)列。一個(gè)隊(duì)列需要頭指針和尾指針才能確定唯一。⑩棧：是限定僅在棧頂(表尾)進(jìn)行插入或刪除操作的線性表。表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為后進(jìn)先出的線性表。?隊(duì)列：是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而另一端刪除元素。允許插入的一端叫做隊(duì)尾，允許刪除的一端則稱為隊(duì)頭。?鏈隊(duì)列：用鏈表示的隊(duì)列。一個(gè)隊(duì)列需要頭指針和尾指針才能確定唯一。?循環(huán)隊(duì)列：兩個(gè)指針front指示隊(duì)列頭元素和rear指示隊(duì)列尾元素的位置。初始化建空隊(duì)列時(shí)，令front=rear=0，每當(dāng)插入新的隊(duì)列尾元素時(shí)，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時(shí)，“頭指針增1”。?串：是由零個(gè)或多個(gè)字符組成的有限序列。?數(shù)組的存儲(chǔ)位置計(jì)算：假設(shè)每個(gè)數(shù)據(jù)元素需占用L個(gè)存儲(chǔ)單元，則二維數(shù)組A中任一元素A[ij]的存儲(chǔ)位置可由下式確定：??以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)：LOC(i,j)=LOC(0,0)+(n*i+j)*L;(n為行數(shù))??以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)：LOC(i,j)=LOC(0,0)+(n*j+i)*L;(n為列數(shù))?廣義表：是線性表的推廣，在廣義表的定義中，ai可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。?二叉樹的性質(zhì)：??性質(zhì)1：在二叉樹的第K層上至多有2k-1個(gè)結(jié)點(diǎn)(K≥1)。??性質(zhì)2：深度為k的二叉樹至多2k-1個(gè)結(jié)點(diǎn)(k≥1)。??????深度為k的二叉樹至少有k個(gè)結(jié)點(diǎn)(k≥1)。??????深度為k的完全二叉樹至少有2k-1個(gè)結(jié)點(diǎn)(k≥1)。??性質(zhì)3：對(duì)任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為N0，度為2的結(jié)點(diǎn)數(shù)為N2，則N0=N2+1?？偨Y(jié)點(diǎn)個(gè)數(shù)N=N0+N1+N2。??性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。?滿二叉樹：一顆深度為k且有2的k次方減1個(gè)結(jié)點(diǎn)的二叉樹。?完全二叉樹：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。?樹轉(zhuǎn)換成二叉樹：連兄弟，留長(zhǎng)子，刪孩子。??注意：由于樹根沒(méi)有兄弟結(jié)點(diǎn)，固樹轉(zhuǎn)換為二叉樹后，二叉樹根結(jié)點(diǎn)的右子樹必為空。①森林轉(zhuǎn)換成二叉樹：連樹根及兄弟，留長(zhǎng)子，刪孩子。②二叉樹轉(zhuǎn)換成樹：連左孩子的右孩子及其右孩子…，刪原樹右孩子。③赫夫曼樹：又稱最優(yōu)樹，是一類帶權(quán)路徑長(zhǎng)度最短的樹。WPL=23+43+52+71=35④赫夫曼編碼：在赫夫曼樹上，左分支代表0，右分支代表1。由根結(jié)點(diǎn)到指定結(jié)點(diǎn)的路徑(從上到下把0、1連起來(lái))，就是該結(jié)點(diǎn)的赫夫曼編碼；如上圖(d)中a為0，b為10，c為110，d為111。⑤無(wú)向完全圖：有n(n-1)/2條邊的無(wú)向圖。?有向完全圖：有n(n-1)條邊的有向圖。⑥鄰接矩陣：無(wú)向圖的鄰接矩陣關(guān)于主對(duì)角線對(duì)稱，在整個(gè)矩陣中非零元素的個(gè)數(shù)等于邊個(gè)數(shù)的2倍，第i行和第i列中非零元素的個(gè)數(shù)等于該結(jié)點(diǎn)的度。⑦鄰接表：無(wú)向圖的鄰接矩陣關(guān)于主對(duì)角線對(duì)稱，在整個(gè)矩陣中非零元素的個(gè)數(shù)等于邊個(gè)數(shù)的2倍，第i行和第i列中非零元素的個(gè)數(shù)等于該結(jié)點(diǎn)的度。⑧深度優(yōu)先遍歷：⑨廣度優(yōu)先遍歷：⑩最小生成樹：普里姆算法（Prim）：連相鄰權(quán)值最小的?？唆斔箍査惴ǎ↘ruskal）：先連權(quán)值最小的，再依次連。?拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。?順序查找法平均查找長(zhǎng)度：ASL=(n+1)/2。?折半查找法（二分查找法）平均查找長(zhǎng)度：ASL=(n+1)/n*log2(n+1)-1?索引順序表查找法（分塊查找法）平均查找長(zhǎng)度：ASL≈log2(n/s+1)+s/2。?直接插入排序：將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。?冒泡排序：首先將一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個(gè)記錄交換之，然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字。以此類推，直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字進(jìn)行過(guò)比較為止。?快速排序：通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。①順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時(shí)，宜采用以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。②在順序棧中有“上溢”和“下溢”的現(xiàn)象，“上溢”是棧頂指針指出棧的外面是出錯(cuò)狀態(tài)，“下溢”可以表示棧為空棧，因此用來(lái)作為控制轉(zhuǎn)移的條件。③隊(duì)列是一種運(yùn)算受限的線性表，允許刪除的一端稱為隊(duì)頭（front），允許插入的一端稱為隊(duì)尾（rear），隊(duì)列的操作原則是先進(jìn)先出的，又稱作FIFO表。隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。④循環(huán)隊(duì)列：判定循環(huán)隊(duì)列是空還是滿，方法有三種：?一種是另設(shè)一個(gè)布爾變量來(lái)判斷；?第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（（rear+1）%m=front）？滿：空；?第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。⑤隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列，為了便于在表尾進(jìn)行插入（入隊(duì)）的操作，在表尾增加一個(gè)尾指針，一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢的問(wèn)題。在鏈隊(duì)列的出隊(duì)算法中，要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。⑥串是零個(gè)或多個(gè)字符組成的有限序列。?空串：是指長(zhǎng)度為零的串，也就是串中不包含任何字符（結(jié)點(diǎn)）?空白串：指串中包含一個(gè)或多個(gè)空格字符的串。⑦子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置?？沾侨我獯淖哟我獯亲陨淼淖哟?。⑧串的基本運(yùn)算有：?求串長(zhǎng)strlen（char*s）串復(fù)制strcpy（char*to，char*from）?字符定位strchr（char*s，charc）串聯(lián)接strcat（char*to，char*from）?串比較charcmp（char*s1，char*s2）⑨地址的計(jì)算方法：?按行優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（（i-1）*n+（j-1））*d?按列優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（（j-1）*n+（i-1））*d⑩圖的存儲(chǔ)結(jié)構(gòu)：?鄰接矩陣表示法：用一個(gè)n階方陣來(lái)表示圖的結(jié)構(gòu)是唯一的；無(wú)向圖中鄰接矩陣是對(duì)稱的；有向圖中行是出度，列是入度。?鄰接表表示法：用頂點(diǎn)表和鄰接表構(gòu)成不是唯一的；頂點(diǎn)表結(jié)構(gòu)vertex|firstedge，指針域存放鄰接表頭指針；鄰接表是用頭指針確定。?圖的遍歷：?深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問(wèn)結(jié)點(diǎn)。?廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊(duì)列保存已訪問(wèn)結(jié)點(diǎn)。?直接插入排序：?直接選擇排序：?冒泡排序：?快速排序：①n個(gè)結(jié)點(diǎn)的二叉樹共有2n個(gè)指針域，其中有n-1個(gè)指針域是存放了地址，有n+1個(gè)指針是空指針。②在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有e條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有2e條邊。③在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為O(log2n)，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為O(nlog2n)。④AOV網(wǎng)是一種有向無(wú)回路的圖。⑤設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有2m個(gè)空指針域。（m個(gè)葉子節(jié)點(diǎn)的哈夫曼樹總共有2m-1個(gè)節(jié)點(diǎn)）⑥設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為(R-F+M)％M。⑦快速排序的最壞時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(nlog2n)。⑧數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種情況。⑨二分查找的過(guò)程可以用一棵二叉樹來(lái)描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過(guò)二叉判定樹的高度1+log2n。⑩設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為O(n2)，快速排序的平均時(shí)間復(fù)雜度為O(nlog2n)。?設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為p>llink->rlink=p->rlink;p->rlink->llink=p->rlink（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。?設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單元，則該循環(huán)隊(duì)列中最多能夠存儲(chǔ)m-1個(gè)隊(duì)列元素；當(dāng)前實(shí)際存儲(chǔ)(R-F+M)%M個(gè)隊(duì)列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個(gè)位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。?設(shè)某無(wú)向圖G中有n個(gè)頂點(diǎn)，用鄰接矩陣A作為該圖的存儲(chǔ)結(jié)構(gòu)，則頂點(diǎn)i和頂點(diǎn)j互為鄰接點(diǎn)的條件是A[i][j]=1。?數(shù)據(jù)項(xiàng)是不可分割的構(gòu)成數(shù)據(jù)元素的最小單位；數(shù)據(jù)元素是數(shù)據(jù)的基本單位。?設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為O(n)。兩方面：一是插入時(shí)間復(fù)雜度O(1)；二是保持有序時(shí)間復(fù)雜度O(n)?設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=l+N2+2N3+3N4+……+(m-1)Nm?！咀⒔狻坑?叉樹的性質(zhì)引申出，對(duì)于任何一顆樹T，如果其終端結(jié)點(diǎn)樹為n0度為i的結(jié)點(diǎn)數(shù)為ni，則n0=1+n2+2n3+···+(i-1)ni?設(shè)有一個(gè)順序共享?xiàng)[0：n-1]，其中第一個(gè)棧項(xiàng)指針top1的初值為-1，第二個(gè)棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是top1+1=top2。?在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是可以隨機(jī)訪問(wèn)到任一個(gè)頂點(diǎn)的簡(jiǎn)單鏈表。?設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是head==0。?不帶頭結(jié)點(diǎn)是head==NULL，帶頭結(jié)點(diǎn)是head->next==NULL?設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是head->next==head。?設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是只有一個(gè)孩子節(jié)點(diǎn)(或高度等于其結(jié)點(diǎn)數(shù))。①設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為rear->next=s；rear=s。（注意：入隊(duì)要從隊(duì)尾入）②設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的新結(jié)點(diǎn)X，則進(jìn)行插入操作的語(yǔ)句序列為s->next=p->next;p->next=s（設(shè)結(jié)點(diǎn)的指針域?yàn)閚ext）。③設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為F==R④設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是p->lchild==NULL&&p->rchild==NULL。⑤散列表中解決沖突的兩種方法是開(kāi)放定址法和鏈地址法。⑥設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為top=top->next；?若指針變量top指向當(dāng)前順序棧的棧頂，則刪除棧頂元素的操作序列為top=top-1⑦設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為s->left=p；s->right=p->right；p->right=s；p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。⑧解決散列表沖突的兩種方法是開(kāi)放定址法和鏈地址法。⑨設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s->next=p->next;p->next=s。⑩設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=head->rlink和head=p->llink（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。?設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為s->left=p；s->right=p->right；p->right->left=s；p->right=s；。?設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key%p，則p最好選擇小于等于m的最大素?cái)?shù)。?設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為6.5。?設(shè)分塊查找中將長(zhǎng)為n的表分成均等的b個(gè)塊,每塊s個(gè)元素,則b=(n/s)上取整。?如果索引表中采用順序查找,則ASL=(b+1)/2+(s+1)/2;?如果索引表中采用折半查找,則ASL=(s+1)/2+log2(b+1)-1;?設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：s->next=p->next；2)p->next=s；3)t=p->data；p->data=s->data；5)s->data=t；?設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列雙向循環(huán)鏈表存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。?如果只是插入元素，單向循環(huán)列表就可以了；?如果還需要?jiǎng)h除元素，就要雙向循環(huán)列表，可以最快的找到尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。?有N個(gè)關(guān)鍵字排序，各排序最大最小情況如下：?快速排序算法的平均時(shí)間復(fù)雜度為O(nlog2n)，直接插入排序算法的平均時(shí)間復(fù)雜度為O(n^2)。?設(shè)一棵m叉樹脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其存儲(chǔ)結(jié)構(gòu)，則該樹中有n(m-1)+1個(gè)空指針域?！咀⒔狻縨叉樹n個(gè)結(jié)點(diǎn)，得出總的指針域?yàn)閙*n，不為空的指針域就等于分枝數(shù)，根結(jié)點(diǎn)沒(méi)有分支指向它，推出非空指針域?yàn)閚-1，總指針域減非空指針域就等于空的指針域即m*n-（n-1）?設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的語(yǔ)句序列為：q=p->next；p->data=q->data；p->next=q->next；feee(q)；①數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：線性結(jié)構(gòu)，樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。②設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊：則用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為O(n^2)；?用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為O(n+e)。③鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。④樹最適合用來(lái)表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。⑤在一個(gè)單鏈表中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)（若存在），則執(zhí)行p=q->next；q->next=p->next操作。⑥常對(duì)數(shù)組進(jìn)行的兩種基本操作是索引和修改。⑦在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行q->next=s;s->next=p操作。⑧設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作模式匹配。⑨一個(gè)高度為h的滿二叉樹共有n個(gè)結(jié)點(diǎn)，其中有m個(gè)葉子結(jié)點(diǎn)，則有n=2m-1成立。⑩實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷算法需要使用隊(duì)列，深度優(yōu)先搜索遍歷算法需要使用棧。?順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。?樹的先序?qū)?yīng)二叉樹的先序，樹的后序?qū)?yīng)二叉樹的中序。?在n(n>0)個(gè)元素的順序棧中刪除1個(gè)元素的時(shí)間復(fù)雜度為：O(1)。?設(shè)SQ為循環(huán)隊(duì)列，存儲(chǔ)在數(shù)組d[m]中，則SQ出隊(duì)操作對(duì)其隊(duì)頭指針front的修改是front=(front+1)%m??。?對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q[0…m-1]，隊(duì)頭、隊(duì)尾指針?lè)謩e為f、r，其判空的條件是r=f，判滿的條件是(r+1)%m=f。①設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否匹配出現(xiàn)的算法，采用棧的數(shù)據(jù)結(jié)構(gòu)最佳。②設(shè)廣義表L=((a,b,c)),則L的長(zhǎng)度為1，深度為2。③衡量查找算法效率的主要標(biāo)準(zhǔn)是平均查找長(zhǎng)度。④棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。⑤在稀疏矩陣的三元組順序表中，每個(gè)三元組表示矩陣中非零元素的行號(hào)、列號(hào)和數(shù)據(jù)值。⑥順序結(jié)構(gòu)邏輯上相鄰的結(jié)點(diǎn)物理上也是相鄰的。因此，其存儲(chǔ)密度大，存儲(chǔ)空間利用串高。⑦含有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，空指針域的個(gè)數(shù)為n+1，非空指針個(gè)數(shù)為n-1。⑧在數(shù)據(jù)結(jié)構(gòu)中，從存儲(chǔ)結(jié)構(gòu)上可以將之分為順序存儲(chǔ)和非順序存儲(chǔ)；從邏輯結(jié)構(gòu)上可以將之分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。⑨深度優(yōu)先遍歷類似二叉樹的先序遍歷；廣度優(yōu)先遍歷類似二叉樹的層次遍歷。⑩n個(gè)頂點(diǎn)的有向圖最多有n(n-1)條邊；無(wú)向圖最多有n(n-1)/2條邊。?如果要求用線性表既能較快地查找,又能適應(yīng)動(dòng)態(tài)變化的要求,則可采用分塊查找。?任意一棵二叉樹的葉子結(jié)點(diǎn)在其先序、中序和后序序列中的相對(duì)位置不發(fā)生變化。?在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn),正確的操作是s->next=p->next;p->next=s。?某算法的時(shí)間復(fù)雜度是O(n^2)，表明該算法的執(zhí)行時(shí)間與n^2成正比。?對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭向量的大小為n,占用的存儲(chǔ)空間為2e。?對(duì)于順序表，訪問(wèn)某結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，刪除某結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。?以數(shù)據(jù)集{4,5,6,7,10,12,18}為結(jié)點(diǎn)權(quán)值，畫出構(gòu)造的哈弗曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng)度。?廣義表(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?樹最適合用來(lái)表示的結(jié)構(gòu)是元素間具有分支層次關(guān)系的結(jié)構(gòu)。?圖G是一個(gè)非連通無(wú)向圖，共有28條邊，則該圖至少有9個(gè)頂點(diǎn)。①棧的特點(diǎn)是一個(gè)線性結(jié)構(gòu)，數(shù)據(jù)先進(jìn)后出，且只能在棧頂進(jìn)行增刪操作。②與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)。③數(shù)據(jù)結(jié)構(gòu)被形式定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系有限集合。④當(dāng)利用大小為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行top--語(yǔ)句修改top指針。⑤設(shè)有一個(gè)字符串S=“abcdefgh”，問(wèn)該串的最大子串個(gè)數(shù)為37。⑥若StrIndex(S,T)表示求T在S中的位置的操作，則對(duì)于S=“BeijingandNanjing”，T=“jing”，StrIndex(S,T)的結(jié)果為4。⑦字符串按存儲(chǔ)方式可以分為：順序存儲(chǔ)、鏈接存儲(chǔ)和堆分配存儲(chǔ)。⑧在C語(yǔ)言中，以字符\0表示串值的終結(jié)。⑨A[N,N]是對(duì)稱矩陣，將下三角（含對(duì)角線）以行序存儲(chǔ)到一維數(shù)組arr[N(N+1)/2]中，則對(duì)任一上三角元素arr[i,j]對(duì)應(yīng)arr[k]的下標(biāo)k是：解析如下⑩有一個(gè)100*90的稀疏矩陣，非零元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是66。?已知廣義表LS=（（a,b,c）,（d,e,f）），對(duì)其運(yùn)用Head和Tail運(yùn)算，取出其中原子e的運(yùn)算是Head(Tail(Head(Tail(LS))))?畫出廣義表（（（（a），b）），（（（），d），（e，f）））的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)圖示。?引入二叉線索樹的目的是加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度。?利用二叉鏈表存儲(chǔ)一般樹，則根結(jié)點(diǎn)的右指針是空；因?yàn)樽蠛⒆佑倚值?，根?jié)點(diǎn)無(wú)兄弟。?深度優(yōu)先遍歷類似于二叉樹的先序遍歷；廣度優(yōu)先遍歷類似于二叉樹的層次遍歷。?用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常借助隊(duì)列來(lái)實(shí)現(xiàn)算法。用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常借助棧來(lái)實(shí)現(xiàn)算法。?拓?fù)渑判蚍椒梢耘袛喑鲆粋€(gè)有向圖是否有環(huán)。?圖中的一條路徑長(zhǎng)度為k，該路徑所含的頂點(diǎn)數(shù)為K+1。?數(shù)據(jù)的最小單位是數(shù)據(jù)項(xiàng)。?設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為O(n)。①在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是可以隨機(jī)訪問(wèn)到任意點(diǎn)的簡(jiǎn)單鏈表。②設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，……，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=l+N2+2N3+3N4+……+(m-1)Nm。③設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角線上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有i*(i+1)/2+j-1或i*(i+1)/2+i個(gè)數(shù)據(jù)元素。④設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是head==0。head為指向表頭結(jié)點(diǎn)的指針，分別寫出帶有頭結(jié)點(diǎn)的單鏈表、單項(xiàng)循環(huán)鏈表和雙向循環(huán)鏈表判空的條件：?jiǎn)捂湵鞱ULL==head->next單向循環(huán)head==head->next雙向循環(huán)head==head->next&&head==head->prior⑤head為指向表頭結(jié)點(diǎn)的指針，分別寫出不帶有頭結(jié)點(diǎn)的單鏈表、單項(xiàng)循環(huán)鏈表和雙向循環(huán)鏈表判空的條件：?jiǎn)捂湵鞱ULL==head單向循環(huán)head==head->next雙向循環(huán)head==head->next&&head==head->prior⑥設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為F==R。⑦散列表中解決沖突的兩種方法是開(kāi)放地址法和鏈接法。⑧設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為top=top->next。⑨設(shè)關(guān)鍵字序列為(Kl，K2，?，Kn)，則用篩選法建初始堆必須從第n/2個(gè)元素開(kāi)始進(jìn)行篩選。⑩建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為O(n^2)。?設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為(n+1)/2。?設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為6.5。?在堆排序中，對(duì)n個(gè)記錄建立初始堆需要調(diào)用n/2次調(diào)整算法。?已知一棵完全二叉樹中共有768結(jié)點(diǎn)，則該樹中共有384個(gè)葉子結(jié)點(diǎn)。?一個(gè)一維數(shù)組a[10]中存儲(chǔ)著有序表(15,26,34,39,45,56,58,63,74,76)，根據(jù)折半搜索所對(duì)應(yīng)的判定樹，寫出該判定樹中度為1的結(jié)點(diǎn)個(gè)數(shù)，并求出在等概率情況下進(jìn)行成功搜索時(shí)的平均搜索長(zhǎng)度。度為1的結(jié)點(diǎn)個(gè)數(shù)：3；平均搜索長(zhǎng)度：29/10。?一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為O(1)。解析：數(shù)組是隨機(jī)訪問(wèn)的數(shù)據(jù)結(jié)構(gòu),平均時(shí)間復(fù)雜度為O(1)?含n個(gè)頂點(diǎn)的無(wú)向連通圖中至少含有n-1條邊。?順序表中,邏輯上相鄰的元素,其物理位置也相鄰,在鏈表中,邏輯上相鄰的元素,其物理位置不一定相鄰。?利用三元組表存放稀疏矩陣中的非零元素，則在三元組表中每個(gè)三元組元素對(duì)應(yīng)一個(gè)非零元素的行號(hào)、列號(hào)和值。?數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)(或存儲(chǔ)結(jié)構(gòu))無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。①區(qū)分循環(huán)隊(duì)列的滿與空，有三種方法，它們是少用一個(gè)存儲(chǔ)單元、設(shè)置一個(gè)標(biāo)志位和設(shè)置一個(gè)計(jì)數(shù)器。②根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成單鏈表和雙鏈表。③數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度。④最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是rear==front；隊(duì)滿條件是（rear+1）%n==front；當(dāng)前隊(duì)列中的元素個(gè)數(shù)為(rear-front+n)%n。⑤一個(gè)遞歸算法必須包括終止條件和遞歸部分。⑥循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0…m]中，則入隊(duì)時(shí)的操作為rear=(rear+1)mod(m+1)。⑦設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用棧數(shù)據(jù)結(jié)構(gòu)最佳。⑧元素的移動(dòng)次數(shù)與關(guān)鍵字的初始排列次序無(wú)關(guān)的是：基數(shù)排序?元素的比較次數(shù)與初始序列無(wú)關(guān)是：選擇排序?算法的時(shí)間復(fù)雜度與初始序列無(wú)關(guān)的是：直接選擇排序⑨若一個(gè)棧以向量V[1…n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是：top=top-1;V[top]=x。⑩利用帶頭結(jié)點(diǎn)的二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是空。二叉鏈表：左孩子右兄弟，根節(jié)點(diǎn)沒(méi)有兄弟，所以為空。?設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較h次。?入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。正確，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是動(dòng)態(tài)分配空間的。?用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)有關(guān)。圖的鄰接矩陣存儲(chǔ)所占用空間大小只與頂點(diǎn)個(gè)數(shù)有關(guān)，更準(zhǔn)確地說(shuō)，設(shè)頂點(diǎn)n個(gè)，則與n^2成正比?設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為O(1)。?堆是完全二叉樹，完全二叉樹不一定是堆。?不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。?設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對(duì)i=1，2，…，n/2而言滿足的條件為ki<=k2i&&ki<=k2i+1。?設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行3趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。?設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)log2n+1。?畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲(chǔ)結(jié)構(gòu)。21設(shè)散列表的地址范圍是[0…9]，散列函數(shù)為H（key）=（key2+2）MOD9,并采用鏈表處理沖突，請(qǐng)畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6①二分查找的過(guò)程可以用一棵二叉樹來(lái)描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時(shí)的查找長(zhǎng)度不超過(guò)二叉判定樹的高度1+log2n。②設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列雙向循環(huán)鏈表存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。③將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是n次，最多2n-1次。④循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0…m]中，則入隊(duì)時(shí)的操作為rear=(rear+1)%(m+1)。?入隊(duì)是：rear=(rear+1)%(m+1)//m+1代表有m+1個(gè)空間。。它是0到m的數(shù)組?出隊(duì)是：front=（front+1）%（m+1）⑤循環(huán)隊(duì)列放在一維數(shù)組A[0…M-1]中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M-1個(gè)元素。初始時(shí)為空。則隊(duì)空：end1==end2；隊(duì)滿：end1==(end2+1)modM⑥一個(gè)棧的入棧序列為1，2，3，…，n，其出棧序列是p1，p2，p3…，pn。若p2=3，則p3可能取值的個(gè)數(shù)是n-1；⑦圖的BFS生成樹的樹高小或相等DFS生成樹的樹高。【例題】線性表(a1,a2,…,an)采用順序存儲(chǔ)結(jié)構(gòu)。試問(wèn)：（1）在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？（2）若元素插在ai與ai+1之間（0≤i≤n-1）的概率為，則平均每插入一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？①線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線性結(jié)構(gòu)的鏈?zhǔn)酱鎯?chǔ)是一種順序存取的存儲(chǔ)結(jié)構(gòu)。②數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。③一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱為存儲(chǔ)結(jié)構(gòu)。④鏈棧和順序棧相比較，有一個(gè)較為明顯的優(yōu)點(diǎn)是通常不會(huì)出現(xiàn)棧滿的情況。⑤引入循環(huán)隊(duì)列的目的是為了克服“假溢出”現(xiàn)象。⑥區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是犧牲一個(gè)存儲(chǔ)單元和設(shè)標(biāo)記。⑦設(shè)循環(huán)隊(duì)列存放在向量data[0…M]中，則隊(duì)頭指針front在循環(huán)意義下的出隊(duì)操作可表示為front=(front+1)%(M+1)，若用犧牲一個(gè)單元的辦法來(lái)區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針rear），則隊(duì)滿的條件為front==(rear+1)%(M+1)。⑧對(duì)于長(zhǎng)度為n且順序存儲(chǔ)的線性表，在任何位置上操作都是等概率的情況下，插入一個(gè)元素需要平均移動(dòng)表中的元素個(gè)數(shù)；刪除一個(gè)元素平均需要移動(dòng)表中元素。⑨在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置上插入或刪除其操作過(guò)程不