數(shù)據(jù)結(jié)構(gòu) 填空題

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題庫(kù)之二：填空題若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新的數(shù)據(jù)元素前，需要先依次移動(dòng) 個(gè)數(shù)據(jù)元素。在非空雙向循環(huán)鏈表中由q所指的那個(gè)鏈結(jié)點(diǎn)后插入一個(gè)由p指的鏈結(jié)點(diǎn)的動(dòng)作對(duì)應(yīng)的語(yǔ)句依 次為：p-prior=q; p-next=q-next; q-next=p;。（空白處為一條賦值語(yǔ)句）已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的地 址為 LOC（a1），那么，LOC（ai）=。 具有2000個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為。 具有n0個(gè)葉結(jié)點(diǎn)的哈夫曼樹（Huffman）的分支總數(shù)為。 若連通圖的頂點(diǎn)個(gè)數(shù)為n，則該圖的生成樹的邊數(shù)為。在

2、序列（2，5，8，11，15，16，22，24，27，35, 40）中采用折半查找（二分查找）方法查找元素24,需要進(jìn)行 次元素之間的比較。 索引文件中的索引表是提供的，并且索引表的表項(xiàng)按有序列排列。 對(duì)具有n個(gè)元素的任意序列采用插入排序法進(jìn)行排序，整個(gè)排序過(guò)程中要進(jìn)行次元 素之間的比較。 插入排序法、選擇排序法、拓?fù)渑判蚍ㄅc歸并排序法中，不是內(nèi)排序方法。在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的倍。 圖的深度優(yōu)先搜索方法類似于二叉樹的遍歷。數(shù)據(jù)文件最重要的操作除了插入、刪除、修改和查找外，還 。將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個(gè)一維數(shù)組中，然后采

3、用折半查找方法查找元素12,被比較過(guò)的數(shù)組元素的下標(biāo)依次為。在索引表，若一個(gè)索引項(xiàng)對(duì)應(yīng)基本數(shù)據(jù)中一條記錄，則稱此索引為稠密索引；若索引表中一個(gè)索引對(duì)應(yīng)基本數(shù)據(jù)中的若干記錄，則稱此索引為索引。每趟排序從未排序的子序列中依次取出元素與已經(jīng)排好序的序列中元素進(jìn)行比較，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱為 排序法。從未排序序列中選擇一個(gè)元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一 部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。這種排序法稱為 排序法。希爾排序法、快速排序法、堆積排序法和二路歸并排序法四種排序法

4、中，要求輔助空間最多 TOC o 1-5 h z 的是。對(duì)序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個(gè)元素為基準(zhǔn)元素得到的劃分結(jié)果是。數(shù)據(jù)結(jié)構(gòu)課程討論的主要內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和。若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用存儲(chǔ)結(jié)構(gòu)。若鏈結(jié)點(diǎn)的構(gòu)造為datalnext，那么，判斷由list所指的單向循環(huán)鏈表中只有一個(gè)結(jié)點(diǎn)的條件是 求串T在主串S中首次出現(xiàn)的位置的操作是。完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個(gè)名詞術(shù)語(yǔ)中，與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)系的是。一個(gè)無(wú)向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣一定是一 。在序列(2,5,8,

5、11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要進(jìn)行次元素之間的比較。若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為H(key)=key MOD 9,與18發(fā)生沖突的元素有個(gè)。每一趟排序時(shí)從排好序的元素中挑出一個(gè)值最小的元素與這些未排小序的元素的第一個(gè)元素交換位置，這種排序方法成為排序法。排序過(guò)程中所進(jìn)行的元素之間的比較次數(shù)與參加排序的序列的初始狀態(tài)無(wú)關(guān)的排序方法是 排序法。若堆棧采用順序存儲(chǔ)結(jié)構(gòu)，在不產(chǎn)生溢出的時(shí)候往堆棧中插入一個(gè)新元素，首先，然后再。在一棵二叉樹中有n0個(gè)葉結(jié)點(diǎn)，有n2個(gè)度為2的結(jié)點(diǎn)，則n0=。 索引文

6、件包括 和 兩部分，而且是按照關(guān)鍵字值有序排列的。對(duì)具有n個(gè)元素的序列采用插入排序法和選擇排序法，排序趟數(shù)均為，而采用泡排序 法進(jìn)行排序，排序趟數(shù)是一個(gè)范圍。一般情況下，將一個(gè)遞歸算法變換成等價(jià)的非遞歸算法主要設(shè) 機(jī)制。循環(huán)單鏈表與循環(huán)非循環(huán)單鏈表的主要不同是。若具有n個(gè)結(jié)點(diǎn)的非空二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，該鏈表一共有個(gè)指針域，其中個(gè)指針域存放非空指針，有個(gè)指針域存放空指針(nil)。 具有n個(gè)頂點(diǎn)的無(wú)向圖的邊數(shù)最多為，具有n個(gè)頂點(diǎn)的有向圖的邊數(shù)最多為在散列文件(Hash文件)中，處理沖突的方法通常有、 三種。 數(shù)據(jù)結(jié)構(gòu)課程研究的主要內(nèi)容包括、三方面。 在長(zhǎng)度為n的線性表A的第i個(gè)位置插入一

7、個(gè)新元素的過(guò)程應(yīng)該首先， 然后，最后。(1WnWn+1)若具有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表結(jié)構(gòu)，則該鏈表中共有個(gè)指針域，其中個(gè)指針域用于鏈接孩子結(jié)點(diǎn)，個(gè)指針域存放nil。 TOC o 1-5 h z 對(duì)具有n個(gè)元素的序列采用堆積排序法進(jìn)行排序，排序趟數(shù)為?？焖倥判蛟谄骄闆r下的空間復(fù)雜度為。 若一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為。 具有n個(gè)結(jié)點(diǎn)的非空二叉排序樹的最小深度為。 深度為h且有個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點(diǎn)處在第1層)。二叉樹的前序遍歷序列為A，B，C，E，F(xiàn)，D，G，H，中序遍歷序列為A，E，C，F(xiàn)，B， G， D， H，其后序遍歷序列為。已知序列(

8、34, 76, 45，18, 26, 54, 92, 65,)，按照逐點(diǎn)插入法建立一棵二叉排序列樹，該樹的深度是。一個(gè)不帶有權(quán)的有向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣是一 。帶權(quán)連通圖 G=(V,E)，其中 V=v1,v2,v3,v4,v5,E=(v1,v2)7,(v1,v4)6, (v1,v4)9, (v2,v3)8, (v2,v4)4, (v2,v5)4, (v3,v4)6, (v4,v5)2,(注：頂點(diǎn)偶對(duì)右下角的數(shù)據(jù)為邊上的權(quán)值)，G的最小 生成樹的權(quán)值之和為。在線性表中采用折半查找法(二分查找法)查找一個(gè)數(shù)據(jù)元素，線性表中元素應(yīng)該按值有序，并且采用存儲(chǔ)方法。52.若對(duì)序列(49, 3

9、8, 65, 97, 76, 13, 27, 50)采用選擇排序法排序，則第三趟結(jié)束后序列的狀 態(tài)是。設(shè)某非空單鏈表，其結(jié)點(diǎn)形式為datalnext,若要?jiǎng)h除指針q所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，則需 執(zhí)行下列語(yǔ)句序列：p=q-next; delete p; 隊(duì)列可以看成是一種運(yùn)算受限制的線性表，也稱為 線性表。在非空樹上，沒(méi)有直接前趨。 設(shè)有33個(gè)值，用它們組成一棵哈夫曼樹，則該哈夫曼樹中共有個(gè)結(jié)點(diǎn)。 無(wú)向圖中的連通分量定義為無(wú)向圖的。在開散列表上查找鍵值等于K的結(jié)點(diǎn)，首先必須計(jì)算該鍵值的，然后再通過(guò)指針查找該結(jié)點(diǎn)。對(duì)靜態(tài)表順序查找算法采用設(shè)置崗哨方式與普通的設(shè)置循環(huán)控制變量相比，進(jìn)行一次查找所 花

10、費(fèi)的平均時(shí)間大約減少。若要對(duì)某二叉排序樹進(jìn)行遍歷，保證輸出的所有結(jié)點(diǎn)鍵值序列按遞增次序排列，應(yīng)對(duì)該二叉樹采用 遍歷法。文件的基本存取單位是。設(shè)需將一組數(shù)據(jù)按升序排序。在無(wú)序區(qū)中依次比較相鄰兩個(gè)元素ai和ai+1的值，若ai的值 大于ai+1的值，則交換ai和ai+1。如此反復(fù)，直到某一趟中沒(méi)有記錄需要交換為止，該排序方 法被稱為。在插入排序、快速排列、堆排序、歸并排序中，排序方法不穩(wěn)定的 。 抽象數(shù)據(jù)類型的特點(diǎn)是將和封裝在一起，從而現(xiàn)實(shí)信息隱藏。 從順序表中刪除一個(gè)元素時(shí)，表中所有在被刪元素之后的元素均需一個(gè)位置。 在隊(duì)列中，允許進(jìn)行插入操作的一端稱為，允許進(jìn)行刪除操作的一端稱為。 設(shè) S1=

11、good”,S2= ,S3=book”，則 S1, S2 和 S3 依次聯(lián)接后的結(jié)果是。已知在一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，則該樹中含 有的葉子結(jié)點(diǎn)的數(shù)目為。每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做排序。如果在排序前，關(guān)鍵字序列已接近正序或逆序，則在堆排序和快速排序兩者之中，選用 較為適當(dāng)。假設(shè)哈希表的表長(zhǎng)為m，哈希函數(shù)為H(key)，若用線性探查法解決沖突，則探查地址序列的 形式表達(dá)為。用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是 TOC o 1-5 h z 和；若只設(shè)尾指針，則出

12、隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是和。深度為h的完全二叉樹至少有 個(gè)結(jié)點(diǎn)；至多有 個(gè)結(jié)點(diǎn)；h和結(jié)點(diǎn)總數(shù)n之間的關(guān)系是。 在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù) 。n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣至少有個(gè)非零元素。 假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a,b,c,d,e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為。 串 S= I am a worker”的長(zhǎng)度是。假設(shè)一個(gè)10階的下三角矩陣A按列優(yōu)順序壓縮存儲(chǔ)在一維數(shù)組C中，則C數(shù)組的大小應(yīng)為在n個(gè)結(jié)點(diǎn)的線索二叉鏈表中，有個(gè)線索指針。若采用鄰接矩陣結(jié)構(gòu)存儲(chǔ)具有n個(gè)頂點(diǎn)的圖，則對(duì)該圖進(jìn)行廣度優(yōu)先遍歷的算法時(shí)間

13、復(fù)雜度 為。對(duì)關(guān)鍵字序列(52，80，63，44，48，91)進(jìn)行一趟快速排序之后得到的結(jié)果為由10000個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹，在等概率查找的假設(shè)下，查找成功時(shí)的平均查找長(zhǎng)度的 最大值可能達(dá)到。 TOC o 1-5 h z 在線性表的單鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)口 域，另一個(gè)叫 域。 對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度 ，在 表尾插入元素的時(shí)間復(fù)雜度為。 對(duì)于一個(gè)長(zhǎng)度為n的單鏈接存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為，在表尾插入元素的時(shí)間復(fù)雜度為。在線性表的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i,則它的前驅(qū)元素的下標(biāo)為，后繼元素的下標(biāo)為。87 .在線

14、性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為，若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為。88、 在循環(huán)單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針指向 結(jié)點(diǎn)。89、 在雙向鏈表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)指針域，一個(gè)指向其 結(jié)點(diǎn)，另一個(gè)指向其 結(jié)點(diǎn)。90、 在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右指針域指向 結(jié)點(diǎn)。91、若對(duì)長(zhǎng)度n=10000的線性表進(jìn)行二級(jí)索引存儲(chǔ)，每級(jí)索引表中的索引項(xiàng)是下一級(jí)20個(gè)表項(xiàng)的索引，則一級(jí)索引表的長(zhǎng)度為。92、 在程序運(yùn)行過(guò)程中不能擴(kuò)充的數(shù)組是分配的數(shù)組。這種數(shù)組在聲明它時(shí)必須指 定它的大小。93、將一個(gè)n階三對(duì)角矩陣A的三條對(duì)角線

15、上的元素按行壓縮存放于一個(gè)一維數(shù)組B中，A00 存放于B0中。對(duì)于任意給定數(shù)組元素A I J ，如果它能夠在數(shù)組B中找到，則它應(yīng)在 位置。94、 隊(duì)列的插入操作在 進(jìn)行，刪除操作在進(jìn)行。95、設(shè)有一個(gè)順序棧S，元素S1，S2, S3, S4，S5, S6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)镾2，S3，S4，S6，S5，S1，則順序棧的容量至少應(yīng)為。96、 通常程序在調(diào)用另一個(gè)程序時(shí)，都需要使用一個(gè) 來(lái)保存被調(diào)用程序內(nèi)分配的 局部變量、形式參數(shù)的存儲(chǔ)空間以及返回地址。97、 在一棵樹中，結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。98、一棵樹的廣義表表示為a （b （c，d （e，f），g （h），I （j，k （x，y）

16、，結(jié)點(diǎn)k的所有祖先的結(jié)點(diǎn)數(shù)為 個(gè)。99、根據(jù)一組記錄（56, 42, 50，64, 48）依次插入結(jié)點(diǎn)生成一棵AVL樹（高度平衡的二叉搜索樹）時(shí)，當(dāng)插入到值為 的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。100、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為和。101、在一個(gè)稀疏矩陣中，每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的 、和 三項(xiàng)。在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按 為主序、為輔序的次序排列。 隊(duì)列的插入操作在進(jìn)行，刪除操作在進(jìn)行。 棧又稱為表，隊(duì)列又稱為表。 在一個(gè)循環(huán)順序隊(duì)列Q中，判斷隊(duì)空的條件為，判斷隊(duì)滿的條件為 在一個(gè)順序棧中，若棧頂指針等于，則為空

17、棧；若棧頂指針等于， 則為滿棧。在一個(gè)鏈棧中，若棧頂指針等于NULL，則為；在一個(gè)鏈隊(duì)中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為或該隊(duì)列為。 向一個(gè)鏈棧插入一個(gè)新結(jié)點(diǎn)時(shí)，首先把棧頂指針的值賦給，然后把新結(jié)點(diǎn)的 存儲(chǔ)位置賦給。假定front和rear分別為一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針，則該鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件為 。中綴算術(shù)表達(dá)式3+4/(25-(6+15)*8所對(duì)應(yīng)的后綴算術(shù)表達(dá)式為。后綴算術(shù)表達(dá)式24 8 + 3 * 4 10 7 - * /所對(duì)應(yīng)的中綴算術(shù)表達(dá)式為，其值 為。 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為。 一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為個(gè)。在一棵二叉樹中，

18、假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為 個(gè)。 對(duì)于一棵二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為i，則它的左孩子結(jié)點(diǎn)的編號(hào)為，右孩 子結(jié)點(diǎn)的編號(hào)為，雙親結(jié)點(diǎn)的編號(hào)為。 在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為。 假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18,則它的最小深度為，最大深度為。假定一棵二叉樹順序存儲(chǔ)在一維數(shù)組a中，則ai元素的左孩子元素為，右孩 子元素為，雙親元素(i1)為。 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)應(yīng)二叉鏈表中指針總數(shù)為 個(gè)，其中 個(gè)用于指向孩子結(jié)點(diǎn)，個(gè)指針空閑著。在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定該結(jié)點(diǎn)的值。 對(duì)一棵二叉搜索樹

19、進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一 。從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 查找，若元素的大于根結(jié)點(diǎn)的值，則繼續(xù)向查找。 在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)為，右 孩子元素的下標(biāo)為。在一個(gè)小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中白，在一個(gè)大根堆中，堆頂結(jié)點(diǎn) 的值是所有結(jié)點(diǎn)中的。 當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí)，需要把 素填補(bǔ)到 位置，然后再按條件把它逐層調(diào)整。 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的倍。 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有 條邊。

20、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有頂點(diǎn)則至少需要條邊。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別為 和 條。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，當(dāng)分別采用鄰接矩陣、鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度依次為 和。對(duì)用鄰接矩陣表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為，對(duì)用鄰接表表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為。對(duì)于下面的無(wú)向圖G1，假定用鄰接矩陣表示，則從頂點(diǎn)v0開始進(jìn)行深度優(yōu)先搜索遍歷得 到的頂點(diǎn)序列為，從頂點(diǎn)v0開始進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為對(duì)于下面的有向圖G2,假

21、定用鄰接矩陣表示，則從頂點(diǎn)v0開始進(jìn)行深度優(yōu)先搜索遍歷得 到的頂點(diǎn)序列為，從頂點(diǎn)v0開始進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為對(duì)于下面的帶權(quán)圖G3，其最小生成樹的權(quán)為。對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為和 以順序查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為， 時(shí)間復(fù)雜度為。 以二分查找方法從長(zhǎng)度為12的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為。從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為和。在線性表的 存儲(chǔ)中，無(wú)法查找到一個(gè)元素的前驅(qū)或后繼元素。在線性表的 存儲(chǔ)中，對(duì)每一個(gè)元素只能采用順序

22、查找。在線性表的散列存儲(chǔ)中，處理沖突有和 兩種方法。對(duì)于線性表(18,25,63,50,42,32,90)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K % 9作為散列函數(shù)，則散列地址為0的元素有 個(gè)，散列地址為5的元素有 個(gè)。144 .每次從無(wú)序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做 排序；每次從無(wú)序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端， 此種排序方法叫做排序。每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做 排序；每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做排序。 在直接選擇排序中，記錄比較次數(shù)的時(shí)間復(fù)雜度為，

23、記錄移動(dòng)次數(shù)的時(shí)間復(fù) 雜度為。在堆排序的過(guò)程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行次篩運(yùn)算，由初始堆到堆排序結(jié)束，需要對(duì)樹根結(jié)點(diǎn)進(jìn)行 次篩運(yùn)算。 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度 ，整個(gè)堆排 序過(guò)程的時(shí)間復(fù)雜度為。149 .假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為150,快速排序在平均情況下的時(shí)間復(fù)雜度為，在最壞情況下的時(shí)間復(fù)雜度為151,假定一組記錄的排序碼為(46,79,56,38,40,80),對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為在二路歸并排序中，對(duì)n個(gè)記錄進(jìn)行歸并的趟數(shù)為。 對(duì)20個(gè)記錄進(jìn)行歸并排序時(shí)，共需要進(jìn)行趟歸并，

24、在第三趟歸并時(shí)是把長(zhǎng)度為的有序表兩兩歸并為長(zhǎng)度為的有序表。假定一組記錄的排序碼為(46,79,56,38,40,80),對(duì)其進(jìn)行歸并排序的過(guò)程中，第二趟歸并后 的結(jié)果為。已知具有n個(gè)元素的一維數(shù)組采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素的 地址為 LOC(a1)，那么，LOC(ai)=。含有3個(gè)2度結(jié)點(diǎn)和4個(gè)葉結(jié)點(diǎn)的二叉樹可含個(gè)1度結(jié)點(diǎn)。含有2n個(gè)結(jié)點(diǎn)的二叉樹高度至少是，至多是(僅含根結(jié)點(diǎn)的二叉樹高度為零)。用起泡法對(duì)n個(gè)關(guān)鍵碼排序，在最好情況下，只需做次比較和 次移動(dòng)；在最壞的情況下要做 次比較。數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)包括順序、索引和散列等四種。在鏈表中進(jìn)行插入和 操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高。如果一個(gè)對(duì)象部分地包含自己，或自己定義自己，則稱這個(gè)對(duì)象 的對(duì)象。一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點(diǎn)肯定沒(méi)有 子女。向一棵二叉搜索樹中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的 上。在對(duì)一組記錄關(guān)鍵字(54，38，96，23，15，72，60，45，83)進(jìn)行冒泡排序時(shí)，整個(gè)冒泡排序過(guò)程中需進(jìn)行 趟才能完成。將一個(gè)n階三對(duì)角矩陣A的三條對(duì)角線上的元素按行壓縮存放于一個(gè)一維數(shù)組B中，A00存放于B0中。對(duì)于任意給