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

一、填空題數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)包括順序、(鏈接)、索引和散列等四種。設(shè)關(guān)鍵字序列｛7,12,26,30,47,58,66,70,82,90｝,當(dāng)用折半查找方法查找時,所需比較的次數(shù)為3次的關(guān)鍵字分別是(7265882)。假定一個線性表為｛12,23,74,55,63,40,82,36｝，若按key%3條件進行劃分,使得同一余數(shù)的元素成為一個子表,則包含74的子表長度為(2)。和折半查找相比,順序查找的優(yōu)點是除了不要求表中數(shù)據(jù)元素有序之外,對(存儲)結(jié)構(gòu)也無特殊要求。設(shè)雙向循環(huán)鏈表每個結(jié)點結(jié)構(gòu)為(data,llink,rlink),則結(jié)點*p的前驅(qū)結(jié)點的地址為(p->llink)。n個頂點的連通無向圖的生成樹含有(n-1)條邊。在一個最大堆中,堆頂結(jié)點的值是所有結(jié)點中的(最大值)。假定對長度n=50的有序表進行折半查找，則對應(yīng)的判定樹中最底下一層的結(jié)點數(shù)為(19)個。對于帶頭結(jié)點的鏈棧top,取棧頂元素的操作是(*y=top->next->data)。假定一棵二叉樹的結(jié)點個數(shù)為50,則它的最小高度為(5)。假定樹根結(jié)點的深度為0。二維數(shù)組是一種非線性結(jié)構(gòu),其中的每一個數(shù)組元素最多有(2)個直接前驅(qū)(或直接后繼)。在堆排序中,對任意一個分支結(jié)點進行調(diào)整運算的時間復(fù)雜度為(O(log2n))。隊列的刪除操作在(隊頭(或隊首))進行。設(shè)圖G=(V,E),V={1,2,3,4},E={<1,2>,<1,3>,〈2,4>,〈3,4>},從頂點1出發(fā)，對圖G進行廣度優(yōu)先搜索的序列有(2)種。向一棵二叉排序樹中插入一個元素時,若元素的值小于根結(jié)點的值,則應(yīng)把它插入到根結(jié)點的(左子樹)上?？焖倥判蛟谄骄闆r下的時間復(fù)雜度為(O(nlog2n))。由關(guān)鍵字序列{42,97,75,23,68,34}建成的最大堆是(97,68,75,23,42,34)。對于關(guān)鍵字序列(12,13,11,18,60,15,7,18,25,100)進行初始建堆,必須從關(guān)鍵字為(60)的結(jié)點開始。從有序表(12,18,30,43,56,78,82,95)中折半查找元素56時,其查找長度為(3)。設(shè)有二叉樹根結(jié)點的層次為0,一棵高度為h的滿二叉樹中的葉子結(jié)點個數(shù)是(2h)。在一個最小堆中,堆頂結(jié)點的值是所有結(jié)點中的(最小值)。在長度為n的順序表中刪除一個元素時，等概率情況下的平均移動元素的次數(shù)是((n-1)/2)。由關(guān)鍵字序列（57,24,76,63,18,31,15）生成的一棵二叉排序樹,其等查找概率情況下查找成功的平均查找長度為（18/7）數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、（存儲結(jié)構(gòu)）和數(shù)據(jù)的運算三個方面。在一棵m階B樹上，每個非根結(jié)點的關(guān)鍵字?jǐn)?shù)最多為（m-1）個。在雙向鏈表中,每個結(jié)點除了數(shù)據(jù)域外,還有兩個指針域,它們分別指向（前趨結(jié)點和后繼結(jié)點）。一般來說，深度優(yōu)先生成樹的高度比廣度優(yōu)先生成樹的高度要（高）。遞歸工作棧起到兩個作用，其一是將遞歸調(diào)用時的實際參數(shù)和返回地址傳遞給下一層遞歸;其二是保存本層的形式參數(shù)和（局部變量）。在一個堆的順序存儲中,若一個元素的下標(biāo)為i（OWiWn-1），則它的右子女元素的下標(biāo)為（2i+2）。數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)和（非線性）結(jié)構(gòu)兩大類。隊列是具有（先進先出）特性的線性表?；緮?shù)據(jù)類型是計算機已經(jīng)實現(xiàn)了的（數(shù)據(jù)結(jié)構(gòu)）。n個頂點且含有環(huán)路的無向連通圖中，至少含有（n）條邊。若設(shè)L是指向帶表頭的單鏈表，語句L->link=L->link->link的作用是（刪除）單鏈表中的第一個結(jié)點。已知8個數(shù)據(jù)元素為(34,76,45,18,26,54,92,65),按照依次插入結(jié)點的方法生成一棵二叉排序樹后,最后兩層上的結(jié)點總數(shù)為(2)。大小為M的順序存儲的循環(huán)隊列sq隊滿的條件為((sq.rear+l)%M==sq.front)。若設(shè)順序棧的最大容量為MaxSize,top==-l表示?？?，則判斷棧滿的條件是(top==MaxSize-1)。假定一個順序表的長度為40,并假定順序查找每個元素的概率都相同,則在查找成功情況下的平均搜索長度為(20.5)。設(shè)有程序段為for(i=1;i<10;i++)for(j=1;j<=i;j++){p=i*j;printf(“%4d\n”,p);}則執(zhí)行p=i*j的次數(shù)為(45)。一棵高度為5的完全二叉樹中,最多包含有(63)個結(jié)點。假定樹根結(jié)點的高度為0。第i(i=1,2,…，n-1)趟從參加排序的序列中取出第i個元素，把它插入到由第0個至第i-1個元素組成的有序表中適當(dāng)?shù)奈恢?，此種排序方法叫做(直接插入)排序。設(shè)棧S和隊列Q的初始狀態(tài)為空，元素A,B,C,D,E,和F依次通過棧S,且一個元素出棧后即進入隊列Q,若6個元素出隊列的順序是B,D,C,F,E,A,則棧S的容量至少是(3)。45.在對m階B樹插入元素的過程中，每向一個結(jié)點插入一個關(guān)鍵字后,若該結(jié)點的關(guān)鍵字個數(shù)等于(m)個,則必須把它分裂為2個結(jié)點。棧是一種限定在表的一端進行插入和刪除的線性表,又被稱為(后出先進)表。在無向圖G的鄰接矩陣表示中，第j列中非零元的個數(shù)等于該頂點的(度)。在一個鏈?zhǔn)疥犃兄?若隊頭指針與隊尾指針的值相同,則表示該隊列至多有(1)個結(jié)點。假定一棵二叉樹的結(jié)點數(shù)為18,則它的最小高度為(4)。假定樹根結(jié)點的高度為0。在單鏈表中,除了表頭結(jié)點外,任意結(jié)點的存儲位置由其直接(前驅(qū))結(jié)點的指針域的值所指示。由分別帶權(quán)為9,6,2,5,7的五個葉子結(jié)點構(gòu)造的哈夫曼樹的帶權(quán)路徑長度為(65)。對長度為20的有序表進行二分查找的判定樹的高度為(5)。快速排序在平均情況下的空間復(fù)雜度為(O(log2n))。隊列是一種限定在表的一端插入,在另一端刪除的線性表,它又被稱為(先進先出)表。當(dāng)用長度為MaxSize的數(shù)組順序存儲一個棧時，若用top==MaxSize表示?？?，則表示棧滿的條件為(top==0)。若進棧序列為a,b,c，且進棧和出?？梢源┎暹M行，則可能出現(xiàn)(5)個不同的出棧序列。若設(shè)一個n的矩陣A的開始存儲地址LOC(0,0)及元素所占存儲單元數(shù)d已知，按行存儲時其任意一個矩陣元素a[i][j]的存儲地址為(L0C(0,0)+(i*n+j)*d)。如果n個頂點的圖是一個環(huán)，則它有(n)棵生成樹。設(shè)有程序段為:for(i=1;i<=10;i++)for(j=1;j<=i;j++)p=i*j;則執(zhí)行p=i*j的次數(shù)為(45)。在單鏈表中某P結(jié)點后插入S結(jié)點的操作是(s->next二p->next;p->next=s;)。以順序查找方法從長度為n的順序表或單鏈表中查找一個元素的漸進時間復(fù)雜度為(O(n))。在直接選擇排序中，記錄比較次數(shù)的時間復(fù)雜度為(O(n2))。棧下溢是指在(?？?時進行出棧操作。在單鏈表設(shè)置表頭結(jié)點的作用是插入和刪除表中第一個元素時不必對（表頭指針）進行特殊處理。一維數(shù)組所占用的空間是連續(xù)的。但數(shù)組元素不一定順序存取,通常是按元素的（下標(biāo)（或順序號））存取的。利用三元組表存放稀疏矩陣中的非零元素,則在三元組表中每個三元組元素對應(yīng)一個非零元素的行號、列號和（值）。克魯斯卡爾算法適用于求（邊稀疏）的網(wǎng)的最小生成樹。用鏈表表示線性表,表中元素之間的邏輯關(guān)系是通過鏈表中結(jié)點的（指針）來實現(xiàn)的。將一棵樹按照左孩子-右兄弟表示法轉(zhuǎn)換成對應(yīng)的二叉樹,則該二叉樹中樹根結(jié)點肯定沒有（右）孩子。由帶權(quán)為9,6,2,5,7的五個葉子結(jié)點構(gòu)造的哈夫曼樹,其根結(jié)點的權(quán)值為（29）。11個頂點的連通網(wǎng)絡(luò)N有10條邊，其中權(quán)值為1,2,3,4,5的邊各2條,則網(wǎng)絡(luò)N的最小生成樹各邊的權(quán)值之和（30）線性表是由n（n±0）個（數(shù)據(jù)元素）組成的有限序列。給定一組數(shù)據(jù)元素的關(guān)鍵字為{46,79,56,38,40,84},對其進行一趟快速排序處理,得到的右子表中有（3）個元素。將一個n階對稱矩陣的上三角部分或下三角部分壓縮存放于一個一維數(shù)組中，則一維數(shù)組需要存儲（n（n+1）/2）個矩陣元素。對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為(n-1)。在使用Kruskal算法構(gòu)造連通網(wǎng)絡(luò)的最小生成樹時，只有當(dāng)一條候選邊的兩個端點不在同一個(連通量)上，才會被加入到生成樹中。設(shè)序列｛25，36，40，45，48，56，60，68，72，85｝，當(dāng)用折半查找方法查找36時，所需比較的次數(shù)為(2)。哈希查找是通過(哈希函數(shù))來確定記錄的存儲地址的。對n個數(shù)據(jù)對象進行堆排序，總的時間復(fù)雜度為(O(nlog2n))。在線性表的散列存儲中，裝載因子又稱為裝載系數(shù)，若用m表示散列表的長度,n表示待散列存儲的元素的個數(shù)，則等于(n/m)。設(shè)圖的頂點數(shù)為n,則求解最短路徑的Dijkstra算法的時間復(fù)雜度為(O(n2))。已知一棵3階B樹中含有50個關(guān)鍵字,則該樹的最大高度為(5)。從一棵二叉排序樹中查找一個元素時，若給定值大于根結(jié)點的值，則需要向(右子樹)繼續(xù)查找。鏈接存儲表示的結(jié)點存儲空間一般在程序的運行過程中進行動態(tài)地(分配)和釋放。線性表的鏈接存儲只能通過(鏈接指針)順序訪問。直接插入排序在初始有序時，進行(n-1)次關(guān)鍵字比較。每次直接或通過基準(zhǔn)元素間接比較兩個元素,若出現(xiàn)逆序排列就交換它們的位置,這種排序方法叫做（交換）排序。單鏈表中邏輯上相鄰的結(jié)點而在物理位置上（不一定）相鄰。鏈表只適用于（順序）查找。在堆排序中，如果n個對象的初始堆已經(jīng)建好，那么到排序結(jié)束，還需要從堆頂結(jié)點出發(fā)調(diào)用（n-1）次調(diào)整算法。向一個順序棧插入一個元素時，首先使（棧頂指針）后移一個位置，然后把待插入元素寫入到這個位置上。在帶表頭結(jié)點的單鏈表中刪除某一指定結(jié)點，必須找到該結(jié)點的（前一個）結(jié)點。在一棵高度為3的四叉樹中，最多含有（85）個結(jié)點，假定樹根結(jié)點的高度為0。在含有3個結(jié)點a,b,c的二叉樹中，前根序列為abc且后根序列為cba的二叉樹有（4）棵。設(shè)圖G=（V,E）,V={VO,VI,V2,V3},E={（VO,VI）,（VO,V2）,（VO,V3）,（V1,V3）}，則從頂點VO開始的圖G的不同深度優(yōu)先序列有（4）種。在一般情況下用直接插入排序、選擇排序和冒泡排序的過程中,所需記錄交換次數(shù)最少的是（選擇排序）。在鏈表的結(jié)點中,數(shù)據(jù)元素所占的存儲量和整個結(jié)點所占的存儲量之比稱作（存儲密度）°1OO.用鄰接矩陣存儲圖，占用的存儲空間與圖中的（頂點）數(shù)有關(guān)。對稱矩陣的行數(shù)與列數(shù)(相等)且以主對角線為對稱軸,aij=aji,因此只存儲它的上三角部分或下三角部分即可。在直接選擇排序中,記錄移動次數(shù)的時間復(fù)雜度為(O(n))。對關(guān)鍵字序列(15,18,11,13,19,16,12,17,10,8)進行增量為5的一趟希爾排序的結(jié)果為((15,12,11,10,8,16,18,17,13,19))。已知完全二叉樹有200個結(jié)點,則整個二叉樹有(1)個度為1的結(jié)點。普里姆算法適用于求(邊稠密)的網(wǎng)的最小生成樹。在一個堆的順序存儲中,若一個元素的下標(biāo)為i(OWiWn-1),則它的左孩子元素的下標(biāo)為(2i+1)。若用鄰接矩陣表示有向圖,則頂點i的入度等于矩陣中(所對應(yīng)列中的非零元素個數(shù))o108.鏈隊列l(wèi)q為空的條件為(Lq->rear==lq.front)。109.長度為11的有序表進行折半查找時,在等查找概率情況下查找成功的平均查找長度為(3)o110.第i(i=0,1,...,n-2)趟從參加排序的序列中第i個至第n-1個元素中挑選出一個最小元素,把它交換到第i個位置，此種排序方法叫做(直接選擇)排序?？焖倥判蛟谧顗那闆r下的時間復(fù)雜度為(O(n2))。由關(guān)鍵字序列｛36,96,84,18,52,27｝建成的最小堆是((18,36,27,96,52,84))。深度為10的完全二叉樹,至少有(512)個結(jié)點。在一棵二叉樹中,假定雙分支結(jié)點數(shù)為5個,單分支結(jié)點數(shù)為6個,則葉子結(jié)點數(shù)為(6)個。向一個棧頂指針為top的鏈?zhǔn)綏Ｖ胁迦胍粋€新結(jié)點*p時,應(yīng)執(zhí)行(p->next二top)和top=p操作。假設(shè)用<x,y>表示樹的邊(其中x是y的雙親)，已知一棵樹的邊集為{<b,d>,<a,b>,<c,g>,<c,f>,<c,h>,<a,c>},該樹的度是(3)。設(shè)待排序的表為(42,55,12,47,94,06,18,63),利用快速排序方法對其進行排序,經(jīng)第一趟排序后,表的狀態(tài)為((18,06,12,42,94,47,55,63))。估算算法時間復(fù)雜度時考慮的問題規(guī)模通常是指算法求解問題的(輸入量)。在一棵三叉樹中,度為3的結(jié)點數(shù)有2個,度為2的結(jié)點數(shù)有1個,度為1的結(jié)點數(shù)為2個,那么度為0的結(jié)點數(shù)有(6)個。n(n>0)個頂點的連通無向圖各頂點的度之和最少為(2(n-1))。對n個元素的序列進行冒泡排序時，(初始數(shù)據(jù)有序)情況下比較次數(shù)最少，比較次數(shù)為(n-1)。已知一棵3階B樹中含有50個關(guān)鍵字,則該樹的最小高度為(4)。僅允許在表的同一端進行插入和刪除運算的線性表被稱為(棧)。鏈表與順序表、索引表、散列表等都是數(shù)據(jù)邏輯結(jié)構(gòu)的(存儲)表示。如果一個對象部分地包含自己,或自己定義自己,則稱這個對象是(遞歸)的對象。127.在有向圖的鄰接表表示中,每個頂點鄰接表中所含的結(jié)點數(shù)等于該頂點的（出度）。128.給定一組數(shù)據(jù)對象的關(guān)鍵碼為{46,79,56,38,40,84},則利用堆排序方法建立的初始堆（最大堆）為（{84,79,56,38,40,46}）。設(shè)關(guān)鍵字序列（17,8,13,25,24,16,3,19,1）,用希爾排序法按升序排序,用初始增量4進行一趟排序后的結(jié)果是（1,8,3,19,17,16,13,25,24）。設(shè)循環(huán)隊列用數(shù)組A[m]表示，隊頭、隊尾指針分別是front和rear,則判定隊滿的條件為（（rear+1）%M==front）。求解帶權(quán)連通圖最小生成樹的Prim算法使用圖的（鄰接矩陣）作為存儲結(jié)構(gòu)。在堆排序中，對n個記錄建立初始堆需要調(diào)用（n/2）次調(diào)整算法。已知一棵二叉樹的先根序列為ABDFCE,中根序列為DFBACE,則后根序列為（FDBECA）。用折半查找法查找一個線性表中的元素時,此線性表必須是（有序的）。在有向圖的鄰接矩陣表示中，第j列元素之和等于第j個頂點的（入度）。在鏈表中進行插入和（刪除）操作的效率比在順序存儲結(jié)構(gòu)中進行相同操作的效率高。137.算法的一個特性是（有窮性）