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

1、數(shù)據(jù)結(jié)構(gòu)第二章測試題復(fù)制您的姓名： 填空題 *_1.線性表是（）。 單選題A、一個(gè)有限序列，可以為空(正確答案)B、一個(gè)無限序列，不可以為空C、一個(gè)無限序列，可以為空D、一個(gè)無限序列，不可以為空2.在一個(gè)長度為n的順序表中刪除第i個(gè)元素(0=inext=s; s-prior=p; p-next-prior=s; s-next=p-next;B、s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;C、p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;D、s-prior=p; s-next=p-n

2、ext; p-next-prior=s; p-next=s;(正確答案)6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)(若存在)，則需修改指針的操作為（）。 單選題A、p-next=p-next-next;(正確答案)B、p=p-next;C、p=p-next-next;D、p-next=p;7.在一個(gè)長度為n的順序表中向第i個(gè)元素(0inext=p-next; p-next=sB、q-next=s; s-next=p(正確答案)C、p-next=s-next; s-next=pD、p-next=s; s-next=q9.以下關(guān)于線性表的說法，不正確的是（） 單選題A、線性表中的數(shù)據(jù)元素

3、可以是數(shù)字、字符、記錄等不同類型。B、線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C、線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前驅(qū)和直接后繼。(正確答案)D、存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前驅(qū)和直接后繼。10.線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。 單選題A、隨機(jī)存取(正確答案)B、順序存取C、索引存取D、散列存取11.在順序表中，只要知道（），就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。 單選題A、基地址B、結(jié)點(diǎn)大小C、向量大小D、基地址和結(jié)點(diǎn)大小(正確答案)12.在等概率情況下，順序表的插入操作要移動(dòng)（）結(jié)點(diǎn)。 單選題A、全部B、一半(正確答案)C、三分之一D、四分之一13.在（）運(yùn)算中，使

4、用順序表比鏈表好。 單選題A、插入B、刪除C、根據(jù)序號查找(正確答案)D、根據(jù)元素值查找14.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，并保持該表有序，其時(shí)間復(fù)雜度為（）。 單選題A、O(1)B、O(n)(正確答案)C、O(n2)D、O(log2n)15.對于順序表，以下說法錯(cuò)誤的是（）。 單選題A、順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對地址(正確答案)B、順序表的所有存儲結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C、順序表的特點(diǎn)是：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰D、順序表的特點(diǎn)是：邏輯上相鄰的元素，存儲在物理位置也相鄰的單元中16.對順序表上的插入

5、、刪除算法的時(shí)間復(fù)雜性分析來說，常以（）為標(biāo)準(zhǔn)操作。 單選題A、條件判斷B、結(jié)點(diǎn)移動(dòng)(正確答案)C、算術(shù)表達(dá)式D、賦值語句17.對于順序表的優(yōu)缺點(diǎn)，以下說法錯(cuò)誤的是（）。 單選題A、無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間B、可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)C、插入和刪除運(yùn)算較方便(正確答案)D、容易造成一部分空間長期閑置而得不到充分利用18.鏈表不具有的特點(diǎn)是（）。 單選題A、可隨機(jī)訪問任一個(gè)元素(正確答案)B、插入刪除不需要移動(dòng)元素C、不必事先估計(jì)存儲空間D、所需空間及線性表長度成正比19.若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采用（）存儲方式節(jié)省時(shí)間。 單選題A、單鏈

6、表B、雙向鏈表C、單循環(huán)鏈表D、順序表(正確答案)20.設(shè)指針p指向雙向鏈表的某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對稱性可用（）式來刻畫。 單選題A、p-prior-next = p-next-nextB、p-prior-prior = p-next-priorC、p-prior-next = p-next-prior(正確答案)D、p-next-next = p-prior-prior21.以下錯(cuò)誤的是（）。 單選題A、對循環(huán)鏈表來說，從表中任一結(jié)點(diǎn)出發(fā)，都能通過前后操作掃描整個(gè)循環(huán)鏈表(正確答案)B、對單鏈表來說，只有從頭結(jié)點(diǎn)開始才能掃描表中全部結(jié)點(diǎn)C、雙鏈表的特點(diǎn)：是找結(jié)點(diǎn)的前驅(qū)和后繼都很容易D、

7、對雙鏈表來說，結(jié)點(diǎn)*p的存儲位置既存放在其前驅(qū)結(jié)點(diǎn)的后繼指針域中，也存放在它的后繼結(jié)點(diǎn)的前驅(qū)指針域中。23.以下說法錯(cuò)誤的是（）。 單選題A、對于線性表來說，查找定位運(yùn)算在順序表和單鏈表上的量級均為O(n)B、讀表元運(yùn)算在順序表上只需常數(shù)時(shí)間O(1)便可實(shí)現(xiàn)，因此順序表是一種隨機(jī)存取結(jié)構(gòu)C、在鏈表上實(shí)現(xiàn)讀表元運(yùn)算的平均時(shí)間復(fù)雜性為O(1)(正確答案)D、插入、刪除操作在鏈表上的實(shí)現(xiàn)可在O(n)時(shí)間內(nèi)完成24.循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。 單選題A、不需要頭指針B、已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)C、從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表(正確答案)D、在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地

8、保證鏈表不斷開25.以下說法正確的是（）。 單選題A、線性結(jié)構(gòu)的基本特征是：每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼B、線性表的各種基本運(yùn)算在順序存儲結(jié)構(gòu)上的實(shí)現(xiàn)均比在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實(shí)現(xiàn)效率要低C、在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素位置有關(guān)(正確答案)D、順序存儲的線性表的插入和刪除操作不需要付出很大的代價(jià)，因此平均操作只有近一半的元素需要移動(dòng)31.設(shè)rear是指向非空帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，則刪除表頭結(jié)點(diǎn)的操作可表示為（）。 單選題A、p=rear; rear=rear-next;free(p);B、rear=rear-next; free(rear

9、);C、rear=rear-next-next;free(read);D、p=rear-next-next;rear-next-next=p-next;free(p);(正確答案)32.單鏈表中，增加頭結(jié)點(diǎn)的目的是為了（）。 單選題A、使單鏈表至少有一個(gè)結(jié)點(diǎn)B、標(biāo)示表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C、方便運(yùn)算的實(shí)現(xiàn)(正確答案)D、說明單鏈表是線性表的鏈?zhǔn)酱鎯?shí)現(xiàn)33.帶頭結(jié)點(diǎn)的單鏈表Head為空的判定條件是（）。 單選題A、Head=NULLB、Head-next=NULL(正確答案)C、Head-next=Head34.空的單循環(huán)鏈表L的尾結(jié)點(diǎn)*p，滿足（）。 單選題A、P-next=NULLB、P=NULLC、P-next=L(正確答案)35.單鏈表的每個(gè)結(jié)點(diǎn)中包括一個(gè)指針next，它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。現(xiàn)要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的單鏈表結(jié)點(diǎn)之后，下面的操作序列中哪一個(gè)是正確的？（）。 單選題A、p-next=q-next;q=p-nextB、p-next=q;q-next=p-next;C、q-next=p-next;p-next=q;(正確答案)D、q=p-next;p-next=q-next;36.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（）。 單選題A、p-nex