【正文】 　判斷題1．取線性表的第i個元素的時間同i的大小有關（　　） 【答案】 2．線性表的特點是每個元素都有一個前驅和一個后繼（　　） 【答案】 3． 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高（　?。?【答案】 4．線性表采用鏈表存儲時，結點的存儲空間可以是不連續(xù)的（　?。?【答案】√ 5．鏈表是采用鏈式存儲結構的線性表，進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高（　　） 【答案】√ 6．順序存儲方式只能用于存儲線性結構（　?。?【答案】 【解析】線性結構、樹型結構和圖狀結構均可用順序存儲表示。 　if( MAXSIZE) return。i=0。}/*Insert_SqList*/ 2．設 A=（a1，a2，…，am） 和 B=（b1，b2，…，bn）均為順序表，試設計一個比較A，B大小的算法（請注意：在算法中，不要破壞原表A和B）。amp。 　　　　return ?1:1。 p=ha。}/*ListConcat */4．試設計一個算法，在無頭結點的動態(tài)單鏈表上實現(xiàn)線性表操作INSERT（L，i，b），并和在帶頭結點的動態(tài)單鏈表上實現(xiàn)相同操作的算法進行比較。 　newdata=b。 while(i1) p=pnext。試設計一個高效的算法，刪除表中所有值大于 mink且小于 maxk的元素（若表中存在這樣的元素），同時釋放被刪結點空間（注意：mink和maxk是給定的兩個參變量。 　　while(pnextdata=mink) p=pnext。 　}}/*Delete_Between */ 6．已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。q=pnext。 　　　　　　　　　　　q=qnext。q=pnext。 　p=Lnext。 /*從鏈表的第一元素結點處斷開*/ 　while(snext) 　　{qnext=p。 /*把L的元素逐個插入新表表頭*/ 　　} 　qnext=p。 線性表A，B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。　　*C=A。　pnext=q?！　　=t。 　pa=Anext。q=panext。q=pbnext。 } *C=A。 【算法分析】先從B和C中找出共有元素，記為same，再在A中從當前位置開始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳過，到大于same時就再找下一個same。 m=0。amp。 /*找到了相同元素same*/ while([j]==same) j++。(*A).elemsame) (*A).elem[m++]=(*A).elem[i++]。 /*跳過相同的元素*/ } }/*while*/ while(i(*A).length) (*A).elem[m++]=(*A).elem[i++]。這就要求從第二結點開始，將各結點依次插入到有序鏈表中。/*暫存p的后繼*/ q=la。/*查找插入位置*/ pnext=qnext。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當對鏈表進行一次LOCATE（L，X）的操作后，被訪問的結點（元素值等于X的結點）中的頻度域freq的值便增1，同時調整鏈表中結點之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結點總是靠近表頭結點。 while(!=xamp。 /*沒找到x結點*/ pfreq++。 while(qfreq=pfreqamp。 pnext=qnext。}/*Locate_DuList */13．已知三個帶頭結點的線性鏈表A、B和C中的結點均依元素值自小至大非遞減排列（可能存在兩個以上值相同的結點），編寫算法對A表進行如下操作：使操作后的鏈表A中僅留下三個表中均包含的數據元素的結點，且沒有值相同的結點，并釋放所有無用結點。 【算法源代碼】 LinkList Common(LinkList A, LinkList B, LinkList C){ pa=Anext。 while(pa amp。 pc) /*當三表均不空時，查找共同元素*/ { while(pa amp。free(u)。 pb) /*處理A和B表元素值相等的結點*/ { while(pc amp。pa=panext。pa=panext} else if(predata==padata) /*重復結點不鏈入A表*/ {u=pa。pre=pa。 /* 鏈表的工作指針后移*/ } } else if(pa==NULL)prenext=NULL。pa=panext。程序中不得使用malloc申請空間。/*p和q鏈表初始化為空表*/ s=head。} /*第一個偶數結點*/ else { pre=p。/*查找插入位置*/ snext=prenext。} /*第一奇數結點*/ else {pre=q。 snext=pre