一基礎知識題
試描述頭指針
頭結點
開始結點的區別
並說明頭指針和頭結點的作用
何時選用順序表何時選用鏈表作為線性表的存儲結構為宜?
在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決於哪兩個因素?
為什麼在單循環鏈表中設置尾指針比設置頭指針更好?
在單鏈表雙鏈表和單循環鏈表中若僅知道指針p指向某結點不知道頭指針能否將結點*p從相應的鏈表中刪去?若可以其時間復雜度各為多少?
下述算法的功能是什麼?
LinkList Demo(LinkList L){ // L 是無頭結點單鏈表
ListNode *Q*P;
if(L&&L>next){
Q=L;L=L>next;P=L;
while (P>next) P=P>next;
P>next=Q; Q>next=NULL;
}
return L;
}// Demo
二算法設計題
設線性表的n個結點定義為(aaan)重寫順序表上實現的插入和刪除算法InsertList 和DeleteList
試分別用順序表和單鏈表作為存儲結構實現將線性表(aaan)就地逆置的操作所謂就地指輔助空間應為O()
設順序表L是一個遞增有序表試寫一算法將x插入L中並使L仍是一個有序表
設順序表L是一個遞減有序表試寫一算法將x插入其後仍保持L的有序性
寫一算法在單鏈表上實現線性表的ListLength(L)運算
已知L和L分別指向兩個單鏈表的頭結點且已知其長度分別為m和n試寫一算法將這兩個鏈表連接在一起請分析你的算法的時間復雜度
設 A和B是兩個單鏈表其表中元素遞增有序試寫一算法將A和B歸並成一個按元素值遞減有序的單鏈表C並要求輔助空間為O()請分析算法的時間復雜度
已知單鏈表L是一個遞增有序表試寫一高效算法刪除表中值大於min 且小於max的結點(若表中有這樣的結點)同時釋放被刪結點的空間這裡min 和 max是兩個給定的參數請分析你的算法的時間復雜度
寫一算法將單鏈表中值重復的結點刪除使所得的結果表中各結點值均不相同
假設在長度大於的單循環鏈表中既無頭結點也無頭指針s為指向鏈表中某個結點的指針試編寫算法刪除結點*s的直接前趨結點
已知由單鏈表表示的線性表中含有三類字符的數據元素(如字母字符數字字符和其它字符)試編寫算法構造三個以循環鏈表表示的線性表使每個表中只含同一類的字符且利用原表中的結點空間作為這三個表的結點空間頭結點可另辟空間
設有一個雙鏈表每個結點中除有priordata和next三個域外還有一個訪問頻度域freq在鏈表被起用之前其值均初始化為零每當在鏈表進行一次LocateNode(Lx)運算時令元素值為x的結點中freq域的值加並調整表中結點的次序使其按訪問頻度的遞減序排列以便使頻繁訪問的結點總是靠近表頭試寫一符合上述要求的LocateNode運算的算法
From:http://tw.wingwit.com/Article/program/sjjg/201311/23994.html
