數(shù)據(jù)結(jié)構(gòu)答案

1、. z.數(shù)據(jù)構(gòu)造模擬卷A一、選擇題在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復(fù)雜度為 A 。A. O(n)B. O(n/2)C. O(1)D. O(n2)帶頭結(jié)點的單鏈表first為空的判定條件是： B 。A. first = NULL; B. first-link = NULL;C. first-link = first; D. first != NULL;3. 從邏輯上可以把數(shù)據(jù)構(gòu)造分為 C 兩大類。A動態(tài)構(gòu)造、靜態(tài)構(gòu)造 B順序構(gòu)造、鏈式構(gòu)造C線性構(gòu)造、非線性構(gòu)造 D初等構(gòu)造、構(gòu)造型構(gòu)造在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存實際參數(shù)的值。在傳值參數(shù)情形，需為對應(yīng)形式參數(shù)分

2、配空間，以存放實際參數(shù)的副本；在引用參數(shù)情形，需保存實際參數(shù)的 D ，在被調(diào)用程序中可直接操縱實際參數(shù)。A. 空間B. 副本C. 返回地址D. 地址5. 以下數(shù)據(jù)構(gòu)造中，哪一個是線性構(gòu)造 D 。A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串6. 以下屬于邏輯構(gòu)造的是 C 。A順序表 B. 哈希表 C.有序表 D. 單鏈表對于長度為9的有序順序表，假設(shè)采用折半搜索，在等概率情況下搜索成功的平均搜索長度為C的值除以9。A. 20 B. 18 C. 25 D. 22在有向圖中每個頂點的度等于該頂點的 C 。A. 入度 B. 出度C. 入度與出度之和D. 入度與出度之差在基于排序碼比擬的排序算法中，

3、 C 算法的最壞情況下的時間復(fù)雜度不高于O(nlog2n)。A. 起泡排序B. 希爾排序C. 歸并排序D. 快速排序當?shù)闹递^小時，散列存儲通常比其他存儲方式具有 B 的查找速度。A. 較慢B. 較快C. 一樣 D.不同二、填空題二維數(shù)組是一種非線性構(gòu)造，其中的每一個數(shù)組元素最多有_2_個直接前驅(qū)或直接后繼。將一個n階三對角矩陣A的三條對角線上的元素按行壓縮存放于一個一維數(shù)組B中，A00存放于B0中。對于任意給定數(shù)組元素BK，它應(yīng)是A中第_(K+1)/3_行的元素。鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結(jié)點，只需改變相關(guān)結(jié)點的_指針_域的值。在一個鏈式棧中，假設(shè)棧頂指針等于NULL則為_空棧_。主

4、程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的_返回_地址。在一棵樹中，_葉子_結(jié)點沒有后繼結(jié)點。一棵樹的廣義表表示為a (b (c, d (e, f), g (h) ), i (j, k (*, y) ) )，結(jié)點f的層數(shù)為_3_。假定根結(jié)點的層數(shù)為0。在一棵AVL樹高度平衡的二叉搜索樹中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過_1_。n (n0) 個頂點的無向圖最多有_ n(n-1)/2_條邊，最少有_0_條邊。在索引存儲中，假設(shè)一個索引項對應(yīng)數(shù)據(jù)對象表中的一個表項記錄，則稱此索引為_稠密_索引，假設(shè)對應(yīng)數(shù)據(jù)對象表中的假設(shè)

5、干個表項，則稱此索引為_稀疏_索引。三、判斷題數(shù)組是一種復(fù)雜的數(shù)據(jù)構(gòu)造，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的(對)鏈式存儲在插入和刪除時需要保持物理存儲空間的順序分配，不需要保持數(shù)據(jù)元素之間的邏輯順序(錯)在用循環(huán)單鏈表表示的鏈式隊列中，可以不設(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針(對)通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高(錯)一個廣義表的表尾總是一個廣義表(對)當從一個小根堆最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到適宜位置為止(對)對于一棵具有n個結(jié)點，其高度為h的二叉樹，進展任一種次序遍歷的時間復(fù)雜度為O(h)( 錯)

6、存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)(錯)直接選擇排序是一種穩(wěn)定的排序方法(錯)閉散列法通常比開散列法時間效率更高(錯)四、運算題設(shè)有一個1010的對稱矩陣A，將其下三角局部按行存放在一個一維數(shù)組B中，A00存放于B0中，則A85存放于B中什么位置。解：根據(jù)題意，矩陣A中當元素下標I與J滿足IJ時，任意元素AIJ在一維數(shù)組B中的存放位置為I * (I + 1) / 2 + J，因此，A85在數(shù)組B中位置為8* (8+1) / 2 + 5 = 41。這是一個統(tǒng)計單鏈表中結(jié)點的值等于給定值*的結(jié)點數(shù)的算法，其中while循環(huán)有錯，請重新編寫出正確的whil

7、e循環(huán)。int count (ListNode * Ha, ElemType * ) / Ha為不帶頭結(jié)點的單鏈表的頭指針int n = 0;while ( Ha-link != NULL ) Ha = Ha-link;if ( Ha-data = * ) n+;return n;解：while ( Ha != NULL ) if ( Ha-data = * ) n+;Ha = Ha-link;一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：解：后序序

8、列：C, B, F, E, I, J, H, G, D, A一個有序表 (15,26,34,39,45,56,58,63,74,76,83,94) 順序存儲于一維數(shù)組a12中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34, 56, 58, 63, 94時的比擬次數(shù)。34 56 58 63 9434 56 58 63 94 元素值 比擬次數(shù)34 56 58 63 94034 56 58 63 9402 1 3 4 4元素值 比擬次數(shù) 設(shè)散列表為HT17, 待插入關(guān)鍵碼序列為Jan, Feb, Mar, Apr, May,June, July, Aug, Sep, Oct, Nov, Dec，散

9、列函數(shù)為H (key) = i 2，其中，i是關(guān)鍵碼第一個字母在字母表中的序號?，F(xiàn)采用線性探查法解決沖突。字母ABCDEFGHIJKLM序號12345678910111213字母NOPQRSTUVW*YZ序號14151617181920212223242526試畫出相應(yīng)的散列表；H(Jan) = 102 = 5，成功.H(Feb) = 62 = 3，成功.H(Mar) = 132 = 6，成功.H(Apr) = 12 = 0，成功.H(May) = 132 = 6，= 7，成功，H(June) = 102 = 5，= 6，= 7，=8，成功.H(July) = 102 = 5，= 6，= 7，

10、= 8，= 9，成功.H(Aug) = 12 = 0，= 1，成功.H(Sep) = 192 = 9，= 10，成功.H(Oct) = 152 = 7，= 8，= 9，= 10，= 11，成功.H(Nov) = 142 = 7，= 8，= 9，= 10，= 11，= 12，成功.H(Dec) = 42 = 2，成功.相應(yīng)的散列表：012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2) (1)(1) (1) (1) (2) (4)(5)(2) (5)(6)計算等概率下搜索成功的平均搜索長度；1/12 * (1 + 2 + 1

11、+ 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12五、算法設(shè)計題二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:struct BTreeNode chardata;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點。 int BTreeCount ( BinTreeNode* BT );解：int BTreeCo

12、unt(BinTreeNode* BT)if(BT=NULL)return 0; /2分else return BTreeCount(BT-leftChild)+BTreeCount(BT-rightChild)+1; /4分數(shù)據(jù)構(gòu)造模擬卷 B一、單項選擇題1以下與數(shù)據(jù)的存儲構(gòu)造無關(guān)的術(shù)語是 C 。A循環(huán)隊列 B. 鏈表 C. 哈希表 D. 棧2以下數(shù)據(jù)構(gòu)造中，哪一個是線性構(gòu)造 D 。A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串3以下那一個術(shù)語與數(shù)據(jù)的存儲構(gòu)造無關(guān)？ B 。A棧 B. 哈希表 C. 線索樹 D. 雙向鏈表4在下面的程序段中，對*的賦值語句的頻度為 C 。FOR i:=1 T

13、O n DO FOR j:=1 TO n DO *:=*+1;A O(2n) BO(n) CO(n2) DO(log2n)5.下面關(guān)于線性表的表達中，錯誤的選項是哪一個 B 。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進展插入和刪除操作。C線性表采用存儲，不必占用一片連續(xù)的存儲單元。D線性表采用存儲，便于插入和刪除操作。6線性表是具有n個 C 的有限序列n0。A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項 E信息項7.假設(shè)*線性表最常用的操作是存取任一指定序號的元素和在最后進展插入和刪除運算，則利用 A 存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表

14、D單循環(huán)鏈表8.*線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用 D 存儲方式最節(jié)省運算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表9.下面給出的四種排序法中( D )排序法是不穩(wěn)定性排序法。 A. 插入 B. 冒泡 C. 二路歸并 D. 堆積10. 以下排序算法中，其中 D 是穩(wěn)定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接選擇排序，歸并排序 D. 歸并排序，冒泡排序11.一算術(shù)表達式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( D )。A-A+B*C/DE B. -A+B*C

15、D/E C-+*ABC/DE D. -+A*BC/DE12.算術(shù)表達式a+b*c+d/e轉(zhuǎn)為后綴表達式后為 B 。Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+EEFDGAB/+*-C*二、填空題，在橫線處填寫適宜內(nèi)容1. 數(shù)據(jù)構(gòu)造的存儲構(gòu)造包括順序、_、索引和散列等四種。2. 在程序運行過程中可以擴大的數(shù)組是_動態(tài)_分配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。3. 在鏈表中進展插入和刪除操作的效率比在順序存儲構(gòu)造中進展一樣操作的效率高。4. 棧是一種限定在表的一端進展插入和刪除的線性表，又被稱為_后出先進_表。5. 如果一個對象局部地包含自己，或自己定義

16、自己，則稱這個對象是_遞歸_的對象。6. 一棵樹的廣義表表示為a(b(c,d(e,f),g(h),i(j,k(*,y)，結(jié)點f的層數(shù)為_3_。假定樹根結(jié)點的層數(shù)為0。7. 一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點肯定沒有_右_子女。8. 向一棵二叉搜索樹中插入一個元素時，假設(shè)元素的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的_左子樹_上。 9. 設(shè)圖G=(V,E)，V=1,2,3,4, E=,，從頂點1出發(fā)，對圖G進展廣度優(yōu)先搜索的序列有_2_種。10. 每次直接或通過基準元素間接比擬兩個元素，假設(shè)出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做_交換_排序。11. 快

17、速排序在平均情況下的空間復(fù)雜度為_ O(log2n) _。12. 假設(shè)對長度n=10000的線性表進展二級索引存儲，每級索引表中的索引項是下一級20個表項的索引，則一級索引表的長度為_500_。三、判斷題1.在順序表中進展順序搜索時，假設(shè)各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長度 對 2. 在二叉搜索樹中，假設(shè)各結(jié)點的搜索概率不等，使得搜索概率越小的結(jié)點離樹根越近，則得到的是最優(yōu)二叉搜索樹錯 3. 對于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動都能使整個工程提前完成 錯 4. 直接選擇排序是一種穩(wěn)定的排序方法錯 5. 閉散列法通常比開散列法時間效率更高 錯 6.數(shù)

18、據(jù)的邏輯構(gòu)造是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的對 7.順序表和一維數(shù)組一樣，都可以按下標隨機或直接訪問對 8.在一個順序存儲的循環(huán)隊列中, 隊頭指針指向隊頭元素的后一個位置 錯 9.用非遞歸方法實現(xiàn)遞歸算法時一定要使用遞歸工作棧 錯 10.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進展中序遍歷和后序遍歷，則具有一樣的結(jié)果 對 四、運算題1. 設(shè)有一個二維數(shù)組A1020，按行存放于一個連續(xù)的存儲空間中，A00的存儲地址是200，每個數(shù)組元素占1個存儲字，則A62的存儲字地址是多少。 A62的存儲字地址：322答案說明： 按行存儲時，計算Aij地址的公式為 L

19、OC(i,j)=LOC(0,0)+(i*n+j)*d 其中首地址LOC(0,0)=200, 每個數(shù)組元素的存儲占用數(shù)d=1, 二維數(shù)組的列數(shù)n=20，根據(jù)題意，元素A62的存儲地址為 LOC(6,2)=200+(6*20+2)*1=3222. 一棵二叉樹的中序和后序序列如下，求該二叉樹的高度假定空樹的高度為-1和度為2、度為1及度為0的結(jié)點個數(shù)。 中序序列：c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a求解一下問題：高度： 4 度為2的結(jié)點數(shù)：3度為1的結(jié)點數(shù)： 3 度為0的結(jié)點數(shù)：43. 假定一組記錄為(36,75,83,54,12,67,60,40)

20、，將按次序把每個結(jié)點插入到初始為空的一棵AVL樹中，請答復(fù)在插入時需進展左單旋轉(zhuǎn)、右單旋轉(zhuǎn)、先左后右雙旋轉(zhuǎn)、先右后左雙旋轉(zhuǎn)，不調(diào)整的結(jié)點數(shù)各是多少？左單旋轉(zhuǎn)結(jié)點個數(shù)： 1 右單旋轉(zhuǎn)結(jié)點個數(shù)：0先左后右雙旋轉(zhuǎn)結(jié)點個數(shù)： 1 先右后左雙旋轉(zhuǎn)結(jié)點個數(shù)：0不調(diào)整結(jié)點個數(shù)：64. 一個帶權(quán)圖的頂點集V和邊集G分別為： V=0,1,2,3,4,5,6; E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18, (4,5)6,(4,6)6,(5,6)12; 試根據(jù)迪克斯特拉(Dijkstra)算法求出從頂點0到其余各頂點的最短路徑，在下

21、面填寫對應(yīng)的路徑長度。 頂點： 0 1 2 3 4 5 6 0161014252131 路徑長度：5. 一個數(shù)據(jù)表為36,25,25*,62,40,53，請寫出在進展快速排序的過程中每次劃分后數(shù)據(jù)表的變化。(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53 (2) 25* 25 36 53 40 62 (3) 25* 25 36 40 53 62 五、算法設(shè)計題1設(shè)有一個表頭為first的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點按逆序。解答1 template void List : : Tnerse() if (first= NULL

22、)return ;ListNode * p=firstlink ; , *pr =NULL ; While (p !=NULL ) Firstlink =pr ;Pr =first ;first =p ;p =plink;first -link =pr ;解答2 template void List : : Tnerse() ListNode * p , *head = new ListNode ( ) ;While (first ! = NULL ) P=first ;first = firstlink;plink =headlink ; headlink =p;first = headli

23、nk ; delete head ;數(shù)據(jù)構(gòu)造模擬卷 C一、單項選擇題1數(shù)據(jù)構(gòu)造是D。A一種數(shù)據(jù)類型B數(shù)據(jù)的存儲構(gòu)造C一組性質(zhì)一樣的數(shù)據(jù)元素的集合D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2算法分析的目的是B。A區(qū)分數(shù)據(jù)構(gòu)造的合理性B評價算法的效率C研究算法中輸入與輸出的關(guān)系D鑒別算法的可讀性3在線性表的以下運算中，不改變數(shù)據(jù)元素之間構(gòu)造關(guān)系的運算是D。A插入B刪除C排序D定位4假設(shè)進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進展，則可能出現(xiàn)的出棧序列為B。A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，15設(shè)串sl=Data Str

24、uctures with Java,s2=it，則子串定位函數(shù)inde*(s1,s2)的值為D。A15B16C17D186二維數(shù)組A89按行優(yōu)先順序存儲，假設(shè)數(shù)組元素A23的存儲地址為1087，A47的存儲地址為1153，則數(shù)組元素A67的存儲地址為A。A1207B1209C1211D12137在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)構(gòu)造是A。A隊列B棧C線性表D有序表8在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系B。A不一定一樣B都一樣C都不一樣D互為逆序9假設(shè)采用孩子兄弟鏈表作為樹的存儲構(gòu)造，則樹的后序遍歷應(yīng)采用二叉樹的C。A層次遍歷算法B前序遍歷算法C中序遍歷算

25、法D后序遍歷算法10假設(shè)用鄰接矩陣表示一個有向圖，則其中每一列包含的1的個數(shù)為A。A圖中每個頂點的入度B圖中每個頂點的出度C圖中弧的條數(shù)D圖中連通分量的數(shù)目11圖的鄰接矩陣表示法適用于表示C。A無向圖B有向圖C稠密圖D稀疏圖12在對n個關(guān)鍵字進展直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進展第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為D。AiBi+1Cn-iDn-i+1二、填空題1棧是_特殊_的線性表，其運算遵循_后進先出_的原則。2_棧_是限定僅在表尾進展插入或刪除操作的線性表。3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3，1，2_。4二叉樹由_根結(jié)點、

26、左子樹、右子樹_三個根本單元組成。5在二叉樹中，指針p所指結(jié)點為葉子結(jié)點的條件是P-Lchild=NULL & P-Rchild=NULL_。6具有256個結(jié)點的完全二叉樹的深度為_9_。7一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有_12_個葉子結(jié)點。8假設(shè)不考慮基數(shù)排序，則在排序過程中，主要進展的兩種根本操作是關(guān)鍵字的_比擬_和記錄的_移動_。9.分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是_冒泡排序_算法，最費時間的是_快速排序_算法。10不受待排序初始序列的影響，時間復(fù)雜度為O(N2)的排序算法是_選擇排序_，在排序算法的最后一趟開場之前，所有元素都可能不在其最終位置上的排序算法是_歸并排序_。三、解答題1*廣義表的表頭和表尾均為a,(b,c)，畫出該廣義表的圖形表示。2二叉樹的先序序列和中序