[ppt模板]數(shù)據(jù)結(jié)構(gòu)線性表試題-全文預(yù)覽
【正文】 源代碼】 void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) { i=0。 Anext=pc。pbnext=pre。panext=pre。pb=Bnext。 /*指針p和q同時(shí)后移*/ }/*while*/}/*merge1 */9．假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即 A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。 /*將B的元素插入*/ if (s) { t=qnext。 while(pamp。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)?！ next=q。p=q。 q=pnext。 }/*else*/ }/*while*/}/*Delete_Equal */7．試設(shè)計(jì)一個(gè)算法，對(duì)帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)就地逆置。 free(r)。 /*p和q指向相鄰的兩個(gè)元素*/ while(pnext) { if(pdata!=qdata) /*若相鄰兩元素不相等時(shí)，p和q都向后推一步*/ { p=pnext。試設(shè)計(jì)一個(gè)高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時(shí)釋放被刪結(jié)點(diǎn)空間。 /*p是最后一個(gè)不大于mink的元素*/ if(pnext) /*如果還有比mink更大的元素*/ { q=pnext。它們的值可以和表中的元素相同，也可以不同）。 newnext=pnext。 if(i==1) {/*插入在鏈表頭部*/ Newnext=*L。 【算法分析】 1）生成新結(jié)點(diǎn)存放元素b，由指針new指向； 2）將new插入在單鏈表的第i個(gè)元素的位置上：若i==1，new插在鏈表首部；否則查找第i1個(gè)結(jié)點(diǎn)，由指針p指向，然后將new插在p之后。/*由指針p指向ha的尾元結(jié)點(diǎn)*/ p=pnext。 /*當(dāng)兩個(gè)順序表可以互相比較的部分完全相同時(shí)，哪個(gè)較長(zhǎng)， 哪個(gè)就較大*/ }/*ListComp */3．已知指針 ha和 hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和n。i=。 【算法分析】比較順序表A和B，并用返回值表示結(jié)果，值為1，表示AB；值為1，表示AB；值為0，表示A=B。i) [i+1]=。 for(i=。 9．順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作（ ?。?【答案】√ 10．順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好（ ?。?【答案】 程序設(shè)計(jì)題1．設(shè)順序表va中的數(shù)據(jù)元素遞增有序。 sdata=_____________。 9．若要在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn)*p結(jié)點(diǎn)之前插入一個(gè)*s結(jié)點(diǎn)時(shí)，可執(zhí)行下列操作： snext=_____________。 【答案】（1）順序 （2）鏈?zhǔn)?5．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_____________，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_____________。 【答案】主要是使插入和刪除等操作統(tǒng)一，在第一個(gè)元素之前插入元素和刪除第一個(gè)結(jié)點(diǎn)不必另作判斷。 B）pprior=ppriorprior ppriornext=p。 qnext=p。 pnext=q。 ppriornext=q。 qnext=p。 A） O(0) B） O(1) C） O(n) D） O(n2) 【答案】C 3．雙向鏈表中有兩個(gè)指針域，prior和next，分別指向前驅(qū)及后繼，設(shè)p指向鏈表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為（ ） A） pprior=q。 B） qprior=pprior。 C） qnext=p。 D） ppriornext=q。 【答案】D 4．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是（ ） A）O(nlog2n） B） O(1） C） O(n） D） O(n2） 【答案】C 5． 在一個(gè)以 h 為頭指針的單循環(huán)鏈中，p 指針指向鏈尾結(jié)點(diǎn)的條件是（ ） A）pnext==NULL B） pnext==h C）pnextnext==h D） pdata==1 【答案】B 6．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的線性表，建立其單鏈表的時(shí)間復(fù)雜度是（ ） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 【答案】A 8．在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ） A）ppriornext=pnext pnextprior=pprior。 【答案】（n1）/2 2．在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_____________。 【答案】（1）數(shù)據(jù)元素的前后順序 （2）元素中的指針 4．當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行的是存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_____________存儲(chǔ)結(jié)構(gòu)最節(jié)省時(shí)間，相反當(dāng)經(jīng)常進(jìn)行插入和刪除操作時(shí)，則采用_____________存儲(chǔ)結(jié)構(gòu)最節(jié)省時(shí)間。 【答案】從任一結(jié)點(diǎn)出發(fā)都可訪問到鏈表中每一個(gè)元素。 pdata= _____________。 【答案】Lnextnext==L
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1