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