點擊查看：2015年計算機二級公共基礎(chǔ)知識考點測試題匯總
線性鏈表
1[單選題]對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是( )
A.冒泡排序為n/2
B.冒泡排序為n
C.快速排序為n
D.快速排序為n(n-1)/2
參考答案：D
參考解析：對于長度為n的線性表，在最壞情況下，冒泡排序需要進(jìn)行的比較次數(shù)是n(n—1)/2，快速排序需要進(jìn)行的比較次數(shù)是n(n-1)/2，簡單插入排序需要進(jìn)行的比較次數(shù)是n(n—1)/2，希爾排序需要進(jìn)行的比較次數(shù)是0(n1 5)，簡單選擇排序需要進(jìn)行的比較次數(shù)是n(n-1)/2，堆排序需要進(jìn)行的比較次數(shù)是0(nl092n)。因此選項D正確。
2[單選題]在長度為n的有序線性表中進(jìn)行二分查找，最壞情況下需要較的次數(shù)是( )。
參考答案：C
參考解析：對于長度為n的線性表進(jìn)行順序查找，平均要進(jìn)行n/2次比較，在最壞情況下要進(jìn)行n次比較;對于長度為n的線性表進(jìn)行二分查找，在最壞情況下要進(jìn)行l(wèi)092n次比較(但二分查找要求線性表是順序存儲的有序表)。因此本題的正確答案是C。
3[單選題]已知線性表的首元素的地址是1025，每個數(shù)據(jù)元素的長度為2，則第10個兀素的地址為( )
A.1035B.1045C.1027D.1043
參考答案：D
4[單選題]在長度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為( )。
參考答案：B
參考解析：
5[填空題]線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊列是一種特殊的線性表，循環(huán)隊列是隊列的( )存儲結(jié)構(gòu)。
參考解析：順序
【分析】在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。
6[填空題]數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于________。
參考解析：線性【分析】帶鏈的隊列如下圖l.16所示。從圖中可以看出帶鏈的隊是線性結(jié)構(gòu)。總結(jié)：常用的數(shù)據(jù)結(jié)構(gòu)比如：線性表、棧、隊列是線性結(jié)構(gòu)(不管是采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu));樹、二叉樹、圖都是非線性結(jié)構(gòu)(不管是采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu))。
7[填空題]對長度為l0的線性表進(jìn)行冒泡排序，最壞情況下需要比較的次數(shù)為________。
參考解析：45
【分析】假設(shè)線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要比較的次數(shù)為n(n-1)/2。因此本題的正確答案是10x(10—1)÷2=45。
8[單選題]在線性鏈表的插入算法中，若要把結(jié)點q插在結(jié)點P后面，下列操作正確的是：( )
A.使結(jié)點P指向結(jié)點q，再使結(jié)點q指向結(jié)點P的后件結(jié)點
B.使結(jié)點q指向P的后件結(jié)點，再使結(jié)點P指向結(jié)點q
C.使結(jié)點q指向結(jié)點P，再使結(jié)點P指向結(jié)點q的后件結(jié)點
D.使結(jié)點P指向q的后件結(jié)點，再使結(jié)點q指向結(jié)點P
參考答案：B
參考解析：在修改結(jié)點指針域的操作中，有一個操作順序的問題。比較選項A和B只是操作順序顛倒了-下。A中先使結(jié)點p指向q后，q就成為P新的后件結(jié)點了，原先通過結(jié)點P指向的后件結(jié)點與結(jié)點P脫節(jié)了那么后面的-步操作沒有任何意義的：使結(jié)點q指向P的后件結(jié)點即使結(jié)點q成為自己的后件結(jié)點。按照B指定的順序操作就不會出現(xiàn)在引用結(jié)點p的指針域之前已經(jīng)把它的值修改了的情形。至于C和D項是命題者設(shè)計的干擾項想讓考生把P和(1的順序搞混。
總結(jié)，做這種類型的試題，最好畫圖。插入結(jié)點：若結(jié)點p的后面是結(jié)點s，要在p和s之間插入結(jié)點q，-般先將結(jié)點q指向結(jié)點s，再將結(jié)點p指向q，順序不能顛倒。刪除結(jié)點：若結(jié)點p的后面是結(jié)點q.結(jié)點q的后面是結(jié)點s，若要刪除結(jié)點q，只需將結(jié)點p指向結(jié)點s即可。
9[單選題]在一個n×m的二維線性表中順序查找一個數(shù)據(jù)元素的算法時間復(fù)雜度是( )
A.O(n+m)B.O(n×m)C.O(n2)D.O(m2)
參考答案：B
參考解析：在-維線性表中順序查找一個數(shù)據(jù)元素的算法時間復(fù)雜度是O(n)，其中n是線性表的長度二維線性表的順序查找方法和-維線性表相似，只不過是多了-維罷了。在二維表中進(jìn)行順序查找有兩個方法：-是把二維線性表看成是n個長度為m的-維線性表，順序查找就是對這n個-維線性表依次實施順序查找，因此它的算法時間復(fù)雜度是O(n)×o(m)=o(n×m);二是直接把n×m的二維線性表看成一個n×m的-維線性表，那么在它當(dāng)中用順序查找法查捧一個元素的算法時間復(fù)雜度是O(n×m)。
10[單選題]下列對于線性鏈表的描述中正確的是( )。
參考答案：A
參考解析：線性鏈表是通過增加一個指針域來把相鄰的數(shù)據(jù)元素鏈接成一個線性序列。線性鏈表的這種結(jié)構(gòu)使得它存儲數(shù)據(jù)的空間可以是離散的，并不像順序表那樣一定要求物理上的連續(xù)空間。因此選項A正確n
11[單選題]在線性鏈表的插入算法中，若要把結(jié)點q插在結(jié)點P后面，下列操作正確的是( )。
參考答案：B
參考解析：
12[單選題]在一個n×m的二維線性表中順序查找一個數(shù)據(jù)元素的算法時間復(fù)雜度是( )。
參考答案：B
參考解析：
13[填空題]已知線性表的每個元素占2個字節(jié)，它的第5個元素在內(nèi)存中的存儲地址是1005，那么它的第2個元素在內(nèi)存中的存儲地址是________。
答案：999
14[填空題]線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。隊列是-種特殊的線性表，循環(huán)隊列是隊列的________存儲結(jié)構(gòu)。
參考解析：順序【分析】在實際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)-般采用循環(huán)隊列的形式。
15[單選題]已知線性表的首元素的地址是1025，每個數(shù)據(jù)元素的長度為2，則第10個兀素的地址為( )。
參考答案：D
16[單選題]下列關(guān)于鏈表結(jié)構(gòu)的敘述正確的是( )。
參考答案：A
17[單選題]下列敘述中正確的是( )。【考點5鏈表】
A.棧是“先進(jìn)先出”的線性表
B.隊列是“先進(jìn)后出”的線性表
C.循環(huán)隊列是非線性結(jié)構(gòu)
D.有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)
參考答案：D
參考解析：本題主要考查了棧、隊列、循環(huán)隊列的概念，棧是先進(jìn)后出的線性表，隊列是先進(jìn)先出的線性表。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。有序線性表既可以采用順序存儲結(jié)構(gòu)，又可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。
18[單選題]在表示樹的多重鏈表中，除了要存儲結(jié)點的值和多個指針之外，還必須需要存儲( )。
參考答案：A
相關(guān)推薦：
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
