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

資料結構 復習題

填空

1. 在資料結構中,?從邏輯上能夠把資料結構分為

   • 線性結構

   • 非線性結構

2. 資料結構在計算機記憶體中的表示是指

   • 資料的存盤結構

3. 鏈式存盤的特點是利用**指標** 來表示資料元之間的邏輯關系，

4. 對于給定的n個元素，可以構造出的邏輯結構有

   • 集合

   • 樹形結構

   • 線性結構

   • 圖結構

5. 順序存盤結構是通過==結點物理上相鄰==表示元素之間的關系的；

   • 鏈式存盤結構是通過**結點指標**表示元素之間的關系的，

6. 回圈單鏈表的最大優點是：

   • 從任一結點出發都可訪問到鏈表中每一個元素，

7. 堆疊是一種操作受限的線性表，

• 它只能在線性表的==一端==進行插入和洗掉操作，

• 對堆疊的訪問是按照==后進先出==的原則進行的，

8. 堆疊是==操作受限==的線性表，

   其運算遵循的原則：后進先出，

9. 堆疊可以在線性表的==堆疊頂==進行操作和洗掉，

10. 回圈佇列的引入，

    • 目的：克服假溢位時大量的移動資料元素，

11. 對于一個具有n個結點的二叉樹，

    • 當它為一棵==完全==二叉樹時具有最小高度，

12. 哈夫曼樹

    • 是==帶權路徑長度最小的二叉樹==，又稱**最優二叉樹**，

13. 完全圖

    • 是**任意兩個頂點之間存在邊**；

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

14. 一般線性表順序查找，

    • 查找成功的平均查找長度為==（n+1）/2==，

    • 查找失敗的平均查找長度為n+1，

15.采用分塊查找時，

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

16. 在線性表的順序存盤中

    • 元素之間的邏輯關系是通過： 物理位置相鄰 決定的

    在線性表的鏈接存盤中，

    • 元素之間的邏輯關系是通過：**指標**決定的，

17. 空格串

    • 長度為： 空格數，
    • 空串的長度為 0 ，

18. 己知三對角矩陣A[1…9,1…9]的每個元素占2個單元，現將其三條對角線上的元素逐行存盤在起始地址為1000的連續的記憶體單元中，則元素A[7,8]的地址為：

    • 1038

19. 設廣義表L = ((),())

    • head(L)：()；
    • tail(L)：( ( ) )；
    • L的長度：2；
    • 深度：2，

20. 一棵深度為k的二叉樹，

    • 最多有2k-1個結點，

21. 圖，的存盤結構常采用____兩種

    • 鄰接矩陣
    • 鄰接表，

22.指標q值為null，指標p指向單鏈表L的某個結點

• 洗掉其后繼節點（要求由指標q指向）的陳述句是 ：

  • q=p->next，

  • p->next=q->next，

  • free(q)

選擇

1. n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有 （C）個，

   • A.n B.2e C.e D.n+e

2. 如果在資料結構中每個資料元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是（C）

   • A. 堆疊 B. 佇列 C. 樹 D. 圖

3. 資料結構研究的內容是（D），

   • A．資料的邏輯結構 B．資料的存盤結構

   • C．建立在相應邏輯結構和存盤結構上的演算法 D．包括以上三個方面

4. 若下面幾個符號串編碼集合中，不是前綴編碼的是（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}

5. 一棵二叉樹，前序遍歷序列為：ABCDEFG，它的中序遍歷序列可能是（B）

   • A．CABDEFG B：ABCDEFG C．DACEFBG D．ADCFEG

6. 設有陣列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

7. 下面的說法中，只有（A）是正確的

   • A.串是一種特殊的線性表 B. 串的長度必須大于零

   • C.串中元素只能是字母 D. 空串就是空白串

8. 設有一個堆疊，元素的進堆疊次序為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

9. 在一個具有n個單元的順序堆疊中，假定以地址低端（即0單元）作為堆疊底，以top作為堆疊頂指標，當做出堆疊處理時，top變化為（C）

   • A．top不變 B．top=0 C．top– D．top++

10. 在一個單鏈表中，已知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

11. 設一維陣列中有n個陣列元素，則讀取第i個陣列元素的平均時間復雜度為（ C），

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

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

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

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

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

14. 在二叉排序樹中插入一個結點的時間復雜度為（B），

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

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

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

判斷

1. 無向連通圖，所有頂點的度之和為偶數， [√]

2. 無向連通圖邊數一定大于頂點個數減1， [×]

3. 無向連通圖至少有一個頂點的度為1， [×]

4. 用鄰接表法存盤圖，占用的存盤空間數只與圖中結點個數有關，而與邊數無關， [×]

5. 用鄰接矩陣法存盤圖，占用的存盤空間數只與圖中結點個數有關，而與邊數無關， [√]

6. 在一個有向圖中，所有頂點的入度與出度之和等于所有邊之和的2倍， [√]

7. 演算法分析的兩個主要方面是時間復雜度和空間復雜度的分析， [√]

8. 通過對堆堆疊S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)，輸出的序列為：123， [×]

9. 在用陣列表示的回圈佇列中，front值一定小于等于rear值， [×]

10. 若一個堆疊的輸入序列為{1, 2, 3, 4, 5}，則不可能得到{3, 4, 1, 2, 5}這樣的出堆疊序列， [√]

11. 已知一棵二叉樹的先序遍歷結果是ABC,　則CAB不可能是中序遍歷結果， [√]

12. 一棵有124個結點的完全二叉樹，其葉結點個數是確定的， [√]

13. 若用鏈表來表示一個線性表，則表中元素的地址一定是連續的， [×]

14. 任何二叉搜索樹中同一層的結點從左到右是有序的（從小到大）， [√]

15. 某二叉樹的前序和中序遍歷序列正好一樣，則該二叉樹中的任何結點一定都無左孩子， [√]

簡答

存盤結構

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

1. 如果該線性結構是佇列，寫出其出隊順序；

   • ABCDE

   • 佇列：先進先出

2. 如果該線性結構是堆疊，那么，輸出序列可能是dceab么？為什么？

   • 不可能
   • 因為：
     • d是第一個出堆疊字符，說明ab已分別壓入堆疊內；并且壓入堆疊的順序為abcde；
     • 由以上得出：ab出堆疊的順序只能是b、a，而不是ab，所以出堆疊序列dceab是不肯能的

3. 如果該線性結構是堆疊，且輸出序列是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)

森林

下圖所示的森林：

1. 求樹（a）的先根序列和后根序列；

   • ABCDEF
   • BDEFCA

2. 求森林先序序列和中序序列

   • ABCDEFGHIJK
   • BDEFCAIJKHG

3. 將此森林轉換為相應的二叉樹；

阿克曼（Ackerman）函式

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

1. 寫出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));
        }
    }
}

c

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);
	}
}

2. 寫出計算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）請列出冒泡排序（升序）的程序

直接選擇排序：

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

參考

初始值 {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