《數(shù)據(jù)結(jié)構(gòu)》綜合練習(xí)

1、綜合練習(xí)、單項(xiàng)選擇題數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱之為（C ）。存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)設(shè)語(yǔ)句X+的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間復(fù)雜度為（B ）。for（i=1; i=n; i+）for（j=i; j=n; j+）x+;A.0(1)2B.O( n)3C.0(n)D.0( n)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是（D）o便于隨機(jī)存取B.存儲(chǔ)密度高C.無(wú)需預(yù)分配空間D.便于進(jìn)行插入和刪除操作假設(shè)在順序表a,ai,an-i中，每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的數(shù)目為4,且第0個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為100,則第7個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是（ D ）o106 B.

2、 107C.124D.128在線性表中若經(jīng)常要存取第順序表C.不帶頭結(jié)點(diǎn)的單鏈表i個(gè)數(shù)據(jù)元素及其前趨，則宜采用（帶頭結(jié)點(diǎn)的單鏈表D.循環(huán)單鏈表A ）存儲(chǔ)方式。在鏈表中若經(jīng)常要?jiǎng)h除表中最后一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則宜采用（C ）存儲(chǔ)方式。順序表B.用頭指針標(biāo)識(shí)的循環(huán)單鏈表用尾指針標(biāo)識(shí)的循環(huán)單鏈表D.雙向鏈表在一個(gè)含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時(shí)間復(fù)雜度是（C ）oO（1） B. O（log 2n） C. O（n） D. O（n2）要將一個(gè)順序表a 0,a 1,a n-1中第i個(gè)數(shù)據(jù)元素ai（0 i n-1）刪除，需要移動(dòng)（B ） 個(gè)數(shù)據(jù)

3、元素。A.i B. n-i-1C. n-i D. n-i+1在棧中存取數(shù)據(jù)的原則是（B ）oA.先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.沒有限制若將整數(shù)1、2、3、4依次進(jìn)棧，則不可能得到的出棧序列是（D ）oA . 1234 B.1324 C.4321 D.1423A .需要判斷棧是否滿C.需要判斷棧元素的類型12.在順序棧中，若棧頂指針在鏈棧中，進(jìn)行出棧操作時(shí)（ B ）o需要判斷棧是否為空無(wú)需對(duì)棧作任何差別top指向棧頂元素的存儲(chǔ)單元，且順序棧的最大容量是maxSize,則順序棧的判空條件是（B）A . top=0 B.top=-1 C. top=maxSize D.top=maxSize-1

4、在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxSize。則順序棧的判滿的條件是（C ）。A . top=0 B.top=-1 C. top=maxSize D.top=maxSize-1在隊(duì)列中存取數(shù)據(jù)元素的原則是（ A ）。A .先進(jìn)先出B.先進(jìn)后出后進(jìn)后出D.沒有限制在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ) 單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判空條件是（A ）。A. front=rearB. front!=rearC.

5、fron t=rear+1D. fron t=（rear+1）% maxSize在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ) 單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判滿條件是（D ）。A. front=rearB. front!=rearC. fron t=rear+1D. fron t=（rear+1）% maxSize在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件， front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的

6、下一個(gè)存儲(chǔ) 單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的長(zhǎng)度是（ C ）。A. rear-frontrear-fr on t+1（rear-fro nt+maxSize）%maxSize D. （rear-fro nt+1）%maxSize設(shè)長(zhǎng)度為n的鏈隊(duì)列采用單循環(huán)鏈表加以表示，若只設(shè)一個(gè)頭指針指向隊(duì)首元素，貝U入隊(duì)操作的時(shí)間復(fù)雜度為（B ）。A . 0（1）B. 0（n）C. O（log 2n）D . O（n2）串的長(zhǎng)度是指（A ）A.串中包含的字符個(gè)數(shù)B.串中包含的不同字符個(gè)數(shù)C.串中除空格以外的字符個(gè)數(shù)D.串中包含的不同字母?jìng)€(gè)數(shù)設(shè)有兩個(gè)串p和q，其中q是p的子串，求q在p中首次出

7、現(xiàn)的位置的算法稱為（C ）A .求子串B .聯(lián)接C.模式匹配D .求串長(zhǎng)設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鬟M(jìn)行存儲(chǔ)，an為第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，則ass的地址為（B ）。A. 13B.33C. 18D.407.有一個(gè)二維數(shù)組 A1.6, 0.7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，那么這個(gè)數(shù)組占用的存儲(chǔ)空間大小是（ D）個(gè)字節(jié)。A. 48B. 96C. 252D. 288在哈夫曼樹中，任何一個(gè)結(jié)點(diǎn)它的度都是（ C ）。A.0 或 1 B. 1或 2 C. 0 或 2 D. 0或 1 或 224.對(duì)一棵深度為h的二叉樹，其結(jié)點(diǎn)的個(gè)

8、數(shù)最多為（D ）。A.2hB. 2h-1C. 2D. 2-1C.只有一個(gè)根結(jié)點(diǎn)D.任意一棵二叉樹25.假設(shè)一棵二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)個(gè)數(shù)為3,則這棵二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是（C ）A.2B. 3C. 4D. 526.若某棵二叉樹的先根遍歷序列為ABCDEF中根遍歷序列為CBDAEF則這棵二叉樹的后根遍歷序列為（B ）。A. FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA在有n個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中有（ C ）個(gè)空的指針域。A . n-1 B. n C. n+1 D. 0利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（C ）。A.指向最左孩子B.指

9、向最右孩子C .空 D .非空引入二叉線索樹的目的是（ A ）。A.加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B .為了能在二叉樹中方便的進(jìn)行插入與刪除C.為了能方便的找到雙親D.使二叉樹的遍歷結(jié)果唯一設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若 F中有n個(gè)非終端結(jié)點(diǎn)，則 B中右指針 域?yàn)榭盏慕Y(jié)點(diǎn)有（C）個(gè)。A. n-1B. nC. n + 1D. n + 2在一個(gè)有-個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為I，則所有頂點(diǎn)的入度之和為 （A）。A. B.-C.； - -D.具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（ A ）條邊才能確保是一個(gè)連通圖。 TOC o 1-5 h z A.5B.6C.7D.8個(gè)有n個(gè)頂點(diǎn)的無(wú)向

10、圖最多有（C ）條邊。疚沖一i；C.浙:忌D.-n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣至少有（B ）個(gè)非零元素。A . nB . 2（n-1）C. n/2D. n2對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，下列敘述正確的是（ A ）。第：行上的非零元素個(gè)數(shù)和第：列上的非零元素個(gè)數(shù)一定相等矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)第:行與第：列上的非零元素的總數(shù)等于頂點(diǎn).的度數(shù)矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù).32.任何一個(gè)無(wú)向連通圖的最小生成樹（ B ）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在下面（B ）方法可以判斷出一個(gè)有向圖是否有環(huán)。A .深度優(yōu)先遍歷B .拓?fù)渑判駽 .求最短路徑D .

11、求關(guān)鍵路徑對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（B ）A. 以順序方式存儲(chǔ) B.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字值有序排列以鏈接方式存儲(chǔ) D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字值有序排列38.用二分查找法查找具有n個(gè)結(jié)點(diǎn)的順序表時(shí)，查找每個(gè)結(jié)點(diǎn)的平均比較次數(shù)是2A.O(n ) B.O( nlog2n) C.O( n) D.O(log2n)若有一個(gè)長(zhǎng)度為64的有序表，現(xiàn)用二分查找方法查找某一記錄，則查找不成功，最多需要比較（B ） 次。A.9B.7C.5D.3若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱這種存儲(chǔ)結(jié)構(gòu)為（D ）A.順序存儲(chǔ)結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C.索引存儲(chǔ)結(jié)構(gòu)D.散列存儲(chǔ)結(jié)構(gòu)設(shè)哈

12、希表長(zhǎng)為14，哈希函數(shù)是H（key）=key%11 ,表中已有數(shù)據(jù)的關(guān)鍵字為15，38, 61,84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測(cè)法解決沖突，則放入的位置是（D ）。A . 8B . 3C. 5D. 942下面給出的四種排序算法中，（B ）是不穩(wěn)定的排序。A 插入排序B 堆排序C.二路歸并排序D 冒泡排序43在下列排序算法中，哪一種算法的時(shí)間復(fù)雜度與初始排序序列無(wú)關(guān)（D ）。A .直接插入排序B .冒泡排序C.快速排序D .直接選擇排序關(guān)鍵字序列（8, 9, 10, 4, 5, 6, 20, 1 , 2）只能是下列排序算法中（C ）的兩趟排序 后的結(jié)果。A 選擇排序B.冒

13、泡排序C.插入排序D.堆排序 組記錄的關(guān)鍵字為（46, 79, 56, 38, 40, 84）,則利用快速排序的方法，以第一個(gè)記 錄為支點(diǎn)得到的一次劃分結(jié)果為（ C ）。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） 在對(duì)一組關(guān)鍵字序列15 , 33,55, 100, 65, 50, 40, 95，進(jìn)行直接插入排序時(shí)，把65 插入，需要比較（A ）次。A. 2B. 4C. 6D. 8從待排序的序列中選出關(guān)鍵字值最大的記錄放到有序序列中，該排序方法稱為 （B ）

14、。A.希爾排序B.直接選擇排序C.冒泡排序D.快速排序當(dāng)待排序序列基本有序時(shí)，以下排序方法中，（B ）最不利于其優(yōu)勢(shì)的發(fā)揮。A.直接選擇排序B.快速排序C.冒泡排序D.直接插入排序在待排序序列局部有序時(shí)，效率最高的排序算法是（B ）。A.直接選擇排序B.直接插入排序C.快速排序D.歸并排序50.數(shù)據(jù)表中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（D ）算法最節(jié)省時(shí)間。A .冒泡排序B .快速排序C.簡(jiǎn)單選擇排序D .堆排序二、填空題一個(gè)串的任意連續(xù)字符組成的子序列稱為串的子串，該串稱為 主串 TOC o 1-5 h z 若兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置上的字符也相等，則稱兩個(gè)串

15、相等。尋找子串在主串中的位置，稱為模式匹配。其中，子串又稱為模式串 。設(shè)數(shù)組A1.5,1.6 的基地址為1000 ,每個(gè)元素占5個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素 A5,5的存儲(chǔ)地址為1140。一個(gè)n x n的對(duì)稱矩陣，如果以相同的元素只存儲(chǔ)一次的原則進(jìn)行壓縮存儲(chǔ)，則其元素壓縮后所需的存儲(chǔ)容量為n（n+1）/2。對(duì)矩陣壓縮的目的是為了節(jié)省存儲(chǔ)空間。循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過(guò)數(shù)學(xué)上的 求模（或取余）運(yùn)算來(lái)實(shí)現(xiàn)的。50 。一棵具有100個(gè)結(jié)點(diǎn)的完全二叉樹，其葉結(jié)點(diǎn)的個(gè)數(shù)為 TOC o 1-5 h z 以5 , 9, 12, 13, 20,

16、 30為葉結(jié)點(diǎn)的權(quán)值所構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是217有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹中，結(jié)點(diǎn)的總數(shù)是 2m-1 。若一棵完全二叉樹的第 4層(根結(jié)點(diǎn)在第0層)有7個(gè)結(jié)點(diǎn)，則這棵完全二叉樹的葉子結(jié)點(diǎn)總數(shù)是11。在深度為k的完全二叉樹中至少有丄個(gè)結(jié)點(diǎn)，至多有2角個(gè)結(jié)點(diǎn)。假定待查找記錄個(gè)數(shù)為n,則在等概率的情況下，順序查找在查找成功情況下的平均查找長(zhǎng)度為(n +1)/2;在查找失敗情況下的平均查找長(zhǎng)度為n+1。對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須以順。分塊查找分為兩個(gè)階段，分和 在塊內(nèi)查找待查的元素。哈希法存儲(chǔ)中，沖突指的是不同關(guān)鍵字值對(duì)應(yīng)到相同的存儲(chǔ)地址。一棵二叉排序樹用中序遍歷輸出的信息是遞增 序

17、列。哈希法存儲(chǔ)的基本思想是根據(jù)關(guān)鍵字來(lái)決定存儲(chǔ)地址。若用.表示圖中頂點(diǎn)數(shù)，則有畑現(xiàn)注 條邊的無(wú)向圖稱為完全圖。個(gè)頂點(diǎn)的連通無(wú)向圖至少有 條邊，至多有 : 條邊。若有向圖的鄰接矩陣為： TOC o 1-5 h z /01C1010 11191011aooo10100/則頂點(diǎn)，的入度是3對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為-，出度為二，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為_- 。在求最小生成樹的兩種算法中，克魯斯卡爾算法適合于稀疏圖。數(shù)據(jù)結(jié)構(gòu)中的迪杰斯特拉算法是用來(lái)求某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。執(zhí)行排序操作時(shí)，根據(jù)使用的存儲(chǔ)器可將排序算法分為內(nèi)排序 和 外排序 。在對(duì)一組記錄序列50,40,95,20,15,70,60,45,80進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表中時(shí)，為尋找插入位置需比較3 次。在直接插入排序和直接選擇排序中，若初始記錄序列基本有序，則選用直接插入排序。在對(duì)一組記錄序列50,40,95,20,15,70,60,45,80進(jìn)行直接選擇排序時(shí)，第4次交換和選擇后，未排序記錄為 50,