(word完整版)數(shù)據(jù)結(jié)構(gòu)考試題及答案資料,推薦文檔_第1頁
(word完整版)數(shù)據(jù)結(jié)構(gòu)考試題及答案資料,推薦文檔_第2頁
(word完整版)數(shù)據(jù)結(jié)構(gòu)考試題及答案資料,推薦文檔_第3頁
(word完整版)數(shù)據(jù)結(jié)構(gòu)考試題及答案資料,推薦文檔_第4頁
免費(fèi)預(yù)覽已結(jié)束,剩余15頁可下載查看

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、2012 年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu)D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A。A 數(shù)據(jù)的存儲結(jié)構(gòu)B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)D數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A邏輯B存儲C邏輯和存儲D物理4 在存儲數(shù)據(jù)時(shí),通常不僅要存儲各數(shù)據(jù)元素的值,而且還要存儲C 。A數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲方法5在決定選取何種存儲結(jié)構(gòu)時(shí),一般不考慮A。A各結(jié)點(diǎn)的值如何B結(jié)點(diǎn)個(gè)數(shù)的多少C對數(shù)據(jù)有哪些運(yùn)算D所用的編程

2、語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。6以下說法正確的是D。A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7算法分析的目的是C,算法分析的兩個(gè)主要方面是A。(1)A 找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)C分析算法的易讀性和文檔性(2)A空間復(fù)雜度和時(shí)間復(fù)雜度B正確性和簡明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時(shí)間復(fù)雜度是O(n2)。s 0;for( I 0; i n; i)for( j0;j n;j)s Bij ;sum s ;9下面程序段的時(shí)間復(fù)雜度是O(n*m )。

3、for( i 0; i n; i)for( j0;j m;j )Aij 0;10下面程序段的時(shí)間復(fù)雜度是O(log3n)。i 0;while(i n)i i * 3 ;11在以下的敘述中,正確的是B。A線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)后出12通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性,這意味著B 。A數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同,而且對應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等13鏈表不具備的特點(diǎn)是A。A可隨機(jī)訪問任一結(jié)點(diǎn)B插入刪除

4、不需要移動(dòng)元素C不必事先估計(jì)存儲空間D所需空間與其長度成正比14不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。next NULLChead next headD head! NULL15帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。next NULLChead next headD head! NULL16若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn),則采用D存儲方式最節(jié)省運(yùn)算時(shí)間。A單鏈表點(diǎn)的雙循環(huán)鏈表B給出表頭指針的單循環(huán)鏈表C雙鏈表D帶頭結(jié)17需要分配較大空間, 插入和刪除不需要移動(dòng)元素的線性表,其存儲結(jié)構(gòu)是 B。A單鏈表B靜態(tài)鏈表C線性鏈表D順序存儲結(jié)構(gòu)18非空的

5、循環(huán)單鏈表 head的尾結(jié)點(diǎn)(由 p 所指向)滿足 C。Ap next NULLB p NULLCp next headDp head19在循環(huán)雙鏈表的 p 所指的結(jié)點(diǎn)之前插入 s 所指結(jié)點(diǎn)的操作是D 。AppriorpriorBppriorpriorCsprior next sDspriorprior s20如果最常用的操作是取第i 個(gè)結(jié)點(diǎn)及其前驅(qū),則采用D存儲方式最節(jié)省時(shí)間。A單鏈表B雙鏈表C單循環(huán)鏈表D 順序表21在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是B 。AO(1)B O(n)C O(n2)DO( nlog2n)22在一個(gè)長度為 n( n 1)的

6、單鏈表上,設(shè)有頭和尾兩個(gè)指針,執(zhí)行B操作與鏈表的長度有關(guān)。A刪除單鏈表中的第一個(gè)元素B刪除單鏈表中的最后一個(gè)元素C在單鏈表第一個(gè)元素前插入一個(gè)新元素D在單鏈表最后一個(gè)元素后插入一個(gè)新元素23與單鏈表相比,雙鏈表的優(yōu)點(diǎn)之一是D。A插入、刪除操作更簡單B可以進(jìn)行隨機(jī)訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結(jié)點(diǎn)更靈活24如果對線性表的操作只有兩種,即刪除第一個(gè)元素, 在最后一個(gè)元素的后面插入新元素,則最好使用B。A只有表頭指針沒有表尾指針的循環(huán)單鏈表B只有表尾指針沒有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長度為n 的順序表的第i 個(gè)位置上插入一個(gè)元素(1in1),元素的移動(dòng)次數(shù)為

7、:A。An i 1Bn iCiDi 126對于只在表的首、 尾兩端進(jìn)行插入操作的線性表,宜采用的存儲結(jié)構(gòu)為C。A順序表C用尾指針表示的循環(huán)單鏈表B 用頭指針表示的循環(huán)單鏈表D單鏈表27下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)?C。A 插入運(yùn)算方便B 可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C 存儲密度大D 刪除運(yùn)算方便28下面關(guān)于線性表的敘述中,錯(cuò)誤的是哪一個(gè)?B。A 線性表采用順序存儲,必須占用一片連續(xù)的存儲單元B 線性表采用順序存儲,便于進(jìn)行插入和刪除操作。C 線性表采用鏈?zhǔn)酱鎯?,不必占用一片連續(xù)的存儲單元D 線性表采用鏈?zhǔn)酱鎯?,便于進(jìn)行插入和刪除操作。29線性表是具有n 個(gè)B的有限序列。A字符B數(shù)據(jù)元素

8、C數(shù)據(jù)項(xiàng)D表元素30在n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中,算法的時(shí)間復(fù)雜度是O(1)的操作是A。A訪問第 i(1 i n)個(gè)結(jié)點(diǎn)和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)( 1i n)B在第 i( 1 i n)個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第 i (1 i n)個(gè)結(jié)點(diǎn)D以上都不對31若長度為 n 的線性表采用順序存儲結(jié)構(gòu),在其第 i 個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為 C。AO(0)B O(1)C O( n)DO( n2)32對于順序存儲的線性表,訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C 。A O(n) O(n)BO( n) O(1)C O( 1) O( n)DO(1) O(1)33線性表( a1,a2,

9、,an)以鏈?zhǔn)椒绞酱鎯ΓL問第i 位置元素的時(shí)間復(fù)雜度為C。AO(0)B O(1)C O( n)DO( n2)34單鏈表中,增加一個(gè)頭結(jié)點(diǎn)的目的是為了C。A使單鏈表至少有一個(gè)結(jié)點(diǎn)B標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C方面運(yùn)算的實(shí)現(xiàn)D說明單鏈表是線性表的鏈?zhǔn)酱鎯?5在單鏈表指針為p 的結(jié)點(diǎn)之后插入指針為s 的結(jié)點(diǎn),正確的操作是B 。Apnext pnext pnext s;Cpnext snext s next;p nexts36線性表的順序存儲結(jié)構(gòu)是一種A。A隨機(jī)存取的存儲結(jié)構(gòu)B順序存取的存儲結(jié)構(gòu)C索引存取的存儲結(jié)構(gòu)D Hash 存取的存儲結(jié)構(gòu)37棧的特點(diǎn)是B,隊(duì)列的特點(diǎn)是A。A先進(jìn)先出B先進(jìn)后出38棧

10、和隊(duì)列的共同點(diǎn)是C。A都是先進(jìn)后出B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素D沒有共同點(diǎn)39一個(gè)棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是C。AedcbaB decbaCdceabDabcde40設(shè)有一個(gè)棧,元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列C是不可能的出棧序列。AA,B,C,D,EBB,C,D,E,ACE,A,B,C,DDE,D,C,B,A41以下B不是隊(duì)列的基本運(yùn)算 ?A從隊(duì)尾插入一個(gè)新元素B從隊(duì)列中刪除第i 個(gè)元素C判斷一個(gè)隊(duì)列是否為空D讀取隊(duì)頭元素的值42若已知一個(gè)棧的進(jìn)棧序列是1,2,3,n,其輸出序列為 p1,p2,p3,pn,若 p1n,則 pi 為C

11、。AiB n iCni 1D不確定43判定一個(gè)順序棧st(最多元素為 MaxSize)為空的條件是B。Ast top !top 1Cst top !top MaxSize44判定一個(gè)順序棧st(最多元素為 MaxSize)為滿的條件是D。Ast top !top 1Cst top !top MaxSize45一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是B。A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,146判定一個(gè)循環(huán)隊(duì)列qu(最多元素為 MaxSize)為空的條件是C。Aqu rear qurear qu front 1 MaxSizeCqufront 147在循環(huán)

12、隊(duì)列中,若front 與 rear 分別表示對頭元素和隊(duì)尾元素的位置,則判斷循環(huán)隊(duì)列空的條件是C。A front rear 1B rear front 1C front rearD front 048向一個(gè)棧頂指針為h 的帶頭結(jié)點(diǎn)的鏈棧中插入指針s 所指的結(jié)點(diǎn)時(shí), 應(yīng)執(zhí)行D操作。Ahnext h ;Csnext hnext s ;49輸入序列為 ABC ,可以變?yōu)?CBA 時(shí),經(jīng)過的棧操作為B。Apush,pop,push,pop,push,popBpush,push,push,pop, pop,popCpush,push, pop, pop,push,popD push, pop, push

13、,push,pop, pop50若棧采用順序存儲方式存儲,現(xiàn)兩棧共享空間V1m ,top1 、top2分別代表第 1 和第 2 個(gè)棧的棧頂,棧1 的底在 V1 ,棧 2 的底在 Vm ,則棧滿的條件是B。A |top2 top1| 0B top1 1top2C top1 top2 mD top1 top251設(shè)計(jì)一個(gè)判別表達(dá)式中左、 右括號是否配對出現(xiàn)的算法,采用D數(shù)據(jù)結(jié)構(gòu)最佳。A 線性表的順序存儲結(jié)構(gòu)B 隊(duì)列C線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D棧52允許對隊(duì)列進(jìn)行的操作有D。A對隊(duì)列中的元素排序B取出最近進(jìn)隊(duì)的元素C在隊(duì)頭元素之前插入元素D刪除隊(duì)頭元素53對于循環(huán)隊(duì)列D。A無法判斷隊(duì)列是否為空B無法判斷

14、隊(duì)列是否為滿C隊(duì)列不可能滿D以上說法都不對54若用一個(gè)大小為 6 的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前 rear 和 front 的值分別為 0 和 3,當(dāng)從隊(duì)列中刪除一個(gè)元素, 再加入兩個(gè)元素后, rear 和 front 的值分別為B。A1 和5B2 和4C4 和2D5 和155隊(duì)列的 “先進(jìn)先出 ”特性是指D。A最早插入隊(duì)列中的元素總是最后被刪除B當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí),總是插入操作優(yōu)先C每當(dāng)有刪除操作時(shí),總是要先做一次插入操作D每次從隊(duì)列中刪除的總是最早插入的元素56和順序棧相比,鏈棧有一個(gè)比較明顯的優(yōu)勢是A。A通常不會出現(xiàn)棧滿的情況B 通常不會出現(xiàn)??盏那闆rC插入操作更容易實(shí)現(xiàn)D刪除操作

15、更容易實(shí)現(xiàn)57用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列,其頭指針指向隊(duì)頭結(jié)點(diǎn), 尾指針指向隊(duì)尾結(jié)點(diǎn),則在進(jìn)行出隊(duì)操作時(shí)C。A僅修改隊(duì)頭指針B僅修改隊(duì)尾指針C隊(duì)頭、隊(duì)尾指針都可能要修改D隊(duì)頭、隊(duì)尾指針都要修改58若串 S software,其子串的數(shù)目是B。A8B37C36D959串的長度是指B。A串中所含不同字母的個(gè)數(shù)B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù)D串中所含非空格字符的個(gè)數(shù)60串是一種特殊的線性表,其特殊性體現(xiàn)在B。A可以順序存儲B數(shù)據(jù)元素是一個(gè)字符C可以鏈?zhǔn)酱鎯數(shù)據(jù)元素可以是多個(gè)字符61設(shè)有兩個(gè)串 p 和 q,求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱為B。A連接B 模式匹配C求子串D求串

16、長62數(shù)組 A 中,每個(gè)元素的長度為 3 個(gè)字節(jié),行下標(biāo) i 從 1 到 8,列下標(biāo) j 從 1 到 10,從首地址 SA 開始連續(xù)存放的存儲器內(nèi), 該數(shù)組按行存放,元素 A85的起始地址為C。ASA 141B SA144C SA 222D SA 22563數(shù)組 A 中,每個(gè)元素的長度為3 個(gè)字節(jié),行下標(biāo)i 從 1 到 8,列下標(biāo)j從 1 到 10,從首地址 SA 開始連續(xù)存放的存儲器內(nèi), 該數(shù)組按行存放,元素 A58的起始地址為C。ASA141BSA180C SA 222D SA 22564若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下:froat averagenew float30 ;假設(shè)該數(shù)組的內(nèi)存起始位置

17、為200,average15的內(nèi)存地址是C。A214B215C260D25665設(shè)二維數(shù)組 A1 m ,1 n 按行存儲在數(shù)組 B 中,則二維數(shù)組元素Ai ,j 在一維數(shù)組 B 中的下標(biāo)為A。An* ( i1) jBn* ( i1) j1Ci* (j 1)Dj*m i 166有一個(gè) 100×90 的稀疏矩陣,非 0 元素有則用三元組表示該矩陣時(shí),所需的字節(jié)數(shù)是10,設(shè)每個(gè)整型數(shù)占B。2 個(gè)字節(jié),A20B66C18 000D3367數(shù)組A 0 4,1 3,57中含有的元素個(gè)數(shù)是A。A55B45C36D1668對矩陣進(jìn)行壓縮存儲是為了D。A方便運(yùn)算B 方便存儲C提高運(yùn)算速度D減少存儲空間

18、69設(shè)有一個(gè) 10 階的對稱矩陣A ,采用壓縮存儲方式,以行序?yàn)橹鞔鎯?,a1, 1 為第一個(gè)元素,其存儲地址為1,每個(gè)元素占 1 個(gè)地址空間,則a8,5 的地址為B。A13B 33C18D4070稀疏矩陣一般的壓縮存儲方式有兩種,即C。A二維數(shù)組和三維數(shù)組B 三元組和散列C三元組和十字鏈表D散列和十字鏈表71樹最適合用來表示C 。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)72深度為 5 的二叉樹至多有C個(gè)結(jié)點(diǎn)。A16B 32C31C 1073對一個(gè)滿二叉樹, m 個(gè)葉子, n 個(gè)結(jié)點(diǎn),深度為 h,則D 。An hmB h m 2nC m h1Dn 2h1

19、74任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序A 。A不發(fā)生改變B發(fā)生改變C不能確定D以上都不對75在線索化樹中, 每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息,還是線索化信息,若0 標(biāo)識樹結(jié)構(gòu)信息, 1 標(biāo)識線索,對應(yīng)葉結(jié)點(diǎn)的左右鏈域,應(yīng)標(biāo)識為_ D_。A00B01C10D1176在下述論述中,正確的是D。只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;二叉樹的度為2;二叉樹的左右子樹可任意交換;深度為 K 的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。ABCD77設(shè)森林F 對應(yīng)的二叉樹為B,它有m 個(gè)結(jié)點(diǎn), B的根為p,p 的右子樹的結(jié)點(diǎn)個(gè)數(shù)為n,森林F 中第一棵樹

20、的結(jié)點(diǎn)的個(gè)數(shù)是A。Am nB mn1Cn1D不能確定78若一棵二叉樹具有10 個(gè)度為 2 的結(jié)點(diǎn), 5 個(gè)度為 1 的結(jié)點(diǎn),則度為0的結(jié)點(diǎn)的個(gè)數(shù)是B 。A9B11C15D不能確定79具有10 個(gè)葉子結(jié)點(diǎn)的二叉樹中有B個(gè)度為2 的結(jié)點(diǎn)。A8B9C10D1180在一個(gè)無向圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。A1/2 B1C2D 481在一個(gè)有向圖中,所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A1/2 B1C2D 482某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG ,后序序列為 BDCAFGE ,則其左子樹中結(jié)點(diǎn)數(shù)目為:CA3B2C4D583已知一算術(shù)表達(dá)式的中綴形式為A B *C D/E,

21、后綴形式為 ABC * DE/,其前綴形式為D。AA B*C/DEBA B*CD/EC *ABC/DED A*BC/DE84已知一個(gè)圖,如圖所示,若從頂點(diǎn)a 出發(fā)按深度搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為_D_;按廣度搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為 _A_;Aa,b,e,c,d,fB a,c,f,e,b,dCa, e, b, c,f , d,Da,e, d, f,c,bAa,b,c,e,d,fB a,b,c,e,f ,dCa, e, b, c,f , d,Da,c, f, d,e,b85采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_。A先序遍歷B中序遍歷C后序遍歷D

22、按層遍歷86采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_D_。A先序遍歷B中序遍歷C后序遍歷D按層遍歷87具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。A n1B nC n(n1)/2D 2n88廣義表(a),a)的表頭是 C ,表尾是C。AaB ()C (a)D (a)89廣義表(a)的表頭是 C,表尾是B。AaB ()C (a)D (a)90順序查找法適合于存儲結(jié)構(gòu)為B 的線性表。A 散列存儲B 順序存儲或鏈?zhǔn)酱鎯壓縮存儲D 索引存儲91對線性表進(jìn)行折半查找時(shí),要求線性表必須B。A以順序方式存儲B以順序方式存儲, 且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯以鏈?zhǔn)椒绞酱鎯Γ?且結(jié)點(diǎn)按關(guān)鍵字有

23、序排列92采用折半查找法查找長度為n 的線性表時(shí),每個(gè)元素的平均查找長度為D 。AO(n2)BO(nlog2n)CO( n)DO(log2n)93有一個(gè)有序表為 1 ,3,9,12,32,41,45,62,75,77,82,95,100 ,當(dāng)折半查找值為82 的結(jié)點(diǎn)時(shí), C次比較后查找成功。A 11B 5C 4D894二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法B。A正確B錯(cuò)誤95下面關(guān)于B 樹和B樹的敘述中,不正確的結(jié)論是A。AB樹和B樹都能有效的支持順序查找BB 樹和B樹都能有效的支持隨機(jī)查找CB 樹和 B樹都是平衡的多叉樹DB 樹和 B樹

24、都可用于文件索引結(jié)構(gòu)96以下說法錯(cuò)誤的是B。A散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息,不包含指針。C負(fù)載因子是散列表的一個(gè)重要參數(shù),它反映了散列表的飽滿程度。D散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。97查找效率最高的二叉排序樹是C。A所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。B所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。C平衡二叉樹。D沒有左子樹的二叉排序樹。98排序方法中, 從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較,將其放入已排序序列的正確位置上的方法,稱為A希爾排序B。冒泡排序C 插入排序C。D。選擇排序99在

25、所有的排序方法中, 關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D。A希爾排序B冒泡排序C直接插入排序D直接選擇排序100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆。A94, 31,53,23, 16,72B94,53, 31,72,16,23C16, 53,23,94, 31,72D16,31, 23,94,53,72101堆排序是一種B排序。A插入B選擇C交換D歸并102D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A順序查找 B折半查找103直接選擇排序的時(shí)間復(fù)雜度為AO(n) BO(log2n)C分塊查找D插入D。(n 為元素個(gè)數(shù))CO(nlog2n)DO(n2)二、填空題。1數(shù)

26、據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型,樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4 種。3在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)后續(xù)結(jié)點(diǎn)。4線性結(jié)構(gòu)中元素之間存在一對一 關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對多 關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。5在樹形結(jié)構(gòu)中, 樹根結(jié)點(diǎn)沒有前驅(qū) 結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn);葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個(gè) 。6數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、 鏈?zhǔn)?、索引和散列?/p>

27、儲 。7衡量一個(gè)算法的優(yōu)劣主要考慮正確性、 可讀性、健壯性和 時(shí)間復(fù)雜度與空間復(fù)雜度 。8評估一個(gè)算法的優(yōu)劣,通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。9算法的 5 個(gè)重要特性是有窮性、確定性 、可行性、輸入和輸出。10在一個(gè)長度為 n 的順序表中刪除第i 個(gè)元素時(shí),需向前移動(dòng)n i1個(gè)元素。11在單鏈表中, 要?jiǎng)h除某一指定的結(jié)點(diǎn), 必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。12在雙鏈表中,每個(gè)結(jié)點(diǎn)有兩個(gè)指針域,一個(gè)指向 前驅(qū) 結(jié)點(diǎn),另一個(gè)指向 后繼結(jié)點(diǎn) 。13在順序表中插入或刪除一個(gè)數(shù)據(jù)元素,需要平均移動(dòng) n 個(gè)數(shù)據(jù)元素,移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與 位置 有關(guān)。14當(dāng)線性表的元素總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除

28、操作,但要求以最快的速度存取線性表的元素是,應(yīng)采用順序存儲結(jié)構(gòu)。15根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù),將線性鏈表分成單鏈表和 雙鏈表。16順序存儲結(jié)構(gòu)是通過 下標(biāo) 表示元素之間的關(guān)系的; 鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 指針 表示元素之間的關(guān)系的。17帶頭結(jié)點(diǎn)的循環(huán)鏈表L 中只有一個(gè)元素結(jié)點(diǎn)的條件是L nextnextL。18棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表,其運(yùn)算遵循后進(jìn)先出的原則。19空串是零個(gè)字符的串,其長度等于零??瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串,其長度等于其包含的空格個(gè)數(shù)。20組成串的數(shù)據(jù)元素只能是單個(gè)字符。21一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱為該串的子串。

29、22子串”str 在”主串”datastructure中的”位置是5。23二維數(shù)組 M 的每個(gè)元素是 6 個(gè)字符組成的串,行下標(biāo) i 的范圍從 0 到 8,列下標(biāo) j 的范圍從 1 到 10,則存放 M 至少需要 540 個(gè)字節(jié); M 的第 8 列和第 5行共占 108 個(gè)字節(jié)。24稀疏矩陣一般的壓縮存儲方法有兩種,即三元組表和十字鏈表。25廣義表(a),(b),c),(d)的長度是3,深度是4。26在一棵二叉樹中,度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為n2,則有 n0n21。27在有n 個(gè)結(jié)點(diǎn)的二叉鏈表中,空鏈域的個(gè)數(shù)為_n1_。28一棵有n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有_2n1_個(gè)

30、結(jié)點(diǎn)。29深度為5 的二叉樹至多有31個(gè)結(jié)點(diǎn)。30若某二叉樹有20 個(gè)葉子結(jié)點(diǎn), 有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子, 則該二叉樹的總結(jié)點(diǎn)個(gè)數(shù)為69。31某二叉樹的前序遍歷序列是abdgcefh,中序序列是 dgbaechf,其后序序列為gdbehfca。32線索二叉樹的左線索指向其遍歷序列中的前驅(qū)遍歷序列中的后繼。33在各種查找方法中, 平均查找長度與結(jié)點(diǎn)個(gè)數(shù)列查找法。34在分塊索引查找方法中,首先查找索引表,右線索指向其n 無關(guān)的查找方法是散,然后查找相應(yīng)的塊表。35一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列,構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。36具有 10 個(gè)頂點(diǎn)的無向圖

31、,邊的總數(shù)最多為_45_。37已知圖 G 的鄰接表如圖所示,其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為 _v1v2v3v6v5v4_ ,其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為 _v1v2v5v4v3v6_。38索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。 一個(gè)索引隸屬于某個(gè)數(shù)據(jù)記錄集,它由若干索引項(xiàng)組成, 索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對應(yīng)記錄的地址 。39Prim 算法生成一個(gè)最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n 1 ,當(dāng)前選擇的邊的權(quán)值是候選邊中最小的, 選中的邊加入樹中不產(chǎn)生回路三項(xiàng)原則。40在一棵 m 階 B 樹中,除根結(jié)點(diǎn)外,每個(gè)結(jié)點(diǎn)最多有m棵子樹,最少有 m/2棵子樹。

32、三、判斷題。1在決定選取何種存儲結(jié)構(gòu)時(shí),一般不考慮各結(jié)點(diǎn)的值如何。( )2抽象數(shù)據(jù)類型( ADT )包括定義和實(shí)現(xiàn)兩方面,其中定義是獨(dú)立于實(shí)現(xiàn)的,定義僅給出一個(gè) ADT 的邏輯特性,不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。 ( )3抽象數(shù)據(jù)類型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。( )4順序存儲方式插入和刪除時(shí)效率太低,因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。?× )5線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí),結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)的。( ×)6對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。( × )7順序存儲方式只能用于存儲線性結(jié)構(gòu)。( × )8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。( × )9線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。( × )10線性表就是順序存儲的表。 ( × )11取線性表的第i 個(gè)元素的時(shí)間同i 的大小有關(guān)。( × )12循環(huán)鏈表不是線性表。 ( × )13鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí),在鏈表中比在順序表中效率高。( )14雙向鏈表可隨機(jī)訪問任一結(jié)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論