[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題-文庫吧
2024-12-31 06:15 本頁面
【正文】 在鏈表中比在順序存儲結(jié)構(gòu)中效率高（ ） 【答案】√ 6．順序存儲方式只能用于存儲線性結(jié)構(gòu)（ ） 【答案】 【解析】線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖狀結(jié)構(gòu)均可用順序存儲表示。 9．順序存儲結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作（ ） 【答案】√ 10．順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶茫ā 。?【答案】 程序設(shè)計題1．設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試設(shè)計一個算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。 【算法源代碼】 void Insert_SqList(SqList va,int x)/*把x插入遞增有序表va中*/{ int i。 if( MAXSIZE) return。 for(i=。xamp。amp。i=0。i) [i+1]=。 [i+1]=x。 ++。}/*Insert_SqList*/ 2．設(shè) A=（a1，a2，…，am） 和 B=（b1，b2，…，bn）均為順序表，試設(shè)計一個比較A，B大小的算法（請注意：在算法中，不要破壞原表A和B）。 【算法分析】比較順序表A和B，并用返回值表示結(jié)果，值為1，表示AB；值為1，表示AB；值為0，表示A=B。 1）當(dāng)兩個順序表可以互相比較時，若對應(yīng)元素不等，則返回值為1或1； 2）當(dāng)兩個順序表可以互相比較的部分完全相同時，若表長也相同，則返回值為0；否則，哪個較長，哪個就較大 【算法源代碼】int ListComp(SqList A,SqList B) { for(i=1。i=amp。amp。i=。i++) if(!=) return ?1:1。 if(==) return 0。 return ?1:1。 /*當(dāng)兩個順序表可以互相比較的部分完全相同時，哪個較長， 哪個就較大*/ }/*ListComp */3．已知指針 ha和 hb分別指向兩個單鏈表的頭結(jié)點(diǎn)，并且已知兩個鏈表的長度分別為m和n。試設(shè)計一個算法將這兩個鏈表連接在一起（即令其中一個表的首元結(jié)點(diǎn)連在另一個表的最后一個結(jié)點(diǎn)之后），假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時間完成連接運(yùn)算。 【算法分析】 1）單鏈表ha的頭結(jié)點(diǎn)作為連接后的鏈表的頭結(jié)點(diǎn)，即hc=ha； 2）查找單鏈表ha的最后一個結(jié)點(diǎn)，由指針p指向，即pnext==NULL； 3）將單鏈表hb的首元結(jié)點(diǎn)（非頭結(jié)點(diǎn)）連接在p之后，即pnext=hbnext； 4）回收單鏈表hb的頭結(jié)點(diǎn)空間 【算法源代碼】 void ListConcat(LinkList ha,LinkList hb,LinkList *hc)/*把鏈表hb接在ha后面形成鏈表hc*/{ *hc=ha。 p=ha。/*由指針p指向ha的尾元結(jié)點(diǎn)*/ p=pnext。 pnext=hbnext。 free(hb)。}/*ListConcat */4．試設(shè)計一個算法，在無頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)線性表操作INSERT（L，i，b），并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。 【算法分析】 1）生成新結(jié)點(diǎn)存放元素b，由指針new指向； 2）將new插入在單鏈表的第i個元素的位置上：若i==1，new插在鏈表首部；否則查找第i1個結(jié)點(diǎn)，由指針p指向，然后將new插在p之后。 【算法源代碼】 void Insert(LinkList *L,int i,int b){ LinkList new。 new=(LinkList*)malloc(sizeof(LNode))。 newdata=b。 if(i==1) {/*插入在鏈表頭部*/ Newnext=*L。 *L=new。 } else { /*插入在第i個元素的位置*/ p=*L。 while(i1) p=pnext。 newnext=pnext?！next=new。 }}/*Insert */5．已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試設(shè)計一個高效的算法，刪除表中所有值大于 mink且小于 maxk的元素（若表中存在這樣的元素），同時釋放被刪結(jié)點(diǎn)空間（注意：mink和maxk是給定的兩個參變量。它們的值可以和表中的元素相同，也可以不同）。 【算法分析】 1）查找最后一個不大于mink的元素結(jié)點(diǎn)，由指針p指向； 2）如果還有比mink更大的元素，查找第一個不小于maxk的元素，由指針q指向； 3）pnext=q，即刪除表中所有值大于 mink且小于 maxk的元素。 【算法源代碼】 void Delete_Between(LinkList *L,int mink,int maxk){ p=*L。 while(pnextdata=mink) p=pnext。 /*p是最后一個不大于mink的元素*/ if(pnext) /*如果還有比mink更大的元素*/ { q=pnext。 while(qdatamaxk) q=qnext。 /*q是第一個不小于maxk的元素*/ pnext=q。 }}/*Delete_Between */ 6．已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試設(shè)計一個高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結(jié)點(diǎn)空間。 【算法分析】 1）初始化指針p和q，分別指向鏈表中相鄰的兩個元素； 2）當(dāng)pnext不為空時，做如下處理： ①若相鄰兩元素不相等時，p和q都向后推一步； ②否則，當(dāng)相鄰元素相等時，刪除多余元素。 【算法源代碼】 void Delete_Equal(LinkList *L) { p=(*L)next。q=
試題試卷相關(guān)推薦
鄂ICP備17016276號-1