數(shù)據(jù)結(jié)構(gòu)考試.題1

1、#要求：所有的題目的解答均寫在答題紙上，需寫清楚題目的序號(hào)。每張答題紙都要寫上姓名和學(xué)號(hào)。一、單項(xiàng)選擇題（每小題1.5分，共計(jì)30分）1.數(shù)據(jù)結(jié)構(gòu)是指。A.一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C.一組性質(zhì)相同的數(shù)據(jù)元素的集合D.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合2.以下算法的時(shí)間復(fù)雜度為。voidfun(intn)inti=1while(i1）個(gè)元素的線性表的運(yùn)算只有4種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前面插入新元

2、素；在最后一個(gè)元素的后面插入新元素，則最好使用以下哪種存儲(chǔ)結(jié)構(gòu)，并簡(jiǎn)要說(shuō)明理由。（1）只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的循環(huán)單鏈表（2）只有尾結(jié)點(diǎn)指針沒(méi)有頭結(jié)點(diǎn)指針的非循環(huán)雙鏈表（3）只有頭結(jié)點(diǎn)指針沒(méi)有尾結(jié)點(diǎn)指針的循環(huán)雙鏈表（4）既有頭結(jié)點(diǎn)指針也有尾結(jié)點(diǎn)指針的循環(huán)單鏈表2.已知一棵度為4的樹(shù)中，其度為0、1、2、3的結(jié)點(diǎn)數(shù)分別為14、4、3、2，求該樹(shù)的結(jié)點(diǎn)總數(shù)n和度為4的結(jié)點(diǎn)個(gè)數(shù)，并給出推導(dǎo)過(guò)程。3.有人提出這樣的一種從圖G中頂點(diǎn)u開(kāi)始構(gòu)

3、造最小生成樹(shù)的方法：假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖，T=(U，TE)是G的最小生成樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集，則由G構(gòu)造從起始頂點(diǎn)u出發(fā)的最小生成樹(shù)T的步驟如下：（1）初始化U=u。以u(píng)到其他頂點(diǎn)的所有邊為候選邊。（2）重復(fù)以下步驟n1次，使得其他n1個(gè)頂點(diǎn)被加入到U中。從候選邊中挑選權(quán)值最小的邊加入到TE，設(shè)該邊在VU中的頂點(diǎn)是v，將v加入U(xiǎn)中?？疾轫旤c(diǎn)v，將v與VU頂點(diǎn)集中的所有邊作為新的候選邊。若