【文章內(nèi)容簡介】 ) 用某種排序方法對關(guān)鍵字序列{35,84,21,47,15,27,68,25,20}進(jìn)行排序時，序列的變化情況如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用的方法是（ ）。A) 直接選擇排序 B) 希爾排序 C) 堆排序 D) 快速排序(108) 一組記錄的排序碼為(46,79,56,38,40,84)，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的第一次劃分結(jié)果為（ ）。 A) 38,40,46,56,79,84 B) 40,38,46,79,56,84 C) 40,38,46,56,79,84 D) 40,38,46,84,56,79(109) 快速排序在最壞情況下的時間復(fù)雜度是（　　?。〢) O(n2log2n) B) O(n2) C) O(nlog2n) D) O(log2n)(110) 下列排序算法中不穩(wěn)定的是（ ）。A) 直接選擇排序 B) 折半插入排序 C) 冒泡排序 D) 快速排序(111) 對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個子序列，再對兩個子序列進(jìn)行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是（ ）。A) 直接選擇排序 B) 直接插入排序 C) 快速排序 D) 冒泡排序 (112) 將5個不同的數(shù)據(jù)進(jìn)行排序，至多需要比較（ ）次。A) 8 B) 9 C) 10 D) 25(113) 排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（　　?。?。A)選擇排序 B)快速排序 C)冒泡排序 D)插入排序(114) 排序算法中，不穩(wěn)定的排序是（　　?。?。A)直接插入排序 B)冒泡排序 C)堆排序 D)選擇排序(115) 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（ ）.A) 希爾排序 B) 冒泡排序 C) 插入排序 D) 選擇排序(116) 從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（ ）。A) 希爾排序 B) 歸并排序 C) 插入排序 D) 選擇排序(117) 對ｎ個不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（ ）A) 從小到大排列好的 B) 從大到小排列好的C) 元素?zé)o序 D) 元素基本有序(118) 對ｎ個不同的排序碼進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為（ ）。A) n+1 B) n C) n1 D) n(n1)/2(119) 快速排序在下列哪種情況下最易發(fā)揮其長處。（ ）A) 被排序的數(shù)據(jù)中含有多個相同排序碼 B) 被排序的數(shù)據(jù)已基本有序C) 被排序的數(shù)據(jù)完全無序D) 被排序的數(shù)據(jù)中的最大值和最小值相差懸殊(120) 對有n個記錄的表作快速排序，在最壞情況下，算法的時間復(fù)雜度是（ ）。A) O(n) B) O(n2) C) O(nlog2n) D) O(n3)(121) 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。A) 38, 40, 46, 56, 79, 84 B) 40, 38, 46 , 79, 56, 84 C) 40, 38，46, 56, 79, 84 D) 40, 38, 46, 84, 56, 79(122) 下列關(guān)鍵字序列中，（ ）是堆。A) 16, 72, 31, 23, 94, 53 B) 94, 23, 31, 72, 16, 53 C) 16, 53, 23, 94，31, 72 D) 16, 23, 53, 31, 94, 72(123) 堆是一種（ ）排序。A) 插入 B) 選擇 C) 交換 D) 歸并(124) 堆的形狀是一棵（ ）。 A) 二叉排序樹 B) 滿二叉樹 C) 完全二叉樹 D) 平衡二叉樹(125) 若一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為（ ）。A) 79, 46, 56, 38, 40, 84 B) 84, 79, 56, 38, 40, 46 C) 84, 79, 56, 46, 40, 38 D) 84, 56, 79, 40, 46, 38 (126) 下述幾種排序方法中，要求內(nèi)存最大的是（ ）。A) 插入排序 B) 快速排序 C) 歸并排序 D) 選擇排序(127) 有一組數(shù)據(jù)（15，9，7，8，20，1，7，4），用堆排序的篩選方法建立的初始堆為（ ）。A) 1，4，8，9，20，7，15，7 B) 1，7，15，7，4，8，20，9C) 1，4，7，8，20，15，7，9 D) A，B，C 均不對。(128) 51．下列四個序列中，哪一個是堆（ ）。 A) 75,65,30,15,25,45,20,10 B) 75,65,45,10,30,25,20,15C) 75,45,65,30,15,25,20,10 D) 75,45,65,10,25,30,20,15(129) 以下序列不是堆的是( )。A) (100,85,98,77,80,60,82,40,20,10,66) B) (100,98,85,82,80,77,66,60,40,20,10)C) (10,20,40,60,66,77,80,82,85,98,100) D) (100,85,40,77,80,60,66,98,82,10,20)(130) 快速排序方法在（ ）情況下最不利于發(fā)揮其長處。A) 要排序的數(shù)據(jù)量太大 B) 要排序的數(shù)據(jù)中含有多個相同值C) 要排序的數(shù)據(jù)個數(shù)為奇數(shù) D) 要排序的數(shù)據(jù)已基本有序(131) 對關(guān)鍵碼序列28，16，32，12，60，2，5，72 快速排序，從小到大一次劃分結(jié)果為（ ）。A) (2,5,12,16)26(60,32,72) B) (5,16,2,12)28(60,32,72)C) (2,16,12,5)28(60,32,72) D) (5,16,2,12)28(32,60,72)(132) 對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快的情形是（ ）。A) {21,25,5,17,9,23,30} B){25,23,30,17,21,5,9}C) {21,9,17,30,25,23,5} D) {5,9,17,21,23,25,30}二、填空題(133) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的 操作對象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。(134) 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。(135) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個方面的內(nèi)容。(136) 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。(137) 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。(138) 在線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。(139) 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個 。(140) 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 。(141) 數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序 、 鏈?zhǔn)?、 索引 和 散列 。(142) 數(shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。(143) 一個算法的效率可分為 時間 效率和 空間 效率。(144) 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 集合，線性表，樹，圖四種。(145) 順序映象的特點是借助元素在存儲器中的 相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象的特點是借助是指示元素存儲地址的 指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。任何一個算法的設(shè)計取決于選定 邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的 存儲結(jié)構(gòu)。(146) 數(shù)據(jù)類型是一組___________性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。(147) 數(shù)據(jù)對象是___________性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。(148) 如果操作不改變原邏輯結(jié)構(gòu)的“值”，而只是從中提取某些信息作為運(yùn)算結(jié)果，則稱該類運(yùn)算為 型運(yùn)算。引用(149) 算法的 健壯特性是指做為一個好的算法，當(dāng)輸入的數(shù)據(jù)非法時，也能適當(dāng)?shù)刈龀稣_反應(yīng)或進(jìn)行相應(yīng)的處理，而不會產(chǎn)生一些莫名其妙的輸出結(jié)果。(150) 算法分析不是針對實際執(zhí)行時間的精確的算出算法執(zhí)行具體時間的分析，而是針對算法中語句的 執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。(151) T(n)=O(f(n))，它表示隨問題規(guī)模n的增大算法的執(zhí)行時間的增長率和f(n)的增長率 相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。(152) 若算法執(zhí)行時所需要的輔助空間相對于輸入數(shù)據(jù)量而言是個常數(shù)，則稱這個算法為 原地工作，輔助空間為O(1)。(153) 在帶有頭結(jié)點的單鏈表中L中，第一個元素結(jié)點的指針是 。Lnext(154) 在一個帶頭節(jié)點的單循環(huán)鏈表中，p指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針head可用p表示為head= 。pnextnext(155) 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點 , 若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句: pynext=pxnext。 pxnext=py。(156) 對于棧操作數(shù)據(jù)的原則是 。后進(jìn)先出(157) 設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為 。(rearfront+m)%m(158) 若已知一個棧的入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1= =n,則pi為 。ni+1 (159) 隊列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。(160) 通常程序在調(diào)用另一個程序時，都需要使用一個 棧來保存被調(diào)用程序內(nèi)分配的局部變量。形式參數(shù)的存儲空間以及返回地址。(161) 棧下溢是指在___棧空_____時進(jìn)行出棧操作。(162) 用P表示入棧操作，D表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的P和D的操作串為_______ 。PDPPDPDD(163) 在具有n個單元的循環(huán)隊列中，隊滿共有 n1個元素。(164) 隊列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。(165) 循環(huán)隊列的引入，目的是為了克服_______假溢出。(166) 所謂稀疏矩陣指的是_______非零元很少(tm*n)且分布沒有規(guī)律 。(167) 在稀疏矩陣表示所對應(yīng)的三元組線性表中，每個三元組元素按 行為主序， 列號為輔序的次序排列。(168) 二位數(shù)組Amn按行優(yōu)先順序存儲在內(nèi)存中，元素a00地址為loc(a00),每個元素在內(nèi)存中占d個字節(jié)，元素aij的地址計算公式為loc(aij)= loc(a00)＋(i*n+j)*d 。(169) 去除廣義表LS=(a1,a2,a3,……，an)中第1個元素，由其余元素構(gòu)成的廣義表稱為LS的____表尾_____。(170) 樹內(nèi)個結(jié)點的度 最大值稱為樹的度。(171) 一個二叉樹第5層節(jié)點最多有 16個。(172) 已知完全二叉樹T的第5層只有7個結(jié)點，則該樹共有____11____個葉子結(jié)點。(173) 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為N0,度為2的結(jié)點的個數(shù)為N2,則有N0 =______N2+1。(174) 假設(shè)用于通信的電文由8個字母組成，其頻率分別為7,19,2,6,32,3,27,10。設(shè)計哈夫曼編碼，其中字母的編碼長度最大是 5位。(175) 一棵具有257個結(jié)點的完全二叉樹，它的深度為