山大網(wǎng)絡(luò)《數(shù)據(jù)結(jié)構(gòu)》試卷( B 卷)

山大網(wǎng)絡(luò)《數(shù)據(jù)結(jié)構(gòu)》試卷(B卷)山大網(wǎng)絡(luò)《數(shù)據(jù)結(jié)構(gòu)》試卷(B卷)山大網(wǎng)絡(luò)《數(shù)據(jù)結(jié)構(gòu)》試卷(B卷)資料僅供參考文件編號(hào)：2022年4月山大網(wǎng)絡(luò)《數(shù)據(jù)結(jié)構(gòu)》試卷(B卷)版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：《數(shù)據(jù)結(jié)構(gòu)》試卷（B卷）一、單項(xiàng)選擇題1.線(xiàn)性表是__A___。A．一個(gè)有限序列，可以為空 B．一個(gè)有限序列，不可以為空C．一個(gè)無(wú)限序列，可以為空 D．一個(gè)無(wú)限序列，不可以為空2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0<=i<=n)時(shí)，需向前移動(dòng)A個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i3.線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址_D___。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以4.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較___C_個(gè)元素結(jié)點(diǎn)。A．n/2 B．n C．（n+1）/2 D．（n-1）/25.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是_AD。A．p->next=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->next;p->next->prior=s;p->next=s;6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為_(kāi)_A___。A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;7.在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0<i<n+l)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)__B_個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i8.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行BA．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9.以下關(guān)于線(xiàn)性表的說(shuō)法不正確的是_C__。

A．線(xiàn)性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類(lèi)型。B．線(xiàn)性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C．線(xiàn)性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D．存在這樣的線(xiàn)性表：表中各結(jié)點(diǎn)都沒(méi)有直接前趨和直接后繼。10.線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種__A____的存儲(chǔ)結(jié)構(gòu)。

A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取11.在順序表中，只要知道__D___，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A．基地址 B．結(jié)點(diǎn)大小C．向量大小 D．基地址和結(jié)點(diǎn)大小12.在等概率情況下，順序表的插入操作要移動(dòng)__B__結(jié)點(diǎn)。

A．全部 B．一半

C．三分之一

D．四分之一13.在_C_運(yùn)算中，使用順序表比鏈表好。

A．插入

B．刪除

C．根據(jù)序號(hào)查找

D．根據(jù)元素值查找14.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是__B___。

A．O(1)

B．O(n)

C．O(n2) D．O(log2n)15.設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列___C_____。A．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,D D．E,D,C,B,A16.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為_(kāi)_C___。A．top不變 B．top=0 C．top-- D．top++17.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行_B__。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;18.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿(mǎn)的條件為_(kāi)_D___。A．rear％n==front B．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front二、填空題1.線(xiàn)性表是一種典型的_線(xiàn)性結(jié)構(gòu)__結(jié)構(gòu)。2.在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移_n-i+1_個(gè)元素。3.順序表中邏輯上相鄰的元素的物理位置_必定相鄰_。4.要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需前移一個(gè)位置，移動(dòng)過(guò)程是從_前____向__后___依次移動(dòng)每一個(gè)元素。5.在線(xiàn)性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)__物理存儲(chǔ)位置___決定的；在線(xiàn)性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)鏈域的指針值決定的。6.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向__前趨__結(jié)點(diǎn)，另一個(gè)指向_后繼___結(jié)點(diǎn)。7.當(dāng)對(duì)一個(gè)線(xiàn)性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用__順序__存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用__鏈接_存儲(chǔ)結(jié)構(gòu)為宜。8.順序表中邏輯上相鄰的元素，物理位置__一定_相鄰，單鏈表中邏輯上相鄰的元素，物理位置_不一定__相鄰。9.線(xiàn)性表、棧和隊(duì)列都是__線(xiàn)性__結(jié)構(gòu)，可以在線(xiàn)性表的_任何_位置插入和刪除元素；對(duì)于棧只能在_棧頂__位置插入和刪除元素；對(duì)于隊(duì)列只能在_隊(duì)尾__位置插入元素和在隊(duì)頭位置刪除元素。10.根據(jù)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_(kāi)_單鏈表___和__雙鏈表__；而根據(jù)指針的聯(lián)接方式，鏈表又可分為_(kāi)_非循環(huán)鏈表__和__循環(huán)鏈表__。11.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是_使空表和非空表統(tǒng)一；算法處理一致__。12.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)O(1)__，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)_O(n)__。13.對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_(kāi)棧滿(mǎn)__，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_(kāi)_?？誣__，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明棧的可用最大容量為_(kāi)_m____。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的_棧底___分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)___兩個(gè)棧的棧頂在?？臻g的某一位置相遇____時(shí)才產(chǎn)生上溢。三、簡(jiǎn)答題1.描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。答：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱(chēng)為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線(xiàn)性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線(xiàn)性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2.線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？

答：線(xiàn)性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。3.對(duì)于線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)，如果有n個(gè)線(xiàn)性表同時(shí)并存，而且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線(xiàn)性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)為什么答：應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4.對(duì)于線(xiàn)性表的兩種存儲(chǔ)