浙江理工大學(xué)2019級(jí)數(shù)據(jù)結(jié)構(gòu)試題及答案試卷一、

單選題（每題2分，共20分）1.

對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。A．健壯性和可讀性B．并行性C．正確性D．時(shí)空復(fù)雜度2.

在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.

對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？()A.經(jīng)常需要隨機(jī)地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4.

一個(gè)棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是()A.231 B.321C.312 D.1235.

AOV網(wǎng)是一種（）。A．有向圖B．無(wú)向圖C．無(wú)向無(wú)環(huán)圖D．有向無(wú)環(huán)圖7.

若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（）參數(shù)。A．值B．函數(shù)C．指針D．引用8.

在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）。A．行號(hào)B．列號(hào)C．元素值D．非零元素個(gè)數(shù)二、

填空題（每空1分，共28分）1.

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_____________________。2.

隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。3.

當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件是___top==0_____________。4.

對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_________，在表尾插入元素的時(shí)間復(fù)雜度為____________。7.

二叉樹是指度為2的____________________樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是_____________。8.

對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)______________。對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。9.

對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為_____________個(gè)，其中_______________個(gè)用于指向孩子，_________________個(gè)指針是空閑的。10.

若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類推，則A[i]元素的左孩子元素為________,右孩子元素為_______________，雙親元素為____________。11.

在線性表的散列存儲(chǔ)中，處理沖突的常用方法有________________________和_____________________________兩種。

三、

運(yùn)算題（每題6分，共24分）1.

已知一個(gè)6′5稀疏矩陣如下所示，試：（1）

寫出它的三元組線性表；（2）

給出三元組線性表的順序存儲(chǔ)表示。2.

設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。3.

對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出：從頂點(diǎn)①出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；從頂點(diǎn)②出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；圖64.

已知一個(gè)圖的頂點(diǎn)集V和邊集圖6V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。四、閱讀算法（每題7分，共14分）1.

intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}指出該算法的功能；(2)

該算法的時(shí)間復(fù)雜度是多少？2.

寫出下述算法的功能：voidAJ(adjlistGL,inti,intn){QueueQ; InitQueue(Q); cout<<i<<''; visited[i]=true; QInsert(Q,i);while(!QueueEmpty(Q)){ intk=QDelete(Q); edgenode*p=GL[k]; while(p!=NULL) {intj=p->adjvex; if(!visited[j]){cout<<j<<''; visited[j]=true; QInsert(Q,j);} p=p->next;}}}HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。ElemTypeDeleFront(LNode*&HL)參考答案一、單選題（每題2分，共20分）1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C二、

填空題（每空1分，共26分）1.

聯(lián)系圖（或圖結(jié)構(gòu)）2.

尾首3.

top==04.

O（1）O（n）5.

128441086.

337.

65565515132-145-2515637圖78.

有序序列后綴表達(dá)式（或逆波蘭式）9.

2nn-1n+110.

2i+12i+2(i-1)/211.

開放定址法鏈接法12.

快速歸并三、

運(yùn)算題（每題6分，共24分）1.

（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)圖8（2）三元組線性表的順序存儲(chǔ)表示如圖7圖82.

如圖8所示。3.

DFS：????…BFS：???…?4.

拓樸排序?yàn)椋?365721四、

閱讀算法（每題7分，共14分）1.

(1)判斷n是否是素?cái)?shù)（或質(zhì)數(shù)）（2）O（）2.

功能為：從初始點(diǎn)vi出發(fā)廣度