(2021年)數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題

1、數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題 PAGE PAGE 24數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題編輯整理：尊敬的讀者朋友們：這里是精品文檔編輯中心，本文檔內(nèi)容是由我和我的同事精心編輯整理后發(fā)布的，發(fā)布之前我們對(duì)文中內(nèi)容進(jìn)行仔細(xì)校對(duì)，但是難免會(huì)有疏漏的地方，但是任然希望（數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題）的內(nèi)容能夠給您的工作和學(xué)習(xí)帶來(lái)便利。同時(shí)也真誠(chéng)的希望收到您的建議和反饋，這將是我們進(jìn)步的源泉，前進(jìn)的動(dòng)力。本文可編輯可修改，如果覺(jué)得對(duì)您有幫助請(qǐng)收藏以便隨時(shí)查閱，最后祝您生活愉快 業(yè)績(jī)進(jìn)步，以下為數(shù)據(jù)結(jié)構(gòu)與算法期末考試復(fù)習(xí)試題的全部?jī)?nèi)容。數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、選擇題。在數(shù)據(jù)結(jié)

2、構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為CA動(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)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 A。A數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)D數(shù)據(jù)元素之間的關(guān)系在數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)A邏輯B存儲(chǔ)C邏輯和存儲(chǔ)D物理在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)CA數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類(lèi)型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲(chǔ)方法在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮AA各結(jié)點(diǎn)的值如何B結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算D所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。以下說(shuō)法正確的是 D。 A數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

3、B數(shù)據(jù)元素是數(shù)據(jù)的最小單位 C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合 D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)算法分析的目的是 C，算法分析的兩個(gè)主要方面是 A。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中的輸入和輸出的關(guān)C分析算法的效率以求改進(jìn)C分析算法的易讀性和文檔性A空間復(fù)雜度和時(shí)間復(fù)雜度B正確性和簡(jiǎn)明性 C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜下面程序段的時(shí)間復(fù)雜度是 .s =0；for（ I =0; in； i+） for（j=0；jn；j+)s +=Bij； sum = s ；下面程序段的時(shí)間復(fù)雜度是 O（nm)for( i =0; in; i+)for(j=0；jm；j+）Aij 0；下面程序段

4、的時(shí)間復(fù)雜度是 i 0;while（inext =NULLD head！=NULL帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是BAhead = NULLB head- next =NULL Cheadnext =headD head!=NULL若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表B給出表頭指針的單循環(huán)鏈表C雙鏈表D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是BA單鏈表B靜態(tài)鏈表C線性鏈表D順序存儲(chǔ)結(jié)構(gòu)非空的循環(huán)單鏈表 head 的尾結(jié)點(diǎn)（由 p 所指向)滿足 CAp-next = N

5、ULLBp = NULLCpnext =headDp = head在循環(huán)雙鏈表的 p 所指的結(jié)點(diǎn)之前插入 s 所指結(jié)點(diǎn)的操作是DAp-prior = s;s-next = p;ppriornext = s；s-prior = ppriorBpprior = s；ppriornext = s;snext = p;sprior = p-priorCs-next = p;sprior = p-prior；p-prior = s；pprior-next = sDs-next = p；sprior = p-prior；p-prior-next = s;pprior= s 20如果最常用的操作是取第 i

6、個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 D 存儲(chǔ)方式最節(jié)省時(shí)間。A單鏈表B雙鏈表C單循環(huán)鏈表D 順序表在一個(gè)具有 nB 。AO（1）BO（n）CO（n2）DO(nlog2n)在一個(gè)長(zhǎng)度為 n（n1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B 操作與鏈表長(zhǎng)度有關(guān).刪除單鏈表中的第一個(gè)元素刪除單鏈表中的最后一個(gè)元素 C在單鏈表第一個(gè)元素前插入一個(gè)新元素D與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是 D 。A插入、刪除操作更簡(jiǎn)單B可以進(jìn)行隨機(jī)訪問(wèn) CD順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活則最好使用B。A只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表 B只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表CD循環(huán)雙鏈表在長(zhǎng)度為 n 的順序表的第 i 個(gè)位置上插入一個(gè)元素（

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

8、B數(shù)據(jù)元素C數(shù)據(jù)項(xiàng)D表元素在 n 個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中,算法的時(shí)間復(fù)雜度是 O（1）的操作是AA訪問(wèn)第 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=inext=s;s-next=pnextB snext=pnext ；pnext=s； Cp-next=s；p-next=s-nextDpnext=s-next;pnext=s36線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A。A隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B順序存取的存儲(chǔ)結(jié)構(gòu)C索引存取的存儲(chǔ)結(jié)構(gòu)DHash 存取的存儲(chǔ)結(jié)構(gòu)棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是 AA先進(jìn)先出B先進(jìn)后出棧和隊(duì)列的共同點(diǎn)是

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

10、一個(gè)順序棧 st（最多元素為 MaxSize）為空的條件是 BAst-top ！= -1Bsttop = 1Cst-top != MaxSizeD sttop = MaxSize判定一個(gè)順序棧 st(最多元素為 MaxSize）為滿的條件是 DAst-top ！= -1Bsttop = -1Csttop != MaxSizeDst-top = MaxSize一個(gè)隊(duì)列的入隊(duì)序列是 1,2，3，4，則隊(duì)列的輸出序列是 BA4，3，2，1B1，2，3,4C1，4，3,2D3，2,4,1判定一個(gè)循環(huán)隊(duì)列 qu（最多元素為 MaxSize)為空的條件是 C.Aqu-rear qufront =MaxSi

11、zefront -1=MaxSizeBqurear qu-Cqu-rear =qu-frontD qu-rear=qu-front1在循環(huán)隊(duì)列中，若 front 與 rear列空的條件是C.Afront=rear+1Brear=front+1Cfront=rear Dfront=048向一個(gè)棧頂指針為作。h的帶頭結(jié)點(diǎn)的鏈棧中插入指針 s 所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 D 操Ahnext=s ;Csnext=h ；h =s;Bs-next=h ；Ds-next=h-next ；hnext=s ；輸入序列為 ABC，可以變?yōu)?CBA 時(shí),經(jīng)過(guò)的棧操作為B . Apush,pop，push,pop，push

12、，popBpush,push，push,pop， popCpush,push,pop， pop，push，popDpush，pop，push，push，pop， pop若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間 V1 m，top1、top2分別代表第1 和第 2 個(gè)棧的棧頂，棧 1 的底在 V1，棧 2 的底在 Vm B 。A|top2top1|=0B top1+1=top2Ctop1+top2=m Dtop1=top2設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 D數(shù)據(jù)結(jié)構(gòu)最佳A線性表的順序存儲(chǔ)結(jié)構(gòu)B隊(duì)列C線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D棧允許對(duì)隊(duì)列進(jìn)行的操作有 D。 A對(duì)隊(duì)列中的元素排序B取

13、出最近進(jìn)隊(duì)的元C在隊(duì)頭元素之前插入元素D刪除隊(duì)頭元素對(duì)于循環(huán)隊(duì)列D.無(wú)法判斷隊(duì)列是否為空B無(wú)法判斷隊(duì)列是否為C隊(duì)列不可能滿D以上說(shuō)法都不對(duì)若用一個(gè)大小為 6 的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列,且當(dāng)前 rear 和 front 的值分別為 0 和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear 和 front 的值分別為B 。A1 和 5B2 和 4C4 和 2D5 和 1隊(duì)列的“先進(jìn)先出”特性是指D. A最早插入隊(duì)列中的元素總是最后被刪除 B當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)C每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作 D每次從隊(duì)列中刪除的總是最早插入的元素和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)

14、勢(shì)是 A。 A通常不會(huì)出現(xiàn)棧滿的情況B 通常不會(huì)出現(xiàn)?？盏那镃插入操作更容易實(shí)現(xiàn)D刪除操作更容易實(shí)現(xiàn)用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn),則在行出隊(duì)操作時(shí)C。僅修改隊(duì)頭指針B僅修改隊(duì)尾指針 C隊(duì)頭、隊(duì)尾指針都可能要修改D隊(duì)頭、隊(duì)尾指針都要修若串 S=software，其子串的數(shù)目是BA8B37C36D9串的長(zhǎng)度是指 B。串中所含不同字母的個(gè)數(shù)B串中所含字符的個(gè)數(shù) C串中所含不同字符的個(gè)數(shù)D串中所含非空格字符的個(gè)串是一種特殊的線性表,其特殊性體現(xiàn)在 BA可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符 C可以鏈?zhǔn)酱鎯?chǔ)D數(shù)據(jù)元素可以是多個(gè)字符設(shè)有兩個(gè)串 p 和 q，求 q 在 p

15、 中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為 BA連接B 模式匹配C求子串D求串長(zhǎng)數(shù)組 A 中，每個(gè)元素的長(zhǎng)度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到10，從首地址 SA 開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素 A85的起始地為C .ASA141 B SA144CSA222DSA225數(shù)組 A 中，每個(gè)元素的長(zhǎng)度為 3 個(gè)字節(jié)，行下標(biāo) i 從 1 到 8，列下標(biāo) j 從 1 到10，從首地址 SA 開(kāi)始連續(xù)存放的存儲(chǔ)器內(nèi),該數(shù)組按行存放，元素 A58的起始地為C。ASA141 B SA180CSA222DSA225若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下: froat average=new

16、float30;假設(shè)該數(shù)組的內(nèi)存起始位置為 200， average15的內(nèi)存地址是 CA214B215C260D256設(shè)二維數(shù)組 A1m，1n按行存儲(chǔ)在數(shù)組 B 中，則二維數(shù)組元素 Ai，j在一數(shù)組 B 中的下標(biāo)為A.An*(i1)+j B n(i1）+j-1Ci*（j-1)Djm+i1有一個(gè) 10090 的稀疏矩陣，非 0 元素有 10，設(shè)每個(gè)整型數(shù)占 2 個(gè)字節(jié)，則用三組表示該矩陣時(shí)，所需的字節(jié)數(shù)是B.A20B 66C18 000D3367數(shù)組 A0 4,-1 3，5 7中含有的元素個(gè)數(shù)是 AA55B 45C36D16對(duì)矩陣進(jìn)行壓縮存儲(chǔ)是為了D。A方便運(yùn)算 B 方便存儲(chǔ)C提高運(yùn)算速度D減

17、少存儲(chǔ)空間設(shè)有一個(gè) 10 階的對(duì)稱(chēng)矩陣 A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ),a為第一個(gè)元素，1，1其存儲(chǔ)地址為 1,每個(gè)元素占 1 個(gè)地址空間，則 a的地址為 B 。8，5A13 B 33C18D40稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種,即 C。 A二維數(shù)組三維數(shù)組B 三元組和散列C三元組和十字鏈表D 散列和十字鏈表樹(shù)最適合用來(lái)表示C 。A有序數(shù)據(jù)元素B無(wú)序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無(wú)聯(lián)系的數(shù)深度為 5 的二叉樹(shù)至多有C個(gè)結(jié)點(diǎn)A16B 32C 31C10對(duì)一個(gè)滿二叉樹(shù)，m 個(gè)葉子,n 個(gè)結(jié)點(diǎn)，深度為 h，則 D。An = h+mB h+m = 2nC m = h-1D

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

19、棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是A.Am-nBmn-1Cn+1D不能確定若一棵二叉樹(shù)具有 10 個(gè)度為 2 的結(jié)點(diǎn)，5 個(gè)度為 1 的結(jié)點(diǎn)，則度為 0是 B .A9B11C15D不能確定具有 10 個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有B個(gè)度為 2 的結(jié)點(diǎn)A8B9C10D11在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的 C倍A1/2B 1C 2D 4在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B 倍A1/2B 1C 2D 4某二叉樹(shù)結(jié)點(diǎn)的中序序列為 ABCDEFG，后序序列為 BDCAFGE，則其左子樹(shù)中結(jié)點(diǎn)數(shù)為：CA3B2C4D5已知一算術(shù)表達(dá)式的中綴形式為 AB CD/E，后綴形式為 ABC *+D

20、E/，其前綴式為D.AA+B*C/DEBA+B*CD/EC +ABC/DED+A*BC/DEabecdf已知一個(gè)圖,如圖所示，若從頂點(diǎn) a 出發(fā)按歷，則可能得到的一種頂點(diǎn)序列為D;按廣歷，則可能得到的一種頂點(diǎn)序列為abecdfAa,b,e，c，d，fBa，c，f,e， b,dCa,e，b，c,f，d，Da，e,d，f，c,bAa,b,c,e，d,fBa,b，c，e，f，d Ca，e，b，c，f，d，Da，c，f，d，e，b采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的AA先序遍歷B中序遍歷C后序遍歷D按層遍歷度搜索法進(jìn)行遍度搜索法進(jìn)行遍采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的DA

21、先序遍歷B中序遍歷C后序遍歷D按層遍歷具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。A n1B nC n（n1）/2D 2n廣義表（(a，a)的表頭是 C ，表尾是 C 。AaB （）C （a）D （ a)廣義表（(a）的表頭是 C ，表尾是 B 。AaB （)C （a）D （ a）順序查找法適合于存儲(chǔ)結(jié)構(gòu)為B 的線性表。A 散列存儲(chǔ)B 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C 壓縮存儲(chǔ)D 索引存儲(chǔ)對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 B 。A 以順序方式存儲(chǔ)B 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列 C 以鏈?zhǔn)椒绞酱鎯?chǔ)D 以鏈?zhǔn)椒绞酱鎯?chǔ),且結(jié)點(diǎn)按鍵字有序排列采用折半查找法查找長(zhǎng)度為 n 的線性表時(shí)，每個(gè)元素的平均查找

22、長(zhǎng)度為 D 。AO（n2）BO(nlogn)CO（n)DO（logn）2293有一個(gè)有序表為1，3,9，12，32,41，4562，75,77，82，9，100，當(dāng)折半查找值為 82 的結(jié)點(diǎn)時(shí)， C次比較后查找成功。A 11B 5C4D8二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其孩子的值.這種說(shuō)法B.A 正確B 錯(cuò) 誤下面關(guān)于 B 樹(shù)和 B+樹(shù)的敘述中，不正確的結(jié)論是 A 。A B 樹(shù)和 B+樹(shù)都能有效的支持順序查找B B 樹(shù)和 B+樹(shù)都能有效的支持隨機(jī)查C B 樹(shù)和 B+樹(shù)都是平衡的多叉樹(shù)D B 樹(shù)和 B+樹(shù)都可用于文件索引結(jié)構(gòu)以下說(shuō)法錯(cuò)誤的是B。 A散列法存

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

24、序C直接插入排序D直接選擇排序堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆A94,31，53,23,16,72B94，53，31，72,16，23 C16，53，23，94,31,72D16，31,23,94，53,72堆排序是一種B排序。A插入B選擇C交換D歸并D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高A順序查找B折半查找C分塊查找D插入直接選擇排序的時(shí)間復(fù)雜度為D。(n 為元素個(gè)數(shù))AO(n)n）2D O(n2）2二、填空題.數(shù)據(jù)邏輯結(jié)構(gòu)包括 線性結(jié)構(gòu)、 樹(shù)形結(jié)構(gòu) 和 圖狀結(jié)構(gòu) 三種類(lèi)型，樹(shù)形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱(chēng)非線性結(jié)構(gòu).2數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和 圖狀結(jié)構(gòu)4 種

25、。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn) 沒(méi)有 前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn) 沒(méi)有 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)后續(xù)結(jié)點(diǎn)。構(gòu)中元素之間存在 多對(duì)多 關(guān)系。在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有 前驅(qū) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有 后續(xù) 結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以 任意多個(gè) 。數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是 順序 、 鏈?zhǔn)?、索引 和散列 存儲(chǔ) .衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和 時(shí)間復(fù)雜度與 空間復(fù)雜度 .評(píng)估一個(gè)算法的優(yōu)劣，通常從 時(shí)間復(fù)雜度和 空間復(fù)雜度兩個(gè)方面考察。算法的 5 個(gè)重要特性是 有窮性 、 確定性 、 可行性 、輸

26、入和輸出。在一個(gè)長(zhǎng)度為 n 的順序表中刪除第 i 個(gè)元素時(shí)，需向前移動(dòng) n-i-1 個(gè)元素。在單鏈表中,要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的 前驅(qū) 結(jié)點(diǎn)。在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 前驅(qū) 結(jié)點(diǎn),另一個(gè)指向 后繼結(jié)點(diǎn) .在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng) n 個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與 位置有關(guān).當(dāng)線性表的元素總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除操作,但要求以最快的速度存取性表的元素是，應(yīng)采用 順序存儲(chǔ)結(jié)構(gòu)。根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分單鏈表和 雙鏈表 。順序存儲(chǔ)結(jié)構(gòu)是通過(guò) 下標(biāo)表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò) 指針

27、表元素之間的關(guān)系的。帶頭結(jié)點(diǎn)的循環(huán)鏈表 L 中只有一個(gè)元素結(jié)點(diǎn)的條件是 L-nextnext=L。則。長(zhǎng)度等于其包含的空格個(gè)數(shù)。組成串的數(shù)據(jù)元素只能是 單個(gè)字符 。一個(gè)字符串中 任意個(gè)連續(xù)字符構(gòu)成的部分 稱(chēng)為該串的子串。22子串 ”str” 在主串 ”datastructure” 中的位置是523二維數(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稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即 三元組表 和 十字鏈表 。25廣義表（a),（(b，c（(）的長(zhǎng)

28、度是 3 ，深度是 4 。在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為 n0，度為 2 的結(jié)點(diǎn)的個(gè)數(shù)為 n2，有 n0n2+1 。在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為n+1.一棵有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1_個(gè)結(jié)點(diǎn)。深度為 5 的二叉樹(shù)至多有 31個(gè)結(jié)點(diǎn)。若某二叉樹(shù)有 20 個(gè)葉子結(jié)點(diǎn)，有 30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為69。某二叉樹(shù)的前序遍歷序列是 abdgcefh,中序序列是 dgbaechfgdbehfca 。線索二叉樹(shù)的左線索指向其 遍歷序列中的前驅(qū)，右線索指向其遍歷列中的后繼 。在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n 無(wú)關(guān)的查找方法是 散列查找法

29、。在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的 塊表 。對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。具有 10 個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為45.已知圖 G 的鄰接表如圖所示,其從頂點(diǎn) v1 出發(fā)的深度優(yōu)先搜索序列為_(kāi)v1v2v3v6v5v4_，其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為_(kāi)v1v2v5v4v3v6。vv1v6v2v5v5v4v4v6v3若干索引項(xiàng)組成，索引項(xiàng)的結(jié)構(gòu)為 關(guān)鍵字 和 關(guān)鍵字對(duì)應(yīng)記錄的地址 。Prim 算法生成一個(gè)最小生成樹(shù)每一步選擇都要滿足 邊的總數(shù)不超過(guò) n1 ， 當(dāng)前選擇的邊的權(quán)值是候選邊中最小的 , 選中的邊加入樹(shù)中不產(chǎn)生回路 三項(xiàng)原則。在一棵 m 階 B 樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有 m 棵子樹(shù)，最少