數(shù)據(jù)結(jié)構(gòu)習(xí)題集2015

淮南師范學(xué)院計(jì)算機(jī)學(xué)院網(wǎng)絡(luò)工程14（1）班數(shù)據(jù)結(jié)構(gòu)作業(yè) PAGE1-數(shù)據(jù)結(jié)構(gòu)作業(yè)2014-2015第2學(xué)期課程：數(shù)據(jù)結(jié)構(gòu)學(xué)院：計(jì)算機(jī)學(xué)院專業(yè)：網(wǎng)絡(luò)工程班級(jí)：14（1）班姓名：學(xué)號(hào)：

第1章緒論一、選擇題：1、下列算法的時(shí)間復(fù)雜度是（）for(i=0;i<n;i++) c[i]=i；A．O（1）B．O（n）C．O（log2n）D．O（nlog2n）2、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址，這種方法稱為（）A．索引存儲(chǔ)方法B．順序存儲(chǔ)方法C．鏈?zhǔn)酱鎯?chǔ)方法D．散列存儲(chǔ)方法3、以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)？（）。A.順序表B.鏈表C.散列表D.隊(duì)列4、算法在發(fā)生非法操作時(shí)可以做出處理的特性稱為（）。A．正確性 B．易讀性 C．健壯性 D．高效性5、邏輯結(jié)構(gòu)是指數(shù)據(jù)元素的（）。A．關(guān)聯(lián)方式 B．存儲(chǔ)方式 C．結(jié)構(gòu) D．?dāng)?shù)據(jù)項(xiàng)6、研究數(shù)據(jù)結(jié)構(gòu)就是研究（）。A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) B．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其數(shù)據(jù)的運(yùn)算7、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）。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)8、以下有關(guān)數(shù)據(jù)的敘述中錯(cuò)誤的是（）。A．計(jì)算機(jī)能夠處理的數(shù)據(jù)包括整數(shù)、實(shí)數(shù)、字符、聲音、圖像等B．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它取決于數(shù)據(jù)的存儲(chǔ)方式C．?dāng)?shù)據(jù)存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)依賴于計(jì)算機(jī)語(yǔ)言D．?dāng)?shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的9、數(shù)據(jù)的基本單位是（）。A.數(shù)據(jù)結(jié)構(gòu)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.文件10、下列算法的時(shí)間復(fù)雜度是（）for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j；A．O（m2）B．O（n2）C．O（m×n）D．O（m+n）11、算法分析的兩個(gè)主要方面是（）。A．正確性和簡(jiǎn)明性 B．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性C．可讀性和可維護(hù)性 D．時(shí)間復(fù)雜性和空間復(fù)雜性12、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（）。A．存儲(chǔ)結(jié)構(gòu)B．邏輯結(jié)構(gòu)C．算法D．操作13、下列敘述中正確的是()。A．一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)B．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)C．一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D．一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率二、填空題：1、數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容，分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、（）和（）。2、()結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。3、程序段“for(i=1;i<=n;i++){k++;for(j=1;j<=n;j++)x=x+k;}”的時(shí)間復(fù)雜度為()。4、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的（）以及它們之間的（）和運(yùn)算等的學(xué)科。5、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是（）的有限集合，R是D上的（）有限集合。6、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是（）和（）。7、線性結(jié)構(gòu)中元素之間存在（）關(guān)系，樹(shù)形結(jié)構(gòu)中元素之間存在（）關(guān)系，圖形結(jié)構(gòu)中元素之間存在（）關(guān)系。8、在線性結(jié)構(gòu)中，（）沒(méi)有前驅(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)。9、在樹(shù)形結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有（）結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有（）個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有（）結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。10、在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以（）。11、對(duì)于給定的n個(gè)元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有（）四種。12、順序映象的特點(diǎn)是借助元素在存儲(chǔ)器中的（）來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映象的特點(diǎn)是借助是指示元素存儲(chǔ)地址的（）表示數(shù)據(jù)元素之間的邏輯關(guān)系。任何一個(gè)算法的設(shè)計(jì)取決于選定（）結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的（）結(jié)構(gòu)。13、數(shù)據(jù)類型是一組（）的值集合以及定義在這個(gè)值集合上的一組操作的總稱。14、數(shù)據(jù)對(duì)象是（）數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。判斷題：1、順序存儲(chǔ)方式優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入和刪除運(yùn)算效率高。（）2、順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)屬于動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。（）3、線性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。（）4、數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。（）5、在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。（）6、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）7、基于某種邏輯結(jié)構(gòu)之上的運(yùn)算，其實(shí)現(xiàn)是惟一的。（）成績(jī)____________日期____________________

第2章線性表選擇題：1、在表長(zhǎng)為n的順序表上做插入運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)數(shù)為（）。A．nB．n/2C．n/3D．n/42、在一個(gè)單鏈表中，若P所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入S所指結(jié)點(diǎn)，則執(zhí)行（）A．S->next=P->next;P->next=SB．P->next=S->next;S->next=P；C．P->next=P;P->next=S；D．P->next=S;S->next=P；3、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為（）A．Ｏ（1）B．Ｏ（log2n）C．O（n）D．O（n2）4、對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為（）A．順序表B．用頭指針表示的單循環(huán)鏈表C．用尾指針表示的單循環(huán)鏈表D．單鏈表5、線性表是（）A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不能為空C．一個(gè)無(wú)限序列，可以為空D．一個(gè)無(wú)限序列，不能為空6、在n個(gè)結(jié)點(diǎn)的雙鏈表的某個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）A．O（n）B．O（1）C．O（log2n）D．O（n2）7、線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的地址（）A．必須是連續(xù)的B．必須是不連續(xù)的C．連續(xù)與否均可D．必須有相等的間隔8、在單鏈表中，增加頭結(jié)點(diǎn)的目的是（）A．使單鏈表至少有一結(jié)點(diǎn)B．標(biāo)志表中首結(jié)點(diǎn)位置C．方便運(yùn)算的實(shí)現(xiàn)D．說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)9、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）A．head=NULL；B．head->next=NULL；C．head->next=head；D．head!=NULL；10、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度為（）A．Ｏ（1）B．Ｏ（n）C．Ｏ（n2）D．Ｏ（log2n）11、下列有關(guān)線性表的敘述中，正確的是（）A．線性表中的元素之間是線性關(guān)系B．線性表中至少有一個(gè)元素C．線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨D．線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼12、在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)需有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，它指向該結(jié)點(diǎn)的（）A．直接前趨B．直接后繼C．開(kāi)始結(jié)點(diǎn)D．終端結(jié)點(diǎn)13、將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A．nB.2n-1C.2nD.n-114、鏈表不具有的特點(diǎn)是（）。A．隨機(jī)訪問(wèn)B．不必事先估計(jì)存儲(chǔ)空間C．插入刪除時(shí)不需移動(dòng)元素D．所需的空間與線性表成正比15、在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前趨，若在p，q之間插入s結(jié)點(diǎn)，則執(zhí)行的操作是（）。A．s->next=p->next;p->next=s;B．q->next=s;s->next=p;C．p->next=s->next;s->next=p;D．p->next=s;s->next=q;16、鏈表具有的特點(diǎn)是（）。A．可隨機(jī)訪問(wèn)任一元素 B．插入、刪除需要移動(dòng)元素C．不必事先估計(jì)存儲(chǔ)空間 D．存儲(chǔ)空間是靜態(tài)分配的17、一個(gè)順序表一旦說(shuō)明，其中可用空間大?。ǎ〢．已固定 B．可以改變 C．不能固定 D．動(dòng)態(tài)變化18、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。順序表 B．單鏈表 C．雙向鏈表 D．單循環(huán)鏈表19、兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素的前驅(qū)的條件是（）。A．P->next==Q B．Q->next==PC．P==Q D．P->next==Q->next20、下面關(guān)于線性表的敘述中，錯(cuò)誤的是（）。A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D．線性表采用鏈接存儲(chǔ)，便于進(jìn)行插入和刪除操作21、在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（）。A．訪問(wèn)第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前趨（2≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D．將n個(gè)結(jié)點(diǎn)從小到大排序22、在一個(gè)單鏈表中，若刪除p指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行的操作為（）。A．q=p->next;p->next=p->next->next;free(q);B．p=p->next;q=p->next;p=q->next;free(q);C．q=p->next->next;p=p->next;free(q);D．p=p->next->next;q=p->next;free(q);23、若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則最節(jié)省運(yùn)算時(shí)間的存儲(chǔ)方式是（）。A．單鏈表 B．僅有頭指針的單循環(huán)鏈表C．雙鏈表 D．僅有尾指針的單循環(huán)鏈表24、求循環(huán)鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是（）。A．O(n)和O(1) B．O(1)和O(1) C．O(1)和O(n) D．O(n)和O(n)25、求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前驅(qū)的時(shí)間復(fù)雜度分別是（）。 A．O（n）和O（1） B．O（1）和O（1） C．O（1）和O（n） D．O(n)和O（n）26、非空的單循環(huán)鏈表的頭指針為head,尾指針為rear，則下列條件成立的是（）。A．rear->next==head B．rear->next->next==headC．head->next==rear D．head->next->next==rear27、從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)的元素的個(gè)數(shù)是（）。A．n-i B．n-i+1 C．n-i-1 D．i28、用鏈表表示線性表的優(yōu)點(diǎn)是（）。A．便于隨機(jī)存取 B．花費(fèi)的存儲(chǔ)空間比順序表少C．?dāng)?shù)據(jù)元素的物理順序與邏輯順序相同D．便于插入與刪除29、采用順序搜索方法查找長(zhǎng)度為n的順序表示，搜索成功的平均搜索長(zhǎng)度為（）。A．n B．n/2 C．(n-1)/2 D．(n+1)/230、將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（）。A．O(1) B．O(n) C．O(m) D．O(m+n)31、若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為head，則該鏈表為空的判定條件是()。A．head==NULL B．head->next==NULL C．head!=NULL D．head->next==head填空題：1、在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，其時(shí)間復(fù)雜度為（）。2、在僅有尾指針R指示的單循環(huán)鏈表R中，在表尾插入一個(gè)結(jié)點(diǎn)S的語(yǔ)句序列是（）。3、在帶頭結(jié)點(diǎn)的雙鏈表Ｌ中，指針Ｐ所指結(jié)點(diǎn)是數(shù)據(jù)首結(jié)點(diǎn)的條件是（）。4、在具有n個(gè)結(jié)點(diǎn)的雙鏈表中做插入、刪除運(yùn)算，平均時(shí)間復(fù)雜度為（）。5、在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1≤i≤n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)（）個(gè)元素。6、在雙循環(huán)鏈表中，若要在指針p所指結(jié)點(diǎn)之前插入指針s所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：s->prior=p->prior;p->prior->next=s;()和p->prior=s;。7、已知指針p指向雙向鏈表中的一個(gè)結(jié)點(diǎn)（非首結(jié)點(diǎn)、非尾結(jié)點(diǎn)），則將結(jié)點(diǎn)s插入在p結(jié)點(diǎn)的直接后繼位置的語(yǔ)句是（）s->prior=p；s->next->prior=s；p->next=s;8、已知帶表頭結(jié)點(diǎn)的單鏈表L，指針p指向L鏈表中的一個(gè)結(jié)點(diǎn)（非首結(jié)點(diǎn)、非尾結(jié)點(diǎn)），則刪除結(jié)點(diǎn)p的直接后繼結(jié)點(diǎn)的語(yǔ)句是（）；刪除首結(jié)點(diǎn)的語(yǔ)句是（）。9、在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)（）元素，具體移動(dòng)的元素個(gè)數(shù)與（）有關(guān)。10、在雙向循環(huán)鏈表L中，指針P所指向結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是（）。11、在帶有頭結(jié)點(diǎn)的單鏈表中L中，第一個(gè)元素結(jié)點(diǎn)的指針是（）。12、在一個(gè)帶頭節(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=（）。13、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句:（）。判斷題1、在有序的順序表和有序的鏈表上，均可以使用折半查找法來(lái)提高查找速度。（）2、順序存儲(chǔ)的線性表可以隨機(jī)存取。（）3、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（）程序設(shè)計(jì)題數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)類型定義如下：鏈?zhǔn)酱鎯?chǔ)：typedefstructLinkList{intdata;structLinkList*next;}Node,*LinkList;1、已知帶頭結(jié)點(diǎn)的單鏈表head中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，寫一算法將值為x的結(jié)點(diǎn)插入到表head中，使head仍然有序。2、對(duì)給定的單鏈表L，編寫一個(gè)刪除L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)算法。3、閱讀算法并根據(jù)輸入數(shù)據(jù)畫出鏈表。linklistcreatelistr1(){charch;linklisthead=(listnode*)malloc(sizeof(listnode));listnode*p，*r；r=head;while((ch=getchar())!=‵\n′){p=(listnode*)malloc(sizeof(listnode));while(p)p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}輸入數(shù)據(jù)為：text（注：尾插法創(chuàng)建鏈表）4、閱讀下面的程序，說(shuō)明程序的具體功能。typedefintelementypetypedefstructnode{elemtypedata;strunctnode*next;}linklist;voidfunction(linklist*head,elemtypex){linklist*q,*p;q=head;p=q-next;while(p!=NULL)&&(p->data!=x){q=p;p=p->next;}if(q==NULL)printf(“thereisnothisnode::\n”);else{q->next=p->next;free(p);}}該程序的功能是：5、從帶頭結(jié)點(diǎn)的鏈表L中刪除重復(fù)的元素,并使剩余元素間的相應(yīng)次序保持不變.要求本算法的空間復(fù)雜記度為O(1)。成績(jī)____________日期____________________

第3章棧和隊(duì)列選擇題：1、循環(huán)隊(duì)列是空隊(duì)列的條件是（）A．Q.rear==Q.frontB．（Q.rear+1）%maxsize==Q.frontC．Q.rear==0D．Q.front==02、鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是（）A．通常不會(huì)出現(xiàn)棧滿的情況B．通常不會(huì)出現(xiàn)?？盏那闆r

C．插入操作更加方便D．刪除操作更加方便3、若一個(gè)棧的輸入序列是１，２，３，……，n，輸出序列的第一個(gè)元素是ｎ，則第ｉ個(gè)輸出元素是（）A．n-iB．n–i+1C．iD．不確定4、棧與一般線性表的區(qū)別主要在（）A．元素個(gè)數(shù)B．元素類型C．邏輯結(jié)構(gòu)D．插入、刪除元素的位置5、一個(gè)鏈棧的棧頂指針是top，則執(zhí)行出棧操作時(shí)（棧非空），用x保存被刪除結(jié)點(diǎn)，則執(zhí)行（）A．x=top;top=topnext；B．x=topdata；C．top=topnext;x=topdata；D．x=topdata;top=topnext；6、對(duì)于一個(gè)棧，給定輸入序列為1，2，3，則下列不可能為輸出序列的是（）A．1，2，3B．3，2，1C．3，1，2D．2，1，37、在鏈接隊(duì)列執(zhí)行入隊(duì)操作（）A．需判別隊(duì)是否空B．需判別隊(duì)是否滿C．限制在鏈表頭p進(jìn)行D．限制在鏈表尾p進(jìn)行8、以下不屬于棧的基本運(yùn)算是（）。A．刪除棧頂元素B．刪除棧底元素C．判斷棧是否為空D．將棧置為空棧9、一個(gè)棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（）。A．e,d,c,b,aB．d,e,c,b,aC．d,c,e,a,bD．a(chǎn),b,c,d,e10、設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．棧C．隊(duì)列D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)11、循環(huán)隊(duì)列的特點(diǎn)之一是不會(huì)產(chǎn)生（）。A．上溢出B．下溢出C．隊(duì)滿D．假溢出12、設(shè)數(shù)組Data[n]作為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作的語(yǔ)句為（）。A．rear=(rear+1)%(n+1)B．front=(front+1)%nC．rear=(rear+1)%nD．front=(front+1)%(n+1)13、棧是限定在（）處進(jìn)行插入或刪除操作的線性表。A．端點(diǎn) B．棧底 C．棧頂 D．中間14、容量是10的循環(huán)隊(duì)列的隊(duì)頭位置qfront為2，隊(duì)列中的數(shù)據(jù)元素個(gè)數(shù)為5，則隊(duì)的第一個(gè)入隊(duì)數(shù)據(jù)元素的位置是（）A．2 B．7 C．1 D．015、循環(huán)隊(duì)列的出隊(duì)操作是（）A． qfront=(qfront+1)%maxsize; B．qfront=qfront+1;C．qrear=(qrear+1)%maxsize;D．qrear=qrear+1;16、當(dāng)循環(huán)隊(duì)列q是滿隊(duì)列時(shí)，存放隊(duì)列元素的數(shù)組data有n個(gè)元素，則data中存放（）個(gè)數(shù)據(jù)元素。A．n B.n-1 C.n-2 D.017、以下哪一個(gè)不是隊(duì)列的基本運(yùn)算（）。A．從隊(duì)尾插入一個(gè)新元素B．從隊(duì)列中刪除第i個(gè)元素C．判斷一個(gè)隊(duì)列是否為空D．讀取隊(duì)頭元素的值18、在一個(gè)鏈隊(duì)列中，若f,r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（）。A．fnext=s;f=s B．rnext=s;r=s;C．snext=r;r=s; D．snext=f;f=s19、循環(huán)隊(duì)列的入隊(duì)操作應(yīng)為（）。A．qrear=qrear+1;qdata[qrear]=x; B．qdata[qrear++]=x;C．qrear=(qrear+1)%maxsize;qdata[qrear]=x;D．qdata[qrear]=x;q->rear=(qrear+1)%maxsize;20、棧和隊(duì)列都是（）。A．限制存取點(diǎn)的線性結(jié)構(gòu) B．限制存取點(diǎn)的非線性結(jié)構(gòu)C．順序存儲(chǔ)的線性結(jié)構(gòu) D．鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)21、實(shí)現(xiàn)遞歸調(diào)用屬于（）的應(yīng)用。A．隊(duì)列 B．棧 C．?dāng)?shù)組 D．樹(shù)22、順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進(jìn)棧操作的主要語(yǔ)句為（）。A．s.elem［s.top］=e；s.top=s.top+1； B．s.elem［s.top］=e；s.top=s.top+1；C．s.top=s.top+1；s.elem［s.top+1］=e； D．s.top=s.top+1；s.elem［s.top］=e；23、循環(huán)隊(duì)列sq中，用數(shù)組elem［0··25］存放數(shù)據(jù)元素，sq.front指示隊(duì)頭元素的前一個(gè)位置，sq.rear指示隊(duì)尾元素的當(dāng)前位置，設(shè)當(dāng)前sq.front為20，sq.rear為12，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A．8 B．16 C．17 D．1824、鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是（）。A．插入操作更加方便 B．通常不會(huì)出現(xiàn)棧滿的情況C．不會(huì)出現(xiàn)?？盏那闆r D．刪除操作更加方便25、若已知一個(gè)棧的入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為（）。 A．i B．n==i C．n-i+1 D．不確定26、若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則不可能出現(xiàn)的出棧序列是()。A．2，4，3，1，5，6 B．3，2，4，1，6，5C．4，3，2，1，5，6 D．2，3，5，1，6，427、對(duì)于棧操作數(shù)據(jù)的原則是（）。A．先進(jìn)先出 B．后進(jìn)先出 C．后進(jìn)后出 D．不分順序28、棧和隊(duì)列的共同點(diǎn)是（）。A．都是先進(jìn)先出 B．都是先進(jìn)后出C．只允許在端點(diǎn)處插入和刪除元素 D．沒(méi)有共同點(diǎn)29、一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是（）。A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,130、引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是()。A．出隊(duì) B．入隊(duì) C．取隊(duì)頭元素 D．取隊(duì)尾元素31、設(shè)數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A．(rear-front+m)%mB）rear-front+1 C）(front-rear+m)%mD）(rear-front)%m填空題：1、循環(huán)隊(duì)列用數(shù)組data[m]存放其元素值，已知其頭、尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中元素的個(gè)數(shù)是（）。2、棧頂?shù)奈恢檬请S著（）操作而變化的。3、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列a，b，c，d，e進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為（）。4、隊(duì)列的隊(duì)尾位置隨著（）而變化。5、在（）的情況下，鏈隊(duì)列的出隊(duì)操作需要修改尾指針。6、從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪除的結(jié)點(diǎn)的值保存在x中，其操作步驟為（）。7、用數(shù)組A[m]來(lái)存放循環(huán)隊(duì)列q的元素，且它的頭、尾指針?lè)謩e為front和rear，隊(duì)列滿足條件(q.rear+1)%m==q.front,則隊(duì)列中當(dāng)前的元素個(gè)數(shù)為（）。8、順序棧s存儲(chǔ)在數(shù)組s->data[max]中，對(duì)s進(jìn)行出棧操作，執(zhí)行的語(yǔ)句序列是（）。9、以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)列中的初始化操作voidinitqueue(seqqueue*q){q->front=0;();}10、對(duì)于棧操作數(shù)據(jù)的原則是（）。11、一個(gè)鏈棧的棧頂指針用top表示，當(dāng)p所指向的結(jié)點(diǎn)進(jìn)棧時(shí)，執(zhí)行的操作為（）。12、一個(gè)鏈棧的棧頂指針用top表示，當(dāng)進(jìn)行退棧時(shí)所進(jìn)行的指針操作為（）。13、（）是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。14、用P表示入棧操作，D表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的P和D的操作串為（）。15、在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿共有（）個(gè)元素。16、循環(huán)隊(duì)列的引入，目的是為了克服（）。判斷題：1、循環(huán)隊(duì)列中無(wú)上溢現(xiàn)象。（）2、循環(huán)隊(duì)列只有下溢，沒(méi)有上溢。（）3、對(duì)順序棧而言，在棧滿狀態(tài)，如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”。（）4、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的條件是一樣的。（）5、為解決隊(duì)列“假滿”問(wèn)題，可以采用循環(huán)隊(duì)列實(shí)現(xiàn)隊(duì)列存儲(chǔ)。（）6、隊(duì)列是后進(jìn)先出的線性表。（）7、棧是后進(jìn)先出表。（）應(yīng)用題：1、設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳，B，C，D，E，寫出下列出棧序列的操作序列。（1）CBADE（2）ACBED，其中I為進(jìn)棧操作，O為出棧操作。2、如果編號(hào)為1、2、3的三輛列車順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，那么可能得到的三輛列車出站序列有哪些？不可能出現(xiàn)的序列是什么？答：程序設(shè)計(jì)題：寫一個(gè)函數(shù)，利用棧完成數(shù)的進(jìn)制轉(zhuǎn)換并顯示。voidconversion(intn，intbase)//n為要轉(zhuǎn)換的十進(jìn)制數(shù)，base為進(jìn)制{}成績(jī)____________日期____________________第4章串一、單選題1．下列那些為空串（）A．S=“”B．S=“”C．S=“φ”D．S=“θ”2．S1=“ABCD”，S2=“CD”則S2在S3中的位置是（）A．1B．2C．3D．43．假設(shè)S=“abcaabcaaabca”，T=“bca”，Index(S,T,3)的結(jié)果是（）A．2B．6C．11D．04．在串中，對(duì)于SubString(&Sub,S,pos,len)基本操作，pos和len的約束條件是（）A．0<pos<StrLength(S)+1且1<=len<=StrLength(S)-pos+1B．0<pos<StrLength(S)+1且0<=len<=StrLength(S)-pos-1C．1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1D．1<=pos<=StrLength(S)且1<=len<=StrLength(S)-pos-15．串是一種特殊的線性表，其特殊性體現(xiàn)在()。A．可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C．可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符6．串是()。A．少于一個(gè)字母的序列B.任意個(gè)字母的序列C．不少于一個(gè)字符的序列D.有限個(gè)字符的序列7．串的長(zhǎng)度是()。A．串中不同字母的個(gè)數(shù)B.串中不同字符的個(gè)數(shù)C．串中所含的字符的個(gè)數(shù)D.串中所含字符的個(gè)數(shù)，且大于08．設(shè)有S1=‘ABCDEFG’，S2=‘PQRST’，函數(shù)con(x，y)返回x和y串的連接串，subs(i，j)返回串S的從序號(hào)I的字符開(kāi)始的j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，則con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的結(jié)果是()。A．BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF9．若某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用()存儲(chǔ)方式最為節(jié)省空間。A．鏈?zhǔn)紹.堆結(jié)構(gòu)C.順序表二、填空題：1．串是每個(gè)結(jié)點(diǎn)僅由一個(gè)字符組成的____________________。2．在串中，SubString(“student”,5,0)的結(jié)果是____________________。3．假設(shè)S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace(S,T,V)結(jié)果是__________。4．在串中，對(duì)于StrCompare(S,T)基本操作，若S<T，返回值__________________。5．在串順序存儲(chǔ)結(jié)構(gòu)中，實(shí)現(xiàn)串操作的原操作為_(kāi)_______________________。6．串與線性表在邏輯結(jié)構(gòu)上極為相似，區(qū)別僅在于_____________________________；在基本操作上差別很大，線性表的基本操作大多數(shù)以_____________作為操作對(duì)象，而串的基本操作通常以______________________作為操作對(duì)象。7．兩個(gè)串相等的充分必要條件是____________________且_____________________________________。8．空串是指_____________________，空格串是指____________________________。9．串是一種特殊的線性表,其特殊性體現(xiàn)在_____________________________。三、判斷題1．空串是由空白字符組成的串（）2．串的定長(zhǎng)順序結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長(zhǎng)度的存儲(chǔ)區(qū)。()3．串的堆分配存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配得到的。（）4．串中StrInsert(&S,pos,T)基本操作是最小的操作子集（）5．串是由有限個(gè)字符構(gòu)成的連續(xù)序列，串長(zhǎng)度為串中字符的個(gè)數(shù)，子串是主串中字符構(gòu)成的有限序列。（）6．如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，那么則說(shuō)明前者是后者的子串。()7．串類型的最小操作子集不能利用其他串操作來(lái)實(shí)現(xiàn)，反之，其他串操作（除串清除ClearString和串銷毀DestroyString外）均可在最小操作子集上實(shí)現(xiàn)。()四、簡(jiǎn)答題1．串是字符組成的，長(zhǎng)度為1的串和字符是否概念相同？為什么？答：五、算法設(shè)計(jì)題1．設(shè)串s和串t采用順序存儲(chǔ)結(jié)構(gòu)，編寫函數(shù)實(shí)現(xiàn)串s和串t的比較操作，要求比較結(jié)果包括大于、小于和等于三種情況。解：2．輸入一個(gè)由若干單詞組成的文本行，每個(gè)單詞之間用若干個(gè)空格隔開(kāi)，統(tǒng)計(jì)此文本中單詞的個(gè)數(shù)。成績(jī)____________日期____________________第5章數(shù)組和廣義表一、單項(xiàng)選擇題1.常對(duì)數(shù)組進(jìn)行的兩種基本操作是()。A.建立與刪除B.索引和修改C.對(duì)數(shù)據(jù)元素的存取和修改D.查找與索引2.二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元，即一個(gè)字節(jié)）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從0到9，則存放M至少需要()個(gè)字節(jié)；M數(shù)組的第8列和第5行共占()個(gè)字節(jié)。A.90、114B.180、54C.240、60D.540、1083.二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是()。A.80B.100C.240D.2704.二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]的起始地址為()。A.SA+141B.SA+144C.SA+222D.SA+2255.假設(shè)以行優(yōu)先順序存儲(chǔ)三維數(shù)組R[6][9][6]，其中元素R[0][0][0]的地址為2100，且每個(gè)元素占4個(gè)存儲(chǔ)單元，則存儲(chǔ)地址為2832的元素是()。A．R[3][3][3] B．R[3][3][4] C．R[4][3][5] D．R[4][3][4]6.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式以行序?yàn)橹餍虼鎯?chǔ)，a00為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a45的地址為()。A．13 B．35 C．17 D．367.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是()。A．便于進(jìn)行矩陣運(yùn)算 B．便于輸入和輸出C．節(jié)省存儲(chǔ)空間 D．降低運(yùn)算的時(shí)間復(fù)雜度二、填空題（將正確的答案填在相應(yīng)的空中）1.已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0])，則A[i][j]的地址是_____________________________。2.二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A[0][0]的存儲(chǔ)地址是200，則A[6][12]的地址是________________________。3.二維數(shù)組A[10..20][5..10]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，A[10][5]的存儲(chǔ)地址是1000，則A[18][9]的地址是____________________________________。4．求下列廣義表操作的結(jié)果：(1)GetTail[GetHead[((a,b),(c,d))]];________________________(2)GetTail[GetHead[GetTail[((a,b),(c,d))]]]________________________成績(jī)____________日期____________________第6章樹(shù)和二叉樹(shù)選擇題：1、在具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，結(jié)點(diǎn)i（i>1）的父結(jié)點(diǎn)是（）A．2iB．不存在C．2i+1D．?i/2?2、有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)所具有的結(jié)點(diǎn)數(shù)為（）A．mB．m+1C．2mD．2m-13、下列陳述中正確的（）A．二叉樹(shù)是度為2的有序樹(shù)B．二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分C．二叉樹(shù)中必有度為2的結(jié)點(diǎn)D．二叉樹(shù)中最多只有兩棵子樹(shù)，并且有左右之分4、以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，在具有ｎ個(gè)結(jié)點(diǎn)的二叉鏈表中(n>0)，空鏈域的個(gè)數(shù)為（）A．2n-1B．n-1C．n+1D．2n+15、將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為（）A．99B．98C．50D．486、在一棵具有五層的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（）A．31B．32C．33D．167、在一棵二叉樹(shù)中，第5層上的結(jié)點(diǎn)數(shù)最多為（）A．8B．15C．16D．328、由二叉樹(shù)的（）遍歷，可以惟一確定一棵二叉樹(shù)A．前序和后序B．前序和中序C．后序D．中序9、具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（）。A.5B.6C.7D.810、已知一棵二叉樹(shù)的先序遍歷序列為EFHIGJK，中序遍歷序列為HFIEJGK，則該二叉樹(shù)根的右子樹(shù)的根是（）。A．EB.FC.GD.J11、由4個(gè)結(jié)點(diǎn)構(gòu)造出的不同的二叉樹(shù)個(gè)數(shù)共有（）。A．8B.10C．12D．1412、在完全二叉樹(shù)中，如果一個(gè)結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則它沒(méi)有（）。A.左孩子結(jié)點(diǎn)B.右孩子結(jié)點(diǎn)C.左、右孩子結(jié)點(diǎn)D.左、右孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)13、深度為6的二叉樹(shù)最多有（）個(gè)結(jié)點(diǎn)。A．64 B．63 C．32 D．3114、二叉樹(shù)使用二叉鏈表存儲(chǔ)，若p指針指向二叉樹(shù)的一個(gè)結(jié)點(diǎn)，當(dāng)p->lchild=NULL時(shí)，則（）。p結(jié)點(diǎn)左孩子為空 B．p結(jié)點(diǎn)有右孩子p結(jié)點(diǎn)右孩子為空 D．p結(jié)點(diǎn)有左孩子15、在具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，若結(jié)點(diǎn)i有左孩子，則結(jié)點(diǎn)i的左孩子編號(hào)為（）。A．2i B．不存在 C．2i+1 D．2i-116、將含100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，按從上到下從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為１。編號(hào)為50的結(jié)點(diǎn)X的雙親的編號(hào)為（）。A．25B．48C．100D．無(wú)法確定17、三個(gè)結(jié)點(diǎn)可以構(gòu)成（）種不同形狀的二叉樹(shù)。１ Ｂ．2 C．3 D．518、若由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)是非空的二叉樹(shù)，則二叉樹(shù)形狀是（）。A．根結(jié)點(diǎn)無(wú)右子樹(shù)的二叉樹(shù) B．根結(jié)點(diǎn)無(wú)左子樹(shù)的二叉樹(shù)C．根結(jié)點(diǎn)可能有左子樹(shù)和右子樹(shù) D．各結(jié)點(diǎn)只有一個(gè)孩子的二叉樹(shù)19、哈夫曼樹(shù)是訪問(wèn)葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度（）的二叉樹(shù)。A．最短 B．最長(zhǎng) C．可變 D．不定20、某二叉樹(shù)的前序和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。A．空或只有一個(gè)結(jié)點(diǎn) B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無(wú)左孩子 D．任一結(jié)點(diǎn)無(wú)右孩子21、樹(shù)中所有結(jié)點(diǎn)的度之和等于所有結(jié)點(diǎn)數(shù)加（）。A．0 B．1 C．-1 D．222、含有10個(gè)結(jié)點(diǎn)的二叉樹(shù)中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的結(jié)點(diǎn)數(shù)為（）A．3 B．4 C．5 D．623、除第一層外，滿二叉樹(shù)中每一層結(jié)點(diǎn)個(gè)數(shù)是上一層結(jié)點(diǎn)個(gè)數(shù)的（）A．1/2倍 B．1倍 C．2倍 D．3倍24、對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的父結(jié)點(diǎn)的編號(hào)為（）A．24 B．25 C．98 D．9925、在一棵度為3的樹(shù)中，度為3的節(jié)點(diǎn)個(gè)數(shù)為2，度為2的節(jié)點(diǎn)個(gè)數(shù)為1，則度為0的節(jié)點(diǎn)個(gè)數(shù)為（）。 A．4 B．5 C．6 D．726、樹(shù)最適合用來(lái)表示（）。A．有序數(shù)據(jù)元素 B．無(wú)序數(shù)據(jù)元素 C．元素之間具有分支層次關(guān)系的數(shù)據(jù) D．元素之間無(wú)聯(lián)系的數(shù)據(jù)27、判定線索二叉樹(shù)中某結(jié)點(diǎn)P沒(méi)有左孩子的條件是（）A）P!=NULLB）P->lchild!=NULLC）P->Ltag=0D）P->Ltag=128、在一個(gè)非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）。 A．只有右子樹(shù)上的所有結(jié)點(diǎn) B．只有右子樹(shù)上的部分結(jié)點(diǎn)C．只有左子樹(shù)的上的部分結(jié)點(diǎn) D．只有左子樹(shù)上的所有結(jié)點(diǎn)29、權(quán)值為{1,2,6,8}的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是（）。 A．18 B．28 C．19 D．2930、對(duì)一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，k個(gè)分枝結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)，則（）。 A．n=m+1 B．m+1=2nC．m=k-1 D．n=2k+131、有30個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為（）。 A．4 B．5 C．6 D．7填空題：1、12個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉結(jié)點(diǎn)有（）個(gè)。2、在任何一棵二叉樹(shù)中，度為０的結(jié)點(diǎn)n0和度為２的結(jié)點(diǎn)n2之間的關(guān)系是（）。3、已知完全二叉樹(shù)的第4層有4個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是（）。4、10個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉結(jié)點(diǎn)有（）個(gè)。5、一個(gè)二叉樹(shù)中，度為2的結(jié)點(diǎn)有3個(gè)，則葉結(jié)點(diǎn)有（）個(gè)。6、若二叉樹(shù)的一個(gè)葉子是某子樹(shù)的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的后根遍歷序列中的（）個(gè)結(jié)點(diǎn)。7、下圖為某樹(shù)的靜態(tài)雙親表示，則結(jié)點(diǎn)D、E的雙親結(jié)點(diǎn)分別為（）和（）。A-1B0C0D1E2012348、二叉樹(shù)通常有（）存儲(chǔ)結(jié)構(gòu)和（）存儲(chǔ)結(jié)構(gòu)兩種。9、樹(shù)內(nèi)各結(jié)點(diǎn)的度（）稱為樹(shù)的度。10、已知完全二叉樹(shù)T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹(shù)共有（）個(gè)葉子結(jié)點(diǎn)。11、一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為（）。判斷題：1、完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左孩子，則它必須是葉子。（）2、由二叉樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵二叉樹(shù)。（）3、一般在哈夫曼樹(shù)中，權(quán)值越大的葉子離根結(jié)點(diǎn)越近。（）4、二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都是2。（）5、一棵哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。（）6、若一個(gè)二叉樹(shù)的葉結(jié)點(diǎn)是先根遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是中根遍歷的序列中的最后一個(gè)結(jié)點(diǎn)。（）7、中序遍歷二叉排序樹(shù)的結(jié)點(diǎn)不能得到排好序的結(jié)點(diǎn)序列。（）8、完全二叉樹(shù)一定是滿二叉樹(shù)。（）9、由二叉樹(shù)的前序和中序遍歷序列可以推導(dǎo)出此二叉樹(shù)的后序遍歷序列。（）10、滿二叉樹(shù)一定是完全二叉樹(shù)。（）11、完全二叉樹(shù)可采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)，非完全二叉樹(shù)則不能。（）應(yīng)用題：1、對(duì)給定的一組權(quán)值W=｛5，2，9，11，8，3，7｝，試構(gòu)造相應(yīng)的哈夫曼樹(shù)，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。答：2、設(shè)有一組結(jié)點(diǎn)，其權(quán)值W=｛1，4，9，16，25，36，49｝，畫出由這些結(jié)點(diǎn)所構(gòu)成的哈夫曼樹(shù)，并計(jì)算帶權(quán)路徑長(zhǎng)度。答：3、已知一棵二叉樹(shù)如圖所示。請(qǐng)分別寫出按前序、中序、后序和層次遍歷是得到的頂點(diǎn)序列。AABECFHDG4、已知一棵二叉樹(shù)的先根遍歷序列和中根遍歷序列分別是ABDGHE及GDHBEA，畫出這棵二叉樹(shù)。答：5、已知一棵二叉樹(shù)的前序序列為ABCDEFGH，中序序列為CBEDFAGH，請(qǐng)畫出該二叉樹(shù)。程序設(shè)計(jì)題：1．利用二叉樹(shù)遍歷算法輸出二叉樹(shù)中葉子結(jié)點(diǎn)。解：2．利用二叉樹(shù)遍歷算法求二叉樹(shù)的高度，假設(shè)根結(jié)點(diǎn)的高度為1.成績(jī)____________日期____________________

第7章圖一、選擇題：1、在一個(gè)具有n個(gè)結(jié)點(diǎn)的無(wú)向圖中，要連通全部結(jié)點(diǎn)至少需要（）A．n條邊B．n+1條邊C．n-1條邊D．n/2條邊2、最小生成樹(shù)指的是（）A．由連通圖所得到的邊數(shù)最少的生成樹(shù)B．由連通圖所得到的頂點(diǎn)相對(duì)較少的生成樹(shù)C．連通圖的所有生成樹(shù)中權(quán)值之和最小的生成樹(shù)D．連通圖的極小連通子圖3、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（）A．1/2倍B．1倍C．2倍D．4倍4、有n個(gè)結(jié)點(diǎn)的無(wú)向圖的邊數(shù)最多為（）A．n+1B．n（n-1）/2C．n（n+1）D．2n（n+1）5、若n個(gè)頂點(diǎn)的無(wú)向圖采用鄰接矩陣存儲(chǔ)方法，該鄰接矩陣是一個(gè)（）A．一般矩陣B．對(duì)稱矩陣C．對(duì)角矩陣D．稀疏矩陣6、設(shè)有一個(gè)有向圖如下所示，請(qǐng)指出下列（）序列不是該圖的拓?fù)渑判蛐蛄?？A.EAFBGDCB.AEBCGFDC.ABCEGFDD.EBAGFCD7、拓?fù)渑判蚴菍?duì)（）進(jìn)行的。A.無(wú)向圖B.有向圖C.任意圖D.有向圖和無(wú)向圖8、下面哪一種圖的鄰接矩陣肯定是對(duì)稱矩陣（）。A．有向圖B.無(wú)向圖C.AOV網(wǎng)D.AOE網(wǎng)9、設(shè)有向圖G有n個(gè)頂點(diǎn)，它的鄰接矩陣為A，G中第i個(gè)頂點(diǎn)Vi的度為（）。A.B.C.D.210、深度優(yōu)先遍歷類似于二叉樹(shù)的（）。A．先序遍歷 B．中序遍歷 C．后序遍歷D．層次遍歷11、有n個(gè)頂點(diǎn)的無(wú)向圖的鄰接矩陣是用（）數(shù)組存儲(chǔ)。A．n行n列 B．一維 C．任意行n列 D．n行任意列12、最小生成樹(shù)的構(gòu)造可使用（）。A．prim算法 B．冒泡算法 C．迪杰斯特拉算法 D．哈夫曼算法13、有8個(gè)結(jié)點(diǎn)的有向完全圖有（）條邊。A．14 B．28 C．56 D．11214、有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有（）條邊。A．14 B．28 C．56 D．11215、廣度優(yōu)先遍歷類似于二叉樹(shù)的（）A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷16、在含有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（）。A．e B．2e C．n2-e D．n2-2e17、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（）倍。 A．1/2 B．1 C．2 D．418、如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹(shù)，應(yīng)采用（）。A． 深度優(yōu)先搜索算法 B． 廣度優(yōu)先搜索算法C．求最小生成樹(shù)的prim算法 D．拓?fù)渑判蛩惴?9、n個(gè)頂點(diǎn)的完全有向圖中含有()。A．n-1條有向邊B．n條有向邊 C．n(n-1)/2條有向邊D．n(n-1)條有向邊20、在無(wú)向圖中定義頂點(diǎn)Vi域Vj之間的路徑為從Vi到達(dá)Vj的一個(gè)（）。A．頂點(diǎn)序列 B．邊序列 C．權(quán)值總和D．邊的條數(shù)21、下面（）方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）。A．求節(jié)點(diǎn)的度 B．拓?fù)渑判駽．求最短路徑 D．求關(guān)鍵路徑22、已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓?fù)湫蛄惺牵ǎ?。A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V723、關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。A．從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B．從源點(diǎn)到匯點(diǎn)的最短路徑C．最長(zhǎng)回路 D．最短回路24、設(shè)圖的鄰接鏈表如下圖所示，則該圖的邊的數(shù)目是（）。25題圖25題圖A．4 B．5 C．10 D．2025、有8個(gè)結(jié)點(diǎn)的無(wú)向連通圖最少有（）條邊。A．5 B．6 C．7 D．826、已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A．0243156B．0135642 C．0423165D．013425627、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A．0132B．0231 C．0321 D．012328、已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)點(diǎn)序列是（）。A．0321 B．0123 C．0132 D．0312二、填空題：1、已知一個(gè)圖用鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是（）。2、圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于（）圖。3、若要求一個(gè)稀疏圖的最小生成樹(shù)，最好用（）算法來(lái)求解；若要求一個(gè)稠密圖G的最小生成樹(shù)，最好用（）算法來(lái)求解。4、在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的（）。5、一個(gè)無(wú)向圖有n個(gè)頂點(diǎn)，e條邊，則所有頂點(diǎn)的度數(shù)之和為（）。6、圖有（）、（）等存儲(chǔ)結(jié)構(gòu)，遍歷圖有（）、（）等方法。7、有向圖G用鄰接表矩陣存儲(chǔ)，其第i行的所有非零元素之和等于頂點(diǎn)i的（）。8、圖的BFS生成樹(shù)的樹(shù)高比DFS生成樹(shù)的樹(shù)高（）。9、Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長(zhǎng)度（）的次序來(lái)得到最短路徑的。10、拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有（）個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。三、判斷題：1、有回路的圖不能進(jìn)行拓?fù)渑判?。（?、連通分量是無(wú)向圖中的極小連通子圖。（）3、強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。（）4、任何一個(gè)有向圖，其全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄?。（）四、?yīng)用題：1、寫出下面有向圖的鄰接矩陣表示和拓?fù)渑判蛐蛄小?5125121314161答：2.已知有向圖如右圖所示，請(qǐng)給出該圖的：VV5V4V2V3V1V6(2)鄰接矩陣示意圖(3)鄰接表示意圖(4)逆鄰接表示意圖答：求下圖的最小生成樹(shù)，要求畫出最小生成樹(shù)的生成過(guò)程。113161543121 16 21 11 5 19 6 33 14 6 4答：4、試?yán)肈ijkstra算法求圖7-5中頂點(diǎn)A到其他各頂點(diǎn)之間的最短路徑。GGABDCEF圖7-515122568491043成績(jī)____________日期____________________第9章查找選擇題：1、二叉排序樹(shù)中，關(guān)鍵字值最大的結(jié)點(diǎn)（）A．左指針一定為空B．右指針一定為空C．左、右指針均為空D．左、右指針均不為空2、順序查找法適合于存儲(chǔ)結(jié)構(gòu)為的線性表。（）A．散列存儲(chǔ)B．順序存儲(chǔ)或鏈接存儲(chǔ)C．壓縮存儲(chǔ)D．索引存儲(chǔ)3、在查找過(guò)程中，若同時(shí)還要做增、刪工作，這種查找則稱為（）A．靜態(tài)查找B．動(dòng)態(tài)查找C．內(nèi)查找D．外查找4、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）A．以順序方式存儲(chǔ)B．以順序方式存儲(chǔ)且元素有序C．以鏈接方式存儲(chǔ)D．以鏈接方式存儲(chǔ)且元素有序5、一棵二叉排序樹(shù)T，用（）方法進(jìn)行遍歷，可以得到各結(jié)點(diǎn)鍵值的遞增序列A．先根遍歷B．中根遍歷C．層次遍歷D．后根遍歷6、散列表的地址區(qū)間為0～16，散列函數(shù)為H1（K）=K%17，采用線性探測(cè)法解決沖突，將關(guān)鍵字序列26，25，72，38，1，18，59依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址為（）。A．8B.9C.10D.117、索引順序表的特點(diǎn)是順序表中的數(shù)據(jù)（）。A．有序 B．無(wú)序 C．塊間有序 D．散列8、靜態(tài)查找表與動(dòng)態(tài)查找表兩者的根本差別在于（）。A．邏輯結(jié)構(gòu)不同 B．存儲(chǔ)實(shí)現(xiàn)不同C．施加的操作不同 D．?dāng)?shù)據(jù)元素的類型不同9、設(shè)有序表的關(guān)鍵字序列為{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，當(dāng)用二分查找法查找鍵值為84的結(jié)點(diǎn)時(shí)，經(jīng)（）次比較后查找成功。A．2 B．3 C．4 D．1210、索引順序表中包含（）。A．順序表 B．索引表 C．順序表和索引表 D．索引11、與其他查找方法相比，散列查找法的特點(diǎn)是（）。A．通過(guò)關(guān)鍵字比較進(jìn)行查找B．通過(guò)關(guān)鍵字計(jì)算記錄存儲(chǔ)地址,并進(jìn)行地址的比較。C．通過(guò)關(guān)鍵字計(jì)算記錄存儲(chǔ)地址，并進(jìn)行一定的比較查找D．通過(guò)關(guān)鍵字比較進(jìn)行查找，并計(jì)算記錄存儲(chǔ)地址12、在散列函數(shù)H(k)=kMODm中，一般來(lái)講，m應(yīng)?。ǎ?。A．奇數(shù) B．偶數(shù) C．素?cái)?shù) D．充分大的數(shù)13、已知一個(gè)有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)二分檢索值為90的元素時(shí)，檢索成功需比較的次數(shù)是（）。A．1 B．2 C．3 D．414、由同一組關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)()。A．其形態(tài)不一定相同，但平均查找長(zhǎng)度相同B．其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同C．其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同D．其形態(tài)均相同，平均查找長(zhǎng)度也都相同15、衡量查找算法效率的主要標(biāo)準(zhǔn)是（）。A．元素的個(gè)數(shù) B．所需的存儲(chǔ)量 C．平均查找長(zhǎng)度D．算法難易程度填空題：1、對(duì)于二叉排序樹(shù)的查找，若根結(jié)點(diǎn)元素的鍵值大于被查找元素的鍵值，則應(yīng)該在該二叉樹(shù)的上繼續(xù)查找。3、在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是。4、散列法存儲(chǔ)的基本思想是由決定數(shù)據(jù)的存儲(chǔ)地址。5、由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，所以可用來(lái)衡量查找算法的性能。6、查找有靜態(tài)查找和動(dòng)態(tài)查找，當(dāng)查找不成功時(shí)動(dòng)態(tài)查找會(huì)。7、順序查找法中設(shè)置監(jiān)視哨，可以起到的作用。8、假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長(zhǎng)度為：。9、折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是的順序表。10、在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為。11、折半查找有序表（4,6,12,20,28,38,50,70,