[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題(完整版)
【正文】 選擇題1．對于線性表最常用的操作是查找指定序號的元素和在末尾插入元素，則選擇（ ）最節(jié)省時間 A）順序表 B）帶頭結(jié)點的雙循環(huán)鏈表 C）單鏈表 D）帶尾結(jié)點的單循環(huán)鏈表 【答案】A 2．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法時間復(fù)雜度為（ ?。?1≤i≤n+1)。 pprior=qnext。 pprior=q。 3．線性表的順序存儲是通過_____________來反應(yīng)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過_____________來反應(yīng)元素之間的邏輯關(guān)系。 t=pdata。 【算法源代碼】 void Insert_SqList(SqList va,int x)/*把x插入遞增有序表va中*/{ int i。 ++。 if(==) return 0。 free(hb)。 } else { /*插入在第i個元素的位置*/ p=*L。 【算法源代碼】 void Delete_Between(LinkList *L,int mink,int maxk){ p=*L。 【算法源代碼】 void Delete_Equal(LinkList *L) { p=(*L)next。p=q。 pnext=NULL。}/*LinkList_reverse*/8．設(shè)線性表A=（a1，a2，…，am） 和 B=（b1，b2，…，bn），試設(shè)計一個按下列規(guī)則合并A，B為線性表C的算法，即使得 C=（a1，b1，…，am，bm，bm+1 ，…，bn ）當(dāng) m≤n時； 或者 C=（a1，b1，…，an，bn，an+1 ，…，am ）當(dāng)m＞n時。q) { s=pnext。 【算法源代碼】 void reverse_merge(LinkList A,LinkList B,LinkList *C) { LinkList pa,pb,pre。 } else /*將B的元素插入新表*/ { pc=pb。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復(fù)雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。jamp。amp。 【算法分析】本題明確指出單鏈表帶頭結(jié)點，其結(jié)點數(shù)據(jù)是正整數(shù)且不相同，要求利用直接插入原則把鏈表整理成遞增有序鏈表。qnextdatapdata) q=qnext。 【算法源代碼】 DuLNode * Locate_DuList(DuLinkList *L,int x) { p=(*L)next。 /*將x結(jié)點從鏈表上摘下*/ q=ppre。 /*調(diào)整位置*/ } return p。 /*pa，pb和pc是工作指針*/ pre=A。pa=panext。 if(pc) {if(pcdatapadata) /*處理pa結(jié)點，后移指針*/ {u=pa。} else {prenext=pa。*/ {u=pa。 q=NULL。}/*插入當(dāng)前最小值結(jié)點*/ else {while (prenext!=NULL) if (prenextdatasdata) pre=prenext。} /*修改頭指針*/ else {while (prenext!=NULL) /*查找插入位置*/ if (prenextdatasdata) pre=prenext。 /*鏈入結(jié)點*/ prenext=s。 /*鏈入結(jié)點*/ prenext=s。 while (s!=NULL) { r=snext。free(u)。pa=panext。free(u)。} else if(padata pbdata)pb=pbnext。amp。限定算法的時間復(fù)雜度為O（m+n+p），其中m、n和p分別為三個表的長度。amp。amp。/*將p結(jié)點鏈入鏈表*/ qnext=p。 【算法源代碼】 void InsertSort (LinkList la){ if(lanext!=NULL) /*鏈表不為空表*/ { p=lanextnext。 /*需保留的元素移動到新位置*/ while(i(*A).lengthamp。 k) { if ([j][k]) j++。 【算法源代碼】 void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) { i=0。pbnext=pre
試題試卷相關(guān)推薦
鄂ICP備17016276號-1