數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案(12級)-wenkub.com
2025-06-19 14:40 本頁面
【正文】 { y= Out_Queue(q)；x=Out_Queue (q)；In_Queue(q，x)；x= Out_Queue (q)。 In_Queue(q, ’r’)。Init_Queue(q)。a；{x=pops。 (1) for(i＝1；i＝n；i++) for(j＝1；j＝n；j++) s++； (2) for(i＝1；i＝n；i++) for(j＝i；j＝n；j++)s++；(3) for(i＝1；i＝n；i++) for(j＝1；j＝i；j++) s++；(4) i＝1； k＝0；while(i＝n1){k+＝10*i；i++；}(5) for (i＝1；i＝n；i++) for (j＝1；j＝i ；j++) for (k＝1；k＝j(luò)；k++) x=x+1；(1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n1) (5) Ο(n3)2. 寫出下列程序段的運行結(jié)果(棧中的元素類型是char)：main( ){如果整個排序過程在內(nèi)存中進行，則排序叫內(nèi)部排序。一個稱為基本表，另一個稱為溢出表。答：此法要求設(shè)立多個散列函數(shù)Hi，i=1，…，k。比如散列查找的時間性能很優(yōu)越，但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。 (2)若它的右子樹不空，則右子樹上所有結(jié)點的鍵值均大于它根結(jié)點鍵值。 V1 V3 V5 V4 V2。答：哈夫曼樹為:在上述哈夫曼樹的每個左分支上標以0，右分支上標以1，并設(shè)這8個字母分別為A、B、C、D、E、F、G和H，則它們的哈夫曼樹為分別為:A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：000116. 畫出無向圖G1的鄰接矩陣和鄰接表示意圖，并寫出每個頂點的度。12. 已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試畫出這棵二叉樹。 (1) 先序序列與中序序列相同。串變量和串常量:串常量在程序的執(zhí)行過程中只能引用不能改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值的。6. 設(shè)s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。 CDBA。 BCDA。 ADCB。答：可能序列有14種：ABCD。3. 簡述棧和隊列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點和不同點。答：一般線性表使用數(shù)組來表示的。數(shù)據(jù)存儲結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲方式或者數(shù)據(jù)元素的物理關(guān)系。數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計算機程序加工和處理的對象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。( )29. 在索引順序文件中插入新的記錄時，必須復(fù)制整個文件。( √ )25. 對于n個記錄的集合進行快速排序，所需要的平均時間是O(nlog2 n)。( √ )21. m階B樹每一個結(jié)點的子樹個數(shù)都小于或等于m。( √ )17. 有回路的圖不能進行拓撲排序。( )13. 若有一個結(jié)點是某二叉樹子樹的中序遍歷序列中的最后一個結(jié)點，則它必是該子 樹的前序遍歷序列中的最后一個結(jié)點。 ( √ )9．使用三元組表示稀疏矩陣的元素，有時并不能節(jié)省存儲時間。( )5．在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結(jié)點查找任何一個元素。(每小題1分，共10分)( )1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。(50) 二路歸并排序的時間復(fù)雜度是___ O(nlog2n)______。(47) 堆排序是不穩(wěn)定，空間復(fù)雜度為 ____ O(1)_____。(43) 在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為___ O(log2n)_____，整個堆排序過程的時間復(fù)雜度為____ O(nlog2n)____。(39) 在分塊查找中首先查找 _____索引________，然后再查找相應(yīng)的______塊_________。(35) 散列表中解決沖突的兩種方法是____開放地址法_________和____鏈地址法_________。(31) 在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定_____小于______該結(jié)點的值，右子樹上所有結(jié)點的值一定____大于_______該結(jié)點的值。(27) 在圖G的鄰接表表示中，每個頂點鄰接表中所含的結(jié)點數(shù)，對于無向圖來說等于該 頂點的 ______度數(shù)______，對于有向圖來說等于該頂點的______出度數(shù)______。(23) 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為________模式匹配________。(19) s=” I am a man” 長度為____10_______(16) 鏈式存儲結(jié)構(gòu)中的結(jié)點包含______數(shù)據(jù)__________域和_____指針__________域。(12) 線性表的存儲結(jié)構(gòu)有_________順序存儲和鏈式存儲____________________。(8) 對算法從時間和空間兩方面進行度量，分別稱為 空間復(fù)雜度和時間復(fù)雜度 分析。(6) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指 數(shù)據(jù)元素間的邏輯關(guān)系 ，數(shù)據(jù)的存儲結(jié)構(gòu)是指 數(shù)據(jù)元素存儲方式或者數(shù)據(jù)元素的物理關(guān)系 。(2) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 結(jié)構(gòu)和 物理結(jié)構(gòu) 結(jié)構(gòu)。A. 快速排序 B． 堆排序C． 歸并排序 D． 直接插入排序(77) 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是___ B _______。 A. 2，3，5，8，6 B. 3，2，5，8，6 C. 3，2，5，6，8 D. 2，3，6，5，8(73) 下列排序方法中，哪一種方法的比較次數(shù)與紀錄的初始排列狀態(tài)無關(guān)___ D _____。A. 起泡排序 B. 直接插入排序 C. 二路歸并排序 D. 快速排序(69) 一組記錄為{46，79，56，38，84，40}，則采用冒泡排序法按升序排列時第一趟排序結(jié)果是___ B _____ 。A．最大概率 B．最小概率 C．同等概率 D．平均概率(65) 下述排序算法中，穩(wěn)定的是___ B _____。 B. 平方取中法 C. 二分法 D. 開放地址法(61) 當(dāng)α的值較小時，散列存儲通常比其他存儲方式具有_____ B ______的查找速度。A. 以順序方式存儲 B. 以鏈接方式存儲C. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列D. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列(57) 設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為___ B _____。A. n1 B. n C. n+1 D. n*(n1)/2(53) 在無向圖G的鄰接矩陣A中，若A[i,j]等于1，則A[j,i]等于____C ____。 A. 23 B. 37 C. 44 D. 46(49) 在樹中除根結(jié)點外，其余結(jié)點分成m (m≥0)個____A ____的集合T1,T2,T3...Tm,每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點(1≤i≤m)。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉樹中第五層上的結(jié)點數(shù)最多為____C____。D. 15A. “STRUCTURE” A. BCDEF____ B ______。C. 串中所含字符的個數(shù)A. 串中不同字符的個數(shù)B. 串的長度必須大于零C. rearnext=s；rear=s；(33) 設(shè)指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為B. FRA. RF____ B _____。B. 4A. 6 A. top=top+1。C. n+1i
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1