點擊查看：2015年計算機二級公共基礎知識考點測試題匯總

　　線性鏈表

　　1[單選題]對于長度為n的線性表，在最壞情況下，下列各排序法所對應的比較次數(shù)中正確的是(　　)

　　A.冒泡排序為n/2

　　B.冒泡排序為n

　　C.快速排序為n

　　D.快速排序為n(n-1)/2

　　參考答案：D

　　參考解析：對于長度為n的線性表，在最壞情況下，冒泡排序需要進行的比較次數(shù)是n(n—1)/2，快速排序需要進行的比較次數(shù)是n(n-1)/2，簡單插入排序需要進行的比較次數(shù)是n(n—1)/2，希爾排序需要進行的比較次數(shù)是0(n1 5)，簡單選擇排序需要進行的比較次數(shù)是n(n-1)/2，堆排序需要進行的比較次數(shù)是0(nl092n)。因此選項D正確。

　　2[單選題]在長度為n的有序線性表中進行二分查找，最壞情況下需要較的次數(shù)是(　　)。

　　參考答案：C

　　參考解析：對于長度為n的線性表進行順序查找，平均要進行n/2次比較，在最壞情況下要進行n次比較;對于長度為n的線性表進行二分查找，在最壞情況下要進行l(wèi)092n次比較(但二分查找要求線性表是順序存儲的有序表)。因此本題的正確答案是C。

　　3[單選題]已知線性表的首元素的地址是1025，每個數(shù)據(jù)元素的長度為2，則第10個兀素的地址為(　　)

　　A.1035B.1045C.1027D.1043

　　參考答案：D

　　4[單選題]在長度為64的有序線性表中進行順序查找，最壞情況下需要比較的次數(shù)為(　　)。

　　參考答案：B

　　參考解析：

　　5[填空題]線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。隊列是一種特殊的線性表，循環(huán)隊列是隊列的(　　)存儲結構。

　　參考解析：順序

　　【分析】在實際應用中，隊列的順序存儲結構一般采用循環(huán)隊列的形式。

　　6[填空題]數(shù)據(jù)結構分為線性結構和非線性結構，帶鏈的隊列屬于________。

　　參考解析：線性【分析】帶鏈的隊列如下圖l.16所示。從圖中可以看出帶鏈的隊是線性結構�？偨Y：常用的數(shù)據(jù)結構比如：線性表、棧、隊列是線性結構(不管是采用順序存儲結構還是鏈式存儲結構);樹、二叉樹、圖都是非線性結構(不管是采用順序存儲結構還是鏈式存儲結構)。

　　7[填空題]對長度為l0的線性表進行冒泡排序，最壞情況下需要比較的次數(shù)為________。

　　參考解析：45

　　【分析】假設線性表的長度為n，則在最壞情況下，冒泡排序需要經(jīng)過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要比較的次數(shù)為n(n-1)/2。因此本題的正確答案是10x(10—1)÷2=45。

　　8[單選題]在線性鏈表的插入算法中，若要把結點q插在結點P后面，下列操作正確的是：(　　)

　　A.使結點P指向結點q，再使結點q指向結點P的后件結點

　　B.使結點q指向P的后件結點，再使結點P指向結點q

　　C.使結點q指向結點P，再使結點P指向結點q的后件結點

　　D.使結點P指向q的后件結點，再使結點q指向結點P

　　參考答案：B

　　參考解析：在修改結點指針域的操作中，有一個操作順序的問題。比較選項A和B只是操作順序顛倒了-下。A中先使結點p指向q后，q就成為P新的后件結點了，原先通過結點P指向的后件結點與結點P脫節(jié)了那么后面的-步操作沒有任何意義的：使結點q指向P的后件結點即使結點q成為自己的后件結點。按照B指定的順序操作就不會出現(xiàn)在引用結點p的指針域之前已經(jīng)把它的值修改了的情形。至于C和D項是命題者設計的干擾項想讓考生把P和(1的順序搞混。

　　總結，做這種類型的試題，最好畫圖。插入結點：若結點p的后面是結點s，要在p和s之間插入結點q，-般先將結點q指向結點s，再將結點p指向q，順序不能顛倒。刪除結點：若結點p的后面是結點q.結點q的后面是結點s，若要刪除結點q，只需將結點p指向結點s即可。

　　9[單選題]在一個n×m的二維線性表中順序查找一個數(shù)據(jù)元素的算法時間復雜度是(　　)

　　A.O(n+m)B.O(n×m)C.O(n2)D.O(m2)

　　參考答案：B

　　參考解析：在-維線性表中順序查找一個數(shù)據(jù)元素的算法時間復雜度是O(n)，其中n是線性表的長度二維線性表的順序查找方法和-維線性表相似，只不過是多了-維罷了。在二維表中進行順序查找有兩個方法：-是把二維線性表看成是n個長度為m的-維線性表，順序查找就是對這n個-維線性表依次實施順序查找，因此它的算法時間復雜度是O(n)×o(m)=o(n×m);二是直接把n×m的二維線性表看成一個n×m的-維線性表，那么在它當中用順序查找法查捧一個元素的算法時間復雜度是O(n×m)。

　　10[單選題]下列對于線性鏈表的描述中正確的是(　　)。

　　參考答案：A

　　參考解析：線性鏈表是通過增加一個指針域來把相鄰的數(shù)據(jù)元素鏈接成一個線性序列。線性鏈表的這種結構使得它存儲數(shù)據(jù)的空間可以是離散的，并不像順序表那樣一定要求物理上的連續(xù)空間。因此選項A正確n

　　11[單選題]在線性鏈表的插入算法中，若要把結點q插在結點P后面，下列操作正確的是(　　)。

　　參考答案：B

　　參考解析：

　　12[單選題]在一個n×m的二維線性表中順序查找一個數(shù)據(jù)元素的算法時間復雜度是(　　)。

　　參考答案：B

　　參考解析：

　　13[填空題]已知線性表的每個元素占2個字節(jié)，它的第5個元素在內(nèi)存中的存儲地址是1005，那么它的第2個元素在內(nèi)存中的存儲地址是________。

　　答案：999

　　14[填空題]線性表的存儲結構主要分為順序存儲結構和鏈式存儲結構。隊列是-種特殊的線性表，循環(huán)隊列是隊列的________存儲結構。

　　參考解析：順序【分析】在實際應用中，隊列的順序存儲結構-般采用循環(huán)隊列的形式。

　　15[單選題]已知線性表的首元素的地址是1025，每個數(shù)據(jù)元素的長度為2，則第10個兀素的地址為(　　)。

　　參考答案：D

　　16[單選題]下列關于鏈表結構的敘述正確的是(　　)。

　　參考答案：A

　　17[單選題]下列敘述中正確的是(　　)�！究键c5鏈表】

　　A.棧是“先進先出”的線性表

　　B.隊列是“先進后出”的線性表

　　C.循環(huán)隊列是非線性結構

　　D.有序線性表既可以采用順序存儲結構，也可以采用鏈式存儲結構

　　參考答案：D

　　參考解析：本題主要考查了棧、隊列、循環(huán)隊列的概念，棧是先進后出的線性表，隊列是先進先出的線性表。根據(jù)數(shù)據(jù)結構中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結構分為兩大類型：線性結構與非線性結構。有序線性表既可以采用順序存儲結構，又可以采用鏈式存儲結構。

　　18[單選題]在表示樹的多重鏈表中，除了要存儲結點的值和多個指針之外，還必須需要存儲(　　)。

　　參考答案：A

　　相關推薦：

　　2015計算機二級公共基礎知識考前沖刺練試題匯總

　　2015計算機二級公共基礎知識精選選擇題專項練習

　　2015計算機二級《公共基礎知識》精選選擇題90道