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

1、四種基本邏輯結(jié)構(gòu)是：____？2、算法區(qū)別于程序的主要地方是____。3、算法評價一般考慮四個方面：____、____、____、____；其中在數(shù)據(jù)結(jié)構(gòu)里主要考慮____。4、時間和空間性能往往是一對矛盾嗎？5、空間耗費包括代碼部分嗎？6、程序段時間復(fù)雜性的簡單判斷？

7、算法的時間復(fù)雜性越高，則從計算機速度提高得到的收益就越大嗎？

第二部分復(fù)習(xí)提綱(不分題型)1、順序表和鏈表哪個可以按序號隨機存??？按值能否隨機存?。?．順序表和鏈表中的邏輯關(guān)系分別用什么表示？3．鏈表中結(jié)點物理地址一定不連續(xù)嗎？4、尋找單鏈表中當(dāng)前結(jié)點的后繼和前趨的時間復(fù)雜度分別是____。5、單鏈表中插入、刪除結(jié)點的執(zhí)行步驟？6、何謂存儲密度？順序表、鏈表分別如何？L…

a1

a2

an7、例：將順序表中所有負數(shù)移動到表的前端，要求移動次數(shù)小。解：雙向掃描：從前向后找一個正數(shù)，再從后向前找一個負數(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??;//從后向前找負數(shù)

if(i<j){//交換

x=L->data[i];L->data[i]=L->data[j];L->data[j]=x;i++;j??;}}}+--+--++-+--+-8、例：刪除順序表中所有的正數(shù)，要求移動次數(shù)小。解：搜索順序表，對每一個正數(shù)，先不刪除，而是累計當(dāng)前正數(shù)個數(shù)s，于是，對每個非正數(shù)，將它一次性前移s位。算法復(fù)雜性為O（n）。voiddels(sqlist*L){ints,i;s=0; //正數(shù)計數(shù)器

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

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

L->n=L->n-s; //調(diào)整表長}+--+--++-+--+-1、什么問題需要用?；蜿犃衼砻枋?？2、怎樣克服假溢出？3、已知進棧序列，怎樣判斷哪些出棧序列可能或不可能？4、C語言中，串的存儲方式是_____。5、空串、空白串、串相等、模式匹配含義？6、strcmp()、strlen()、strcat()、strcpy()函數(shù)功能？1、數(shù)組的基本運算是讀、寫。沒有插入刪除等運算2、為什么說數(shù)組是隨機存儲結(jié)構(gòu)？3、對稱矩陣、稀疏矩陣，誰壓縮存儲后還可以隨機存??？4、十字鏈表中的結(jié)點需存儲非零元素的哪五個信息？5、廣義表的分類，圖形表示與識別？6、廣義表不僅是線性表的推廣，也是樹的推廣。7、用head()和tail()函數(shù)在廣義表A=(a,(x,y,z),b)中取出原子b。1、3個結(jié)點可構(gòu)成____個不同形態(tài)的二叉樹。2、二叉樹的先根遍歷序列和后根遍歷序列相同，則該二叉樹的特征是____。3、能否有二叉樹，其任何遍歷次序都相同？4、某完全二叉樹有5個葉子，則其結(jié)點總數(shù)為____。(10或9，一般2n或2n-1)5、某完全二叉樹的第5層只有6個結(jié)點，則其葉子結(jié)點數(shù)是____。6、樹的先根遍歷需要借助__來實現(xiàn)、層次遍歷需要借助__來實現(xiàn)。(棧,隊列)7、線索二叉樹上，求結(jié)點的(遍歷)前趨和后繼時可利用線索得到，是否就不必進行遍歷了？8、線索二叉樹中，線索的含義？9、哈夫曼樹的特點？10、如何畫中序、先序、后序線索二叉鏈表（線索二叉樹）？解：以中序線索二叉鏈表為例，下列二叉樹的中序線索二叉鏈表如圖所示。詳細過程見課本。ABCDEFCBDEA00000F1111111NULLNULL中序：DBEFACABCDEFNULLNULL中序線索二叉樹中序線索二叉鏈表11．如何由先序＋中序、后序＋中序還原出二叉樹？解：①對前序序列，序列的第一個點就是整個二叉樹的根；②對后序序列，序列的最后一個點就是整個二叉樹的根；③對中序序列，以根為界，序列的前一部分為根的左子樹，后一部分為根的右子樹；并且，前一部分是左子樹的中序序列，后一部分是右子樹的中序序列。若給定了前序和中序序列，反復(fù)利用上面的①和③，即由前序序列找到根，由中序序列得到左、右子樹；再對每個子樹由前序序列找到子樹的根，由中序序列得到子樹的左、右子樹，等等類推，每次得到一個點(子樹的根)，從而逐漸還原和構(gòu)造出該二叉樹。例由先根和中根序列構(gòu)造二叉樹G先根序列中根序列ABHFDECKGHBDFAEKCHFDKGBCEA后根+中根呢？12、例：判斷二叉樹是否所有結(jié)點都為正數(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); //由左右子樹共同決定真或假}13、例：判斷是否二叉樹t否滿足小根堆的特點。解：設(shè)二叉樹結(jié)點類型為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);}1．n個頂點及e條邊的無向圖，鄰接表中的邊結(jié)點數(shù)為____，鄰接矩陣中1的個數(shù)為___。若是有向圖呢？2、n個頂點的無向圖、有向圖，邊數(shù)范圍分別是多少？3、圖的DFS遍歷類似樹的____遍歷，是其推廣。4、在鄰接矩陣和鄰接表上進行BFS或DFS遍歷時，時間復(fù)雜性分別為多少？5、某圖有3個連通分量，則要訪問所有頂點時，必須調(diào)用__次DFS遍歷算法。6、若有向圖的鄰接矩陣中，主對角線以下的元素均為零，則該圖可拓撲排序嗎？7、拓撲排序可用以分析工程能否順利進行。

8、何謂關(guān)鍵路徑？0101010101010111010001100V11V22V33V44……m24∧1∧3∧1．各種排序算法的復(fù)雜度如何？(好、壞、平均?)(1)、哪些最好和最壞時間復(fù)雜度都為O(nlog2n)？(2)、趟數(shù)最少和最多情況如何？(3)、哪些空間復(fù)雜性為O(n)？2、初始序列基本有序時，哪些排序方法好？3、n個數(shù)據(jù)直接插入排序，可能的最少比較次數(shù)是____。4、希爾排序的增量序列中，最后一個增量為____。5、堆的定義？6、基數(shù)排序的排序趟數(shù)？練習(xí)：(49,38,13,76,65,97,27,49)7．各種排序方法步驟如何？（會寫每趟結(jié)果，冒泡、選擇、快速排序等）1、順序查找法既可用于順序表，也可用于鏈表嗎？2、二分查找對數(shù)據(jù)的要求？3