[ppt模板]數(shù)據(jù)結(jié)構(gòu)線(xiàn)性表試題-wenkub
2023-01-30 06:15:42 本頁(yè)面
【正文】 { for(i=1。 [i+1]=x。xamp。試設(shè)計(jì)一個(gè)算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。 【答案】（1）pnext （2）sdata （3） t 10．某線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占據(jù)4個(gè)存儲(chǔ)單元，首地址為100，則下標(biāo)為11的（第12個(gè)）元素的存儲(chǔ)地址為_(kāi)____________。 pnext=s。 【答案】（1）O(1) （2）O(n) 7. 對(duì)于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共_____________個(gè)，單鏈表為_(kāi)____________個(gè)。另外，不論鏈表是否為空，鏈表頭指針不變。 C）pnextprior=p pnext=pnextnext D）pnext=ppriorprior pprior=pnextnext。 qprior=pprior。 ppriornext=q。 qnext=p。 ppriornext=q。第2章 選擇題1．對(duì)于線(xiàn)性表最常用的操作是查找指定序號(hào)的元素和在末尾插入元素，則選擇（ ）最節(jié)省時(shí)間 A）順序表 B）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 C）單鏈表 D）帶尾結(jié)點(diǎn)的單循環(huán)鏈表 【答案】A 2．若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法時(shí)間復(fù)雜度為（ ?。?1≤i≤n+1)。 qprior=pprior。 pprior=qnext。 qnext=p。 pprior=q。 【答案】A 9．線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其元素地址（ ?。?A）必須是連續(xù)的 B）一定是不連續(xù)的 C）部分地址是連續(xù)的 D）連續(xù)與否均可 【答案】D 填空題1．線(xiàn)性表L=（a1，a2，…，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_____________。 3．線(xiàn)性表的順序存儲(chǔ)是通過(guò)_____________來(lái)反應(yīng)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)_____________來(lái)反應(yīng)元素之間的邏輯關(guān)系。 【答案】（1）4 （2）2 8. 循環(huán)單鏈表的最大優(yōu)點(diǎn)是_____________。 t=pdata。 【答案】144 11．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是_____________。 【算法源代碼】 void Insert_SqList(SqList va,int x)/*把x插入遞增有序表va中*/{ int i。amp。 ++。i=amp。 if(==) return 0。 【算法分析】 1）單鏈表ha的頭結(jié)點(diǎn)作為連接后的鏈表的頭結(jié)點(diǎn)，即hc=ha； 2）查找單鏈表ha的最后一個(gè)結(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。 free(hb)。 new=(LinkList*)malloc(sizeof(LNode))。 } else { /*插入在第i個(gè)元素的位置*/ p=*L。 }}/*Insert */5．已知線(xiàn)性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。 【算法源代碼】 void Delete_Between(LinkList *L,int mink,int maxk){ p=*L。 /*q是第一個(gè)不小于maxk的元素*/ pnext=q。 【算法源代碼】 void Delete_Equal(LinkList *L) { p=(*L)next。 } else { while(qdata==pdata) /*當(dāng)相鄰元素相等時(shí)刪除多余元素*/ { r=q。p=q。 【算法源代碼】 void LinkList_reverse(LinkList L){ if(!Lnext||!Lnextnext) return。 pnext=NULL。s=snext。}/*LinkList_reverse*/8．設(shè)線(xiàn)性表A=（a1，a2，…，am） 和 B=（b1，b2，…，bn），試設(shè)計(jì)一個(gè)按下列規(guī)則合并A，B為線(xiàn)性表C的算法，即使得 C=（a1，b1，…，am，bm，bm+1 ，…，bn ）當(dāng) m≤n時(shí)； 或者 C=（a1，b1，…，an，bn，an+1 ，…，am ）當(dāng)m＞n時(shí)?！ =Bnext。q) { s=pnext。 /*若A非空，將A的元素插入*/ } p=s。 【算法源代碼】 void reverse_merge(LinkList A,LinkList B,LinkList *C) { LinkList pa,pb,pre。 while(pa||pb) { if(padatapbdata||!pb) /*將A的元素插入新表*/ { pc=pa。 } else /*將B的元素插入新表*/ { pc=pb。 } pre=pc。試對(duì)順序表編寫(xiě)實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度（注意：題中沒(méi)有特別
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1