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