【正文】 will take place all the T239。 //修改長度}else //T1 長度與T2 長度相等{ for(i=0。Slength=lent1lent2。//求T1 串的next[]向量do{pos=kmp(S,T1,next,temppos)。}else j=next[j]。next[i]=j。int length 。gets()。break。}seqstring。 若串S =“software”，其子串的數(shù)目為（ 36 ）。p=prlink?！敬稹浚篿nclude include /*將一個雙鏈表改成循環(huán)雙鏈表*/void dlinktocdlink(dlinklist head){ dlinklist r。}}void main() /*測試函數(shù)*/{ dlinklist head。x)。datatype x,y。if (!p) printf(\n 雙鏈表中不存在值為y 的結(jié)點,無法插入新結(jié)點!\n)。printf(\n 雙鏈表的內(nèi)容是：\n)。 /*將新結(jié)點s 插入到雙鏈表鏈尾*/19sllink=r。head=r=(dlinklist) malloc(sizeof(dnode))。即使值為x 的新結(jié)點成為值為y 的結(jié)點的前驅(qū)結(jié)點。 /*創(chuàng)建單鏈表*/print(head)。 /*刪除大于x 而小于y 的結(jié)點*/prenext=p。 /*初始化*/while (p amp。 /*分裂單鏈表head*/printf(\n 原單鏈表為:\n)。}else /*保留偶數(shù)值結(jié)點*/{ pre=p。L=r=(linklist)malloc(sizeof(linknode))。headnext=q。else printf(單鏈表head 是無序的！\n)。head=creatlinklist()。amp。pnext amp。print(head)。int y,x。amp。printf(\nLength of head is:%d,count(head))?！敬稹浚?，實現(xiàn)本題功能的算法程序如下（）include int count(linklist head){ int c=0。p=pnext。scanf(%d,amp。head=r=(linklist)malloc(sizeof(linknode))。 D．pnext=s。 D．p =pnextnext。A．O(1) B．O(n) C．O(n2) D．O(nlog2n)（6）用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時（ D ）。amp。if (pinfo==x) return p else return NULL。該算法的時間復(fù)雜度也是O(n!)。return count。i++) /*插入排序*/{ j=i1。amp。 /*計數(shù)器加1*/}i=n。k++。i++){ j=i+1。int i,j,k,x,count=0。但為順序從小到大列舉出所有的排列，不能立即調(diào)整得太大，如本例中將數(shù)字6 與數(shù)字4 交換得到的排列為126453 就不是排列124653 的下一個排列。return 0。 /*輸出排列的元素個數(shù)*/scanf(%d,amp。}else b[0]=str[j]。in。 str[k]=str[i]。R 的全排列可歸納定義如下：當(dāng)n=1 時，perm(R)=(r)，其中r 是集合R 中惟一的元素；當(dāng)n1 時，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)構(gòu)成?！敬稹浚貉h(huán)隊列中當(dāng)前結(jié)點個數(shù)的計算公式是：(n+rearfront)%n 編號為1,2,3,4 的四列火車通過一個棧式的列車調(diào)度站，可能得到的調(diào)度結(jié)果有哪些？如果有n 列火車通過調(diào)度站，請設(shè)計一個算法，輸出所有可能的調(diào)度結(jié)果。while (j=0 amp。i=0。int i。隊列也是一種特殊的線性表，它的特殊性表現(xiàn)在約定了在這種線性表中數(shù)據(jù)的插入在表的一端進行，數(shù)據(jù)的刪除在表的另一端進行，因此隊列具有先進先出，后進后出的特點。A．n?i B．n ? i +1 C．n ? i ? 1 D．i（5）若長度為n 的線性表采用順序存儲結(jié)構(gòu)存儲，在第i 個位置上插入一個新元素的時間復(fù)雜度為（ A ）。i++)for(j=0。for(j=i+1。（3）for(i=0。對于表11 中的對數(shù)函數(shù)logn，沒有給出對數(shù)基，原因是對于任何大于1 的常數(shù)a 和b 都有l(wèi)ogan =logbn/logba,所以logan 和logbn 都有一個相對的乘法系數(shù)1/logba，其中a 是一個常量。算法中基本操作的執(zhí)行次數(shù)一般是與問題規(guī)模有關(guān)的，對于結(jié)點個數(shù)為n 的數(shù)據(jù)處理問題，用T(n)表示算法基本操作的執(zhí)行次數(shù)。 算法有哪些特點？它和程序的主要區(qū)別是什么？【答】：算法具有（1）有窮性（2）確定性（3）0 個或多個輸入（4）1 個或多個輸出（5）可行性等特征。 數(shù)據(jù)結(jié)構(gòu)涉及哪幾個方面？【答】：數(shù)據(jù)結(jié)構(gòu)涉及三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算集合。抽象數(shù)據(jù)類型是與表示無關(guān)的數(shù)據(jù)類型，是一個數(shù)據(jù)模型及定義在該模型上的一組運算。上述定義表明，函數(shù)f 頂多是函數(shù)g 的c 倍，除非n 小于n0。 對于下面的程序段，分析帶下劃線的語句的執(zhí)行次數(shù)，并給出它們的時間復(fù)雜度T(n)。jn。t=a[k]。s=s+x。A．插入和刪除在表的不同位置執(zhí)行 B．插入和刪除在表的兩端位置執(zhí)行C．插入和刪除分別在表的兩端執(zhí)行 D．插入和刪除都在表的某一端執(zhí)行（8）棧是一種特殊的線性表，具有（ B ）性質(zhì)。 /*假設(shè)數(shù)據(jù)類型為整型*/typedef struct {datatype data[N]。i++)if (Ldata[i]==x) c++。Ldata[i++]=Ldata[j]。j。據(jù)此，本題可以通過算法產(chǎn)生n 個數(shù)的全排列，然后將滿足出棧規(guī)則的序列輸出。/*求整數(shù)序列str[]從k 到n 的全排列*/void perm(int str[],int k,int n){int i,temp。 /*遞歸調(diào)用*/temp=str[i]。jnamp。in。in。隨著n 的增大，算法的執(zhí)行效率非常的低。在前面數(shù)字1，2，5 固定的情況下，還應(yīng)選擇對應(yīng)最小整數(shù)的那個排列，為此還需將后面那部分?jǐn)?shù)字的排列顛倒，如將數(shù)字6，4，3 的排列順序顛倒，得到排列1,2,5,3,4,6，這才是排列1，2，4，6，95，3 的下一個排列。i=n。 a[j]a[i]) j++。i++) /*輸出當(dāng)前排列*/{ printf(%4d,a[i])。 a[i]a[i1]) i。 /*交換兩元素的值*/a[j]=a[i]。amp。 /*輸入排列規(guī)模*/scanf(%d,amp。A．pnext==NULL B．p==NULL C．pnext==head D．p==head（3）在帶頭結(jié)點的單鏈表中查找x 應(yīng)選擇的程序體是（ C ）。amp。D．node *p=head。A．順序表 B．鏈表 C．散列表 D．隊列（9）在一個單鏈表中，若刪除p 所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（ A ）。pnext=s。【答】：單鏈表存儲結(jié)構(gòu)定義如下（相關(guān)文件：）include 12include typedef struct node{ int data。x)。return head。linklist p=head。p=pnext。即使值為x 的新結(jié)點成為值為y 的結(jié)點的前驅(qū)結(jié)點。}if (p)/*找到了值為y 的結(jié)點*/{ s=(linklist)malloc(sizeof(linknode))。 /*輸出單鏈表*/printf(\n 請輸入y 與x 的值:\n)。linklist p=headnext。else flag=0。 flag){if (pdata=pnextdata) p=pnext。a39。p=headnext。 /*創(chuàng)建單鏈表*/print(head)。p=headnext。 /*置鏈表結(jié)束標(biāo)記*/return L。print(L)。p=pnext。q=pre。x,amp。struct dlink_node *llink,*rlink。scanf(%d,amp。scanf(%d,amp。}}本題的求解程序如下：include include void insertxaty(dlinklist head,datatype y,datatype x){ dlinklist s,p。srlink=p。printf(\n 請輸入要輸入的位置結(jié)點值y:\n)。/*輸出新的雙鏈表*/getch()。printf(\n 從右向左打印的雙鏈表的內(nèi)容是:\n)。headllink=r。dlinktocdlink(head)。 對于半帶寬為b 的帶狀矩陣，它的特點是：對于矩陣元素aij ，若它滿足（|ij|b），則aij = 0。for(i=0。int i,m。if(m==1) printf(s1s2\n)。next[0]=1。24i=temppos,j=0。}//替換函數(shù)void takeplace(seqstring*S,seqstring*T1,seqstring*T2){int next[maxsize],temppos=0,pos,i。iSlength。i) //后移留空Sstr[i+lent2lent1]=Sstr[i]。}temppos=pos+T2length。S=(seqstring*)malloc(sizeof(seqstring))。printf(輸入替換串(input T2):\n)。free(T2)。while(i){if(j==1||[i]==[j]){++i。while(islength){ j=0。k。slength=s+。k++)sstr[c+k]=[k]。printf(Input string s:)。=strlen()。} linkstrnode。){ p=(linkstrnode *)malloc(sizeof(linkstrnode))。p=head。S1=S1next。strcreate(amp。if (k==1) printf(s1s2)。if (L==NULL) L=r=s。if (S==NULL|| T1==NULL ) return S。amp。 /*未找到子串T1*/else{ flag=1。if (pre==NULL) /*如果T1 出現(xiàn)在S 的鏈頭*/S=temp。}int main(){linkstring S,T1,T2。 /*建立字符串T1*/print(T1)。} 已知如下字符串，求它們的next 數(shù)組值：（1）“bbdcfbbdac”32【答】：1010001230（2）“aaaaaaa”【答】：1012345（3）“babbabab”【答】：10011232 已知正文t =“ababbaabaa”，模式p =“aab”，試使用KMP 快速模式匹配算法尋找p在t 中首次出現(xiàn)的起始位置，給出具體的匹配過程分析。 //三元組存儲結(jié)構(gòu)spmatrix c。c[k][1]=a[i][1]。c[k][2]=b[j][2]。i++。}while(i=a[0][2]){c[k][0]=a[i][0]。}//函數(shù)pressmatrix 將普通矩陣存儲轉(zhuǎn)換為三元組存儲結(jié)構(gòu)void pressmatrix(matrix *A , spmatrix B){ int i, j, k。B[k][2]=Adata[i][j]。i++。data)。printf(\n)。 /*輸入行和列*/scanf(%d%d,amp。p,a)。}}程序運行時先輸入矩陣的行和列，然后按普通矩陣格式輸入矩陣值，一組程序測試用例運行結(jié)果如下圖：【參考程序2】：37include include define MAX 100typedef struct{int data[MAX][3]。Avalue)。 j ++)scanf(%d,amp。j 3。 j = Bvalue){if(Adata[i][0] == Bdata[j][0]){38if(Adata[i][1] == Bdata[j][1]){Cdata[k][0] = Adata[i][0]。Cdata[k][2] = Adata[i][2]。}}else if(Adata[i][0] Bdata[j][0]){Cdata[k][0] = Adata[i][0]。39k ++。Cdata[k][1] = Bdata[j][1]。return C。C = addmatrix(A,B,C)。int m,n,value。Adata[0][0] = Am。Adata[i][j])。j