第一章　數(shù)據(jù)結(jié)構(gòu)與算法
    一、選擇題
    【例1】算法的時(shí)間復(fù)雜度取決于_______。(考點(diǎn)2)
    A)問(wèn)題的規(guī)模
    B)待處理的數(shù)據(jù)的初態(tài)
    C)問(wèn)題的難度
    D)A)和B)
    解析：算法的時(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，在同一個(gè)問(wèn)題規(guī)模下，而且與輸入數(shù)據(jù)有關(guān)。即與輸入數(shù)據(jù)所有的可能取值范圍、輸入各種數(shù)據(jù)或數(shù)據(jù)集的概率有關(guān)。
    答案：D)
    【例2】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成_______。(考點(diǎn)3)
    A)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)
    B)線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)
    C)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)
    D)動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)
    解析：邏輯結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系，線(xiàn)性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對(duì)一的關(guān)系，非線(xiàn)性結(jié)構(gòu)表示數(shù)據(jù)元素之間為一對(duì)多或者多對(duì)一的關(guān)系，所以答案為B)。
    答案：B)
    【例3】以下_______不是棧的基本運(yùn)算。(考點(diǎn)5)
    A)判斷棧是否為素空
    B)將棧置為空棧
    C)刪除棧頂元素
    D)刪除棧底元素
    解析：棧的基本運(yùn)算有：入棧，出棧(刪除棧頂元素)，初始化、置空、判斷棧是否為空或滿(mǎn)、提取棧頂元素等，對(duì)棧的操作都是在棧頂進(jìn)行的。
    答案：D)
    【例4】鏈表不具備的特點(diǎn)是_______。(考點(diǎn)6)
    A)可隨機(jī)訪(fǎng)問(wèn)任意一個(gè)結(jié)點(diǎn)
    B)插入和刪除不需要移動(dòng)任何元素
    C)不必事先估計(jì)存儲(chǔ)空間
    D)所需空間與其長(zhǎng)度成正比
    解析：順序表可以隨機(jī)訪(fǎng)問(wèn)任意一個(gè)結(jié)點(diǎn)，而鏈表必須從第一個(gè)數(shù)據(jù)結(jié)點(diǎn)出發(fā)，逐一查找每個(gè)結(jié)點(diǎn)。所以答案為A)。
    答案：A)
    【例5】已知某二叉樹(shù)的后序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。(考點(diǎn)8)
    A)ACBED
    B)DEABC
    C)DECAB
    D)EDBAC
    解析：后序遍歷的順序是"左子樹(shù)-右子樹(shù)-根結(jié)點(diǎn)";中序遍歷順序是"左子樹(shù)-根結(jié)點(diǎn)-右子樹(shù)";前序遍歷順序是"根結(jié)點(diǎn)-左子樹(shù)-右子樹(shù)"。根據(jù)各種遍歷算法，不難得出前序遍歷序列是EDBAC。所以答案為D)。
    答案：D)
    【例6】設(shè)有一個(gè)已按各元素的值排好序的線(xiàn)性表(長(zhǎng)度大于2)，對(duì)給定的值k，分別用順序查找法和二分查找法查找一個(gè)與k相等的元素，比較的次數(shù)分別是s和b，在查找不成功的情況下，s和b的關(guān)系是_______。(考點(diǎn)9)
    A)s=b
    B)s>b
    C)s解析：對(duì)于順序查找，查找不成功時(shí)和給定關(guān)鍵字比較的次數(shù)為n+1。二分查找查找不成功的關(guān)鍵字比較次數(shù)為[log2n]+1。當(dāng)n≥2時(shí)，顯然n+1>[log2n]+1。
    答案：B)
    【例7】在快速排序過(guò)程中，每次劃分，將被劃分的表(或子表)分成左、右兩個(gè)子表，考慮這兩個(gè)子表，下列結(jié)論一定正確的是_______。(考點(diǎn)11)
    A)左、右兩個(gè)子表都已各自排好序
    B)左邊子表中的元素都不大于右邊子表中的元素
    C) 左邊子表的長(zhǎng)度小于右邊子表的長(zhǎng)度
    D)左、右兩個(gè)子表中元素的平均值相等
    解析：快速排序基本思想是：任取待排序表中的某個(gè)元素作為基準(zhǔn)(一般取第一個(gè)元素)，通過(guò)一趟排序，將待排元素分為左右兩個(gè)子表，左子表元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子表的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對(duì)兩個(gè)子表繼續(xù)進(jìn)行排序，直至整個(gè)表有序。
    答案：B)
    二、填空題
    【例1】問(wèn)題處理方案的正確而完整的描述稱(chēng)為_(kāi)______。(考點(diǎn)1)
    解析：計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱(chēng)為計(jì)算機(jī)算法。
    答案：算法
    【例2】一個(gè)空的數(shù)據(jù)結(jié)構(gòu)是按線(xiàn)性結(jié)構(gòu)處理的，則屬于_______。(考點(diǎn)4)
    解析：一個(gè)空的數(shù)據(jù)結(jié)構(gòu)是線(xiàn)性結(jié)構(gòu)或是非線(xiàn)性結(jié)構(gòu)，要根據(jù)具體情況而定。如果對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線(xiàn)性結(jié)構(gòu)來(lái)處理的，則屬于線(xiàn)性結(jié)構(gòu)，否則屬于非線(xiàn)性結(jié)構(gòu)。
    答案：線(xiàn)性結(jié)構(gòu)
    【例3】設(shè)樹(shù)T的度為4，其中度為1、2、3和4的結(jié)點(diǎn)的個(gè)數(shù)分別為4、2、1、1，則T中葉子結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)______。(考點(diǎn)7)
    解析：根據(jù)樹(shù)的性質(zhì)：樹(shù)的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度與對(duì)應(yīng)的結(jié)點(diǎn)個(gè)數(shù)乘積之和加1。
    因此樹(shù)的結(jié)點(diǎn)數(shù)為1×4+2×2+3×1+4×1+1=16。葉子結(jié)點(diǎn)數(shù)目等于樹(shù)結(jié)點(diǎn)總數(shù)減去度不為0的結(jié)點(diǎn)數(shù)之和，即16-(4+2+1+1)=8。
    答案：8
    【例4】二分法查找的存儲(chǔ)結(jié)構(gòu)僅限于_______且是有序的。(考點(diǎn)10)
    解析：二分查找，也稱(chēng)折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲(chǔ)結(jié)構(gòu)，且表中元素必須按關(guān)鍵字有序(升序或降序均可)。
    答案：順序存儲(chǔ)結(jié)構(gòu)