第一篇：數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案總結(jié)
第一章
第1章作業(yè)：1.1,1.2,1.6(1)(3)1.8 1.1 簡述下列概念：數(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ù)：指能夠被計(jì)算機(jī)識別、存儲和加工處理的信息載體。
● 數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可以由若干數(shù)據(jù)項(xiàng)組成。
● 數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。通常數(shù)據(jù)類型可以看作是程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。
● 數(shù)據(jù)結(jié)構(gòu)：指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。
● 邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。
● 存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結(jié)構(gòu).● 線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。● 非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。
1.2 試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子、敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運(yùn)算三個(gè)方面的內(nèi)容。
答：例如有一張學(xué)生體檢情況登記表，記錄了一個(gè)班的學(xué)生的身高、體重等各項(xiàng)體檢信息。這張登記表中，每個(gè)學(xué)生的各項(xiàng)體檢信息排在一行上。這個(gè)表就是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)記錄(有姓名，學(xué)號，身高和體重等字段)就是一個(gè)結(jié)點(diǎn)，對于整個(gè)表來說，只有一個(gè)開始結(jié)點(diǎn)(它的前面無記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼(它的前面和后面均有且只有一個(gè)記錄)。這幾個(gè)關(guān)系就確定了這個(gè)表的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)。
這個(gè)表中的數(shù)據(jù)如何存儲到計(jì)算機(jī)里，并且如何表示數(shù)據(jù)元素之間的關(guān)系呢? 即用一片連續(xù)的內(nèi)存單元來存放這些記錄(如用數(shù)組表示)還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢? 這就是存儲結(jié)構(gòu)的問題。
在這個(gè)表的某種存儲結(jié)構(gòu)基礎(chǔ)上，可實(shí)現(xiàn)對這張表中的記錄進(jìn)行查詢，修改，刪除等操作。對這個(gè)表可以進(jìn)行哪些操作以及如何實(shí)現(xiàn)這些操作就是數(shù)據(jù)的運(yùn)算問題了。
1.6 設(shè)n為正整數(shù)，利用大“O”記號，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。
(1)i=1;k=0;while(i
通過分析以上程序段，可將i+j看成一個(gè)控制循環(huán)次數(shù)的變量，且每執(zhí)行一次循環(huán)，i+j的值加1。該程序段的主要時(shí)間消耗是while循環(huán)，而while循環(huán)共做了n次，所以該程序段的執(zhí)行時(shí)間為：
T(n)=O(n)
1.8 按增長率由小至大的順序排列下列各函數(shù)：2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)
答：常見的時(shí)間復(fù)雜度按數(shù)量級遞增排列,依次為:常數(shù)階0(1)、對數(shù)階0(log2n)、線性階0(n)、線性對數(shù)階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數(shù)階0(2n)。先將題中的函數(shù)分成如下幾類：
常數(shù)階：2 對數(shù)階：lgn K次方階：n、n0.5(3/2)100
指數(shù)階(按指數(shù)由小到大排)：nlgn、(3/2)n、2n、n!、nn
注意：(2/3)^n由于底數(shù)小于1，所以是一個(gè)遞減函數(shù)，其數(shù)量級應(yīng)小于常數(shù)階。
根據(jù)以上分析按增長率由小至大的順序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn
第二章
第二章作業(yè)：2.2，2.6,2.9,2.13 2.2 何時(shí)選用順序表、何時(shí)選用鏈表作為線性表的存儲結(jié)構(gòu)為宜? 答：在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體問題的要求和性質(zhì)來選擇順序表或鏈表作為線性表的存儲結(jié)構(gòu)，通常有以下幾方面的考慮： 1.基于空間的考慮。當(dāng)要求存儲的線性表長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲空間，宜采用順序表；反之，當(dāng)線性表長度變化大，難以估計(jì)其存儲規(guī)模時(shí)，采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。
2.基于時(shí)間的考慮。若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲結(jié)構(gòu)為宜；反之，若需要對線性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲結(jié)構(gòu)。并且，若鏈表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜。2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是無頭結(jié)點(diǎn)單鏈表 ListNode *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;}// Demo 答：該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。
2.7 設(shè)線性表的n個(gè)結(jié)點(diǎn)定義為(a0,a1,...an-1)，重寫順序表上實(shí)現(xiàn)的插入和刪除算法：InsertList 和DeleteList.解：算法如下: #define ListSize 100 // 假定表空間大小為100 typedef int DataType;//假定DataType的類型為int型 typedef struct{ DataType data[ListSize];// 向量data用于存放表結(jié)點(diǎn) int length;// 當(dāng)前的表長度 } Seqlist;//以上為定義表結(jié)構(gòu)
void InsertList(Seqlist *L, Datatype x, int i){ //將新結(jié)點(diǎn)x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)ai的位置上，即插入的合法位置為：0<=i<=L->length int j;if(i < 0 || i > L-> length)Error(“position error”);// 非法位置，退出，if(L->length>=ListSize)Error(“overflow“);
for(j=L->length-1;j >= i;j--)L->data[ j+1]=L->data [ j ];L->data[ i ]=x;L->length++;} 2.9 設(shè)順序表L是一個(gè)遞增有序表，試寫一算法，將x插入L中，并使L仍是一個(gè)有序表。
答：因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開始向前尋找到第一個(gè)小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后，所以可邊尋找，邊后移元素，當(dāng)找到第一個(gè)小于或等于x的元素位置i時(shí)，該位置也空出來了。
算法如下：
//順序表存儲結(jié)構(gòu)如題2.7 void InsertIncreaseList(Seqlist *L , Datatype x){ int i;if(L->length>=ListSize)Error(“overflow”);
for(i=L-> length;i>0 && L->data[ i-1 ] > x;i--)L->data[ i ]=L->data[ i ];// 比較并移動元素 L->data[ i ] =x;L-> length++;} 2.13 設(shè) A和B是兩個(gè)單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個(gè)按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)，請分析算法的時(shí)間復(fù)雜度。
解：根據(jù)已知條件，A和B是兩個(gè)遞增有序表，所以可以先取A表的表頭建立空的C表。然后同時(shí)掃描A表和B表，將兩表中最大的結(jié)點(diǎn)從對應(yīng)表中摘下，并作為開始結(jié)點(diǎn)插入C表中。如此反復(fù)，直到A表或B表為空。最后將不為空的A表或B表中的結(jié)點(diǎn)依次摘下并作為開始結(jié)點(diǎn)插入C表中。這時(shí)，得到的C表就是由A表和B表歸并成的一個(gè)按元素值遞減有序的單鏈表C。并且輔助空間為O(1)。
算法如下：
LinkList MergeSort(LinkList A , LinkList B){// 歸并兩個(gè)帶頭結(jié)點(diǎn)的遞增有序表為一個(gè)帶頭結(jié)點(diǎn)遞減有序表 ListNode *pa , *pb , *q , *C;pa=A->next;//pa指向A表開始結(jié)點(diǎn)
C=A;C->next=NULL;//取A表的表頭建立空的C表 pb=B->next;//pb指向B表開始結(jié)點(diǎn) free(B);//回收B表的頭結(jié)點(diǎn)空間 while(pa && pb){ if(pb->data <= pa->data){ // 當(dāng)B中的元素小于等于A中當(dāng)前元素時(shí)，將pa表的開始結(jié)點(diǎn)摘下 q=pa;pa=pa->next;} else {// 當(dāng)B中的元素大于A中當(dāng)前元素時(shí)，將pb表的開始結(jié)點(diǎn)摘下 q=pb;pb=pb->next;} q->next=C->next;C->next=q;//將摘下的結(jié)點(diǎn)q作為開始結(jié)點(diǎn)插入C表 } //若pa表非空，則處理pa表 while(pa){ q=pa;pa=pa->next;q->next=C->next;C->next=q;} //若pb表非空，則處理pb表 while(pb){ q=pb;pa=pb->next;q->next=C->next;C->next=q;} return(C);} 該算法的時(shí)間復(fù)雜度分析如下：
算法中有三個(gè)while 循環(huán)，其中第二個(gè)和第三個(gè)循環(huán)只執(zhí)行一個(gè)。每個(gè)循環(huán)做的工作都是對鏈表中結(jié)點(diǎn)掃描處理。整個(gè)算法完成后，A表和B表中的每個(gè)結(jié)點(diǎn)都被處理了一遍。所以若A表和B表的表長分別是m和n，則該算法的時(shí)間復(fù)雜度O(m+n)
●練習(xí)2.1：寫出在線性表中的查找運(yùn)算算法。
即查找數(shù)據(jù)元素x在表中的位置，也就是數(shù)據(jù)元素下標(biāo)值加1。
例如：若L.data[i]=x,則返回i+1;若不存在，則返回n+1 練習(xí)2.2：編寫尾插法建立鏈表的算法。
練習(xí)2.3：若是帶頭指針的單鏈表，算法又是怎樣？
若是兩個(gè)鏈表，既知道頭結(jié)點(diǎn)，又知道尾結(jié)點(diǎn)，算法又是怎樣？
●練習(xí)2：按升序打印帶頭結(jié)點(diǎn)h的單鏈表中各節(jié)點(diǎn)的數(shù)據(jù)域值，并將打印完的節(jié)點(diǎn)從表中刪除。
第三章
第三章作業(yè)：3.2, 3.3，3.4（2），3.6，3.11 3.2 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿? 答：循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的“假上溢”現(xiàn)象，能夠使存儲隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的“空”或“滿”不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是另設(shè)一布爾變量來區(qū)別隊(duì)列的空和滿。二是少用一個(gè)元素的空間,每次入隊(duì)前測試入隊(duì)后頭尾指針是否會重合，如果會重合就認(rèn)為隊(duì)列已滿。三是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。
3.3設(shè)長度為n的鏈隊(duì)用單循環(huán)鏈表表示，若設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間為何? 若只設(shè)尾指針呢? 答：當(dāng)只設(shè)頭指針時(shí)，出隊(duì)的時(shí)間為1，而入隊(duì)的時(shí)間需要n，因?yàn)槊看稳腙?duì)均需從頭指針開始查找，找到最后一個(gè)元素時(shí)方可進(jìn)行入隊(duì)操作。若只設(shè)尾指針，則出入隊(duì)時(shí)間均為1。因?yàn)槭茄h(huán)鏈表，尾指針?biāo)傅南乱粋€(gè)元素就是頭指針?biāo)冈?，所以出?duì)時(shí)不需要遍歷整個(gè)隊(duì)列。3.4 指出下述程序段的功能是什么?(2)SeqStack S1, S2, tmp;
DataType x;
...//假設(shè)棧tmp和S2已做過初始化
while(!StackEmpty(&S1))
{
x=Pop(&S1);
Push(&tmp,x);
}
while(!StackEmpty(&tmp))
{
x=Pop(&tmp);
Push(&S1,x);
Push(&S2, x);
}(2)程序段的功能是利用tmp棧將一個(gè)非空棧s1的所有元素按原樣復(fù)制到一個(gè)棧s2當(dāng)中去。
3.6 利用棧的基本操作，寫一個(gè)將棧S中所有結(jié)點(diǎn)均刪去的算法void ClearStack(SeqStack *S)，并說明S為何要作為指針參數(shù)
解：算法如下
void ClearStack(SeqStack *S)
{ // 刪除棧中所有結(jié)點(diǎn)
S->Top =-1;//其實(shí)只是將棧置空
}
因?yàn)橐每盏氖菞，如果不用指針來做參數(shù)傳遞，那么函數(shù)進(jìn)行的操作不能對原來的棧產(chǎn)生影響，系統(tǒng)將會在內(nèi)存中開辟另外的單元來對形參進(jìn)行函數(shù)操作。結(jié)果等于什么也沒有做。所以想要把函數(shù)操作的結(jié)果返回給實(shí)參的話，就只能用指針來做參數(shù)傳遞了。
3.8 設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號是否正確配對。(提示： 對表達(dá)式進(jìn)行掃描，凡遇到‘(’就進(jìn)棧，遇‘)’就退掉棧頂?shù)摹?’，表達(dá)式被掃描完畢，棧應(yīng)為空。解：
根據(jù)提示，可以設(shè)計(jì)算法如下：
int PairBracket(char *SR)
{//檢查表達(dá)式SR中括號是否配對
int i;
SeqStack S;//定義一個(gè)棧
InitStack(&s);
for(i=0;i { if(SR[i]==‘(’)Push(&S, SR[i]);//遇‘(’時(shí)進(jìn)棧 if(SR[i]==‘)’)//遇‘)’ if(!StackEmpty(S))//棧不為空時(shí)，將棧頂元素出棧 Pop(&s); else return 0;//不匹配，返回0 } if（EmptyStack(&s)）return 1;// 匹配，返回1 else return 0;//不匹配，返回0 } 6.12 若二叉樹中各結(jié)點(diǎn)的值均不相同，則由二叉樹的前序序列和中序序列，或由其后序序列和中序序列均能唯一地確定一棵二叉樹，但由前序序列和后序序列卻不一定能唯一地確定一棵二叉樹。 (1)已知一棵二叉樹的前序序列和中序序列分別為ABDGHCEFI和GDHBAECIF，請畫出此二叉樹。(2)已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請畫出此二叉樹。(3)已知一棵二叉樹的前序序列和后序序列分別為AB和BA，請畫出這兩棵不同的二叉樹。解： (1)已知二叉樹的前序序列為ABDGHCEFI和中序序列GDHBAECIF，則可以根據(jù)前序序列找到根結(jié)點(diǎn)為A，由此，通過中序序列可知它的兩棵子樹包分別含有GDHB和ECIF結(jié)點(diǎn)，又由前序序列可知B和C分別為兩棵子樹的根結(jié)點(diǎn)...以此類推可畫出所有結(jié)點(diǎn)： ○A / ○B(yǎng) ○C / / ○D ○E○F / / ○G ○H ○I (2)以同樣的方法可畫出該二叉樹： ○A / ○B(yǎng) ○F ○C ○G / ○D ○E ○H (3)這兩棵不同的二叉樹為： ○A ○A / ○B(yǎng) ○B(yǎng) 6.21 以二叉鏈表為存儲結(jié)構(gòu)，寫一算法交換各結(jié)點(diǎn)的左右子樹。 答：要交換各結(jié)點(diǎn)的左右子樹，最方便的辦法是用后序遍歷算法，每訪問一個(gè)結(jié)點(diǎn)時(shí)把兩棵子樹的指針進(jìn)行交換，最后一次訪問是交換根結(jié)點(diǎn)的子樹。 void ChangeBinTree(BinTree *T) { //交換子樹 if(*T) { //這里以指針為參數(shù)使得交換在實(shí)參的結(jié)點(diǎn)上進(jìn)行后序遍歷 BinTree temp; ChangeBinTree(&(*T)->lchild); ChangeBinTree(&(*T)->rchild); temp=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=temp; } } 9.11試寫出二分查找的遞歸算法。解： int BinSearch(SeqList R，KeyType K，int low，int high) { //在有序表R[low..high]中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回零 int mid； //置當(dāng)前查找區(qū)間上、下界的初值 if(low<=high){ //當(dāng)前查找區(qū)間R[low..high]非空 mid=(low+high)/2； if(R[mid].key==K)return mid； //查找成功返回 if(R[mid].key>K) return BinSearch(R，K,low，mid-1)//在R[low..mid-1]中查找 else return BinSearch(R，K,mid+1，high)； //在R[mid+1..high]中查找 } return 0； //當(dāng)low>high時(shí)表示查找區(qū)間為空，查找失敗 } //BinSeareh 10.7.將哨兵放在R[n]中，被排序的記錄放在R[0..n-1]中，重寫直接插入排序算法。解： 重寫的算法如下： void InsertSort(SeqList R) {//對順序表中記錄R[0..n-1]按遞增序進(jìn)行插入排序 int i,j; for(i=n-2;i>=0;i--)//在有序區(qū)中依次插入R[n-2]..R[0] if(R[i].key>R[i+1].key)//若不是這樣則R[i]原位不動 { R[n]=R[i];j=i+1;//R[n]是哨兵 do{ //從左向右在有序區(qū)中查找插入位置 R[j-1]=R[j];//將關(guān)鍵字小于R[i].key的記錄向右移 j++; }while(R[j].key R[j-1]=R[n];//將R[i]插入到正確位置上 }//endif }//InsertSort.12.1 常見的文件組織方式有哪幾種?各有何特點(diǎn)? 文件上的操作有哪幾種? 如何評價(jià)文件組織的效率? 答： 常用的文件組織方式有：順序文件、索引文件、散列文件和多關(guān)鍵字文件。 ●順序文件的特點(diǎn)是，它是按記錄進(jìn)入文件的先后順序存放，其邏輯結(jié)構(gòu)和物理順序是一致的。 ●索引文件的特點(diǎn)是，在主文件之外還另外建立了一張表，由這張表來指明邏輯記錄和物理記錄之間的一一對應(yīng)關(guān)系。索引文件在存儲器上分為兩個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)，前者存放索引表，后者存放主文件。●散列文件是利用散列存儲方式組織的，它類似于散列表，即根據(jù)文件中關(guān)鍵字的特點(diǎn)，設(shè)計(jì)一個(gè)散列函數(shù)和處理沖突的方法，將記錄散列到存儲設(shè)備上，對于散列文件，磁盤上的文件記錄通常是成組存放的。 ●多關(guān)鍵字文件則包含有多個(gè)次關(guān)鍵索引的，不同于前述幾種文件，只含有一個(gè)主關(guān)鍵字。 文件的操作有兩種：檢索和維護(hù)。 評價(jià)一個(gè)文件組織的效率，是執(zhí)行文件操作(如查找、刪除等)所花費(fèi)的時(shí)間和文件組織所需的存儲空間。 第一章 緒論 一、選擇題 1.組成數(shù)據(jù)的基本單位是（） （A）數(shù)據(jù)項(xiàng)（B）數(shù)據(jù)類型（C）數(shù)據(jù)元素（D）數(shù)據(jù)變量 2.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（）以及它們之間的相互關(guān)系。 （A）理想結(jié)構(gòu)，物理結(jié)構(gòu)（B）理想結(jié)構(gòu)，抽象結(jié)構(gòu) （C）物理結(jié)構(gòu)，邏輯結(jié)構(gòu)（D）抽象結(jié)構(gòu)，邏輯結(jié)構(gòu) 3.在數(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) 4.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的（①）以及它們之間的（②）和運(yùn)算等的學(xué)科。 ①（A）數(shù)據(jù)元素（B）計(jì)算方法（C）邏輯存儲（D）數(shù)據(jù)映像 ②（A）結(jié)構(gòu)（B）關(guān)系（C）運(yùn)算（D）算法 5.算法分析的目的是（）。 （A）找出數(shù)據(jù)結(jié)構(gòu)的合理性（B）研究算法中的輸入和輸出的關(guān)系 （C）分析算法的效率以求改進(jìn)（D）分析算法的易懂性和文檔性 6.計(jì)算機(jī)算法指的是（①）,它必須具備輸入、輸出和（②）等5個(gè)特性。 ①（A）計(jì)算方法（B）排序方法（C）解決問題的有限運(yùn)算序列（D）調(diào)度方法 ②（A）可執(zhí)行性、可移植性和可擴(kuò)充性（B）可行性、確定性和有窮性 （C）確定性、有窮性和穩(wěn)定性（D）易讀性、穩(wěn)定性和安全性 二、判斷題 1.數(shù)據(jù)的機(jī)內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。（） 2.算法就是程序。（） 3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（） 4.算法的五個(gè)特性為：有窮性、輸入、輸出、完成性和確定性。（） 5.算法的時(shí)間復(fù)雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（） 三、填空題 1.數(shù)據(jù)邏輯結(jié)構(gòu)包括________、________、_________ 和_________四種類型,其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_____。 2.在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)____前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有______個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)______后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)后續(xù)結(jié)點(diǎn)。 3.在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有_______結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有________結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以_________。 4.在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以_________。 5.線性結(jié)構(gòu)中元素之間存在________關(guān)系,樹形結(jié)構(gòu)中元素之間存在______關(guān)系,圖形結(jié)構(gòu)中元素之間存在_______關(guān)系。 6.算法的五個(gè)重要特性是_______、_______、______、_______、_______。 7.數(shù)據(jù)結(jié)構(gòu)的三要素是指______、_______和________。 8.鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比較,主要優(yōu)點(diǎn)是________________________________。 9.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結(jié)構(gòu)宜用_________結(jié)構(gòu),為了方便插入一個(gè)元素,數(shù)據(jù)結(jié)構(gòu)宜用____________結(jié)構(gòu)。 四、算法分析題 1.求下列算法段的語句頻度及時(shí)間復(fù)雜度 參考答案： 一、選擇題 1.C 2.C 3.C 4.A、B 5.C 6.C、B 二、判斷題: 1、√ 2、× 3、× 4、× 5、√ 三、填空題 1、線性、樹形、圖形、集合? ；非線性（網(wǎng)狀） 2、沒有；1；沒有；1 3、前驅(qū)；1；后繼；任意多個(gè) 4、任意多個(gè) 5、一對一；一對多；多對多 6、有窮性；確定性；可行性；輸入；輸出 7、數(shù)據(jù)元素；邏輯結(jié)構(gòu)；存儲結(jié)構(gòu) 8、插入、刪除、合并等操作較方便 9、順序存儲；鏈?zhǔn)酱鎯?/p> 四、算法分析題 for(i=1;i<=n;i++)for(j =1;j <=i;j++)x=x+1;分析：該算法為一個(gè)二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因些，時(shí)間頻度T(n)=1+2+3+…+n=n*(n+1)/2 有 1/4≤T(n)/n2≤1，故它的時(shí)間復(fù)雜度為Ｏ(n2), 即Ｔ(n)與n2 數(shù)量級相同。 2、分析下列算法段的時(shí)間頻度及時(shí)間復(fù)雜度 for（i=1;i<=n;i++） for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=i+j-k; 分析算法規(guī)律可知時(shí)間頻度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)由于有1/6 ≤ T（n）/ n3 ≤1，故時(shí)間復(fù)雜度為Ｏ(n3) 第二章 線性表 一、選擇題 1.一個(gè)線性表第一個(gè)元素的存儲地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是()（A）110（B）108（C）100（D）120 2.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動（）個(gè)元素。 （A）64（B）63（C）63.5（D）7 3.線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，其地址（）。 (A)必須是連續(xù)的(B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的(D)連續(xù)與否均可以 4.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（） （A）s->next=p;p->next=s;（B）s->next=p->next;p->next=s;（C）s->next=p->next;p=s;（D）p->next=s;s->next=p;5.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（） （A）p->next=p->next->next;（B）p=p->next;p->next=p->next->next;（C）p->next=p->next;（D）p =p->next->next;6.下列有關(guān)線性表的敘述中，正確的是（） （A）線性表中的元素之間隔是線性關(guān)系 （B）線性表中至少有一個(gè)元素 （C）線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨 （D）線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼 7.線性表是具有n個(gè)（）的有限序列（n≠0) （A）表元素（B）字符（C）數(shù)據(jù)元素 （D）數(shù)據(jù)項(xiàng) 二、判斷題 1.線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。（） 2.如果沒有提供指針類型的語言，就無法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)。（） 3.線性結(jié)構(gòu)的特點(diǎn)是只有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，只有一個(gè)結(jié)點(diǎn)沒有后繼，其余的結(jié)點(diǎn)只有一個(gè)前驅(qū)和后繼。（） 4.語句p=p->next完成了指針賦值并使p指針得到了p指針?biāo)负罄^結(jié)點(diǎn)的數(shù)據(jù)域值。（） 5.要想刪除p指針的后繼結(jié)點(diǎn)，我們應(yīng)該執(zhí)行q=p->next ； p->next=q->next； free(q)。（） 三、填空題 1.已知P為單鏈表中的非首尾結(jié)點(diǎn)，在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句為：_______________________。 2.順序表中邏輯上相鄰的元素物理位置()相鄰，單鏈表中邏輯上相鄰的元素物理位置_________相鄰。 3.線性表L＝（a1，a2，...，an）采用順序存儲，假定在不同的n＋1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動的元素個(gè)數(shù)是________________________ 4.在非空雙向循環(huán)鏈表中，在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過程如下： p->prior=q->prior;q->prior->next=p;p->next=q;______________________; 5.已知L是無表頭結(jié)點(diǎn)的單鏈表，是從下列提供的答案中選擇合適的語句序列，分別實(shí)現(xiàn)： （1）表尾插入s結(jié)點(diǎn)的語句序列是_______________________________(2)表尾插入 s結(jié)點(diǎn)的語句序列是_______________________________ 1.p->next=s;2.p=L;3.L=s; 4.p->next=s->next; 5.s->next=p->next;6.s->next=L;7.s->next=null; 8.while(p->next!= Q)? p=p-next;9.while(p->next!=null)p=p->next; 四、算法設(shè)計(jì)題 1.試編寫一個(gè)求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整型）。 2.已知帶有頭結(jié)點(diǎn)的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值為x的所有結(jié)點(diǎn)的c函數(shù)。 3.某百貨公司倉庫中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域?，F(xiàn)出庫（銷售）m臺價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。 4.某百貨公司倉庫中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域?，F(xiàn)新到m臺價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。 5.線性表中的元素值按遞增有序排列，針對順序表和循環(huán)鏈表兩種不同的存儲方式，分別編寫C函數(shù)刪除線性表中值介于a與b（a≤b）之間的元素。 6.設(shè)A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是兩個(gè)給定的線性表,它們的結(jié)點(diǎn)個(gè)數(shù)分別是n和m,且結(jié)點(diǎn)值均是整數(shù)。 若n=m，且 ai= bi（0≤i 若n 若存在一個(gè)j，j 試編寫一個(gè)比較A和B的C函數(shù)，該函數(shù)返回-1或 0或 1，分別表示 A 7.試編寫算法,刪除雙向循環(huán)鏈表中第k個(gè)結(jié)點(diǎn)。 8.線性表由前后兩部分性質(zhì)不同的元素組成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n為兩部分元素的個(gè)數(shù),若線性表分別采用數(shù)組和鏈表兩種方式存儲,編寫算法將兩部分元素?fù)Q位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析兩種存儲方式下算法的時(shí)間和空間復(fù)雜度。 9.用循環(huán)鏈表作線性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存儲結(jié)構(gòu),頭指針分別為ah和bh，設(shè)計(jì)C函數(shù)，把兩個(gè)線性表合并成形如（a0,b0,a1,b1,…）的線性表，要求不開辟新的動態(tài)空間,利用原來循環(huán)鏈表的結(jié)點(diǎn)完成合并操作,結(jié)構(gòu)仍為循環(huán)鏈表,頭指針為head,并分析算法的時(shí)間復(fù)雜度。 10.試寫出將一個(gè)線性表分解為兩個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，并將兩個(gè)循環(huán)鏈表的長度放在各自的頭結(jié)點(diǎn)的數(shù)據(jù)域中的C函數(shù)。其中,線性表中序號為偶數(shù)的元素分解到第一個(gè)循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個(gè)循環(huán)鏈表中。 11.試寫出把線性鏈表改為循環(huán)鏈表的C函數(shù)。 12.己知非空線性鏈表中x結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)為y,試寫出刪除x結(jié)點(diǎn)的C函數(shù)。 參考答案： 一、選擇題 1.B 2.C 3.D 4.B 5.A 6.A 7、C 二、判斷題: 參考答案： 1、× 2、√ 3、× 4、× 5、√ 三、填空題 1、s->next=p->next;p->next=s; 2、一定；不一定 3、n/2 4、q->prior=p; 5、(1)6)3)(2)2)9）1)7) 四、算法設(shè)計(jì)題 1、#include “stdio.h” #include “malloc.h” typedef struct node {int data;struct node *link;}NODE;int aver(NODE *head){int i=0,sum=0,ave;NODE *p;p=head;while(p!=NULL){p=p->link;++i; sum=sum+p->data;} ave=sum/i;return(ave);} 2、#include “stdio.h” #include “malloc.h” typedef struct node { int data;/* 假設(shè)數(shù)據(jù)域?yàn)檎?*/ struct node *link;}NODE;void del_link(NODE *head,int x)/* 刪除數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)*/ { NODE *p,*q,*s;p=head;q=head->link;while(q!=head){if(q->data==x){p->link=q->link;s=q;q=q->link;free(s);} else { p=q;q=q->link;} } } 3、void del(NODE *head,float price,int num){ NODE *p,*q,*s;p=head;q=head->next;while(q->price next;} if(q->price==price)q->num=q->num-num;else printf(“無此產(chǎn)品”);if(q->num==0){ p->next=q->next;free(q);} } 4、#include “stdio.h” #include “malloc.h” typedef struct node { float price;int num;struct node *next;}NODE;void ins(NODE *head,float price,int num) { NODE *p,*q,*s;p=head;q=head->next;while(q->price next;} if(q->price==price)q->num=q->num+num;else { s=(NODE *)malloc(sizeof(NODE));s->price=price;s->num=num;s->next=p->next;p->next=s;} } 5、順序表： 算法思想：從0開始掃描線性表，用k記錄下元素值在a與b之間的元素個(gè)數(shù)，對于不滿足該條件的元素，前移k個(gè)位置，最后修改線性表的長度。 void del（elemtype list[]，int *n，elemtype a，elemtype b） { int i=0，k=0； while（i i++;} *n=*n-k;/* 修改線性表的長度*/ } 循環(huán)鏈表: void del(NODE *head,elemtype a,elemtype b){ NODE *p,*q;p= head;q=p->link;/* 假設(shè)循環(huán)鏈表帶有頭結(jié)點(diǎn) */ while(q!=head && q->data 6、#define MAXSIZE 100 int listA[MAXSIZE],listB[MAXSIZE];int n,m;int compare(int a[],int b[]){ int i=0; while(a[i]==b[i]&&i 7、void del(DUNODE **head,int i){ DUNODE *p;if(i==0){ *head=*head->next;*head->prior=NULL;return(0);} Else {for(j=0;j void convert(elemtype list[],int l,int h)/* 將數(shù)組中第l個(gè)到第h個(gè)元素逆置*/ { int i;elemtype temp;for(i=h;i<=(l+h)/2;i++){ temp=list[i];list[i]=list[l+h-i];list[l+h-i]=temp;} } void exchange(elemtype list[],int n,int m);{ convert(list,0,n+m-1);convert(list,0,m-1);convert(list,m,n+m-1);} 該算法的時(shí)間復(fù)雜度為O(n+m),空間復(fù)雜度為O(1)鏈接存儲:(不帶頭結(jié)點(diǎn)的單鏈表)typedef struct node { elemtype data;struct node *link;}NODE;void convert(NODE **head,int n,int m){ NODE *p,*q,*r;int i;p=*head;q=*head;for(i=0;i q=q->link;/*q指向an-1結(jié)點(diǎn) */ r=q->link;q->link=NULL;while(r->link!=NULL)r=r->link;/*r指向最后一個(gè)bm-1結(jié)點(diǎn) */ *head=q;r->link=p;} 該算法的時(shí)間復(fù)雜度為O(n+m),但比順序存儲節(jié)省時(shí)間(不需要移動元素,只需改變指針),空間復(fù)雜度為O(1)9.typedef struct node { elemtype data;struct node *link;}NODE;NODE *union(NODE *ah,NODE *bh){ NODE *a,*b,*head,*r,*q;head=ah;a=ah;b=bh;while(a->link!=ah&&b->link!=bh){ r=a->link;q=b->link;a->link=b;b->link=r;a=r;b=q;} if(a->link==ah)/*a的結(jié)點(diǎn)個(gè)數(shù)小于等于b的結(jié)點(diǎn)個(gè)數(shù) */ { a->link=b;while(b->link!=bh)b=b->link;b->link=head;} if(b->link==bh)/*b的結(jié)點(diǎn)個(gè)數(shù)小于a的結(jié)點(diǎn)個(gè)數(shù) */ { r=a->link;a->link=b;b->link=r;} return(head);} 該算法的時(shí)間復(fù)雜度為O(n+m),其中n和m為兩個(gè)循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù).10.typedef struct node { elemtype data;struct node *link;}NODE;void analyze(NODE *a） { NODE *rh，*qh，*r,*q,*p； int i=0，j=0；/*i為序號是奇數(shù)的結(jié)點(diǎn)個(gè)數(shù) j為序號是偶數(shù)的結(jié)點(diǎn)個(gè)數(shù) */ p=a； rh=（NODE *）malloc（sizeof（NODE））；/*rh為序號是奇數(shù)的鏈表頭指針 */ qh=(NODE *)malloc(sizeof(NODE));/*qh為序號是偶數(shù)的鏈表頭指針 */ r=rh;q=qh; while(p!=NULL){ r->link=p;r=p;i++;p=p->link;if(p!=NULL){ q->link=p;q=p;j++;p=p->link;} } rh->data=i;r->link=rh;qh->data=j;q->link=qh;} 11.typedef struct node { elemtype data;struct node *link;}NODE;void change(NODE *head){ NODE *p;p=head;if(head!=NULL){ while(p->link!=NULL)p=p->link;p->link=head;} } 12.typedef struct node { elemtype data;struct node *link;}NODE;void del(NODE *x,NODE *y){ NODE *p,*q;elemtype d1;p=y;q=x;while(q->next!=NULL)/* 把后一個(gè)結(jié)點(diǎn)數(shù)據(jù)域前移到前一個(gè)結(jié)點(diǎn)*/ { p->data=q->data;q=q->link;p=q;p->link=NULL;/* 刪除最后一個(gè)結(jié)點(diǎn)*/ free(q);} 第三章 棧和隊(duì)列 一、選擇題 1.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（）。（A）edcba（B）decba（C）dceab（D）abcde 2.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（）。 （A）線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)（B）散列方式和索引方式（C）鏈表存儲結(jié)構(gòu)和數(shù)組（D）線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu) 3.判定一個(gè)棧ST(最多元素為m0)為空的條件是（）。（A）ST-〉top!=0（B）ST-〉top==0（C）ST-〉top!=m0（D）ST-〉top=m0 4.判定一個(gè)棧ST(最多元素為m0)為棧滿的條件是（）。（A）ST->top!=0（B）ST->top==0（C）ST->top!=m0-1（D）ST->top==m0-1 5.一個(gè)隊(duì)列的入列序列是1,2,3,4,則隊(duì)列的輸出序列是（）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1 6.循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值,已知其頭尾指針分別是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（） （A）(rear-front+m)%m（B）rear-front+1（C）rear-front-1（D）rear-front 7.棧和隊(duì)列的共同點(diǎn)是（） （A）都是先進(jìn)后出（B）都是先進(jìn)先出 （C）只允許在端點(diǎn)處插入和刪除元素（D）沒有共同點(diǎn) 8.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。 （A）abcd*+-（B）abc+*d-（C）abc*+d-（D）-+*abcd 9.4個(gè)元素a1，a2，a3和a4依次通過一個(gè)棧，在a4進(jìn)棧前，棧的狀態(tài)，則不可能的出棧序是（） (A)a4，a3，a2，a1(B)a3，a2，a4，a1(C)a3，a1，a4，a2(D)a3，a4，a2，a1 10.以數(shù)組Q[0..m－1]存放循環(huán)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù)，隊(duì)列第一個(gè)元素的實(shí)際位置是（）(A)rear－qulen(B)rear－qulen＋m (C)m－qulen (D)1＋（rear＋m－qulen）% m 二、填空題 1.棧的特點(diǎn)是_______________________,隊(duì)列的特點(diǎn)是__________________________。2.線性表、棧和隊(duì)列都是_____________________結(jié)構(gòu),可以在線性表的______________位置插入和刪除元素，對于棧只能在________插入和刪除元素，對于隊(duì)列只能在_______插入元素 和_________刪除元素。 3.一個(gè)棧的輸入序列是12345,則棧有輸出序列12345是____________。(正確/錯(cuò)誤)4.設(shè)棧S和隊(duì)列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_____個(gè)元素。 三、算法設(shè)計(jì)題 1.假設(shè)有兩個(gè)棧s1和s2共享一個(gè)數(shù)組stack[M],其中一個(gè)棧底設(shè)在stack[0]處，另一個(gè)棧底設(shè)在stack[M-1]處。試編寫對任一棧作進(jìn)棧和出棧運(yùn)算的C函數(shù)push（x,i)和pop(i),i=l,2。其中i=1表示左邊的棧，,i=2表示右邊的棧。要求在整個(gè)數(shù)組元素都被占用時(shí)才產(chǎn)生溢出。 2.利用兩個(gè)棧s1,s2模擬一個(gè)隊(duì)列時(shí),如何用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的運(yùn)算?寫出模擬隊(duì)列的插入和刪除的C函數(shù)。 一個(gè)棧s1用于插入元素,另一個(gè)棧s2用于刪除元素.參考答案： 一、選擇題 1.C 2.A 3.B 4.B 5.B 6.B 7、C 8、C 9、C 10、D 二、填空題 1、先進(jìn)先出；先進(jìn)后出 2、線性 ； 任何 ；棧頂；隊(duì)尾；對頭 3、正確的 4、3 三、算法設(shè)計(jì)題 1.#define M 100 elemtype stack[M];int top1=0,top2=m-1;int push(elemtype x,int i){ if(top1-top2==1)return(1);/*上溢處理*/ else if(i==1)stack[top1++]=x;if(i==2)stack[top2--]=x;return(0);} int pop(elemtype *px,int i){ if(i==1)if(top1==0)return(1);else { top1--;*px=stack[top1];return(0);} else if(i==2)if(top2==M-1)return(1);else { top2++;*px=stack[top2];return(0);} } 2.elemtype s1[MAXSIZE],s2[MAZSIZE];int top1,top2;void enqueue(elemtype x){ if(top1==MAXSIZE)return(1);else { push(s1,x);return(0);}} void dequeue(elemtype *px){ elemtype x;top2=0;while(!empty(s1)){ pop(s1,&x);push(s2,x);} pop(s2,&x);while(!empty(s2)){ pop(s2,&x);push(s1,x);} } 第四章 串 一、選擇題 1.下列關(guān)于串的敘述中，正確的是（） (A)一個(gè)串的字符個(gè)數(shù)即該串的長度(B)一個(gè)串的長度至少是1 (C)空串是由一個(gè)空格字符組成的串(D)兩個(gè)串S1和S2若長度相同，則這兩個(gè)串相等 2.字符串“abaaabab”的nextval值為(?)(A)(0,1,01,1,0,4,1,0,1)(B)(0,1,0,0,0,0,2,1,0,1)(C)(0,1,0,1,0,0,0，1,1)(D)(0,1,0,1,0,1,0,1,1) 3.字符串滿足下式,其中head和tail的定義同廣義表類似,如head(‘xyz’)= ‘x’,tail(‘xyz’)= ‘yz’,則s=()。concat(head(tail(s)),head(tail(tail(s))))= ‘dc’。 (A)abcd(B)acbd(C)acdb(D)adcb 4.串是一種特殊的線性表,其特殊性表現(xiàn)在（）(A)可以順序存儲(B)數(shù)據(jù)元素是一個(gè)字符(C)可以鏈?zhǔn)酱鎯?D)數(shù)據(jù)元素可以是多個(gè)字符 5．設(shè)串S1=‘ABCDEFG’,s2=‘PQRST’,函數(shù)CONCAT（X，Y）返回X和Y串的連接串，SUBSTR（S，I，J）返回串S從序號I開始的J個(gè)字符組成的字串，LENGTH（S）返回串S的長度，則CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的結(jié)果串是（） （A）BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF 二、算法設(shè)計(jì) 1.分別在順序存儲和一般鏈接存儲兩種方式下,用C語言寫出實(shí)現(xiàn)把串s1復(fù)制到串s2的串復(fù)制函數(shù)strcpy(s1,s2)。 2.在一般鏈接存儲(一個(gè)結(jié)點(diǎn)存放一個(gè)字符)方式下,寫出采用簡單算法實(shí)現(xiàn)串的模式匹配的C語言函數(shù)int L_index(t,p)。 參考答案： 一、選擇題 1.A 2.B 3.D 4.D 5.D 二、算法設(shè)計(jì) 1.順序存儲： #include “string.h” #define MAXN 100 char s[MAXN];int S_strlen(char s[]){ int i;for(i=0;s[i]!='
第二篇：嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及答案解析