c語言數(shù)據(jù)結構總結

1、數(shù)據(jù)結構大全一、概論二、線性表三、棧和隊列四、串五、多維數(shù)組和廣義表.十、文件_六、樹七、圖八、排序九、查找27一、概論1、評價一個算法時間性能的主要標準是 ( 算法的時間復雜度) 。2、算法的時間復雜度與 問題的規(guī)模 有關外，還與輸入實例的 ( 初始狀態(tài) ) 有關。3、一般，將算法求解問題的輸入量稱為 ( 問題的規(guī)模 ) 。4、在選擇算法時，除首先考慮正確性外，還應考慮哪三點 ?答：選用的算法首先應該是”正確”的。此外，主要考慮如下三點： 執(zhí)行算法所耗費的時間； 執(zhí) 行算法所耗費的存儲空間，其中主要考慮輔助存儲空間： 算法應易于理解，易于編碼，易于調(diào)試等等 。6、下列四種排序方法中，不穩(wěn)定的

2、方法是 ( D )A、直接插入排序B冒泡排序C、歸并排序D直接選擇排序7、按增長率由小至大的順序排列下列各函數(shù)：100 n n n 0.5 n lgn 3/22100, (3/2)n ，(2/3)n ，nn,n0.5 , n!， 2n， lgn , nlgn, n3/2答：常見的時間復雜度按數(shù)量級遞增排列，依次為：常數(shù)0(1)、對數(shù)階0(log2n)、線形階0(n)、線形對數(shù)階0(nlog2n)、平方階0(n2)立方階0(n3)、k次方階0(n)、指數(shù)階0(2)。顯然，時間復雜度為指 數(shù)階0(2n)的算法效率極低，當n值稍大時就無法應用。先將題中的函數(shù)分成如下幾類：常數(shù)階： 2100對數(shù)階：

3、lgn0.53/2K 次方階： n 、 n指數(shù)階 (按指數(shù)由小到大排 )： nlgn、 (3/2)n、 2n、n!、 nn注意：(2/3)n由于底數(shù)小于1,所以是一個遞減函數(shù)，其數(shù)量級應小于常數(shù)階。根據(jù)以上分析按增長率由小至大的順序可排列如下：(2/3)n <2100 < lgn < n0.5< n3/2 < nlgn <(3/2)n < 2n < n! < nn順序存儲方法 、 鏈接 存儲方法、 索引 存100n2和2n,要使前者快于后者，n至少要B 、線性表中包含的數(shù)據(jù)元素個數(shù)D存在這樣的線性表：表中各結8、常用的存儲表示方法有哪幾種

4、? 常用的存儲表示方法： 儲方法、 散列 存儲方法。9、設有兩個算法在同一機器上運行,其執(zhí)行時間分別為( 15 )。二、線性表1、以下關于線性表的說法不正確的是 ( C )。A、線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。 不是任意的。C線性表中的每個結點都有且只有一個直接前趨和直接后繼。 點都沒有直接前趨和直接后繼。2、線性表是一種典型的 ( 線性 )結構。3、線性表的邏輯結構特征是什么 ?答：對于非空的線性表： 有且僅有一個開始結點 A1,沒有直接前趨，有且僅有一個直接后繼A2;有且僅有一個終結結點 AN沒有直接后繼，有且僅有一個直接前趨AN-1 :其余的內(nèi)部結點 AI(2<

5、 I WN-1 )都有且僅有一個直接前趨 AI-1和一個AI+1。4、 線性表的順序存儲結構是一種 ( 隨機存取 )的存儲結構。 線性結構的順序存儲結構是一種隨機存 取的存儲結構, 線性表的鏈式存儲結構是一種順序存取的存儲結構。 線性表若采用鏈式存儲表示時所有結點之間的存 儲單元地址可連續(xù)可不連續(xù)5、在順序表中,只要知道 ( 基地址和結點大小 ) ,就可在相同時間內(nèi)求出任一結點的存儲地 址。6、在等概率情況下,順序表的插入操作要移動 ( 一半 )結點。7、在一個長度為n的順序表中刪除第i個元素，要移動（n-i ）個元素8、如果要在第i個元素前插入一個元素，要后移 （n-i+1 ）個元素。9、采

6、用（順序）存儲結構的線性表叫順序表。10、 順序表中邏輯上相鄰的元素的物理位置（相鄰）。11、在（C ）運算中，使用順序表比鏈表好。A、插入B、刪除C、根據(jù)序號查找D、根據(jù)元素值查找12、 在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是（0（n）。13、 在無頭結點的單鏈表中，第1個結點的地址存放在頭指針中，其他結點的存儲地址存放在 （前趨）結點的next域中。14、在（循環(huán)）鏈表中，從任何一結點出發(fā)都能訪問到表中的所有結點。15、（雙向）鏈表適合從指點結點開始，尋找直接前趨的運算。16、順序表相對于鏈表的優(yōu)點有節(jié)省存儲和隨機存取。17、在鏈表的開始結點前設置頭結點的優(yōu)

7、點是什么？答：頭結點是在鏈表的開始結點之前附加一個結點。它具有兩個優(yōu)點：（1）、由于開始結點的位置被，所以在鏈表的第一個存放在頭結點的指針域中位置上的操作就和在表的其它位置上操作一致，無須進行特殊處理；（2）、無論鏈表是否為空，其頭指針是指向頭結點的非空指針（空表中頭結點的指針 域空），因此空表和非空表的處理也就統(tǒng)一了。18、（雙向鏈表）適合作為經(jīng)常在首尾兩端操作線性表的存儲結構。19、如果線性表的存儲空間變化較大，則適合用（鏈）表。20、當線性表的數(shù)據(jù)變化不大，主要用于查詢時，用（順序）表比較好。21、在鏈表中，每個結點中含8個字符，1個指針域。其中每個字符占1個字節(jié)，每個指針占4個字節(jié)。則

8、該結點的存儲密度是（2/3 ）。（1+1+4）/（8+1）=2/3 存儲密度=（結點數(shù)據(jù)本身所占的存儲量）/ （結點結構所占的存儲總量）22、鏈表相對于順序表的優(yōu)點有插入和刪除操作方便。23、在n個結點的順序表中 插入一個結點需平均移動 n/2個結點，具體任務的移動次數(shù)取決于 表長 n和插入位置i。24、在n個結點的順序表中 刪除一個結點需平均移動（n 1） /2個結點，具體任務的移動次數(shù)取決于表長n和刪除位置io25、尾指針是指向終端結點的指針查找時間都是0（1），用頭指針來表示該鏈表，則查找終端結點的時間為O（n）。補充：1、 順序表上實現(xiàn)的基本運算：表的初始化、求表長、取表中第i個結點三

9、種運算的時間復雜度都為 O（1）。2、順序表插入操作算法分析 問題的規(guī)模表的長度L- > length （設值為n）是問題的規(guī)模。 移動結點的次數(shù)由表長 n和插入位置i決定算法的時間主要花費在for循環(huán)中的結點后移語句上。該語句的執(zhí)行次數(shù)是n-i+1。當i=n +1 :移動結點次數(shù)為 0,即算法在最好時間復雜度是 0（1）當i=1 :移動結點次數(shù)為 n,即算法在最壞情況下時間復雜度是0（n） 移動結點的平均次數(shù)Eis（n）K+l其中：在表中第i個位置插入一個結點的移動次數(shù)為n-i+1pi表示在表中第i個位置上插入一個結點的概率。不失一般性，假設在表中任何合法位置(Ki <n+1上的

10、插入結點的機會是均等的，則pi=p2 = - =pn+i=1/(n+1)因此，在等概率插入的情況下，1+1E0)弓工一 +1)恥+1)j-i即在順序表上進行插入運算，平均要移動一半結點。3、順序表刪除操作算法分析 結點的移動次數(shù)由 表長n和位置i決定：i=n時，結點的移動次數(shù)為0,即為0(1)i=1時，結點的移動次數(shù)為n-1，算法時間復雜度分別是0(n) 移動結點的平均次數(shù)Ede( n)E血龍聆F-i其中：刪除表中第i個位置結點的移動次數(shù)為n-ip表示刪除表中第i個位置上結點的概率。不失一般性，假設在表中任何合法位置(Ki n上的刪除結點的機會是均等的，貝Upi=p2= =pn=1/n因此，在

11、等概率插入的情況下，_1順序表上做刪除運算，平均要移動表中約一半的結點，平均時間復雜度也是0(n)。4、單鏈表的運算：頭插法建表、尾插法建表、尾插法建帶頭結點的單鏈表 三個算法的時間復雜度 均為0(n)。5、單鏈表的查找運算：按序號查找、按值查找其平均時間復雜度為 0(n)。6、單鏈表的插入運算：算法的時間主要耗費在查找操作GetNode上，故時間復雜度亦為0(n)。7、單鏈表的刪除運算：算法的時間復雜度也是 O (n)。8、循環(huán)鏈表：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結點an,然后將結點b1鏈到an的后面，其執(zhí)行時間是0(n)。若在尾指針表示的單循環(huán)

12、鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。9、雙向鏈表的前插和刪除本結點操作：兩個算法的時間復雜度均為O(1)。10、結點ai的存儲地址不失一般性，設線性表中所有結點的類型相同，則每個結點所占用存儲空間大小亦相同。假設 表中每個結點占用 c個存儲單元，其中第一個單元的存儲地址則是該結點的存儲地址，并設表中開始結點ai的存儲地址(簡稱為基地址)是 LOC ( ai),那么結點ai的存儲地址LOC (aj可通過下式計 算：LOC (ai) = LOC (a1) + (i-1 ) *c 1< i <n順序表鏈表基 于 空 間 考 慮分 配 方 式靜態(tài)分配。程序執(zhí)行之前必

13、須明確規(guī) 定存儲規(guī)模。若線性表長度 n變化較 大，則存儲規(guī)模難于預先確定估計過 大將造成空間浪費，估計太小又將使 空間溢出機會增多。動態(tài)分配只要內(nèi)存空間尚有空閑，就不會 產(chǎn)生溢出。因此，當線性表的長度變化較 大，難以估計其存儲規(guī)模時，以采用動態(tài) 鏈表作為存儲結構為好。存 儲 密 度為1。當線性表的長度變化不大，易 于事先確定其大小時，為了節(jié)約存儲 空間，宜米用順序表作為存儲結構。<1基 于 時 間 考 慮存 取 方 法隨機存取結構，對表中任一結點都可 在0（ 1）時間內(nèi)直接取得線性表的 操作主要是進行查找，很少做插入和 刪除操作時，采用順序表做存儲結構 為宜。順序存取結構，鏈表中的結點，

14、需從頭指 針起順著鏈掃描才能取得。插 入 刪 除 操在順序表中進行插入和刪除，平均要 移動表中近一半的結點，尤其是當每 個結點的信息量較大時，移動結點的 時間開銷就相當可觀。在鏈表中的任何位置上進行插入和刪除， 都只需要修改指針。對于頻刪除，都只需 要修改指針。對于頻刪除，都只需要修改 指針。對于頻刪除主要發(fā)生在表的首尾兩 端，則采用尾指針表示的單循環(huán)鏈表為宜三、棧和隊列1、棧與一般的線性表的區(qū)別在于（運算是否受限制）。2、一個棧的入棧序列是 abcde,則棧的不可能的輸出序列是（C ）。A、Edcba B、 decbaC、 dceabD、abcde）。3、在對棧的操作中，能改變棧的結構的是（

15、Ini tStack（S）4、順序棧的類型定義如下：typedef maxsize 64;typedef struct int datamaxsize;int top;seqstack;seqstack *s;順序棧s棧滿條件是（s->top=maxsize-1 ）。5、向一個棧頂指針為HS的鏈棧中將一個S指針所指的結點入棧，執(zhí)行（S->next=HS->next;HS=s; ）。6、若已知一個棧的入棧序列是1, 2, 3,，n,其輸出序列是 p1,p2,p3,，pn,若p1=n，則pi=（ n _i+1）。7、在棧中，可進行插入和刪除操作的一端稱（棧頂）。8、在棧的出棧操作

16、中，要先判斷棧是否空，否則會產(chǎn)生（下溢）現(xiàn)象。9、當程序中同時使用（2）個棧時，讓它們共享同一向量空間可減少上溢的發(fā)生。10、棧的特點是（后進先出）。當問題滿足（先進后出）原則時可使用 隊列作數(shù)據(jù)結構。當問題11、由于鏈棧的操作只在鏈表頭部進行，所以沒有必要設置（頭）結點。12、若內(nèi)存空間充足，（鏈）棧可不定義棧滿運算。13、一個隊列的入列序列是1 2 3 4，則隊列的輸出序列是（1 2 3 4 ）。14、隊列與一般的線性表的區(qū)別在于（運算是否受限制）。15、假上溢”現(xiàn)象會出現(xiàn)在（順序隊列）中。16、在一個鏈隊中，假設F和R分別是隊首和隊尾指針，則刪除一個結點的運算是（F=F->n ex

17、t;）。17、假設以數(shù)組sequm存放循環(huán)隊列，同時設變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含的元素個數(shù)，則判別隊滿的條件是（quele n=m）。18、為了克服 假上溢”，一般可用（循環(huán)）向量存儲隊列中的元素。19、在順序隊列中，若隊列非空，（隊頭）指針指向隊頭元素，隊尾指針指向隊尾元素的下一位置。20、循環(huán)隊列采用的是（順序）存儲結構。21、設F和R是循環(huán)隊列的隊頭指針和隊尾指針，則判斷隊空的條件是（F=R ）。22、在（隊列中只有一個元素）情況下，鏈隊列的出隊操作需要修改尾指針。23、說出解決循環(huán)隊列中，判斷隊空和隊滿情況的三種方法。答： 另設一布爾變量以區(qū)別隊列

18、的空和滿；少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認為隊滿（注意：REAR所指的單元始終為空）； 使用一個計數(shù)器記錄隊列中元素的總數(shù)（實際上是隊列長度）。24、設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用（線性表的順序存儲結構）數(shù)據(jù)結構最佳。25、在計算遞歸函數(shù)時，如不使用遞歸過程，則一般情況下必須借助于（棧）數(shù)據(jù)結構。26、計算機在運行遞歸程序時，要用到（系統(tǒng)）提供的棧。27、什么是遞歸算法？設計遞歸算法要分哪兩個步驟？答：所謂遞歸是指：若在一個函數(shù)、過程或者數(shù)據(jù)結構定義的內(nèi)部又直接（或間接）出現(xiàn)有定義本身的應用，則稱它們是遞歸的，或者是

19、遞歸定義的。遞歸算法的設計步驟第一步驟（遞歸步驟）：將規(guī)模較大的原問題分解為一個或多個規(guī)模更小、但具有類似于原問題特性的子問題，即較大的問題遞歸地用較小的子問題來描述，解原問題的方法同樣可用來解這些子問題；第二步驟：確定一個或多個無須分解、可直接求解的最小子問題（稱為遞歸的終止條件）。28、在棧結構中，允許插入、刪除的這一端為棧頂（Top ），另一端稱為棧底（Bottom ）。29、在有n個元素的棧中，進棧和退棧操作的時間復雜度為0（1）和0（1）。30、在隊列結構中，允許插入的一端稱為隊尾，允許刪除的一端稱為 隊頭。31、設長度為n的鏈隊列用單循環(huán)鏈表，若只設 頭指針，則入隊和出隊操作的時間

20、復雜度分別為O（n）和O（1）;若只設尾指針，則 入隊和出隊操作的時間復雜度分別為O（1）和O（1）。32、設循環(huán)向量有 m個元素，循環(huán)向量中有一個循環(huán)隊列。在循環(huán)隊列中，設頭指針front指向隊頭元素，隊尾指針指向隊尾元素后的一個空閑元素。（1） 在循環(huán)隊列中，隊空標志為front=rear ;隊滿標志為 front=（rear+1）%QueueSize。（2） 當 rear>=front 時，隊列長度為 rear-front ;當 rear<front;隊列長度是 rear+Queue-front ；33、設將整數(shù)1，2，3, 4依次進棧，但只要出棧時棧非空，則可將出棧操作按任

21、何次序夾入其中， 請回答下述問題：（1）若入、出棧次序為 Push（1）, Pop（）,Push（2）,Push（3）, Pop（）, Pop（ ）,Push（4）, Pop（）,則出棧的數(shù)字序 列為何（這里Push（i）表示i進棧，Pop（）表示出棧）?（2）能否得到出棧序列 1423和1432?并說明為什么不能得到或者如何得到。(3) 請分析 1，2 ，3 ，4 的 24 種排列中，哪些序列是可以通過相應的入出棧操作得到的。 答： (1)出棧序列為： 1324(2) 不 能 得 到 1423 序 列 。 因 為 要 得 到 14 的 出 棧 序 列 ， 則 應 做 Push(1),Pop(

22、),Push(2),Push (3),Push(4),Pop() 。這樣， 3在棧頂， 2 在棧底，所以不能得到 23的出棧 序列。能得到 1432 的出棧序列。 具體操作為： Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop() 。(3) 在 1，2 ， 3 ，4 的 24 種排列中，可通過相應入出棧操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：1423,2413,3124,3142,3412,4123

23、,4132,4213,4231,431234、指出下述程序段的功能是什么 ?(1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1 答：程序段的功能是將一棧中的元素按反序重新排列，也就是原來在棧頂?shù)脑胤诺綏５祝瑮５椎?元素放到棧頂。此棧中元素個數(shù)限制在 64 個以內(nèi)。(2) SeqStack S1, S2, tmp;DataType x;./假設棧 tmp 和 S2 已做過初始化while ( !

24、 StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);答：程序段的功能是利用tmp棧將一個非空棧si的所有元素按原樣復制到一個棧s2當中去。(3) void Demo2( SeqStack *S, int m) / 設 DataType 為 int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if

25、( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i); 答：程序段的功能是利用棧 T ，將一個非空棧 S 中值等于 m 的元素全部刪去。(4) void Demo3( CirQueue *Q) / 設 DataType 為 int 型 int x; SeqStack S; InitStack( &S); while (! QueueEmpty( Q ) x=DeQueue( Q); Push( &S,x); while (! StackEmpty( &s)

26、 x=Pop(&S); EnQueue( Q,x );/ Demo3答：程序段的功能是將一個循環(huán)隊列 Q 經(jīng)過 S 棧的處理，反向排列，原來的隊頭變成隊尾，原來的 隊尾變成隊頭。(5) CirQueue Q1, Q2; / 設 DataType 為 int 型 int x, i , n= 0;./設Q1已有內(nèi)容， Q2已初始化過while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+; for (i=0; i< n; i+) x=DeQueue(&Q2) ;EnQueue

27、( &Q1, x) ; EnQueue( &Q2, x);答：這段程序的功能是將隊列 1 的所有元素復制到隊列 2 中去，但其執(zhí)行過程是先把隊列 1 的 元素全部出隊，進入隊列2，然后再把隊列 2 的元素復制到隊列 1 中。補充：1 、 順序棧 的基本操作S-> dataO是棧前提條件： 設 S 是 SeqStack 類型的指針變量。若棧底位置在向量的低端，即 底元素。1 ) 進棧操作進棧時，需要將 S->top 加 1注意： S->top=StackSize-1 表示棧滿 "上溢"現(xiàn)象-當棧滿時，再做進棧運算產(chǎn)生空間溢出的現(xiàn)象。 上溢是一

28、種出錯狀態(tài)，應設法避免。(2) 退棧操作退棧時，需將 S-> top 減 1注意：S- > top<0表示空棧下溢是正?，F(xiàn)象，常用作程序下溢 ”是正?，F(xiàn)象，常用作程序真上溢 ”是一種出錯狀態(tài)，"下溢"現(xiàn)象一一當?？諘r，做退棧運算產(chǎn)生的溢出現(xiàn)象。 控制轉移的條件。2、順序隊列 中的溢出現(xiàn)象 "下溢"現(xiàn)象 當隊列為空時，做出隊運算產(chǎn)生的溢出現(xiàn)象。 控制轉移的條件。 "真上溢 "現(xiàn)象 當隊列滿時，做進棧運算產(chǎn)生空間溢出的現(xiàn)象。應設法避免。 " 假上溢 " 現(xiàn)象 由于入隊和出隊操作中，頭尾指針只增加不減小

29、，致使被刪元素的空間永遠 無法重新利用。當隊列中實際的元素個數(shù)遠遠小于向量空間的規(guī)模時，也可能由于尾指針已超越向 量空間的上界而不能做入隊操作。該現(xiàn)象稱為"假上溢 "現(xiàn)象 。為充分利用向量空間， 克服 "假上溢 "現(xiàn)象的方法是 ：將向量空間想象為一個首尾相接的圓環(huán)， 并 稱這種向量為循環(huán)向量。存儲在其中的隊列稱為循環(huán)隊列(Circular Queue )。四、串1、串是一種特殊的線性表，其特殊性體現(xiàn)在 ( 數(shù)據(jù)元素是一個字符)。2、有兩個串P和Q,求P和Q中首此出現(xiàn)的位置的運算稱(求子串)。3、設串s仁'ABCDEFG',s2='

30、PQRST',函數(shù)con(x,y)返回x和y串的連接串，subs(s,l,j)返回串s的從 序號i的字符開始的j個字符組成的子串，le n(s)返回串s的長度，則 con(subs(s1,2,len(s2),subs(s1,len(s2),2) 的結果串是 ( D )。A、 BCDEF B、 BCDEFGC、 BCPQRST D、 BCDEFEF4、在空串和空格串中，長度不為 0 的是( 空格串 )。5、在串的模式匹配中，一般 ( 有效位移的個數(shù)小于合法位移的個數(shù) )。6、在順序串中，根據(jù)空間分配方式的不同，可分為 ( 靜態(tài)分配和動態(tài)分配 )。7、按存儲結構不同，串可分為 ( 順序串和

31、鏈串 ) 。通常在程序中使用的串可分為： 串變量 和串常 量。8、在 C 語言中，以字符 ( 0)表示串值的終結。9、在鏈串中，為了提高存儲密度，應該增大 ( 結點的大小 ).10、假設每個字符占 1個字節(jié)， 若結點大小為 4 的鏈串的存儲密度為 50%，則其每個指針占 (4)個字節(jié)。11、順序串上的子串定位運算算法分析：該算法最壞情況下的時間復雜度為 O(n-m+1)m) 。分析：當目標串和模式串分別是"an-1b"和"am-1b"時，對所有n-m+1個合法的位移，均要比較m個字符才能確定該位移是否為有效位移，因此所需 比較字符的總次數(shù)為( n-m+1

32、)m。12、串(String )是零個或多個字符 組成的有限序列。一般記為S="a1a2an"。13、長度為零 的串稱為 空串 (Empty String )，它不包含任何字符。 僅由一個或多個空格 組成的串 稱為 空白串 ( Blank String )。14、子串定位運算 又稱串的模式匹配或串匹配。 在串匹配中， 一般將被匹配的主串 稱為目標(串)， 子串 稱為模式(串) 。15、樸素的串匹配算法最壞情況下需比較字符的總次數(shù)為 ( n-m+1 ) m。 n 為主串長， m 為子串長。16、串匹配就是對于合法的位置(又稱合法的位移)OW i依次將目標串中的子串"

33、titi+1tm-1"和模式串”P0p1p2pm-1"進行比較： 若"titi+1tm-1"= "P0P1P2pm-1",則稱從位置i開始的匹配成功，或稱i為有效位移。 若"titi+1ti+m-1”豐"PP1P2pm-1”，則稱從位置i開始的匹配失敗，或稱i為無效位移。因此，串匹配問題可簡化為找出某給定模式串P在給定目標串T中首次出現(xiàn)的有效位移。17、樸素模式算法在最好的情況下的運行時間是(M )(為一次內(nèi)循環(huán)為單位) 。18、設T0.n-1="adaabaabcaabaa",P0.m-1=&

34、quot;aab".當用模式串匹配目標串 T時，請給出所有的有效 位移。算法 NaiveStrMatch(T,P) 返回的位移是哪一個位移。解：所有的有效位移 i 的值為： 2， 5， 9。算法 NaveStrMatch(T,P) 的返回值是第一個有效位移， 因此是 2。19、假設有如下的串說明： char s13O="Stocktom,CA", s23O="March 5 1999", s33O, *P;(1) 在執(zhí)行如下的每個語句后P 的值是什么 ?p=stchr(s1,'t'); p=strchr(s2,'9

35、9;); p=strchr(s2,'6');答：stchr(*s,c)函數(shù)的功能是查找字符c在串s中的位置，若找到，則返回該位置，否則返回NULL。因此：執(zhí)行p=stchr(s1,'t');后p的值是指向第一個字符t的位置,也就是p=&s11。執(zhí)行p=strchr(s2,'9');后p的值是指向s2串中第一個9所在的位置 也就是p=&s29。' 執(zhí)行p=strchr(s2,'6');之后，p的返回值是 NULL。(2) 在執(zhí)行下列語句后， s3 的值是什么 ?strcpy(s3,s1); strcat(s3

36、,","); strcat(s3,s2);答： strcpy 函數(shù)功能是串拷貝， strcat 函數(shù)的功能是串聯(lián)接。所以 ：在執(zhí)行 strcpy(s3,s1);后，S3 的值是"Stocktom,CA"在執(zhí)行 strcat(s3,","); 后， s3 的值變成 "Stocktom,Ca,"在執(zhí)行完 strcat(s3,s2);后，s3 的值就成了 "Stocktom,Ca,March 5,1999"(3) 調(diào)用函數(shù)strcmp(s1,s2)的返回值是什么？答：函數(shù)strcmp(串1,串2)的功

37、能是串比較，按串的大小進行比較，返回大于0，等于0或小于0的值以表示串1比串2大，串1等于串2，串1小于串2。因此在調(diào)用函數(shù) strcmp(s1,s2)后，返 回值是大于 0 的數(shù)(字符比較是以 ascii 碼值相比的 )(4) 調(diào)用函數(shù) strcmp(&s15,"ton") 的返回值是什么 ?答：首先,我們要知道 &s15 是一個地址,當放在函數(shù) strcmp 中時,它就表示指向以它為首地址的 一個字符串，所以在 strcmp( &s15,"ton")中，前一個字符串值是 "tom,CA",用它和"

38、ton"比較，應 該是后者更大,所以返回值是小于 0的數(shù)。(5) 調(diào)用函數(shù)stlen(strcat(s1,s2)的返回值是什么？答：strlen是求串長的函數(shù)，我們先將s1,s2聯(lián)接起來，值是"Stocktom,CAMarch 5,1999",數(shù)一數(shù)有幾個字符 ?是不是 23 個(空格也是一個 )? 所以返回值是 23。五、多維數(shù)組和廣義表1、n維數(shù)組中的每個元素都最多有 (n)個直接前趨。2、 對于一個一維數(shù)組 A12，若一個數(shù)據(jù)元素占用字節(jié)數(shù)為S，首地址為1,則Ai(i>=0)的存儲 地址為(A )，若首地址為 D，貝U Ai的存儲地址為(B)。答：A-

39、(1+S*I) B-(D+S*I)3、已知二維數(shù)組 Amn 采用行優(yōu)先順序存儲,每個元素占 k 個存儲單元,并且第一個元素的存儲地址 LOC(A00 ),則 Aij 的地址是 (1+(n*i+j)*k)。4、在多維數(shù)組中,數(shù)據(jù)元素的存放地址直接可通過地址計算公式計算出。因此,數(shù)組是一種( 隨機 )存取結構。5、稀疏矩陣的一般的壓縮方法有 ( 三元組表 )。6、設矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先存放在一維數(shù)組B中。對下三角矩陣中任一元素 aij(設矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先 存放在一維數(shù)組 B 中,對下三角矩陣中任一元素 aij(i>

40、;=j) ,在一維數(shù)組 B 中下標 K 的值是 ( D)。A、 i(i-1)/2+j-1B、 i(i-1)/2+jC、 i(i+1)/2+j-1D、 i(i+1)/2+j7、在稀疏矩陣的三元組表表示法中,每個三元組表示( 矩陣中非零元素的行號、列號和值)8、對稀疏矩陣進行壓縮存儲是為了( 節(jié)約存儲空間)。9、矩陣的壓縮存儲就是為多個相同的非零元素分配(1)個存儲空間，不為零元素分配空間。10、一般，特殊矩陣按規(guī)律壓縮存儲到一個向量中后，能(隨機)存取。11、廣義表是線性表的推廣，它們之間的區(qū)別在于(能否使用子表)。12、在廣義表中，限制了表中成分遞歸，但沒有限制共享的是(再入表)。13、廣義表

41、(a),(b),c),(d)的表頭是(a )。廣義表(a),(b),c),(d)的表尾是(b),c),(d)。廣義 表(a),(b),c),(d)的深度是(4 )。廣義表(a),(b),c),(d)的長度是(3 )。14、遞歸表、再人表、純表、線性表之間的關系滿足：遞歸表二再入表二純表二線性表15、廣義表是線性表的推廣，線性表是廣義表的特例。當廣義表中的元素都是原子時，即為線性表。16、設二維數(shù)組 A5*6的每個元素占4個字節(jié)，已知Loc(a00)=1000，A共占多少個字節(jié)？ A的終端結點a45的起始地位為何？按行和按列優(yōu)先存儲時，a25的起始地址分別為何？解：(1)因含5*6=30個元素，

42、因此 A共占30*4=120個字節(jié)。(2) a45 的起始地址為：Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116(3) 按行優(yōu)先順序排列時，a25=1000+(2*6+5)*4=1068按列優(yōu)先順序排列時：(二維數(shù)組可用行列下標互換來計算)a25=1000+(5*5+2)*4=110817、求下列廣義表運算的結果：(1)head (p,h,w);(2)tail(b,k,p,h);(3) head (a,b),(c,d);(4) tail(a,b),(c,d); head(tail(a,b),(c,d);(6)tailhead)(a,b),(c,d

43、).答: (1)head (p,h,w)=p;(2)tail(b,k,p,h)=(k,p,h);(3) head (a,b),(c,d)=(a,b);(4)tail(a,b),(c,d)=(c,d); head(tail(a,b),(c,d)=(c,d);(6)tail(head(a,b),(c,d)=(b)補充：1數(shù)組元素的地址計算公式(1 )按行優(yōu)先順序存儲的二維數(shù)組Amn地址計算公式LOC(aj)=LOC(a n)+(i-1) n為-1沫其中： LOC(an)是開始結點的存放地址(即基地址) d為每個元素所占的存儲單元數(shù) 由地址計算公式可得，數(shù)組中任一元素可通過地址公式在相同時間內(nèi)存取。

44、即順序存儲的數(shù) 組是隨機存取結構。(2 )按列優(yōu)先順序存儲的二維數(shù)組Amn地址計算公式LOC(aij)=LOC(an)+(j-1) m+i-1 >d(3)按行優(yōu)先順序存儲的三維數(shù)組Amnp地址計算公式LOC(aijk)=LOC(am)+(i-1) n和+(j-1) p+k-1為(4 )下界不為1的二維數(shù)組的地址計算公式二維數(shù)組 Ac1.d1,c2.d2的地址計算公式：LOC(a ij)=LOC(a c1c2)+(i-c1)(d2-c2+1)+j-c2 d x下界為0的二維數(shù)組的地址計算公式(C語言中使用)LOC(a j)=LOC(a 00)+i (d2+1)+j d<2、對稱矩陣的

45、地址計算公式LOC(aij)=LOC(sak)=LOC(sa0)+kd=LOC(sa0)+l(I+1) /2+J xd通過下標變換公式，能立即找到矩陣元素aj在其壓縮存儲表示sa中的對應位置k。因此是隨機存取結構?！纠縎21和ai2均存儲在sa4中，這是因為k=I *1+1） /2+J=2X（2+1）/ 2+仁43、三角矩陣的壓縮存儲（三角矩陣的壓縮存儲結構是隨機存取結構。）三角矩陣中的重復元素c可共享一個存儲空間，其余的元素正好有n*n+1）/2個，因此，三角矩陣可壓縮存儲到向量sa0. n（n+1）/2中，其中c存放在向量的最后一個分量中。 上三角矩陣中aj和sak之間的對應關系i 仙-

46、i+1） / 2+j-i 當 i wjk= V-nX（n+1）/2當 i>j 下三角矩陣中aj和sak之間的對應關系i *+1）/2+j 當 i >jk= ynX（n+1）/2當 i v j十、文件1、通常，磁帶只適合用于存儲 （順序）文件。2、性質(zhì)相同的記錄的集合稱（文件）。3、文件的邏輯結構是一種（線性）結構。4、對于存儲在磁盤上的順序文件的記錄進行直接存取是根據(jù)（邏輯記錄號 ）。5、存儲在磁帶上的順序文件的查找只能用（順序查找 ）。6、 索引文件的索引表很大時，可建靜態(tài)索引，即建立索引的索引 查找表，其中最多可建（4 ） 級。7、在索引文件中，若記錄要經(jīng)常變動，則應采用（動態(tài)

47、）索引。當文件中記錄數(shù)不多時，可用二叉排序樹比較好。當文件中記錄數(shù)較多時，用B樹比較好。8、下面關于B樹和B+樹的敘述中，不正確的是 （ C ）A. B樹和B+樹都是平衡的多分樹；B. B樹和B+樹都是可用于文件的索引結構；C. B樹和B+樹都能有效地支持順序檢索; D. B樹和B+樹都能有效地支持隨機檢索。9、以下關于ISAM文件的說法中，錯誤的是 （D）。A、她的中文含義是索引順序存儲方法；B、專為磁盤存取文件設計；C、采用靜態(tài)索引結構；D、刪除記錄操作比插入記錄操作復雜。10、為什么索引順序文件是最常用的文件組織。答：因為：索引順序文件的主文件按關鍵字有序，所以適合隨機存取和順序存取。索

48、引順序文件的索引是稀疏索引，所以占空間較少。11、 對于散列文件，只能作（直接）存取。補充：1、文件分類（1）文件可以按照記錄中關鍵字的多少，分成： 單關鍵字文件：文件中的記錄只有一個惟一標識記錄的主關鍵字。 多關鍵字文件：文件中的記錄除了含有一個主關鍵字外，還含有若干個次關鍵字的文件。（2 ）文件分成 定長文件和不定長文件 由定長記錄組成的文件稱做定長文件，含有的信息長度相同的記錄稱定長記錄。 文件中記錄含有的信息長度不等，則稱其為不定長文件。2、文件上的操作主要有兩類：檢索和維護。（1） 檢索即在文件中查找滿足給定條件的記錄。它既可以按記錄的邏輯號（即記錄存入文件時的順 序編號 ）查找，也

49、可以按 關鍵字 查找。按檢索條件的不同，可將檢索分為四種詢問： 簡單詢問 ：只詢問單個關鍵字等于給定值的記錄。 范圍詢問 ：只詢問單個關鍵字屬于某個 范圍內(nèi)的所有記錄。 函數(shù)詢問 ：規(guī)定單個關鍵字的某個函數(shù)，詢問該函數(shù)的某個值。 布爾詢問 ：以上三種詢問用布爾運算 （ 與、或、非 ）組合起來的詢問。（ 2）維護 操作主要是指： 對文件進行記錄的插入、刪除及修改等更新操作。 為提高文件的效率，進行再組織操作， 文件被破壞后的恢復操作，以及文件中數(shù)據(jù)的安全保護等。（ 3） 文件操作的處理方式文件上的檢索和更新操作，都可有實時和批量兩種不同的處理方式。 實時處理 ：響應時間要求嚴格，要求在接受詢問后

50、幾秒種內(nèi)完成檢索和更新。 批量處理 ：響應時間要求寬松一些，不同的文件系統(tǒng)有不同的要求。3、文件的存儲結構 文件的存儲結構是指文件在外存上的組織方式。 文件在外存上的基本的組織方式有四種： 順序 組織，索引組織，散列組織 和 鏈組織 ；對應的的文件名稱分別為： 順序文件、索引文件、散列文件 和多關鍵字文件 。4 文件組織方式的選擇常用外存設備有： 磁帶是順序存取設備，只適用于存儲順序文件 磁盤是直接存取設備，適用于存儲順序文件、索引文件、散列文件和多關鍵 字文件等5、 評價一個文件組織的效率，是 執(zhí)行文件操作所花費的時間 和 文件組織所需的存儲空間 。通常文 件組織的主要目的，是為了能高效、方

51、便地對文件進行操作，而 檢索功能的多寡 和 速度的快慢 ， 是衡量文件操作質(zhì)量的重要標志。6、 順序文件分類（ 1） 順序有序文件： 記錄按其主關鍵字有序的順序文件為順序有序文件。（ 2） 順序無序文件： 記錄未按其主關鍵字有序排列的順序文件為順序有序文件。7、順序文件主要優(yōu)點是 連續(xù)存取的速度較快； 順序文件多用于磁帶。8、索引文件由 主文件 和 索引表 構成。9、索引順序文件和索引非順序文件（ 1）索引順序文件 （Indexed Sequential File） 主文件按主關鍵字有序的文件稱索引順序文件。 在索引順序文件中，可對一組記錄建立一個索引項。這種索引表稱為 稀疏索引 。（ 2）索

52、引非順序文件 （Indexed NonSequentail File） 主文件按主關鍵字無序得文件稱索引非順序文件。 在索引非順序文件中， 必須為每個記錄建立一個索引項， 這樣建立的索引表稱為 稠密索引 。 通常將索引非順序文件簡稱為索引文件。 索引非順序文件主文件無序， 順序存取將會頻繁地引起磁頭移動， 適合于隨機存取， 不 適合于順序存取。 索引順序文件的主文件是有序的，適合于隨機存取、順序存取。 索引順序文件的索引是稀疏索引。索引占用空間較少，是最常用的一種文件組織。 最常用的索引順序文件： ISAM 文件 和 VSAM 文件 。10、索引文件在存儲器上分為兩個區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)

53、存放索引表，數(shù)據(jù)區(qū)存放主文件。11、樹 表結構選擇： 當數(shù)據(jù)文件的記錄數(shù)不很多，內(nèi)存容量足以容納整個索引表時，可采用二叉排序樹（或AVL樹）作索引； 當文件很大時，索引表（樹表）本身也在外存，查找索引時訪問外存的次數(shù)恰為查找路徑上的結點數(shù)。采用m階B-樹（或其變型）作為索引表為宜（m的選擇取決于索引項的多少和緩沖區(qū)的大小）。12、 由于訪問外存的時間比內(nèi)存中查找的時間大得多，所以外存的索引表的查找性能主要著眼于訪 問外存的次數(shù)，即索引表的深度。13、 ISAM為Indexed Sequential Access Methed（索引順序存取方法）的縮寫，它是一種專為 磁盤存取文 件設計的文件組織

54、方式，采用靜態(tài)索引結構。ISAM文件由多級主索引、柱面索引、磁道索引和主文件組成。磁道索引中的每一個索引項，都由兩個子索引項組成：基本索引和溢出索引項。14、VSAM是Virtual Storage Access Method（虛擬存儲存取方法）的縮寫，它也是一種索引順序文件的組織方式，采用B+樹作為動態(tài)索引結構。對B+樹可進行兩種查找運算：一種是從最小關鍵字起進行順序查找；另一種是從根結點開始進行隨機查找。VSAM 文件的結構由三部分組成：索引集，順序集和數(shù)據(jù)集。和ISAM文件相比，基于B+樹的VSAM文件有如下優(yōu)點：能保持較高的查找效率，查找一個后插入記錄和查找一個原有記錄具有相同的速度；

55、動態(tài)地分配和釋放存儲空間，可以保持平均75%的存儲利用率；而且永遠不必對文件進行再組織。因而基于B+樹的VSAM文件，通常被作為大型索引順序文件的標準組織。15、散列文件是利用散列存儲方式組織的文件，亦稱直接存取文件。即根據(jù)文件中關鍵字的特點, 設計一個散列函數(shù)和處理沖突的方法，將記錄散列到存儲設備上。比較項目散列表散列文件存儲單位若干記錄為一組桶處理沖突辦法開放地址法、拉鏈法拉鏈法16、散列文件的特點：散列文件的優(yōu)點（1 ）文件隨機存放，記錄不需進行排序。（2）插入、刪除方便。（3）存取速度快；不需要索引區(qū)，節(jié)省存儲空間。散列文件的缺點（1）不能進行順序存取，只能按關鍵字隨機存取（2）詢問方

56、式限于簡單詢問（3）在經(jīng)過多次插入、刪除后，可能造成文件結構不合理，需要重新組織文件。17、 多重表文件是將索引方法和鏈接方法相結合的一種組織方式18、多關鍵字文件和其他文件的區(qū)別多關鍵字文件其他文件包含的關鍵字主關鍵字外還有多個次關鍵字只含一個主關鍵字索引建立的索引建立主關鍵字索引和多個次關 鍵字索引只有（沒有）主關鍵字索引查詢查詢對主關鍵字索引或次關鍵字索引查詢只能順序存取主文件記錄進行比較，效率低文件組織方式四種基本組織方法都可以四種組織方法都可以六、樹1、在樹中，互為堂兄弟的結點擁有相同的（祖先）。2、樹最適合用來表示（元素之間具有分支層次關系的數(shù)據(jù)）3、在樹中，度為（0 ）的結點稱為葉子。4、在樹中，除跟結點外，其他結點都有且只有一個（雙親（或前趨）結點。5、有100個結點的樹有（99）條邊。6、若將樹中的每個結點的各