[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題(存儲版)
【正文】 e([k]==same) k++。 /*A的剩余元素重新存儲*/ (*A).length=m。 while (qnext!=NULLamp。試編寫符合上述要求的 LOCATE操作的算法。 pprenext=pnext。 qnext=p。pb=Bnext。amp。amp。pa=panext。 /*若A表已結(jié)束，置A表表尾*/ else /*處理原A表未到尾而B或C到尾的情況*/ { prenext=NULL。 【算法分析】本題要求將一個鏈表分解成兩個鏈表，兩個鏈表都要有序，兩鏈表建立過程中不得使用malloc申請空間，這就是要利用原鏈表空間，隨著原鏈表的分解，新建鏈表隨之排序。 if(predatasdata) {snext=pre。 if (predatasdata) {snext=pre。 /*s指向新的待排序結(jié)點(diǎn)*/ }}。qnext=NULL。pnext=NULL。編一函數(shù)，將 head鏈中結(jié)點(diǎn)分成一個奇數(shù)鏈和一個偶數(shù)鏈，分別由p，q指向，每個鏈中的數(shù)據(jù)按由小到大排列。pc=pcnext。pre=pa。amp。amp。要消除重復(fù)元素，應(yīng)記住前驅(qū)，要求時間復(fù)雜度O（m+n+p），在查找每個鏈表時，指針不能回溯。 /*查找插入位置*/ if(q!=ppre) /*將x結(jié)點(diǎn)插入*/ { qnextpre=p。 if(p==(*L)) return NULL。}12．設(shè)有一個雙向循環(huán)鏈表，每個結(jié)點(diǎn)中除有 prior，data和 next三個域外，還增設(shè)了一個訪問頻度域freq。 /*直接插入原則認(rèn)為第一元素有序，然后從第二元素起依次插入*/ while (p!=NULL) { r=pnext。(*A).elem==same) i++。 else{ same=[j]。 k=0。 } pre=pc。 while(pa||pb) { if(padatapbdata||!pb) /*將A的元素插入新表*/ { pc=pa。 /*若A非空，將A的元素插入*/ } p=s?！ =Bnext。s=snext。 【算法源代碼】 void LinkList_reverse(LinkList L){ if(!Lnext||!Lnextnext) return。 } else { while(qdata==pdata) /*當(dāng)相鄰元素相等時刪除多余元素*/ { r=q。 /*q是第一個不小于maxk的元素*/ pnext=q。 }}/*Insert */5．已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。 new=(LinkList*)malloc(sizeof(LNode))。 【算法分析】 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。i=amp。amp。 【答案】144 11．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是_____________。 【答案】（1）4 （2）2 8. 循環(huán)單鏈表的最大優(yōu)點(diǎn)是_____________。 【答案】A 9．線性表采用鏈?zhǔn)酱鎯r，其元素地址（ ） A）必須是連續(xù)的 B）一定是不連續(xù)的 C）部分地址是連續(xù)的 D）連續(xù)與否均可 【答案】D 填空題1．線性表L=（a1，a2，…，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是_____________。 qnext=p。 qprior=pprior。 ppriornext=q。 ppriornext=q。 C）pnextprior=p pnext=pnextnext D）pnext=ppriorprior pprior=pnextnext。 【答案】（1）O(1) （2）O(n) 7. 對于雙向鏈表，在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)需修改的指針共_____________個，單鏈表為_____________個。 【答案】（1）pnext （2）sdata （3） t 10．某線性表采用順序存儲結(jié)構(gòu)，每個元素占據(jù)4個存儲單元，首地址為100，則下標(biāo)為11的（第12個）元素的存儲地址為_____________。xamp。 1）當(dāng)兩個順序表可以互相比較時，若對應(yīng)元素不等，則返回值為1或1； 2）當(dāng)兩個順序表可以互相比較的部分完全相同時，若表長也相同，則返回值為0；否則，哪個較長，哪個就較大 【算法源代碼】int ListComp(SqList A,SqList B)
試題試卷相關(guān)推薦
鄂ICP備17016276號-1