《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案 (2)

1、貴州大學(xué)理學(xué)院數(shù)學(xué)系信息與計算科學(xué)專業(yè)數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案(2003-2004學(xué)年第2學(xué)期)一、 單項選擇題1對于一個算法，當(dāng)輸入非法數(shù)據(jù)時，也要能作出相應(yīng)的處理，這種要求稱為（ ）。 (A)、正確性 (B). 可行性 (C). 健壯性 (D). 輸入性2設(shè)S為C語言的語句,計算機(jī)執(zhí)行下面算法時，算法的時間復(fù)雜度為（ ）。for(i=n-1；i=0；i-) for(j=0；jnext; p-next= Q.front-next; （B）、p=Q.front-next; Q.front-next=p-next; （C）、p=Q.rear-next; p-next= Q.rear-next;

2、 （D）、p=Q-next; Q-next=p-next;9 Huffman樹的帶權(quán)路徑長度WPL等于（ ）（A）、除根結(jié)點之外的所有結(jié)點權(quán)值之和 （B）、所有結(jié)點權(quán)值之和（C）、各葉子結(jié)點的帶權(quán)路徑長度之和 （D）、根結(jié)點的值10線索二叉鏈表是利用（ ）域存儲后繼結(jié)點的地址。 （A）、lchild （B）、data （C）、rchild （D）、root二、填空題1 邏輯結(jié)構(gòu)決定了算法的 ，而存儲結(jié)構(gòu)決定了算法的 。2 棧和隊列都是一種 的線性表，棧的插入和刪除只能在 進(jìn)行。3 線性表（a1,a2,an）的順序存儲結(jié)構(gòu)中，設(shè)每個單元的長度為L，元素ai的存儲地址LOC(ai)為 4 已知一雙

3、向鏈表如下(指針域名為next和prior)： y x e q p現(xiàn)將p所指的結(jié)點插入到x和y結(jié)點之間，其操作步驟為： ； ； ； ；5n個結(jié)點無向完全圖的的邊數(shù)為 ， n個結(jié)點的生成樹的邊數(shù)為 。6已知一有向無環(huán)圖如下： BACDFEG 任意寫出二種拓?fù)渑判蛐蛄校?、 。7已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為 ，層序遍歷序列為 。三、應(yīng)用題1 設(shè)散列函數(shù)H(k)=k % 13,設(shè)關(guān)鍵字系列為22,12,24,6,45,7,8,13,21,要求用線性探測法處理沖突。(6分)(1) 構(gòu)造HASH表。(2) 分別求查找成功和不成功時的平均查找長度。2

4、給定表（19,14,22,15,20,21,56,10）.（8分）（1） 按元素在表中的次序，建立一棵二叉排序樹（2） 對(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。（3） 畫出對(2)中的遍歷序列進(jìn)行折半查找過程的判定樹。3 已知二個稀疏矩陣A和B的壓縮存儲三元組表如下： A BijVijV13-525224633725241342-152-9529558寫出A-B壓縮存儲的三元組表。（5分）4 已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）, 試寫出插入排序（升序）過程。并指出具有n個元素的插入排序的時間復(fù)雜度是多少？(5分)5 已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點A開始的

5、最小生成樹。(8分，要有過程) A B C D E F（1）求從頂點A開始的最小生成樹。（2）分別畫出以A為起點的DFS生成樹和BFS生成樹。6已知數(shù)據(jù)六個字母及在通信中出現(xiàn)頻率如下表：ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點及權(quán)值，完成如下工作(7分，要有過程)。（1） 畫出對應(yīng)的Huffman樹。（2） 計算帶權(quán)路徑長度WPL。（3） 求A、B、C、D、E、F的Huffman編碼。7 已知有如下的有向網(wǎng)： 2 5 36 4 10 6 1 2 2 AEBDC求頂點A到其它各頂點的最短路徑（采用Dijkstra算法，要有過程）。（6分）三、 設(shè)計題（30

6、分，每題10分,用C語言寫出算法，做在答題紙上）1 已知線性表（a1,a2,an）以順序存儲結(jié)構(gòu)為存儲結(jié)構(gòu)，其類型定義如下： #define LIST_INIT_SIZE 100 /順序表初始分配容量 typedef struct Elemtype *elem; /順序存儲空間基址 int length; /當(dāng)前長度（存儲元素個數(shù)） SqList;設(shè)計一個算法，刪除其元素值為x的結(jié)點（假若x是唯一的）。并求出其算法的平均時間復(fù)雜度。其算法函數(shù)頭部如下： Status ListDelete(Sqlist &L,Elemtype x) ana2a12設(shè)順序棧如左圖所示。 其中結(jié)點定義如下： top

7、 typedef struct Elemtype *base; /棧底指針Elemtype *top; /棧頂指針 Stack;設(shè)計算法，將棧頂元素出棧并存入e中 base3設(shè)二叉鏈樹的類型定義如下： typedef int Elemtype; typedef struct node Elemtype data; struct node *lchild, *rchild; BinNode, *BinTree;試寫出求該二叉樹葉子結(jié)點數(shù)的算法: Status CountLeaves(BinTree &root,int &n) /n is the number of leaves 答案：選擇題（每

8、題1分）1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、 填空題1 設(shè)計、實現(xiàn)2 特殊、棧頂3 LOC（a1）+(i-1)*L4 p-next=q-next;q-next-prior=p; q-next=p;p-prior=q;5 n(n-1)/2、n-16 ADCBFEG、ABCDEFFG7 ABC、ABC二、 應(yīng)用題1 （1）Hash表（4分）地址0123456789101112關(guān)鍵安132164572282412探測次數(shù)171231311（2）查找成功的平均查找長度：（1分） （5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找長度：

9、（1分） （2+1+9+8+7+6+5+4+3+2+1）/13=2（1）、構(gòu)造（3分） 19 14 22 10 15 20 56 21(2)、10 14 15 19 20 21 22 56（2分）（3）、（3分）3、(5分，每行0.5)ijv13-524633741342-152185584、 初始關(guān)鍵字： 18 12 25 53 18 第 一 趟：12 18 25 53 18第 二 趟：12 18 25 53 18第 三 趟：12 18 25 53 18第 四 趟：12 18 18 25 53 （4分） O（n2）（1分）。5、7分（1）4分A B 1 C 3 2 5 D 4 E F（2）4

10、分6、(1) 3分 E F A B C D （2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= (1分)（3）A：010 B：011 C：110 D：111 E：00 F；10 （3分）12、A-B：（A、B） 1分A-C：（A、D、C） 2分A-D：（A、D） 1分 A-E：（A、D、E） 2分 三，設(shè)計題（20分）1、(10分)Status ListDelete(Sqlist &L,ElemType x) int i,j; for(i=0;ilength;i+)if(L-elemi=x) break; if(i=L-length) return ER

11、ROR; for(j=i;jlengthi-1;j+) L-elemj=L-elemj+1; L-length-; （8分）平均時間復(fù)雜度：（2分）設(shè)元素個數(shù)記為n，則平均時間復(fù)雜度為：2（10分）void pop(Stack &S,Elemtype &e) if(S.top=S.base) return ERROR; S.top-; e=*s.top;2、（10分）voidCountLeaves(BinTree T,int &n)if(T)if(!(T-lchild)&!( T-rchild) n+; CountLeaves (T-lchild,n); CountLeaves (T-rchi

12、ld,n);習(xí)題1一、單項選擇題1. 數(shù)據(jù)結(jié)構(gòu)是指（ ）。A.數(shù)據(jù)元素的組織形式 B.數(shù)據(jù)類型C.數(shù)據(jù)存儲結(jié)構(gòu) D.數(shù)據(jù)定義2. 數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址不相同的，稱之為（ ）。A.存儲結(jié)構(gòu) B.邏輯結(jié)構(gòu) C.鏈?zhǔn)酱鎯Y(jié)構(gòu) D.順序存儲結(jié)構(gòu)3. 樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（ ）。A.一對一關(guān)系 B.多對多關(guān)系 C.多對一關(guān)系 D.一對多關(guān)系4. 設(shè)語句x+的時間是單位時間，則以下語句的時間復(fù)雜度為（ ）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;A.O(1) B.O( ) C.O(n) D.O( )5. 算法分析的目的是（1），算法分析

13、的兩個主要方面是（2）。（1） A.找出數(shù)據(jù)結(jié)構(gòu)的合理性 B.研究算法中的輸入和輸出關(guān)系C.分析算法的效率以求改進(jìn) D.分析算法的易懂性和文檔性（2） A.空間復(fù)雜度和時間復(fù)雜度 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性6. 計算機(jī)算法指的是（1），它具備輸入，輸出和（2）等五個特性。（1） A.計算方法 B.排序方法C.解決問題的有限運(yùn)算序列 D.調(diào)度方法（2） A.可行性，可移植性和可擴(kuò)充性 B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性 D.易讀性，穩(wěn)定性和安全性7. 數(shù)據(jù)在計算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲方式，在存儲空間使用的靈活性上，鏈?zhǔn)酱鎯Ρ软樞虼鎯σ?

14、）。A.低 B.高 C.相同 D.不好說8. 數(shù)據(jù)結(jié)構(gòu)作為一門獨立的課程出現(xiàn)是在（ ）年。A.1946 B.1953 C.1964 D.19689. 數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點（ ）。A.正確 B.錯誤C.前半句對，后半句錯 D.前半句錯，后半句對10. 計算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是（ ）。A.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)項 D.數(shù)據(jù)庫二、填空題1. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是_?_和_。2. 數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是_、_、_和_。3. 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是_的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是_的。4. 一個算法的效率可分為_效率

15、和_效率。5. 在樹型結(jié)構(gòu)中，樹根結(jié)點沒有_結(jié)點，其余每個結(jié)點的有且只有_個前趨驅(qū)結(jié)點；葉子結(jié)點沒有_結(jié)點；其余每個結(jié)點的后續(xù)結(jié)點可以_。6. 在圖型結(jié)構(gòu)中，每個結(jié)點的前趨結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以_。7. 線性結(jié)構(gòu)中元素之間存在_關(guān)系；樹型結(jié)構(gòu)中元素之間存在_關(guān)系；圖型結(jié)構(gòu)中元素之間存在_關(guān)系。8. 下面程序段的時間復(fù)雜度是_。for(i=0;in;i+)for(j=0;jn;j+)Aij=0;9. 下面程序段的時間復(fù)雜度是_。i=s=0;while(sn) i+; s+=i;10. 下面程序段的時間復(fù)雜度是_。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum

16、=s;11. 下面程序段的時間復(fù)雜度是_。i=1;while(i=n)i=i*3;12. 衡量算法正確性的標(biāo)準(zhǔn)通常是_。13. 算法時間復(fù)雜度的分析通常有兩種方法，即_和_的方法，通常我們對算法求時間復(fù)雜度時，采用后一種方法。三、求下列程序段的時間復(fù)雜度。1. x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;2. x=0;for(i=1;in;i+)for(j=1;j=n-i;j+) x+;3. int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+) cij=0;for(k=0;k=0)&Ai!=k)j-;return (i);5. fact

17、(n) if(n=1)return (1); elsereturn (n*fact(n-1);習(xí)題1參考答案一、單項選擇題1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空題1. 線性結(jié)構(gòu)，非線性結(jié)構(gòu)2. 集合，線性，樹，圖3. 一對一，一對多或多對多4. 時間，空間5. 前趨，一，后繼，多6. 有多個7. 一對一，一對多，多對多8. O( )9. O( )10. O( )11. O(log n)12. 程序?qū)τ诰脑O(shè)計的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13. 事后統(tǒng)計，事前估計三、算法設(shè)計題 1. O( ) 2. O(

18、) 3. O(n ) 4. O(n) 5. O(n) 習(xí)題2一、單項選擇題1. 線性表是_。A一個有限序列，可以為空 B一個有限序列，不可以為空C一個無限序列，可以為空 D一個無限序列，不可以為空2. 在一個長度為n的順序表中刪除第i個元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;C p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;D s-prior=p; s-next=p

19、-next; p-next-prior=s; p-next=s; 6. 設(shè)單鏈表中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指針的操作為_。Ap-next=p-next-next; Bp=p-next;Cp=p-next-next; Dp-next=p; 7. 在一個長度為n的順序表中向第i個元素(0 inext=p-next; p-next=sBq-next=s; s-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9. 以下關(guān)于線性表的說法不正確的是_。 A線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的

20、數(shù)據(jù)元素個數(shù)不是任意的。C線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。10. 線性表的順序存儲結(jié)構(gòu)是一種_的存儲結(jié)構(gòu)。 A隨機(jī)存取 B順序存取 C索引存取 D散列存取11. 在順序表中，只要知道_，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A基地址 B結(jié)點大小 C向量大小 D基地址和結(jié)點大小12. 在等概率情況下，順序表的插入操作要移動_結(jié)點。 A全部 B一半 C三分之一 D四分之一13. 在_運(yùn)算中，使用順序表比鏈表好。 A插入 B刪除 C根據(jù)序號查找 D根據(jù)元素值查找14. 在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該

21、表有序的時間復(fù)雜度是_。 AO(1) BO(n) CO(n2) DO(log2n)15. 設(shè)有一個棧，元素的進(jìn)棧次序為A, B, C, D, E,下列是不可能的出棧序列_。AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 16. 在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時，top變化為_。Atop不變 Btop=0 Ctop- Dtop+17. 向一個棧頂指針為hs的鏈棧中插入一個s結(jié)點時，應(yīng)執(zhí)行_。Ahs-next=s; Bs-next=hs; hs=s;Cs-ne

22、xt=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; 18. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為_。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front 19. 在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為_。Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front

23、20. 在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為_。Afront=front-next Brear=rear-nextCrear=front-next Dfront=rear-next二、填空題1. 線性表是一種典型的_結(jié)構(gòu)。2. 在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移_個元素。3. 順序表中邏輯上相鄰的元素的物理位置_。4. 要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_一個位置，移動過程是從_向_依次移動每一個元素。5. 在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_決定的；在線性表的鏈接存儲中，元素之間的邏

24、輯關(guān)系是通過_決定的。6. 在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向_結(jié)點，另一個指向_結(jié)點。7. 當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用_存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用_存儲結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素，物理位置_相鄰，單鏈表中邏輯上相鄰的元素，物理位置_相鄰。9. 線性表、棧和隊列都是_結(jié)構(gòu)，可以在線性表的_位置插入和刪除元素；對于棧只能在_位置插入和刪除元素；對于隊列只能在_位置插入元素和在_位置刪除元素。10. 根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_和_；而根據(jù)指針的聯(lián)接方式，鏈表又可分為

25、_和_。11. 在單鏈表中設(shè)置頭結(jié)點的作用是_。12. 對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為_，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_。 13. 對于一個棧作進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否為_，作退棧運(yùn)算時，應(yīng)先判別棧是否為_，當(dāng)棧中元素為m時，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明棧的可用最大容量為_。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的_分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_時才產(chǎn)生上溢。14. 設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push, push, pop, push, pop,

26、 push, push后，輸出序列是_。15. 無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，進(jìn)行插入或刪除運(yùn)算的時間復(fù)雜度均相同為_。三、簡答題1. 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？3. 對于線性表的兩種存儲結(jié)構(gòu)，如果有n個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭

27、指針好嗎？為什么?6. 假定有四個元素A, B, C, D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L) / L是無頭結(jié)點的單鏈表LinkList *q,*p;if(L&L-next) q=L; L=L-next; p=L;while (p-next) p=p-next; p-next=q; q-next=NULL;return (L);四、算法設(shè)計題1. 設(shè)計在無頭結(jié)點的單鏈表中刪除第i個結(jié)點的算法。2. 在單鏈表上實現(xiàn)線性表的求表長ListL

28、ength(L)運(yùn)算。3. 設(shè)計將帶表頭的鏈表逆置算法。4. 假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head，每個結(jié)點含三個域：data, next和prior。其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由next域連接起來，試編一個算法，利用prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。5. 已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。6. 已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于ma

29、x但大于min的元素的算法。7. 假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運(yùn)算的算法：（1）向循環(huán)鏈隊列插入一個元素值為x的結(jié)點；（2）從循環(huán)鏈隊列中刪除一個結(jié)點。8. 設(shè)順序表L是一個遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。習(xí)題2參考答案一、單項選擇題1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11D 12B 13C 14B 15C 16C 17B 18D 19C 20A二、填空題1線性 2n-i+1 3相鄰 4前移，前，后5物理存儲位置，鏈域的指針值 6前趨，后繼7順序，鏈接 8一定，不一定9線性

30、，任何，棧頂，隊尾，隊頭10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11使空表和非空表統(tǒng)一；算法處理一致12O(1)，O(n)13棧滿，?？?，m，棧底，兩個棧的棧頂在?？臻g的某一位置相遇142、315O(1)三、簡答題1頭指針是指向鏈表中第一個結(jié)點（即表頭結(jié)點）的指針；在表頭結(jié)點之前附設(shè)的結(jié)點稱為頭結(jié)點；表頭結(jié)點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，

31、因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。3應(yīng)選用鏈接存儲結(jié)構(gòu)，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴(kuò)充。4應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種

32、隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點和終端結(jié)點的位置分別是rear-next-next 和 rear, 查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n)。6共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為fro

33、nt，隊尾指針為rear，隊列的容量（即存儲的空間大小）為maxnum。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，但元素卻不能入隊，一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。 一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個

34、位置，假定空余空間足夠。 第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列中的元素總是使front指針指向隊列中的第一個位置。 第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運(yùn)算時仍遵循“先進(jìn)先出”的原則。8該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。四、算法設(shè)計題 1算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)in-1時，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時，刪除第一個結(jié)點：（3）當(dāng)in時，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點時，須用指針記住該

35、結(jié)點的前趨結(jié)點。算法描述如下：delete(LinkList *q,int i) /在無頭結(jié)點的單鏈表中刪除第i個結(jié)點 LinkList *p,*s; int j; if(inext; free(s); else j=0; s=q; while(jnext;j+;if (s= =NULL) printf(Cantt delete); else p-next=s-next; free(s); 2由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法描述如下：int ListLength ( LinkList *L ) /求帶頭結(jié)點的單鏈表的表長 int len=0;

36、ListList *p; p=L; while ( p-next!=NULL ) p=p-next;len+; return (len);3設(shè)單循環(huán)鏈表的頭指針為head，類型為LinkList。逆置時需將每一個結(jié)點的指針域作以修改，使其原前趨結(jié)點成為后繼。如要更改q結(jié)點的指針域時，設(shè)s指向其原前趨結(jié)點，p指向其原后繼結(jié)點，則只需進(jìn)行q-next=s;操作即可，算法描述如下：void invert(LinkList *head) /逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s; q=head; p=head-next; while (p!=head) /當(dāng)表不為空時

37、，逐個結(jié)點逆置 s=q; q=p; p=p-next; q-next=s; p-next=q; 4定義類型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點鏈入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q; p=head-next; /p指向待插入的結(jié)點，初始時指向第一個結(jié)點 while(p!=NULL) s=head; / s指向q結(jié)點的前趨結(jié)點 q=head-prior; /q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點 while(q!=NULL) & (p-dataq-data) /查找插入結(jié)點p的合適的插入位置 s=q; q=q-prior; s-prior=p; p-prior=q; /結(jié)點p插入到結(jié)點s和結(jié)點q之間 p=p-next;5算法描述如下：delete(LinkList *head,