數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)試題和答案解析[12級(jí)]-在線瀏覽
2024-08-02 17:05本頁(yè)面
【正文】 個(gè)數(shù)D. 串中不同數(shù)字的個(gè)數(shù) (37) 兩個(gè)字符串相等的充要條件是____ C ______。B. 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等C. 同時(shí)具備(A)和(B)兩個(gè)條件 D. 以上答案都不對(duì)(38) 串是一種特殊的線性表，其特殊性體現(xiàn)在____ B _______。____ B ______。C. 求子串A. BCDEFC. BCPQRSTA. “STRUCTURE” C. “ASTRUCTUR” A. 16B. 11D. 15(43) 假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn)數(shù)為_(kāi)___B____。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為_(kāi)___C____。A. 31 B. 32 C. 33 D. 16(47) 已知8個(gè)數(shù)據(jù)元素為(374125965)，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，最后兩層上的結(jié)點(diǎn)總數(shù)為_(kāi)___B____。 A. 23 B. 37 C. 44 D. 46(49) 在樹(shù)中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m (m≥0)個(gè)____A ____的集合T1,T2,T3...Tm,每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱(chēng)為T(mén)i的父結(jié)點(diǎn)，Ti稱(chēng)為T(mén)的子結(jié)點(diǎn)(1≤i≤m)。A. 3 B. 4 C. 5 D. 1(51) 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的____B____倍。A. n1 B. n C. n+1 D. n*(n1)/2(53) 在無(wú)向圖G的鄰接矩陣A中，若A[i,j]等于1，則A[j,i]等于____C ____。(訪問(wèn)標(biāo)志位數(shù)組空間)A. O(n) B. O(e) C. O(ne) D. O(n+e)(55) 請(qǐng)指出在順序表{11123452}中，用折半法查找關(guān)鍵碼12需做____ C ___次關(guān)鍵碼比較。A. 以順序方式存儲(chǔ) B. 以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列(57) 設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為_(kāi)__ B _____。 (59) 設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇___ B _____。 B. 平方取中法 C. 二分法 D. 開(kāi)放地址法(61) 當(dāng)α的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有_____ B ______的查找速度。A．順序表 B．有序的順序表C．鏈表 D．有序的鏈表(63) 如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用_____ D ____查找方法。A．最大概率 B．最小概率 C．同等概率 D．平均概率(65) 下述排序算法中，穩(wěn)定的是___ B _____。 (67) 下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是___ D _____。A. 起泡排序 B. 直接插入排序 C. 二路歸并排序 D. 快速排序(69) 一組記錄為{46，79，56，38，84，40}，則采用冒泡排序法按升序排列時(shí)第一趟排序結(jié)果是___ B _____ 。A. 插入 B. 堆 (71) 每次從無(wú)序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做___ 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ù)與紀(jì)錄的初始排列狀態(tài)無(wú)關(guān)___ D _____。A. 直接插入排序 B．二路歸并排序C．以第一元素為分界元素的快速排序 D．基數(shù)排序(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是__ C ____。A. 快速排序 B． 堆排序C． 歸并排序 D． 直接插入排序(77) 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是___ B _______。A. 堆排序 B．冒泡排序 C．快速排序 D． SHELL排序二、填空題。(2) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 結(jié)構(gòu)和 物理結(jié)構(gòu) 結(jié)構(gòu)。(4) 數(shù)據(jù)的物理結(jié)構(gòu)被分為_(kāi)__順序存儲(chǔ)______、___鏈?zhǔn)酱鎯?chǔ)_____、____索引存儲(chǔ)______和______散列表（Hash）存儲(chǔ)_____四種。(6) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指 數(shù)據(jù)元素間的邏輯關(guān)系 ，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系 。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱(chēng)這種結(jié)構(gòu)為_(kāi)_______網(wǎng)狀結(jié)構(gòu)________。(8) 對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱(chēng)為 空間復(fù)雜度和時(shí)間復(fù)雜度 分析。(10) for(i=1，t=1，s=0；i=n；i++) {t=t*i；s=s+t；}的時(shí)間復(fù)雜度為_(kāi)__Ο(n)______。(12) 線性表的存儲(chǔ)結(jié)構(gòu)有_________順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)____________________。(14) 設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中___ ni+1____個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中___ ni ____個(gè)元素。(16) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含______數(shù)據(jù)__________域和_____指針__________域。(18) 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱(chēng)為_(kāi)___ FILO ________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱(chēng)為(19) s=” I am a man” 長(zhǎng)度為_(kāi)___10_______(21) s=”this is the main string”,sub=”string”,strindex(s,sub)是：_______13_______。(23) 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為_(kāi)_______模式匹配________。(25) 在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0 ，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2 ，則：n0 =______n2 +1______。(27) 在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該 頂點(diǎn)的 ______度數(shù)______，對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的______出度數(shù)______。(29) 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為_(kāi)_____ O(n)____；若采用折半法查找，則時(shí)間復(fù)雜度為_(kāi)_____ O(log2n)____。(31) 在一棵二叉排序樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定_____小于______該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定____大于_______該結(jié)點(diǎn)的值。(33) 對(duì)于線性表（70，34，55，23，65，41，20）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素是_____70_________，散列地址為6的是____34,20,55_________。(35) 散列表中解決沖突的兩種方法是____開(kāi)放地址法_________和____鏈地址法_________。(37) 散列法存儲(chǔ)的基本思想是由________關(guān)鍵碼直接______________決定數(shù)據(jù)的存儲(chǔ)地址。(39) 在分塊查找中首先查找 _____索引________，然后再查找相應(yīng)的______塊_________。(41) 對(duì)兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹(shù)，____中序_______ 遍歷它們得到的序列的順序是一樣的。(43) 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_(kāi)__ O(log2n)_____，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1