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

　　線性鏈表

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

　　A.冒泡排序為n/2

　　B.冒泡排序為n

　　C.快速排序為n

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

　　參考答案：D

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

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

　　參考答案：C

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

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

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

　　參考答案：D

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

　　參考答案：B

　　參考解析：

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

　　參考解析：順序

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

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

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

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

　　參考解析：45

　　【分析】假設線性表的長度為n，則在最壞情況下，冒泡排序需要經過n/2遍的從前往后的掃描和n/2遍的從后往前的掃描，需要比較的次數為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脫節了那么后面的-步操作沒有任何意義的：使結點q指向P的后件結點即使結點q成為自己的后件結點。按照B指定的順序操作就不會出現在引用結點p的指針域之前已經把它的值修改了的情形。至于C和D項是命題者設計的干擾項想讓考生把P和(1的順序搞混。

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

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

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

　　參考答案：B

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

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

　　參考答案：A

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

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

　　參考答案：B

　　參考解析：

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

　　參考答案：B

　　參考解析：

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

　　答案：999

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

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

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

　　參考答案：D

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

　　參考答案：A

　　17[單選題]下列敘述中正確的是(　　)。【考點5鏈表】

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

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

　　C.循環隊列是非線性結構

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

　　參考答案：D

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

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

　　參考答案：A

　　相關推薦：

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

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

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