數(shù)據(jù)結(jié)構(gòu)第一次至第四次作業(yè)答案

1、第一次作業(yè)答案填空題：1、已知棧的基本操作函數(shù)：int InitStack(SqStack *S); /構(gòu)造空棧int StackEmpty(SqStack *S);/判斷?？読nt Push(SqStack*S,ElemType e);/入棧int Pop(SqStack *S,ElemType *e);/出棧函數(shù)conversion實現(xiàn)十進制數(shù)轉(zhuǎn)換為八進制數(shù)，請將函數(shù)補充完整。void conversion()InitStack(S);scanf(%d，& N);while(N)Push(S,N%8) _;N=N/8;while( _ !StackEmpty(S) _)Pop(S,&e);

2、printf(%d ，e);/conversion2.設(shè)循環(huán)隊列的容量為 70,現(xiàn)經(jīng)過一系列的入隊和出隊操作后，front 為20 , rear為11 ,則隊列中元素的個數(shù)為(615)。.在一個單鏈表中刪除 p所指結(jié)點的后繼結(jié)點時，應(yīng)執(zhí)行以下操作：q=p-next;p-next=(q-next).一個算法的效率可分為(時間)效率和(空間)效率。.數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R),其中D是(數(shù)據(jù)元素)的有限集合，R是D上的(關(guān)系)有限集合。.下面程序段的時間復(fù)雜度是(0 (m*n)for（i=0;im;i+）for（j=0;jlchild=NULL)&(root-rchild=NULL)sum

3、+;printf(%dn,root-data);DLR(root-lchild);DLR(root-rchild); return(0);4、(1)s-next=p-next (2)p-next=s5、 (1) ACBD(2) ACDB (3) ADCB (4)BCDA (5)BCAD (6)BDCA(7) CABD (8)CADB (9)CDAB (10)DCBA第四次作業(yè)答案排序過程的每1、寫出用直接插入排序?qū)㈥P(guān)鍵字序列54,23,89,48,64,50,25,90,34一趟結(jié)果。答案：初始:54 , 23, 89, 48, 64, 50, 25, 90, 34 1 :2354)89486

4、45025, 90, 34 2：235489)4864502590, 34 3 ：23485489)6450259034 4 :2348546489)50259034 5 ：23485054 6489)259034 6 ：232548 50546489)9034 7：2325 48 50546489, 90),34 8 ：23 25 48 50546489, 90, 34)設(shè)待排序序列為10,18,4,3,6,12,1,9,15,8請寫出希爾排序每一趟的結(jié)果。增量序列為 5 , 3, 2, 1。答案：初始：10, 18, 4, 3, 6, 12, 1, 9, 15, 8 d=5：10,1 ,4

5、,3,6,12, 18, 9,15, 8 d=3： 3, 1, 4, 8, 6, 12, 10, 9, 15, 18 d=2：3,1,4,8,6,9, 10, 12,15, 18 d=1 : 1 , 3, 4, 6, 8, 9, 10, 12 , 15, 18m*nn*n5.設(shè)循環(huán)隊列的容量為40(序號從0到39),現(xiàn)經(jīng)過一系列的入隊和出隊 運算后，有 front=11 , rear=19;front=19 , rear=11 ；問在這兩種情況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式：(N+r-f)%N(1)L=(40+19-11)%40=8L=(40+11-19)%40=326、

6、若一個線性表中最常用的操作是取第i個元素和找第i個元素的前趨元 素，則采用(順序表)存儲方式最節(jié)省時間.7.在一個長度為n的順序表中刪除第i個元素，需要向前移動(N-i )個元 素8、帶頭結(jié)點的單鏈表head為空的判定條件是(head-next=NULL)9、一個循環(huán)隊列Q的存儲空間大小為M,其隊頭和隊尾指針分別為front和 rear ,則循環(huán)隊列中元素的個數(shù)為(rear-front+m ) %m10、設(shè)用長為n,模式用長為m,則KMPJ法所需的附加空間為(O(m)A:唯一的31C:是一棵樹也是一棵二叉樹28D:可行性、確定性和有窮性1、單項選擇題數(shù)據(jù)結(jié)構(gòu)第一章練習(xí)題）以及它們之間的（）和運

7、算等的學(xué)科。A數(shù)據(jù)元素B計算方法C邏輯存儲D數(shù)據(jù)映像A結(jié)構(gòu)B關(guān)系C運算 D算法數(shù)據(jù)結(jié)構(gòu)被形式的定義為（K,R）,其中K是（）的有限集，R是K上的（有限集。A算法B數(shù)據(jù)元素C數(shù)據(jù)操作D邏輯結(jié)構(gòu)A操彳B映像C存儲D關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（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內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)A數(shù)據(jù)的存儲結(jié)構(gòu)B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的邏輯結(jié)構(gòu)D數(shù)據(jù)元素之間的關(guān)系1.5在數(shù)據(jù)結(jié)構(gòu)中,與所使用的計算機無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A邏輯 B存儲 C邏輯和存儲D物理1.6算法分析的目的是（），算法分析的兩個主要方面是A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中輸入與輸出的關(guān)系C

8、分析算法效率以求改進D分析算法的易懂性和文檔性A空間復(fù)雜度和時間復(fù)雜度B正確性和簡明性C可讀性和文檔性D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性）,它必須具備輸入、輸出和（）等5個特性。A計算方法B排序方法C解決問題的有限運算序列D調(diào)度方法A可行性、可移植性和可擴充性B可行性、確定性和有窮性C確定性、有窮性和穩(wěn)定性D易讀性、穩(wěn)定性和安全性 TOC o 1-5 h z 在以下的敘述中，正確的是()。A線性表和線性存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進先出D隊列的操作方式是先進后出在決定選擇何種存儲結(jié)構(gòu)時，一般不考慮()。A各結(jié)點的值如何B結(jié)點個數(shù)的多少C對數(shù)據(jù)有哪些運算

9、D所用編程語言實現(xiàn)這種結(jié)構(gòu)是否方便在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲()。A數(shù)據(jù)的處理方法 B數(shù)據(jù)元素的類型C數(shù)據(jù)元素之間的關(guān)系D數(shù)據(jù)的存儲方法( )。(1)方法原地工作的含義是指不需要額外的輔助空間(2)在相同的規(guī)模 n下，復(fù)雜度O (n)的算法在時間上總是優(yōu)于復(fù)雜度O (2n)算法(3)所謂時間復(fù)雜度是指最壞情況下，估計算法執(zhí)行時間的一個上界(4)同一個算法，實現(xiàn)語句的級別越高，執(zhí)行效率越低A (1) B (10 (2) C (1) (4) D (3)1.12通常要求同一邏輯結(jié)構(gòu)中所有數(shù)據(jù)元素具有相同的特性，這意味著()。A數(shù)據(jù)元素具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)

10、據(jù)項個數(shù)要相同，而且對應(yīng)的數(shù)據(jù)項類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等( )。A數(shù)據(jù)元素師數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的各數(shù)據(jù)項的集合D 一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)2、設(shè)計與分析題2.1設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：B=(K,R)K=k1,k2,k9R=,畫出這個邏輯結(jié)構(gòu)的圖示， 并確定相對關(guān)系 R,哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點。2.2設(shè)有如圖所示的邏輯結(jié)構(gòu)圖示，給出它的邏輯結(jié)構(gòu)。k9下面程序段的時間復(fù)雜度是()。for (i=0;in;i+)for (j=0;jm;j+) Aij=0；下面程序段的時間復(fù)雜度是()。i=

11、s=0;while (sn)(i+;i=i+1s+=i;s=s+i下面程序段的時間復(fù)雜度是()。s=0;for (i=0;in;i+)for (j+0;jn;j+) s+=Bij;sum=s下面程序段的時間復(fù)雜度是()。i=1 while(in)i=i*3;有如下遞歸函數(shù)fact(n),分析其時間復(fù)雜度。 fact(int n) if (n1)return 1;elsereturn (n*fact(n-1)2.8求兩個n階矩形的乘法 #define MAX 100Void maxtrixmult(int n, int i,j,k;float x;for (i=1;n;i+) for (j=1;

12、jn;j+) x=0;C=A*B,其算法如下:float aMAXMAX),bMAXMAX,float cMAXMAX) TOC o 1-5 h z for( k=1;k=n;k+)x+=aik*bkj;cij=x; 3、填空題。.數(shù)據(jù)的物理結(jié)構(gòu)包括 的表示和 的表示。.對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有 , , , _ 四種。.數(shù)據(jù)的邏輯結(jié)構(gòu)是指 。. 一個數(shù)據(jù)結(jié)構(gòu)在計算機中 稱為存儲結(jié)構(gòu)。.抽象數(shù)據(jù)類型的定義僅取決于它的一組 ,而與 無關(guān)，即 不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特征不變,都不影響其外部使用。.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是 。.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的 _ 和 ,

13、以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的_操作(運算)_,設(shè)計出相應(yīng)的算法。. 一個算法具有 5個特性：、.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是： 二i=1 ; WHILE i1) sum=1 ;for (i=0;sumn;i+) sum+=1;4、簡答題。.數(shù)據(jù)結(jié)構(gòu)是一門研究什么內(nèi)容的學(xué)科？.數(shù)據(jù)元素之間的關(guān)系在計算機中有幾種表示方法？各有什么特點?.數(shù)據(jù)類型和抽象數(shù)據(jù)類型是如何定義的。二者有何相同和不同之處，抽象數(shù)據(jù)類型的主 要特點是什么？使用抽象數(shù)據(jù)類型的主要好處是什么？.回答問題：(1)在數(shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)及數(shù)據(jù)的運算之間存在著怎樣的關(guān)系?(2)若邏輯結(jié)構(gòu)相同但存儲結(jié)構(gòu)不同，則為不同的數(shù)據(jù)結(jié)構(gòu)。這樣的說法對嗎？舉例 說明之。(3)在給定的邏輯結(jié)構(gòu)及其存儲表示上可以定義不同的運算集合，從而得到不同的數(shù) 據(jù)