1、2013年“數據結構與C程序設計”(代碼991)試題一、單項選擇題（本題共一、單項選擇題（本題共20分，每小題各分，每小題各2分）分）1對于長度為n的線性表，建立其對應的單鏈表的時間復雜度為()。AO(1)；BO(log2n)；O(n)；DO(n2)。2一般情況下，在一個雙向鏈表中插入一個新的鏈結點，()。A需要修改4個指針域內的指針；B需要修改3個指針域內的指針；C需要修改2個指針域內的指針；D只需要修改1個指針域內的指針。3假設用單

2、個字母表示中綴表達式中的一個運算數(或稱運算對象)，并利用堆棧產生中綴表達式對應的后綴表達式。對于中綴表達式AB(CDE)，當從左至右掃描到運算數E時，堆棧中的運算符依次是()。(注：不包含表達式的分界符)A；B(；C；(。4若某二叉排序樹的前序遍歷序列為50204030806070，則后序遍歷序列為()。A30402050706080；B30402070608050；C70608050304020；D70608030402050。5分

3、別以6381257對應葉結點的權值構造的哈夫曼(Huffman)樹的深度為()。A6；B5；C4；D3。6下列關于圖的敘述中，錯誤的是()。A根據圖的定義，圖中至少有一個頂點；B根據圖的定義，圖中至少有一個頂點和一條邊(弧)；C具有n個頂點的無向圖最多有n(n1)2條邊；D具有n個頂點的有向圖最多有n(n1)條邊(弧)。7若在有向圖G的拓撲序列中，頂點vi在頂點vj之前，則下列4種情形中不可能出現的是()。AG中有??；BG中沒有弧；CG

4、中有一條從頂點vi到頂點vj的路徑；DG中有一條從頂點vj到頂點vi的路徑。8下列關于查找操作的敘述中，錯誤的是()。A在順序表中查找元素可以采用順序查找法，也可以采用折半查找法；B在鏈表中查找結點只能采用順序查找法，不能采用折半查找法；C一般情況下，順序查找法不如折半查找法的時間效率高；D折半查找的過程可以用一棵稱之為“判定樹”的二叉樹來描述。9在一棵m階B樹中，除根結點之外的任何分支結點包含關鍵字的個數至少是()。Am21；Bm2；

5、Cm21；Dm2。10若對序列(4938659776132749’)進行快速排序，則第一趟排序結束(即確定了第1個分界元素的最終位置)時，序列的狀態(tài)是()。A(132749’3849769765)；B(13382749’49769765)；C(133849’2749977665)；D(133849’2749769765)。二、填空題二、填空題(本題共本題共20分，每小題各分，每小題各2分)1非空線性表在采()存儲結構的情況下，刪除表的一

6、個數據元素平均需要移動表中近一半元素的位置。2將一個長度為n的單鏈表鏈接到一個長度為m的單鏈表后面，該算法的時間復雜度用大O符號表示為()。四、算法設計題（本題四、算法設計題（本題15分）分）假設長度為n的順序表A[1..n]中每個數據元素為一整數，請寫出按照下列思想將表中數據元素按值從小到大進行排序的算法：第1趟排序將最小值元素放在A[1]中，最大值元素放在A[n]中；第2趟排序將次小值元素放在A[2]中，次大值元素放在A[n1]中；

7、……，依此下去，直至排序結束。五、填空題五、填空題(本題共本題共20分，每小題各分，每小題各2分)1已知某等比數列的第一項a1為1，公比為3，下列程序的功能是輸出該數列中小于1000的最大項an及其對應的n。請在程序的空白處(符號處)填入合適內容，使程序完整。main()intn=1a=1q=3while(1)a=aqnif(a=1000)printf(“n=%da=%dn”n1)2下列遞歸函數FUNC2的功能是判斷整型數組a[n]是否

8、為遞增數組，即判斷數組的元素是否按值從小到大排列。若是一個遞增數組，則函數返回true，否則，函數返回false。請在函數的空白處(符號處)填入合適內容，使函數完整。boolFUNC2(inta[]intn)if(n==1)returntrueif(n==2)returnreturn3下列程序的功能是主函數調用FUNC3函數求方陣a中兩條對角線上元素之和。請在程序的空白處(符號處)填入合適內容，使程序完整。#defineN10voidF