華南理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程習(xí)題集部分答案

1、數(shù)據(jù)結(jié)構(gòu)課程習(xí)題集 第 1 頁 （共 25 頁） 一、 . 選擇題 . 1. 算法的計算量的大小稱為計算的（ B ）。 A效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度 .2. 算法的時間復(fù)雜度取決于（ C ）. A問題的規(guī)模B. 待處理數(shù)據(jù)的初態(tài) C. A 和 B D. 難確定 .3. 下面關(guān)于算法說法錯誤的是（ D ） A算法最終必須由計算機程序?qū)崿F(xiàn) B. 為解決某問題的算法同為該問題編寫的程序含義是相同的 C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的 .4 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。 A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B 順序結(jié)構(gòu)、鏈式結(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu)D

2、 初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) .5 以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ D ）？ A廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串 .6 下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（ A ） A存儲密度大 B 插入運算方便 C刪除運算方便 D 可方便地用于各種邏輯結(jié)構(gòu)的存儲表示 .7 下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ B ） A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 B線性表采用順序存儲，便于進行插入和刪除操作。 C線性表采用存儲，不必占用一片連續(xù)的存儲單元。 D線性表采用存儲，便于插入和刪除操作。 .8 若某線性表最常用的操作是存取任 一指定序號的元素和在最后進行插入和刪 除運算，則利用

3、（ A ）存儲方式最節(jié)省時間。 A順序表 B 雙鏈表 C 帶頭結(jié)點的雙循環(huán)鏈表 D 單循 環(huán)鏈表 .9 設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點， 則選用（ D ） 最節(jié)省時間。 A. 單鏈表 B. 單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D. 帶頭結(jié)點的雙 循環(huán)鏈表 .10. 鏈表不具有的特點是（ B ）. A 插入、刪除不需要移動元素 B 可隨機訪問任一元素 C 不必事先估計存儲空間 D 所需空間與線性長度成正比 .11. 設(shè)一個棧的輸入序列是 1 ，2，3，4，5, 則下列序列中，是棧的合法輸出序 列的是（ D ）。 A. 5 1 2 3 4B. 4 5 1 3 2 C. 4

4、3 1 2 5D. 3 2 1 5 4 .12. 某堆棧的輸入序列為 a, b，c ，d, 下面的四個序列中，不可能是它的輸出 序列的是（ D ）。 A. a ，c，b，d B. b, c， d， a C. c, d ， b, a D. d, c，a，b .13. 用方式存儲的隊列，在進行刪除運算時（ D ）。 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 .14. 用不帶頭結(jié)點的單鏈表存儲隊列時 , 其隊頭指針指向隊頭結(jié)點 , 其隊尾指針 指向隊尾結(jié)點，則在進行刪除操作時 （ D ） 。 A 僅修改隊頭指針B. 僅修改隊尾指針 C. 隊頭、隊

5、尾指針都要修改 D. 隊頭, 隊尾指針都可能要修改 .15 下面關(guān)于串的的敘述中，哪一個是不正確的？（B ） A串是字符的有限序列B 空串是由空格構(gòu)成的串 C模式匹配是串的一種重要運算 D 串既可以采用順序存儲，也可以采用 鏈式存儲 .16 串是一種特殊的線性表，其特殊性體現(xiàn)在 （ B ） A可以順序存儲B數(shù)據(jù)元素是一個字符 C可以存儲D 數(shù)據(jù)元素可以是多個字符 .17 關(guān)于空串與空格串，下面說確的是 （ D ） 。 A 空串與空格串是相同的B空串與空格串長度是相同的 C空格串中存放的都是空格D空串中存放的都是 NULL . 18 圖中有關(guān)路徑的定義是（ A ）。 A 由頂點和相鄰頂點序偶構(gòu)成

6、的邊所形成的序列 B 由不同頂點所形成 的序列 C由不同邊所形成的序列D 上述定義都不是 .19 設(shè)無向圖的頂點個數(shù)為 n，則該圖最多有（ B ）條邊。 2 An-1B n（n-1）/2 C n（n+1）/2D0 E n2 .20 一個 n 個頂點的連通無向圖，其邊的個數(shù)至少為（A ）。 An-1 B n C n+1 D nlogn ； .21 某排序方法的穩(wěn)定性是指 （ D ） 。 A該排序算法不允許有相同的關(guān)鍵字記錄 B該排序算法允許有相同的關(guān)鍵字記錄 C平均時間為 0（n log n ）的排序方法 D 以上都不對 22如果只想得到 1000個元素組成的序列中第 5 個最小元素之前的部分排

7、序的 序列，用（ D ）方法最快。 A起泡排序 B 快速排列 C Shell 排序 D 堆排序 E 簡單選擇排序 .23 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是 （ C ） 排序法。 A插入 B. 選擇 C. 冒泡 D. 都不是 24下面給出的四種排序方法中，排序過程中的比較次數(shù)與排序方法無關(guān)的是。 （ A ） A選擇排序法 B. 插入排序法 C. 快速排序法 D. 都不是 25對序列 15 ，9，7，8，20，-1 ，4進行排序，進行一趟后數(shù)據(jù)的排列變?yōu)?4， 9，-1，8，20，7，15 ；則采用的是（ C ）排序。 A. 選擇 B. 快速 C. 希爾 D. 冒泡 26. 設(shè)樹 T的度為

8、 4，其中度為 1，2，3和 4的結(jié)點個數(shù)分別為 4，2，1，1 則 T 中的葉子數(shù)為（D ） A5B 6 C7D8 27一棵完全二叉樹上有 1001 個結(jié)點，其中葉子結(jié)點的個數(shù)是（ E ） A 250 B 500 C 254 D 505 E 以上答案都不對 28. 有關(guān)二叉樹下列說確的是( B ) . A二叉樹的度為 2 B 一棵二叉樹的度可以小于 2 C二叉樹中至少有一個結(jié)點的度為 2 D 二叉樹中任何一個結(jié)點的度都為 2 .29 二叉樹的第 I 層上最多含有結(jié)點數(shù)為( C ). A2I B 2 I-1 -1 C 2I-1D 2I -1 .30 對于有 n 個結(jié)點的二叉樹 , 其高度為(

9、C ). Anlog 2n B log 2n C ? log 2n? |+1 D 不確定 .31 對二叉樹的結(jié)點從 1 開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、 右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號， 可采用 ( C ) 次序的遍歷實現(xiàn)編號。 A先序B. 中序 C. 后序 D. 從根開始按 層次遍歷 .32. 對 N 個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找 長度為 ( A ) A(N+1)/2 B. N/2 C. N D. (1+N)*N /2 .33. 對線性表進行二分查找時，要求線性表必須( B ) A.以順序方式存儲 B. 以順

10、序方式存儲 , 且數(shù)據(jù)元素有序 C.以方式存儲 D. 以方式存儲 , 且數(shù)據(jù)元素有序 .34 當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用 順序查找，但前者比后者的查找速度 ( C ). A 必定快 B. 不一定 C. 在大部分情況下要快 D. 取決于表遞增還 是遞減 .35. 具有 12 個關(guān)鍵字的有序表，折半查找的平均查找長度( A ) . A. 3.1 B. 4 C. 2.5 D. 5 .36. 既希望較快的查找又便于線性表動態(tài)變化的查找方法是 ( C ) A順序查找 B. 折半查找 C. 索引順序查找 D. 哈希法查找 二、填空題 .1. 對于長度為 255 的表，

11、采用分塊查找，每塊的最佳長度為 16。 .2. 順序查找 n 個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為 _ n _次；當使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為 _n+1 _ 。 .3 在有序表 A1.12 中，采用二分查找算法查等于 A12 的元素，所比較的元 素下標依次為 _6.9.11.12 。 .4. 在一棵二叉樹中，第 5 層上的結(jié)點數(shù)最多為 16 個。 .5. 、 n(n0) 個結(jié)點構(gòu)成的二叉樹，葉結(jié)點最多 floor(n+1)/2) 個，最少有 1 個。若二叉樹有 m個葉結(jié)點，則度為 2 的結(jié)點有 m-1 個。 .6 二叉樹中某一結(jié)點左子樹的深度減去右子樹的深度

12、稱為該結(jié)點的 平衡因子 。 .7. 假定一棵二叉樹的結(jié)點數(shù)為 18，則它的最小深度為 5 ，最大深度為 16 ； .8. 在一棵二叉樹中，度為零的結(jié)點的個數(shù)為 n 0，度為 2的結(jié)點的個數(shù)為 n 2， 則有 n0= n 2 +1。 .9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為 abc，問有 _5_種不同形態(tài)的二叉樹可以 得到這一遍歷結(jié)果，這些二叉樹分別是 。 .10 若不考慮基數(shù)排序，則在排序過程中，主要進行的兩種基本操作是關(guān)鍵字 的_比較_和記錄的 _移動_。 .11 直接插入排序用監(jiān)視哨的作用是 _免去查找過程中每一步都要檢測整個表是 否查找完畢，提高查找效率 。 .12. 不受待排序初始序列的影

13、響，時間復(fù)雜度為 O(N) 的排序算法是 _簡單選擇 排序 _，在排序算法的最后一趟開始之前， 所有元素都可能不在其最終位置上的 排序算法是 _直接插入排序 _。 .13. 判斷一個無向圖是一棵樹的條件是 _n 個定點， n-1 條邊的無向連通圖 。 .14 具有 10個頂點的無向圖，邊的總數(shù)最多為 _45_。 .15 若用 n 表示圖中頂點數(shù)目，則有 條邊的無向圖成為完全圖。 .16 空格串是指 _由空格字符所組成的字符串 _，其長度等于 _空格個數(shù) _。 .17設(shè)T和P是兩個給定的串，在T中尋找等于 P的子串的過程稱為 _模式匹配 ， 又稱 P為_模式串 _。 .18 串的兩種最基本的存儲

14、方式是 _順序儲存 _、_鏈式儲存_；兩個串相等的充 分必要條件是 _長度相等對應(yīng)位置字符也相等 _ 。 .19. 已知鏈隊列的頭尾指針分別是 f 和 r ，則將值 x 入隊的操作序列是 s=(LinkedList)malloc(sizeof(LNode) ； s-data=x;s-next=r-next ； r-next=s ；r=s ；。 .20. 向棧中壓入元素的操作是 _移動指針和插入 。 .21. 在具有 n 個單元的循環(huán)隊列中，隊滿時共有 _n-1_個元素。 .22 用 S表示入棧操作， X 表示出棧操作，若元素入棧的順序為 1234，為了得 到1342出棧順序，相應(yīng)的 S和X的操

15、作串為 _SXSSXSX_X。 .23. 單鏈表是 _線性表 _的存儲表示。 .24. 在雙鏈表中， 每個結(jié)點有兩個指針域， 一個指向 _前驅(qū) _，另一個指向 _后繼 _。 .25 存儲的特點是利用 _指針_來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 .26. 順序存儲結(jié)構(gòu)是通過 _相鄰位置 _表示元素之間的關(guān)系的 ; 鏈式存儲結(jié)構(gòu)是通 過_指針_表示元素之間的關(guān)系的。 .27 線性表 L=(a1,a2, ,an )用數(shù)組表示，假定刪除表中任一元素的概率相 同，則刪除一個元素平均需要移動元素的個數(shù)是 _(n-1)/2_。 .28 根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分 成_單鏈表

16、_和_多重鏈表_；而又根據(jù)指針的連接方式， 鏈表又可分成 _動態(tài)鏈表 _ 和 _靜態(tài)鏈表 _。 .29 數(shù)據(jù)的物理結(jié)構(gòu)包括 _順序儲存 _的表示和 _鏈式儲存 _的表示。 .30 抽象數(shù)據(jù)類型的定義僅取決于它的一組 _邏輯特性 _，而與_在計算機部如何 表示和實現(xiàn) _無關(guān)，即不論其部結(jié)構(gòu)如何變化，只要它的 _數(shù)學(xué)特性 _不變，都不 影響其外部使用。 .31 數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是 算法的時間復(fù)雜度和空間復(fù)雜度 .32. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的 _邏輯結(jié)構(gòu) 和 _物理結(jié)構(gòu) ，以及它們之間的相互關(guān) 系，并對與這種結(jié)構(gòu)定義相應(yīng)的 操作 ，設(shè)計出相應(yīng)的 算法 _。 三程序填空題 1 已知單鏈

17、表 H 為一個用帶頭結(jié)點的鏈表表示的線性表， 如下算法是 將 其倒置 。 請在下劃線處填上正確的語句。 template void Line_ListLink ： Reverse ( ) Line_ListNode *p ， *head=new Line_ListNode( ) ； while(_ first != NULL ) p=first ；first=first link ； plink= head-link; first=head link ； delete _ head ; 2在順序表中隨機存取的數(shù)據(jù)，很容易在順序表中實現(xiàn) 按序號查找 元素。代 碼如下所示，請在下劃線處填上正確的語

18、句。 template bool Line_ListSqu： Find(_ int i _ ，T DataType temp; for(i = 1; _ i flag=1 _ ; i+) flag = 0;for(j = 0; _ j n-i ; j+) if(_ aj.key aj+1.key) flag = 1; temp = aj; aj = aj+1; aj+1 = temp; .5. 按值查找是指在 線性表中查找 與給定值 x 相等的數(shù)據(jù)元素，具體實現(xiàn)代 碼如下，請在下劃線處填上正確的語句。 template int Line_ListSqu： Search(const T retu

19、rn 0; rear=(rear+1)% m; arear=x; length ; return length; int dequeue(int a, int rear, int length, int *x) if() printf( “queueempty”); return 0; *x= a (rear- length +m)%m; Length ; return length; .8.- 刪除運算是將單鏈表的第 i 個結(jié)點刪去。先在單鏈表中找到第 i 1 個結(jié) 點，再刪除其后的結(jié)點。具體算法代碼如下所 , 請在下劃線處填上正確的語句。 template Line_ListLink in

20、t p; Sub.length = 0; if (i S.length | j= 0 |i-1+j s.length return Sub; / 參數(shù)錯誤時，返回空串 for(p = i 1; _pi-1+j _; p+) /把S.chi 1至 S.chi 1+j 復(fù)制到串 Sub 中 Sub.chp i +1 = S.chp; Sub.chj =0; sub.length _ = j; return Sub; 四閱讀理解題 （描述算法思路 , 再綜合出其功能 ） 本題說明 : 算法思路指的是對某種數(shù)據(jù)結(jié)構(gòu) （如, 記錄序列 ）, 進行操作 （如,移動位置）, 的 處理步驟 （ 如,1,2,3

21、 .）. 算法功能指的是要達到的處理目標 (如, 合并成有序的單鏈表 .) .1. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . main() int i,max,a10; printf( “請輸入 10 個整數(shù): ”); for(i=0;i=10;i+) scanf( “ %d”, max=a0; i=1; while(imax) max=ai; i+; printf( “值為 : ”,max); 答：10 個數(shù)字找出其最大值 .2. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . void delete(node *head,int x) node *p,*q; q=he

22、ad; p=head-next; while(p!=NULL) if(p=NULL) printf( 未找到 x ！n); else if(q=head) printf(x 為第一個結(jié)點，無前趨！ n); else q-data=x; q-next=p-next; free(p); .3. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . int InsertPosList(struct List *L, int pos, ElemType x) int i; if(posL-size+1) /*若 pos 越界則插入失敗 */ return 0; if(L-size=L-MaxSize

23、) /* 重新分配更大的存儲空間 */ againMalloc(L); for(i=L-size-1; i=pos-1; i-) L-listi+1=L-listi; L-listpos-1=x; L-size+; return 1; .4. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . void InsertIncreaseList( Seqlist *L , Datatype x ) int i; if ( L-length=ListSize) Error( “overflow); for ( i=L - length ; i0 i-) L-data i =L-data i ;

24、/ 比較并移動元素 L-data i =x; L - length+; .5. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . void DeleteList ( LinkList L, DataType min , DataType max ) ListNode *p , *q , *s; p=L; while( p-next q=p-next;/p 指向第一個不大于 min 結(jié)點的直接前趨， q 指向第一個 大于 min 的結(jié)點 while(q free(s);/ 刪除結(jié)點，釋放空間 p-next=q;/ 將 *p 結(jié)點的直接后繼指針指向 *q 結(jié)點 .6. 閱讀如下算法代碼：描述

25、算法思路 , 再綜合出其功能 . void enqueue(int x) int temp; if(count= n) printf( 隊列上 溢出n); Else count+; temp = (front+count)%n; Queuetemp=x; int dequeue() int temp; if(count =0) printf( 隊列下溢出 n); else temp=Queuefront; front=(front+1)%n; count-; return temp; .7. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . Status ListInsert_L(Lin

26、kList k = 0; / 初始化， p 指向頭結(jié)點， k 為計數(shù)器 while (p + k; / 找到第 i-1 個元素所在結(jié)點 if (!p | k i-1) return ERROR; / 無法插入 if(!(s = (LinkLinst) malloc(sizeof(LNode) / 申請元素 e 的結(jié) 點空間 return OVERFLOW; / 存無空閑單元，無法申請到空間 s-data = e / 申請一個結(jié)點 s ； s-next =p-next ; / 修改 s 的指針域指向 p 的下一結(jié)點 p-next = s; / 修改 p 的指針域指向 s return OK; /

27、LinstInsert_L .8. 下閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . Quicskort(Recordnode r， int low ， int high) /*low 和 high 為記錄序列的下界和上界 */ int i ，j ； struct Recordnode x ； i=low ； j=high ； x=rlow ； while(ij) /* 在序列的右端掃描 */ while(i=x.key)j-; if(ij) ri=rj;i+;/* 在序列的左端掃描 */ while(ij if(ij) rj=ri;j-; ri=x; /* 使用遞歸 */ if(lo

28、wi) Quicksort(r,low,i-1); if(ihigh) Quicksort(r,j+1,high); .9. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . int Binsch(ElemType A, int low, int high, KeyType K) 求出待查區(qū)間中點元素 查找成功返回元素的下 在左子表上繼續(xù)查找 在右子表上繼續(xù)查找 查找區(qū)間為空，查找失敗 if(low=high) int mid=(low+high)/2; / 的下標 if(K=Amid.key) / 標 return mid; else if(KAmid.key) / return Bi

29、nsch(A,low,mid-1,K); else / return Binsch(A,mid+1,high,K); else return -1; / 返回 -1 .10. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . void charge(int a, int n) int i, j, temp; i=0; j=n-1; while(ij) while(ai0 if(ij) temp=ai; ai=aj; aj=temp; i+; j-; .11. 閱讀如下算法代碼：描述算法思路 , 再綜合出其功能 . string Concat_Str(string if (S.length

30、 + T.length MaxLength) /連接后串的長度小于串的 最大長度 for(i = 0; i T.length; i+) S.chS.length+i = T.chi; S.chS.length+T.length =0; S.length += T.length; else / 連接后串的長度大于串的最大長度， for(i = 0; i next; pb = Lb-next;Lc = pc = La; while (pa pc = pa; pa = pa-next; Else pc-next = pc-next = pb; pc = pb; pb = pb-next; pc-next = pa? pa : pb; free(Lb); 五編程題。 .1.設(shè)一 循環(huán)隊列