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