數(shù)據(jù)結(jié)構(gòu)與算法C語言版期末復(fù)習(xí)題

《數(shù)據(jù)結(jié)構(gòu)與算法》期末復(fù)習(xí)題一、選擇題。.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為—C 。A.動態(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ī)內(nèi)存中的表示是指。A.數(shù)據(jù)的存儲結(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ī)無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A.邏輯B.存儲 C.邏輯和存儲 D.物理.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲C。A.數(shù)據(jù)的處理方法 B.數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系 D.數(shù)據(jù)的存儲方法.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮A。A.各結(jié)點(diǎn)的值如何 B.結(jié)點(diǎn)個數(shù)的多少C.對數(shù)據(jù)有哪些運(yùn)算D.所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。.以下說法正確的是D。A.數(shù)據(jù)項是數(shù)據(jù)的基本單位B.數(shù)據(jù)元素是數(shù)據(jù)的最小單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu).算法分析的目的是C ，算法分析的兩個主要方面是_AA.找出數(shù)據(jù)結(jié)構(gòu)的合理性A.找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(jìn)A.空間復(fù)雜度和時間復(fù)雜度C.可讀性和文檔性B.研究算法中的輸入和輸出的關(guān)系C分析算法的易讀性和文檔性B.正確性和簡明性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性.下面程序段的時間復(fù)雜度是O(n2)s=0;for(I=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;.下面程序段的時間復(fù)雜度是O(n*m) for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;1.下面程序段的時間復(fù)雜度是O(log3n) 。=0；while(i<=n)i=i*3；.在以下的敘述中，正確的是 B。A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出D.隊列的操作方式是先進(jìn)后出.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著上_。A.數(shù)據(jù)元素具有同一特點(diǎn)B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等.鏈表不具備的特點(diǎn)是 A。A.可隨機(jī)訪問任一結(jié)點(diǎn) B.插入刪除不需要移動元素C.不必事先估計存儲空間 D.所需空間與其長度成正比.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 A。A.head==NULL Bhead->next==NULLC.head->next==headDhead!=NULL15.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。A.head==NULL Bhead->next==NULLC.head->next==headDhead!=NULL.若某表最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)或刪除最后一個結(jié)點(diǎn)，則采用D 存儲方式最節(jié)省運(yùn)算時間。A.單鏈表B.給出表頭指針的單循環(huán)鏈表 C.雙鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表.需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是_」_。A.單鏈表 B.靜態(tài)鏈表 C.線性鏈表 D.順序存儲結(jié)構(gòu).非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足C。A.p->next==NULLB.p==NULLC.p->next==headD.p==head.在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 D。p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorp->prior=s；p->prior->next=s；s->next=p；s->prior=p->priors->next=p；s->prior=p->prior；p->prior=s；p->prior->next=ss->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s.如果最常用的操作是取第i個結(jié)點(diǎn)及其前驅(qū)，則采用D存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表 C.單循環(huán)鏈表 D.順序表.在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然保持有序的時間復(fù)雜度是B。A.O(1)B.O(n) C.O(n2)D.O(nlog2n).在一個長度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行_B_操作與鏈表的長度有關(guān)。A.刪除單鏈表中的第一個元素B.刪除單鏈表中的最后一個元素C.在單鏈表第一個元素前插入一個新元素D.在單鏈表最后一個元素后插入一個新元素.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。A.插入、刪除操作更簡單B.可以進(jìn)行隨機(jī)訪問C.可以省略表頭指針或表尾指針D.順序訪問相鄰結(jié)點(diǎn)更靈活.如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用—。A.只有表頭指針沒有表尾指針的循環(huán)單鏈表B.只有表尾指針沒有表頭指針的循環(huán)單鏈表C.非循環(huán)雙鏈表D.循環(huán)雙鏈表.在長度為n的順序表的第i個位置上插入一個元素(1WiWn+1),元素的移動次數(shù)為：A。A.n-i+1 B.n-i C.i D.i-1.對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為_C—。A.順序表 B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表 D.單鏈表.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？ C。A插入運(yùn)算方便 B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大 D刪除運(yùn)算方便.下面關(guān)于線性表的敘述中，錯誤的是哪一個？。A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進(jìn)行插入和刪除操作。3C線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D線性表采用鏈?zhǔn)酱鎯?，便于進(jìn)行插入和刪除操作。.線性表是具有n個B 的有限序列。A.字符B.數(shù)據(jù)元素 C.數(shù)據(jù)項 D.表元素.在n個結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時間復(fù)雜度是O(1)的操作是AA.訪問第i(1<=i<=n)個結(jié)點(diǎn)和求第i個結(jié)點(diǎn)的直接前驅(qū)(1<i<=n)B.在第i(1<=i<=n)個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)C.刪除第i(1<=i<=n)個結(jié)點(diǎn)D.以上都不對.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為一C_。A.O(0)B.O⑴ C.O(n)D.0(n2).對于順序存儲的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時間復(fù)雜度為 C。A.O(n)O(n)B.O(n)O(1) C.O(1)O(n)D.O(1)O(1).線性表(a1,a2,…，an)以鏈?zhǔn)椒绞酱鎯?，訪問第i位置元素的時間復(fù)雜度為 C。A.O(0)B.O(1)C.O(n)D.O(n2).單鏈表中，增加一個頭結(jié)點(diǎn)的目的是為了C。A.使單鏈表至少有一個結(jié)點(diǎn) B.標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C.方面運(yùn)算的實(shí)現(xiàn) D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是 B。A.p->next=s；s->next=p->next B.s->next=p->next；p->next=s;C.p->next=s；p->next=s->next D.p->next=s->next；p->next=s.線性表的順序存儲結(jié)構(gòu)是一種A。A.隨機(jī)存取的存儲結(jié)構(gòu) B.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu) D.Hash存取的存儲結(jié)構(gòu).棧的特點(diǎn)是B ，隊列的特點(diǎn)是A—。A.先進(jìn)先出B.先進(jìn)后出.棧和隊列的共同點(diǎn)是C。A.都是先進(jìn)后出 B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素 D.沒有共同點(diǎn).一個棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是 C。A.edcba B.decbaC.dceabD.abcde

.設(shè)有一個棧，元素依次進(jìn)棧的順序為A、B、C、D、E。下列C 是不可能的出棧序列。A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,D D.E,D,C,B,A.以下B不是隊列的基本運(yùn)算？A.從隊尾插入一個新元素 B.從隊列中刪除第i個元素C.判斷一個隊列是否為空 D.讀取隊頭元素的值42.若已知一個棧的進(jìn)棧序列是42.若已知一個棧的進(jìn)棧序列是1,2,3,,n,=n，貝Upi為 C。A.iB.n-i C.n-i+1 D.不確定其輸出序列為pl,p2,p3,…，pn,若pl43.判定一個順序棧st（最多元素為MaxSize）為空的條件是_BA.st->top!=-1 B.st->top==-1C.st->top!=MaxSize D.st->top==MaxSize44.判定一個順序棧st（最多元素為MaxSize）為滿的條件是D。A.st->top!=-1 B.st->top==-1C.st->top!=MaxSize D.st->top==MaxSize.一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是_q—。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1.判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是_C—。A.qu->rear-qu->front==MaxSize B.qu->rear-qu->front-1==MaxSizeC.qu->rear==qu->front D.qu->rear=qu->front-1.在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環(huán)隊列空的條件是C。A.front==rear+1 B.rear==front+1 C.front==rearD.front==0.向一個棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時，應(yīng)執(zhí)行D操作。A.h->next=s; B.s->next=h;C.s->next=h;h=s; D.s->next=h->next;h->next=s;.輸入序列為ABC,可以變?yōu)镃BA時，經(jīng)過的棧操作為—B_。A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop.若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1m],top[1]、top⑵分別代表第1和第2個棧的棧頂，棧1的底在V[1],棧2的底在V[m],則棧滿的條件是■―B_。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=m D.top[1]=top[2].設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法，采用4數(shù)據(jù)結(jié)構(gòu)最佳。TOC\o"1-5"\h\zA.線性表的順序存儲結(jié)構(gòu) B.隊列 C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D.棧.允許對隊列進(jìn)行的操作有D。A.對隊列中的元素排序B.取出最近進(jìn)隊的元素C.在隊頭元素之前插入元素 D.刪除隊頭元素.對于循環(huán)隊列 D。A.無法判斷隊列是否為空 B.無法判斷隊列是否為滿C.隊列不可能滿 D.以上說法都不對.若用一個大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3,當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 B。A.1和5B.2和4C.4和2D.5和1.隊列的“先進(jìn)先出”特性是指—D—。A.最早插入隊列中的元素總是最后被刪除B.當(dāng)同時進(jìn)行插入、刪除操作時，總是插入操作優(yōu)先C.每當(dāng)有刪除操作時，總是要先做一次插入操作D.每次從隊列中刪除的總是最早插入的元素.和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是A。A.通常不會出現(xiàn)棧滿的情況 B.通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實(shí)現(xiàn) D.刪除操作更容易實(shí)現(xiàn).用不帶頭結(jié)點(diǎn)的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點(diǎn)，尾指針指向隊尾結(jié)點(diǎn)，則在進(jìn)行出隊操作時 C。A.僅修改隊頭指針 B.僅修改隊尾指針C.隊頭、隊尾指針都可能要修改 D.隊頭、隊尾指針都要修改.若串S='software',其子串的數(shù)目是B。A.8 B.37C.36D.9.串的長度是指」_。A.串中所含不同字母的個數(shù) B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù) D.串中所含非空格字符的個數(shù).串是一種特殊的線性表，其特殊性體現(xiàn)在」_。A.可以順序存儲 B.數(shù)據(jù)元素是一個字符C可以鏈?zhǔn)酱鎯?D.數(shù)據(jù)元素可以是多個字符.設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為」—。A.連接 B.模式匹配C.求子串D.求串長.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始地址為 C。A.SA+141B.SA+144 C.SA+222D.SA+225.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[5][8]的起始地址為C。A.SA+141B.SA+180 C.SA+222D.SA+225.若聲明一個浮點(diǎn)數(shù)數(shù)組如下：froataverage[]=newfloat[30];假設(shè)該數(shù)組的內(nèi)存起始位置為200,average[15]的內(nèi)存地址是C。A.214B.215 C.260 D.256.設(shè)二維數(shù)組A[1…m,1…n]按行存儲在數(shù)組B中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為A。A.n*(i-1)+jB.n*(i-1)+j-1 C.i*(j-1)D.j*m+i-1.有一個100X90的稀疏矩陣，非0元素有10,設(shè)每個整型數(shù)占2個字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是B。A.20B.66C.18000D.33.數(shù)組A[0…4,-1…-3,5…7]中含有的元素個數(shù)是A。A.55B.45C.36 D.16.對矩陣進(jìn)行壓縮存儲是為了 D。A.方便運(yùn)算B.方便存儲 C.提高運(yùn)算速度D.減少存儲空間.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，a11為第一個元素，其存儲地址為1,每個元素占1個地址空間，則a8,5的地址為。,A.13B.33C.18D.40.稀疏矩陣一般的壓縮存儲方式有兩種，即C。A.二維數(shù)組和三維數(shù)組 B. 三元組和散列C.三元組和十字鏈表 D. 散列和十字鏈表.樹最適合用來表示C。A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù).深度為5的二叉樹至多有 C個結(jié)點(diǎn)。A.16 B.32C. 31C. 10.對一個滿二叉樹，m個葉子，n個結(jié)點(diǎn)，深度為h,則D—A.n=h+mBh+m=2nCm=h-1Dn=2h-1

.任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序A。A.不發(fā)生改變 B.發(fā)生改變C.不能確定 D.以上都不對.在線索化樹中，每個結(jié)點(diǎn)必須設(shè)置一個標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識樹結(jié)構(gòu)信息，1標(biāo)識線索，對應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識為D 。A.00 B.01 C.10 D.11.在下述論述中，正確的是D。①只有一個結(jié)點(diǎn)的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的順序二叉樹的結(jié)點(diǎn)個數(shù)小于或等于深度相同的滿二叉樹。A.①②③ B.②③④C.②④D.①④.設(shè)森林F對應(yīng)的二叉樹為B,它有m個結(jié)點(diǎn)，B的根為p,p的右子樹的結(jié)點(diǎn)個數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)的個數(shù)是一A 。A.m-n B.m-n-1C.n+1D.不能確定.若一棵二叉樹具有10個度為2的結(jié)點(diǎn),5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個數(shù)是A.9B.11 C.15 D.不能確定.具有10個葉子結(jié)點(diǎn)的二叉樹中有B個度為2的結(jié)點(diǎn)。A.8 B.9C.10D.11.在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。A.1/2B1C2D4.在一個有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的」_倍。A.1/2B1C2D4.某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹中結(jié)點(diǎn)數(shù)目為：—C—A.3 B.2 C.4 D.5.已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為 D—。A.-A+B*C/DE B.-A+B*CD/E C-+*ABC/DE D.-+A*BC/DE.已知一個圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為D；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為___A一;TOC\o"1-5"\h\z①A.a, b, e, c, d, f B. a, c, f, e, b, dC.a, e, b, c, f, d, D. a, e, d, f, c, b②A.a, b, c, e, d, f B. a, b, c, e, f, dC.a,e,b,c,f,d,D.a,c,f,d,e,b.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的___AA.先序遍歷 B.中序遍歷 C.后序遍歷 D.按層遍歷.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的一D一。A.先序遍歷 B.中序遍歷 C.后序遍歷 D.按層遍歷.具有n個結(jié)點(diǎn)的連通圖至少有 A條邊。TOC\o"1-5"\h\zA. n-1B.nC.n(n-1)/2 D.2n.廣義表((a),a)的表頭是C，表尾是C。A.a B () C (a) D ((a)).廣義表((a))的表頭是J^_，表尾是B。A.a B () C (a) D ((a)).順序查找法適合于存儲結(jié)構(gòu)為B的線性表。A散列存儲 B順序存儲或鏈?zhǔn)酱鎯壓縮存儲 D索引存儲.對線性表進(jìn)行折半查找時，要求線性表必須B。A以順序方式存儲 B以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?D以鏈?zhǔn)椒绞酱鎯Γ医Y(jié)點(diǎn)按關(guān)鍵字有序排列TOC\o"1-5"\h\z.采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為 D。AO(n2) BO(nlog2n) CO(n) DO(log2n).有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100},當(dāng)折半查找值為82的結(jié)點(diǎn)時，_C一次比較后查找成功。A. 11 B5 C4 D8.二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法B。A正確 B錯誤.下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是 A。AB樹和B+樹都能有效的支持順序查找 BB樹和B+樹都能有效的支持隨機(jī)查找CB樹和B+樹都是平衡的多叉樹 DB樹和B+樹都可用于文件索引結(jié)構(gòu).以下說法錯誤的是B。A.散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B.散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。C.負(fù)載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D.散列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97.查找效率最高的二叉排序樹是C。A.所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。B.所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。C.平衡二叉樹。D.沒有左子樹的二叉排序樹。.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C。A.希爾排序 B。冒泡排序 C插入排序 D。選擇排序.在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是3A.希爾排序B.冒泡排序 C.直接插入排序 D.直接選擇排序.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列 D是一個堆。A.94,31,53,23,16,72 B.94,53,31,72,16,23C.16,53,23,94,31,72 D.16,31,23,94,53,72.堆排序是一種 B排序。A.插入 B.選擇 C.交換 D.歸并.D 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A.順序查找 B.折半查找 C.分塊查找 D.插入.直接選擇排序的時間復(fù)雜度為 D。(n為元素個數(shù))A.O(n) B.O(log2n) C.O(nlog2n) D.O(n2)二、填空題。.數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型,樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。.數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。.在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有」個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有個后續(xù)結(jié)點(diǎn)。.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。.在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn),其余每個結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個。10.數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈?zhǔn)?、_索引和散列存儲。.衡量一個算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時間復(fù)雜度與空間復(fù)雜度。.評估一個算法的優(yōu)劣，通常從時間復(fù)雜度和空間復(fù)雜度 兩個方面考察。.算法的5個重要特性是有窮性、確定性、 可行性、輸入和輸出。.在一個長度為n的順序表中刪除第i個元素時，需向前移動n-i-1個元素。.在單鏈表中，要刪除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的—前工結(jié)點(diǎn)。.在雙鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向前驅(qū)結(jié)點(diǎn),另一個指向后繼結(jié)點(diǎn)。.在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動0個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與位置有關(guān)。.當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用順序存儲結(jié)構(gòu)。.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)包含的指針個數(shù)，將線性鏈表分成單鏈表和雙鏈表。.順序存儲結(jié)構(gòu)是通過下標(biāo) 表示元素之間的關(guān)系的：鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指針表示元素之間的關(guān)系的。.帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是_L->next->next=L。.棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表,其運(yùn)算遵循后進(jìn)先出的原則。.空串是零個字符的串,其長度等于零?？瞻状怯梢粋€或多個空格字符組成的串,其長度等于其包含的空格個數(shù)。.組成串的數(shù)據(jù)元素只能是單個字符。.一個字符串中任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。.子串“str"在主串“datastructure”中的位置是 5 。.二維數(shù)組M的每個元素是6個字符組成的串，行下標(biāo)i的范圍從0到8,列下標(biāo)j的范圍從1到10,則存放M至少需要540個字節(jié)；M的第8列和第5行共占1M個字節(jié)。.稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。11.廣義表((a),((b),c),(((d))))的長度是3，深度是4。.在一棵二叉樹中，度為零的結(jié)點(diǎn)的個數(shù)為n0,度為2的結(jié)點(diǎn)的個數(shù)為n2,則有n0=n2+1 。.在有n個結(jié)點(diǎn)的二叉鏈表中，空鏈域的個數(shù)為一n+1__。.一棵有n個葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個結(jié)點(diǎn)。.深度為5的二叉樹至多有31個結(jié)點(diǎn)。.若某二叉樹有20個葉子結(jié)點(diǎn)，有30個結(jié)點(diǎn)僅有一個孩子，則該二叉樹的總結(jié)點(diǎn)個數(shù)為69。.某二叉樹的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列為gdbehfca。.線索二叉樹的左線索指向其遍歷序列中的前驅(qū) ，右線索指向其遍歷序列中的后繼。.在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)的杳找方法是散列杳找法。.在分塊索引查找方法中，首先查找 索引表 ，然后杳找相應(yīng)的塊表。.一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。.具有10個頂點(diǎn)的無向圖，邊的總數(shù)最多為45。.已知圖G的鄰接表如圖所示，其從頂點(diǎn)v1出發(fā)的深度優(yōu)先搜索序列為v1v2V3V6V5V4,其從頂點(diǎn)v1出發(fā)的廣度優(yōu)先搜索序列為v1v2V5V4V3V6.。.索引是為了加快檢索速度而引進(jìn)的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對應(yīng)記錄的地址。12.Prim算法生成一個最小生成樹每一步選擇都要滿足汕的總數(shù)不超過止1當(dāng)前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。.在一棵m階B樹中，除根結(jié)點(diǎn)外，每個結(jié)點(diǎn)最多有m棵子樹，最少有m/2棵子樹。三、判斷題。.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點(diǎn)的值如何。（J）.抽象數(shù)據(jù)類型（人口丁）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機(jī)中實(shí)現(xiàn)。（J）.抽象數(shù)據(jù)類型與計算機(jī)內(nèi)部表示和實(shí)現(xiàn)無關(guān)。（J）.順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶?。（X）.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲空間可以是不連續(xù)