[ppt模板]數(shù)據(jù)結構線性表試題-在線瀏覽
2025-03-04 06:15本頁面
【正文】 一個前驅和一個后繼（ ?。?【答案】 3． 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高（ ?。?【答案】 4．線性表采用鏈表存儲時，結點的存儲空間可以是不連續(xù)的（ ） 【答案】√ 5．鏈表是采用鏈式存儲結構的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高（ ?。?【答案】√ 6．順序存儲方式只能用于存儲線性結構（ ） 【答案】 【解析】線性結構、樹型結構和圖狀結構均可用順序存儲表示。試設計一個算法，將x插入到順序表的適當位置上，以保持該表的有序性。 if( MAXSIZE) return。xamp。i=0。 [i+1]=x。}/*Insert_SqList*/ 2．設 A=（a1，a2，…，am） 和 B=（b1，b2，…，bn）均為順序表，試設計一個比較A，B大小的算法（請注意：在算法中，不要破壞原表A和B）。 1）當兩個順序表可以互相比較時，若對應元素不等，則返回值為1或1； 2）當兩個順序表可以互相比較的部分完全相同時，若表長也相同，則返回值為0；否則，哪個較長，哪個就較大 【算法源代碼】int ListComp(SqList A,SqList B) { for(i=1。amp。i++) if(!=) return ?1:1。 return ?1:1。試設計一個算法將這兩個鏈表連接在一起（即令其中一個表的首元結點連在另一個表的最后一個結點之后），假設指針hc指向連接后的鏈表的頭結點，并要求算法以盡可能短的時間完成連接運算。 p=ha。 pnext=hbnext。}/*ListConcat */4．試設計一個算法，在無頭結點的動態(tài)單鏈表上實現(xiàn)線性表操作INSERT（L，i，b），并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。 【算法源代碼】 void Insert(LinkList *L,int i,int b){ LinkList new。 newdata=b。 *L=new。 while(i1) p=pnext?！next=new。試設計一個高效的算法，刪除表中所有值大于 mink且小于 maxk的元素（若表中存在這樣的元素），同時釋放被刪結點空間（注意：mink和maxk是給定的兩個參變量。 【算法分析】 1）查找最后一個不大于mink的元素結點，由指針p指向； 2）如果還有比mink更大的元素，查找第一個不小于maxk的元素，由指針q指向； 3）pnext=q，即刪除表中所有值大于 mink且小于 maxk的元素。 while(pnextdata=mink) p=pnext。 while(qdatamaxk) q=qnext。 }}/*Delete_Between */ 6．已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。 【算法分析】 1）初始化指針p和q，分別指向鏈表中相鄰的兩個元素； 2）當pnext不為空時，做如下處理： ①若相鄰兩元素不相等時，p和q都向后推一步； ②否則，當相鄰元素相等時，刪除多余元素。q=pnext。 q=pnext。 q=qnext。 } pnext=q。q=pnext。 【算法分析】 1）空表或長度為1的表，不做任何處理； 2）表長大于2時，做如下處理： ①首先將整個鏈表一分為二，即從鏈表的第一元素結點處斷開； ②逐個地把剩余鏈表的當前元素q插入到鏈表的頭部。 p=Lnext。 s=qnext。 /*從鏈表的第一元素結點處斷開*/ while(snext) {qnext=p。 q=s。 /*把L的元素逐個插入新表表頭*/ } qnext=p。Lnext=s。 線性表A，B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。 【算法分析】 1）初始化指針p指向鏈表A的當前元素，指針q指向鏈表B的當前元素； 2）當鏈表A和B均為結束時，做如下處理： ①將B的元素插入 ②若A非空，將A的元素插入 ③指針p和q同時后移 【算法源代碼】 void merge1(LinkList A,LinkList B,LinkList *C) { p=Anext?！ ?C=A。amp?！next=q。 qnext=s。 q=t。 【算法分析】按從小到大的順序依次把A和B的元素插入新表的頭部pc處，最后處理A或B的剩余元素。 pa=Anext。 /*pa和pb分別指向A和B的當前元素*/ pre=NULL。q=panext。pa=q。q=pbnext。pb=q。 } *C=A。 /*構造新表頭*/}/*reverse_merge*/10．已知A，B和C為三個遞增有序的線性表，現(xiàn)要求對A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。 【算法分析】先從B和C中找出共有元素，記為same，再在A中從當前位置開始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳過，到大于same時就再找下一個same。 j=0。 m=0。amp。amp。 else if([j][k]) k++。 /*找到了相同元素same*/ while([j]==same) j++。 /*j和k后移到新的元素*/ while(i(*A).lengthamp。(*A).elemsame) (*A).elem[m++]=(*A).elem[i++]。amp。 /*跳過相同的元素*/ }
試題試卷相關推薦
鄂ICP備17016276號-1