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

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