中國(guó)石油大學(xué)期末考試復(fù)習(xí)題-070109數(shù)據(jù)結(jié)構(gòu)-18

《數(shù)據(jù)結(jié)構(gòu)》綜合復(fù)習(xí)資料一、填空題1、數(shù)據(jù)結(jié)構(gòu)是（）。2、數(shù)據(jù)結(jié)構(gòu)的四種基本形式為集合、（）、（）和（）。3、線性結(jié)構(gòu)的基本特征是:若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒(méi)有直接前驅(qū)外，其他結(jié)點(diǎn)有且僅有一個(gè)直接（）；除終端結(jié)點(diǎn)沒(méi)有直接（）外，其它結(jié)點(diǎn)有且僅有一個(gè)直接（）。4、堆棧的特點(diǎn)是（），隊(duì)列的特點(diǎn)是（），字符串中的數(shù)據(jù)元素為（）。5、字符串s1=“Iamastudent！”(單詞與單詞之間一個(gè)空格),s2=“student”,則字符串s1的長(zhǎng)度為（），串s2是串s1的一個(gè)（）串，串s2在s1中的位置為（）。6、KMP算法的特點(diǎn)：效率較（）；（）回溯，對(duì)主串僅需要從頭到尾掃描（）遍，可以邊讀入邊匹配。7、廣義表（（a），（（b），c），（（（d））））的長(zhǎng)度為（），表頭為（），表尾為（）。8、ADT稱為抽象數(shù)據(jù)類型，它是指（）。9、求下列程序的時(shí)間復(fù)雜度，并用大O表示方法表示（）。for(i=1;i<=n;++i)for(j=1;j<=i;++j){++x;a[i][j]=x;}10、以下運(yùn)算實(shí)現(xiàn)在鏈棧上的退棧操作，請(qǐng)?jiān)赺____處用適當(dāng)句子予以填充。intPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x=;ls=;;return(1)；}elsereturn(0);}11、用堆棧求中綴表達(dá)式a+b*c/d+e*f的后綴表達(dá)式，求出的后綴表達(dá)式為（）。12、C語(yǔ)言中存儲(chǔ)數(shù)組是采用以（）為主序存儲(chǔ)的，在C語(yǔ)言中定義二維數(shù)組floata[8][10],每個(gè)數(shù)據(jù)元素占4個(gè)字節(jié)，則數(shù)組共占用（）字節(jié)的內(nèi)存。若第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為8000，則a[5][8]的存儲(chǔ)地址為（）。13、含零個(gè)字符的串稱為（）串，用表示。其他串稱為（）串。任何串中所含字符的個(gè)數(shù)稱為該串的（）。14、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為（）、（）、（）和（）四種。15、算法設(shè)計(jì)的評(píng)價(jià)標(biāo)準(zhǔn)為（）、（）、（）、（）。16、在線性表的單鏈接存儲(chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為（），若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為（）。17、堆棧的特點(diǎn)是（），所以又稱（）表，隊(duì)列的特點(diǎn)是（），所以又稱（）表。18、（）通常稱作串的模式匹配。在一個(gè)主串中查找子串是否存在，存在返回（）；不存在返回()。19、在一個(gè)稀疏矩陣中，每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的（）、（）和（）三項(xiàng),同時(shí)存儲(chǔ)稀疏矩陣行數(shù)、列數(shù)和非零數(shù)據(jù)元素的個(gè)數(shù)。20、線性表的常見(jiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有（）、（）和（）。21、隊(duì)列簡(jiǎn)稱（）表，在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到（），被刪除的只能是排在（）的結(jié)點(diǎn)。二、單項(xiàng)選擇題1、一個(gè)堆棧的入棧序列為abcde，若出棧和入棧操作可間隔進(jìn)行，則出棧序列不可能的為（）。A、edcbaB、decbaC、decabD、abcde2、設(shè)A是一個(gè)m*n階矩陣，A按列序存儲(chǔ)在一組連續(xù)的存儲(chǔ)單元中，每個(gè)元素占用w個(gè)存儲(chǔ)單元，若A[1,1]的存儲(chǔ)地址為base，則A[i,j]的存儲(chǔ)地址為（）。A、base+[(i-1)*m+(j-1)]*wB、base+[(j-1)*m+(i-1)]*wC、base+（j*m+i）*wD、base+（j*m+i）*w3、設(shè)定樹(shù)根的層次為1，則有64個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（）。A、8B、7C、6D、4、在二叉樹(shù)的先序遍歷，中序遍歷和后序遍歷算法中，所有葉子結(jié)點(diǎn)的先后順序（）。A、都不相同Ｂ、前序遍歷和中序遍歷相同，而與后序遍歷不同Ｃ、完全相同Ｄ、前序遍歷和后序遍歷相同，而與中序遍歷不同5、關(guān)于有向圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)，下列敘述正確的是（）。①存儲(chǔ)矩陣不一定是對(duì)稱的;②第i行中1的個(gè)數(shù)為頂點(diǎn)i的出度;③第i列中1的個(gè)數(shù)為頂點(diǎn)i的入度;④矩陣中1的個(gè)數(shù)為圖中弧的數(shù)目;⑤很容易判斷頂點(diǎn)i和頂點(diǎn)j是否有弧相連。A、①②③④B、②③④⑤C、①③④⑤D、全對(duì)6、關(guān)于邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，正確的描述是（）。A、線性數(shù)據(jù)結(jié)構(gòu)必須采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、一種邏輯結(jié)構(gòu)，可以用不同的存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)，反之亦然C、一種邏輯結(jié)構(gòu)，可以用不同的存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)，反之不然D、一種存儲(chǔ)結(jié)構(gòu)只能表示一種邏輯結(jié)構(gòu)7、關(guān)于鏈表的特點(diǎn)描述不正確的是（）。A、存儲(chǔ)空間不一定連續(xù)；B、元素之間的后繼關(guān)系是由指針來(lái)體現(xiàn)的；C、邏輯上相鄰，物理上不一定相鄰；D、隨機(jī)存?。樞虼嫒。?，即訪問(wèn)任何一個(gè)元素的時(shí)間相同。8、在順序存儲(chǔ)（空間大小為m）的循環(huán)隊(duì)列q中，下列判滿正確的是（）。A、q.front%m=0;B、q.rear%m=0;C、(q.rear+1)%m=q.front;D、q.front=q.rear;9、已知廣義表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列運(yùn)算的結(jié)果:tail(head(tail(C)))=()。A、（a）B、(A)C、(b)D、A10、已給下圖，哪一項(xiàng)是該圖的拓?fù)渑判?？（）A、1，2，3，4，5B、1，3，2，4，5C、1，2，4，3，5D、1，2，3，5，411、已知含10個(gè)結(jié)點(diǎn)的二叉排序樹(shù)是一棵完全二叉樹(shù)，則該二叉排序樹(shù)在等概率情況下查找成功的平均查找長(zhǎng)度等于（）。A、1.0B、2.9C、3.4D、12、以下說(shuō)法錯(cuò)誤的是（）。A、散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。B、散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。C、裝填因子是散列法的一個(gè)重要參數(shù)，它反映散列表的裝填程度。D、散列表的查找效率主要取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。13、以下說(shuō)法正確的是（）。A、因鏈棧本身沒(méi)有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況B、因順序棧本身沒(méi)有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況C、對(duì)于鏈棧而言,在棧滿狀態(tài)下,如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“上溢”D、對(duì)于順序棧而言在棧滿狀態(tài)下如果此時(shí)再作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“下溢”14、下列判斷正確的是（）。A、如果兩個(gè)串含有相同的字符，則這兩個(gè)串相等。B、數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對(duì)它進(jìn)行插入、刪除等運(yùn)算。C、在索引順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長(zhǎng)度不僅與表中元素個(gè)數(shù)有關(guān)，而且與每一塊中元素個(gè)數(shù)有關(guān)。D、對(duì)任意圖，從它的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問(wèn)圖的每個(gè)頂點(diǎn)。15、對(duì)廣義表L=((a,b),c,d)進(jìn)行操作tail(head(L))的結(jié)果是（）。A、(c,d)B、(d)C、bD、(b)16、下列說(shuō)法正確的是（）。A、樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同B、樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷序列相同C、樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同D、樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷序列相同三、基本技能測(cè)試題1、已知一任意關(guān)鍵字序列{19,14,22,01,66,21,83,27,56,13}，按元素在序列中的次序構(gòu)造一棵平衡二叉樹(shù)，給出構(gòu)造過(guò)程（當(dāng)有調(diào)整時(shí)給出調(diào)整后的平衡二叉樹(shù)）并求查找成功的平均查找長(zhǎng)度。2、有待排序的元素序列{72，13，70，23，95，16，5，68，26，45}，請(qǐng)用快速排序的方法對(duì)上述序列排序，給出每一趟排序后的結(jié)果。3、畫出下圖的鄰接表存儲(chǔ)結(jié)構(gòu)示意圖，并根據(jù)鄰接表存儲(chǔ)結(jié)構(gòu)示意圖求出圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。4、學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是什么？5、已知二叉樹(shù)的先序序列為ABDEGCFHIJ，中序序列為DBGEAHFIJC，畫出這個(gè)二叉樹(shù)。6、給出一組關(guān)鍵字序列{29，18，25，47，58，12，15，10}，構(gòu)造初始堆，給出構(gòu)造工程。7、已知字符A、B、C、D、E、F的使用頻率分別為9、15、32、22、18、4，構(gòu)造哈夫曼樹(shù)（HuffmanTree），求出各個(gè)字符的哈夫曼編碼。8、已知一個(gè)無(wú)向圖的鄰接表如下圖所示。Λ421V1Λ421V1Λ1452V2Λ1452V244Λ53V3Λ53V3Λ3214V4Λ3214V4Λ325V5Λ325V5(1)畫出這個(gè)圖。(2)根據(jù)鄰接表，以v1為出發(fā)點(diǎn)，對(duì)圖進(jìn)行廣度優(yōu)先搜索和深度優(yōu)先搜索，寫出各自訪問(wèn)序列。ABCFEABCFEDG5065406045524250307010、給出下面二叉樹(shù)的先序遍歷、中序遍歷、后續(xù)遍歷和層序遍歷序列。11、已知無(wú)向圖如下，請(qǐng)完成。（1）給出圖的鄰接鏈表存儲(chǔ)結(jié)構(gòu)圖；（2）依據(jù)你的存儲(chǔ)結(jié)構(gòu)圖，寫出從A開(kāi)始的廣度和深度優(yōu)先遍歷序列。12、對(duì)于數(shù)據(jù)序列{49,38,65,97,76,13,27,50}，構(gòu)造平衡二叉樹(shù)，給出構(gòu)造過(guò)程。三、算法設(shè)計(jì)與編程題1、以順序表作為存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)實(shí)現(xiàn)線性表就地(即使用盡可能少的附加空間)逆置的算法，在原表的存儲(chǔ)空間內(nèi)將線性表數(shù)據(jù)元素順序有(a1，a2,...,an)逆置為(an,...,a2,a1)。2、用順序表存儲(chǔ)空間的動(dòng)態(tài)分配的方法實(shí)現(xiàn)線性表的插入算法。即在順序存儲(chǔ)的線性表中的第i個(gè)數(shù)據(jù)元素之前插入一個(gè)數(shù)據(jù)元素。3、已知Q是一個(gè)非空隊(duì)列，S是一個(gè)空棧。僅用隊(duì)列和棧的ADT函數(shù)和少量工作變量，編寫一個(gè)算法，將隊(duì)列Q中的所有元素逆置。棧的ADT函數(shù)有：makeEmpty(s:stack)；置空棧push(s:stack;value:datatype)；新元素value進(jìn)棧pop(s:stack):datatype；出棧，返回棧頂值isEmpty(s:stack):boolean；判?？辗耜?duì)列的ADT函數(shù)有：enqueue(q:queue;value:datatype)；元素value進(jìn)隊(duì)deQueue(q:queue):datatype；出隊(duì)列，返回隊(duì)頭值isEmpty(q:queue):boolean；判隊(duì)列空否4、圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)定義如下：鄰接矩陣:typedefstruct{intvexnum,arcnum;charvexs[100];intarcs[100,100]}MGraph;鄰接表：typedefstructarcptr{intadjvex;//鄰接點(diǎn)的存儲(chǔ)位置structarcptr*nextarc;}ArcNode;//下鄰接點(diǎn)typedefstructvexnode{chardata;//數(shù)據(jù)元素ArcNode*firstarc;}Vnode;//第一個(gè)鄰接點(diǎn)typedefstruct{intvexnum,arcnum;//圖的頂點(diǎn)個(gè)數(shù)Vnodevertices[100];}ALGraph;給出將無(wú)向圖的鄰接矩陣轉(zhuǎn)換成鄰接表的算法。

《數(shù)據(jù)結(jié)構(gòu)》綜合復(fù)習(xí)資料參考答案一、填空題1、答案：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶結(jié)構(gòu)的數(shù)據(jù)元素的集合2、答案：線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)3、答案：前驅(qū)、后繼、后繼4、答案：先進(jìn)后出、先進(jìn)先出、字符5、答案：15、子、86、答案：高、不、一7、答案：3、（a）、（（（b），c），（（（d））））8、答案：一個(gè)數(shù)學(xué)模型及定義在這個(gè)模型上的一組操作或運(yùn)算的總稱9、答案：O(n2)10、答案：p->datals->next;free(p);11、答案：abc*d/+ef*+12、答案：行、320、823213、答案：空、非空、長(zhǎng)度14、答案：集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)15、答案：正確性、易讀性、健壯性、效率16、答案：p->next、p+117、答案：先進(jìn)后出、先進(jìn)后出、先進(jìn)先出、先進(jìn)先出18、答案：子串的定位操作、子串在主串中的位置、019、答案：行號(hào)、列號(hào)、元素值20、答案：?jiǎn)捂湵?、雙鏈表、循環(huán)鏈表21、答案：先入先出、隊(duì)尾、隊(duì)頭二、單項(xiàng)選擇題題目12345678910答案CBBCDBDCBA題目111213141516答案BBACDA三、基本技能測(cè)試題1、答案：參見(jiàn)教材227-232頁(yè)。2、答案：參見(jiàn)教材273-276頁(yè)。3、答案：參見(jiàn)教材163頁(yè)和167-170頁(yè)。4、答案：（1）學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法；（2）初步掌握算法的時(shí)間分析和空間分析技術(shù)；（3）能夠設(shè)計(jì)符合軟件工程規(guī)范的、較復(fù)雜的程序；程序結(jié)構(gòu)清晰，正確易懂，較好的時(shí)間和空間復(fù)雜度。5、答案：6、答案：7、答案：A:0001B:001C:01D:11E:10F:00008、答案：（1）（2）廣度優(yōu)先搜索序列：V1->V2->V4->V5->V3深度優(yōu)先搜索序列：V1->V2->V5->V3->V49、答案：10、答案：先序遍歷序列：abdgcef中序遍歷序列：dgbaecf后續(xù)遍歷序列：gdbefca層序遍歷序列：abcdefg11、答案：（1）(2)廣度優(yōu)先遍歷序列：ABCGFDE深度優(yōu)先遍歷序列：ABDCEFG12、答案：三、算法設(shè)計(jì)與編程題1、答案：要將該表逆置，可以將表中的開(kāi)始結(jié)點(diǎn)與終端結(jié)點(diǎn)互換，第二個(gè)結(jié)點(diǎn)與倒數(shù)第二個(gè)結(jié)點(diǎn)互換，如此反復(fù)，就可將整個(gè)表逆置了。算法如下：

//表結(jié)構(gòu)定義同上

voidReverseList(Seqlist*L)

{Datatypet;//設(shè)置臨時(shí)空間用于存放data

inti;

for(i=0;i<L->length/2;i++)

{t=L->data[i];//交換數(shù)據(jù)

L->data[i]

=L->data[L->length-1-i]

;

L->data[L->length-1-i]=t

;

}

}2、答案：StatusListInsert_sq(sequenlist&L,inti,entrytypee){if(i<1||i>L.len+1)returnERROR;//i值不合法if(L.len>=L.listsize)//檢查空間是否已滿{newbase=(elemtype*)realloc(L.a,(listsize+LISTINCREMENT)*sizeof(elemtype));//增加空間if(!newbase)exit(Overflow);//空間增加失敗L.a=newbase;//空間增加成功L.listsize+=LISTINCREMENT;}q=&(L.a[i-1])；//q指向插入位置for(p=&(L.a[L.len-1]);p>=q;--p)*(p+1)=*p;//將線性表第i個(gè)元素之后的所有元素向后移動(dòng)*q=e;//插入e++L.len;//表長(zhǎng)+1ReturnOK;}3、答案：voidchange（queueq,stacks）{datatypetemp;