數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)期末考試復(fù)習(xí)試題

1、WORD格式"數(shù)據(jù)構(gòu)造與算法" c 語(yǔ)言版期末考復(fù)習(xí)題一、選擇題。1在數(shù)據(jù)構(gòu)造中，從邏輯上可以把數(shù)據(jù)構(gòu)造分為C。A 動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造B緊湊構(gòu)造和非緊湊構(gòu)造C線性構(gòu)造和非線性構(gòu)造D內(nèi)部構(gòu)造和外部構(gòu)造2數(shù)據(jù)構(gòu)造在計(jì)算機(jī)內(nèi)存中的表示是指A。A 數(shù)據(jù)的存儲(chǔ)構(gòu)造B數(shù)據(jù)構(gòu)造C數(shù)據(jù)的邏輯構(gòu)造D數(shù)據(jù)元素之間的關(guān)系3在數(shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的A構(gòu)造。A 邏輯B存儲(chǔ)C邏輯和存儲(chǔ)D物理4在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)C。A 數(shù)據(jù)的處理方法B數(shù)據(jù)元素的類(lèi)型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲(chǔ)方法5在決定選取何種存儲(chǔ)構(gòu)造時(shí)，一般不考慮A。A 各結(jié)點(diǎn)的值如何B

2、結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算D所用的編程語(yǔ)言實(shí)現(xiàn)這種構(gòu)造是否方便。6以下說(shuō)法正確的選項(xiàng)是D。A 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的根本單位專(zhuān)業(yè)資料整理WORD格式1專(zhuān)業(yè)資料整理WORD格式B數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)構(gòu)造是帶構(gòu)造的數(shù)據(jù)項(xiàng)的集合D一些外表上很不一樣的數(shù)據(jù)可以有一樣的邏輯構(gòu)造7算法分析的目的是C，算法分析的兩個(gè)主要方面是A。1A 找出數(shù)據(jù)構(gòu)造的合理性B研究算法中的輸入和輸出的關(guān)系C分析算法的效率以求改進(jìn)C分析算法的易讀性和文檔性2A 空間復(fù)雜度和時(shí)間復(fù)雜度B正確性和簡(jiǎn)明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8下面程序段的時(shí)間復(fù)雜度是O(n2)。s =0;for( I =0; i<n;

3、 i+)for(j=0;j<n;j+)s +=Bij;sum = s ;9下面程序段的時(shí)間復(fù)雜度是O(n*m)。for( i =0; i<n; i+)for(j=0;j<m;j+)Aij 0;10下面程序段的時(shí)間復(fù)雜度是O(log3n)。專(zhuān)業(yè)資料整理WORD格式2專(zhuān)業(yè)資料整理WORD格式i 0；while i<=n i = i * 3 ；11在以下的表達(dá)中，正確的選項(xiàng)是B。A 線性表的順序存儲(chǔ)構(gòu)造優(yōu)于鏈表存儲(chǔ)構(gòu)造B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)后出12通常要求同一邏輯構(gòu)造中的所有數(shù)據(jù)元素具有一樣的特性，這意味著B(niǎo) 。A

4、 數(shù)據(jù)元素具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要一樣，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類(lèi)型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等專(zhuān)業(yè)資料整理WORD格式13鏈表不具備的特點(diǎn)是A 可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)C不必事先估計(jì)存儲(chǔ)空間A 。B插入刪除不需要移動(dòng)元素D所需空間與其長(zhǎng)度成正比專(zhuān)業(yè)資料整理WORD格式14不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。A head = NULLB head->next =NULL專(zhuān)業(yè)資料整理WORD格式3專(zhuān)業(yè)資料整理WORD格式Chead->next =headD head!=NULL15帶頭結(jié)點(diǎn)的單鏈表head 為空的判定條件是B。A

5、 head = NULLB head->next =NULLChead->next =headD head!=NULL16假設(shè)某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，那么采用D 存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A 單鏈表B給出表頭指針的單循環(huán)鏈表C雙鏈表D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)構(gòu)造是B 。A 單鏈表B靜態(tài)鏈表C線性鏈表D順序存儲(chǔ)構(gòu)造18非空的循環(huán)單鏈表head 的尾結(jié)點(diǎn)由 p 所指向滿足C。A p->next = NULLBp = NULLCp->next =headDp = head19在

6、循環(huán)雙鏈表的p 所指的結(jié)點(diǎn)之前插入s 所指結(jié)點(diǎn)的操作是D。A p->prior = s；s->next = p；p->prior->next = s；s->prior = p->priorBp->prior = s；p->prior->next = s；s->next = p；s->prior = p->prior專(zhuān)業(yè)資料整理WORD格式4專(zhuān)業(yè)資料整理WORD格式Cs->next = p；s->prior = p->prior ；p->prior = s；p->prior->next =

7、 sDs->next = p；s->prior = p->prior ；p->prior->next = s；p->prior = s20如果最常用的操作是取第i 個(gè)結(jié)點(diǎn)及其前驅(qū)，那么采用D存儲(chǔ)方式最節(jié)省時(shí)間。A 單鏈表B雙鏈表C單循環(huán)鏈表D順序表21在一個(gè)具有n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是B 。A O1BOnC On2DOnlog2n22在一個(gè)長(zhǎng)度為nn>1的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B操作與鏈表的長(zhǎng)度有關(guān)。A 刪除單鏈表中的第一個(gè)元素B刪除單鏈表中的最后一個(gè)元素C在單鏈表第一個(gè)元素前插入一個(gè)新元素D在單鏈

8、表最后一個(gè)元素后插入一個(gè)新元素23與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。A 插入、刪除操作更簡(jiǎn)單B可以進(jìn)展隨機(jī)訪問(wèn)C可以省略表頭指針或表尾指針D順序訪問(wèn)相鄰結(jié)點(diǎn)更靈活專(zhuān)業(yè)資料整理WORD格式5專(zhuān)業(yè)資料整理WORD格式24如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，那么最好使用B。A 只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表C非循環(huán)雙鏈表D循環(huán)雙鏈表25在長(zhǎng)度為 n 的順序表的第 i 個(gè)位置上插入一個(gè)元素1 in+1，元素的移動(dòng)次數(shù)為：A。A n i + 1Bn iCiDi 126對(duì)于只在表的首、尾兩端進(jìn)展插入操作的線性表，宜采用

9、的存儲(chǔ)構(gòu)造為C。A 順序表B用頭指針表示的循環(huán)單鏈表C用尾指針表示的循環(huán)單鏈表D單鏈表27下述哪一條是順序存儲(chǔ)構(gòu)造的優(yōu)點(diǎn)？C。A 插入運(yùn)算方便B 可方便地用于各種邏輯構(gòu)造的存儲(chǔ)表示C 存儲(chǔ)密度大D 刪除運(yùn)算方便28下面關(guān)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是哪一個(gè)？B。A 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B 線性表采用順序存儲(chǔ)，便于進(jìn)展插入和刪除操作。專(zhuān)業(yè)資料整理WORD格式6專(zhuān)業(yè)資料整理WORD格式C 線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D 線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)展插入和刪除操作。29線性表是具有n 個(gè)B的有限序列。A字符B數(shù)據(jù)元素C數(shù)據(jù)項(xiàng)D表元素30在 n 個(gè)結(jié)點(diǎn)的線性

10、表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是O1的操作是A 。A訪問(wèn)第 i1<=i<=n 個(gè)結(jié)點(diǎn)和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū) 1<i<=nB在第 i1<=i<=n個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)C刪除第 i 1<=i<=n 個(gè)結(jié)點(diǎn)D以上都不對(duì)31假設(shè)長(zhǎng)度為 n 的線性表采用順序存儲(chǔ)構(gòu)造，在其第 i 個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為C。AO(0)BO(1)CO(n)DO(n2)32對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C 。AO(n) O(n)BO(n) O(1)CO(1) O(n)DO(1) O(1)33線性表a1,a2,an以鏈?zhǔn)椒绞?/p>

11、存儲(chǔ)，訪問(wèn)第i 位置元素的時(shí)間復(fù)雜度為C。專(zhuān)業(yè)資料整理WORD格式7專(zhuān)業(yè)資料整理WORD格式AO(0)BO(1)CO(n)DO(n2)34單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了C。A使單鏈表至少有一個(gè)結(jié)點(diǎn)B標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C方面運(yùn)算的實(shí)現(xiàn)D說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)35在單鏈表指針為p 的結(jié)點(diǎn)之后插入指針為s 的結(jié)點(diǎn)，正確的操作是B。Ap->next=s；s->next=p->nextB s->next=p->next ；p->next=s;Cp->next=s；p->next=s->nextDp->next=s->ne

12、xt；p->next=s專(zhuān)業(yè)資料整理WORD格式36線性表的順序存儲(chǔ)構(gòu)造是一種A隨機(jī)存取的存儲(chǔ)構(gòu)造C索引存取的存儲(chǔ)構(gòu)造A 。B順序存取的存儲(chǔ)構(gòu)造DHash 存取的存儲(chǔ)構(gòu)造專(zhuān)業(yè)資料整理WORD格式37棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是A。A 先進(jìn)先出B先進(jìn)后出38棧和隊(duì)列的共同點(diǎn)是C。A 都是先進(jìn)后出B都是先進(jìn)先出C只允許在端點(diǎn)處插入和刪除元素D沒(méi)有共同點(diǎn)39一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，那么棧的不可能的輸出序列是C。A edcbaB decbaCdceabDabcde專(zhuān)業(yè)資料整理WORD格式8專(zhuān)業(yè)資料整理WORD格式40設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、 D、E。以下C是不可能

13、的出棧序列。A A,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假設(shè)一個(gè)棧的進(jìn)棧序列是1，2，3，n，其輸出序列為 p1，p2，p3，, ，pn，假設(shè) p1n，那么 pi 為C。A iBniCni 1D不確定43判定一個(gè)順序棧st最多元素為 MaxSize為空的條件是B。A st->top != -1Bst->top = -1Cst->top != MaxSizeD st->top =MaxSize44判定一個(gè)順序棧s

14、t最多元素為 MaxSize為滿的條件是D。A st->top != -1Bst->top = -1Cst->top != MaxSizeDst->top =MaxSize45一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，那么隊(duì)列的輸出序列是B。A 4，3，2，1B1，2，3，4專(zhuān)業(yè)資料整理WORD格式9專(zhuān)業(yè)資料整理WORD格式C1，4，3，2D3，2，4，146判定一個(gè)循環(huán)隊(duì)列qu最多元素為 MaxSize為空的條件是C。A qu->rear qu->front =MaxSizeBqu->rear qu->front -1=MaxSizeCqu->

15、rear =qu->frontD qu->rear =qu->front -147在循環(huán)隊(duì)列中，假設(shè) front 與 rear 分別表示對(duì)頭元素和隊(duì)尾元素的位置，那么判斷循環(huán)隊(duì)列空的條件是C。A front=rear+1Brear=front+1Cfront=rearDfront=048向一個(gè)棧頂指針為h 的帶頭結(jié)點(diǎn)的鏈棧中插入指針s 所指的結(jié)點(diǎn)時(shí)， 應(yīng)執(zhí)行D 操作。A h->next=s ;Bs->next=h ;Cs->next=h ;h =s ;Ds->next=h->next ;h->next=s ;49輸入序列為 ABC ，可以變

16、為 CBA 時(shí)，經(jīng)過(guò)的棧操作為B。A push，pop，push，pop，push，popBpush，push，push，pop， pop，popCpush，push，pop， pop，push，popDpush，pop，push，push，pop，pop50假設(shè)棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1m ，top1 、top2 分別代表第 1 和第 2 個(gè)棧的棧頂，棧 1 的底在 V1 ，棧 2 的底在 Vm ，那么棧滿的條專(zhuān)業(yè)資料整理WORD格式10專(zhuān)業(yè)資料整理WORD格式件是B。A |top2-top1|=0B top1+1=top2C top1+top2=mDtop1=top251設(shè)

17、計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D數(shù)據(jù)構(gòu)造最正確。A 線性表的順序存儲(chǔ)構(gòu)造B隊(duì)列C線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造D棧專(zhuān)業(yè)資料整理WORD格式52允許對(duì)隊(duì)列進(jìn)展的操作有A對(duì)隊(duì)列中的元素排序C在隊(duì)頭元素之前插入元素D 。B取出最近進(jìn)隊(duì)的元素D刪除隊(duì)頭元素專(zhuān)業(yè)資料整理WORD格式53對(duì)于循環(huán)隊(duì)列D。A無(wú)法判斷隊(duì)列是否為空B無(wú)法判斷隊(duì)列是否為滿C隊(duì)列不可能滿D以上說(shuō)法都不對(duì)54假設(shè)用一個(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和155隊(duì)列的

18、“先進(jìn)先出特性是指D。專(zhuān)業(yè)資料整理WORD格式11專(zhuān)業(yè)資料整理WORD格式A最早插入隊(duì)列中的元素總是最后被刪除B當(dāng)同時(shí)進(jìn)展插入、刪除操作時(shí)，總是插入操作優(yōu)先C每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作D每次從隊(duì)列中刪除的總是最早插入的元素56和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是A。A通常不會(huì)出現(xiàn)棧滿的情況B通常不會(huì)出現(xiàn)?？盏那闆rC插入操作更容易實(shí)現(xiàn)D刪除操作更容易實(shí)現(xiàn)57用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(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假設(shè)串 S=software，其子串的數(shù)

19、目是B。A8B37C36D959串的長(zhǎng)度是指B。A串中所含不同字母的個(gè)數(shù)B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù)D串中所含非空格字符的個(gè)數(shù)60串是一種特殊的線性表，其特殊性表達(dá)在B。A 可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符專(zhuān)業(yè)資料整理WORD格式12專(zhuān)業(yè)資料整理WORD格式C可以鏈?zhǔn)酱鎯?chǔ)D數(shù)據(jù)元素可以是多個(gè)字符61設(shè)有兩個(gè)串 p 和 q，求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為B。A 連接B模式匹配C求子串D求串長(zhǎng)62數(shù)組 A 中，每個(gè)元素的長(zhǎng)度為3 個(gè)字節(jié)，行下標(biāo)i 從 1 到 8，列下標(biāo) j 從 1到 10，從首地址 SA 開(kāi)場(chǎng)連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為C

20、。A SA 141B SA144CSA222DSA22563數(shù)組 A 中，每個(gè)元素的長(zhǎng)度為3 個(gè)字節(jié)，行下標(biāo)i 從 1 到 8，列下標(biāo) j 從 1到 10，從首地址 SA 開(kāi)場(chǎng)連續(xù)存放的存儲(chǔ)器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為C。A SA 141B SA180CSA222DSA22564假設(shè)聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froat average=new float30;假設(shè)該數(shù)組的內(nèi)存起始位置為200， average15的內(nèi)存地址是C。A 214B 215C260D25665設(shè)二維數(shù)組A1 ,m,1,n按行存儲(chǔ)在數(shù)組B 中，那么二維數(shù)組元素Ai,j在一維數(shù)組 B 中的下標(biāo)為A。A n*(

21、i-1)+jB n*(i-1)+j-1Ci*(j-1)Dj*m+i-1專(zhuān)業(yè)資料整理WORD格式13專(zhuān)業(yè)資料整理WORD格式66有一個(gè) 100×90 的稀疏矩陣，非0 元素有 10，設(shè)每個(gè)整型數(shù)占2 個(gè)字節(jié)，那么用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是B。A 20B 66C18 000D3367數(shù)組 A0 , 4，-1 ,-3，5, 7中含有的元素個(gè)數(shù)是 A。A 55B 45C36D1668對(duì)矩陣進(jìn)展壓縮存儲(chǔ)是為了D。A 方便運(yùn)算B方便存儲(chǔ)C提高運(yùn)算速度D減少存儲(chǔ)空間69設(shè)有一個(gè) 10 階的對(duì)稱(chēng)矩陣 A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)， a1，1為第一個(gè)元素，其存儲(chǔ)地址為 1，每個(gè)元素占

22、 1 個(gè)地址空間，那么 a8，5的地址為B 。A 13B 33C18D4070稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種，即C。A 二維數(shù)組和三維數(shù)組B三元組和散列C三元組和十字鏈表D散列和十字鏈表71樹(shù)最適合用來(lái)表示C。A 有序數(shù)據(jù)元素B無(wú)序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無(wú)聯(lián)系的數(shù)據(jù)專(zhuān)業(yè)資料整理WORD格式14專(zhuān)業(yè)資料整理WORD格式72深度為 5 的二叉樹(shù)至多有C個(gè)結(jié)點(diǎn)。A 16B 32C31C1073對(duì)一個(gè)滿二叉樹(shù)， m 個(gè)葉子， n 個(gè)結(jié)點(diǎn)，深度為h，那么D。A n = h+mB h+m = 2nC m = h-1Dn = 2h-174任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后

23、序遍歷序列中的相對(duì)次序A 。A 不發(fā)生改變B發(fā)生改變C不能確定D以上都不對(duì)75在線索化樹(shù)中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹(shù)構(gòu)造信息，還是線索化信息，假設(shè)0 標(biāo)識(shí)樹(shù)構(gòu)造信息， 1 標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為 _ D_。A 00B01C10D1176在下述論述中，正確的選項(xiàng)是D。只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0；二叉樹(shù)的度為2；二叉樹(shù)的左右子樹(shù)可任意交換；深度為 K 的順序二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度一樣的滿二叉樹(shù)。A BCD77設(shè)森林 F 對(duì)應(yīng)的二叉樹(shù)為B，它有 m 個(gè)結(jié)點(diǎn)， B 的根為 p，p 的右子樹(shù)的結(jié)專(zhuān)業(yè)資料整理WORD格式15專(zhuān)業(yè)資料整理WORD格式點(diǎn)

24、個(gè)數(shù)為 n，森林 F 中第一棵樹(shù)的結(jié)點(diǎn)的個(gè)數(shù)是A。A m-nBm-n-1Cn+1D不能確定78假設(shè)一棵二叉樹(shù)具有10 個(gè)度為 2 的結(jié)點(diǎn)， 5 個(gè)度為 1 的結(jié)點(diǎn)，那么度為0 的結(jié)點(diǎn)的個(gè)數(shù)是B 。A 9B11C15D不能確定79具有 10 個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)中有B個(gè)度為 2 的結(jié)點(diǎn)。A 8B9C10D1180在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。A1/2 B1C2D 481在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A1/2B1C2D4左中右我按我做的題目舉例吧：后序序列為：bfegcda, 中序序列為： badefcg, 求前序序列。這里會(huì)用：后序列序列最

25、后一個(gè)值即樹(shù)或子樹(shù)的根。由后序“bfegcda 知 a 為根，由中序“badefcg知 a 的左子樹(shù)僅有b 一個(gè)節(jié)點(diǎn)。即圖1.去除序列中的b 和 a 得后序“fegcd和中序“defcg，可知， d 為 a 的右子樹(shù)樹(shù)根后序最后一個(gè)值且d 的左子樹(shù)為空 d 前面無(wú)值，同理再去掉d 得到，“fegc和“efcg，可知 c 為 d 的右子樹(shù)樹(shù)根，如圖2.由中序“efcg知c 的右子樹(shù)為 g，左子樹(shù)為 e,f ，同理得最后結(jié)果樹(shù)為圖3.于是得出前序列為：abdcefg82某二叉樹(shù)結(jié)點(diǎn)的中序序列為ABCDEFG ，后序序列為 BDCAFGE ，那么其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：CA3B2C4D 5專(zhuān)業(yè)資料整理

26、WORD格式16專(zhuān)業(yè)資料整理WORD格式83一算術(shù)表達(dá)式的中綴形式為AB *CD/E，后綴形式為 ABC*+DE/，其前綴形式為D。將算術(shù)表達(dá)式的中綴形式作為一棵二叉樹(shù)的中序遍歷序列，將后綴形式作為這棵二叉樹(shù)的后序遍歷序列，再由二叉樹(shù)的中序遍歷序列和后序遍歷序列唯一確實(shí)定這棵二叉樹(shù)，在對(duì)其進(jìn)展先序遍歷，就可得出算術(shù)表達(dá)式的前綴形式。AA+B*C/DEBA+B*CD/EC+*ABC/DED+A*BC/DE84一個(gè)圖，如下列圖，假設(shè)從頂點(diǎn) a 出a發(fā)按深度搜索法進(jìn)展遍歷，那么可能得到的一種頂點(diǎn)序bec列為_(kāi)D_；按廣度搜索法進(jìn)展遍歷，那么可能df得到的一種頂點(diǎn)序列為 _A_； Aa，b，e，c，d

27、，fBa，c，f ，e，b，dCa，e，b，c，f，d，Da，e，d，f ，c，b Aa，b，c，e，d，fBa，b，c，e，f，dCa，e，b，c，f，d，Da，c，f ，d，e，b85采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的_A_。A 先序遍歷B中序遍歷C后序遍歷D按層遍歷86采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的_D_。A 先序遍歷B中序遍歷C后序遍歷D按層遍歷87具有 n 個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。專(zhuān)業(yè)資料整理WORD格式17專(zhuān)業(yè)資料整理WORD格式An-1B nC n(n-1)/2D 2n88廣義表a，a的表頭是C，表尾是C。A aBC aD a89廣義表a的

28、表頭是C，表尾是B。A aBC aD a90順序查找法適合于存儲(chǔ)構(gòu)造為B的線性表。A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)91對(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)按關(guān)鍵字有序排列92采用折半查找法查找長(zhǎng)度為n 的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為D 。AO(n2)BO(nlog2n)CO(n)DO(log2n)93有一個(gè)有序表為 1，3，9，12，32，41，45，62，75，77，82，95，100，專(zhuān)業(yè)資料整理WORD格式18專(zhuān)業(yè)資料整理WORD格式當(dāng)折半查找值為82 的結(jié)點(diǎn)時(shí)，

29、 C次比較后查找成功。A 11B 5C 4D894二叉樹(shù)為二叉排序樹(shù)的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法B。A正確B錯(cuò)誤95下面關(guān)于 B 樹(shù)和 B+樹(shù)的表達(dá)中，不正確的結(jié)論是A。AB 樹(shù)和 B+樹(shù)都能有效的支持順序查找BB 樹(shù)和 B+樹(shù)都能有效的支持隨機(jī)查找CB 樹(shù)和 B+樹(shù)都是平衡的多叉樹(shù)DB 樹(shù)和 B+樹(shù)都可用于文件索引構(gòu)造96以下說(shuō)法錯(cuò)誤的選項(xiàng)是B。A 散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址B散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。C負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。D散列表的查找效率主要取決于散列表構(gòu)造

30、時(shí)選取的散列函數(shù)和處理沖突的方法。97查找效率最高的二叉排序樹(shù)是C。A 所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)。B所有結(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)。專(zhuān)業(yè)資料整理WORD格式19專(zhuān)業(yè)資料整理WORD格式C平衡二叉樹(shù)。D沒(méi)有左子樹(shù)的二叉排序樹(shù)。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)展比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為C。A 希爾排序B。冒泡排序C 插入排序D。選擇排序99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是D 。A 希爾排序B冒泡排序C直接插入排序D直接選擇排序？100堆是一種有用的數(shù)據(jù)構(gòu)造。以下關(guān)鍵碼序列D是一個(gè)堆。A 94,31

31、,53,23,16,72B94,53,31,72,16,23將所有數(shù)據(jù)序列按完全二叉樹(shù)從根開(kāi)場(chǎng)放,如果所有分支都小于或者等于孩子結(jié)點(diǎn)關(guān)鍵碼,就是小頂堆 ,反之 ,如果所有分支結(jié)點(diǎn)的關(guān)鍵碼大于或者等于孩子結(jié)點(diǎn)關(guān)鍵碼,那么為大頂堆C16,53,23,94,31,72D16,31,23,94,53,72101堆排序是一種B排序。A 插入B 選擇C交換D歸并102D在鏈表中進(jìn)展操作比在順序表中進(jìn)展操作效率高。A 順序查找B折半查找C分塊查找D插入專(zhuān)業(yè)資料整理WORD格式20專(zhuān)業(yè)資料整理WORD格式103直接選擇排序的時(shí)間復(fù)雜度為D。n 為元素個(gè)數(shù)A On)B O(log2n)CO(nlog2n)D O

32、(n2)二、填空題。1數(shù)據(jù)邏輯構(gòu)造包括線性構(gòu)造、樹(shù)形構(gòu)造和圖狀構(gòu)造三種類(lèi)型，樹(shù)形構(gòu)造和圖狀構(gòu)造合稱(chēng)非線性構(gòu)造。2數(shù)據(jù)的邏輯構(gòu)造分為集合、線性構(gòu)造、樹(shù)形構(gòu)造和圖狀構(gòu)造4 種。3在線性構(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)。4線性構(gòu)造中元素之間存在一對(duì)一關(guān)系，樹(shù)形構(gòu)造中元素之間存在一對(duì)多關(guān)系，圖形構(gòu)造中元素之間存在多對(duì)多關(guān)系。5在樹(shù)形構(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è)。專(zhuān)業(yè)資料整理WORD格式21專(zhuān)業(yè)資料整理WORD格式6數(shù)

33、據(jù)構(gòu)造的根本存儲(chǔ)方法是順序、鏈?zhǔn)健⑺饕蜕⒘写鎯?chǔ) 。7衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、強(qiáng)健性和時(shí)間復(fù)雜度與空間復(fù)雜度。8評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度 和 空間復(fù)雜度 兩個(gè)方面考察。9算法的 5 個(gè)重要特性是有窮性、確定性、可行性、輸入和輸出。10在一個(gè)長(zhǎng)度為 n 的順序表中刪除第i 個(gè)元素時(shí)，需向前移動(dòng)n-i-1個(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ù)

34、根本穩(wěn)定，且很少進(jìn)展插入和刪除操作，但要求以最專(zhuān)業(yè)資料整理WORD格式22專(zhuān)業(yè)資料整理WORD格式快的速度存取線性表的元素是，應(yīng)采用順序存儲(chǔ)構(gòu)造。15根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成單鏈表和 雙鏈表 。16順序存儲(chǔ)構(gòu)造是通過(guò)下標(biāo) 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)構(gòu)造是通過(guò) 指針 表示元素之間的關(guān)系的。17帶頭結(jié)點(diǎn)的循環(huán)鏈表L 中只有一個(gè)元素結(jié)點(diǎn)的條件是L->next->next=L。18棧是限定僅在表尾進(jìn)展插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先出的原那么。19空串是零個(gè)字符的串，其長(zhǎng)度等于零?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串，其長(zhǎng)度等于其包含的

35、空格個(gè)數(shù)。20組成串的數(shù)據(jù)元素只能是單個(gè)字符。21一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的局部稱(chēng)為該串的子串。22子串str在主串datastructure中的位置是5。23二維數(shù)組 M 的每個(gè)元素是 6 個(gè)字符組成的串， 行下標(biāo) i 的X圍從 0 到 8，列專(zhuān)業(yè)資料整理WORD格式23專(zhuān)業(yè)資料整理WORD格式下標(biāo) j 的X圍從 1 到 10，那么存放 M 至少需要 540 個(gè)字節(jié)； M 的第 8 列和第 5 行共占 108 個(gè)字節(jié)。24稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈表。25廣義表a，b，c，d的長(zhǎng)度是3，深度是4。26在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為 n0，度為 2 的結(jié)點(diǎn)

36、的個(gè)數(shù)為n2，那么有 n0n2+1。27在有 n 個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為_(kāi)n+1_。28一棵有 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共有_2n-1_個(gè)結(jié)點(diǎn)。29深度為 5 的二叉樹(shù)至多有31個(gè)結(jié)點(diǎn)。30假設(shè)某二叉樹(shù)有20 個(gè)葉子結(jié)點(diǎn)，有30 個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，那么該二叉樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)為69。31某二叉樹(shù)的前序遍歷序列是abdgcefh，中序序列是 dgbaechf，其后序序列為gdbehfca。專(zhuān)業(yè)資料整理WORD格式24專(zhuān)業(yè)資料整理WORD格式32線索二叉樹(shù)的左線索指向其遍歷序列中的前驅(qū)，右線索指向其遍歷序列中的后繼。33在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n 無(wú)關(guān)的查找方法是散列查找

37、法。34在分塊索引查找方法中，首先查找索引表，然后查找相應(yīng)的塊表。35一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)展排序的過(guò)程。36具有 10 個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)45_。37圖G 的鄰接表如下列圖，其從頂點(diǎn)v1 出發(fā)的深度優(yōu)先搜索序列為_(kāi)v1v2v3v6v5v4_，其從頂點(diǎn) v1 出發(fā)的廣度優(yōu)先搜索序列為_(kāi)v1v2v5v4v3v6_。v1v2v5v 4v2v3v5v3v6v4v5v4v6v 3v638索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)構(gòu)造。一個(gè)索引隸屬于某個(gè)數(shù)專(zhuān)業(yè)資料整理WORD格式25專(zhuān)業(yè)資料整理WORD格式據(jù)記錄集，它由假設(shè)干索引

38、項(xiàng)組成，索引項(xiàng)的構(gòu)造為關(guān)鍵字和 關(guān)鍵字對(duì)應(yīng)記錄的地址。39Prim 算法生成一個(gè)最小生成樹(shù)每一步選擇都要滿足邊的總數(shù)不超過(guò) n-1，當(dāng)前選擇的邊的權(quán)值是候選邊中最小的， 選中的邊參加樹(shù)中不產(chǎn)生回路三項(xiàng)原那么。40在一棵 m 階 B 樹(shù)中，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)最多有m棵子樹(shù)，最少有m/2棵子樹(shù)。三、判斷題。1在決定選取何種存儲(chǔ)構(gòu)造時(shí)，一般不考慮各結(jié)點(diǎn)的值如何。2抽象數(shù)據(jù)類(lèi)型 ADT 包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè) ADT 的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。 ( )3抽象數(shù)據(jù)類(lèi)型與計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)無(wú)關(guān)。4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。 ×5線性表采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。 × 6對(duì)任何數(shù)據(jù)構(gòu)造鏈?zhǔn)酱鎯?chǔ)構(gòu)造一定優(yōu)于順序存儲(chǔ)構(gòu)造。 ×7順序存儲(chǔ)方式只能用于存儲(chǔ)線性構(gòu)造。 ×8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。 ×9線性表中每個(gè)