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

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題一、名詞解釋數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)物理結(jié)構(gòu)、順序存儲、鏈?zhǔn)酱鎯?、算法、時間復(fù)雜度、空間復(fù)雜度。線性表、順序表、單鏈表、雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表、三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第1個元素結(jié)點）。棧（順序棧、鏈棧）、隊列（順序隊、鏈隊）、循環(huán)隊列、遞歸、稀疏矩陣、三元組。樹、葉子結(jié)點、結(jié)點的度、樹的度、樹的高（深）度、二叉樹、遍歷、滿二叉樹、完全二叉樹、哈夫曼樹、WPL、哈夫曼編碼。圖（有向、無向）、網(wǎng)、邊、弧、度、入度、出度、完全圖（有向、無向）、（強(qiáng)）連通圖（分量）、（最小）生成樹、鄰接矩陣、鄰接表、DFS、BFS。查找表、關(guān)鍵字

2、、靜態(tài)查找、動態(tài)查找、ASL、順序查找、折半查找、分塊查找、二叉排序樹。7、排序、內(nèi)（外）排序、穩(wěn)定性、插入（直接、希爾），交換（起泡、快速），選擇（直接、堆），2路歸并。一、填空題數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，并在這種結(jié)構(gòu)上定義相關(guān)的運算，設(shè)計實現(xiàn)這些運算的算法，分析算法的效率。算法的效率包括時間和空間兩個方面，分別稱為.時間復(fù)雜度和空間復(fù)雜度。數(shù)據(jù)的基本單位是數(shù)據(jù)元素，數(shù)據(jù)的最小單位是數(shù)據(jù)項。算法是對特定問題求解.步驟的一種描述,是指令的有限序列。一個算法的時間復(fù)雜度為（3n3+2n7）,其數(shù)量級表示為_O（n3）_。一個算法具有5個特性：_確定性、_可行性_、_有窮性、輸入和輸

3、出。算法性能的分析和度量，可以從算法的時間復(fù)雜度一和空間復(fù)雜度來評價算法的優(yōu)劣。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、_線性結(jié)構(gòu)_、_樹形結(jié)構(gòu)_和_圖型結(jié)構(gòu)四種類型。&數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，它可以采用順序存儲或鏈?zhǔn)酱鎯煞N存儲方法。線性表有兩種存儲結(jié)構(gòu)，分別為順序存儲和鏈?zhǔn)酱鎯。鏈?zhǔn)酱鎯Φ奶攸c是利用指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表宜采用鏈?zhǔn)酱鎯Υ鎯Y(jié)構(gòu)。線性表中的數(shù)據(jù)元素之間具有一對一的線性關(guān)系，除第一個和最后一個元素外，其他數(shù)據(jù)元素有且只有一個直接后繼和直接前趨。在一個單鏈表中p所指結(jié)點之后插入一個s所指結(jié)點時，應(yīng)執(zhí)行s-next=

4、和p-next=的操作。在一個單鏈表中刪除p的后繼結(jié)點q時，應(yīng)執(zhí)行以下操作p-next=_q-next。對帶頭結(jié)點head的單鏈表，則判斷其為空的條件為_head-next=NULL。16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.對帶頭結(jié)點head的循環(huán)單鏈表尾結(jié)點(由p所指向)判非空的條件為p-next=head。在棧結(jié)構(gòu)中，允許插入的一端稱為棧頂;在隊列結(jié)構(gòu)中，允許插入的一端稱為隊尾。隊列中元素的入隊和出隊?wèi)?yīng)遵循先進(jìn)先出原則,數(shù)據(jù)元素1,2,3,4,5按照次序入隊后，第一個出隊的是。在循

5、環(huán)隊列中，存儲空間為0n-1。設(shè)隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么其隊空標(biāo)志為rear二front,隊滿標(biāo)志_(rear+1)%n=front_。設(shè)順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存儲地址為239。在一個長度為n的順序表中刪除第i個元素(1WiWn),需向前移動n-i個元素。在一個長度為n的順序表中第i個元素前(1WiWn),插入一個元素，需向后移動n-i+1個元素。在順序存儲的線性表中插入或刪除一個元素平均約移動表中50%(或一半)的元素。在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為0(1),因此，順序表也

6、稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p,需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為0(n)。一個廣義表為(a,(a,b),d,e,(ij),k),貝V該廣義表的長度為_5，深度為_3。已知廣義表A=(a,b,c),(d,e,f),則運算tail(head(tail(A)=(e,f)_。已知廣義表Ls=(a,(b,c,d),e),運用head和tail函數(shù)取出Ls中的原子b的運算是head(head(tail(LS)。廣義表(a,b),c,d)的表頭是_(a,b)表尾是_(c,d)。廣義表(a,b,c,d)的表頭是a表尾是(b,c,d)。兩個串相等的充分必要條件是：串長相等

7、且對應(yīng)的字符相等。不含任何字符的串稱為空串其長度為0_。對于稀疏矩陣的壓縮存儲，通常用一個三元組表示非零元素的信息，其中包括非零元素所在的行、列以及它的值。若二叉樹中有20個葉子結(jié)點，則該二叉樹有19個度為2的結(jié)點。若二叉樹中度為2的結(jié)點有15個，則該二叉樹有16個葉子結(jié)點。深度為h且有21-1個結(jié)點的二叉樹稱為滿二叉樹。深度為k的二叉樹最多有27-1個結(jié)點,最少有k個結(jié)點,第i層上最多有2(i-1)個結(jié)點。深度為5的滿二叉樹共有31個結(jié)點，其中有16個葉子節(jié)點。若深度為6的完全二叉樹的第6層有3個葉結(jié)點，則該二叉樹一共有_34個結(jié)點。深度為15的滿二叉樹上，第11層有2,11-1)=1024

8、個結(jié)點。一棵具有100個結(jié)點的完全二叉樹，它的深度為_7，其中度為1的結(jié)點有1_個。某二叉樹的后根遍歷序列為abd，中根遍歷序列為adb，則它的先根遍歷序列為dab。43哈夫曼樹是指對于一組帶有確定權(quán)值的葉子結(jié)點構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。具有m個葉子結(jié)點的哈夫曼樹共有2m-1個結(jié)點。已知一棵哈夫曼樹含有60個葉子結(jié)點，則該樹中共有59個非葉子結(jié)點。在一個具有n個頂點無向完全圖中，含有_n(n-1)/2邊；在一個具有n個頂點有向完全圖中，含有_n(n-1)邊。一個具有4個頂點的無向完全圖有_6_條邊。具有n個頂點的連通圖至少需有_n-1_條邊。一個連通圖的生成樹是該圖的極小連通子圖。若

9、這個連通圖有n個頂點，則它的生成樹有n-1_條邊。在有向圖的鄰接矩陣中，第i行中非零元素的個數(shù)正好是第i個頂點的出度_；第i列中非零元素的個數(shù)正好是第i個頂點的入度_。在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的_2_倍。在無向圖G的鄰接矩陣A中，若Aij等于1,則Aji等于_1。對二叉排序樹進(jìn)行中序遍歷，可以得到按關(guān)鍵字從小到大排列的結(jié)點序列。一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)折半查找值為82的結(jié)點時，經(jīng)過_4_次比較后查找成功。在線性表中采用折半查找法查找一個數(shù)據(jù)元素，線性表中元素應(yīng)該按值有序，并且采用順序存儲存儲方法。在簡單選擇排序、

10、堆排序、快速排列、歸并排序四種排序方法中，排序方法穩(wěn)定的是歸并排序。冒泡排序是一種穩(wěn)定的排序方法，對n個元素的序列進(jìn)行冒泡排序時，最多需進(jìn)行_n-1_趟。該排序方法的時間復(fù)雜度為_0血)_。給定序列100，86，48，73，35，39，42，57，66，21，按堆的定義，則它一定大根一堆。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的一種或多種關(guān)系。當(dāng)結(jié)點之間存在M對N(M：N)的聯(lián)系時，稱這種結(jié)構(gòu)為.圖狀結(jié)構(gòu)。隊列的插入操作是在隊列的隊尾進(jìn)行,刪除操作是在隊列的隊頭進(jìn)行。每次從無序表中順序取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做直接插入排序;每次從無序表中挑選出一個最小或最大元素，把它交

11、換到有序表的一端，此種排序方法叫做簡單選擇(或直接選擇)排序。二叉樹的前序遍歷序列為A,B，C，E，F(xiàn)，D，G，H,中序遍歷序列為A,E，C，F(xiàn)，B，G，H，其后序遍歷序列為_E,F,C,G,H,D,B,A一。對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i(0ViVn-1)，則它的左孩子結(jié)點的編63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.號為_2i，右孩子結(jié)點的編號為_2i+l，雙親結(jié)點的編號為_i/2。在一個具有6個頂點的無向完全圖中，包含有_15條邊，在一個具有6個頂點的有向完全圖中，包含有_30條弧。快速排序在平均

12、情況下的時間復(fù)雜度為O(nlogn)，在最壞情況下的時間復(fù)雜度為0()。從一棵二叉排序樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明查找成功，若元素的值小于根結(jié)點的值，則繼續(xù)向左子樹查找,若元素的大于根結(jié)點的值，則繼續(xù)向右子樹查找。在循環(huán)單鏈表中，最后一個結(jié)點的指針域指向一首結(jié)點。假定一棵樹的廣義表表示為A(C,D(E,F，G),H(I，J),則樹中所含的結(jié)點數(shù)為_9個，樹的深度為_,樹的度為3。通常從四個方面評價算法的質(zhì)量：-正確性_、-可讀性_、一健壯性一和一效率與低存儲量需求。假設(shè)一棵完全二叉樹含1000個結(jié)點，則其中度為2的結(jié)點數(shù)為499。一個算法的時間復(fù)雜度為(3n3+2n7)

13、/(5n)，其數(shù)量級表示為_0(n2)。在快速排序、堆排序和歸并排序中，最壞時間復(fù)雜度為0(厲)的排序算法有快速排序。數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D,R),其中D是數(shù)據(jù)元素的有限集合,R是D上的_關(guān)系一有限集合。在歸并排序中，進(jìn)行每趟歸并的時間復(fù)雜度為0(n),整個排序過程的時間復(fù)雜度為.O(nlogn),空間復(fù)雜度為0(n)。-2一若一棵二叉樹有10個葉結(jié)點，則該二叉樹中度為2的結(jié)的點個數(shù)為_。對用鄰接矩陣表示的具有n個定點和e條邊的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為0(n2)_,對用鄰接表表示的圖進(jìn)行任一種遍歷時，其時間復(fù)雜度為0(n+e)。從有序表(12，18，30，43，56，78，82，

14、95)中依次二分查找43和56元素時，其查找長度分別為_1和3。對于一棵具有n個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為2n個，其中n-1個用于指向孩子，n+1個指針是空閑的。從邏輯結(jié)構(gòu)看，線性表是典型的線性結(jié)構(gòu)，樹是典型的.非線性結(jié)構(gòu)。設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild,則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是p-lchild=NULL&p-rchild=NULL。棧是一種先進(jìn)后出表。隊列又稱為先進(jìn)先出表。若對序列(49，38，65，97，76，13，27，50)采用直接選擇排序法排序，則第三趟結(jié)束后序列的狀態(tài)是（13,27,38）,97,76,49,65,

15、50。利用關(guān)鍵碼分別為10,20,30,40的四個結(jié)點，能構(gòu)造出14種不同的二叉排序樹.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進(jìn)行(按遞增排序)，冒泡排序最省時間，快速排序最費時間?？沾拈L度是0；空格串的長度是空格的個數(shù)。串中所含字符個數(shù)稱為該串的長度在n個結(jié)點的單鏈表中，在P指向的結(jié)點之后插入一個結(jié)點的時間復(fù)雜度為_0(n)。設(shè)SQ為循環(huán)隊列，存儲在數(shù)組dm中，則SQ出隊操作對其隊頭指針front的修改是front=(front+1)%m。樹的度是指_樹內(nèi)各結(jié)點的度的最大值。已知鏈棧的結(jié)點結(jié)構(gòu)為棧頂指針為top，則實現(xiàn)將指針p所指結(jié)點插入棧頂

16、的語句依次為p-next=top和top=p。堆排序的空間復(fù)雜度0(1)。深度為n(n0)的二叉樹最多有2nT個結(jié)點。設(shè)關(guān)鍵字序列為(K,K，K)，則用篩選法建初始堆必須從第n/2_個元素開始進(jìn)行篩選。l2n圖有鄰接矩陣、鄰接表等存儲結(jié)構(gòu),遍歷圖有深度優(yōu)先搜索、廣度優(yōu)先搜索等方法。在一個有向圖的鄰接表中，一個頂點的鏈表中結(jié)點的個數(shù)等于這個頂點的出度_，在逆鄰接表中，一個頂點的鏈表中結(jié)點的個數(shù)等于這個頂點的入度。對于有10個元素的有序表采用二分查找，需要比較3次方可找到其對應(yīng)的鍵值，則該元素在有序表中的位置可能是1,3,6,9。折半查找有序表(4，6，12，20，28，38，50，70，88，1

17、00)，若查找表中元素20，它將依次與表中元素比較大小。在對一組記錄關(guān)鍵字(54，38，96，23，15，72，60，45，83)進(jìn)行冒泡排序時，整個冒泡排序過程中需進(jìn)行8_趟才能完成。對關(guān)鍵字序列(52,80,63,44,48,91)進(jìn)行一趟快速排序之后得到的結(jié)果為48,44,52,63,80,91q在堆排序和快速排序中，若初始記錄接近正序或反序，則選用堆排序；若初始記錄基本無序,則最好選用快速排序。在對一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行直接插入排序時,當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置至少需比較_3次。設(shè)一組記錄關(guān)鍵字序列為(80,70,33

18、,65,24,56,48)，則用篩選法建成的初始堆為(80,70,56,65,24,33,48)或一(24,65,33,80,70,56,48)。、單選題在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是（）數(shù)據(jù)項B.數(shù)據(jù)元素C.數(shù)據(jù)對象D.數(shù)據(jù)文件數(shù)據(jù)結(jié)構(gòu)是（）種數(shù)據(jù)類型B.數(shù)據(jù)的存儲結(jié)構(gòu)C.一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（）.1.2.3.4.5.6.7.8.9.10.11.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)算法指的是（）。計算機(jī)程序C.排序算法算法分析的目的是（）辨別數(shù)據(jù)結(jié)構(gòu)的合理性C.研究算

19、法中輸入與輸出的關(guān)系靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)解決問題的計算方法D.解決問題的有限運算序列評價算法的效率D.鑒別算法的可讀性某程序的時間復(fù)雜度為（3n+nlog2n+n2+8）,其數(shù)量級表示為（）。A.O（n）B.O（nlogn）C.O（n2）D.O（logn）for（i=0；in；i+）for（j=0；jnext=NULLhead!=NULLD.head-next=head已知棧的最大容量為4。若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行,則可能出現(xiàn)的出棧序列為()5，4，3，2，1，6B.2，3，5，6，1，4C.3，C.3，2，5，4，1，61，4，6，5

20、，2，3若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用(存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.單向循環(huán)D.順序表18.對一個算法的評價，不包括如下A.單鏈表B.雙鏈表C.單向循環(huán)D.順序表18.對一個算法的評價，不包括如下()方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D時空復(fù)雜度19.隊列的刪除操作是在()進(jìn)行。A.隊首隊尾C.A.隊首隊尾C.隊前對后A.數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)A.數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型計算機(jī)識別、存儲和加工處理的對象被統(tǒng)稱為(數(shù)據(jù)元素串是任意有限個(符號構(gòu)成的序列符號構(gòu)成的集合符號構(gòu)成的序列符號構(gòu)成的集合字符構(gòu)成的序列字符構(gòu)成的集合字符構(gòu)成的序列字符

21、構(gòu)成的集合如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時(必須判別棧是否滿對棧不作任何判別必須判別棧是否滿對棧不作任何判別必須判別棧是否空判別棧元素的類型二分查找要求被查找的表是()鍵值有序的鏈接表鏈接表但鍵值不一定有序鍵值有序的順序表順序表但鍵值不一定有序24.25.26.27.28.29.30.31.32.33.34.35.36.37.當(dāng)初始序列已經(jīng)按鍵值有序，用直接插入算法對其進(jìn)行排序，需要循環(huán)的次數(shù)為（n2nlog2nn2nlog2nlog2nnT堆是一個鍵值序列kl,k2,堆是一個鍵值序列kl,k2,，kn，對i=l,2,：|_n/2_|,滿足（kiWk2iWk2i+lkik2i+lk2i

22、kiWk2ikiWk2i且kiWk2i+l(2i+lWn)kiWk2i或kiWk2i+l(2i+lWn)隊列的插入操作是在（）進(jìn)行。隊列的插入操作是在（）進(jìn)行。A.隊首B.隊尾C.隊前D.對后A.隊首B.隊尾C.隊前D.對后一棵具有5層滿二叉樹中節(jié)點總數(shù)為（）。A、31B、32C、33D、快速排序在最壞情況下的時間復(fù)雜度為（）。A.O（lognA.O（logn）B.O（nlogn）廣義表是線性表的推廣，它們之間的區(qū)別在于（）C.0(n)D.0(n2)A.能否使用子表A.能否使用子表C.表的長度能否使用原子項D.是否能為空如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是（）。有向完全圖

23、B.連通圖C.強(qiáng)連通圖如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是（）。有向完全圖B.連通圖C.強(qiáng)連通圖有向無環(huán)圖對n個關(guān)鍵字的序列進(jìn)行快速排序，平均情況下的空間復(fù)雜度為（）A.O(1)C.O(n)B.O（log2A.O(1)C.O(n)B.O（log2n）與線性表相比，串的插入和刪除操作的特點是（D.O(nlog2n)A.通常以串整體作為操作對象B.需要更多的輔助空間算法的時間復(fù)雜度較高涉及移動的元素更多算法的時間復(fù)雜度較高涉及移動的元素更多假設(shè)帶頭結(jié)點的單向循環(huán)鏈表的頭指針為假設(shè)帶頭結(jié)點的單向循環(huán)鏈表的頭指針為head,則該鏈表為空的判定條件是（）。A.head=NULLB.

24、head-nextA.head=NULLB.head-next二二NULLC.head!=NULLD.head-next二二head在單鏈表中，指針在單鏈表中，指針p指向值為x的結(jié)點，能實現(xiàn)“刪除x的后繼”的語句是.A.p=p-A.p=p-next;B.p=p-next-next;C.p-C.p-next=p;D.p-next=p-next-next;一個棧的入棧序列是a,b,c,d,e,一個棧的入棧序列是a,b,c,d,e,則棧的輸出序列不可能是（A.dceabdecbaedcbaabcdeA.dceabdecbaedcbaabcde若進(jìn)棧序列為若進(jìn)棧序列為a,b，c,進(jìn)棧過程中允許出棧，則

25、以下是不可能得到的出棧序列。A.a,b,cb,a,cc,a,bc,b,aA.a,b,cb,a,cc,a,bc,b,a若進(jìn)棧序列為若進(jìn)棧序列為1,2,3,4,進(jìn)棧過程中允許出棧，貝y可能的出棧序列是.A.2,4,1,33,1,4,2A.2,4,1,33,1,4,23,4,1,2D.1,2,3,4設(shè)有一個棧，按A、B、C、D的順序進(jìn)棧，則可能為出棧序列的是()A.DCBAB.CDABC.DBACD.DCAB一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是()A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1一個最多能容納m個元素的順序存儲循環(huán)隊列Q,其頭尾指針分別為fr

26、ont和rear,則判定該隊列為滿的條件是A.(Q.rear+1)%m=Q.frontB.Q.front=Q.rearQ.rear+1=Q.frontD.(Q.front+1)%m=Q.rear設(shè)數(shù)組Datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，貝執(zhí)行出隊操作的語句為().A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD.front=(front+1)%(m+1)假設(shè)以數(shù)組An存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。若設(shè)定尾指針指向隊列中的隊尾元素,頭指針指向隊列中隊頭元素的前一個位置

27、,則當(dāng)前存于隊列中的元素個數(shù)為()A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n若用一個大小為6的一維數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊里中刪除一個元素，再加入兩個元素后，rear和front的值分別是()A.1和A.1和5B.5和1兩個字符串相等的條件是(A.串的長度相等B.C.都是非空串D.如下陳述中正確的是。A.串是一種特殊的線性表C.串中元素只能是字母C.2和4D.4和2)含有相同的字符集串的長度相等且對應(yīng)的字符相同串的長度必須大于零空串就是空格串一棵含18個結(jié)點的

28、二叉樹的高度至少為A.3B.4C.5D.6將一棵有40個結(jié)點的完全二叉樹從上到下,從左到右依次對結(jié)點進(jìn)行編號,根結(jié)點的編號為1,則編號為15的結(jié)點的左孩子的編號為A.16B.30C.31D.32在程序的執(zhí)行過程中,對實現(xiàn)函數(shù)的遞歸調(diào)用應(yīng)該借助于結(jié)構(gòu)A.線性表B.棧C.隊列D.樹具有100個結(jié)點的完全二叉樹的深度為。49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.A.6B.7C.8D.9A.6B.7C.8D.9已知二叉樹的先序遍歷序列為ABDECF，中序遍歷序列為DBEAFC，則后序遍歷序列為ADEBAFCBDEFBCACDEBCFADDEBFCA

29、如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是()A.棧B.隊列C.樹D.圖已知一棵含50個結(jié)點的二叉樹中只有一個葉子結(jié)點，則該樹中度為1的結(jié)點個數(shù)為()A.0B.1C.48D.49具有100個結(jié)點的完全二叉樹，其中含有個度為1的結(jié)點。A.1B.0C.2D.不確定已知二叉樹的先序遍歷序列為ABCD，中序遍歷序列為BCDA,則后序遍歷序列為AABCDBBCDACCDBADDCBA對一棵有100個結(jié)點的完全二叉樹按層序編號，則編號為49的結(jié)點，它的左孩子的編號為()TOC o 1-5 h zA.99B.98C.97D.50有m個葉子結(jié)點的哈夫曼樹，其結(jié)點總數(shù)是(

30、)A.2m-1B.2mC.2m+1D.2(m+1)無向圖的鄰接矩陣是一個。A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣廣義表中元素分為()A.原子兀素B.表兀素C.原子兀素和表兀素D.任意兀素廣義表A=()，(a),(b，(c,d)的長度為()A.2B.3C.4D.5廣義表A：()，(a)，(b，(c，d)的深度為()A.2B.3C.4D.5A.圖中每個頂點的入度C.圖中弧的條數(shù)鄰接矩陣為對稱矩陣的圖是(A.圖中每個頂點的入度C.圖中弧的條數(shù)鄰接矩陣為對稱矩陣的圖是(A.有向圖B.帶權(quán)有向圖在一個具有n個頂點的無向圖中,圖中每個頂點的出度圖中連通分量的數(shù)目)有向圖或無向圖D.無向圖要連通全

31、部頂點至少需要的邊數(shù)為()A.n/2B.nC.n-1D.n+1下面的序列中是大根堆。A.1,2,8,5,3,9,10,49,8,7,6,4,8,2,1A.1,2,8,5,3,9,10,49,8,7,6,4,8,2,11,5,10,6,7,8,9,29,8,7,6,5,4,3,1一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為。A.38，40，46，56，79，84B.40，38，46，79，56，8440，38，46，56，79，84D.40，38，46，84，56，79對關(guān)鍵字序列（5，1，4，3，7，2，8，6）進(jìn)行快速排

32、序時，以第一個元素5為基準(zhǔn)的一次劃分的結(jié)果為（）A（1，2，3，4，5，6，7，8）B（1，4，3，2，5，7，8，6）C（2，1，4，3，5，7，8，6）D（8，7，6，5，4，3，2，1）使用折半查找，線性表必須。A.以順序方式存儲B.以順序方式存儲，且元素已按值排好序C.以鏈?zhǔn)椒绞酱鎯.以鏈?zhǔn)椒绞酱鎯?，且元素已按值排好序已?個元素（34，76，45，18，26，54，92，65），按照依次插入結(jié)點的方法生成一棵二叉排序樹，則該樹的深度為（）A.4B.5C.6D.7若有序表的關(guān)鍵字序列為（b,c,d,e,f,g,q,r,s,t）,則在折半查找關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為

33、（）Af,c,bBf,d,bCg,c,bDg,d,b在對查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于（）A.靜態(tài)查找表B.動態(tài)查找表C.靜態(tài)查找表與動態(tài)查找表D.靜態(tài)查找表或動態(tài)查找表有一個有序表為：（2,5,8,11,15,16,22,24,27,35,50）當(dāng)折半查找值為24的結(jié)點時，經(jīng)過次比較后查找成功。TOC o 1-5 h zA.1B.2C.3D.4有一個有序表為：（21,32,41,45,62,75,77,82,95）,當(dāng)折半查找值為82的結(jié)點時，經(jīng)過次比較后查找成功。A.1B.2C.4D.3下面排序算法的時間復(fù)雜度最小的是。A.直接

34、插入排序B.簡單選擇排序C.冒泡排序D.快速排序以下排序方法中，穩(wěn)定的排序方法是。A.直接插入排序和冒泡排序B.簡單選擇排序和歸并排序C.冒泡排序和快速排序D.堆排序和基數(shù)排序按排序過程中依據(jù)的原則分類，快速排序?qū)儆冢ǎ〢.插入類的排序方法B.選擇類的排序方法C.交換類的排序方法D.歸并類的排序方法在一棵二叉排序樹中，若左子樹不空，左子樹上所有結(jié)點的值均（）根結(jié)點的值A(chǔ).大于B.小于C.不小于D.大于等于）來實現(xiàn)算法的。D.圖）來實現(xiàn)算法的。D.圖）來實現(xiàn)算法的。D.圖A.棧B.隊列C.樹用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時，通常是采用（A.棧B.隊列C.樹從一個順序隊列刪除元素時，首先要（）。7

35、5.76.75.76.77.78.79.80.81.82.83.84.85.86.A.前移一位隊首指針A.前移一位隊首指針后移一位隊首指針取出隊首指針?biāo)肝恢蒙系脑谼.取出隊尾指針?biāo)肝恢蒙系脑卦谝粋€具有n個頂點的無向圖中，要連通所有頂點則至少需要（）條邊。TOC o 1-5 h zA.nB.2nC.n-1D.n+1在有向圖的鄰接表存儲表示中，頂點V在鏈表結(jié)點中出現(xiàn)的次數(shù)是（）。A.頂點V的入度B.頂點V的出度C.頂點V的度D.依附于頂點V的邊的數(shù)目由權(quán)值分別為3,6,7,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A.74B.23C.51D.53設(shè)串sl二DataStruet

36、ureswith“,s2=it，則子串定位函數(shù)index的值為（）。A.15B.16C.17D.18一棵深度為6的二叉樹至多有（）個結(jié)點。A.64B.32C.31D.63A.64B.32C.31D.63將含100個結(jié)點的完全二叉樹從根這一層開始，每層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1,編號為49的結(jié)點X的雙親編號為（）。A.24B.25C.23D.A.24B.25C.23D.無法確定）遍歷的結(jié)果序列相同。D.）遍歷的結(jié)果序列相同。D.層次遍歷A.先序B.中序C.后序鏈表適用于（）查找A.順序B.二分法C.順序，也能二分法D.隨機(jī)折半查找有序表6,15,30,37,65,70,72,89

37、,99,若要查找元素37，需要依次與表中元素進(jìn)行比較。A.65，15，37B.68，30，37C.65，15，30D.65，15，30，3787下列排序方法中，穩(wěn)定的排序方法為（）。A.希爾排序B.堆排序C.快速排序D.直接插入排序當(dāng)利用大小為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則退棧時，用（）語句修改top指針。A.top+;B.top=0;C.top-;D.top=N;在順序表中，只要知道，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A.基地址B.結(jié)點大小C.向量大小D.基地址和結(jié)點大小在一棵二叉樹中，第4層上的結(jié)點數(shù)最多為（）。A.31B.8C.15D.16線性表的順序存儲結(jié)

38、構(gòu)是一種的存儲結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存儲器中的表示是指（）A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素之間的關(guān)系C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)的物理存儲結(jié)構(gòu)下述幾種排序方法中，要求內(nèi)存最大的是（）A.插入排序快速排序C.歸并排序D.選擇排序若長度為n的線性表采用順序存儲結(jié)構(gòu)，則在表中第i個位置（1二i二n+1）插入一個新元素的算法的時間復(fù)雜度為（）A.O（0）B.O（1）C.O（n）D.O（n2）一個棧的輸入序列為ABCDE，則不可能出現(xiàn)的輸出序列是（）A.ABCDEB.EDCBAC.CABEDD.BADCE對序列（22，86，19，49，12，30，65，35，18

39、）進(jìn)行一趟排序后得到的結(jié)果如下：（18，12，19，22，49，30，65，35，86），則可以認(rèn)為使用的排序方法是（）A.選擇排序B.冒泡排序C.快速排序D.插入排序?qū)Χ鏄涞慕Y(jié)點從1開始編號，要求每個結(jié)點的編號大于其左孩子（如果有的話）的編號，而小于其右（孩子如果有的話）的編號，則可以采用（）次序的遍歷實現(xiàn)二叉樹的結(jié)點編號A.先序A.先序B.中序C.后序是一棵滿二叉樹。A.二叉排序樹C.有15個結(jié)點的完全二叉樹層次遍歷B.深度為5有31個結(jié)點的二叉樹哈夫曼（Huffman）樹某二叉樹結(jié)點的中序序列為BDAECF,后序序列為DBEFCA,則該二叉樹對應(yīng)的森林包括（）棵樹A.1B.2C.3D.

40、4A.1B.2C.3D.4下面關(guān)于圖的存儲的敘述中正確的是（）用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)C用鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)三、判斷題：（對的打/,錯的打乂）（乂）1數(shù)據(jù)元素是數(shù)據(jù)處理的最小單位。（/）2數(shù)據(jù)項是數(shù)據(jù)處理的最小單位。（乂）3線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。（/）4順序存儲的線性表可以隨機(jī)訪問，鏈?zhǔn)酱鎯Φ木€性表只能順序訪問。（乂）5在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的

41、兩個元素在物理位置上不一定相鄰。（乂）6.線性表的順序存儲和鏈?zhǔn)酱鎯Χ急仨氄加脙?nèi)存中的連續(xù)存儲單元。（/）7棧和隊列的存儲方式,既可以順序存儲也可以鏈?zhǔn)酱鎯?。?）&棧和隊列都是操作受限制的線性表。（/）9棧的特點是先進(jìn)后出，隊列的特點是先進(jìn)先出。（/）10.空串是任意串的子串。（乂）11.串中任意個字符組成的子序列稱為該串的子串。（乂）12.樹型結(jié)構(gòu)中每個結(jié)點都有一個直接前趨。（乂）13.二叉樹中每個結(jié)點的度最大為2,因此二叉樹是一種特殊的樹。（乂）14.滿二叉樹中存在度為1的結(jié)點。（乂）15完全二叉樹中每個結(jié)點或者沒有孩子或者有2個孩子。（/）16.在任意一棵二叉樹中，葉子結(jié)點的個數(shù)等于度

42、為2結(jié)點的個數(shù)加1。（/）17.由樹轉(zhuǎn)化為二叉樹，其根結(jié)點的右子樹總是空的。（乂）18.最小生成樹是指邊數(shù)最少的生成樹。（/）19.一棵哈夫曼樹有m個葉子結(jié)點，則其結(jié)點總數(shù)為2m-1。（乂）20.樹的先根遍歷序列等同于該樹對應(yīng)的二叉樹中序遍歷序列。（乂）21.“順序查找法”是指在順序表上進(jìn)行查找的方法。（乂）22.快速排序在任何情況下圴可得到最塊的排序效果。（/）23.在有向圖中每個頂點的度等于各頂點的入度與出度之和。（乂）24.二叉排序樹是用來進(jìn)行排序的。（/）25衡量排序算法的兩個主要性能指標(biāo)是執(zhí)行排序算法所需要的時間和執(zhí)行排序算法所需要的附加空間。（/）26.哈夫曼樹是帶權(quán)值的樹，且權(quán)值

43、較大的結(jié)點離樹較近。TOC o 1-5 h z雙鏈表中至多只有一個結(jié)點的后繼指針為空。（/）在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向?qū)嶋H的隊尾元素，隊列為滿的條件是front=rear。（乂）對鏈表進(jìn)行插入和刪除操作時，不必移動結(jié)點。（/）?？梢宰鳛閷崿F(xiàn)程序設(shè)計語言過程調(diào)用時的一種數(shù)據(jù)結(jié)構(gòu)。（/）線性表的邏輯順序與物理順序總是一致的。（乂）對有向圖G,如果從任一頂點出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點，則該圖一定是完全圖。（乂）邊數(shù)很多的稠密圖，適宜用鄰接矩陣表示。（/）向二叉排序樹插入一個新結(jié)點時，新結(jié)點一定成為二叉排序樹的一個葉子結(jié)點。（/）鍵值序

44、列A,C，D，E，F(xiàn)，E，F(xiàn)是一個堆。（/）二路歸并時，被歸并的兩個子序列中的關(guān)鍵字個數(shù)一定要相等。（乂）非空線性表中任意一個數(shù)據(jù)元素都有且僅有一個直接前驅(qū)元素。（乂）每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運算：插入、刪除和搜索。（乂）當(dāng)從一個最小堆中刪除一個元素時，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。（/）空串與由空格組成的串沒有區(qū)別。（乂）單鏈表可以實現(xiàn)隨機(jī)存取。（乂）深度為h的非空二叉樹的第i層最多有2h-1個結(jié)點。（乂）完全二叉樹就是滿二叉樹。（乂）已知一棵二叉樹的前序序列和中序序列可以唯一地構(gòu)造出該二叉樹。（/）非空二叉排序樹的任意一棵子樹也是二

45、叉排序樹。（/）有向圖是一種非線性結(jié)構(gòu)。（/）TOC o 1-5 h z圖的廣度優(yōu)先搜索算法通常采用遞歸算法求解。（/）線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。（/）折半查找方法適用于按值有序的線性鏈表的查找。（乂）圖的深度優(yōu)先搜索是一種典型的回溯搜索的例子，可以通過遞歸算法求解。（/）選擇排序過程中元素之間的比較次數(shù)與原始序列的狀態(tài)無關(guān)。（/）棧是一種線性結(jié)構(gòu)。（/）順序表中所有結(jié)點的類型必須相同。（/）對于一棵具有n個結(jié)點，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為0（n）。（/）遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常不需要用遞歸的算法來實現(xiàn)對它的操作。（乂）用Chi

46、,Ch2表示兩個字符，若0rd(Chl)V0rd(Ch2),則稱ChlVCh2。(/)四、應(yīng)用題：已知二叉樹的先序序列和中序序列分別為ABCDEFG和CBEDAFG，要求：畫出該二叉樹；(2)寫出該二叉樹的后序遍歷序列。已知一棵二叉樹的中根遍歷序列和后根遍歷序列分別為BDCEAFHG和DECBHGFA，要求：畫出該二叉樹；(2)寫出該二叉樹的先序遍歷序列。將下面的樹轉(zhuǎn)換為二叉樹，寫出轉(zhuǎn)換后二叉樹的先序、中序、后序的遍歷序列。RABCDEFGHI若以(4，5，6，7，8)作為葉子結(jié)點的權(quán)值，要求：(1)試構(gòu)造相應(yīng)的哈夫曼樹；計算該哈夫曼樹的帶權(quán)路徑長度；(3)寫出各結(jié)點對應(yīng)的哈夫曼編碼。以數(shù)據(jù)集

47、4，5，6，7，10，12，18為結(jié)點權(quán)值，試構(gòu)成哈夫曼樹，并計算其帶權(quán)路徑長度為。有七個帶權(quán)結(jié)點，其權(quán)值分別為3,7,8,2,6,10,14，要求：(1)試以它們?yōu)槿~子結(jié)點構(gòu)造一棵哈夫曼樹；(2)計算該哈夫曼樹的帶權(quán)路徑長度；(3)寫出各葉子結(jié)點對應(yīng)的哈夫曼編碼。設(shè)一個無向圖為G=(V,E),其中V=v1,v2,v3,v4,v5,v6,v7,v8,E=(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v4,v8),(v5,v8),(v3,v6),(v3,v7),(v6,v7),畫出該無向圖;畫出其鄰接表;根椐鄰接表，寫出從頂點v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列。

48、8設(shè)一個無向圖為G=(V,E),其中V=v1,v2,v3,v4,v5,v6，E=(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v3,v6),(v4,v5),(v5,v6),畫出該無向圖;畫出其鄰接矩陣,根椐鄰接矩陣，寫出從頂點v1出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列。9.對如下無向圖,要求：（1）寫出該圖中每個頂點的度；（2）畫出該圖的鄰接表；（3）根椐鄰接表，分別寫出從頂點A出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列。（1）寫出該圖中每個頂點的度；（2）畫出該圖的鄰接表；（3）根椐鄰接表，分別寫出從頂點A出發(fā)進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索得到的頂點序列。BBCDEF

49、題10圖題12圖10.已知無向圖如上中圖所示，要求：（1）試給出該圖的鄰接矩陣；（2）根據(jù)鄰接矩陣，分別寫出從頂點A出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷序列。11.已知有向圖的鄰接表如下左圖所示，試寫出從頂點A出發(fā)，對該圖進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點序列。ABcDITTai*cnj*LTEz：TitTai12.對于如上右圖所示的有向圖，試給出：（1）鄰接矩陣；（2）鄰接表。13.對如下圖所示的無向圖，試給出：（1）鄰接矩陣；（2）根據(jù)鄰接矩陣，分別寫出從頂點AA1012B1575C6D128E9F6出發(fā)的深度優(yōu)先和廣度優(yōu)先遍歷序列。829869b從空樹起，依次插入關(guān)鍵字（8，12，5，7，

50、9，1，13，10），構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹；（2）畫出從（1）所得樹中插入關(guān)鍵字為6的結(jié)點之后的二叉排序樹。（3）畫出從（2）所得樹中刪除關(guān)鍵字為12的結(jié)點之后的二叉排序樹。按序列（46，88，45，39，70，58，97，23）的輸入順序建立一顆二叉排序樹.（1）畫出該二叉排序樹；（2）在（1）的基礎(chǔ)上插入結(jié)點42后，畫出對應(yīng)的二叉排序樹;（3）在（2）的基礎(chǔ)上刪除結(jié)點88后，畫出對應(yīng)的二叉排序樹。16從空樹起，依次插入關(guān)鍵字37，50，42，18，48，12，56，30，23，構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹；（2）畫出從（1）所得樹中刪除關(guān)鍵字為50的結(jié)點

51、之后的二叉排序樹。從空樹起，依次插入關(guān)鍵字（28，16，20，39，65，32，10），構(gòu)造一棵二叉排序樹。（1）畫出該二叉排序樹；（2）畫出從（1）所得樹中插入關(guān)鍵字為88的結(jié)點之后的二叉排序樹。用直接插入排序算法對數(shù)據(jù)序列（47，33，61，82，72，11，25，57）進(jìn)行升序排序，試寫出每一趟的排序結(jié)果。寫出利用簡單選擇排序方法對一組關(guān)鍵碼為（54，38，96，23，15，72，60）的記錄進(jìn)行升序排序時，每趟排序的結(jié)果。20已知關(guān)鍵碼序列25，23，16，68，94，72，71，73，如果采用堆排序，它是否為堆？如果不是堆，請把其調(diào)整為堆。21.已知一組數(shù)值序列為（50，47，65，33，41，26，71，56），請完成下面的各項操作：（1）采用直接插入排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。（2）采用冒泡排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。（3）采用快速排序法對該組序列作升序排序，并給出每一趟的排序結(jié)果。（4）畫出與該序列對應(yīng)的完全二叉樹；判斷該序列是否為堆