《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題

PAGE2《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)題一、填空題1.數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是和2.數(shù)據(jù)元素之間有多種關(guān)系，其中常見(jiàn)的關(guān)系有、、、。3.線性表的順序存儲(chǔ)是用實(shí)現(xiàn)的。4.在長(zhǎng)度為n的順序表中插入一個(gè)元素，等概率的情況下的平均移動(dòng)元素的次數(shù)是____5.三個(gè)結(jié)點(diǎn)可構(gòu)成________種不同形態(tài)的二叉樹(shù)。6.對(duì)于棧只能在_______(位置)插入和刪除元素。7.對(duì)矩陣壓縮是為了_______8.深度為k的完全二叉樹(shù)至少有_______個(gè)結(jié)點(diǎn)，至多有_______個(gè)結(jié)點(diǎn)。9.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為_(kāi)____個(gè)，其中________個(gè)用于鏈接孩子結(jié)點(diǎn)。10.對(duì)二叉排序樹(shù)進(jìn)行________遍歷，可得到排好序的遞增結(jié)點(diǎn)序列。11.N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有______條邊12.己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當(dāng)用二分法查找90時(shí)，需__________次查找成功，47時(shí)__________成功，查100時(shí)，需__________次才能確定不成功。算法的計(jì)算量的大小稱為計(jì)算的____在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)____決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)____決定的。對(duì)于一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*P后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)___,在給定值為X的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)___.無(wú)論對(duì)于順序存儲(chǔ)還是鏈接存儲(chǔ)的隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為_(kāi)___.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹(shù)，該樹(shù)中所有結(jié)點(diǎn)的度數(shù)之和為_(kāi)___在一個(gè)完全二叉樹(shù)的順序存儲(chǔ)中，若一個(gè)結(jié)點(diǎn)的下標(biāo)為i，則它的左子女結(jié)點(diǎn)的下標(biāo)為_(kāi)___,右子女結(jié)點(diǎn)的下標(biāo)為_(kāi)___.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)應(yīng)二叉鏈表中指針總數(shù)為_(kāi)___個(gè)，其中____個(gè)用于指向子女結(jié)點(diǎn)，____個(gè)指針空閑著以折半搜索方法搜索一個(gè)線性表時(shí)，此線性表必須是____存儲(chǔ)的____表在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的____倍。10.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有____條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有____條邊。11.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有頂點(diǎn)則至少需要____條邊。12.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別為_(kāi)___和____條二、選擇題1.算法的時(shí)間復(fù)雜度取決于（）

A．問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B2.下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（）

A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。

D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3.若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1<=i<=n+1)。

A.O(0)B.O(1)C.O(n)D.O(n2)4.對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（）

A．head==NULLB．head.next==NULLC．head.next==headD．head!=NULL5.一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（）。

A.不確定B.n-i+1C.iD.n-i6.已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？()

A.s->link=p；p->link=s；B.s->link=p->link；p->link=s；

C.s->link=p->link；p=s；D.p->link=s；s->link=p；7.設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊。

A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n28.下列排序算法中()不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。

A.快速排序B.shell排序C.堆排序D.冒泡排9.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）

A.以順序方式存儲(chǔ)B.以順序方式存儲(chǔ),且數(shù)據(jù)元素有序C.以鏈接方式存儲(chǔ)D.以鏈接方式存儲(chǔ),且數(shù)據(jù)元素有序10.在下面的排序方法中，輔助空間為O（n）的是()。

A．希爾排序B.堆排序C.選擇排序D.歸并排序在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為（）

FORi:=1TOnDO

x:=x+1;

A．O(2n)B．O(n)C．O(n2)D．O(log2n)線性表是具有n個(gè)（）的有限序列（n>0）。

A．表元素B．字符C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1<=i<=n+1)。

A.O(0)B.O(1)C.O(n)D.O(n2)下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）()

A．深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑鏈表不具有的特點(diǎn)是（）

A．插入、刪除不需要移動(dòng)元素B．可隨機(jī)訪問(wèn)任一元素

C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線性長(zhǎng)度成正比某堆棧的輸入序列為a,b，c，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（）。

A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。

A．線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧如果節(jié)點(diǎn)A有兩個(gè)兄弟，B是A的雙親，則B的度為 （）

A.5B.4C.3D.2數(shù)組A[0..4,0..3]中含有元素的個(gè)數(shù)（）。

A.55B.20C.36D.16在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有邊數(shù)的（）倍

A.1/2B.1C.2D.4三、名詞解釋1.堆（heap）2.完全圖3.二叉排序樹(shù)4.樹(shù)中節(jié)點(diǎn)的度和樹(shù)的度5.二叉樹(shù)的后序遍歷1.數(shù)據(jù)結(jié)構(gòu)2.稀疏矩陣3.排序算法的穩(wěn)定性4.連通圖5.AOE網(wǎng)四、簡(jiǎn)答題1、簡(jiǎn)述線性表的特點(diǎn)2121743658第3題圖3、求圖中每個(gè)頂點(diǎn)的入度、出度；4、某二叉樹(shù)的前序遍歷為：ABHFDECKG，中序遍歷為：HBDFAEKCG，請(qǐng)構(gòu)造出此二叉樹(shù)5、給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18),寫出用直接插入排序算法從小到大排序時(shí)第一趟結(jié)束時(shí)的序列（只寫出最終的結(jié)果）；6、給定一組數(shù)據(jù){4,5,2,3}，以它構(gòu)造一棵哈夫曼樹(shù)7、設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，請(qǐng)具體寫出這四輛列車開(kāi)出車站的任意5種可能的順序8、某完全二叉樹(shù)共有701個(gè)結(jié)點(diǎn)，請(qǐng)問(wèn)其樹(shù)葉有多少個(gè)2121743658第3題圖2、舉例說(shuō)明希爾排序是否為穩(wěn)定排序法3、寫出右圖的拓?fù)渑判蛐蛄?、某二叉樹(shù)的后序遍歷為：HDFBKGCEA，中序遍歷為：HBCFAEKCG，請(qǐng)構(gòu)造出此二叉樹(shù)5、有如下的一組數(shù)據(jù)，1,5,6,10,15,16,17,18,19,20,30。畫出其折半查找的判定樹(shù)。6、寫出第3題圖的深度優(yōu)先和廣度優(yōu)先遍歷序列7、用序列(20，15，35，30，25，40)建立一個(gè)二叉排序樹(shù)，畫出該樹(shù)。8、畫一棵深度為4的完全二叉樹(shù)五、算法設(shè)計(jì)題1、對(duì)單鏈表中節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)進(jìn)行定義.說(shuō)明節(jié)點(diǎn)中為整型數(shù)據(jù)2、根據(jù)上題定義的節(jié)點(diǎn)的結(jié)構(gòu)，寫出在單鏈表（first為頭指針）中查找第i個(gè)節(jié)點(diǎn)的算法.函數(shù)頭部如下intGet(node*first,inti)3、寫出冒泡排序算法voidBubbleSort(intr[],intn)參考答案一、填空題數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是時(shí)間復(fù)雜性和空間復(fù)雜性數(shù)據(jù)元素之間有多種關(guān)系，其中常見(jiàn)的關(guān)系有集合、線性、樹(shù)、圖。線性表的順序存儲(chǔ)是用數(shù)組實(shí)現(xiàn)的。在長(zhǎng)度為n的順序表中插入一個(gè)元素，等概率的情況下的平均移動(dòng)元素的次數(shù)是____(n+1)/2三個(gè)結(jié)點(diǎn)可構(gòu)成__5___種不同形態(tài)的二叉樹(shù)。對(duì)于棧只能在___棧頂____(位置)插入和刪除元素。對(duì)矩陣壓縮是為了_節(jié)省存儲(chǔ)空間______深度為k的完全二叉樹(shù)至少有_K個(gè)結(jié)點(diǎn)，至多有_2k-1____個(gè)結(jié)點(diǎn)。對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為_(kāi)__2n_個(gè)，其中___n-1__個(gè)用于鏈接孩子結(jié)點(diǎn)。對(duì)二叉排序樹(shù)進(jìn)行___中序_____遍歷，可得到排好序的遞增結(jié)點(diǎn)序列。N個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有__n-1_條邊己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當(dāng)用二分法查找90時(shí)，需_____2____次查找成功，47時(shí)______4___成功，查100時(shí)，需_____4____次才能確定不成功。二、選擇題算法的時(shí)間復(fù)雜度取決于（C）

A．問(wèn)題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C.A和B下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（B）

A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。

B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。

C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。

D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（C）(1<=i<=n+1)。

A.O(0)B.O(1)C.O(n)D.O(n2)對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（B）

A．head==NULLB．head.next==NULLC．head.next==headD．head!=NULL一個(gè)棧的輸入序列為123…n，若輸出序列的第一個(gè)元素是n，輸出第i（1<=i<=n）個(gè)元素是（B）。

A.不確定B.n-i+1C.iD.n-i已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行下列哪一個(gè)操作？(B)

A.s->link=p；p->link=s；B.s->link=p->link；p->link=s；

C.s->link=p->link；p=s；D.p->link=s；s->link=p；設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（C）條邊。

A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2下列排序算法中(B)不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。

A.快速排序B.shell排序C.堆排序D.冒泡排對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（B）

A.以順序方式存儲(chǔ)B.以順序方式存儲(chǔ),且數(shù)據(jù)元素有序C.以鏈接方式存儲(chǔ)D.以鏈接方式存儲(chǔ),且數(shù)據(jù)元素有序在下面的排序方法中，輔助空間為O（n）的是(D)。

A．希爾排序B.堆排序C.選擇排序D.歸并排序三、名詞解釋堆（heap）堆是具有下列性質(zhì)的完全二叉樹(shù)：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。完全圖無(wú)向完全圖：在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在