4、法？它有哪些特性4有下列幾種用二元組表示的數(shù)據(jù)結(jié)構(gòu)，畫出它們分別對(duì)應(yīng)的邏輯結(jié)構(gòu)圖，并指出它們分別以屬于何種結(jié)構(gòu)。（1）A=(K,R),其中K={a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(2)B=(K,R),其中K＝{a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(3)B=(K,R),其中K={1,2,3,4,5,6}R={r}r={(1,2),(
5、2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}三、計(jì)算題設(shè)n為整數(shù)，求下列各程序段的時(shí)間復(fù)雜度（1）i=1;k=2;While(ij)j=j+1;Elsei=i+1;(3)x=91;y=100While(y>0)If(x>100){x=x-10;y=y-1;}elsex=x+1;44習(xí)題2一、選擇題1線性表是（A）A一個(gè)有限序列，可以為空B一個(gè)有限序列，不能為空C一個(gè)無(wú)限序列，可以為空D一
6、個(gè)無(wú)限序列，不能為空2在一個(gè)長(zhǎng)度為n的順序表中，向第iI個(gè)元素（1≤i≤n+1）位置插入一個(gè)新元素時(shí)，需要從后向前依次后移（B）個(gè)元素。An-iBn-i+1Cn-i-1Di3在一個(gè)順序表的表尾插入一個(gè)元素的時(shí)間復(fù)度的量級(jí)為（B）。AO(n)BO(1)CO(n2)DO(logn)4表長(zhǎng)為n的順序存儲(chǔ)的線性表，當(dāng)在任意位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)為（D），刪除一個(gè)元素需要移動(dòng)元素的平均個(gè)數(shù)為（A）A(n-1)/2BnC(n+1)/2Dn/25設(shè)單鏈表中指針p指向結(jié)點(diǎn)a，若要?jiǎng)h除p之
7、后的結(jié)點(diǎn)（若存在），則需修改指針的操作為（A）。Ap->next=p->next->nextBp=p->nextCp=p->next->nextDnext=p6單鏈表的存儲(chǔ)密度為（C）。A大于1B等于5C小于1D不能確定7在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（B）個(gè)指針域的值。A1B2C3D48在一個(gè)單鏈表中，若要在p所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)，則此算法的時(shí)間復(fù)雜度的量級(jí)為（A）。AO(n)BO(n/2)CO(1)DO(n1/2)9在一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在p所指向的結(jié)點(diǎn)
8、之前插入一個(gè)新結(jié)點(diǎn)，則需要相繼修改（C）個(gè)指針域的值。A2B3C4D6二、簡(jiǎn)答題1什么叫線性表？它有哪些特點(diǎn)？2在鏈表的設(shè)計(jì)中，為什么通常采用帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)？3對(duì)比順序表與單鏈表，說(shuō)明順序表與單鏈表的主要優(yōu)點(diǎn)和主要缺點(diǎn)。444試編寫算法實(shí)現(xiàn)順序表的逆置，即把順序表A中的數(shù)據(jù)元素（a1,a2,…,an）逆置為（an
