數(shù)據(jù)結構 填空題

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

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

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

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

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

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

7、個新元素的過程應該首先， 然后，最后。(1WnWn+1)若具有n個結點的二叉樹采用二叉鏈表結構，則該鏈表中共有個指針域，其中個指針域用于鏈接孩子結點，個指針域存放nil。 TOC o 1-5 h z 對具有n個元素的序列采用堆積排序法進行排序，排序趟數(shù)為?？焖倥判蛟谄骄闆r下的空間復雜度為。 若一棵二叉樹有10個葉結點，則該二叉樹中度為2的結的點個數(shù)為。 具有n個結點的非空二叉排序樹的最小深度為。 深度為h且有個結點的二叉樹稱為滿二叉樹。(設根結點處在第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,)，按照逐點插入法建立一棵二叉排序列樹，該樹的深度是。一個不帶有權的有向圖采用鄰接矩陣存儲方法，其鄰接矩陣是一 。帶權連通圖 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,(注：頂點偶對右下角的數(shù)據(jù)為邊上的權值)，G的最小 生成樹的權值之和為。在線性表中采用折半查找法(二分查找法)查找一個數(shù)據(jù)元素，線性表中元素應該按值有序，并且采用存儲方法。52.若對序列(49, 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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