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