*)設一組初始記錄關鍵字序列(8，3，6，5，9)，以第一個記錄關鍵字8為基準進行一趟快速排序的結果為5,3,6,8,9*)用快速排序法對序列（22，5，8，20，18，10）進行升序排序，寫出每一趟的排序過程。第一趟：{10582018}22第二趟：{85}10{2018}22第三趟：58101820*)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為___選擇排序_______*)內部排序是指排序過程在內存中進行的排序。按照排序過程涉及的存儲設備的不同，排序通常可分為內部排序和外部排序。*)用簡單選擇排序法對關鍵字序列(46，90，48，30，22，78)進行升序排序，寫出每一趟的排序過程。P247答：第一趟：(22)9048304678第二趟：(2230)48904678 第三趟：(223046)904878第四趟：(22304648)9078第五趟：(2230464878)90堆是完全二叉樹，完全二叉樹不一定是堆正確直接選擇排序是一種穩定的排序方法錯誤（它是一種不穩定的排序方法）堆的形狀是一棵__完全二叉樹___________*)假設關鍵字的輸入順序為(12,2,16,30,28,10,16,20,6,18),畫出堆排序每趟排序結束后關鍵字狀態。P2702(1)題圖片*)簡述快速排序算法思想。設要排序的\t"/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/_blank"數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然后將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序*)在快速排序、堆排序、歸并排序中，____歸并排序_____排序是穩定的。快速排序在___被排序的數據完全無序___情況下最易發揮其長處。P246*)希爾排序實質上是采用_分組插入___的方法來實現的。設待排序的關鍵字序列為{12，26，40，28，30，20，6，18}，試寫出使用直接插入排序，每趟排序結束后關鍵字序列的狀態。答初始化關鍵字（12）2640283020618i=1 （1226）40283020618i=2 （122640）283020610i=3 （12262840）3020610i=4 （1226283040）20610i=5 （122026283040）610i=6 （6122026283040）10i=7 （610122026283040）*)簡述插入排序的基本思想每一趟講一個待排序的記錄，安其關鍵字的大小插入到已經排好序的一組記錄的適當位置上，直到所有待排序記錄全部插入為止。折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素52，則它將依次與表中（20703050）比較大小，查找結果是失敗。P231第7題折半查找只適用于有序表，包括有序的順序表和鏈表*）適用于折半查找的表的存儲方式及元素排列要求為順序方式存儲，元素有序*）對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（）次關鍵字。P230第5題解法：第一次（1+22）/2=11假設在左邊第二次（1+10）/2=5第三次（1+4）/2=2第四次與第1個位置上的數進行比較*)散列表的沖突處理方法，按組織形式的不同，分為___開放定址法________和____拉鏈(Chaining)法_________.*)散列表的平均查找長度取決于裝填因子。

*)創建二叉排序樹的時間復雜度為______________*)平衡二叉樹的左子樹和右子樹的深度之差的絕對值不超過1*)已知關鍵字的輸入序列為（352348824135725），畫出建立平衡排序二叉樹的過程。答：如圖所以（因為不知道我做的對錯，如果錯了和我說下）*）對有序表（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找元素42和80，則需要分別依次與哪些元素比較？答：3063428772*）若有18個元素的有序表存放在一維數組A[18]中，第一個元素放A[1]中，現進行折半查找，則查找A［3］的比較序列的下標依次為答：這個題有一點點問題，應該是A[19]才對答案為：9423在一棵空的二叉排序樹中依次插入關鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉排序樹。答：如圖所示：*）長度20的有序表進行折半查找，則對應的判定樹高度為答：5次*）對一個有序表：(13，18，24，35，47，50，62)進行折半查找，畫出折半查找過程的判定樹，并給出查找元素24時，需要依次與哪些元素比較？答：如圖所示*)從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為插入排序*)由3個結點可以構造出（5）種不同的二叉樹*)一個具有1025個結點的二叉樹的高h為11至1025之間注：折半折半的計算算出最小的來*)設F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結點，則B中右指針域為空的結點有（n+1）個。*）利用二叉鏈表存儲樹，則根結點的右指針是（A）。A．空 B．非空C．指向最左孩子 D．指向最右孩子注意：二叉鏈表：

左孩子右兄弟根節點沒有兄弟，所以為空 *)用鄰接表表示圖進行廣度優先遍歷時，通常借助（B）來實現算法。A．棧 B.隊列 C.樹 D．圖廣搜都是隊列

鄰接表是鏈表*)在下列存儲形式中，（D）不是樹的存儲形式？A．雙親表示法 B．孩子鏈表表示法C．孩子兄弟表示法 D．順序存儲表示法*)二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點的個數11二叉樹有如下性質

N0=N2+1，葉子節點個數等于度為2的節點個數+1

*)深度為h的滿m叉樹的第k層有（B）個結點。(1=<k=<h)mk-1 B．mk-1 C．mh-1 D．mh-1*)n（n≥2）個權值均不相同的字符構成哈夫曼樹，以下關于該樹的敘述中，錯誤的是（A）。A．該樹一定是一棵完全二叉樹B．樹中一定沒有度為1的結點C．樹中兩個權值最小的結點一定是兄弟結點D．樹中任一非葉結點的權值一定不小于下一層任一結點的權值*）拓撲排序算法能判斷有向圖中存在環*)一棵完全二叉樹上有1001個結點，則該二叉樹中度為1的結點個數是1，葉子結點的個數是500，二叉樹的高度是10。答：該樹有：2^9+489=1001同所以該樹高度為10其中10層的489個節點度為0同時這489個節點使得第9層有244度為21個度為1第9層共有2^（9-1）個節點256個節點所以第9層度為葉子節點有11個加上第10層的489個一共有500個葉子節點*)某二叉樹結點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結點數目為4個提示：根據中序后序畫出二叉樹*)設哈夫曼樹中有199個結點，則該哈夫曼樹中有（100）個葉子結點提示：在哈夫曼樹中，葉子節點總比內節點多一個，沒有度為1的節點所以設度為0的為a度為2的為ba=b+1n=a+b所以n=2*a-1b=100*)在一個圖中，所有頂點的度數之和等于圖的邊數的（2）倍*)具有n個頂點的有向圖最多有（n(n-1)）條邊。完全有向圖*)若從無向圖的任意一個頂點出發進行一次深度優先搜索可以訪問圖中所有的頂點，則該圖一定是（連通圖）圖*)已知圖的鄰接表如右圖所示，則從頂點v0出發的按照深度優先遍歷的結果是（）*）Kruskal算法適合構造一個稀疏圖G的最小生成樹，Prim算法適合構造一個稠密圖G的最小生成樹*)有很少條邊或弧的圖稱為稀疏圖,反之稱為稠密圖對*)p1882（1）鄰接矩陣和鄰接表*)簡述迪杰斯特拉算法思想。*)簡述圖的廣度優先搜索算法思想。廣度優先搜索是一種圖的搜索算法。在搜索開始，會確定一個搜索的起點，然后選擇一個與其相鄰的且在值上與節點最接近的點，然后迭代進行，如果在最后發現所有鄰居都已經被訪問過，則開始回溯*)簡述克魯斯卡爾算法思想。答：考慮問題的出發點:為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小。

具體做法:先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。*)度為2的有序樹是二叉樹錯*)存在這樣的二叉樹，其任何次序的遍歷結果都相同對*)圖的廣度優先搜索樹是惟一的。錯*)圖的深度優先遍歷類似于二叉樹的__前序遍歷_______*)G是一個非連通無向圖，共有28條邊，則該圖至少有（9）個頂點注：將28條邊全部連接起來的最小頂點數為8，因為非連通，再加一個頂點得答案9*)存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數有關，而且與圖的邊數也有關。 錯*)完全二叉樹某結點有右子樹，則必然有左子樹。 對 *)圖的深度優先序列和廣度優先序列不是惟一的。 對 *)鄰接表只能用于存儲有向圖。 錯 *)從源點到終點的最短路徑是唯一的。對 *)強連通圖的各頂點間均可達。對*)完全二叉樹某結點有右子樹，則必然有左子樹。 對 *)稀疏矩陣壓縮存儲后，必會失去隨機存取功能。 對 *)圖的廣度優先搜索樹是惟一的。錯 *)圖的生成樹是惟一的。 錯 *)無向圖的連通分量是其極小連通子圖。 錯*)二叉樹中每個結點的兩棵子樹的高度差等于1。 錯 *)具有12個結點的完全二叉樹有5個度為2的結點。 對 *)哈夫曼樹中沒有度數為1的結點。 對 *)中序遍歷一棵二叉排序樹可以得到一個有序的序列。 對*)二叉樹的先序、中序、后序遍歷*)在用二叉鏈表存儲一棵二叉樹時，n個結點的二叉樹共有___2n_____個指針域，其中有____n-1____個指針域是存放了地址，有_____n+1__個指針是空指針。*)圖有鄰接矩陣、鄰接表等存儲結構，遍歷圖有深度優先遍歷、廣度優先遍歷等方法。*)在無向圖G的鄰接矩陣A中，A[i][j]=1，則A[j][i]=1*)一棵完全二叉樹有128個結點，則該完全二叉樹的深度為8，葉子結點的個數為___64_____。*)一棵完全二叉樹上有500個結點，則該二叉樹中度為1的結點個數是1，葉子結點的個數是250，二叉樹的高度是9。*)遍歷圖的基本方法有廣度優先遍歷和深度優先遍歷兩種，其中可以借助棧實現的是深度優先遍歷，可以借助隊列實現的是廣度優先遍歷。*)具有10個頂點的無向圖，邊的總數最多為____45____。注：n(n-1)/2*)二叉樹的后序遍歷是CBEDA，中序序列是BCADE，則該二叉樹的樹根是A，根結點的左孩子是B，右孩子是D，二叉樹的先序序列為ABCDE。*)一棵完全二叉樹的順序存儲結構中存儲數據元素為ABCDEF，則該二叉樹的先序遍歷序列為__ABDECF_________，中序遍歷序列為__DBEAFC________，后序遍歷序列為___DEBFCA________。*)樹結構中根節點___沒有_____雙親結點，其余每個結點都有1個雙親結點；葉子結點沒有孩子結點，其余每個結點都有至少1個孩子結點。*)在一個圖中，所有頂點的度數之和等于所有邊數的__2____倍。*)度為2的樹與二叉樹有何區別？答：度為2的樹是不區分左右子樹的，而二叉樹左子樹與右子樹是不一樣的度為2的樹是不包含空樹，而二叉樹是可以有空樹的總結：二叉樹定義要比度為2的樹嚴格*)簡述連通圖的生成樹的定義答：連通圖G(V,E),當從圖的任意一頂點出發，將邊集E(G)分成T（G）和B（G），其中T（G）是遍歷圖時所經歷過的邊的集合，B（G）是遍歷圖未經過邊的集合，即，G1（V,T）就是G的極小聯通子圖，所以G1就是連通圖G的生成樹。*)一份電文中有6種字符：A,B,C,D,E,F，它們的出現頻率依次為6，5，9，13，30，1，畫出對應的哈夫曼樹（要求每個結點左孩子的頻率不高于右孩子的頻率）；計算其帶權路徑長度WPL解：WPL=1*5+5*5+6*4+9*3+13*2+30*1=137*)已知如圖所示的無向網，請畫出它的最小生成樹(兩個算法都要掌握)。答：普里姆算法克魯斯卡爾算法*)假設一棵二叉樹的先序序列：ABDFCEGH，中序序列：BFDAGEHC，畫出這棵二叉樹，求這棵二叉樹的后序序列。答：后序遍歷為：FDBGHECA*)已知如圖所示的有向圖，請給出：每個頂點的入度和出度、鄰接矩陣和鄰接表。ID：入度OD：出度ID(1)=3OD（1）=0（1）ID(2)=2OD（2）=1（1）ID(3)=1OD（3）=2（1）ID(4)=1OD（4）=3（1）ID(5)=2OD（5）=1ID(6)=2OD（6）=3*)P17(1)(2),(3)(4)(5)(6)*)邏輯結構的四種基本關系。*)數據結構主要包括哪三方面內容數據的邏輯結構、數據的存儲結構、數據的運算.*)邏輯結構與存儲結構的關系。邏輯結構反映數據元素之間的邏輯關系，而存儲結構是數據結構在計算機中的表示，它包括數據元素的表示及其關系的表示。一種邏輯結構可以采用一種或幾種存儲方式來表達數據元素之間的邏輯關系，相應的存儲結構稱為給定邏輯結構的存儲實現或存儲映像。*)線性結構與非線性結構的不同點。線性結構是最簡單最常用的一種數據結構,線性結構的特點是結構中的元素之間滿足線性關系,按這個關系可以把所有元素排成一個線性序列.線性表,串,棧和隊列都屬于線性結構.

而非線性結構是指在該類結構中至少存在一個數據元素,它具有兩個或者兩個以上的前驅或后繼.如樹和二叉樹等.*)評估算法的優劣，通常從時間復雜度和空間復雜度兩個方面考察。*)數據的邏輯結構分兩大類：邏輯結構和__儲存____結構，數據的存儲方法主要有兩種：順序存儲方法和鏈式存儲方法。*)程序段“i=1;while(i<=n)i=i*3;”的時間復雜度為。解析：假設循環次數是x。

i=1,3,9,27,i=3^x

條件是i<=n

3^x<=n

所以x<=log3n一共執行循環體log3n次，所以時間復雜度是O(log3n)*)線性結構中元素之間是一對一關系，樹結構中元素之間是一對多關系，圖結構中元素之間是多對多關系。*)線性表的邏輯結構是線性結構，其元素的個數稱為線性表的長度。*)p51(1)(2)(3)(5)(6)(7)(9)(11)(13)*)存儲密度*)非空的循環單鏈表head的尾結點p滿足（A）。A．p->next==head B.p->next==NULL C.p==NULL D.p==headP83(1)(2)(3)(10)(12)(14)(15)P108(1)(5)(6)(7)(8)(11)(12)(14)(15)判斷題：*)數據的邏輯結構是依賴于計算機的。錯*)順序存儲方式只能用于存儲線性結構。錯*)單鏈表不是一種隨機存儲結構對*)循環鏈表不是線性表。錯*)數組元素的下標值越大，存取時間越長。 錯 *)線性表中的所有元素都有一個前驅元素和后繼元素。錯*)一個遞歸算法必須包括終止條件和迭代部分。 錯是遞歸部分 *)稀疏矩陣壓縮存儲后，必會失去隨機存取功能。 對*)空串就是空格串。 錯 空串是"";空白串是null

*)廣義表的元素可以是單原子也可以是子表。對*)棧和隊列都是受限的線性結構。 對 *)以鏈表作為棧的存儲結構，出棧必須判別棧空的情況。對*）循環鏈表不是線性表。錯1.數據結構包括數據的邏輯結構、數據的存儲結構和數據的運算這三個方面的內容。2.在具有n個元素的循環隊列中，隊滿時具有n-1個元素。3.在棧結構中，允許插入、刪除的一端稱為棧頂，另一端稱為棧底。*)當有多個函數構成嵌套調用時，按照____后調用先返回________的原則，上述函數之間的信息傳遞和控制轉移必須通過_____棧_____來實現。4.廣義表(a，(b)，((c，(d))))的長度是2，深度是3，表頭是a，表尾是(b)，((c，(d)))。5.設二維數組A的內存首地址為M，其行下標i=0,1,…,8,列下標j=1,2,…,10。若A按行先存儲，則元素A[8,5]的地址為M+84；當A按列先存儲時，該地址存放的的元素是A[8][5]。設每個字符占一個字節。若其首地址是S，每個元素占k個字節，則數組元素A[i][j]的地址P是p=S+(i*n+j)*kP=M+(8*10+4)*11.評估算法的優劣，通常從時間復雜度和空間復雜度兩個方面考察。2.數據的邏輯結構分兩大類：___線性__結構和_非線性_結構，數據的存儲方法主要有兩種：順序存儲方法和鏈式存儲方法。3.用一個大小為6的數組來實現循環隊列時，如果當前front和rear的值分別為3和0，則從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為4和2。解析：當出隊列中刪除一個元素，也就是出隊，即front+1:=4再插入兩個元素，即rear+2=22.線性結構中元素之間是一對一關系，樹結構中元素之間是一對多關系，圖結構中元素之間是多對多關系。3.具有n個元素的循環隊列中，隊滿時有n-1個元素。4.假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結點數為__9_____個，樹的深度為3，樹的度為___8____。1.數據結構包括數據的邏輯結構、數據的存儲結構和數據的運算這三個方面的內容。2.線性結構中元素之間是一對一關系，樹結構中元素之間是一對多關系，圖結構中元素之間是多對多關系。3.用容量為6的數組來實現循環隊列時，如果當前front和rear的值分別為4和1，則從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為和5,6。*)在具有n個元素的循環隊列中，隊滿時具有n-1個元素。*)在棧結構中，允許插入、刪除的一端稱為棧頂，另一端稱為棧底。*)已知循環隊列的存儲空間大小為20，且當前隊列的頭指針和尾指針的值分別為8和3，則該隊列的當前的長度為__15_____；插入2個元素又刪除5個元素后頭指針變為10，尾指針變為8，隊列長度變為18。長度計算：（20-8）+（3-0）=15*)簡述隊列和棧的相同點和不同點。棧和隊列都是線性表，都是限制了插入刪除點的線性表（或者說是控制了訪問點的線性表）共同點：都是只能在線性表的端點插入和刪除 不同點棧的插入和刪除都在線性表的同一個端點，該點通稱棧頂，相應地，不能插入刪除的另一個端點通稱棧底，其特性是后進先出隊列在線性表的表頭插入，表尾刪除，表頭一般稱隊頭，表尾一般稱隊尾，其特性是先進先出

相同之處：n個（同類）數據元素的有限序列稱為線性表。線性表的特點是數據元素之間存在“一對一”的關系，棧和隊列都是操作受限制的線性表，他們和線性表一樣，數據元素之間都存在“一對一”的關系不同之處：棧只允許在一段進行插入或刪除操作的線性表，其最大的特點是“后進后出”；對列是只允許在一端進行插入，另一端進行刪除操作的線性表，其最大的特點是“先進后出”。*)簡述數據結構主要研究的對象和研究的問題數據的邏輯結構，即數據關系之間的邏輯關系；數據的存儲結構，即數據的邏輯結構在計算機中的表示；操作算法，即插入、刪除、修改、查詢、排序等。*)假定有三個元素A、B、C、D依次進棧，進棧過程中允許出棧，試寫出所有元素C先出棧的出棧序列。ABDC，BADC*)簡述以下三個概念的區別：頭指針，頭結點，首元結點。頭結點：是為了方便操作鏈表而附設的,頭結點數據域通常用來保存跟鏈表有關的信息,比如鏈表的長度；

首元結點：就是鏈表里“正式”的第一個結點,即鏈表的開始結點。

頭指針：頭指針是指向鏈表的基地址。如果鏈表存在頭結點則頭指針就是指向頭結點的地址,反之指向首元結點的地址。*)順序表與鏈表各自的優缺點是什么？順序表存儲：

優點：（1）空間利用率高。（局部性原理，連續存放，命中率高）

（2）存取速度高效，通過下標來直接存儲。缺點：（1）插入和刪除比較慢，比如：插入或者刪除一個元素時，整個表需要遍歷移動元素來重新排一次順序。

（2）不可以增長長度，有空間限制,當需要存取的元素個數可能多于順序表的元素個數時,會出現"溢出"問題.當元素個數遠少于預先分配的空間時,空間浪費巨大。鏈表存儲：優點：（1）存取某個元素速度慢。

（2）插入和刪除速度快，保留原有的物理順序，比如：插入或者刪除一個元素時，只需要改變指針指向即可。

（3）沒有空間限制,存儲元素的個數無上限,基本只與內存空間大小有關.

缺點：（1）占用額外的空間以存儲指針(浪費空間，不連續存放，malloc開辟，空間碎片多)

（2）查找速度慢，因為查找時，需要循環鏈表訪問，需要從開始節點一個一個節點去查找元素訪問。

*)棧、隊列和線性表的區別是什么？棧和隊列都是線性表，并且都是特殊的線性表：特殊在于限制了插入和刪除點棧是在線性表的某固定一端插入和刪除，因此特性為后進先出隊列是在線性表的一端插入，另外一端刪除，因此特性為先進先出*)請將banana用工具H()—Head()，T()—Tail()從L中取出。其中，L=(apple,(orange,(strawberry,(banana)),peach),pear)。H（H（T（H（T（H（T（L）））））））根據廣義表的定義來取值程序設計題主要考鏈表，包括鏈表的查詢，插入，刪除，循環鏈表的合并#include"stdafx.h"#include<stdio.h>#include<iostream.h>typedefintElemType;typedefstructLNode{ ElemTypedata; structLNode*next;}LNode,*LinkList;//鏈表的初始化intInitList(LinkList&L){L=newLNode;L->next=NULL;return1;}//創建一個單鏈表voidCreateList_H(LinkList&L,intn){ inti; LinkListp;L=newLNode; L->next=NULL; for(i=0;i<n;i++){ p=newLNode;// scanf("%d",&p->data); cin>>p->data; p->next=L->next; L->next=p; }}//根據下標查找數據intGetElem(LinkList&L,inti,ElemType&e){LinkListp;p=L->next;intj=1;while(p&&j<i){p=p->next;