華師網(wǎng)絡(luò)教育-本科-數(shù)據(jù)結(jié)構(gòu)-期末復(fù)習(xí)資料

數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)提綱20136月題型1分×15=30分21222分×10=20分11213分×11=22分12214分×2=16分樹1、排序15分×2=12二叉鏈表1、順序表11章概論1。2。3、若結(jié)點(diǎn)的存儲地址與結(jié)點(diǎn)內(nèi)容有某種確定的關(guān)系，則相應(yīng)的存儲結(jié)構(gòu)應(yīng)為散列存儲。4、一種邏輯結(jié)構(gòu)只能對應(yīng)一種存儲結(jié)構(gòu)嗎？錯(cuò)5、數(shù)值型和非數(shù)值型數(shù)據(jù)、原子類型和結(jié)構(gòu)類型、加工型和引用型運(yùn)算含義？數(shù)據(jù)可分為數(shù)值型和非數(shù)值型數(shù)據(jù)類型可分為原子類型和結(jié)構(gòu)類型運(yùn)算可分為加工型和引用型6、數(shù)據(jù)結(jié)構(gòu)可分為邏輯結(jié)構(gòu)和非邏輯結(jié)構(gòu)嗎？錯(cuò)7、算法的正確性，一般不進(jìn)行形式化的證明，而是用測試來驗(yàn)證。對8。9、線性結(jié)構(gòu)可以順序存儲，也可以鏈?zhǔn)酱鎯?非線性結(jié)構(gòu)只能鏈?zhǔn)酱鎯徨e(cuò)10、程序設(shè)計(jì)的實(shí)質(zhì)是：數(shù)據(jù)的表示和數(shù)據(jù)處理，或者說，程序=數(shù)據(jù)結(jié)構(gòu)＋算法。2章線性表：1、順序表、鏈表優(yōu)缺點(diǎn)？邏輯關(guān)系如何表示？順序表是用數(shù)組實(shí)現(xiàn)的，鏈表是用指針或游標(biāo)實(shí)現(xiàn)的。順序表有三個(gè)優(yōu)點(diǎn)：方法簡單，各種高級語言中都有數(shù)組，容易實(shí)現(xiàn)。不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷。但它也有兩個(gè)缺點(diǎn)：在順序表中做插入刪除操作時(shí)，對n較大的順序表效率低。需要預(yù)先分配足夠大的存儲空間，估計(jì)過大將造成空間浪費(fèi)造成溢出。鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。（即指針域或游標(biāo)域來表示邏輯關(guān)系。2、在順序表中插入和刪除結(jié)點(diǎn)時(shí)總要移動其它結(jié)點(diǎn)。錯(cuò)3、順序表插入和刪除時(shí)，移動元素的個(gè)數(shù)與該元素的位置有關(guān)。對4、順序表中按值查找、按序號查找運(yùn)算的復(fù)雜性分別為o(n)、o(1)。5、在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲量和整個(gè)結(jié)點(diǎn)所占的存儲量之比稱作存儲密度。6、鏈表的結(jié)點(diǎn)地址一定不連續(xù)。錯(cuò)（可連續(xù)也可不連續(xù)）7、用尾指針表示單循環(huán)鏈表的好處是找頭找尾都方便。8*p有且僅有一個(gè)后繼結(jié)點(diǎn)的條件是p->next!=null&。9．例：將順序表中所有負(fù)數(shù)移動到表的前端，要求移動次數(shù)小。為（。voidmoves(sqlist*L){inti,j;datatypex;i=1;j=L->n; //1開始while(i<j){while(L->data[i]<0&&i<j)i++;//從前向后找正數(shù)while(L->data[j]>=0&&i<j)j--;//從后向前找負(fù)數(shù)if(i<j){//交換x=L->data[i];L->data[i]=L->data[j];L->data[j]=x;i++;j--;}}}10．例：刪除順序表中所有的正數(shù)，要求移動次數(shù)小。解：搜索順序表，對每一個(gè)正數(shù)，先不刪除，而是累計(jì)當(dāng)前正數(shù)個(gè)數(shù)數(shù)，將它一次性前移s位。算法復(fù)雜性為（。voiddels(sqlist*L){ints,i;s=0; //for(i=0;i<L->n;i++){if(L->data[i]>0)s++; //累計(jì)當(dāng)前正數(shù)elseif(s>0)L->data[i-s]=l->data[i]; //s位}L->n=L->n-s;}

//調(diào)整表長第３章棧、隊(duì)列和串1、棧和隊(duì)列的共同特點(diǎn)是運(yùn)算受限的線性表。2、棧操作的原則是后進(jìn)先出或先進(jìn)后出。3、設(shè)進(jìn)棧順序?yàn)镕，出棧順序?yàn)?。4、若進(jìn)棧序列為a,b,c，則通過入出棧操作能得到的a,b,c的不同排列個(gè)數(shù)為5。5、設(shè)入棧序列為A,B,C,D，則可能的出棧序列有哪些？（哪些不可能？）6、順序棧在進(jìn)行入棧運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行出棧運(yùn)算時(shí)，可能發(fā)生棧的下溢。7、順序棧、鏈棧上進(jìn)行進(jìn)棧操作時(shí)，誰可不需判斷棧滿？鏈棧8、鏈棧一般不需要頭結(jié)點(diǎn)，因?yàn)闊o頭結(jié)點(diǎn)的鏈棧運(yùn)算也很方便。對9pnode;p->data=x;p->next=top;top->p_4章多維數(shù)組和廣義表1．?dāng)?shù)組的基本運(yùn)算。讀、寫，沒有插入刪除運(yùn)算2、多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲方式是因。數(shù)組的元素處行和列兩個(gè)關(guān)系中3、數(shù)組各元素在內(nèi)存中連續(xù)存放，故前后相鄰的兩元素物理地址相差為1或-1。對4、多維數(shù)組可以順序儲存，所以實(shí)際上是一種順序表？錯(cuò)5CA[20][10]212000，則元素A[8][9]2000+89*2。6數(shù)組A[1..8][1..10]中每個(gè)元素占3個(gè)單元從首地址SA開始存放若該數(shù)組按列存放，則元素A[8][5]的地址是SA+39*3 。7A[1..n][1..n])A[i][j]對應(yīng)位置B[k]，則k=i*(i-1)/2+j。8、稀疏矩陣常用的壓縮存儲方法有兩種，即十字鏈表、三元組表。9、十字鏈表中的結(jié)點(diǎn)需存儲非零元素的五個(gè)信息：行號、列號、值、行指針、列指針。10、稀疏矩陣的三元組表示中，三元組是指非零元素的行號、列號和值三項(xiàng)。5章樹型結(jié)構(gòu)1、某樹所有結(jié)點(diǎn)的度數(shù)之和為100，則樹中邊數(shù)為100。2、樹上每個(gè)結(jié)點(diǎn)都可有多個(gè)孩子、一個(gè)雙親嗎？錯(cuò)（根無）3、3個(gè)結(jié)點(diǎn)可構(gòu)成5個(gè)不同形態(tài)的二叉樹。4、何謂完全二叉樹？（會識別）P915、二叉樹必須有結(jié)點(diǎn)的度為2嗎錯(cuò) 可否所有點(diǎn)的度都小于2？對6、樹的度是指樹中結(jié)點(diǎn)的最大度數(shù)，所以二叉樹的度為2。錯(cuò)7、某完全二叉樹有7個(gè)葉子，則其結(jié)點(diǎn)總數(shù)（13或14,即2n-1或2n）8、若二叉樹中沒有度為1的結(jié)點(diǎn)，則為滿二叉樹？錯(cuò)9、滿二叉樹是一種特殊的完全二叉樹嗎？對10、深度為k的二叉樹，結(jié)點(diǎn)數(shù)至多為2k-1，結(jié)點(diǎn)數(shù)至少為k。11、深度為k的二叉樹，葉子數(shù)至多為2k-1，葉子數(shù)至少為1。12、高度為n、結(jié)點(diǎn)數(shù)也為n的二叉樹，共有2n-1棵。(即等于滿二叉樹最底層葉子數(shù))13、200個(gè)結(jié)點(diǎn)的二叉樹，深度至多為200，深度至少為8。14、在深度為7的二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最少為_1_，最多為16(24)_。15、有無可能某二叉樹的任何遍歷次序都相同？有（一個(gè)節(jié)點(diǎn)或空樹）16、某二叉樹的先根遍歷序列和后根遍歷序列相同，則該二叉樹的特征是一個(gè)節(jié)點(diǎn)或空樹。17、二叉樹、森林相互轉(zhuǎn)換。P117如何畫中序、先序、后序線索二叉鏈表（線索二叉樹解：以中序線索二叉鏈表為例，下列二叉樹的中序線索二叉鏈表如圖所示。詳細(xì)過程見課本。例：求二叉樹高度。解：設(shè)二叉樹結(jié)點(diǎn)類型為bitree，函數(shù)名為high，函數(shù)返回高度。inthigh(bitreet){intL,R;if(t==NULL)return0; //0，遞歸出口L=high(t->lchild);R=high(t->rchild)

求左子樹高度求右子樹高度return(L>R?L:R)+1; =+1}1的結(jié)點(diǎn)數(shù)。解：設(shè)二叉樹結(jié)點(diǎn)類型為bitree，函數(shù)名為sum1，函數(shù)返回結(jié)點(diǎn)數(shù)。intsum1(bitreet){intL,R;if(t==NULL)return0;L=sum1(t->lchild);R=sum1(t->rchild)

//當(dāng)前樹為空，遞歸出口求左子樹中相應(yīng)結(jié)點(diǎn)數(shù)求右子樹中相應(yīng)結(jié)點(diǎn)數(shù)if((t->lchild==NULL&&t->rchild!=NULL)||(t->lchild!=NULL&&t->rchild==NULL))//當(dāng)前結(jié)點(diǎn)度為也1returnL+R+1;//度1結(jié)點(diǎn)數(shù)=左子樹中度1結(jié)點(diǎn)數(shù)+右子樹中度1結(jié)點(diǎn)數(shù)+1elsereturnL+R;}22．例：求二叉樹中度為2的結(jié)點(diǎn)數(shù)。解：設(shè)二叉樹結(jié)點(diǎn)類型為bitree，函數(shù)名為sum2，函數(shù)返回結(jié)點(diǎn)數(shù)。intsum2(bitreet){intL,R;if(t==NULL)return0;L=sum2(t->lchild);R=sum2(t->rchild)

//當(dāng)前樹為空，遞歸出口求左子樹中相應(yīng)結(jié)點(diǎn)數(shù)求右子樹中相應(yīng)結(jié)點(diǎn)數(shù)if(t->lchild!=NULL&&t->rchild!=NULL)//當(dāng)前結(jié)點(diǎn)度為也2returnL+R+1;//度2結(jié)點(diǎn)數(shù)=左子樹中度2結(jié)點(diǎn)數(shù)+右子樹中度2結(jié)點(diǎn)數(shù)+1elsereturnL+R;}第6章圖1、n個(gè)頂點(diǎn)的有向圖，最少0 條邊；最多_n(n-1) 條邊。2、n個(gè)頂點(diǎn)的無向圖，最少0 條邊，最多條邊。3、某無向圖有28條邊，則其頂點(diǎn)數(shù)最少8 。4、某圖所有頂點(diǎn)的度數(shù)之和為200，則邊數(shù)條。5、n個(gè)頂點(diǎn)的強(qiáng)連通圖若只有n條邊，則該有向圖的形狀是環(huán)。6、n個(gè)結(jié)點(diǎn)的有向圖，若它有n(n－1)條邊，則它一定是強(qiáng)連通的。對7、有向圖出度、入度關(guān)系？出度總和=入度總和8、含n個(gè)頂點(diǎn)的無向圖，其鄰接矩陣中非零元素的個(gè)數(shù)就是圖中的邊數(shù)。錯(cuò)（2倍）9、在n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為2e_。10n個(gè)頂點(diǎn)和e_o(n)_（求入讀看列數(shù)）11、有向圖邊數(shù)=鄰接矩陣中1的個(gè)數(shù)；也=鄰接表中的邊表結(jié)點(diǎn)數(shù)。正確12、無向圖邊數(shù)=鄰接矩陣中1的個(gè)數(shù)的一半；也=鄰接表中的邊表結(jié)點(diǎn)數(shù)的一半。正確7章排序1、內(nèi)排序是指數(shù)據(jù)全部在內(nèi)存中進(jìn)行排序，穩(wěn)定性是指數(shù)據(jù)中相同關(guān)鍵字的數(shù)據(jù)排序前后相對順序不改變。2、可以將排序算法分為：插入排序、交換排序、選擇排序、歸并排序、分配排序。3、“就地排序”是指排序算法輔助空間的復(fù)雜度為O(1)。4．各種排序算法的結(jié)果總結(jié)。(好、壞、平均性能？穩(wěn)定性？)5、不穩(wěn)定的排序算法沒有實(shí)際的應(yīng)用價(jià)值嗎？錯(cuò)6、誰的空間復(fù)雜性為O(logn)？快速排序27、時(shí)間復(fù)雜性為O(nlogn)且空間復(fù)雜性為O(1)的排序方法是堆排序。28、Shell排序穩(wěn)定嗎？（不穩(wěn)定）其時(shí)間性能與增量序列的選取關(guān)系大不大？對各種排序方法步驟（會寫每趟結(jié)果，歸并、小根堆、直選、快速、希爾練習(xí)：(49,38,13,76,65,97,27,49)8章查找表1、查找表的邏輯結(jié)構(gòu)是集合。2、哪些方法屬于靜態(tài)查找、動態(tài)查找？（會區(qū)分）二者根本區(qū)別？有沒有修改數(shù)據(jù)結(jié)構(gòu),如果結(jié)構(gòu)不變屬于靜態(tài)查找(施加在其上的操作不同)3、對長度為100的順序表，在等概率情況下，查找成功時(shí)的平均查找長度為在找不成功時(shí)的平均查找長度50.5、100(或101)41055個(gè)元素的概率相同，均為3/40，則查找任一元素的平均查找長度為()。1*1/8+2*1/8+3*1/8+