1、A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改3. 以下數據結構中 (是非線性結構。A.隊列B.棧 C.線性表D. 二叉樹4.設有一個二維數組676(10)，每個元素占進制表示。Amn ，假設A00 存放位置在 個空間，問A33(10)存放在(644(10)，A22 存放位置在)位置。腳注(10)表示用 10688 678 C6926965. 樹最適合用來表示 ()。6.7.8.A. 有序數據元素B.無序數據元素C. 元素之間具有分支層次關系的數據二叉樹的第 k 層的結點數最多為 ( ) 。k 2k-1+1D.k-1D. 2k-1若有 18 個元素的有序表存放

2、在一維數組 A19分查找，則查找 A: 3 的比較序列的下標依次為A. 1 ， 2， 3C. 9 ， 5， 3元素之間無聯系的數據中，第一個元素放 A1 中， 現進行二 ( ) 。B. 9 ，5，2， 3D. 9 ，4， 2，3對于線性表( 7， 34， 55， 25， 64， 46， 20， 10)進行散列存儲時，若選用 H(K) =K %9作為散列函數，則散列地址為 1 的元素有( )個。 1 B234數據結構練習題(一)、單選題A.只允許在端點處插入和刪除元素B. 都是先進后出C. 都是先進先出D.沒有共同點用鏈接方式存儲的隊列，在進行插入運算時 ( )。1.棧和隊列的共同特點是 ()。

3、2.9.設有 6 個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。、填空題1.通常從四個方面評價算法的質量： _ 、_、_和_。3 2 22.一個算法的時間復雜度為(n+nlog2n+14n)/n，其數量級表示為 _。3.假定一棵樹的廣義表表示為A(C, D(E，F, G，H( I，J),則樹中所含的結點數為_個，樹的深度為_，樹的度為_ 。4.若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結構中，n 個結點的二叉樹共有 _個指針域，其中有 _ 個指針域是存放了地址，有_個指針是空指針。5.對于一個具有 n 個頂點和 e 條邊的有向圖和無向

4、圖，在其對應的鄰接表中，所含邊結點分別有_ 個和_ 個。6.AOV 網是一種_的圖。7.在一個具有 n 個頂點的無向完全圖中，包含有_條邊，在一個具有 n 個頂點的有向完全圖中，包含有 _條邊。8.假定一個線性表為(12,23,74,55,63,40)，若按 Key%4 條件進行劃分，使得同一余數的元素成為一個子表，則得到的四個子表分別為_、_ 、_ 和_ 。9.在快速排序、堆排序、歸并排序中， _排序是穩定的。三、計算題1.在如下數組 A 中鏈接存儲了一個線性表，表頭指針為A 0.next ，試寫出該線性表。6050789034403572041datan ext9.設有 6 個結點的無向圖

5、，該圖至少應有()條邊才能確保是一個連通圖。2.請畫出下圖的鄰接矩陣和鄰接表。3.已知一個圖的頂點集V 和邊集 E 分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25;用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4.畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。四、閱讀算法1. LinkList mynote(LinkList L)圖中有 n 個頂點，則該強連通圖中至

6、少有(D) n(n+1)序的記錄關鍵字，如果需要用最快的方法10 個記錄關鍵字，則用下列()方法可(A)快速排序(B)堆排序(C)歸并排序(D)插入排序二、填空題1.數據的物理結構主要包括和兩種情況。2.設一棵完全二叉樹中有 500 個結點，則該二叉樹的深度為 _；若用二叉鏈表作為該完全二叉樹的存儲結構，則共有 _個空指針域。3.設輸入序列為 1、2、3，則經過棧的作用后可以得到 _種不同的輸出序列。4.設有向圖 G 用鄰接矩陣 Ann作為存儲結構，則該鄰接矩陣中第 i 行上所有元素之和等于頂點 i 的_，第 i 列上所有元素之和等于頂點i 的_。5.設哈夫曼樹中共有 n 個結點，則該哈夫曼樹

7、中有 _ 個度數為 1 的結點。6.設有向圖 G 中有 n 個頂點 e 條有向邊，所有的頂點入度數之和為d,則 e 和 d 的關系為設某強連通()條邊。(A) n(n-1)&設有 5000 個待排選出其中最小的 以達到此目的。7._遍歷二叉排序樹中的結點可以得到一個遞增的關鍵字序列(填先序、中序或后序)。8.設查找表中有 100 個元素，如果用二分法查找方法查找數據元素X,則最多需要比較_次就可以斷定數據元素 X 是否在查找表中。9.不論是順序存儲結構的棧還是鏈式存儲結構的棧, 其入棧和出棧操作的時間復雜度均為。10.設有 n 個結點的完全二叉樹, 如果按照從自上到下、 從左到右從 1 開始順

8、序編號, 則第i 個結點的雙親結點編號為 _,右孩子結點的編號為 _。11.設一組初始記錄關鍵字為 (72 , 73, 71, 23, 94, 16, 5) ,則以記錄關鍵字 72 為基準的一趟快速排序結果為 _。12.設有向圖 G 中有向邊的集合 E=1，2，2，3，1, 4，4，2，4，3，則該圖的一種拓撲序列為 _ 。13.下列算法實現在順序散列表 (哈希表) 中查找值為 x 的關鍵字， 請在下劃線處填上正確 的語句。struct recordint key; int others;int hashsqsearch(struct record hashtable ,int k)int i

9、,j; j=i=k % p;while (hashtablej.key!=k&hashtablej.flag!=0)j=(_ ) %m; if (i=j)return(-1);if (_ ) return(j); else return(-1);14.下列算法實現在二叉排序樹上查找關鍵值k，請在下劃線處填上正確的語句。typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k)if (t=0 ) return(0);else whil

10、e (t!=0)if (t-key=k)_ ; else if (t-keyk) t=t-lchild;else_ ;二、計算題1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ 中序遍歷序列是 EFAGBCHKIJ,畫出此二叉樹。2.已知待散列的線性表為(36, 15, 40, 63, 22),散列用的一維地址空間為0 . 6，假定 選用的散列函數是 H( K) = K mod 7，若發生沖突采用線性探查法處理，試：(1 )計算出每一個元素的散列地址并在下圖中填寫出散列表：0123456(2)求出在查找每一個元素概率相等情況下的平均查找長度。3.已知序列(10, 18, 4, 3, 6,

11、 12, 1, 9, 18, 8)請用快速排序寫出每一趟排序的結果。四、算法設計題1.設計在單鏈表中刪除值相同的多余結點的算法。2.設計一個求結點 x 在二叉樹中的雙親結點算法。數據結構練習題(四)一、選擇題1設一維數組中有 n 個數組元素，則讀取第 i 個數組元素的平均時間復雜度為( )。2(A) O(n) (B) O(nlog2n)(C) O(1) (D) O(n2)2 設一棵二叉樹的深度為k，則該二叉樹中最多有()個結點。kk-1k(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13設某無向圖中有 n 個頂點 e 條邊，則該無向圖中所有頂點的入度之和為()。(A) n(B) e

12、(C) 2n(D) 2e4. 在二叉排序樹中插入一個結點的時間復雜度為()。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5.設某有向圖的鄰接表中有n 個表頭結點和 m個表結點，則該圖中有()條有向邊。(A) n(B) n-1(C) m(D) m-16.設一組初始記錄關鍵字序列為(345 ,253, 674, 924, 627),則用基數排序需要進行()趟的分配和回收才能使得初始關鍵字序列變成有序序列。(A) 3(B) 4(C) 5(D) 87.設用鏈表作為棧的存儲結構則退棧操作()。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D)

13、 對棧不作任何判別8.下列四種排序中()的空間復雜度最大。(A) 快速排序 (B) 冒泡排序 (C) 希爾排序 (D) 堆9.設某二叉樹中度數為0 的結點數為 N0,度數為 1 的結點數為 N ,度數為 2 的結點數為 N2, 則下列等式成立的是( )。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l10. 設有序順序表中有 n 個數據元素，則利用二分查找法查找數據元素X 的最多比較次數不超過( )。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)、填空題1 設有 n 個無序的記錄關鍵字， 則直接插入排序的時間

14、復雜度為 _，快速排序的平均時間復雜度為 _ 。2 根據初始關鍵字序列 （19 ，22，01，38，10）建立的二叉排序樹的高度為 _。3 深度為 k 的完全二叉樹中最少有 _ 個結點。4.設初始記錄關鍵字序列為（Ki, K2,，K），則用篩選法思想建堆必須從第 _個元素開始進行篩選。5.設哈夫曼樹中共有 99 個結點， 則該樹中有 _ 個葉子結點； 若采用二叉鏈表作為存儲結構，則該樹中有 _ 個空指針域。6.設有一個順序循環隊列中有M 個存儲單元，則該循環隊列中最多能夠存儲 _ 個隊列元素； 當前實際存儲 _ 個隊列元素 （設頭指針 F 指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的

15、位置） 。7.設順序線性表中有 n 個數據元素，則第 i 個位置上插入一個數據元素需要移動表中_ 個數據元素；刪除第 i 個位置上的數據元素需要移動表中 _個元素。8.設一組初始記錄關鍵字序列為 （20， 18， 22， 16， 30， 19），則以 20 為中軸的一趟快速排序結果為 _ 。9.設一組初始記錄關鍵字序列為 （20， 18， 22， 16， 30， 19），則根據這些初始關鍵字序列建成的初始堆為 _ 。10設某無向圖 G 中有 n 個頂點，用鄰接矩陣A 作為該圖的存儲結構，則頂點i 和頂點 j互為鄰接點的條件是 _ 。11 設無向圖對應的鄰接矩陣為A,則 A 中第 i 行上非 0

16、 元素的個數 _ 第 i 列上非 0元素的個數（填等于，大于或小于） 。12 設前序遍歷某二叉樹的序列為ABCD 中序遍歷該二叉樹的序列為BADC 則后序遍歷該二叉樹的序列為 _。13.設散列函數H（k）=k mod p，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe 中查找關鍵字值等于k 的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。typedef struct node int key; struct node *next; lklist;void createlkhash（lklist *hashtable ）int i,k; Ikl

17、ist *s;for(i=0;im;i+)_ ;for(i=0;ikey=ai;k=ai % p; s-next=hashtablek;_三、計算題1、下圖所示的森林：(1) 求樹(a)的先根序列和后根序列；(2) 求森林先序序列和中序序列；(3) 將此森林轉換為相應的二叉樹；2、設散列表的地址范圍是0.9 ，散列函數為 H( key)= ( key2+2)MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9 依次插入散列表的存儲結構。四、算法設計題1.設單鏈表中有僅三類字符的數據元素(大寫字母、數字和其它字符)，要求利用原單鏈表 中結點空間設計出三個單鏈表的算法，使每個單

18、鏈表只包含同類字符。2.設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。3.在鏈式存儲結構上建立一棵二叉排序樹。數據結構練習題(五)一、選擇題1數據的最小單位是()。(A) 數據項 (B) 數據類型 (C) 數據元素 (D) 數據變量2設一組初始記錄關鍵字序列為 (50，40，95，20，15，70，60，45)，則以增量 d=4 的一 趟希爾排序結束后前 4 條記錄關鍵字為()。(A) 40 ， 50， 20， 95(B) 15 ， 40， 60， 20(C) 15 ， 20， 40， 45(D) 45 ， 40， 15， 203設一組初始記錄關鍵字序列為 (25 ，50，15，35

19、，80，85，20，40，36，70) ，其中含有5 個長度為 2 的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的 結果為( )。(A) 15 ,25,35,50, 20, 40, 80, 85,36, 70(B) 15 ,25, 35,50,80,20,85, 40,70, 36(C)15 ,25, 35,50,80, 85,20, 36,40,70(D)15 ,25, 35, 50,80, 20, 36, 40, 70, 854設一個有序的單鏈表中有n 個結點， 現要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為( )。2(A) O(log2n)(B)

20、O(1) (C) O(n2)(D) O(n)5設有序表中有 1000 個元素，則用二分查找查找元素 X 最多需要比較( )次。(A) 25 (B) 10 (C) 7 (D) 16 設連通圖 G 中的邊集 E=(a , b) , (a , e) , (a , c) , (b , e) , (e , d) , (d , f) , (f , c), 則從頂點 a 出發可以得到一種深度優先遍歷的頂點序列為()。(A) abedfc(B) acfebd(C) aebdfc(D) aedfcb7設輸入序列是 1、2、3、n,經過棧的作用后輸出序列的第一個元素是n,則輸出序列中第 i 個輸出元素是( )。(

21、A) n-i(B) n-1-i(C) n+1-i(D) 不能確定8設一組初始記錄關鍵字序列為(45 ，80，55，40，42，85) ，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是( )。(A) 40 ，42，45，55，80，83(B) 42 ，40，45，80，85，88(C) 42 ，40，45，55，80，85(D) 42 ，40，45，85，55，80二、填空題1.在圖的鄰接表中用順序存儲結構存儲表頭結點的優點是 _ 。2.設有一個 n 階的下三角矩陣 A,如果按照行的順序將下三角矩陣中的元素(包括對角線上元素)存放在 n(n+1) 個連續的存儲單元中，則 Aij 與 A

22、00 之間有 _ 個數據元素。3.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為_表；隊列的插入和刪除運算分別在隊列的兩端進行， 先進隊列的元素必定先 出隊列，所以又把隊列稱為 _ 表。4.設一棵完全二叉樹的順序存儲結構中存儲數據元素為ABCDE，F 則該二叉樹的前序遍歷序列為 _ ，中序遍歷序列為 _，后序遍歷序列為 _ 。5.設一棵完全二叉樹有 128 個結點，則該完全二叉樹的深度為 _，有_個葉子結點。6.設有向圖 G 的存儲結構用鄰接矩陣 A 來表示，則 A 中第 i 行中所有非零元素個數之和等于頂點 i 的_ ，第 i 列中所有非零元素個數之和等于頂點 i

23、的_ 。7.下面程序段的功能是實現冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_ ;rj=temp;exchange=1;if (exchange=0) return ；8.下面程序段的功能是實現二分查找算法，請在下劃線處填上正確的語句。struct recordi nt key; int others; int bisearch(struct record r , i nt k) int low=0,mid,high=n-1;while(lowlef

24、t BST-right六、編寫算法int CountX(LNode* HL,ElemType x)1. int i=0; LNode* p=HL;ey=k2.return(t) ， t=t-rchild三、計算題H(15)=15 mod 7=1;.沖突H2(22)=(2+1) mod 7=3;Hi (15)=(1+1) mod 7=2;H(40)=40 mod 7=5;H(63)=63 mod 7=0;H(22)=22 mod 7=1;.沖突(1)01234566336152240(2)ASL=121131.653、(8,9,4,3,6,1),10,(12,18,18)_(1,6,4,3),8

25、,(9),10,12,(18,18)1, (3,4,6),8,9,10,12,18,(18) _1.3, (4,6),8,9,10,12,18,18 _1.3, 4,6,8,9,10,12,18,18 _四、算法設計題1.設計在單鏈表中刪除值相同的多余結點的算法。typedef int datatype;typedef struct node datatype data; struct node *n ext;lklist;void delredundant(lklist *&head)i(22)=(1+1) mod 7=2;2、H(36)=36 mod 7=1;H.沖突lklist *p,*

26、q,*s;for(p=head;p!=0;p=p-next)for(q=p-next,s=q;q!=0; )if (q-data=p-data) s-next=q-next; free(q);q=s-next;else s=q,q=q-next;2.設計一個求結點 x 在二叉樹中的雙親結點算法。typedef struct node datatype data; struct node *lchild,*rchild; bitree;bitree *q20; int r=0,f=0,flag=0;void preorder(bitree *bt, char x)if (bt!=0 & flag

27、=0)if (bt-data=x) flag=1; return;else r=(r+1)% 20; qr=bt; preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x)int i;preorder(bt,x);for(i=f+1; ilchild-data=x | qi-rchild-data) break;if (flag=0) printf(not found xn);else if (idata); else printf(not parent);數據結構練習題（四）參考答案一、選擇題1C

28、2D3 D4B5C6A7B8 A9C10A二、填空題10. Aij=111. 等于12. BDCA13. hashtablei=O , hashtablek=s三、計算題1.(1) ABCDEF; BDEFCA ; (2) ABCDEFGHIJK; BDEFCAIJKHG 林轉換為相應的二叉樹;2.H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法設計題1.設單鏈表中有僅三類字符的數據元素（大寫字母、數字和其它字符），要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedef char datatype;ty

29、pedef struct node datatype data; struct node *n ext;lklist;void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)lklist *p; ha=0,hb=0,hc=0;for(p=head;p!=0;p=head)head=p-next; p-next=0;if (p-data=A & p-datanext=ha; ha=p;else if (p-data=0 &p-datanext=hb; hb=p; else p-next=hc; hc=p;2.設計在鏈式存儲結構上交換

30、二叉樹中所有結點左右子樹的算法。typedef struct node int data; struct node *lchild,*rchild; bitree;void swapbitree(bitree *bt)bitree *p;if(bt=0) return;swapbitree(bt-lchild); swapbitree(bt-rchild);0 678945123p=bt-lchild; bt-lchild=bt-rchild; bt-rchild=p;3.在鏈式存儲結構上建立一棵二叉排序樹。#define n 10typedef struct nodeint key; struct node *lchild,*rchild;bitree;void bstinsert(bitree *&bt,int key)if (bt=0)b