數(shù)據(jù)結(jié)構(gòu)與算法的習(xí)題

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

2、D.不會(huì)出現(xiàn)上溢的情況二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2二叉樹(shù)的度為 2任何一棵二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為一棵二叉樹(shù)的度可以小于 2D.6在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊（）A.B.C.只有右子樹(shù)上的所有結(jié)點(diǎn)只有右子樹(shù)上的部分結(jié)點(diǎn)只有左子樹(shù)上的所有結(jié)點(diǎn)只有左子樹(shù)上的部分結(jié)點(diǎn)D.7在一個(gè)具有 N 個(gè)頂點(diǎn)的無(wú)向完全圖中，包含的邊的總數(shù)是（）A.B.C.N(N-1)/2N(N-1)N(N+1)N(N+1)/2D.8下面的程序在執(zhí)行時(shí)，S 語(yǔ)句共執(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è)二叉樹(shù)有A. n-1n 個(gè)結(jié)點(diǎn)，則其深度為（）B. nC. 5log2n+1D.不確定210已知一棵二叉樹(shù)結(jié)點(diǎn)的先根序列為ABDGCFK，中根序列為 DGBAFCK，則結(jié)點(diǎn)的后根序列為（）A. ACFKBDG B. GDBFKCA C. KCFAGDB D. ABCDFKG11. 任何一個(gè)帶權(quán)的無(wú)向連通圖的最小生成樹(shù)（）A.只有一棵 B.有一棵或多棵C. 一定有多棵D.可能不存在12.已知某二叉樹(shù)的后序遍歷序列是dabec,中序遍歷序列是debac,則它的前序遍歷序列是 （）A.acbedB.decabC. deabcD.cedba13.設(shè)深度為 k 的二叉樹(shù)上只有度為 0 和度為 2

4、的結(jié)點(diǎn)，則這類二叉樹(shù)上所含結(jié)點(diǎn)總數(shù)量是（C）個(gè)A. k+1B. 2kC. 2k-114.下面程序的時(shí)間復(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 個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)（）A. 1B. N/2C. N-1D. N16. 下列說(shuō)法正確的是（A）A. 樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同B. 樹(shù)的先根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷序列相同C. 樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的先根遍歷序列相同D. 樹(shù)的后根遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的后

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