1、第一章作業 一、選擇題1. 算法的計算量的大小稱為計算的( B )。A效率B. 復雜性 C. 現實性 D. 難度2. 算法的時間復雜度取決于( A )A問題的規模B. 待處理數據的初態 C. A 和 B3. 計算機算法指的是( C)，它必須具備( B) 這三個特性。(1) A 計算方法 B. 排序方法 法(2) A 可執行性、可移植性、可擴充性 C. 確定性、有窮性、穩定性 4一個算法應該是( B )。A 程序 B 問題求解步驟的描述 5. 下面關于算法說法錯誤的是( D )A算法最終必須由計算機程序實現C. 解決問題的步驟序列 D. 調度方B. 可執行性、確定性、有窮性D. 易讀性、穩定性、

2、安全性C 要滿足五個基本特性 DA 和 C.B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性D. 以上幾個都是錯誤的6. 下面說法錯誤的是( C )(1 )算法原地工作的含義是指不需要任何額外的輔助空間2)在相同的規模 n 下，復雜度 O(n)的算法在時間上總是優于復雜度O(2n) 的算法(3) 所謂時間復雜度是指最壞情況下，估算算法執行時間的一個上界(4) 同一個算法，實現語言的級別越高，執行效率就越低A (1) B.(1),(2) C.(1),(4) D.(3) 7從邏輯上可以把數據結構分為(C )兩大類。A動態結構、靜態結構B 順序結構、鏈式結

3、構C線性結構、非線性結構D 初等結構、構造型結構8在下面的程序段中，對 x 的賦值語句的頻度為( D ) FOR i:=1 TO n DO FOR j:=1 TO n DOx:=x+1;A O(2n) B O(n) C O(n2) D O(log 2n) 9程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF Aj>Aj+1THEN Aj 與 Aj+1 對換；其中 n 為正整數，則最后一行的語句頻度在最壞情況下是( D ) 32A. O (n) B. O(nlogn) C. O(n3) D. O(n2)二、判斷題1. 數據元素是數據的最小單位。 ( &

4、#215; )2. 記錄是數據處理的最小單位。 ( × )3. 數據的邏輯結構是指數據的各數據項之間的邏輯關系；( × )4算法的優劣與算法描述語言無關，但與所用計算機有關。( )5健壯的算法不會因非法的輸入數據而出現莫名其妙的狀態。( × )6算法可以用不同的語言描述，如果用C 語言或 PASCAL語言等高級語言來描述，則算法實際上就是程序了。 ( × ) 7程序一定是算法。 ( × ) 8數據的物理結構是指數據在計算機內的實際存儲形式。( )9. 數據結構的抽象操作的定義與具體實現有關。 ( × )10. 在順序存儲結構中，有時也

5、存儲數據結構中元素之間的關系。 ( × )11. 順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高。 ( × )三、用 C語言程序完成三元組的初始化、取 i號位上的值及修改 i 號位上的值。 #include<stdio.h>#include<stdlib.h> #define ok 1 #define error -1 typedef int *triplet; typedef int status;status init(triplet *t,int v1,int v2,int v3)*t=(int *)malloc(3*sizeof(in

6、t); if (!(*t) return error;(*t)0=v1;(*t)1=v2;(*t)2=v3; return ok;status get(triplet t,int i,int *e) if(i<1|i>3) return error;*e=ti-1 ; return ok;void main() triplet a; int i,e,e1,e2,e3;int b; printf(" 輸入三元組的三個值 :"); scanf("%d%d%d",&e1,&e2,&e3);b=init(&a,e1,e

7、2,e3);if(b=1) printf("%5d,%5d,%5dn",a0,a1,a2);else printf(" 創建三元組失敗 n"); printf(" 輸入取得三元組元素的位置 :");scanf("%d",&i);b=get(a,i,&e);if(b=1) printf("%5dn" ,e); else printf(" 位置錯誤 n");第二章作業一 選擇題1下述哪一條是順序存儲結構的優點？（A ）A存儲密度大 B 插入運算方便 C 刪除運算方

8、便 D 可方便 地 用于各種邏輯結構 的存儲表示2下面關于線性表的敘述中，錯誤的是哪一個？（B ）A線性表采用順序存儲，必須占用一片連續的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有 n 個（ C ）的有限序列（ n>0）。A表元素B 字符 C 數據元素 D 數據項 E 信息項4若某線性表最常用的操作是存取任 一 指定序號的元素和在最后進行插入和刪除運算， 則利用（ A ）存儲方式最節省時間。A順序表B 雙鏈表 C 帶頭結點的雙循環鏈表 D 單循環鏈表5某線性表中最常用的

9、操作是在最后一個元素之后插入一個元素和刪除第一個元素， 則采用（ D ）存儲方式最節省運算時間。A單鏈表 B 僅有頭指針的單循環鏈表 C 雙鏈表 D 僅有尾指針的 單循環鏈表6設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用（ D ） 最節省時間。A. 單鏈表 B. 單循環鏈表 C. 帶尾指針的單循環鏈表 D. 帶頭結點的雙循環鏈表 7若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點。則采用（D ）存儲方式最節省運算時間。A單鏈表 B 雙鏈表 C 單循環鏈表D 帶頭結點的雙循環鏈表8.靜態鏈表中指針表示的是（ C）.A內存地址 B 數組下標C 下一元素地址 D 左

10、 、 右孩子地址9.鏈表不具有的特點是（ B ）A插入、刪除不需要移動元素 B 可隨機訪問任一元素C不必事先估計存儲空間 D 所需空間與線性長度成正比10. 下面的敘述不正確的是（ B,C）A線性表在鏈式存儲時，查找第 i個元素的時間同i 的值成正比B.線性表在鏈式存儲時，查找第 i個元素的時間同i 的值無關C.線性表在順序存儲時，查找第 i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第 i 個元素的時間同 i 的值無關12. (1) 靜態鏈表既有順序存儲的優點，又有動態鏈表的優點。所以 ， 它存取表中第 i 個元 素的時間與 i 無關。(2) 靜態鏈表中能容納的元素個數的最大數

11、在表定義時就確定了，以后不能增加。(3) 靜態鏈表與動態鏈表在元素的插入、刪除上類似，不需做元素的移動。 以上錯誤的是( B )A ( 1)，(2) B ( 1) C ( 1)，(2) ,(3) D.(2)13. 若長度為 n 的線性表采用順序存儲結構， 在其第 i 個位置插入一個新元素的算法的時間 復雜度為( C ) (1<=i<=n+1) 。2A. O(0) B. O(1)C. O(n)D. O(n2)14. 對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為( C )。AO(n) O(n)B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)1

12、5線性表( a1,a2, ,an )以鏈接方式存儲時， 訪問第 i 位置元素的時間復雜性為 ( C )A O(i ) B 16非空的循環單鏈表O(1) C O(n)head 的尾結點 p 滿足( AO( i-1 )。A p->link=headBp->link=NILL Cp=NILL D p= head17循環鏈表 H的尾結點 P 的特點是( A)。A P.NEXT:=HBP.NEXT:= H.NEXTP:=H D P:=H.NEXT18在一個以 h 為頭的單循環鏈中， p 指針指向鏈尾的條件是( A)A. p->next=h B. p->next=NULLL C.

13、p->next->next=h D. p->data=-1 19完成在雙循環鏈表結點 p 之后插入 s 的操作是( D )；A p->next:=s ; s->priou:=p; p->next->priou:=s ; s->next:=p->next;B p ->next ->priou:=s; p ->next:=s; s ->priou:=p; s ->next:= p->next;C s ->priou:=p; s ->next:=p->next; p->next:=s;

14、p->next->priou:=s ;D s->priou:=p; s->next:=p->next; p->next->priou:=s ; p->next:=s;二、判斷1. 鏈表中的頭結點僅起到標識的作用。 ( × )2. 順序存儲結構的主要缺點是不利于插入或刪除操作。 ( )3 線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的。 ( ) 4順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。( × )5. 對任何數據結構鏈式存儲結構一定優于順序存儲結構。 ( × )6 順序存儲方式只能用于

15、存儲線性結構。 ( × ) 7集合與線性表的區別在于是否按關鍵字排序。( × )8. 所謂靜態鏈表就是一直不發生變化的鏈表。( × )9. 線性表的特點是每個元素都有一個前驅和一個后繼。 ( × )10. 取線性表的第 i 個元素的時間同 i 的大小有關 . ( × )11. 循環鏈表不是線性表 . ( × )12. 線性表只能用順序存儲結構實現。 ( × )13. 線性表就是順序存儲的表。 ( × ) 14為了很方便的插入和刪除數據，可以使用雙向鏈表存放數據。( )15. 順序存儲方式的優點是存儲密度大，且插入、

16、刪除運算效率高。 ( × )16. 鏈表是采用鏈式存儲結構的線性表 , 進行插入、刪除操作時，在鏈表中比在順序存儲結 構中效率高。 ( )三、編寫下列算法：1、將兩個單鏈表合并成一個單鏈表。void merge(ListLink &La,ListLink &Lb)p=La->next;while(p->next) p=p->next;p->next=Lb->next;free(Lb);2、有一個有序單鏈表(從小到大) ，表頭指針為 head，編寫一個算法向該單鏈表中插入一 個元素值為 x 的結點，使插入后該鏈表依然有序。void inse

17、rt(LinkList &head, ElemType x)p=head;while(p->next &&p->next<x) p=p->next;s= ( LinkList ) malloc( sizeof ( LNode ) ;s->data=x;s->next= p->next ;p->next =s ;3、用算法是實現帶頭結點的單鏈表數據結點逆置。(原鏈表為 a1， a2,an)(逆置后為： an,an-1, ,a2,a1)void server(LinkList &L)p=L->next; L-&g

18、t;next=NULL;while(p) r=p->next;/ 將 p 的后繼結點的地址保存在 r 中p->next=L->next;/ 將 p 卸下來，每次插在 L 之和，第一個結點之前L->next=p;p=r;/ 還原 pA。如果對這個隊列重復執第三章作業1、 設隊列中有 A、B、C、D、E 這五個元素，其中隊首元素為行下列4 步操作：（1）輸出隊首元素；（2）把隊首元素值插入到隊尾；（3）刪除隊首元素；（4）再次刪除隊首元素。直到隊列為空為止，求得到的輸出序列。 ACECC （ 1）輸出 A，（2）隊列為 ABCDEA（3）隊列為 BCDEA （ 4）隊列為

19、CDEA 重復：（ 1）輸出 C，（2）隊列為 CDEAC（3）隊列為 DEAC （4）隊列為 EAC重復：（ 1）輸出 E，（2）隊列為 EACE（3）隊列為 ACE （ 4）隊列為 CE重復：（ 1）輸出 C，（2）隊列為 CC（3）隊列為 C（ 4）隊列為空 得到的輸出序列： ACECC2、 假設以帶頭結點的循環鏈表表示隊列，并且只設一個尾指針rear 指向隊尾元素結點(注意不設頭指針) ，試編寫相應的隊列初始化、入隊列和出隊列的算法。void initqueue ( LinkList&rear )/ 初始化隊列為空隊列rear= ( LinkList ) malloc( siz

20、eof ( LNode ) ;rear->next=rear;void inqueue( LinkList&rear ,ElemTypee)/ 入隊列s= ( LinkList ) malloc( sizeof ( LNode ) ;s->data=e;p->next=rear->next;rear->next=p;rear=p;void Delqueue( LinkList &rear ,ElemType &e )/ 出隊列if(rear->next=rear) printf( “隊列為空 ”) ；elsep=rear->ne

21、xt->next; rearr->next->next=p->next; free(p);第六章作業1、已知二叉樹的前序序列為 ABDGHCEFI 和中序序列 GDHBAECIF，求后序序列。2、對二叉樹中的結點進行按層次順序 （每一層自左至右 ） 的訪問操作稱為二叉樹的層次遍歷， 遍歷所得到的結點序列稱為二叉樹層次序列。 現已知一棵二叉樹的層次序列為 ABCDEFGHIJ, 中序序列為 DBGEHJACI，F 請畫出此二叉樹。3、對下圖所示的森林：(1) 求森林的前序序列和后序序列；(2) 將此森林轉換為相應的二叉樹；(1) 此森林的前序序列：此森林的后序序列：ABC

22、DEFGHIJKLMPQRNOBDEFCAIJKHGQRPMNOL中的字母構成，a,b,c,d,e,f,g,h4、假設用于通信的電文由字符集現的概率分別為 0.07, 0.19 ,0.02 , 0.06 ,0.32, 0.03 ,0.21 ,0 .10 這 8 個字母在電文中出(1) 試構造哈夫曼樹。(2) 寫出這 8 個字母的哈夫曼編碼。哈夫曼編碼圖見題圖 根據上圖可得編碼表：根據上圖可得編碼表：a:0010b:10c:00000d:0001e:01f:00001g:11h:00115、算法設計 : 用先序遍歷和中根序遍歷的思想統計葉子結點的個數。 解法一：先序遍歷 int Leaf ( Bitree t )int static n=0;if(t) if(t->lchild=NULL&&t->rchild=NULL) n+;Leaf(t->lchild);Leaf(t->lchild);return n;解法一：中序遍歷int n=0 ；void Leaf ( Bitree t )if(t) Leaf(t->lchild); if(t->lchild=NULL&&t->rchild=NULL) n+;Leaf(t->