數(shù)據(jù)結(jié)構(gòu)C版知識點與相應(yīng)題目

1、WORD6/6 第一章知識點P3 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為：（1）線性結(jié)構(gòu) （2）非線性結(jié)構(gòu): 樹型結(jié)構(gòu)和圖型結(jié)構(gòu) P4 從存儲結(jié)構(gòu)（物理結(jié)構(gòu)）上劃分：（1）順序結(jié)構(gòu) ：所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存放到計算機存中仍然相鄰（2）鏈?zhǔn)浇Y(jié)構(gòu)：所有元素存放在可以不連續(xù)的存儲單元中，但元素之間的關(guān)系可以通過地址確定，邏輯上相鄰的元素存放到計算機存后不一定是相鄰的。 P5 算法的五大特性：（1）輸入（2）輸出 （3）有窮性 （4）確定性（5）可行性（可執(zhí)行）P6 算法分析的任務(wù)/方面：（1）時間復(fù)雜度 （重點是計算時間復(fù)雜度P9 1-5 P10 1-12）（2）空間復(fù)雜度（性）：一

2、個算法在執(zhí)行時所占有的存開銷，稱為空間頻度課后部分習(xí)題解釋：1-2簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、線性結(jié)構(gòu)、非線性結(jié)構(gòu)。 數(shù)據(jù)：指能夠被計算機識別、存儲和加工處理的信息載體。 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在計算機程序常作為一個整體進行考慮和處理 數(shù)據(jù)類型：是一個值的集合以與在這些值上定義的一組操作的總稱。 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個方面的容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。 邏輯結(jié)構(gòu)：指各數(shù)據(jù)元素之間的邏輯關(guān)系。 存儲結(jié)構(gòu)：就是數(shù)據(jù)的邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)。 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類，它的特征是若結(jié)

3、構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表就是一個典型的線性結(jié)構(gòu)。 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個結(jié)點可能有多個直接前驅(qū)和直接后繼。補充習(xí)題（ ）是數(shù)據(jù)的基本單位，在計算機程序常作為一個整體進行考慮和處理。解答數(shù)據(jù)元素 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（ ）、（ ）、（ ）和（ ）。解答集合，線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu) 算法指的是（ ）。A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計算機程序 C 解決問題的計算方法 D 數(shù)據(jù)處理解答A分析計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解

4、決問題的方法；數(shù)據(jù)處理是通過算法完成的。所以，只有A是算法的準(zhǔn)確定義。 下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性解答C 分析高效性是好算法應(yīng)具備的特性。 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中輸入和輸出的關(guān)系C 分析算法的效率以求改進 D 分析算法的易讀性和文檔性 E 空間性能和時間性能 F 正確性和簡明性 G 可讀性和文檔性 H 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性解答C，E 6. 對下列用二元組表示的數(shù)據(jù)結(jié)構(gòu),試分別畫出對應(yīng)的邏輯結(jié)構(gòu)圖，并指出屬于何種結(jié)構(gòu)。 A=(D，R)， 其中D=a1, a2, a3

5、, a4，R= B=(D，R)， 其中D=a, b, c, d, e, f，R=, C=( D，R)，其中D=a，b，c，d，e，f，R=, D=(D，R)， 其中D=1, 2, 3, 4, 5, 6，R=(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6) 解答 屬于集合，其邏輯結(jié)構(gòu)圖如圖1-4(a)所示； 屬于線性結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(b)所示； 屬于樹結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(c)所示； 屬于圖結(jié)構(gòu)，其邏輯結(jié)構(gòu)圖如圖1-4(d)所示。 第二章知識點P16 利用線性表來存儲線性表，表中相鄰的元素存儲在計算機的位置也相鄰P

6、21 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，也稱為鏈表。其存儲方式是：在存中利用存儲單元（可以不連續(xù)）來存放元素值與它在存中的地址，各個元素的存放順序與位置都可以以任意順序進行P25 單鏈表上的插入運算 (1)s-next=p-next; (2)p-next=s;P26 單鏈表上的刪除運算 （1）q-next=p-next; （2）delete(p);補充習(xí)題：（1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）。解答108分析第5個元素的存儲地址=第1個元素的存儲地址(51)2=108（2） 設(shè)單鏈表中指針p 指向結(jié)點A，若要刪除A的后繼結(jié)點（假設(shè)A存在后繼結(jié)點），

7、則需修改指針的操作為（ ）。解答p-next=(p-next)-next（3）線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。 A 隨機存取 B 順序存取 C 索引存取 D 散列存取解答A，B（4） 線性表采用存儲時，其地址（ ）。A 必須是連續(xù)的 B 部分地址必須是連續(xù)的C 一定是不連續(xù)的 D 連續(xù)與否均可以解答D分析線性表的存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在存中任意位置。 在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行（ ）操作。A s-nex

8、t=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q;解答B(yǎng)分析注意此題是在q和p之間插入新結(jié)點，所以，不用考慮修改指針的順序。 在循環(huán)雙鏈表的p所指結(jié)點后插入s所指結(jié)點的操作是（ ）。A p-next=s; s-prior=p; p-next-prior=s; s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C s-prior=p; s-next=p-next; p-next=s;

9、 p-next-prior=s;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s解答D分析在鏈表中，對指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。第三章知識點P40 棧 棧是一種后進先出的線性表，簡稱LIFO表。P52 隊列 先進先出，F(xiàn)IFO表重點習(xí)題：課本P58-59:3-1: 進一個出一個，ABCD先進兩個，AB進，進C出C,進D出D，出B出A，CDBA進A進B，進C進D，出D出C出B出A，DCBA下面的不解釋了，不明白你再問BCDA,BDCA,BCAD,BADC,BACD,

10、前三個一起進CBAD,CBDA,CDBA第一個進去就出來ADCB,ACDB,ACBD一共14種3-2; 3-3第四章知識點P61 串 是由零個或多個 字符 組成的有限序列串s=”a1a2an”喲可以表示為s=（a1,a2,an）,即線性表的形式。因此，串也是一種線性表，是一種數(shù)據(jù)類型受到限制（只能為字符型）的線性表?？沾?不含任何字符的串稱為空串，它的長度n=0,記為s=”空白串 含有一個空格的串稱為空白串，它的長度n=1,記為s=“或s=”.子串、主串 若一個串是另一個串中連續(xù)的一段，則這個串稱為另一個串的子串P62 串的運算 （8）求子串位置index(S,T), 在S中找TP69 串的模

11、式匹配 模式匹配如下： int seqstring:INDEX( seqstring S,seqstring T) int i=0,j=0; while (iS.cuelen )&(j=T.curlen) retuen (i-T.curlen); else return (-1); /匹配失敗 第五章知識點P75 多維數(shù)組的存儲結(jié)構(gòu)LOC(a00)是a00的存地址，d是每個元素占的字節(jié)，i是每行，i*n+j是表示aij前面有多少個元素。地址計算 （1）行優(yōu)先：LOC（aij）=LOC(a00)+(i*n+j)*d （2）列優(yōu)先：LOC（aij）= LOC(a00)+(j*m+i)*d例題： 二

12、維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A105的存儲地址是1000，則元素A1510的存儲地址是（ ）。解答1140分析數(shù)組A中每行共有n=6個元素，元素A1510的前面共存儲了(15-10)6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+（(15-10)6+5）*4=1140。 廣義表(a), (b),c),(d)的長度是（），深度是（），表頭是（），表尾是（）。解答3，4，(a)，(b),c),(d)加深習(xí)題：廣義表(a)的表頭是_，表尾是_。2、廣義表（a）,(b), c), (d)）的表頭是_，表尾是_。3、廣義表(a), (b), c), (d)的長度是_，深度是_。4、廣義表(a, (a, b), d, e, (i, j), k)的長度是_，深度是_。5、設(shè)HEADp為求廣義表p的表頭函數(shù)，TAILp為求廣義表p的表尾函數(shù)，其中是函數(shù)的符號，給出下列廣義表的運算結(jié)果：HEAD(a, b, c)的結(jié)果是_。TAIL(a, b, c)的結(jié)果是_。HEAD(a), (b)的結(jié)果是_。TAIL(a), (b)的結(jié)果是_。HEADTAIL(a, b, c)的結(jié)果是_。TAILHEAD(a, b), (c