復(fù)習(xí)(數(shù)據(jù)結(jié)構(gòu)導(dǎo)論)

1、數(shù)據(jù)結(jié)構(gòu)導(dǎo)論復(fù)習(xí)資料課程代碼：02142一、單項選擇題1一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1=inext = p； p- next = s； Bs- next = p-next； p- next = s；Cs- next = p- next； p = s； D p- next = s； s- next = p；5設(shè)帶頭結(jié)點的單循環(huán)鏈表的頭指針為head，則判斷該鏈表是否為空的條件是Ahead-next=headBhead-next=NULLChead!=NULLDhead=NULL6一個隊列的輸入序列是A，B，C，D，則該隊列的輸出序列是AA，B，C，DBB，C

2、，D，ACD，C，B，ADC，D，B，A7以行序為主序的二維數(shù)組a35中，第一個元素a00的存儲地址是100，每個元素占2個存儲單元，則a12的存儲地址是A100 B108 C114 D1168二叉樹的中序遍歷序列中，結(jié)點P排在結(jié)點Q之前的條件是A在二叉樹中P在Q的左邊 B在二叉樹中P在Q的右邊 C在二叉樹中P是Q的祖先 D在二叉樹中P是Q的子孫9有10個頂點的無向完全圖的邊數(shù)是A11 B45 C55 D9010在帶權(quán)有向圖中求兩個結(jié)點之間的最短路徑可以采用的算法是A迪杰斯特拉（Dijkstra）算法B克魯斯卡爾（Kruskal）算法C普里姆（Prim）算法 D深度優(yōu)先搜索（DFS）算法11利

3、用雙向鏈表作線性表的存儲結(jié)構(gòu)的優(yōu)點是A便于單向進(jìn)行插入和刪除的操作B便于雙向進(jìn)行插入和刪除的操作C節(jié)省空間D便于銷毀結(jié)構(gòu)釋放空間12在閉散列表中，散列到同一個地址而引起的“堆積”問題是 引起的。A同義詞之間發(fā)生沖突 B非同義詞之間發(fā)生沖突C同義詞之間或非同義詞之間發(fā)生沖突 D散列表“溢出”13假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為Afront+1=rearBrear+1=frontCfront=0Dfront=rear1410階上三角矩陣壓縮存儲時需存儲的元素個數(shù)為A11 B56 C100 D10115深度為k（k1）的二叉樹，結(jié)點數(shù)最多有A2

4、k 個 B(2k -1)個 C2k-1個 D(2k+1)個16具有12個結(jié)點的二叉樹的二叉鏈表存儲結(jié)構(gòu)中，空鏈域NULL的個數(shù)為A11 B13 C23 D2517順序存儲的表格中有60000個元素，已按關(guān)鍵字值升序排列，假定對每個元素進(jìn)行查找的概率是相同的，且每個元素的關(guān)鍵字值不相同。用順序查找法查找時，平均比較次數(shù)約為A20000 B30000 C40000 D6000018外存儲器的主要特點是A容量小和存取速度低 B容量大和存取速度低C容量大和存取速度高 D容量小和存取速度高19以下關(guān)于廣義表的敘述中,正確的是A廣義表是由0個或多個單元素或子表構(gòu)成的有限序列B 廣義表至少有一個元素是子表C

5、廣義表不能遞歸定義D廣義表不能為空表20樹形結(jié)構(gòu)中，度為0的結(jié)點稱為A樹根 B葉子C路徑 D二叉樹21已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=，,，,，則圖G的拓?fù)湫蛄惺茿V1,V3,V4,V6,V2,V5,V7BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7DV1,V2,V5,V3,V4,V6,V722有關(guān)圖中路徑的定義，表述正確的是A路徑是頂點和相鄰頂點偶對構(gòu)成的邊所形成的序列B路徑是不同頂點所形成的序列C路徑是不同邊所形成的序列D路徑是不同頂點和不同邊所形成的集合23組成數(shù)據(jù)的基本單位是A數(shù)據(jù)項 B數(shù)據(jù)類型C數(shù)據(jù)

6、元素 D數(shù)據(jù)變量24與串的邏輯結(jié)構(gòu)不同的數(shù)據(jù)結(jié)構(gòu)是A線性表 B棧C隊列 D樹25設(shè)單鏈表中指針p指向結(jié)點A，若要刪除A的直接后繼，則所需修改指針的操作為Ap-next=p-next-nextBp=p-nextCp=p-next-nextDp-next=p26設(shè)字符串S1=ABCDEFG，S2=PQRST，則運算S=CONCAT(SUBSTR(S1,2,LENGTH(S2),SUBSTR(S1,LENGTH(S2),2)后S的結(jié)果為ABCQR BBCDEFCBCDEFG DBCDEFEF27在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并且A的左孩子的平衡因子為-1，右孩子的

7、平衡因子為0，則使其平衡的調(diào)整方法為ALL型 BLR型CRL型 DRR型28排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是哪種排序方法的基本思想？A堆排序 B直接插入排序 C快速排序 D冒泡排序29下面關(guān)于串的敘述中， 是不正確的。A串是字符的有限序列B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?0一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是Aedcba B decba Cdceab DAbcde31有向圖中，所有頂點入度和是所有頂點出度和的 倍。A0.5 B1 C 2 D432在一個單鏈表HL

8、中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行Aq-next=p-next; p-next=q;Bp-next=q-next; q=p;Cp-next=p-next; q-next=q;Dp-next=q-next; q-nxet=p;33下列描述中正確的是A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)結(jié)構(gòu)是具有結(jié)構(gòu)的數(shù)據(jù)對象C數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合D算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時兩者是通用的34歸并排序的時間復(fù)雜度是AO（n2） BO（nlog2n） CO（n） DO（log2n）35順序存儲的表中有90000個元素，已按關(guān)鍵字值升序排列

9、，假設(shè)對每個元素進(jìn)行查找的概率相同，且每個元素的關(guān)鍵字值皆不相同，用順序查找法查找時，需平均比較的次數(shù)為A25000 B30000 C45000 D9000036散列文件是一種A順序文件 B索引文件 C鏈接文件 D計算尋址文件37常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是A棧 B隊列 C鏈表 D數(shù)組38二維數(shù)組Anm以列優(yōu)先順序存儲，數(shù)組A中每個元素占用1個字節(jié)，A11為首元素，其地址為0，則元素Aij的地址為A（i-1）m+(j-1)B(j-1)n+(i-1)C(j-1)n+iDjn+i39序列（21,19,37,5,2）經(jīng)冒泡排序法由小到大排序，在第一次執(zhí)行交換后所得結(jié)果為A(19，21，37，5，2)B

10、(21，19，5，37，2)C(21，19，37，2，5)D(2，21，19，37，5)40數(shù)據(jù)在計算機存儲器內(nèi)表示時，根據(jù)結(jié)點的關(guān)鍵字直接計算出該結(jié)點的存儲地址，這種方法稱為A索引存儲方法B順序存儲方法C鏈?zhǔn)酱鎯Ψ椒―散列存儲方法41在單鏈表中，存儲每個結(jié)點有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結(jié)點的A直接前趨 B直接后繼 C開始結(jié)點 D終端結(jié)點42一整數(shù)序列26，59，77，31，51，11，19，42，以二路歸并排序從小到大排序，第一階段的歸并結(jié)果為A31，51，11，42，26，77，59，19B26，59，31，77，11，51，19，42C11，19，26，31，42

11、，59，51，77D26，11，19，31，51，59，77，4243某二叉樹的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為Aacbed Bbecab Cdeabc Dcedba44在一個圖中，所有頂點的度數(shù)之和與圖的邊數(shù)的比是A12 B11 C21 D4145含有n個結(jié)點的二叉樹用二叉鏈表表示時，空指針域個數(shù)為An-1 Bn Cn+1 Dn+2參考答案：1-5 BCCBA 6-10 ACABA 11-15 BADBB 16-20 BBBAB 21-25 AACDA26-30 DBDBC 31-35 BDCBC 36-40 DABAD 41-45 BBDCC 二、填空題

12、46有個10階矩陣A，采用行序優(yōu)先存儲，每個元素占用1個字節(jié)的存儲空間，A00的地址為1，則A85的地址為： 。47廣義表(a,(a,b),d,e,(i,j),k)的長度是 。48若待散列的序列為(18,25,63,50,42,32,9)，散列函數(shù)為H(key)=key MOD 9，與18發(fā)生沖突的元素有 個。49將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為 。50常用的存儲表示方法有順序存儲和鏈?zhǔn)酱鎯?，其?存儲表示方法插入和刪除數(shù)據(jù)元素方便。51棧的特點是 。52所有存儲結(jié)點存放在一個連續(xù)的存儲區(qū)里，利

13、用結(jié)點在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。這種存儲方式是 。 53單鏈表中指針p指向結(jié)點A，若要刪除A之后的結(jié)點（存在且不釋放存儲空間），則需要修改指針的操作為p-next= 。54在帶有頭結(jié)點的單鏈表head中，首結(jié)點的指針為 。55在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為 。56C程序中，將對稱矩陣Ann的下三角元素壓縮存儲到n(n+1)/2個元素的一維數(shù)組M中，設(shè)aij（ij）存放在數(shù)組Mk中，則k的值（用i,j表示）為 。57具有64個結(jié)點的完全二叉樹的深度為 。58某二叉樹的先序遍歷序列為AJKLMNO，中序遍歷序列為JLKANMO，則根結(jié)點A的右子樹中的結(jié)點個數(shù)為 。59

14、在順序查找、二分查找、散列查找和索引順序查找四種查找方法中，平均查找長度與元素個數(shù)沒有關(guān)系的查找方法是 。60堆排序算法的時間復(fù)雜度為 。61如果要將序列60，18，28，69，99，75，78建成堆，則只需把60與 相互交換。62數(shù)據(jù)的不可分割的最小標(biāo)識單位是 ，它通常不具有完整確定的實際意義，或不被當(dāng)作一個整體對待。63運算分為加工型運算和引用型運算，讀取操作是 運算。64帶有頭結(jié)點的單向循環(huán)鏈表L（L為頭指針）中，指針p所指結(jié)點為尾結(jié)點的條件是 。65在雙鏈表中，前趨指針和后繼指針分別為prior和next。若使指針p往后移動兩個結(jié)點，則需執(zhí)行語句 。66元素s1，s2，s3，s4，s5

15、，s6依次進(jìn)入順序棧S，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為 。67在一棵樹中， 結(jié)點沒有雙親。68邊稀疏的無向圖采用 存儲較省空間。69要將序列51，18，23，68，94，70，73建成堆，則只需把18與 相互交換。70一棵具有n個結(jié)點的二叉樹，采用二叉鏈表存儲，則二叉鏈表中指向孩子結(jié)點的指針有 個。71若連通圖G的頂點個數(shù)為n，則圖G的生成樹的邊數(shù)為 。72一個具有n個頂點的無向圖的邊數(shù)最多為 。73中根遍歷二叉排序樹所得到的結(jié)點訪問序列是鍵值的 序列。74冒泡排序的平均時間復(fù)雜度為 。75將序列(60，20，23，68，94，70，73)建成

16、堆，則只需把20與 互相交換。76向一個長度為n的順序表中第i（1in）個元素之前插入一個元素時，需向后移動_ _ 個元素。77在循環(huán)雙鏈表中，刪除最后一個結(jié)點，其算法的時間復(fù)雜度為 。78隊列的插入操作在隊列的 部分進(jìn)行。79一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素為 。80一個10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲下三角，a00為第一個元素，其存儲地址為1，每個元素占有1個存儲地址空間，則a85的地址為 。81設(shè)字符串S=IAMASTUDENT（其中表示空格字符），則S的長度為_ 。82在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點是 結(jié)點。83在無向圖中，如果從頂點v

17、到頂點v有路徑，則稱v和v是 。84無向完全圖G采用 存儲結(jié)構(gòu)較省空間。參考答案：46. 86 47.5 48.249. 98 50.鏈?zhǔn)?51.先進(jìn)后出52. 順序存儲方式 53. p-next-next54. head-next55. 棧頂56.（i+1）i/2+j57.758. 359.散列查找60.O（nlog2n）61. 1862.數(shù)據(jù)項63.引用型64. p-next= =L65. p= p-next-next66.367. 根68.鄰接表69.5170.n-171.n-172. n(n-1)/273.遞增74. O（n2）75.6076. n-i+177. O（1）78. 隊尾（

18、或尾部）79.n-i-180.4281.1482.葉子83.連通84.鄰接矩陣三、應(yīng)用題85將下圖所示的一棵樹轉(zhuǎn)換為對應(yīng)的二叉樹。題1圖86將下圖所示的一棵二叉樹轉(zhuǎn)換成對應(yīng)的森林。87寫出下圖的鄰接矩陣和每個頂點的入度與出度。88用冒泡排序法對數(shù)據(jù)序列（55，38，65，97，76，138，27，49）進(jìn)行排序，寫出排序過程中的各趟結(jié)果。89如下圖所示，在棧的輸入端元素的輸入順序為A，B，C，D，進(jìn)棧過程中可以退棧，寫出在棧的輸出端以A開頭和以B開頭的所有輸出序列。90一棵二叉樹如下圖所示，寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。91將下圖所示的一棵二叉樹轉(zhuǎn)換成森林。92對于有

19、向無環(huán)圖： 對于下圖，寫出它的4個不同的拓?fù)渑判蛐蛄小?3稀疏矩陣A如下，寫出矩陣A的三元組表。94一棵二叉樹的前根遍歷序列為ABCDEFG，中根遍歷序列為CBDAEGF，試構(gòu)造出該二叉樹。95下述矩陣表示一個無向連通網(wǎng)，試畫出它所表示的連通網(wǎng)。96給定表（80，90，50，70，75，60，40，100），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r為空的二叉排序樹，畫出插入完成后的二叉排序樹。97試寫出一組鍵值（46，58，15，45，90，18，10，62）應(yīng)用直接插入排序算法從小到大排序后各趟的結(jié)果。98在棧的輸入端元素的輸入順序為1，2，3，4，5，6，進(jìn)棧過程中可以退棧，則退棧時能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫出進(jìn)棧、退棧過程，若不能，簡述理由。（用push（x）表示x進(jìn)棧，pop(x)表示x退棧）99如下圖所示無向圖，（1）寫出其鄰接矩陣；（2）寫出三種以頂點A為起點的深度優(yōu)先搜索頂點序列。參考答案：85答：86答：87答：88答：89答：ABCD,ABDC,ACBD,ACDB,ADCB,BA