下載地址：https://wwm.lanzouw.com/ixFNoy9hdyh
密碼:5vyi

文章目錄

資料結構複習題

資料結構複習題

填空

在資料結構中, 從邏輯上能夠把資料結構分為
- 線性結構
- 非線性結構
資料結構在計算機記憶體中的表示是指
- 資料的儲存結構
鏈式儲存的特點是利用**指標** 來表示資料元之間的邏輯關係。
對於給定的n個元素，可以構造出的邏輯結構有
- 集合
- 樹形結構
- 線性結構
- 圖結構
順序儲存結構是通過==結點物理上相鄰==表示元素之間的關係的；
- 鏈式儲存結構是通過**結點指標**表示元素之間的關係的。
迴圈單連結串列的最大優點是：
- 從任一結點出發都可存取到連結串列中每一個元素。
堆疊是一種操作受限的線性表，

它只能線上性表的==一端==進行插入和刪除操作，
對棧的存取是按照==後進先出==的原則進行的。

棧是==操作受限==的線性表，

其運算遵循的原則：後進先出。
棧可以線上性表的==棧頂==進行操作和刪除。
迴圈佇列的引入，
- 目的：克服假溢位時大量的行動資料元素。
對於一個具有n個結點的二元樹，
- 當它為一棵==完全==二元樹時具有最小高度。
哈夫曼樹
- 是==帶權路徑長度最小的二元樹==，又稱**最優二元樹**。
完全圖
- 是**任意兩個頂點之間存在邊**；

連通圖
- 是任意兩個頂點之間都有路徑。

一般線性表順序查詢，
- 查詢成功的平均查詢長度為==（n+1）/2==，
- 查詢失敗的平均查詢長度為n+1。

15.採用分塊查詢時，

陣列的組織方式：資料分成若干塊，
每塊內資料不必有序，但**塊間必須有序，每塊內最大的資料**組成索引塊。

在線性表的順序儲存中
- 元素之間的邏輯關係是通過： 物理位置相鄰 決定的
在線性表的連結儲存中，
- 元素之間的邏輯關係是通過：**指標**決定的。
空格串
- 長度為：空格數，
- 空串的長度為 0 。
己知三對角矩陣A[1…9,1…9]的每個元素佔2個單元，現將其三條對角線上的元素逐行儲存在起始地址為1000的連續的記憶體單元中，則元素A[7,8]的地址為：
- 1038
設廣義表L = ((),())
- head(L)：()；
- tail(L)：( ( ) )；
- L的長度：2；
- 深度：2。
一棵深度為k的二元樹，
- 最多有2k-1個結點。
圖，的儲存結構常採用____兩種
- 鄰接矩陣
- 鄰接表。

22.指標q值為null，指標p指向單連結串列L的某個結點

刪除其後繼節點（要求由指標q指向）的語句是：
- q=p->next，
- p->next=q->next，
- free(q)

選擇

n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有（C）個。
- A.n B.2e C.e D.n+e
如果在資料結構中每個資料元素只可能有一個直接前驅，但可以有多個直接後繼，則該結構是（C）
- A. 棧 B. 佇列 C. 樹 D. 圖
資料結構研究的內容是（D）。
- A．資料的邏輯結構 B．資料的儲存結構
- C．建立在相應邏輯結構和儲存結構上的演演算法 D．包括以上三個方面
若下面幾個符號串編碼集合中，不是字首編碼的是（B）。
- A．{0,10,110,1111} B．{11,10,001,101,0001}
- C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc}
一棵二元樹，前序遍歷序列為：ABCDEFG，它的中序遍歷序列可能是（B）
- A．CABDEFG B：ABCDEFG C．DACEFBG D．ADCFEG
設有陣列A[i,j]，陣列的每個元素長度為3位元組，i的值為1 到8 ，j的值為1 到10，陣列從記憶體首地址BA開始順序存放，

當用以列為主記憶體放時，元素 A[5，8]的儲存首地址為：(B)：
- A. BA+141 B. BA+180 C. BA+222 D. BA+225
下面的說法中，只有（A）是正確的
- A.串是一種特殊的線性表 B. 串的長度必須大於零
- C.串中元素只能是字母 D. 空串就是空白串
設有一個棧，元素的進棧次序為A, B, C, D, E,下列是不可能的出棧序列（C）
- A．A, B, C, D, E B．B, C, D, E, A
- C．E, A, B, C, D D．E, D, C, B, A
在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指標，當做出棧處理時，top變化為（C）
- A．top不變 B．top=0 C．top– D．top++
在一個單連結串列中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執行（B）
- A．s->next=p->next; p->next=s
- B．q->next=s; s->next=p
- C．p->next=s->next; s->next=p
- D．p->next=s; s->next=q
設一維陣列中有n個陣列元素，則讀取第i個陣列元素的平均時間複雜度為（ C）。

(A)O(n) (B) O(nlog2n) © O(1) (D)O(n2)

設，一棵二元樹的深度為k，則該二元樹中最多有（D）個結點。

(A)2k-1 (B) 2k © 2k-1 (D)2k-1

設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（D）。

(A)n (B) e © 2n (D) 2e

在二叉排序樹中插入一個結點的時間複雜度為（B）。

(A)O(1) (B) O(n) © O(log2n) (D) O(n2)

設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（C ）條有向邊。

(A)n (B) n-1 ©m (D)m-1

判斷

無向連通圖，所有頂點的度之和為偶數。 [√]
無向連通圖邊數一定大於頂點個數減1。 [×]
無向連通圖至少有一個頂點的度為1。 [×]
用鄰接表法儲存圖，佔用的儲存空間數只與圖中結點個數有關，而與邊數無關。 [×]
用鄰接矩陣法儲存圖，佔用的儲存空間數只與圖中結點個數有關，而與邊數無關。 [√]
在一個有向圖中，所有頂點的入度與出度之和等於所有邊之和的2倍。 [√]
演演算法分析的兩個主要方面是時間複雜度和空間複雜度的分析。 [√]
通過對堆棧S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。輸出的序列為：123。 [×]
在用陣列表示的迴圈佇列中，front值一定小於等於rear值。 [×]
若一個棧的輸入序列為{1, 2, 3, 4, 5}，則不可能得到{3, 4, 1, 2, 5}這樣的出棧序列。 [√]
已知一棵二元樹的先序遍歷結果是ABC,　則CAB不可能是中序遍歷結果。 [√]
一棵有124個結點的完全二元樹，其葉結點個數是確定的。 [√]
若用連結串列來表示一個線性表，則表中元素的地址一定是連續的。 [×]
任何二元搜尋樹中同一層的結點從左到右是有序的（從小到大）。 [√]
某二元樹的前序和中序遍歷序列正好一樣，則該二元樹中的任何結點一定都無左孩子。 [√]

簡答

儲存結構

有一字元序列abcde依次按照某一線性結構儲存，請回答以下問題：

如果該線性結構是佇列，寫出其出隊順序；
- ABCDE
- 佇列：先進先出
如果該線性結構是棧，那麼，輸出序列可能是dceab麼？為什麼？
- 不可能
- 因為：
  - d是第一個出棧字元，說明ab已分別壓入棧內；並且壓入棧的順序為abcde；
  - 由以上得出：ab出棧的順序只能是b、a，而不是ab，所以出棧序列dceab是不肯能的
如果該線性結構是棧，且輸出序列是adcbe，寫出其操作過程

push(x)：表示把x壓入棧內；

pop(x)：表示把x彈出棧

棧：先進後出，後進先出。

push(a),pop(a),push(b),push(c),push(d),pop(d),pop(c),pop(b),push(e).pop(e)

森林

下圖所示的森林：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片儲存下來直接上傳(img-4MewFbXh-1641106984599)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/clip_image001.jpg)]

求樹（a）的先根序列和後根序列；
- ABCDEF
- BDEFCA
求森林先序序列和中序序列
- ABCDEFGHIJK
- BDEFCAIJKHG
將此森林轉換為相應的二元樹；

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片儲存下來直接上傳(img-yBKbf253-1641106984599)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/clip_image003.jpg)]

阿克曼（Ackerman）函數

在數學上有一個著名的「阿克曼（Ackerman）函數」，該函數定義如下：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片儲存下來直接上傳(img-QL8psIUw-1641106984600)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/image-20220102140023331.png)]

寫出Ack(m,n)的遞迴演演算法；

java

public class Ackerman {

    public static void main(String[] args) {
        System.out.println(" " + ack(3,4) + "");
    }

    public static int ack(int m,int n){
      if (m < 0 || n < 0){
        return -1;
      }else if ( m == 0){
            return n+1;
        }else if (n == 0 && m != 0){
            return ack(m-1,1);
        }else if(n != 0 && m != 0){
            return ack(m-1,ack(m,n-1));
        }
    }
}

int Ack(int m, int n)

{

if(m==0)

  return n+1;

else if (m!=0 && n==0)

 return Ack(m-1, 1);

else

  return Ack(m-1,Ack(m,m-1));

}

//Ackerman遞迴演演算法
int akm1(int m,int n){
	int q;
	if(m==0)
		return n+1;
	else if(n==0)
		return akm1(m-1,1);
	else{
		q=akm1(m,n-1);
		return akm1(m-1,q);
	}
}

寫出計算Ack(m,n)的非遞迴演演算法。

//Ackerman非遞迴演演算法
int akm2(int m,int n){
	struct{
		int vm,vn;  //分別儲存m和n值
		int vf;     //儲存akm(m,n)值
		int tag;  //標識是否求出akm(m,n)值，1:表示未求出，0:表示已求出
	}St[MaxSize];

	int top=-1;  //棧指標
	top++;     //初值進棧
	St[top].vm=m; St[top].vn=n; St[top].tag=1;
	while(top > -1){   //棧不空時迴圈
		if (St[top].tag==1)   //未計算出棧頂元素的vf值
		{ 
			if (St[top].vm==0)      //(1)式
			{
				St[top].vf=St[top].vn+1;
				St[top].tag=0;
			} 
			else if (St[top].vn==0) //(2)式
			{
				top++;
				St[top].vm=St[top-1].vm-1;
				St[top].vn=1;
				St[top].tag=1;
			}
			else                    //(3)式
			{
				top++;
				St[top].vm=St[top-1].vm;
				St[top].vn=St[top-1].vn-1;
				St[top].tag=1;
			}
		}
		else if (St[top].tag==0)  //已計算出vf值
		{
			if (top>0 && St[top-1].vn==0) //(2)式
			{
				St[top-1].vf=St[top].vf;
				St[top-1].tag=0;
				top--;
			}
			else if (top > 0) //(3)式
			{
				St[top-1].vm=St[top-1].vm-1;
				St[top-1].vn=St[top].vf;
				St[top-1].tag=1;
				top--;
			}
		}
		if(top==0 && St[top].tag==0) //棧中只有一個已求出vf的元素時退出迴圈
			break;
	}
	return St[top].vf;

}

排序

4.有一組資料{64，5，7，98，6，24}

（1）請列出直接選擇排序（升序）的過程；

（2）請列出氣泡排序（升序）的過程

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片儲存下來直接上傳(img-ZV9AntAU-1641106984600)(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E5%A4%8D%E4%B9%A0%E9%A2%98.assets/clip_image006.jpg)]

直接選擇排序：

找最小的數，放到第一位~

參考

初始值 {64，5，7，98，6，24}

5，【64，7，98，6，24】

5，6，【7，98，64，24】

5，6，7，【98，64，24】

5，6，7，24【64，98】

5，6，7，24，64，【98】

氣泡排序：

兩個相鄰數直接比較，

參考

初識值：{64，5，7，98，6，24}

第一趟排序：5

【5，64】，7，98，6，24

5，【7，64】，98，6，24

5，7，[64，98]，6，24

5，7，64，【6，98】，24

5，7，64，6，【24，98】

第二趟排序：4

【 5，7】，64，6，24，98

5，【7，64】，6，24，98

5，7，【6，64】，24，98

5，7，6，【24，64】，98

第三趟排序：3

【5，7】，6，24，64，98

5，【6，7】，24，64，98

5，6，【7，24】，64，98

資料結構複習題

文章目錄

資料結構 複習題

填空

選擇

判斷

簡答

儲存結構

森林

阿克曼（Ackerman）函數

排序

直接選擇排序：

氣泡排序：

資料結構複習題