1、2、單項選擇題 ：（本大題共 20 小題，每題 2 分，共 30 分）（說明： 將答案寫在試卷后面的答題紙上）分?jǐn)?shù)評卷人1計算機(jī)識別、存儲和加工處理的對象被統(tǒng)稱為（A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2在具有 n 個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并使鏈表仍然有序的時間復(fù)雜度是（ ）A.O（1）C.O（ nlogn）3.隊和棧的主要區(qū)別是（A.邏輯結(jié)構(gòu)不同C.所包含的運(yùn)算個數(shù)不同4.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是A.插入操作更加方便C.不會出現(xiàn)下溢的情況5下列說法中正確的是（）A.B.C.B.O( n)D.O (n2)B.存儲結(jié)構(gòu)不同D.限定插入和刪除的位置不同B.刪除操作更加方便

2、D.不會出現(xiàn)上溢的情況二叉樹中任何一個結(jié)點(diǎn)的度都為2二叉樹的度為 2任何一棵二叉樹中至少有一個結(jié)點(diǎn)的度為一棵二叉樹的度可以小于 2D.6在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）A.B.C.只有右子樹上的所有結(jié)點(diǎn)只有右子樹上的部分結(jié)點(diǎn)只有左子樹上的所有結(jié)點(diǎn)只有左子樹上的部分結(jié)點(diǎn)D.7在一個具有 N 個頂點(diǎn)的無向完全圖中，包含的邊的總數(shù)是（）A.B.C.N(N-1)/2N(N-1)N(N+1)N(N+1)/2D.8下面的程序在執(zhí)行時，S 語句共執(zhí)行的（）次。i=1;while （i=n）for（j=i;j n;j+）S；i=i+1;A. n(n+1)/2B. n(n-1)/2C. n!D.

3、n9設(shè)二叉樹有A. n-1n 個結(jié)點(diǎn)，則其深度為（）B. nC. 5log2n+1D.不確定210已知一棵二叉樹結(jié)點(diǎn)的先根序列為ABDGCFK，中根序列為 DGBAFCK，則結(jié)點(diǎn)的后根序列為（）A. ACFKBDG B. GDBFKCA C. KCFAGDB D. ABCDFKG11. 任何一個帶權(quán)的無向連通圖的最小生成樹（）A.只有一棵 B.有一棵或多棵C. 一定有多棵D.可能不存在12.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前序遍歷序列是 （）A.acbedB.decabC. deabcD.cedba13.設(shè)深度為 k 的二叉樹上只有度為 0 和度為 2

4、的結(jié)點(diǎn)，則這類二叉樹上所含結(jié)點(diǎn)總數(shù)量是（C）個A. k+1B. 2kC. 2k-114.下面程序的時間復(fù)雜性是()For(i=1;i=n ;i+)For(j=1;j=n ;j+) aij=i*j;2 2A. O(m)B. 0(n)C. O(m*n)15. 含 N 個頂點(diǎn)的連通圖中的任意一條簡單路徑，其長度不可能超過（）A. 1B. N/2C. N-1D. N16. 下列說法正確的是（A）A. 樹的先根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同B. 樹的先根遍歷序列與其對應(yīng)的二叉樹的后根遍歷序列相同C. 樹的后根遍歷序列與其對應(yīng)的二叉樹的先根遍歷序列相同D. 樹的后根遍歷序列與其對應(yīng)的二叉樹的后

5、根遍歷序列相同17. 對于一個具有 N 個結(jié)點(diǎn)和 E 條邊的無向圖，若采用鄰接表示，則表頭向量的大小是 （A）A. NB. N+1C. N-ED. N-118. 判斷一個有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ǎ€可以利用（）A. 求關(guān)鍵路徑的方法B. 求最短路徑的 Dijkstra 方法C. 廣度優(yōu)先遍歷方法D. 深度優(yōu)先遍歷方法19. 一個隊列的輸入序列是1,2,3,4,則隊列的輸出序列是（）（1）在線性表中插入或刪除一個元素，需要平均移動 與 有關(guān)。（2） 順序表中邏輯上相鄰的元素的物理位置 _緊鄰，單鏈表中邏輯上相鄰的元素物理位 置緊鄰。（3） 在單鏈表中，除了首元結(jié)點(diǎn)外，任意結(jié)點(diǎn)的存儲位置由 _指示。（4） 記錄的 _結(jié)構(gòu)是數(shù)據(jù)在物理存儲器上的存儲方式。D.2k+1D. O(m+n)A,4,3,2,1B.1,2,3,4C.1,4,3,220.任何一個帶權(quán)的無向連通圖的最小生成樹（B）A.只有一棵B.有一棵或多棵C. 一定有多棵、填空題（本大