西南石油數(shù)據(jù)結(jié)構(gòu)習題集答案

1、數(shù)據(jù)結(jié)構(gòu)習題集楊先鳳 朱小梅編西南石油大學(xué)計算機科學(xué)學(xué)院二零零七年九月習題一緒論 1習題二線性表 5習題三棧和隊列 10習題四串 14習題五數(shù)組和廣義表 17習題六樹和二叉樹 21習題七圖 27習題八查找 32習題九排序 36習題十文件 40緒論一、單項選擇題1.數(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)系2在數(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)3數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中

2、的表示是指() 。A.數(shù)據(jù)的存儲結(jié)構(gòu)B 數(shù)據(jù)結(jié)構(gòu)C 數(shù)據(jù)的邏輯結(jié)構(gòu)D 數(shù)據(jù)元素之間的關(guān)系4在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的()結(jié)構(gòu)。A.邏輯 B .存儲 c .邏緝和存儲D .物理5 .算法分析的目的是()，算法分析的兩個主要方面是()。 A 找出數(shù)據(jù)結(jié)構(gòu)的合理性B 研究算法中的輸入和輸出的關(guān)系C 分折算治的效率以求改進D 分析算法的易讀性和文檔性 A 空間復(fù)雜度和時間復(fù)雜度B 正確性和簡明性C 可讀性和文檔性D 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲() 。A 數(shù)據(jù)的處理方法B 數(shù)據(jù)元素的類型C 數(shù)據(jù)元素之間的關(guān)系D 數(shù)據(jù)的存儲方法7.

3、算法的計算量的大小稱為計算的() 。A.效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度8. 算法的時間復(fù)雜度取決于()A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)C. A 和B9. 下面說法錯誤的是()(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)10. 在下面的程序段中，對x 的賦值語句的頻度為()for (i=1;i=n;i+)for (j

4、=1;j=n;j+) x:=x+1;2AO(2n) B O(n) C O(n2)D O(log 2n)二、判斷題(在各題后填寫或“X”)1 . 線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。()2 . 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( )3 . 記錄是數(shù)據(jù)處理的最小單位。( )4 .算法就是程序。()5 .數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系；()6 .數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。()7 .在順序存儲結(jié)構(gòu)中，有時也存儲數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。()8 .順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。()9 .線性表若采用鏈式存儲結(jié)構(gòu)時，要求

5、內(nèi)存中可用存儲單元的地址一定是不連續(xù)的。()10 .數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的順序關(guān)系，它依賴于計算機的儲存結(jié)構(gòu).()三、填空題1 .數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的 _ 和 ,以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的 ,設(shè)計出相應(yīng)的 。2 .對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有 , _ 四種。3 .在線性結(jié)構(gòu)中，第一個結(jié)點 前驅(qū)結(jié)點，其余每個結(jié)點有且僅有 個 前驅(qū)結(jié)點；最后一個結(jié)點 后續(xù)結(jié)點，其余每個結(jié)點有且僅有 個后4 .在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 結(jié)點，其余每個結(jié)點有且只有 個前驅(qū)結(jié)點；葉子結(jié)點沒有 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以 。5 . 一個數(shù)據(jù)結(jié)構(gòu)在計算機中 稱為存儲結(jié)構(gòu)

6、。四種關(guān)聯(lián)6 .通常，存儲結(jié)點之間可以有 方式，稱為四種基本存儲方式。7 .抽象數(shù)據(jù)類型的定義僅取決于它的一組 ,而與 無關(guān)，即 不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的 不變，都不影響其外部使用。8 .數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是 9 . 一個算法具有 5個特性：、,有零個 或多個輸入、有一個或多個輸出。10 .常見時間復(fù)雜性的量級有：常數(shù)階 0()、對數(shù)階0()、線性階 0 ()、平方階 0()、和指數(shù)階 0()。通常認為，具有 指數(shù)階量級的算法是 ,而量級低于平方階的算法是 的。11 .計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 。for (i=l ; i=i;j-)s；12 .設(shè)m.n均

7、為自然數(shù)，m可表示為一些不超過n的自然數(shù)之和，f(m,n)為這種表示方式的數(shù)目。例 f(5,3)=5 ,有 5 種表示方式：3+2, 3+1 + 1, 2+2+1, 2+1+1 + 1, 1 + 1 + 1+1+1。 以下是該函數(shù)的程序段，請將未完成的部分填入，使之完整int f(m,n) int m,n; if(m=1) return (1)_;if(n=1) return (2);if(mn) return f(m,m); if (m=n) return 1+ (3)Q return f(m.n-1)+f(m-n, (4) ) 執(zhí)行程序，f(6,4)= 。13 .程序段i=1;while(

8、i=n)i=i*2;的時間復(fù)雜度 T(n)= 。四、應(yīng)用題1.有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對應(yīng)的邏輯圖形表示，并指出它 們分別屬于何種結(jié)構(gòu)。(1) A= (K, R),其中： K=a,b,c,d,e,f,g,h R=r r=, (2) B= (K, R),其中：K=a,b,c,d,e,f,g,h R=r r=, (3) C= (K, R),其中：K=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6) 這里的圓括號對表示兩結(jié)點是雙向的。2 .若有100個學(xué)生，每個學(xué)生有學(xué)號，姓名，平均成績，采用什么

9、樣的數(shù)據(jù)結(jié)構(gòu)最4方便,寫出這些結(jié)構(gòu)？3 .調(diào)用下列函數(shù)f(n),回答下列問題： (1)試指出f(n)值的大小，并寫出f(n)值的推導(dǎo)過程； (2)假定n= 5 ,試指出f(5)值的大小和執(zhí)行f(5)時的輸出結(jié)果 。C 函數(shù)：int f(int n) int i,j, k,sum= 0;for(i=l; ii-1; j-)for(k=1;kj+1;k+ )sum+;printf(sum=%dn,sum)； return (sum);4.設(shè)計求解下列問題的類C語言算法，并分析其最壞情況時間復(fù)雜度。 1) 在數(shù)組A1.n中查找值為K的元素，若找到則輸出其位置i(1=i0) 。A.表元素 B .字符

10、C .數(shù)據(jù)元素D .數(shù)據(jù)項 E .信息項4. 以下說法錯誤的是( )A.對于線性表來說，定位運算LocateElem在順序表和單鏈表上的時間復(fù)雜度均為On)B.讀表元運算在順序表上只需常數(shù)時間0(1)便可實現(xiàn)，因此順序表是一種隨機存取結(jié)構(gòu)C.在鏈表上實現(xiàn)讀表元運算的平均時間復(fù)雜度為0 (1)D.插入、刪除操作在鏈表上的實現(xiàn)可在0 (1)時間內(nèi)完成E.插入、刪除操作在順序表上的實現(xiàn)，平均時間復(fù)雜度為 0 (n)5. 若某線性表中最常用的操作是取第i 個元素和找第i 個元素的前趨元素，則采用() 存儲方式最節(jié)省時間。A.順序表 B .單鏈表 C .雙鏈表 D .單循環(huán)鏈表6設(shè)一個鏈表最常用的操作是

11、在末尾插入結(jié)點和刪除尾結(jié)點，則選用( ) 最節(jié)省時間。A. 單鏈表B. 單循環(huán)鏈表C. 帶尾指針的單循環(huán)鏈表D. 帶頭結(jié)點的雙循環(huán)鏈表7. 靜態(tài)鏈表中指針表示的是() .A內(nèi)存地址B 數(shù)組下標C 下一元素地址D 左、右孩子地址8. 鏈表不具有的特點是()A.插入、刪除不需要移動元素B .可隨機訪問任一元素C.不必事先估計存儲空間D .所需空間與線性長度成正比rear )后，其頭結(jié)點和尾結(jié)點的存儲位置分別9在循環(huán)鏈表中，將頭指針改設(shè)為尾指針（是（）A rear 和 rear-next-nextB rear-next 和 rearC rear-next-next 和 rearD rear 和 re

12、ar-next10 . 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為() 。A 0(n) 0(n) B. 0(n) 0(1) C. 0(1) 0(n) D. 0(1) 0(1)11 .線性表(a1,a2,an)以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為()A 0( i ) B 0( 1) C 0( n) D 0( i-1 )12 在單鏈表指針為p 的結(jié)點之后插入指針為s 的結(jié)點，正確的操作是：() 。A. p-next=s;s-next=p-next;B. s-next=p-next;p-next=s;C. p-next=s;p-next=s-next;D. p-next

13、=s-next;p-next=s;13 .對于一個頭指針為 head的帶頭結(jié)點的單鏈表，判定該表為空表的條件是（）A. head=NULLB. head next=NULLC. headfnext=headD. head!=NULL二、判斷題（在各題后填寫或“x”）1 .鏈表中的頭結(jié)點僅起到標識的作用。（）2 .線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（）3 .順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（）4 .對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。（）5 .所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。（）6 .線性表的特點是每個元素都有一個前驅(qū)和一

14、個后繼。（）7 .循環(huán)鏈表不是線性表.（）8 .線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。（）9 .線性表就是順序存儲的表。（）10 .鏈表是采用鏈式存儲結(jié)構(gòu)的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。（） 三、填空題1 .在順序表中，邏輯上相鄰的元素，其物理位置 相鄰。在單鏈表中，邏輯上相 鄰的元素，其物理位置 相鄰。2 .在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由 指示，首元素結(jié)點的 存儲位置由 指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置 由 指示。3 .在單鏈表中若在每個結(jié)點中增加一個指針域，所含指針指向前驅(qū)結(jié)點，這樣構(gòu)成的鏈表中有兩個方向不同的鏈，稱為 。4 .對于順

15、序表的插入算法insert_sqlist 來說，若以結(jié)點移動為標準操作，則插入算法的在最壞情況下的移動次數(shù)為 ,時間復(fù)雜度是。在平均情況下的移動次數(shù) 為,時間復(fù)雜度是。5 .線性表的常見鏈式存儲結(jié)構(gòu)有 、和。6 .單鏈表表示法的基本思想是用 表示結(jié)點間的邏輯關(guān)系。7 .線性表L= （a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一 個元素平均需要移動元素的個數(shù)是 。8 .設(shè)單鏈表的結(jié)點結(jié)構(gòu)為（data,next） , next為指針域，已知指針 px指向單鏈表中data 為x的結(jié)點，指針py指向data為y的新結(jié)點，若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行 以下語句：; ;9

16、 .對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 個，單鏈表為 個。10 .以下為順序表的定位運算，分析算法，請在 處填上正確的語句。 int locate_sqlist(sqlist L,datatype X)/*在順序表L中查找第一值等于 X的結(jié)點。若找到回傳該結(jié)點序號；否則回傳0*/；while(i & L.last)&(L.datai-1!=X)i+; if()return(i);else return(0); 11 .對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結(jié)點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋帲瓿善涔δ堋ypedef struct node in

17、t data; struct node *next; linknode,*link;void Insertsort(link L) link p,q,r,u;p=L-next; while(2) r=L; q=L-next; while(3)& q-datadata) r=q; q=q-next; u=p-next; (4)_; (5); p=u; 12 .下面是一個求兩個集合A和B之差C=A-B的程序，即當且僅當 e是A的一個元素，但不是B中的一個元素時，e才是C中的一個元素。集合用有序鏈表實現(xiàn)，初始時，A, B集合中的元素按遞增排列，C為空；操作完成后 A, B保持不變，C中元素按遞增排列

18、。下面的函數(shù)append(last,e) 是把值為e的新結(jié)點鏈接在由指針 last指向的結(jié)點的后面，并返 回新結(jié)點的地址；函數(shù)difference(A,B)實現(xiàn)集合運算A-B,并返回表示結(jié)果集合 C的鏈表的首結(jié)點的地址。在執(zhí)行A-B運算之前，用于表示結(jié)果集合的鏈表首先增加一個附加的表頭結(jié)點，以便新結(jié)點的添加，當 A-B運算執(zhí)行完畢，再刪除并釋放表示結(jié)果集合的鏈表的 表頭結(jié)點。typedef struct node int element; struct node *link; NODE;NODE *A , *B, *C;NODE *append (NODE *last,int e) last-

19、link=(NODE*) malloc (sizeof(NODE);last-link-element=e; return(last-link);NODE *difference(NODE *A,NODE *B)NODE *C,*last;C=last=(NODE*) malloc (sizeof(NODE);while (1)_ if (A-elementelement) last=append(last,A-element); A=A-link; else if (2) A=A-link; B=B-link; ELSE (3)while (4)_ last=append(last,A-el

20、ement); A=A-link; (5)_ 二 last=C; C=C-link; free (last); return (C);/*call form:C=difference(A,B);*/四、應(yīng)用題1 .試述頭結(jié)點，首元結(jié)點，頭指針這三個概念的區(qū)別.參考答案：在線性表的鏈式存儲結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義(當然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等)，有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和 刪除第一結(jié)點，其操作與對

21、其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不 為空。首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。2 .在單鏈表和雙向鏈表中，能否從當前結(jié)點出發(fā)訪問到任何一個結(jié)點？參考答案：在單鏈表中不能從當前結(jié)點(若當前結(jié)點不是第一結(jié)點)出發(fā)訪問到任何一個 結(jié)點，鏈表只能從頭指針開始，訪問到鏈表中每個結(jié)點。在雙鏈表中求前驅(qū)和后繼都容易, 從當前結(jié)點向前到第一結(jié)點，向后到最后結(jié)點，可以訪問到任何一個結(jié)點。3 . 一線性表存儲在帶頭結(jié)點的雙向循環(huán)鏈表中，L為頭指針。如下算法：(1)說明該算法的功能。(2)在空缺處填寫相應(yīng)的語句。void unknown (BNODETP *L)p=L-nex

22、t; q=p-next; r=q-next ;while (q!=L) while (p!=L) & (p-dataq-data) p=p-prior;q-prior-next=r ; (1) ;q-next=p-next ; q-prior=p ;(2); (3); q=r ; p=q-prior ;(4);參考答案：1)本算法功能是將雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)域按值自小到大排序，成為非遞 減(可能包括數(shù)據(jù)域值相等的結(jié)點)有序雙向循環(huán)鏈表。2) (1)r-prior=q- prior; /將q結(jié)點摘下，以便插入到適當位置。(2)p-next-prior=q; / (2) (3)將 q 結(jié)點插入(

23、3)p-next=q;(4)r=r-next; 或r=q-next; /后移指針，再將新結(jié)點插入到適當位置。五、算法設(shè)計題1 .設(shè)線性表存于 A1.size 的前num各分量中，且遞增有序。t#設(shè)計一個算法，將 x插入到線性表的適當位置上，以保持線性表的有序性，并在設(shè)計前說明設(shè)計思想，最后說明所設(shè)計算法的時間復(fù)雜度。2試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一個實現(xiàn)線性表的就地( 即使用盡可能少的附 加 空 間 ) 逆 置 的 算 法 ， 在 原 表 的 存 儲 空 間 內(nèi) 將 線 性 表 (a1 ， a2,. .,an) 逆 置 為(a n ,. .,a2,a 1 ) 。3試編寫在無頭結(jié)點的單

24、鏈表上實現(xiàn)線性表基本運算LOCATE(L,X)、 INSERT(L,X， i) 和DELETE(L,i) 的算法，并和在帶頭結(jié)點的單鏈表上實現(xiàn)相的算法進行比較。4 . 將線性表 A=(a1,a2,am), B=(b1,b2,bn) 合并成線性表 C, C=(a1,b1, am,bm,bm+1；.bn) 當 mn時，線性表A B C以單鏈表作為存儲結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點空間構(gòu)成。注意：單鏈表的長度值m和n均未顯式存儲。5 . 已知長度為n 的線性表A 采用順序存儲結(jié)構(gòu)，請寫一時間復(fù)雜度為0(n) 、空間復(fù)雜度為 0(1) 的算法，該算法刪除線性表中所有值為item 的數(shù)據(jù)元素。( O

25、( 1 )表示算法的輔助空間為常量)。6假設(shè)在長度大于1 的循環(huán)鏈表中，既無頭結(jié)點也無頭指針。s 為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點*s 的前趨結(jié)點。7已知一單鏈表中的數(shù)據(jù)元素含有三個字符(即 : 字母字符、數(shù)字字符和其它字符)。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類的字符，且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間( 頭結(jié)點可另辟空間) 。8約瑟夫環(huán)問題約瑟夫問題的一種描述為： 編號1,2,n的n個人按順時針方向圍坐一圈， 每個人持 有一個密碼(正整數(shù))。一開始任選一個報數(shù)上限值 m,從第一個人開始順時針自 1開始順 序報數(shù)，報到 m時停止報數(shù)。報 m的人出列

26、，將他的密碼作為新的 m值，從他在順時針方向上的下一個人開始重新從1 報數(shù)，如此下去，直至所有的人全部出列為止。試設(shè)計一個程序，求出出列順序。利用單向循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程，按照出列順序打印出各人的編號。例如 m 的初值為20； n=7， 7 個人的密碼依次是：3,1,7,2,4,8,4, 出列順序為6,1,4,7,2,3,5。棧和隊列單項選擇題1. 在作 進棧運 算時 , 應(yīng)先 判別 棧是 否 （ ）, 在 作退 棧運算 時應(yīng) 先判 別棧 是否（ ） 。當棧中元素為n 個 , 作進棧運算時發(fā)生上溢, 則說明該棧的最大容量為（） 。 , : A. 空 B. 滿 C. 上溢D. 下溢 :

27、 A. n-1 B. n C. n+1 D. n/22. 若已知一個棧的進棧序列是1, 2, 3,，n,其輸出序列為pl, p2, p3,，pn,若p1 = 3,則 p2為（）。A 可能是 2 B 一定是 2 C 可能是 1 D 一定是 13. 有六個元素6， 5， 4， 3， 2， 1 的順序進棧，問下列哪一個不是合法的出棧序列？（）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 64. 設(shè)有一順序棧S,元素S1,S 2,s 3,s 4,s 5,s 6依次進棧，如果6個元素出棧的順序是 S2,S 3,s 4,s6 , s 5

28、,s 1, 則棧的容量至少應(yīng)該是（）A.2 B. 3C. 5D.65. 若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1.m ， topi 代表第 i 個棧 （ i =1,2）棧頂，棧1 的底在 v1 ，棧 2 的底在 Vm ，則棧滿的條件是() 。A. |top2-top1|=0 B. top1+1=top2C. top1+top2=m D. top1=top26. 執(zhí)行完下列語句段后，i 值為：()int f(int x) return (x0) ? x* f(x-1):2); int i ;i =f(f(1);A 2 B. 4 C. 87.表達式 3* 2A(4+2*2-6*3)-5 中人為

29、乘哥。A. 3,2,4,1,1； (*A(+*-C. 3,2,4,2,2； (*A(-D.求值過程中當掃描到無限遞歸6 時，對象棧和算符棧為（） ，其8. 用鏈接方式存儲的隊列，在進行刪除運算時（A. 僅修改頭指針B.B. 3,2,8D. 3,2,8；（*A-；（*八（-）。僅修改尾指針C. 頭、尾指針都要修改D. 頭、尾指針可能都要修改9. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A.隊列 B .多維數(shù)組 C .棧 D.線性表10. 設(shè)C語言數(shù)組Datam+1作為循環(huán)隊列 SQ的存儲空間，front 為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為（）A.

30、front=front+1B. front=（ front+1 ） % mC.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1)11. 循環(huán)隊列的隊滿條件為( )A. (sq.rear+1) % maxsize =(sq.front+1) % maxsize;B. (sq.front+1) % maxsize =sq.rearC. (sq.rear+1) % maxsize =sq.frontD.sq.rear =sq.front12. 棧和隊列的共同點是() 。A. 都是先進先出B.都是先進后出C. 只允許在端點處插入和刪除元素D. 沒有共同點二、填空題

31、1. 棧是 的線性表，其運算遵循的原則。2. 一個棧的輸入序列是：1 ， 2， 3 則不可能的棧輸出序列是。3. 用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234,為了得到1342出棧順序，相應(yīng)的S和X的操作串為 。4. 循環(huán)隊列的引入，目的是為了克服。5. 隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是。6. 已知鏈隊列的頭尾指針分別是f 和 r ，則將值x 入隊的操作序列是。7表達式求值是應(yīng)用的一個典型例子。8循環(huán)隊列用數(shù)組A0.m-1 存放其元素值，已知其頭尾指針分別是front 和 rear ，則當前隊列的元素個數(shù)是。9 . 以下運算實現(xiàn)在鏈棧上的初

32、始化，請在處用請適當句子予以填充。Void InitStacl(LstackTp *ls) ;10 .以下運算實現(xiàn)在鏈棧上的進棧，請在處用請適當句子予以填充。Void Push ( LStackTp *ls,DataType x ) LstackTp *p;p=malloc(sizeof(LstackTp);p-next=ls;處用請適當句子予以填充。11以下運算實現(xiàn)在鏈棧上的退棧，請在Int Pop(LstackTp *ls,DataType *x) LstackTp *p;if(ls!=NULL) p=ls;*x=;ls=ls-next;else return(0);12. 以下運算實現(xiàn)在

33、鏈隊上的入隊列，請在處用適當句子予以填充。Void EnQueue(QueptrTp *lq,DataType x) LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp);=x;p-next=NULL;(lq-rear)-next=; 三、應(yīng)用題1 給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別棧空與棧滿？2 .畫出對算術(shù)表達式 A-B*C/D-E T F求值時操作數(shù)棧和運算符棧的變化過程。3 . 將兩個棧存入數(shù)組V1.m 應(yīng)如何安排最好？這時?？?、棧滿的條件是什么？4 . 怎樣判定循環(huán)隊列的空和滿？四、算法設(shè)計題1 借助棧( 可用棧

34、的基本運算) 來實現(xiàn)單鏈表的逆置運算。2 . 設(shè)表達式以字符形式已存入數(shù)組En 中， #為表達式的結(jié)束符，試寫出判斷表達式中括號(和)是否配對的C語言描述算法：EXYX(E);(注：算法中可調(diào)用棧操作 的基本算法。)3 .假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。( 1)下面所示的序列中哪些是合法的？A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO( 2)通過對(1 )的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回 tru

35、e ，否則返回false (假定被判定的操作序列已存入一維數(shù)組中)。4 .設(shè)有兩個棧Si,S2都采用順序棧方式，并且共享一個存儲區(qū)O.maxsize-1, 為了盡量利 用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設(shè)計Si,S2有關(guān)入棧和出棧的操作算法。5 . 請利用兩個棧S1 和 S2 來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST,x): 元素x入ST棧；POP(ST,x) ： ST棧頂元素出棧，賦給變量x; Sempty(ST):判ST棧是否為空。那么如何利用棧的運算來實現(xiàn)該隊列的三個運算：enqueue: 插入一個元素入隊列；dequeue:刪除一個元素出隊列

36、；queue_empty:判隊列為空。(請寫明算法的思想及必要的注釋)6 要求循環(huán)隊列不損失一個空間全部都能得到利用，設(shè)置一個標志tag, 以 tag 為 0 或 1來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此相應(yīng)的入隊與出隊算法。7 .已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數(shù)和少量工作變量，編寫一個算法，將隊列 Q中的所有元素逆置。棧的 ADT函數(shù)有：makeEmpty(s:stack);push(s:stack;value:datatype);pop(s:stack):datatype; isEmpty(s:stack):Boolean;隊列的 ADT 函數(shù)有：e

37、nqueue(q:queue:value:datatype);deQueue(q:queue):datatype;isEmpty(q:queue):boolean;置空棧新元素 value 進棧出棧，返回棧頂值判棧空否元素 value 進隊出隊列，返回隊頭值判隊列空否42習題四串一、單項選擇題1 .下面關(guān)于串的的敘述中，哪一個是不正確的？（）A.串是字符的有限序列B .空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運算D .串既可以采用順序存儲，也可以采用鏈式存儲2 .串是一種特殊的線性表，其特殊性體現(xiàn)在（）。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符3

38、.串的長度是指（）A.串中所含不同字母的個數(shù)B .串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D .串中所含非空格字符的個數(shù)4 .設(shè)有兩個串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）A.求子串 B .聯(lián)接 C .匹配 D .求串長5 .若串S= software ”，其子串的個數(shù)是（）。A. 8 B . 37 C . 36 D .9二、填空題1 .含零個字符的串稱為 串。任何串中所含 的個數(shù)稱為該串的長度。2 .空格串是指 ,其長度等于 。3 .當且僅當兩個串的 相等并且各個對應(yīng)位置上的字符都 時，這兩個串相等。一個串中任意個連續(xù)字符組成的序列稱為該串的 串，該串稱為它所

39、有子串的 串。4 . INDEX (DATASTRUCTU R ESTR) =。5 .模式串P= abaabcac的next函數(shù)值序列為 。6 .下列程序判斷字符串s是否對稱，對稱則返回1,否則返回0;如f(abba) 返回1,f(abab)返回 0;int f(1)int i=0,j=0;while (sj)(2) ;for(j-; ij & si=sj; i+,j-); return(3)7 .下列算法實現(xiàn)求采用順序結(jié)構(gòu)存儲的串s和串t的一個最長公共子串。void maxcomstr(orderstring *s,*t; int index, length)int i,j,k,length

40、1,con;index=0;length=0;i=1;while (i=s.len) j=1；while(jlength) index=i; length=length1; _； else (4) ; (5) 三、應(yīng)用題1 .描述以下概念的區(qū)別：空格串與空串。2 .設(shè)有A=，B=mule , C=old , D=my,試計算下列運算的結(jié)果 (注:A+B是CONCAT(A,B)的簡寫，A=的含有兩個空格)。 (a) A+B (b) B+A (c) D+C+B(d) SUBSTR(B,3,2)(e) SUBSTR(C,1,0)(f) LENGTH(A)(g) LENGTH(D)(h) INDEX(

41、B,D)(i) INDEX(C,d)(j) INSERT(D,2,C)(k) INSERT(B,1,A)(l) DELETE(B,2,2) (m) DELETE(B,2,0)3 .設(shè)主串S= xxyxxxyxxxxyxyx 模式串T= xxyxy 。請問：如何用最少的比較次數(shù)找 到T在S中出現(xiàn)的位置？相應(yīng)的比較次數(shù)是多少？4 .給出字符串a(chǎn)bacabaaad在KMPB法中的next和nextval數(shù)組。5 .已知：s = (xyz) +*，t = (x + z) *y。試利用聯(lián)結(jié)、求子串和置換等基本運 算，將s轉(zhuǎn)化為t 。四、算法設(shè)計題1 在順序串上實現(xiàn)串的判等運算EQUAL（S,T）。2在鏈

42、串上實現(xiàn)判等運算EQUAL（S,T）。3若S 和 T 是用結(jié)點大小為1 的單鏈表存儲的兩個串（S、 T 為頭指針），設(shè)計一個算法將串 S 中首次與串T 匹配的子串逆值。4.以順序存儲結(jié)構(gòu)表示串，設(shè)計算法。求串S中出現(xiàn)的第一個最長重復(fù)子串及其位置并分析算法的時間復(fù)雜度。（如果字符串的一個子串（其長度大于1）的各個字符均相同，則稱之為等值子串。如果輸入字符串S,以“！ ”作為結(jié)束標志。串 S中不存在等值子串，則輸出信息“無等值子串”，否則求出（輸出）一個長度最大的等值子串。例如：若S=“ abc123abc123! ”，則輸出“無等值子串”；若S=“ abceebccadddddaaadd! ”，

43、則輸出“ ddddd”。 ）5寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設(shè)串存儲空間。習題五數(shù)組和廣義表一、單項選擇題1 .常對數(shù)組進行的兩種基本操作是（）A.建立與刪除B. 索引與修改 C.查找與修改D.查找與索引2 .對于C語言的二維數(shù)組DataType Amn,每個數(shù)據(jù)元素占 K個存儲單元，二維數(shù)組中任意元素ai,j的存儲位置可由（）式確定.A.Loci,j=Am,n+（n+1）*i+j*kB.Loci,j=loc0,0+（m+n）*i+j*kC.Loci,j=loc0,0+（n+1）*i+j*kD.Loci,j=（n+1）*i+j*k3 .稀疏矩陣的壓縮存儲方法是只存儲（）A.非零元

44、素B. 三元祖（i,j, aij ） C. aij D. i,j4 .數(shù)組A0.5,0.6的每個元素占五個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素 A5, 5的地址是（）。A. 1175 B. 1180 C. 1205 D.12105 . AN, N是對稱矩陣，將下面三角（包括對角線）以行序存儲到一維數(shù)組TN （N+1） /2A. i (i-1 ) /2+j B. j中，則對任一上三角元素aij 對應(yīng)Tk的下標卜是（）。(j-1 ) /2+i C. i (j-i ) /2+1 D. j (i-1 ) /2+1A. j=rj.next B. j=j+16 .用數(shù)組r存儲

45、靜態(tài)鏈表，結(jié)點的 next域指向后繼，工作指針j指向鏈中結(jié)點，使j沿 鏈移動的操作為（）。C. j=j-next D. j=rj- next7 .對稀疏矩陣進行壓縮存儲目的是（.便于輸入和輸出降低運算的時間復(fù)雜度運用head和tail函數(shù)取出LS中原子e的運算是A.便于進行矩陣運算BC.節(jié)省存儲空間D8 .已知廣義表 LS= (a,b,c),(d,e,f),A. head(tail(LS)B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)9.廣義表（a,b,c,d ）的表頭是 （）,表尾是（）。10.A.

46、a B.（）C.（a,b,c,d設(shè)廣義表L= （a,b,c ）,則L的長度和深度分別為（D. (b,c,d )A. 1 和 1 B. 1 和 3 C. 111.下面說法不正確的是（）。A.廣義表的表頭總是一個廣義表B.和2 D. 2 和3廣義表的表尾總是一個廣義表C.廣義表難以用順序存儲結(jié)構(gòu)D.廣義表可以是一個多層次的結(jié)構(gòu)二、填空題1 .通常采用 存儲結(jié)構(gòu)來存放數(shù)組。對二維數(shù)組可有兩種存儲方法：一種是以為主序的存儲方式，另一種是以 為主序的存儲方式。2 .用一維數(shù)組B與列優(yōu)先存放帶狀矩陣 A中的非零元素Ai,j （1 i n,i-2 j i+2）,B中的第8個元素是A中的第 行,第 列的元素。

47、3 .設(shè)n行n列的下三角矩陣 A已壓縮到一維數(shù)組B1.n*(n+1) /2中，若按行為主序存儲，則Ai,j對應(yīng)的B中存儲位置為4 .所謂稀疏矩陣指的是 。5 .廣義表簡稱表，是由零個或多個原子或子表組成的有限序列，原子與表的差別僅在于 。為了區(qū)分原子和表，一般用.表示表，用 一表示原子。一個表的長度是指 ,而表的深度是指 6 .設(shè)廣義表 L=(),(), 則 head(L)是; tail(L) 是L的長度是 ;深度是 。7 .基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下運算按照矩陣 A的列序來進行轉(zhuǎn)置，請在 處用適當?shù)木渥佑靡蕴畛?。Trans_Sparmat(SpMatrixTp a,SpM

48、atrixTp *b) (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) q=i;for(col=1;col+) for(p=1;ptag=0; q-val.data=p-val.data; else (2) if (3)t=reverse(p-val.ptr.tp); s=t;while(s-val.ptr.tp!=NULL) s=s-val.ptr.tp;s-val.ptr.tp=(glist)malloc(sizeof(gnode);s=s-val.ptr.tp;s-tag=1;s-val.ptr.tp=NULL;s-val.ptr.hp=h; (4)_else q=(glist)malloc(sizeof(gnode);q-tag=1;q-val.ptr.tp=NULL; (5)_j_ return(q); 三、應(yīng)用題1 .數(shù)組A1.8 , -2.6 , 0.6以行為主序存儲，設(shè)第一個元素的首地址是78,每個元素的長度為4,試求元素A4,2,3的存儲首地址。2 .特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機存取的功能？為什么?3 .數(shù)組，廣義表與線性表之間有什么樣的關(guān)系？4 .