全國(guó)2012年1月自考《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》試題
課程代碼：02142 
一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)
在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。
1.結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈”的數(shù)據(jù)結(jié)構(gòu)是(      )
A.集合                                                            B.線性結(jié)構(gòu) 
C.樹(shù)形結(jié)構(gòu)                                                     D.圖狀結(jié)構(gòu)
2.下面算法程序段的時(shí)間復(fù)雜度為(      )
for ( int i=0; i<m; i++)
for ( int j=0; j<n; j++)
a［i］［j］=i*j;
A. O(m2)                                                        B. O(n2)  
C. O(mn)                                                        D. O(m+n) 
3.線性結(jié)構(gòu)是(      )
A.具有n（n≥0）個(gè)表元素的有窮序列              B.具有n（n≥0）個(gè)字符的有窮序列
C.具有n（n≥0）個(gè)結(jié)點(diǎn)的有窮序列                 D.具有n（n≥0）個(gè)數(shù)據(jù)項(xiàng)的有窮序列 
4.單鏈表中刪除由某個(gè)指針變量指向的結(jié)點(diǎn)的直接后繼，該算法的時(shí)間復(fù)雜度是(      ) 
A. O(1)                                                           B. O( ) 
C. O(log2n)                                                      D. O(n)
5.關(guān)于串的敘述，正確的是(      ) 
A.串是含有一個(gè)或多個(gè)字符的有窮序列 
B.空串是只含有空格字符的串
C.空串是含有零個(gè)字符或含有空格字符的串
D.串是含有零個(gè)或多個(gè)字符的有窮序列
6.棧的輸入序列依次為1，2，3，4，則不可能的出棧序列是(      )
A.1243                                                            B. 1432 
C. 2134                                                           D.4312
7.隊(duì)列是(      )
A. 先進(jìn)先出的線性表                                     B. 先進(jìn)后出的線性表 
C. 后進(jìn)先出的線性表                                      D.隨意進(jìn)出的線性表
8.10階上三角矩陣壓縮存儲(chǔ)時(shí)需存儲(chǔ)的元素個(gè)數(shù)為(      )
A.11                                                                B.56 
C.100                                                              D.101
9.深度為k（k≥1）的二叉樹(shù)，結(jié)點(diǎn)數(shù)最多有(      )
A.2k 個(gè)                                                            B.(2k -1)個(gè) 
C.2k-1個(gè)                                                         D.(2k+1)個(gè)
10.具有12個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中，空鏈域NULL的個(gè)數(shù)為(      )
A. 11                                                              B.13  
C. 23                                                              D. 25