洛陽理工數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)必過

選擇題〔2*10=20)1、鏈表的特點線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)。數(shù)據(jù)元素ai的存儲映像稱為結(jié)點，包括2個域：存數(shù)據(jù)的數(shù)據(jù)域、存后繼存儲位置的指針域。1)線性鏈表(單鏈表)特點：每個結(jié)點只包含1個指針域。在單鏈表的第一個結(jié)點之前附設(shè)的一個結(jié)點，稱之為頭結(jié)點。假設(shè)L是LinkList型變量，那么L為單鏈表的頭指針，它指向表中第一個結(jié)點；L->next為第一個結(jié)點地址，L->next=NULL為空表。生成結(jié)點：p=(LinkList)malloc(sizeof(LNode))回收結(jié)點：free(q)2)循環(huán)鏈表特點：表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表的操作與線性鏈表根本一致，差異僅在于算法中的循環(huán)條件不是P或P->next是否為空，而是它們是否等于頭指針。3)雙向鏈表特點：有2個指針域，其一指向直接后繼，另一指向直接前趨。2、棧對的特點1.棧：是限定僅在表尾進行插入或刪除操作的線性表。表尾端稱為棧頂，表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為后進先出的線性表。2.隊列：是一種先進先出的線性表，它只允許在表的一端進行插入，而另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端那么稱為隊頭。1)鏈隊列：用鏈表示的隊列。一個隊列需要兩個分別指示隊頭和隊尾的指針〔分別成為頭指針和尾指針〕才能確定唯一。和單鏈表一樣，也給鏈隊列添加一個頭結(jié)點，并令頭指針指向頭結(jié)點。2)循環(huán)隊列：與順序棧類似，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素及隊列尾元素的位置。初始化建空隊列時，令front=rear=0，每當(dāng)插入新的隊列尾元素時，“尾指針增1”；每當(dāng)刪除隊列頭元素時，“頭指針增1”。3、二維數(shù)組Am*n計算任意ai*j元素地址。A1*1為首地址假設(shè)線性表的每個元素需占用size個存儲單元。以行存儲：Loc[i,j]=Loc[1,1]+〔n*(i-1)+j-1〕*size以列存儲：Loc[i,j]=Loc[1,1]+〔m*(j-1)+i-1〕*size3、二叉樹性質(zhì)，特點1.二叉樹：是一種樹型的結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹〔即二叉樹中不存在度大于2的結(jié)點〕，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.二叉樹的性質(zhì)：1)性質(zhì)1：在二叉樹的第i層上至多有2的i減1次方個結(jié)點(i≥1)。2)性質(zhì)2：深度為k的二叉樹至多有2的k次方減1個結(jié)點(k≥1)。深度為k的二叉樹至少有k個結(jié)點(k≥1)。深度為k的完全二叉樹至少有2的k次方減2的k減1次方個結(jié)點(k≥1)。3)性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，那么n0=n2+1。4)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。5)性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹〔其深度為[log2n]+1〕的結(jié)點按層序編號〔從第1層到第[log2n]+1層，每層從左到右〕，那么對任一結(jié)點i〔1≤i≤n〕有：a)如果i=1，那么結(jié)點i是二叉樹的根，無雙親；如果i>1，那么其雙親PARENT(i)是結(jié)點[i/2]。b)如果2i>n，那么結(jié)點i無左孩子〔結(jié)點i為葉子結(jié)點〕；否那么其左孩子LCHILD(i)是結(jié)點2i。c)如果2i+1>n，那么結(jié)點i無右孩子；否那么其右孩子RCHILD(i)是結(jié)點2i+1。5、計算時間復(fù)雜度時間復(fù)雜度：算法中根本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間度量記作，T(n)=O(f(n))；他表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱做算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。例如：(a){++x;s=0;}(b)for(i=1;i<=n;++i){++x;s+=x;}(c)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}含根本操作“x增1”的語句的頻度分別為1、n和n2，那么這3個程序段的時間復(fù)雜度分別為O(1)、O(n)和O(n2)，分別稱為常量階、線性階和平方階。還可呈現(xiàn)對數(shù)階O(logn)、指數(shù)階O(2的n次方)等。7、連通圖的概念連通圖：在無向圖中，任意兩個頂點之間都有路徑。連通分量：在無向圖中的極大連通子圖。二、填空題〔1*15=15〕1、六個空是第一章，概念1.數(shù)據(jù)：是描述客觀事物的數(shù)值，字符以及能輸入到機器且能被處理的各種符號的總稱的集合。2.數(shù)據(jù)元素：是組成數(shù)據(jù)的根本單位，是數(shù)據(jù)集合的個體，在計算機程序中通常作為一個整體進行考慮和處理。3.數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。4.數(shù)據(jù)結(jié)構(gòu)：是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。5.數(shù)據(jù)類型：是一組性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。6.數(shù)據(jù)的抽象：計算機中使用的是二進制數(shù)，匯編語言中那么可給出各種數(shù)據(jù)的十進制表示，他們是二進制數(shù)據(jù)的抽象。7.抽象數(shù)據(jù)類型〔ADT〕:是基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個類型之上的一組操作。ADT包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的。8.邏輯結(jié)構(gòu)：是數(shù)據(jù)元素之間的邏輯關(guān)系的描述。其4類根本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)9.物理結(jié)構(gòu)〔存儲結(jié)構(gòu)〕：是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示〔又稱映像〕。其4種存儲結(jié)構(gòu)：順序存數(shù)結(jié)構(gòu)、鏈?zhǔn)酱鏀?shù)結(jié)構(gòu)、索引存數(shù)結(jié)構(gòu)、散列存數(shù)結(jié)構(gòu)。9.數(shù)據(jù)結(jié)構(gòu)目的是為了在計算機中實現(xiàn)操作，數(shù)據(jù)結(jié)構(gòu)就是研究一類數(shù)據(jù)的表示以其相關(guān)的運算操作。按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的邏輯映像方式把它存放在計算機的存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合，就叫數(shù)據(jù)結(jié)構(gòu)。6.算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。其5個重要特性：有窮性、確定性、可行性、輸入、輸出2.用數(shù)組模擬鏈表結(jié)構(gòu)數(shù)組模擬鏈表，是一種半靜態(tài)鏈表，是鏈表的線性存儲，比鏈?zhǔn)酱鎯σ唵蔚亩嗔恕Ｃ總€鏈表可以用一對數(shù)組或一個記錄數(shù)組表示，每個元素是有兩個數(shù)據(jù)域：分別是數(shù)據(jù)data域和下一個結(jié)點在數(shù)組中的位置next域〔整型的〕。這樣插入，刪除，遍歷等，都可以歸結(jié)到數(shù)組操作了，這就比鏈?zhǔn)酱鎯θ菀锥嗔耍瑓s不喪失鏈表快速插入刪除的優(yōu)勢。以下所說的指針，都是模擬指針，代表某元素在數(shù)字中的位置。一個鏈表或者多個鏈表使用獨立的存儲空間，一般用數(shù)組或者類似結(jié)構(gòu)實現(xiàn)，優(yōu)點是可以自動獲得一個附加數(shù)據(jù)：唯一的編號，并且方便調(diào)試；缺點是不能動態(tài)的分配內(nèi)存。當(dāng)然，另外的在上面加一層塊狀鏈表用來分配內(nèi)存也是可以的，這樣就解決了這個問題。這種方法有時候被叫做數(shù)組模擬鏈表，但是事實上只是用表示在數(shù)組中的位置的下標(biāo)索引代替了指內(nèi)存地址的指針，這種下標(biāo)索引其實也是邏輯上的指針，整個結(jié)構(gòu)還是鏈表，并不算是被模擬的〔但是可以說成是用數(shù)組實現(xiàn)的鏈表〕現(xiàn)要在編號為K,K+1的兩個結(jié)構(gòu)體數(shù)據(jù)之間插入數(shù)據(jù)"x"，"x"存在空閑的arr[9]里，K=3時即在"d""e"之間插入"x"#include<stdio.h>#defineK3voidmain(){struct{intdata;intnum;}arr[10]={{'a',1},{'b',2},{'c',3},{'d',4},{'e',5},{'f',6},{'g',7},{'h',8},{0,0},{0,0}};intpos=0;arr[K].num=9;arr[9].data='x';arr[9].num=(K+1);while(arr[pos].data!=0){printf("%c,",arr[pos].data);pos=arr[pos].num;}printf("\n");}輸出:a,b,c,d,x,e,f,g,h,3、鏈表必考1.優(yōu)點鏈表的主要優(yōu)勢有兩點：一是插入及刪除操作的時間復(fù)雜度為O(1)；二是可以動態(tài)改變大小。2.缺點由于其鏈?zhǔn)酱鎯Φ奶匦裕湵聿痪邆淞己玫目臻g局部性，也就是說，鏈表是一種緩存不友好的數(shù)據(jù)結(jié)構(gòu)。4、二叉樹，完全二叉樹1.二叉樹：是一種樹型的結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹〔即二叉樹中不存在度大于2的結(jié)點〕，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。2.滿二叉樹：一顆深度為k且有2的k次方減1個結(jié)點的二叉樹。3.完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)。先序：__B__EHI__FG__K中序：D__HEIA__CJG__后序：__H__EBF__KG__A三、應(yīng)用題(6*5=30)1、樹兩個題，有圖與無圖例題1：中序序列BDCEAFHG前序序列ABCDEFGH例題2.〔1〕一個二叉樹如圖1所示：寫出該二叉樹的先序，中序，后序遍歷序列；〔2〕把圖1對應(yīng)的二叉樹轉(zhuǎn)換為所對應(yīng)的森林；〔3〕一棵二叉樹的中序遍歷序列為：dfebagc，先序遍歷序列為：abdefcg，請畫出這棵二叉樹。2、圖兩個圖，沒權(quán)重，無向圖1.圖：多個結(jié)點，結(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都有可能相關(guān)。2.無向完全圖：有n(n-1)/2條邊的無向圖。3.有向完全圖：有n(n-1)條邊的有向圖。4.入度：以頂點V為頭的弧的數(shù)目稱為V的入度。5.出度：以V為尾的弧的數(shù)目稱為V的出度。3、一道雙向鏈表1.設(shè)指針變量p指向雙向鏈表中結(jié)點A，指針變量q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列〔設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink〕。答：操作序列如下：q->rlink=p->rlinkp->rlink=qq->rlink->llink=qq->llink=p注意答案不唯一四、讀程序〔5*3=15〕1、鏈表typedefstructLNode{intdata;StructNode*next;}Node,*Linklist;InitList(Linklist*H){*H=(Linklist)malloc(sizeof(LNode));//建立頭結(jié)點(*H)->next=NULL;//建立空的單鏈表H求長度intListLength(LinklistL){//求帶頭結(jié)點的單鏈表長度Inti;Node*P;P=L->next;j=0;//用來存放單鏈表的長度While(p!=NULL){P=P->next;j++;}Returnj;}2、二叉樹/*下面程序段計算二叉樹的葉子節(jié)點個數(shù)*/intcountleaf(BitreeT){if(T==NULL)//如果節(jié)點為空，那么返回0return0;elseif((T->lchild==NULL)&&(T->rchild==NULL))//否那么如果節(jié)點左右孩子有一個為空，另一個存在，那么返回1return1;elsereturn(countleaf(T->lchild)+countleaf(T->rchild));//否那么返回左右子樹葉子節(jié)點之和}3、c語言相關(guān)的，時間復(fù)雜度voidBubbleSort(inta[],intp)//冒泡排序算法{inti,j,temp;for(i=0;i<N-1;i++){for(j=N-1;j>i;j--)//比擬,找出本趟最小關(guān)鍵字的記錄if(a[j]<a[j-1]){temp=a[j];//進行交換,將最小關(guān)鍵字記錄前移a[j]=a[j-1];a[j-1]=temp;}}五、編程題〔10*2=20〕1、單鏈表Linklistchange(Linklisthead)//逆置算法{Linklistp,q;p=head->next;//P指向鏈表第一個元素head->next=NULL;//斷開頭結(jié)點與鏈表while(p!=NULL){q=p;p=p->next;q->next=head->next;//相當(dāng)于頭插法構(gòu)建新的鏈表head->next=q;//每下一個結(jié)點始終在第一個位置}returnhead;}2、二叉樹voidPreOrderTraverse(BiTreeBT){if(BT