班級(jí)班級(jí)學(xué)號(hào)姓名本科．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．密．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．封．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．線．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．試卷說明：1、試卷滿分100分，120分鐘完成試卷；2、鋼筆或圓珠筆直接答在試題中（除題目有特殊規(guī)定外）；3、答卷前將密封線內(nèi)的項(xiàng)目填寫清楚。題號(hào)一二三四五總分合分人復(fù)核人滿分100得分一、單項(xiàng)選擇題（總共10題，每題3分，每題的選項(xiàng)中，只有一個(gè)是正確的，請(qǐng)將正確答案的序號(hào)填在括號(hào)內(nèi)）1.以下關(guān)于線性表的說法，錯(cuò)誤的是（）A.線性表是一種線性結(jié)構(gòu)B.線性表可以采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.線性表的插入和刪除操作效率相同D.線性表中的元素具有邏輯上的順序性2.若進(jìn)棧序列為1，2，3，4，進(jìn)棧過程中可以出棧，則（）不可能是一個(gè)出棧序列。A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，13.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)4.深度為5的完全二叉樹的結(jié)點(diǎn)數(shù)不可能是（）A.15B.16C.17D.185.已知一棵二叉樹的前序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF，則后序遍歷序列為（）A.CBEFDAB.FEDCBAC.CBEDFAD.ABCDEF6.對(duì)有序表(2，5，7，10，14，15，18，23，35，41，52)進(jìn)行折半查找，查找元素10的比較次數(shù)是（）A.2B.3C.4D.57.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)存儲(chǔ)單元，則a85的地址為（）A.13B.33C.18D.408.以下排序算法中，平均時(shí)間復(fù)雜度為O(nlogn)且穩(wěn)定的是（）A.快速排序B.堆排序C.歸并排序D.冒泡排序9.數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）A.存儲(chǔ)結(jié)構(gòu)B.物理結(jié)構(gòu)C.邏輯結(jié)構(gòu)D.物理和存儲(chǔ)結(jié)構(gòu)10.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）A.rear=rear+1B.rear=(rear+1)%(m+1)C.rear=(rear+1)%mD.rear=(rear-1)%m二、多項(xiàng)選擇題（總共5題，每題4分，每題的選項(xiàng)中，有兩個(gè)或兩個(gè)以上是正確的，請(qǐng)將正確答案的序號(hào)填在括號(hào)內(nèi)，多選、少選、錯(cuò)選均不得分）1.下列關(guān)于棧的敘述中，正確的是（）A.棧頂元素最先被刪除B.在棧中只能插入元素C.棧底元素最后被刪除D.棧是先進(jìn)后出的線性表2.下列哪些是圖的遍歷方法（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.前序遍歷D.后序遍歷3.一棵二叉樹的葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有（）A.n0=n2+1B.n2=n0+1C.n0=n2-1D.n2=n0-14.以下屬于內(nèi)部排序的是（）A.冒泡排序B.快速排序C.歸并排序D.外部排序5.以下哪些是線性結(jié)構(gòu)（）A.線性表B.棧C.隊(duì)列D.樹三、判斷題（總共10題，每題2分，判斷下列各題，正確的在括號(hào)內(nèi)打“√”，錯(cuò)誤的打“×”）1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。（）2.隊(duì)列是一種先進(jìn)后出的線性表。（）3.圖的鄰接矩陣一定是對(duì)稱矩陣。（）4.完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必然是葉子結(jié)點(diǎn)。（）5.二叉排序樹的中序遍歷序列是有序的。（）6.折半查找適用于有序的順序表。（）7.稀疏矩陣壓縮存儲(chǔ)后，失去了隨機(jī)存取的特性。（）8.排序算法中的比較次數(shù)越少，時(shí)間復(fù)雜度越低。（）9.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式。（）10.循環(huán)隊(duì)列中，front指向隊(duì)頭元素，rear指向隊(duì)尾元素的下一個(gè)位置。（）四、簡(jiǎn)答題（總共3題，每題10分）1.簡(jiǎn)述線性表順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。2.簡(jiǎn)述圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的基本思想。3.簡(jiǎn)述排序算法的穩(wěn)定性，并舉例說明一個(gè)穩(wěn)定的排序算法和一個(gè)不穩(wěn)定的排序算法。