華師大數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題課件

數(shù)據(jù)結(jié)構(gòu)學(xué)位考試復(fù)習(xí)提綱2013年10月考試時(shí)間90分鐘

第一部分題型1．單選題：2分×15=30分概述1、線性表2、棧隊(duì)串2、數(shù)組廣義表1、樹3、圖2、排序2、查找22．判斷題：2分×10=20分概述1、線性表1、棧隊(duì)串1、數(shù)組廣義表1、樹2、圖2、排序1、查找13．填空題：2分×11=22分概述1、線性表1、棧隊(duì)串1、數(shù)組廣義表2、樹2、圖2、排序1、查找14．應(yīng)用題：8分×2=16分樹1、排序15．程序題：6分×2=12分二叉鏈表1、順序表1數(shù)據(jù)結(jié)構(gòu)學(xué)位考試復(fù)習(xí)提綱考試時(shí)間90分鐘第一部分1、四種基本邏輯結(jié)構(gòu)是：____？2、算法區(qū)別于程序的主要地方是____。3、算法評(píng)價(jià)一般考慮四個(gè)方面：____、____、____、____；其中在數(shù)據(jù)結(jié)構(gòu)里主要考慮____。4、時(shí)間和空間性能往往是一對(duì)矛盾嗎？5、空間耗費(fèi)包括代碼部分嗎？6、程序段時(shí)間復(fù)雜性的簡(jiǎn)單判斷？

7、算法的時(shí)間復(fù)雜性越高，則從計(jì)算機(jī)速度提高得到的收益就越大嗎？第二部分復(fù)習(xí)提綱(不分題型)1、四種基本邏輯結(jié)構(gòu)是：____？第二部分復(fù)習(xí)提綱(不分題1、順序表和鏈表哪個(gè)可以按序號(hào)隨機(jī)存??？按值能否隨機(jī)存??？2．順序表和鏈表中的邏輯關(guān)系分別用什么表示？3．鏈表中結(jié)點(diǎn)物理地址一定不連續(xù)嗎？4、尋找單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前趨的時(shí)間復(fù)雜度分別是____。5、單鏈表中插入、刪除結(jié)點(diǎn)的執(zhí)行步驟？6、何謂存儲(chǔ)密度？順序表、鏈表分別如何？L…

a1

a2an1、順序表和鏈表哪個(gè)可以按序號(hào)隨機(jī)存?。堪粗的芊耠S機(jī)存??？L7、例：將順序表中所有負(fù)數(shù)移動(dòng)到表的前端，要求移動(dòng)次數(shù)小。解：雙向掃描：從前向后找一個(gè)正數(shù)，再從后向前找一個(gè)負(fù)數(shù)，然后交換兩者位置。復(fù)雜性為O（n）。voidmoves(sqlist*L){inti,j;datatypex;i=1;j=L->n;//設(shè)數(shù)組下標(biāo)從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??;}}}+--+--++-+--+-7、例：將順序表中所有負(fù)數(shù)移動(dòng)到表的前端，要求移動(dòng)次數(shù)小。+8、例：刪除順序表中所有的正數(shù)，要求移動(dòng)次數(shù)小。解：搜索順序表，對(duì)每一個(gè)正數(shù)，先不刪除，而是累計(jì)當(dāng)前正數(shù)個(gè)數(shù)s，于是，對(duì)每個(gè)非正數(shù)，將它一次性前移s位。算法復(fù)雜性為O（n）。voiddels(sqlist*L){ints,i;s=0; //正數(shù)計(jì)數(shù)器

for(i=0;i<L->n;i++)if(L->data[i]>0s++; //累計(jì)當(dāng)前正數(shù)

elseif(s>0)L->data[i-s]=l->data[i];//向前移動(dòng)s位

L->n=L->n-s; //調(diào)整表長(zhǎng)}+--+--++-+--+-8、例：刪除順序表中所有的正數(shù)，要求移動(dòng)次數(shù)小。+--1、什么問題需要用棧或隊(duì)列來描述？2、怎樣克服假溢出？3、已知進(jìn)棧序列，怎樣判斷哪些出棧序列可能或不可能？4、C語言中，串的存儲(chǔ)方式是_____。5、空串、空白串、串相等、模式匹配含義？6、strcmp()、strlen()、strcat()、strcpy()函數(shù)功能？1、什么問題需要用?；蜿?duì)列來描述？1、數(shù)組的基本運(yùn)算是讀、寫。沒有插入刪除等運(yùn)算2、為什么說數(shù)組是隨機(jī)存儲(chǔ)結(jié)構(gòu)？3、對(duì)稱矩陣、稀疏矩陣，誰壓縮存儲(chǔ)后還可以隨機(jī)存??？4、十字鏈表中的結(jié)點(diǎn)需存儲(chǔ)非零元素的哪五個(gè)信息？5、廣義表的分類，圖形表示與識(shí)別？6、廣義表不僅是線性表的推廣，也是樹的推廣。7、用head()和tail()函數(shù)在廣義表A=(a,(x,y,z),b)中取出原子b。1、數(shù)組的基本運(yùn)算是讀、寫。沒有插入刪除等運(yùn)算1、3個(gè)結(jié)點(diǎn)可構(gòu)成____個(gè)不同形態(tài)的二叉樹。2、二叉樹的先根遍歷序列和后根遍歷序列相同，則該二叉樹的特征是____。3、能否有二叉樹，其任何遍歷次序都相同？4、某完全二叉樹有5個(gè)葉子，則其結(jié)點(diǎn)總數(shù)為____。(10或9，一般2n或2n-1)5、某完全二叉樹的第5層只有6個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是____。6、樹的先根遍歷需要借助__來實(shí)現(xiàn)、層次遍歷需要借助__來實(shí)現(xiàn)。(棧,隊(duì)列)7、線索二叉樹上，求結(jié)點(diǎn)的(遍歷)前趨和后繼時(shí)可利用線索得到，是否就不必進(jìn)行遍歷了？8、線索二叉樹中，線索的含義？9、哈夫曼樹的特點(diǎn)？1、3個(gè)結(jié)點(diǎn)可構(gòu)成____個(gè)不同形態(tài)的二叉樹。10、如何畫中序、先序、后序線索二叉鏈表（線索二叉樹）？解：以中序線索二叉鏈表為例，下列二叉樹的中序線索二叉鏈表如圖所示。詳細(xì)過程見課本。ABCDEFCBDEA00000F1111111NULLNULL中序：DBEFACABCDEFNULLNULL中序線索二叉樹中序線索二叉鏈表10、如何畫中序、先序、后序線索二叉鏈表（線索二叉樹）？AB11．如何由先序＋中序、后序＋中序還原出二叉樹？解：①對(duì)前序序列，序列的第一個(gè)點(diǎn)就是整個(gè)二叉樹的根；②對(duì)后序序列，序列的最后一個(gè)點(diǎn)就是整個(gè)二叉樹的根；③對(duì)中序序列，以根為界，序列的前一部分為根的左子樹，后一部分為根的右子樹；并且，前一部分是左子樹的中序序列，后一部分是右子樹的中序序列。若給定了前序和中序序列，反復(fù)利用上面的①和③，即由前序序列找到根，由中序序列得到左、右子樹；再對(duì)每個(gè)子樹由前序序列找到子樹的根，由中序序列得到子樹的左、右子樹，等等類推，每次得到一個(gè)點(diǎn)(子樹的根)，從而逐漸還原和構(gòu)造出該二叉樹。11．如何由先序＋中序、后序＋中序還原出二叉樹？例由先根和中根序列構(gòu)造二叉樹G先根序列中根序列ABHFDECKGHBDFAEKCHFDKGBCEA后根+中根呢？例由先根和中根序列構(gòu)造二叉樹G先根序列中根序列ABHFD12、例：判斷二叉樹是否所有結(jié)點(diǎn)都為正數(shù)。解：設(shè)二叉樹根指針類型為bitree，函數(shù)名為detect，函數(shù)返回判斷結(jié)果intdetect(bitreet){if(t==NULL)return1; //空樹返回真，遞歸出口if(t->data<=0)return0; //根不為正數(shù)，返回假returndetect(t->lchild)&&detect(t->rchild); //由左右子樹共同決定真或假}12、例：判斷二叉樹是否所有結(jié)點(diǎn)都為正數(shù)。13、例：判斷是否二叉樹t否滿足小根堆的特點(diǎn)。解：設(shè)二叉樹結(jié)點(diǎn)類型為bitree，函數(shù)名為detect，函數(shù)返回判斷結(jié)果。intdetect(bitreet){if(t==NULL)return1; //空樹返回真

if((t->lchild!=NULL&&t->lchild->data<t->data)||(t->rchild!=NULL&&t->rchild->data<t->data))return0;returndetect(t->lchild)&&detect(t-rchild);}13、例：判斷是否二叉樹t否滿足小根堆的特點(diǎn)。1．n個(gè)頂點(diǎn)及e條邊的無向圖，鄰接表中的邊結(jié)點(diǎn)數(shù)為____，鄰接矩陣中1的個(gè)數(shù)為___。若是有向圖呢？2、n個(gè)頂點(diǎn)的無向圖、有向圖，邊數(shù)范圍分別是多少？3、圖的DFS遍歷類似樹的____遍歷，是其推廣。4、在鄰接矩陣和鄰接表上進(jìn)行BFS或DFS遍歷時(shí)，時(shí)間復(fù)雜性分別為多少？5、某圖有3個(gè)連通分量，則要訪問所有頂點(diǎn)時(shí)，必須調(diào)用__次DFS遍歷算法。6、若有向圖的鄰接矩陣中，主對(duì)角線以下的元素均為零，則該圖可拓?fù)渑判騿幔?、拓?fù)渑判蚩捎靡苑治龉こ棠芊耥樌M(jìn)行。8、何謂關(guān)鍵路徑？0101010101010111010001100V11V22V33V44……m24∧1∧3∧1．n個(gè)頂點(diǎn)及e條邊的無向圖，鄰接表中的邊結(jié)點(diǎn)數(shù)為____1．各種排序算法的復(fù)雜度如何？(好、壞、平均?)(1)、哪些最好和最壞時(shí)間復(fù)雜度都為O(nlog2n)？(2)、趟數(shù)最少和最多情況如何？(3)、哪些空間復(fù)雜性為O(n)？2、初始序列基本有序時(shí)，哪些排序方法好？3、n個(gè)數(shù)據(jù)直接插入排序，可能的最少比較次數(shù)是____。4、希爾排序的增量序列中，最后一個(gè)增量為____。5、堆的定義？6、基數(shù)排序的排序趟數(shù)？練習(xí)：(49,38,13,76,65,97,27,49)7．各種排序方法步驟如何？（會(huì)寫每趟結(jié)果，冒泡、選擇、快速排序等）1．各種排序算法的復(fù)雜度如何？(好、壞、平均?)練習(xí)：(491、順序查找法既可用于順序表，也可用于鏈表嗎？2、二分查找對(duì)