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