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

1、第一章作業(yè)一、選擇題1. 算法的計(jì)算量的大小稱為計(jì)算的（ B ）。A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度2. 算法的時(shí)間復(fù)雜度取決于（ A）A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B3.計(jì)算機(jī)算法指的是（C），它必須具備（B） 這三個(gè)特性。(1) A計(jì)算方法 B. 排序方法 C. 解決問題的步驟序列 D. 調(diào)度方法(2) A可執(zhí)行性、可移植性、可擴(kuò)充性 B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性 D. 易讀性、穩(wěn)定性、安全性 4一個(gè)算法應(yīng)該是（ B ）。 A程序 B問題求解步驟的描述 C要滿足五個(gè)基本特性 DA和C. 5. 下面關(guān)于算法說法錯(cuò)誤的是（ D ）A算

2、法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的6. 下面說法錯(cuò)誤的是（ C ） (1）算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界 （4）同一個(gè)算法，實(shí)現(xiàn)語言的級(jí)別越高，執(zhí)行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3)7從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線

3、性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)8在下面的程序段中，對(duì)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 Aj>Aj+1 THEN Aj與Aj+1對(duì)換；其中 n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（D ）A. O（n） B. O(nlogn) C. O(n3) D. O(n2)  二、判斷題1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( × ) 2. 記錄是數(shù)

4、據(jù)處理的最小單位。 (× ) 3. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系；(× )4算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。( )5健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。( × )6算法可以用不同的語言描述，如果用C 語言或PASCAL語言等高級(jí)語言來描述，則算法實(shí)際上就是程序了。(× ) 7程序一定是算法。(× ) 8數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。( )9. 數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。(× ) 10. 在順序存儲(chǔ)結(jié)構(gòu)中，有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。( 

5、5; )11. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( × )三、用C語言程序完成三元組的初始化、取i號(hào)位上的值及修改i號(hào)位上的值。#include<stdio.h>#include<stdlib.h>#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

6、=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("輸入三元組的三個(gè)值:"); scanf("%d%d%d",&e1,&e2,&e3); b=init(&a,e1,e2,e3); if(b=1) printf("

7、%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("位置錯(cuò)誤n"); 第二章作業(yè)一 選擇題1下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ A ）A存儲(chǔ)密度大 B插入運(yùn)算方便 C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2下面關(guān)于線性表的

8、敘述中，錯(cuò)誤的是哪一個(gè)？（ B ）A線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。D線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。3線性表是具有n個(gè)（ C ）的有限序列（n>0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) E信息項(xiàng)4若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ A ）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表5某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ D ）存儲(chǔ)方式最節(jié)省

9、運(yùn)算時(shí)間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表6設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用( D )最節(jié)省時(shí)間。A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表7若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用（ D ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B雙鏈表 C單循環(huán)鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表8. 靜態(tài)鏈表中指針表示的是（ C ）. A 內(nèi)存地址 B數(shù)組下標(biāo) C下一元素地址 D左、右孩子地址9. 鏈表不具有的特點(diǎn)是（ B ） A插入、刪除不需要移動(dòng)元素 B可隨機(jī)訪問任一元素 C

10、不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比10. 下面的敘述不正確的是（ B,C ）A線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比 B. 線性表在鏈?zhǔn)酱鎯?chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)C. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i 的值成正比D. 線性表在順序存儲(chǔ)時(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)12.(1) 靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無關(guān)。 (2) 靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在表定義時(shí)就確定了，以后不能增加。 (3) 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)。以上錯(cuò)誤的是（ B

11、） A（1），（2） B（1） C（1），（2）,(3) D.（2）13. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ C ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2) 14. 對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)15線性表（ a1,a2,an）以鏈接方式存儲(chǔ)時(shí)，訪問第i位置元素的時(shí)間復(fù)雜性為（ C ）AO（i） BO（1） CO（n） DO（i-1）16非空的

12、循環(huán)單鏈表head的尾結(jié)點(diǎn)p滿足（ A ）。Ap->link=head Bp->link=NILL Cp=NILL Dp= head17循環(huán)鏈表H的尾結(jié)點(diǎn)P的特點(diǎn)是（A ）。 AP.NEXT:=H BP.NEXT:= H.NEXT CP:=H DP:=H.NEXT18在一個(gè)以 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é)點(diǎn)p之后插入s的操作是（ D ）； A p->next:=s ; s-&g

13、t;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 ;

14、p->next:=s;二、判斷1. 鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。(× )2. 順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。( ) 3線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。( )4順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。( × )5. 對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(× ) 6順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。(× )7集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。( × ) 8. 所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。(× ) 9. 線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)

15、和一個(gè)后繼。(× )10. 取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān). (× ) 11. 循環(huán)鏈表不是線性表. (× ) 12. 線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。(× ) 13. 線性表就是順序存儲(chǔ)的表。( × ) 14為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。( )15. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。( × ) 16. 鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí)，在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。 ( )  三、編寫下列算法：1、 將兩個(gè)單鏈表合并成一個(gè)單鏈表。 void m

16、erge(ListLink &La,ListLink &Lb)p=La->next; while(p->next) p=p->next; p->next=Lb->next; free(Lb);2、 有一個(gè)有序單鏈表（從小到大），表頭指針為head，編寫一個(gè)算法向該單鏈表中插入一個(gè)元素值為x的結(jié)點(diǎn)，使插入后該鏈表依然有序。void insert(LinkList &head, ElemType x) p=head; while(p->next &&p->next<x) p=p->next; s= ( L

17、inkList ) malloc( sizeof ( LNode ) ; s->data=x; s->next= p->next ; p->next =s ;3、 用算法是實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表數(shù)據(jù)結(jié)點(diǎn)逆置。（原鏈表為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é)點(diǎn)的地址保存在r中 p->next=L->next;/將p卸下來，每次插在L之和，第一個(gè)結(jié)點(diǎn)之前 L->n

18、ext=p; p=r;/還原p第三章作業(yè)1、 設(shè)隊(duì)列中有A、B、C、D、E這五個(gè)元素，其中隊(duì)首元素為A。如果對(duì)這個(gè)隊(duì)列重復(fù)執(zhí)行下列4步操作：（1） 輸出隊(duì)首元素；（2） 把隊(duì)首元素值插入到隊(duì)尾；（3） 刪除隊(duì)首元素；（4） 再次刪除隊(duì)首元素。直到隊(duì)列為空為止，求得到的輸出序列。ACECC（1）輸出A，(2)隊(duì)列為ABCDEA(3)隊(duì)列為BCDEA （4）隊(duì)列為CDEA重復(fù)：（1）輸出C，(2)隊(duì)列為CDEAC(3)隊(duì)列為DEAC（4）隊(duì)列為EAC重復(fù)：（1）輸出E，(2)隊(duì)列為EACE(3)隊(duì)列為ACE（4）隊(duì)列為CE重復(fù)：（1）輸出C，(2)隊(duì)列為CC(3)隊(duì)列為C（4）隊(duì)列為空得到的輸出序

19、列：ACECC2、 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)尾指針rear指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的隊(duì)列初始化、入隊(duì)列和出隊(duì)列的算法。void initqueue（LinkList &rear）/初始化隊(duì)列為空隊(duì)列rear= ( LinkList ) malloc( sizeof ( LNode ) ;rear->next=rear;void inqueue（LinkList &rear ,ElemType e）/入隊(duì)列 s= ( LinkList ) malloc( sizeof ( LNode ) ; s->data=e; p->

20、;next=rear->next; rear->next=p; rear=p;void Delqueue（LinkList &rear ,ElemType &e）/出隊(duì)列 if(rear->next=rear) printf(“隊(duì)列為空”)； else p=rear->next->next; rearr->next->next=p->next; free(p);第六章作業(yè)1、已知二叉樹的前序序列為ABDGHCEFI和中序序列GDHBAECIF，求后序序列。2、對(duì)二叉樹中的結(jié)點(diǎn)進(jìn)行按層次順序(每一層自左至右)的訪問操作稱為二叉樹的層

21、次遍歷，遍歷所得到的結(jié)點(diǎn)序列稱為二叉樹層次序列?，F(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ,中序序列為DBGEHJACIF，請(qǐng)畫出此二叉樹。3、對(duì)下圖所示的森林： (1)求森林的前序序列和后序序列；(2)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹； (1)此森林的前序序列： ABCDEFGHIJKLMPQRNO此森林的后序序列： BDEFCAIJKHGQRPMNOL4、假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h中的字母構(gòu)成，這8個(gè)字母在電文中出現(xiàn)的概率分別為0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10(1)試構(gòu)造哈夫曼樹。(2)寫出這8個(gè)字母的哈夫曼編碼。

22、哈夫曼編碼圖見題圖根據(jù)上圖可得編碼表：根據(jù)上圖可得編碼表： a:0010b:10c:00000d:0001 e:01f:00001g:11h:00115、算法設(shè)計(jì): 用先序遍歷和中根序遍歷的思想統(tǒng)計(jì)葉子結(jié)點(diǎn)的個(gè)數(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); /還可以用非遞歸的思想實(shí)現(xiàn)6、算