數(shù)據(jù)結(jié)構(gòu)第二章試題

數(shù)據(jù)結(jié)構(gòu)第二章試題數(shù)據(jù)結(jié)構(gòu)第二章試題/NUMPAGES9數(shù)據(jù)結(jié)構(gòu)第二章試題數(shù)據(jù)結(jié)構(gòu)第二章試題第2章線性表一、選擇題1.鏈表不具備的特點(diǎn)是（）。A．可隨機(jī)訪問(wèn)任意結(jié)點(diǎn) B.插入刪除不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與其長(zhǎng)度成正比2.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL3.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL4．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是（）。A．L==NULLB．L->next->==NULLC．L->prior==NULLD.L->next==L5.非空的循環(huán)鏈表head的尾結(jié)點(diǎn)（由P所指向）滿足（）。A．p->next==NULLB．p==NULLC．p->next==headD.p==head6.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是（）。A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;D.s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;7.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．給出表頭指針的單循環(huán)鏈表C．雙鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表8.某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)節(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，故采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表 B．僅有頭結(jié)點(diǎn)的單循環(huán)鏈表C．雙鏈表D.僅有尾指針的單循環(huán)鏈表9.需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是（）。A．單鏈表B．靜態(tài)鏈表C．線性鏈表D.順序存儲(chǔ)結(jié)構(gòu)10.如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及前驅(qū)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表 B．雙鏈表C.單循環(huán)鏈表D.順序表11.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是（）。A．O(1)B．O(n)C．O(n*n)D.O(nlog2n)12.在一個(gè)長(zhǎng)度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行()操作與鏈表的長(zhǎng)度有關(guān)。A．刪除單鏈表中的第一個(gè)元素 B．刪除單鏈表中的最后一個(gè)元素C.在單鏈表第一個(gè)元素前插入一個(gè)新元素D.在單鏈表最后一個(gè)元素后插入一個(gè)新元素13.設(shè)線性表有n個(gè)元素，以下算法中，()在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A．輸出第i(0<=i<=n-1)個(gè)元素值B．交換第0個(gè)元素與第1個(gè)元素的值C.順序輸出這n個(gè)元素的值D.輸出與給定值x相等的元素在線性表中的序號(hào)14.設(shè)線性表有2n個(gè)元素，算法()，在單鏈表上實(shí)現(xiàn)比在順序表上實(shí)現(xiàn)效率更高。A．刪除所有值為x的元素 B．在最后一個(gè)元素的后面插入一個(gè)新元素C.順序輸出前k個(gè)元素D.交換第i個(gè)元素和第2n-i-1個(gè)元素的值(i=0,1,…,n-1)15.與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是()。A．插入、刪除操作更簡(jiǎn)單 B．可以進(jìn)行隨機(jī)訪問(wèn)C.可以省略表頭指針或表尾指針D.順序訪問(wèn)相臨結(jié)點(diǎn)更靈活16.如果對(duì)線性表的運(yùn)算只有4種，即刪除第一個(gè)元素，刪除最后一個(gè)元素，在第一個(gè)元素前面插入新元素，在最后一個(gè)元素的后面插入新元素，則最好使用().A．只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表B．只有表尾指針沒(méi)有表頭指針的非循環(huán)雙鏈表C．只有表頭指針沒(méi)有表尾指針的循環(huán)雙鏈表D．既有表頭指針也有表尾指針的循環(huán)單鏈表17.如果對(duì)線性表的運(yùn)算只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用()。A．只有表頭指針沒(méi)有表尾指針的循環(huán)單鏈表B．非循環(huán)雙鏈表C.只有表尾指針沒(méi)有表頭指針的循環(huán)單鏈表D.循環(huán)雙鏈表18.設(shè)兩個(gè)長(zhǎng)度為n的單鏈表，結(jié)點(diǎn)類型相同。若以h1為表頭指針的鏈表是非循環(huán)的，以h2為表頭指針的鏈表是循環(huán)的，則()。A．對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除第一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(1)B．對(duì)于兩個(gè)鏈表來(lái)說(shuō)，刪除最后一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度都是O(n)C.循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間D.h1和h2是不同類型的變量19.在長(zhǎng)度為n的()上，刪除第一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為O(n)。A．只有表頭指針的不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表B．只有表尾指針的不帶表頭結(jié)點(diǎn)的循環(huán)單鏈表C.只有表尾指針的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表D.只有表頭指針的帶表頭結(jié)點(diǎn)的循環(huán)單鏈表二、填空題1.向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素(0<=i<=n-1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)____個(gè)元素。2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0<=i<=n-1)時(shí)，需向前移動(dòng)____個(gè)元素。3.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用____。4.在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的____結(jié)點(diǎn)。5.訪問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著____依次進(jìn)行。6.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向____，另一個(gè)指向____。7.在____鏈表上，刪除最后一個(gè)結(jié)點(diǎn)其算法的時(shí)間復(fù)雜度為O(1)。8.在非循環(huán)的____鏈表中，可以用表尾指針代替表頭指針。9.在一個(gè)單鏈表中的p所指結(jié)點(diǎn)之前插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行如下操作：(1)s->next=____;(2)p->next=s;(3)t=p->data;(4)p->data=____;(5)s->data=____;10.在一個(gè)單鏈表中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作:Q=p->next;p->data=p->next->data;p->next=____;free(q);11.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=____和p->next____的操作。12.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在*p結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是____;在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是____。三、簡(jiǎn)答題1.簡(jiǎn)述順序表和鏈表存儲(chǔ)方式的特點(diǎn)。2.若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)，為什么？3.對(duì)鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么？4.在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭結(jié)點(diǎn)指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去？若可以，其時(shí)間復(fù)雜度各為多少？5.下列說(shuō)法哪些是錯(cuò)誤的？(1)靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)，又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無(wú)關(guān)。(2)靜態(tài)鏈表中能容納的元素個(gè)數(shù)的最大數(shù)在定義時(shí)就確定了，以后不能增加。(3)靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需要元素的移動(dòng)。四、算法設(shè)計(jì)題1.已知一個(gè)順序表L，其