數(shù)據(jù)結(jié)構(gòu)作業(yè)解答

.第一章作業(yè)一、選擇題1. 算法的計算量的大小稱為計算的（ B ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度2. 算法的時間復(fù)雜度取決于（ A）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計算機算法指的是（C），它必須具備（B） 這三個特性。(1) A計算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 4一個算法應(yīng)該是（ B ）。 A程序 B問題求解步驟的描述 C要滿足五個基本特性 DA和C. 5. 下面關(guān)于算法說法錯誤的是（ D ）A算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的6. 下面說法錯誤的是（ C ） (1）算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 （4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8在下面的程序段中，對x的賦值語句的頻度為（ D ）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 9程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF AjAj+1 THEN Aj與Aj+1對換；其中 n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（D ）A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 二、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( ) 2. 記錄是數(shù)據(jù)處理的最小單位。 ( ) 3. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；( )4算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。( )5健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( )6算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。( ) 7程序一定是算法。( ) 8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。( )9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實現(xiàn)有關(guān)。( ) 10. 在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。( )11. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( )三、用C語言程序完成三元組的初始化、取i號位上的值及修改i號位上的值。#include#include#define ok 1#define error -1typedef int *triplet;typedef int status;status init(triplet *t,int v1,int v2,int v3)*t=(int *)malloc(3*sizeof(int); if (!(*t) return error;(*t)0=v1; (*t)1=v2; (*t)2=v3; return ok; status get(triplet t,int i,int *e) if(i3) 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,e2,e3); if(b=1) printf(%5d,%5d,%5dn,a0,a1,a2); else printf(創(chuàng)建三元組失敗n); printf(輸入取得三元組元素的位置:); scanf(%d,&i); b=get(a,i,&e); if(b=1) printf(%5dn ,e); else printf(位置錯誤n); 第二章作業(yè)一 選擇題1下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（ A ）A存儲密度大 B插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示2下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ B ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3線性表是具有n個（ C ）的有限序列（n0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項 E信息項4若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ A ）存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D ）存儲方式最節(jié)省運算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用( D )最節(jié)省時間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點的雙循環(huán)鏈表7若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點。則采用（ D ）存儲方式最節(jié)省運算時間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ C ）. A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址9. 鏈表不具有的特點是（ B ） A插入、刪除不需要移動元素 B可隨機訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比10. 下面的敘述不正確的是（ B,C ）A線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯r，查找第i個元素的時間同i的值無關(guān)C. 線性表在順序存儲時，查找第i個元素的時間同i 的值成正比D. 線性表在順序存儲時，查找第i個元素的時間同i的值無關(guān)12.(1) 靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關(guān)。 (2) 靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。 (3) 靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是（ B ） A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ C ）(1=ilink=head Bp-link=NILL Cp=NILL Dp= head17循環(huán)鏈表H的尾結(jié)點P的特點是（A ）。 AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一個以 h 為頭的單循環(huán)鏈中，p 指針指向鏈尾的條件是（A） A. p-next=h B. p-next=NULLL C. p-next-next=h D. p-data=-119完成在雙循環(huán)鏈表結(jié)點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; p-next-priou:=s ;D s-priou:=p; s-next:=p-next; p-next-priou:=s ; p-next:=s;二、判斷1. 鏈表中的頭結(jié)點僅起到標(biāo)識的作用。( )2. 順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。( ) 3線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。( )4順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩? )5. 對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。( ) 6順序存儲方式只能用于存儲線性結(jié)構(gòu)。( )7集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。( ) 8. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。( ) 9. 線性表的特點是每個元素都有一個前驅(qū)和一個后繼。( )10. 取線性表的第i個元素的時間同i的大小有關(guān). ( ) 11. 循環(huán)鏈表不是線性表. ( ) 12. 線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。( ) 13. 線性表就是順序存儲的表。( ) 14為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。( )15. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。( ) 16. 鏈表是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。 ( ) 三、編寫下列算法：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的結(jié)點，使插入后該鏈表依然有序。void insert(LinkList &head, ElemType x) p=head; while(p-next &p-nextnext; s= ( LinkList ) malloc( sizeof ( LNode ) ; s-data=x; s-next= p-next ; p-next =s ;3、 用算法是實現(xiàn)帶頭結(jié)點的單鏈表數(shù)據(jù)結(jié)點逆置。（原鏈表為a1，a2,an）（逆置后為：an,an-1,a2,a1） void server(LinkList &L) p=L-next; L-next=NULL;while(p) r=p-next;/將p的后繼結(jié)點的地址保存在r中 p-next=L-next;/將p卸下來，每次插在L之和，第一個結(jié)點之前 L-next=p; p=r;/還原p第三章作業(yè)1、 設(shè)隊列中有A、B、C、D、E這五個元素，其中隊首元素為A。如果對這個隊列重復(fù)執(zhí)行下列4步操作：（1） 輸出隊首元素；（2） 把隊首元素值插入到隊尾；（3） 刪除隊首元素；（4） 再次刪除隊首元素。直到隊列為空為止，求得到的輸出序列。ACECC（1）輸出A，(2)隊列為ABCDEA(3)隊列為BCDEA （4）隊列為CDEA重復(fù)：（1）輸出C，(2)隊列為CDEAC(3)隊列為DEAC（4）隊列為EAC重復(fù)：（1）輸出E，(2)隊列為EACE(3)隊列為ACE（4）隊列為CE重復(fù)：（1）輸出C，(2)隊列為CC(3)隊列為C（4）隊列為空得到的輸出序列：ACECC2、 假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個尾指針rear指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。void initqueue（LinkList &rear）/初始化隊列為空隊列rear= ( LinkList ) malloc( sizeof ( LNode ) ;rear-next=rear;void inqueue（LinkList &rear ,ElemType e）/入隊列 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(“隊列為空”)； else p=rear-next-next; rearr-next-next=p-next; free(p);第六章作業(yè)1、已知二叉樹的前序序列為ABDGHCEFI和中序序列GDHBAECIF，求后序序列。2、對二叉樹中的結(jié)點進行按層次順序(每一層自左至右)的訪問操作稱為二叉樹的層次遍歷，遍歷所得到的結(jié)點序列稱為二叉樹層次序列?，F(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ,中序序列為DBGEHJACIF，請畫出此二叉樹。3、對下圖所示的森林： (1)求森林的前序序列和后序序列；(2)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹； (1)此森林的前序序列： ABCDEFGHIJKLMPQRNO此森林的后序序列： BDEFCAIJKHGQRPMNOL4、假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10(1)試構(gòu)造哈夫曼樹。(2)寫出這8個字母的哈夫曼編碼。哈夫曼編碼圖見題圖根據(jù)上圖可得編碼表：根據(jù)上圖可得編碼表： a:0010b:10c:00000d:0001 e:01f:00001g:11h:00115、算法設(shè)計: 用先序遍歷和中根序遍歷的思想統(tǒng)計葉子結(jié)點的個數(shù)。解法一：先序遍歷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-lchild); /還可以用非遞歸的思想實現(xiàn)6、算法設(shè)計: 已知二叉樹采用二叉鏈表存放，要求返回二叉樹的后序遍歷的第一個結(jié)點的指針，不用棧不用遞歸實現(xiàn)。Bitree order