數(shù)據(jù)結構考試.題1

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

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

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