數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案(12級)(編輯修改稿)
2024-07-19 14:40 本頁面
【文章內(nèi)容簡介】 序表中的適當(dāng)位置，此種排序方法叫做___ A _____ 排序。A. 插入 B. 堆 (71) 每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做___ B _____排序。A. 插入 B. 堆 (72) 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為____ C ____。 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ù)與紀(jì)錄的初始排列狀態(tài)無關(guān)___ D _____。A. 直接插入排序 B. 起泡排序C. 快速排序 D. 直接選擇排序(74) 設(shè)有關(guān)鍵碼初始序列{Q，H，C，Y，P，A,M,S,R,D,F,X}，新序列{F，H，C，D，P，A，M，Q，R，S，Y,X}是采用____ C ____ 方法對初始序列進(jìn)行第一趟掃描的結(jié)果。A. 直接插入排序 B．二路歸并排序C．以第一元素為分界元素的快速排序 D．基數(shù)排序(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是__ C ____。A. 直接插入排序 B. 直接選擇排序C． 快速排序 D． 歸并排序(76) 若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選排序方法是___ C _____ 。A. 快速排序 B． 堆排序C． 歸并排序 D． 直接插入排序(77) 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是___ B _______。A． n B． 2n1 C． 2n D． n1(78) 下列排序算法中，____ C ____ 算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的間反而最多。A. 堆排序 B．冒泡排序 C．快速排序 D． SHELL排序二、填空題。(每空1分，共10分)(1) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 數(shù)據(jù) 以及它們之間的 關(guān)系 和運算等的學(xué)科。(2) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 結(jié)構(gòu)和 物理結(jié)構(gòu) 結(jié)構(gòu)。(3) 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：____線性數(shù)據(jù)結(jié)構(gòu)_______、____樹型結(jié)構(gòu)______和_____圖結(jié)構(gòu)______。(4) 數(shù)據(jù)的物理結(jié)構(gòu)被分為___順序存儲______、___鏈?zhǔn)酱鎯____、____索引存儲______和______散列表（Hash）存儲_____四種。(5) 一種抽象數(shù)據(jù)類型包括_____變量的取值范圍_____和 ____操作的類別_____兩個部分。(6) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指 數(shù)據(jù)元素間的邏輯關(guān)系 ，數(shù)據(jù)的存儲結(jié)構(gòu)是指 數(shù)據(jù)元素存儲方式或者數(shù)據(jù)元素的物理關(guān)系 。(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的____關(guān)系__________。當(dāng)結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為________網(wǎng)狀結(jié)構(gòu)________。當(dāng)結(jié)點之間存在1對N（1：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_____樹結(jié)構(gòu)__________。(8) 對算法從時間和空間兩方面進(jìn)行度量，分別稱為 空間復(fù)雜度和時間復(fù)雜度 分析。(9) 算法的效率可分為______空間_________效率和______時間_________效率。(10) for(i=1，t=1，s=0；i=n；i++) {t=t*i；s=s+t；}的時間復(fù)雜度為___Ο(n)______。(11) 線性表是n個元素的_________有限序列____________________。(12) 線性表的存儲結(jié)構(gòu)有_________順序存儲和鏈?zhǔn)酱鎯___________________。(13) 設(shè)線性表中有n個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_____Ｏ(n)______，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為____ O(n)_______。(14) 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中___ ni+1____個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中___ ni ____個元素。(15) 若頻繁地對線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用_____鏈?zhǔn)絖________存儲結(jié)構(gòu)。(16) 鏈?zhǔn)酱鎯Y(jié)構(gòu)中的結(jié)點包含______數(shù)據(jù)__________域和_____指針__________域。(17) 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為___Ο(1)______，在表尾插入元素的時間復(fù)雜度為_____Ο(n)_______。(18) 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為____ FILO ________表；隊列的插入和刪除運算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出隊列，所以又把隊列稱為_____ FIFO ______表。(19) s=” I am a man” 長度為____10_______(20) s1=”hello “,s2=”boy”,s1,s2連接后為：________ hello boy ______________(21) s=”this is the main string”,sub=”string”,strindex(s,sub)是：_______13_______。(22) int a[10][10],已知a=1000,sizeof(int)=2,求a[3][3]地址：_______1066___________(23) 設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為________模式匹配________。(24) 在樹型結(jié)構(gòu)中，樹根結(jié)點沒有______前趨______結(jié)點，其余每個結(jié)點有且僅有______一______個前驅(qū)結(jié)點；樹葉結(jié)點沒有______后繼______結(jié)點，其余每個結(jié)點的______后繼______結(jié)點數(shù)不受限制。(25) 在一棵二叉樹中，度為0的結(jié)點的個數(shù)為n0 ，度為2的結(jié)點的個數(shù)為n2 ，則：n0 =______n2 +1______。(26) 由分別帶權(quán)為3,9,6,2,5的共五個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為______ 55______。(27) 在圖G的鄰接表表示中，每個頂點鄰接表中所含的結(jié)點數(shù)，對于無向圖來說等于該 頂點的 ______度數(shù)______，對于有向圖來說等于該頂點的______出度數(shù)______。(28) 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為______O(n2 ) ______， 采用鄰接表表示的空間復(fù)雜性為______ O(n+e) ______。(29) 對于長度為n的線性表，若進(jìn)行順序查找，則時間復(fù)雜度為______ O(n)____；若采用折半法查找，則時間復(fù)雜度為______ O(log2n)____。(30) 假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點數(shù)為____1_______，則比較二次查找成功的結(jié)點數(shù)為____2_______，則比較三次查找成功的結(jié)點數(shù)為____4_______，則比較四次查找成功的結(jié)點數(shù)為_____8______，則比較五次查找成功的結(jié)點數(shù)為____5_______，平均查找長度為_____ log2(n+1)1______。(31) 在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定_____小于______該結(jié)點的值，右子樹上所有結(jié)點的值一定____大于_______該結(jié)點的值。 (32) 對一棵二叉排序樹進(jìn)行中序遍歷時，得到的結(jié)點序列是一個_______增序序列_______________。(33) 對于線性表（70，34，55，23，65，41，20）進(jìn)行散列存儲時，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素是_____70_________，散列地址為6的是____34,20,55_________。(34) 在線性表的散列存儲中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則a等于____ n/m _______。(35) 散列表中解決沖突的兩種方法是____開放地址法_________和____鏈地址法_________。(36) 在散列存儲中，裝填因子a的值越大，則_______產(chǎn)生沖突的可能性就越大____________；a的值越小，則_____產(chǎn)生沖突的可能性就越小___________。(37) 散列法存儲的基本思想是由________關(guān)鍵碼直接______________決定數(shù)據(jù)的存儲地址。(38) 構(gòu)造哈希函數(shù)的方法有(寫二個)____
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1