數(shù)據(jù)結(jié)構(gòu)練習(xí)試卷1（共124題）

數(shù)據(jù)結(jié)構(gòu)練習(xí)試卷1（共4套）（共124題）數(shù)據(jù)結(jié)構(gòu)練習(xí)試卷第1套一、中文選擇題(本題共20題，每題1.0分，共20分。)1、在長度為64的有序線性表中進行順序查找，最壞情況下需要比較的次數(shù)為______。A、63B、64C、6D、7標(biāo)準(zhǔn)答案：B知識點解析：在長度為64的有序線性表中，其中的64個數(shù)據(jù)元素是按照從大到小或從小到大的順序排列有序的。在這樣的線性表中進行順序查找，最壞的情況就是查找的數(shù)據(jù)元素不在線性表中或位于線性表的最后。按照線性表的順序查找算法，首先用被查找的數(shù)據(jù)和線性表的第一個數(shù)據(jù)元素進行比較，若相等，則查找成功，否則，繼續(xù)進行比較，即和線性表的第二個數(shù)據(jù)元素進行比較。同樣，若相等，則查找成功，否則，繼續(xù)進行比較。依次類推，直到在線性表中查找到該數(shù)據(jù)或查找到線性表的最后一個元素，算法才結(jié)束。因此，在長度為64的有序線性表中進行順序查找，最壞的情況下需要比較64次。因此，本題的正確答案為B。2、對長度為n的線性表進行順序查找，在最壞情況下，所需要的比較次數(shù)為______。A、1og2nB、n/2C、n2D、n+1標(biāo)準(zhǔn)答案：C知識點解析：在長度為n的線性表中進行順序查找，最壞情況下需要比較n次。選項C正確。3、設(shè)有100個結(jié)點，用二分法查找時，最大比較次數(shù)是______。A、25B、50C、10D、7標(biāo)準(zhǔn)答案：D知識點解析：在最壞情況下，二分法查找的比較次數(shù)均為[1og2(n+1)L]。n為100時，最大比較次數(shù)為7。所以，本題應(yīng)該選擇D。4、如果要求一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，則可采用______的方法。A、分塊B、順序C、二分法D、基于屬性標(biāo)準(zhǔn)答案：A知識點解析：二分法是快速查找方法，但要求線性表是有序的。如果把線性表按趨勢分塊，也就是說，塊之間有序，塊內(nèi)不一定有序。這樣就可以既能較快地查找，又能適應(yīng)動態(tài)變化的要求。本題正確答案為選項A。5、在最壞情況下，下列排序方法中時間復(fù)雜度最小的是______。A、冒泡排序B、快速排序C、插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：在最壞情況下：冒泡排序、快速排序和插入排序需要的比較次數(shù)均為n(n-1)/2，堆排序需要比較的次數(shù)為O(n1og2n)?？芍?，在最壞情況下，堆排序的時間復(fù)雜度最小，本題的正確答案為選項D。6、對于長度為n的線性表，在最壞情況下，下列各排序法所對應(yīng)的比較次數(shù)中正確的是______。A、冒泡排序為n/2B、冒泡排序為nC、快速排序為nD、快速排序為n(n-1)/2標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，在最壞情況下，冒泡排序和快速排序需要的比較次數(shù)為n(n-1)/2。由此可見，選項D正確。7、n個元素進行冒泡排序的過程中，最好情況下的時間復(fù)雜度為______。A、O(1)B、O(1og2n)C、O(n2)D、O(n)標(biāo)準(zhǔn)答案：D知識點解析：最好情況下至少需要一趟排序，即比較n-1次。選項D為本題正確答案。8、若原始數(shù)據(jù)序列(23,4,45,67,12,8,19,7)采用直接插入排序法(順序地將每個元素插入到它之前的適當(dāng)位置)排序，則進行完第4趟后的排序結(jié)果是______。A、4,8,45,23,67,12,19,7B、4,7,8,12,23,45,67,19C、4,12,8,19,7,23,45,67D、4,12,23,45,67,8,19,7標(biāo)準(zhǔn)答案：D知識點解析：直接插入排序的思想是，從序列的第2個元素開始遍歷，每次將遍歷的元素插入到其前面序列的適當(dāng)位置，使該元素及其之前的元素有序。所以，4趟排序后，原序列的前5個元素已排序。故本題應(yīng)該選擇D。9、下面的排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排列無關(guān)的是______。A、希爾排序B、冒泡排序C、直接插入排序D、直接選擇排序標(biāo)準(zhǔn)答案：D知識點解析：如果初始排列基本有序，則對希爾排序來說，前幾趟的插入工作大為減少。冒泡排序和直接插入排序都與初始排序序列有關(guān)，只有直接選擇排序與初始序列無關(guān)。本題正確答案為選項D。10、在排序算法中每一項都與其他諸項進行比較，計算出小于該項的項的個數(shù)，以確定該項的位置叫______。A、插入排序B、交換排序C、選擇排序D、枚舉排序標(biāo)準(zhǔn)答案：D知識點解析：在排序算法中每一項都與其他諸項進行比較，計算出小于該項的項的個數(shù)，以確定該項的位置，這種排序方式是枚舉排序，也是選擇排序的一種。本題正確答案為選項D。11、在下列算法中，______算法可能出現(xiàn)下列情況：在最后一趟開始之前，所有的元素都不在其最終的位置上。A、堆排序B、冒泡排序C、插入排序D、快速排序標(biāo)準(zhǔn)答案：C知識點解析：在插入排序中，如果待排序列中的最后一個元素其關(guān)鍵字值為最小，則在最后一趟開始之前，前n-1個排好序的元素都不在其最終位置上，與排好序后的位置相差一個位置。因此，本題正確答案為選項C。12、在文件“局部有序”或文件長度較小的情況下，最佳內(nèi)部排序方法是______。A、直接插入排序B、冒泡排序C、簡單選擇排序D、歸并排序標(biāo)準(zhǔn)答案：A知識點解析：當(dāng)待排序列基本有序時：①直接插入排序在待排序列基本有序時，每趟的比較次數(shù)大為降低，也即n-1趟比較的時間復(fù)雜度由O(n2)降至O(n)。②對冒泡排序來說，若最大關(guān)鍵字位于序列首部，則每趟排序僅能使其“下沉”一個位置，要使其下沉到底部仍需n-1趟排序，也即時間復(fù)雜度仍為O(n2)。③對簡單選擇排序來說，其比較次數(shù)與待排序列的初始狀態(tài)無關(guān)。④歸并排序要求待排序列已經(jīng)部分有序，而部分有序的含義是待排序列由若干有序的子序列組成，即每個子序列必須有序，并且其時間復(fù)雜度為O(n1og2n)。綜上所述，本題正確答案為選項A。13、從未排序的序列中依次取出一個元素與已排序序列中的元素進行比較，然后將其放在已排序序列的合適位置上，該排序方法稱為______。A、插入排序B、選擇排序C、希爾排序D、歸并排序標(biāo)準(zhǔn)答案：A知識點解析：對于選項A，插入排序是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。本題的正確答案為選項A。對于選項B，通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選擇出關(guān)鍵字最小的記錄，并與第i個記錄交換。對于選項C，希爾排序是先將整個記錄序列分割成若干個子序列，分別進行排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次排序。對于選項D，歸并排序是將兩個或兩個以上的有序表組合成一個新的有序表。14、如果待排序序列中兩個元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。______是穩(wěn)定的排序方法，因為這種方法在比較相鄰元素時，值相同的元素并不進行交換。A、冒泡排序B、希爾排序C、快速排序D、簡單選擇排序標(biāo)準(zhǔn)答案：A知識點解析：根據(jù)表8-1，冒泡排序是穩(wěn)定的排序方法。在冒泡排序中，相鄰元素進行比較，大元素交換到后面，相同元素不交換次序。故本題應(yīng)該選擇A。15、對長度為n的線性表排序，在最壞的情況下，比較次數(shù)不是n(n-1)/2的排序方法是______。A、快速排序B、冒泡排序C、直接插入排序D、堆排序標(biāo)準(zhǔn)答案：D知識點解析：假設(shè)線性表的長度為n，則在最壞情況下，快速排序算法、冒泡排序算法和直接插入排序算法需要的比較次數(shù)均為n(n-1)/2。而堆排序的比較次數(shù)為n1og2n。所以，本題應(yīng)該選擇D。16、冒泡排序在最壞情況下的比較次數(shù)是______。A、n(n+1)/2B、n1og2nC、n(n-1)/2D、n/2標(biāo)準(zhǔn)答案：C知識點解析：冒泡排序的基本思想是：將相鄰的兩個元素進行比較，如果反序，則交換；對于一個待排序的序列，經(jīng)一趟排序后，最大值的元素移動到最后的位置，其他值較大的元素也向最終位置移動，此過程稱為一趟冒泡。對于有n個數(shù)據(jù)的序列，共需n-1趟排序，第i趟對從1到n-i個數(shù)據(jù)進行比較、交換。冒泡排序的最壞情況是待排序序列逆序，第1趟比較n-1次，第2趟比較n-2次，依此類推，最后一趟比較1次，一共進行n-1趟排序。因此，冒泡排序在最壞情況下的比較次數(shù)是(n-1)+(n-2)+…+1，結(jié)果為n(n-1)/2。本題的正確答案是選項C。17、在第一趟排序之后，一定能把數(shù)據(jù)表中最大或最小元素放在其最終位置上的排序算法是______。A、冒泡排序B、基數(shù)排序C、快速排序D、歸并排序標(biāo)準(zhǔn)答案：A知識點解析：對于選項A，冒泡排序?qū)⒈慌判虻挠涗洈?shù)組R[1..n)垂直排列，每個記錄R[i]看作是重量為ki的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R凡掃描到違反本原則的輕氣泡，就使其向上“飄浮”。如此反復(fù)進行，直到最后任何兩個氣泡都是輕者在上，重者在下為止。由此可見，冒泡排序第1趟排序之后，最輕的“氣泡”一定會被浮到最上面，即能把數(shù)據(jù)表中最大或最小元素放在其最終位置上。故本題應(yīng)該選擇A。對于選項B，基數(shù)排序的基本思想是：從低位到高位依次對待排序的關(guān)鍵碼進行分配和收集，經(jīng)過d趟分配和收集，就可以得到一個有序序列。所以，基數(shù)排序第1趟排序之后，得到的是以數(shù)據(jù)表中各元素的個位進行排序的結(jié)果，不一定能把數(shù)據(jù)表中最大或最小元素放在其最終位置上。對于選項C，快速排序的基本思想是：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解?？焖倥判虻?趟排序之后，只能使某個關(guān)鍵元素被插入到一個位置，使得該位置之前的所有元素均小于(或大于)關(guān)鍵元素，之后的所有元素均大于(或小于)關(guān)鍵元素。所以，也不一定能把數(shù)據(jù)表中最大或最小元素放在其最終位置上。對于選項D，歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。所以，歸并排序第1趟排序之后，只能得到兩兩有序的一個序列，并不能把數(shù)據(jù)表中最大或最小元素放在其最終位置上。18、為了用一個數(shù)代表一批數(shù)，人們常用這批數(shù)據(jù)的算術(shù)平均值(簡稱平均值)或中位數(shù)來代表。中位數(shù)就是位于這批數(shù)中間的數(shù)(大于它的數(shù)與小于它的數(shù)一樣多)。對于奇數(shù)個數(shù)而言，排序后很容易確定中間那個數(shù)；對于偶數(shù)個數(shù)而言，排序后中間會有兩個數(shù)，再取這兩個數(shù)的算術(shù)平均，就是中位數(shù)。以下關(guān)于平均值與中位數(shù)的敘述中，______是不正確的。A、中位數(shù)比平均值穩(wěn)健，不易受極端值影響B(tài)、每個數(shù)據(jù)加倍后，平均值也加倍；每個數(shù)據(jù)增加1后，平均值也增加1C、三組各有n個數(shù)據(jù)有三個中位數(shù)，它們的中位數(shù)就是這三組數(shù)據(jù)全體的中位數(shù)D、三組各有n個數(shù)據(jù)有三個平均值，它們的平均值就是這三組數(shù)據(jù)全體的平均值標(biāo)準(zhǔn)答案：C知識點解析：選項C的說法是錯誤的。舉個反例即可，比如，(1,4,7)的中值是4，(5,6,9)的中值是6，(10,12,15)的中值是12。三個中值組為一組(4,6,12)，其中值為6。這9個數(shù)字的中值(1,4,5,6,7,9,10,12,15)為7。19、已知遞歸函數(shù)f(n)的功能是計算1+2+…+n，且n≥1，應(yīng)采用的代碼段是______。A、ifn＞1thenreturn1elsereturnn+f(n-1)B、ifn＞1thenreturn1elsereturnn+f(n+1)C、ifn＜1thenreturn0elsereturnn+f(n-1)D、ifn＜1thenreturn0elsereturnn+f(n+1)標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)題意，f(n)的功能是計算1+2+…+n。因此，f(n-1)=1+2+…+(n-1)=f(n)-n。所以，當(dāng)n＞=1時，f(n)可以表示為f(n-1)+n，當(dāng)n＜l時，不妨令f(n)=0。故本題的4個選項中，只有C符合題意。20、設(shè)最優(yōu)的分配方案為完成這三項工作所需的總天數(shù)最少，則在最優(yōu)分配方案中，______。A、甲執(zhí)行PB、甲執(zhí)行QC、乙執(zhí)行PD、乙執(zhí)行R標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)題意，總共有6種分配方案，如表8-3所示。結(jié)果是，在分配方案4中，乙做工作P，12天；丙做工作Q，11天；甲做工作R，10天。共33天。所以，本題正確答案為選項C。二、中文選擇題（含2小題）(本題共10題，每題1.0分，共10分。)在排序算法中，兩兩比較待排序的記錄，當(dāng)發(fā)現(xiàn)不滿足順序要求時，變更它們的相對位置，這就是(1)排序。每次從未排序的記錄中挑出最小(或最大)關(guān)鍵碼值的記錄，加入到已排序記錄的末尾，這是(2)排序。21、在排序算法中，兩兩比較待排序的記錄，當(dāng)發(fā)現(xiàn)不滿足順序要求時，變更它們的相對位置，這就是(1)排序。每次從未排序的記錄中挑出最小(或最大)關(guān)鍵碼值的記錄，加入到已排序記錄的末尾，這是(2)排序。A、插入B、枚舉C、交換D、歸并E、基數(shù)標(biāo)準(zhǔn)答案：C知識點解析：暫無解析22、A、插入B、枚舉C、交換D、歸并E、選擇標(biāo)準(zhǔn)答案：E知識點解析：交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個記錄的次序相反時即進行交換，直到?jīng)]有反序的記錄為止。應(yīng)用交換排序基本思想的主要排序方法有：冒泡排序和快速排序。第1空的正確答案為選項C。選擇排序的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。常用的選擇排序方法有直接選擇排序和堆排序。第2空的正確答案為選項F。設(shè)有n個結(jié)點進行排序，不穩(wěn)定排序是(1)；快速排序的最壞時間是(2)。23、設(shè)有n個結(jié)點進行排序，不穩(wěn)定排序是(1)；快速排序的最壞時間是(2)。A、直接插入排序B、冒泡排序C、希爾排序D、歸并排序標(biāo)準(zhǔn)答案：C知識點解析：暫無解析24、A、O(n1og2n)B、O(n2)C、O(n2/2)D、O(n)標(biāo)準(zhǔn)答案：B知識點解析：各種排序方法的性能比較如表8-1所示。由表中可以看出，題目中提供出直接插入排序、冒泡排序和歸并排序都是穩(wěn)定排序。希爾排序是不穩(wěn)定排序，所以，第1空的正確答案為選項C?？焖倥判虻淖顗臅r間為O(n2)，對于第2空，選項B為正確答案。設(shè)有n個結(jié)點進行排序，不穩(wěn)定排序是(1)；快速排序的最大比較次數(shù)是(2)。25、設(shè)有n個結(jié)點進行排序，不穩(wěn)定排序是(1)；快速排序的最大比較次數(shù)是(2)。A、直接插入排序B、冒泡排序C、Shell排序D、歸并排序標(biāo)準(zhǔn)答案：C知識點解析：暫無解析26、A、n1og2nB、n2C、n2/2D、n標(biāo)準(zhǔn)答案：B知識點解析：在待排序的文件中，若存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。題目選項中，只有shell排序是不穩(wěn)定的。第1空的正確答案為選項C。快速排序利用分治法的基本思想：將原問題分解為若干個規(guī)模更小但結(jié)構(gòu)與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。它的最壞情況是，每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)，而劃分所得的另一個非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個數(shù)減少一個。因此，快速排序必須做n-1次劃分，第i次劃分開始時區(qū)間長度為n-i+1，所需的比較次數(shù)為n-i(1≤i≤n-1)，故總的比較次數(shù)達到最大值：Cmax=n(n-1)/2=n2第2空的正確答案為選項B。堆排序是一種基于______的排序方法，______不是堆。27、堆排序是一種基于______的排序方法，______不是堆。A、計數(shù)B、插入C、選擇D、歸并標(biāo)準(zhǔn)答案：C知識點解析：暫無解析28、A、15,28,25,56,68,63,30B、15,28,25,30,68,63,56C、68,28,63,25,15,56,30D、68,56,39,63,28,25,15標(biāo)準(zhǔn)答案：D知識點解析：堆排序是在選擇排序的基礎(chǔ)上改進而得，所以，第1空的正確答案為選項C。對題目中的4個序列構(gòu)造完全二叉樹，結(jié)果如圖8-33所示。根據(jù)堆的含義，完全二叉樹中，所有非終端結(jié)點的值均不大于或者不小于其左右孩子的值。根據(jù)這個特點，選項D中的56不符合要求。所以，選項D為正確答案。正規(guī)式(1|3|5)(202)(c|de)表示的正規(guī)集合中元素數(shù)目為(1)，(2)是該正規(guī)集合中的元素。29、正規(guī)式(1|3|5)(202)(c|de)表示的正規(guī)集合中元素數(shù)目為(1)，(2)是該正規(guī)集合中的元素。A、6B、7C、8D、無窮標(biāo)準(zhǔn)答案：A知識點解析：暫無解析30、A、135202cdeB、1202cC、302cdeD、52c標(biāo)準(zhǔn)答案：B知識點解析：在正規(guī)式中，“|”表示或，頭一個括號(1|3|5)的意思是，第1個字符是1或3或5，一共3種情況。第2個括號(202)表示，第2～4個字符一定要是202。最后一個括號(c|de)表示，最后一部分字符必須是c或者de這兩種情況。所以，該正則表達式總共可能出現(xiàn)的情況是3×1×2=6種，分別是1202c、1202de、3202c、3202de、5202c、5202de。由此可見，第2空應(yīng)該選擇B。三、流程圖題(本題共1題，每題1.0分，共1分。)31、閱讀下列說明、流程圖和算法進行填空。下面的流程圖用N-S盒圖形式描述了數(shù)組A中的元素被劃分的過程。其劃分方法是：以數(shù)組中的第一個元素作為基準(zhǔn)數(shù)，將小于基準(zhǔn)數(shù)的元素向低下標(biāo)端移動，而大于基準(zhǔn)數(shù)的元素向高下標(biāo)端移動。當(dāng)劃分結(jié)束時，基準(zhǔn)數(shù)定位于A[i]，并且數(shù)組中下標(biāo)小于i的元素的值均小于基準(zhǔn)數(shù)，下標(biāo)大于i的元素的值均大于基準(zhǔn)數(shù)。設(shè)數(shù)組A的下界為low，上界為high，數(shù)組中的元素互不相同。例如，對數(shù)組(4,2,8,3,6)，以4為基準(zhǔn)數(shù)的劃分過程如圖8-34所示。算法說明：將上述劃分的思想進一步用于被劃分出的數(shù)組的兩部分，就可以對整個數(shù)組實現(xiàn)遞增排序。設(shè)函數(shù)intp(intA[],intlow,inthigh)實現(xiàn)了上述流程圖的劃分過程并返回基準(zhǔn)數(shù)在數(shù)組A中的下標(biāo)。遞歸函數(shù)voidsort(intA[],intL,intH)的功能是實現(xiàn)數(shù)組A中元素的遞增排序。算法如下。voidsort(intA[]，intL，intH){if(L＜H){k=p(A,L,H)；//p()返回基準(zhǔn)數(shù)在數(shù)組A中的下標(biāo)sort((4))；//小于基準(zhǔn)數(shù)的元素排序sort((5))；//大于基準(zhǔn)數(shù)的元素排序}}標(biāo)準(zhǔn)答案：(1)j--;(2)i++;(3)A[i]←pivot或A[j]←pivot;(4)A,L,k-1;(5)A,k+1,H知識點解析：本題的快速排序思想是：首先，以待排序序列的第1個元素為基準(zhǔn)，將序列中所有小于基準(zhǔn)元素的元素排到基準(zhǔn)元素的一邊，將序列中所有大于基準(zhǔn)元素的元素排到基準(zhǔn)的另一邊。具體放在哪一邊，要根據(jù)排序的升降而定。這樣，就以基準(zhǔn)元素為界，將原序列劃分成了兩個部分，然后再分別對這兩個部分遞歸進行快速排序，直到無法再劃分為止。這樣，整個序列就被排序了。題目中已經(jīng)給出了快速排序的劃分算法，我們要做的就是將劃分算法的流程圖和快速排序的遞歸函數(shù)補充完整。先看來流程圖，pivot←A[low]就是將數(shù)組A的第1個元素賦給pivot，作為基準(zhǔn)元素。然后，分別將數(shù)組的下界和上界賦給i和j(i←low;j←high)，我們可以將i和j理解為分別指向數(shù)組首和尾的兩個指針。注意，其中的i指向的位置是基準(zhǔn)元素所在位置。接下來是一個循環(huán)，循環(huán)條件為i＜j。在循環(huán)體中，首先從后往前尋找比基準(zhǔn)元素小的元素，這是通過一個子循環(huán)來完成的。循環(huán)條件i＜j&&A[j]＞pivot的意思是，如果j所指的元素比基準(zhǔn)元素大，并且j還在i的后面的話，我們應(yīng)該把j往前移動1位，所以第1空應(yīng)該填j--或其他等價形式。如果找到比基準(zhǔn)元素小的元素或者j已經(jīng)移動到i的位置了，則循環(huán)結(jié)束。下面的語句A[i]←A[j]剛就是將找到的元素移動到i所指位置。注意，現(xiàn)在可以將j所指位置看作是基準(zhǔn)元素的位置，但是可以暫時不用把基準(zhǔn)元素賦給A[j]。接下來的子循環(huán)跟前面的很類似，循環(huán)條件是i＜j&&A[i]＜pivot，如果i所指元素小于基準(zhǔn)元素，且i并沒有超過j，那么就應(yīng)該將i往前移動1位，所以第2空應(yīng)該填i++或其他等價的形式。直到i＞=j(i和j已經(jīng)重合，所有元素都遍歷完了)，或者A[i]＞=pivot(在基準(zhǔn)元素位置j的左邊找到比基準(zhǔn)元素大的元素了)，則該子循環(huán)結(jié)束。然后執(zhí)行A[j]←A[i]，將找到的元素跟基準(zhǔn)元素交換位置，不過基準(zhǔn)元素可以暫時不用賦給A[i]，因為它還要跟其他元素交換位置。如果子循環(huán)不是因為i＞=j結(jié)束的，那么外循環(huán)就會繼續(xù)。直到所有大于基準(zhǔn)元素的元素都被排到基準(zhǔn)元素后面，小于基準(zhǔn)元素的元素都被排到基準(zhǔn)元素前面。外循環(huán)結(jié)束時，i和j一定是重合的，現(xiàn)在可以把基準(zhǔn)元素寫入它們所指的位置中去了。所以，第3空可以填A(yù)[i]←pivot或A[j]←pivot?，F(xiàn)在來看快速排序的遞歸函數(shù)sort()，在函數(shù)中首先判斷下界L是否小于上界H，這一點很重要，因為它是遞歸函數(shù)回溯的條件。如果L＜H，則表示需排序的元素個數(shù)不為0。在if子句中，首先調(diào)用前面分析過的劃分算法p()函數(shù)，將數(shù)組A的L～H范圍進行一次劃分，然后遞歸調(diào)用了兩次sort()。很顯然，這兩次應(yīng)該分別對劃分出的前半部分和后半部分分別排序。所以，第(4)、(5)空應(yīng)該分別填A(yù),L,k-1和A,k+1,H,或者把它們的位置交換也可以。數(shù)據(jù)結(jié)構(gòu)練習(xí)試卷第2套一、中文選擇題(本題共29題，每題1.0分，共29分。)1、下列對于線性鏈表的描述中正確的是______。A、存儲空間不一定連續(xù)，且各元素的存儲順序是任意的B、存儲空間不一定連續(xù)，且前件元素一定存儲在后件元素的前面C、存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D、存儲空間必須連續(xù)，且各元素的存儲順序是任意的標(biāo)準(zhǔn)答案：A知識點解析：在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，數(shù)據(jù)元素之間的邏輯關(guān)系，是由指針域來確定的。由此可見，選項A的描述正確。因此，本題的正確答案為A。2、在程序的執(zhí)行過程中，用______結(jié)構(gòu)可以實現(xiàn)嵌套調(diào)用函數(shù)的正確返回。A、隊列B、棧C、樹D、圖標(biāo)準(zhǔn)答案：B知識點解析：每當(dāng)程序要調(diào)用一個函數(shù)時，系統(tǒng)會將調(diào)用前的狀態(tài)保存起來，等到調(diào)用返回時再恢復(fù)到調(diào)用前的狀態(tài)。所以，當(dāng)函數(shù)嵌套調(diào)用時，最先被調(diào)用的函數(shù)肯定要等到它嵌套調(diào)用的其他函數(shù)都返回了，才會最后一個返回。即先保存的狀態(tài)需要最后才能被恢復(fù)，這正好符合棧的先進后出的特點。所以，用棧結(jié)構(gòu)可以實現(xiàn)嵌套調(diào)用函數(shù)的正確返回。選項B為本題正確答案。3、堆棧操作中，______保持不變。A、堆棧的頂B、堆棧中的數(shù)據(jù)C、堆棧指針D、堆棧的底標(biāo)準(zhǔn)答案：D知識點解析：堆棧是只能通過訪問它的一端(棧頂)來實現(xiàn)數(shù)據(jù)存儲和檢索的一種線性數(shù)據(jù)結(jié)構(gòu)。由此可見，在對堆棧操作的過程中，棧頂會發(fā)生變化，堆棧中的數(shù)據(jù)肯定會變，堆棧指針通常指向下一個出棧數(shù)據(jù)的位置，故也會發(fā)生變化。唯一不變的只有堆棧的底，所以應(yīng)該選擇D。4、判斷一個表達式中左右括號是否匹配，采用______實現(xiàn)較為方便。A、線性表的順序存儲B、隊列C、線性表的鏈?zhǔn)酱鎯、棧標(biāo)準(zhǔn)答案：D知識點解析：判斷一個表達式中的左右括號是否匹配，一般使用的算法是從左至右掃描表達式，碰到左括號，就將其壓入一個堆棧，碰到右括號，就到堆棧中彈出一個左括號，并判斷兩個括號類型是否一致。就這樣，如果碰到要彈出左括號時堆棧為空，或者兩個括號類型不一致，或者掃描完整個表達式堆棧不為空，則均可斷定表達式中存在括號不匹配的情況。所以，本題應(yīng)采用的數(shù)據(jù)結(jié)構(gòu)是棧，選項D為正確答案。5、在執(zhí)行遞歸過程時，通常使用的數(shù)據(jù)結(jié)構(gòu)是______。A、堆棧(stack)B、隊列(queue)C、圖(graph)D、樹(tree)標(biāo)準(zhǔn)答案：A知識點解析：當(dāng)過程被調(diào)用時，通常會先將現(xiàn)場保存起來，等到過程返回時，再恢復(fù)現(xiàn)場。當(dāng)一個過程直接或間接地調(diào)用了自身，則該過程就被稱為遞歸過程。當(dāng)過程遞歸地調(diào)用時，會連續(xù)地保存現(xiàn)場，而回溯時則會連續(xù)地恢復(fù)現(xiàn)場?，F(xiàn)場的保存和恢復(fù)是先進后出的，這跟數(shù)據(jù)結(jié)構(gòu)中的堆棧的工作方式很相似。故在執(zhí)行遞歸過程時，通常使用的數(shù)據(jù)結(jié)構(gòu)是堆棧。6、若需將一個棧S中的元素逆置，則以下處理方式中正確的是______。A、將棧S中元素依次出棧并入棧T，然后棧T中元素依次出棧并進入棧SB、將棧S中元素依次出棧并入隊，然后使該隊列元素依次出隊并進入棧SC、直接交換棧頂元素和棧底元素D、直接交換棧頂指針和棧底指針標(biāo)準(zhǔn)答案：B知識點解析：棧的特點是先進后出。隊列的特點是先進先出。對于選項A，首先，將棧S中元素依次出棧并入棧T，那么，現(xiàn)在棧T中的元素是棧S中的元素的逆序。然后，棧T中元素依次出棧并進入棧S，那么，棧S中的元素又是棧S中的元素的逆序，實際上，就以原來的順序放置。所以，本選項不滿足題目要求。對于選項A，首先，將棧S中元素依次出棧并入隊，那么，現(xiàn)在隊頭的元素是棧S中的棧頂元素，隊尾元素是棧S的棧底元素。然后，該隊列元素依次出隊并進入棧S，因為隊是先進先出，所以，隊頭元素(也就是原來的棧頂元素)成為棧S的棧底元素，隊尾元素(也就是原來的棧底元素)成為棧S中的棧頂元素。實現(xiàn)了逆序放置。所以，本選項為正確答案。選項C和選項D不符合棧結(jié)構(gòu)的操作要求。7、字符串是一種線性表，其特殊性表現(xiàn)在______。A、它的數(shù)據(jù)元素是一個字符B、它可以鏈?zhǔn)酱鎯、它可以順序存儲D、它的數(shù)據(jù)元素可以是多個字符標(biāo)準(zhǔn)答案：A知識點解析：任何線性表即可以鏈?zhǔn)酱鎯σ部梢皂樞虼鎯?，所以選項B和選項C都不能表現(xiàn)字符串的特殊性。字符串是由某字符集上的字符所組成的任何有限字符序列。所以其每個數(shù)據(jù)元素都只能是1個字符，而不能為多個字符，故本題應(yīng)該選擇A。8、數(shù)組A[-5..5,0..8]按列存儲。若第一個元素的首地址為100，且每個元素占用4個存儲單元，則元素A[2,3]的存儲地址為______。A、244B、260C、364D、300標(biāo)準(zhǔn)答案：B知識點解析：數(shù)組A[-5..5,0..8)如果按列存儲的話，在內(nèi)存中的順序就是：A[-5,0]，A[-4,0]，A[-3,0]，…，A[4,8]，A[5,8]。我們把A[-5,0]～A[5,0]稱為第0列；A[-5,1)～A[5,1]稱為第1列…，則元素A[2,3]之前共有0～2，三個整列，每列有-5～5共11個元素。并且，在第3列中，元素A[2,3]之前還有A[-5,3]～A[1,3]這7個元素。所以，元素A[2,3]之前共有11×3+7=40個元素。首地址為100，且每個元素占用4個存儲單元，則元素A[2,3]的存儲地址為100+40×4=260。9、若二維數(shù)組P[1..5,0..8]的首地址為base，數(shù)組元素按行存儲，且每個元素占用1個存儲單元，則元素P[3,3]在該數(shù)組空間的地址為______。A、base+13B、base+16C、base+18D、base+21標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)定義，二維數(shù)組P[1..5,0..8]中的元素可表示如下：P[1,0]P[1,1]P[1,2]P[1,3]P[1,4]P[1,5]P[1,6]P[1,7]P[1,8]P[2,0]P[2,1]P[2,2]P[2,3]P[2,4]P[2,5]P[2,6]P[2,7]P[2,8]P[3,0]P[3,1]P[3,2]P[3,3]P[3,4]P[3,5]P[3,6]P[3,7]P[3,8]P[4,0]P[4,1]P[4,2]P[4,3]P[4,4]P[4,5]P[4,6]P[4,7]P[4,8]P[5,0]P[5,1]P[5,2]P[5,3]P[5,4]P[5,5]P[5,6]P[5,7]P[5,8]數(shù)組空間首地址為base，也就是說元素P[1,0]的存儲地址為base，按行存儲時，P[3,3]之前存儲了2×9+3個元素，因此P[3,3]在該數(shù)組安間的地址為base+21。10、已知有一維數(shù)組T[0..m*n-1]，其中m＞n。從數(shù)組T的第一個元素(T[0])開始，每隔n個元素取出一個元素依次存入數(shù)組B[1..m]中，即B[1]=T[0]，D[2]=T[n]，依此類推，那么放入B[k](1≤k≤n)的元素是______。A、T[(k-1)*n]B、T(k*n)C、T[(k-1)*m]D、T[k*m]標(biāo)準(zhǔn)答案：A知識點解析：根據(jù)題意，每隔n個元素取出一個元素依次存入數(shù)組B(1..m]中。所以，不難推導(dǎo)出B[1]=T[0]，B[2]=T[n]，B[3]=T[2n]，…，B[k]=T[(k-1)n]故本題應(yīng)該選擇A。11、已知N個數(shù)已存入數(shù)組A[1..M]的前N個元素中(N＜M)，為在A[i](1≤i≤N)之前插入一個新數(shù)，應(yīng)先______，以挪出一個空閑位置插入該數(shù)。A、從A[i]開始直到A[1]，每個數(shù)向后移動一個位置B、從A[1]開始直到A[i]，每個數(shù)向后移動一個位置C、從A[i]開始直到A[N]，每個數(shù)向前移動一個位置D、從A[N]開始直到A[i]，每個數(shù)向后移動一個位置標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)題干內(nèi)容，數(shù)組A[1..M]元素的結(jié)構(gòu)如圖8-10所示。對于選項A，從A[i]開始直到A[1]，每個數(shù)向后移動一個位置，那么，首先移動A[i]到A[i+1]的位置時，會覆蓋A[i+1]的內(nèi)容。而且，最后挪出的空閑位置為A[1]，如圖8-11所示。顯然，不符合題意。對于選項B，首先A[1]內(nèi)容向后移動到A[2]內(nèi)容，那么，A[2]的內(nèi)容被A[1]的內(nèi)容所覆蓋，A[2]內(nèi)容再繼續(xù)向后移，實際上是將A[1]內(nèi)容又覆蓋了A[3]內(nèi)容。依此類推。最后，A[2]～A[i]的值都變成了A[1]的值。空閑位置是A[1]。如圖8-12所示。也不符合題意。對于選項C，從A[i]開始直到A[N]，每個數(shù)向前移動一個位置，那么，首先移動A[i]到A[i-1]的位置時，會覆蓋A[i-1]的內(nèi)容，A[i]的內(nèi)容變成A[i+1]，依此類推，A[N-1]的內(nèi)容成為A[N]的內(nèi)容。而且，最后挪出的空閑位置為A[N]，如圖8-13所示。顯然，不符合題意。對于選項D，從A[N]開始直到A[i]，每個數(shù)向后移動一個位置，那么，首先移動A[N]到A[N+1]的位置時，會覆蓋A[N+1]的內(nèi)容，A[N-1]的內(nèi)容移入A[N]，依此類推，A[i]的內(nèi)容移入A[i+1]。而且，最后挪出的空閑位置為A[i]，如圖8-14所示。顯然符合題意。本題正確答案為選項D。12、設(shè)數(shù)組a[1..3,1..4]中的元素以列為主序存放，每個元素占用1個存儲單元，則數(shù)組元素a[2,3]相對于數(shù)組空間首地址的偏移量為______。A、6B、7C、8D、9標(biāo)準(zhǔn)答案：B知識點解析：當(dāng)數(shù)組元素以列為主序存儲時，首先存儲第1列的所有元素，然后存儲第2列的所有元素，再存儲第3列的所有元素，以此類推，最后存儲最后一列的所有元素。數(shù)組元素a[2,3]表示是在第3行的第2個元素。所以，根據(jù)以列為主序存儲元素的方式，它的位置前有2列元素，再加上兩個元素，所以，它的位置為2*3+2=8，相對第一個元素的偏移量為8-1=7。本題正確答案為選項B。設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素Wij占用6個字節(jié)，行下標(biāo)i從0到8，列下標(biāo)j從2到5，則二維數(shù)組W的數(shù)據(jù)元素共占用(1)個字節(jié)。W中第6行的元素和第4列的元素共占用(2)個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址的字節(jié)號為100，則二維數(shù)組W的最后一個數(shù)據(jù)元素的起始地址的字節(jié)號為(3)，數(shù)據(jù)元素w34的起始地址號為(4)。13、設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素Wij占用6個字節(jié)，行下標(biāo)i從0到8，列下標(biāo)j從2到5，則二維數(shù)組W的數(shù)據(jù)元素共占用(1)個字節(jié)。W中第6行的元素和第4列的元素共占用(2)個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址的字節(jié)號為100，則二維數(shù)組W的最后一個數(shù)據(jù)元素的起始地址的字節(jié)號為(3)，數(shù)據(jù)元素w34的起始地址號為(4)。A、480B、192C、216D、144標(biāo)準(zhǔn)答案：C知識點解析：暫無解析14、A、78B、72C、66D、84標(biāo)準(zhǔn)答案：B知識點解析：暫無解析15、A、310B、311C、315D、314標(biāo)準(zhǔn)答案：A知識點解析：暫無解析16、A、179B、178C、184D、185標(biāo)準(zhǔn)答案：C知識點解析：行下標(biāo)為0～8，說明有8-0+1=9行；列下標(biāo)2～5，說明有5-2+1=4列。所以共有9×4=36個元素。因為每個元素占6個字節(jié)，所以，該數(shù)組共占6×36=216個字節(jié)。所以，第1空的正確答案為選項C。每個元素占6個字節(jié)，每行有4個元素，則每行占6×4=24個字節(jié)。每列有9個元素，所以，每列占6×9=54個字節(jié)。對于第6行和第4列的元素，因為有W64既屬于第6行，又屬于第4列，所以，不應(yīng)當(dāng)重復(fù)計算。因此，第6行和第4列的元素應(yīng)當(dāng)占24+54-6=72個字節(jié)。第2空的標(biāo)準(zhǔn)答案為選項B。第一個元素的起始地址為100，前面已經(jīng)計算過，該數(shù)組所有元素共占用216個字節(jié)。那么，最后一個元素的起始地址就是100+216-6=310。最后一個元素要占用6個字節(jié)，所以要在計算中減去6。第3個空的正確答案為選項A。如果按行存放數(shù)組，那么，存放順序為，首先是第0行的4個元素，然后是第1行的4個元素，以此類推。W34即第3行第4列，前面已有存儲了3行又兩個元素，也就是3×4+2=14個元素。所以，W34的起始地址為100+6×14=184。第4個空的正確答案為選項C。17、對矩陣壓縮存儲的主要目的是______。A、方便運算B、節(jié)省存儲空間C、降低計算復(fù)雜度D、提高運算效率標(biāo)準(zhǔn)答案：B知識點解析：多個相同的非零元素只分配一個存儲空間，對零元素分配存儲空間的方法，就是矩陣壓縮存儲，這樣可以節(jié)省存儲空間，所以，選項B正確。18、數(shù)據(jù)結(jié)構(gòu)中的樹最適合用來表示______的情況。A、數(shù)據(jù)元素有序B、數(shù)據(jù)元素之間具有多對多關(guān)系C、數(shù)據(jù)元素?zé)o序D、數(shù)據(jù)元素之間具有一對多關(guān)系標(biāo)準(zhǔn)答案：D知識點解析：樹結(jié)構(gòu)中一個數(shù)據(jù)元素可以有兩個或兩個以上的直接后繼元素，可以用來描述客觀世界中廣泛存在的層次關(guān)系。樹是n(n≥0)個結(jié)點的有限集合。當(dāng)n=0時稱為空樹。在任一非空樹(n＞0)中，有且僅有一個稱為根的結(jié)點；其余結(jié)點可分為m(m≥0)個互不相交的有限集T1,T2,…,Tm，其中每個集合又都是一棵樹，并且稱為根結(jié)點的子樹。因此，樹中數(shù)據(jù)元素之間具有一對多的邏輯關(guān)系。本題正確答案為選項D。19、對于n個元素的關(guān)鍵字序列{k1,k2,…,kn}，若將其按次序?qū)?yīng)到一棵具有n個結(jié)點的完全二叉樹上，使得任意結(jié)點都不大于其孩子結(jié)點(若存在孩子結(jié)點)，則稱其為小頂堆。根據(jù)以上定義，______是小頂堆。A、

B、

C、

D、

標(biāo)準(zhǔn)答案：D知識點解析：對于n個元素的關(guān)鍵字序列{k1,k2,…,kn}，當(dāng)且僅當(dāng)滿足下列關(guān)系時稱其為堆：Ki≤K2i且Ki≤K2i+1①或者Ki≥K2i≥K2i+1②其中，1≤i≤[n/2]，滿足①式稱為小頂堆，滿足②式稱為大頂堆。顯然，題目中選項A中25與23和51之間的關(guān)系不滿足小頂堆的定義；選項B中51與63和25之間、55與23之間的關(guān)系不滿足小頂堆的定義；選項C的情況與B類似。選項D是小頂堆，為本題正確答案。20、設(shè)有二叉樹如圖8-15所示。對此二叉樹先序遍歷的結(jié)果為______。A、ABCDEFB、BDAECFC、ABDCEFD、DBEFCA標(biāo)準(zhǔn)答案：C知識點解析：二叉樹的遍歷分為先序、中序、后序三種不同方式。本題要求先序遍歷，其遍歷順序應(yīng)該為：訪問根結(jié)點-＞先序遍歷左子樹-＞先序遍歷右子樹。按照定義，先序遍歷序列是ABDCEF，故答案為C。21、二叉排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：若其左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若其右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；其左、右子樹本身就是兩棵二叉排序樹。根據(jù)該定義，對一棵非空的二叉排序樹進行______遍歷，可得到一個結(jié)點元素的遞增序列。A、先序(根、左、右)B、中序(左、根、右)C、后序(左、右、根)D、層序(從樹根開始，按層次)標(biāo)準(zhǔn)答案：B知識點解析：中序遍歷二叉樹的操作定義為：若二叉樹為空，則進行空操作；否則：①中序遍歷根的左子樹；②訪問根結(jié)點；③中序遍歷根的右子樹。顯然，根據(jù)二叉排序樹的定義，對一棵非空的二叉排序樹進行中序遍歷，可得到一個結(jié)點元素的遞增序列。本題正確答案為選項B。22、對圖8-16所示的二叉樹進行中序遍歷(左子樹，根，右子樹)的結(jié)果是______。A、253461B、253416C、265413D、264531標(biāo)準(zhǔn)答案：D知識點解析：根據(jù)中序遍歷的特點，先遍歷左子樹，然后是根，再遍歷右子樹，結(jié)果是264531。本題正確答案為選項D?？紤]具有如下性質(zhì)的二叉樹：除葉子結(jié)點外，每個結(jié)點的值都大于其左子樹上的一切結(jié)點的值，并小于等于其右子樹上的一切結(jié)點的值。現(xiàn)把9個數(shù)1,2,3,4…8,9填入圖8-18所示的二叉樹的9個結(jié)點中，并使之具有上述性質(zhì)，此時N1的值是(1)，N2的值是(2)，N9的值是(3)。現(xiàn)欲把放入此樹并使該樹保持前述性質(zhì)，增加的一個結(jié)點可以放在(4)。23、考慮具有如下性質(zhì)的二叉樹：除葉子結(jié)點外，每個結(jié)點的值都大于其左子樹上的一切結(jié)點的值，并小于等于其右子樹上的一切結(jié)點的值?，F(xiàn)把9個數(shù)1,2,3,4…8,9填入圖8-18所示的二叉樹的9個結(jié)點中，并使之具有上述性質(zhì)，此時N1的值是(1)，N2的值是(2)，N9的值是(3)?，F(xiàn)欲把放入此樹并使該樹保持前述性質(zhì)，增加的一個結(jié)點可以放在(4)。A、1B、2C、3D、4E、7標(biāo)準(zhǔn)答案：E知識點解析：暫無解析24、A、1B、2C、3D、4E、5標(biāo)準(zhǔn)答案：D知識點解析：暫無解析25、A、1B、2C、3D、6E、5標(biāo)準(zhǔn)答案：D知識點解析：暫無解析26、A、N1下面B、N8下面C、N9下面D、N6下面標(biāo)準(zhǔn)答案：B知識點解析：要按照題目要求填結(jié)點，那么，左下角的結(jié)點n7應(yīng)當(dāng)具有最小值，也就是1，右下角的結(jié)點n6，應(yīng)當(dāng)具有最大值，也就是9。如圖8-19所示，現(xiàn)在考慮將2、3、4、5、6、7、8放入其中?，F(xiàn)在，不考慮n7和n6，在要放入數(shù)值的樹中，其左下角結(jié)點為n4，放入剩余數(shù)字的最小值2，根據(jù)題目對此樹的要求，n8應(yīng)當(dāng)放入3。右下角結(jié)點為n3，放入剩余數(shù)字的最大值為8，根據(jù)題目要求，n1應(yīng)當(dāng)放入7。結(jié)果如圖8-20所示。現(xiàn)在只剩下4、5、6了，根據(jù)題目要求，顯然應(yīng)當(dāng)在n2放入4，n5放入5，n6放入6。最終結(jié)果如圖8-21所示。所以，第1空的正確答案為選項G，第2空的正確答案為選項D，第3空的正確答案為選項F。要使此樹保持題目要求的特點，放入3.5，那么，可放到n8下面，作為它的右子樹。第4空的正確答案為選項B。27、在深度為7的滿二叉樹中，葉子結(jié)點的個數(shù)為______。A、32B、31C、64D、63標(biāo)準(zhǔn)答案：C知識點解析：在二叉樹的第k層上，最多有2k-1(k≥1)個結(jié)點。對于滿二叉樹來說，每一層上的結(jié)點數(shù)都達到最大值，即在滿二叉樹的第k層上有2k-1個結(jié)點。因此，在深度為7的滿二叉樹中，所有葉子結(jié)點在第7層上，即其結(jié)點數(shù)為2k-1=27-1=64。因此，本題的正確答案為C。28、在具有100個結(jié)點的樹中，其邊的數(shù)目為______。A、101B、100C、99D、98標(biāo)準(zhǔn)答案：C知識點解析：在樹中，所有的邊必定連接了1對父子結(jié)點，并且除根結(jié)點以外的其余結(jié)點都有且僅有1個父結(jié)點。所以，邊的個數(shù)等于除根結(jié)點以外的其余結(jié)點的個數(shù)。又因為1，棵樹只有1個根結(jié)點，所以1棵樹的邊數(shù)等于它的結(jié)點數(shù)減1。故本題應(yīng)該選擇C。29、設(shè)某種二叉樹有如下特點：結(jié)點的子樹數(shù)目不是2個，則是0個。這樣的一棵二叉樹中有m(m＞0)個子樹為0的結(jié)點時，該二叉樹上的結(jié)點總數(shù)為______。A、2m+1B、2m-1C、2(m-1)D、2(m+1)標(biāo)準(zhǔn)答案：B知識點解析：在任意一棵二叉樹中，若終端結(jié)點的個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則：n0=n2+1根據(jù)題意，n0=m，則n2=n0-1=m-1。所以，結(jié)點總數(shù)為：n0+n2=m+(m-1)=2m-1本題正確答案為選項B。二、中文選擇題（含2小題）(本題共4題，每題1.0分，共4分。)對于二維數(shù)組a[1..4,3..6]，設(shè)每個元素占兩個存儲單元，若分別以行和列為主序存儲，則元素a[3,4]相對于數(shù)組空間起始地址的偏移量分別是(1)和(2)。30、對于二維數(shù)組a[1..4,3..6]，設(shè)每個元素占兩個存儲單元，若分別以行和列為主序存儲，則元素a[3,4]相對于數(shù)組空間起始地址的偏移量分別是(1)和(2)。A、12B、14C、16D、18標(biāo)準(zhǔn)答案：D知識點解析：暫無解析31、A、12B、14C、16D、18標(biāo)準(zhǔn)答案：A知識點解析：每一個二維數(shù)組都可以被看作是一個矩陣。本題的二維數(shù)組a[1..4,3..6]的矩陣如下：以行為主序存儲，即以a[1,3]、a[1,4]、a[1,5]、a[1,6]、a[2,3]……這樣的順序連續(xù)存儲，不難看出，a[3,4]是第10個元素。第1個元素的地址就是數(shù)組空間的起始地址，所以其偏移量為0，那么a[3,4]的偏移量難道為9?千萬不要忘記題目的要求“每個元素占兩個存儲單元”，所以a[3,4]的偏移量是9*2=18。故第1空應(yīng)該選擇D。以列為主序存儲，即以a[1,3]、a[2,3]、a[3,3]、a[4,3]，a[1,4]……這樣的順序連續(xù)存儲，所以a[3,4]是第7個元素。那么a[3,4]的偏移量就是6*2=12。故第2空應(yīng)該選擇A。滿二叉樹的特點是每層上的結(jié)點數(shù)都達到最大值，因此對于高度為h(h＞1)的滿二叉樹，其結(jié)點總數(shù)為(1)。對非空滿二叉樹，由根結(jié)點開始，按照先根后子樹、先左子樹后右子樹的次序，從1、2、3、…依次編號，則對于樹中編號為i的非葉子結(jié)點，其右子樹的編號為(2)(高度為3的滿二叉樹如圖8-17所示)。32、滿二叉樹的特點是每層上的結(jié)點數(shù)都達到最大值，因此對于高度為h(h＞1)的滿二叉樹，其結(jié)點總數(shù)為(1)。對非空滿二叉樹，由根結(jié)點開始，按照先根后子樹、先左子樹后右子樹的次序，從1、2、3、…依次編號，則對于樹中編號為i的非葉子結(jié)點，其右子樹的編號為(2)(高度為3的滿二叉樹如圖8-17所示)。A、2hB、2h-1C、2h-1D、2h-1+1標(biāo)準(zhǔn)答案：C知識點解析：暫無解析33、A、2iB、2i-1C、2i+1D、2i+2標(biāo)準(zhǔn)答案：C知識點解析：滿二叉樹的第1層(樹根)有1個結(jié)點，第二層有2個結(jié)點，第三層有4個結(jié)點，依此類推，第h層有2h-1個結(jié)點。將所有層上的結(jié)點數(shù)相加就是樹中的結(jié)點總數(shù)，即20+21+22+…+2h-1=2h-1。第1空的正確答案為選項C。顯然對非空滿二叉樹中的結(jié)點按照題目中的方式進行編號，結(jié)點i的左子樹編號為2i，右子樹編號為2i+1。第2空的正確答案為選項C。數(shù)據(jù)結(jié)構(gòu)練習(xí)試卷第3套一、中文選擇題(本題共25題，每題1.0分，共25分。)1、數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的______。A、邏輯結(jié)構(gòu)B、存儲結(jié)構(gòu)C、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其運算的實現(xiàn)標(biāo)準(zhǔn)答案：D知識點解析：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)一般包括三方面的內(nèi)容：①數(shù)據(jù)之間的邏輯關(guān)系。從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)。②數(shù)據(jù)的存儲結(jié)構(gòu)。存儲結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)，是邏輯結(jié)構(gòu)在計算機存儲器中的表示，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。③數(shù)據(jù)的運算。也就是在數(shù)據(jù)上所施加的一系列操作。只考慮操作的功能是怎樣的，暫不考慮如何實現(xiàn)。綜上所述，本題的正確答案為選項D。2、在數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(數(shù)據(jù)元素)及結(jié)點間的相互關(guān)系組成數(shù)據(jù)的邏輯結(jié)構(gòu)。按邏輯結(jié)構(gòu)的不同，數(shù)據(jù)結(jié)構(gòu)通常可分為______兩類。A、線性結(jié)構(gòu)和非線性結(jié)構(gòu)B、緊湊結(jié)構(gòu)和稀疏結(jié)構(gòu)C、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)標(biāo)準(zhǔn)答案：A知識點解析：在數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(數(shù)據(jù)元素)及結(jié)點間的相互關(guān)系組成數(shù)據(jù)的邏輯結(jié)構(gòu)。按邏輯結(jié)構(gòu)的不同，數(shù)據(jù)結(jié)構(gòu)通?？煞譃榫€性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。本題正確答案為選項A。3、下面敘述不正確的是______。A、算法的執(zhí)行效率與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)B、算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間C、算法的有窮性是指算法必須能在執(zhí)行有限個步驟之后終止D、算法的時間復(fù)雜度是指執(zhí)行這個算法所需要的時間標(biāo)準(zhǔn)答案：D知識點解析：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，故D選項不正確。4、數(shù)據(jù)的存儲結(jié)構(gòu)是指______。A、數(shù)據(jù)所占的存儲空間量B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示C、數(shù)據(jù)在計算機中的順序存儲方式D、存儲在外存中的數(shù)據(jù)標(biāo)準(zhǔn)答案：B知識點解析：數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)元素在計算機存儲器內(nèi)的表示。數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)，即建立數(shù)據(jù)的機內(nèi)表示。本題正確答案為選項B。5、下列對于線性鏈表的描述中正確的是______。A、存儲空間不一定連續(xù)，且各元素的存儲順序是任意的B、存儲空間不一定連續(xù)，且前件元素一定存儲在后件元素的前面C、存儲空間必須連續(xù)，且前件元素一定存儲在后件元素的前面D、存儲空間必須連續(xù)，且各元素的存儲順序是任意的標(biāo)準(zhǔn)答案：A知識點解析：在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，數(shù)據(jù)元素之間的邏輯關(guān)系，是由指針域來確定的。由此可見，選項A的描述正確。6、下列敘述中正確的是______。A、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)必定是一一對應(yīng)的B、由于計算機存儲空間是向量式的存儲結(jié)構(gòu)，因此，數(shù)據(jù)的存儲結(jié)構(gòu)一定是線性結(jié)構(gòu)C、程序設(shè)計語言中的數(shù)組一般是順序存儲結(jié)構(gòu)，因此，利用數(shù)組只能處理線性結(jié)構(gòu)D、以上三種說法都不對標(biāo)準(zhǔn)答案：D知識點解析：數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)在存儲器中的映像，它包含數(shù)據(jù)元素的映像和關(guān)系的映像。存儲結(jié)構(gòu)在計算機中有兩種，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。①順序存儲結(jié)構(gòu)是把數(shù)據(jù)元素存儲在一塊連續(xù)地址空間的內(nèi)存中。②鏈?zhǔn)酱鎯Y(jié)構(gòu)是使用指針把相互直接關(guān)聯(lián)的結(jié)點鏈接起來。因此，這兩種存儲結(jié)構(gòu)都是線性的?？梢?，邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)不是一一對應(yīng)的。因此，選項A和選項B的說法都是錯誤的。無論數(shù)據(jù)的邏輯結(jié)構(gòu)是線性的還是非線性的，只能選擇順序存儲結(jié)構(gòu)或鏈?zhǔn)酱鎯Y(jié)構(gòu)來實現(xiàn)存儲。程序設(shè)計語言中，數(shù)組是內(nèi)存中一段連續(xù)的地址空間，可看作是順序存儲結(jié)構(gòu)。可以用數(shù)組來實現(xiàn)樹型邏輯結(jié)構(gòu)的存儲，比如二叉樹。因此，選項C的說法是錯誤的。7、以下關(guān)于字符串的判定語句中正確的是______。A、字符串是一種特殊的線性表B、串的長度必須大于零C、字符串不屬于線性表的一種D、空格字符組成的串就是空串標(biāo)準(zhǔn)答案：A知識點解析：字符集中的字符所組成的有限字符序列，就是字符串，它是特殊的線性表，選項A說法正確。選項C錯誤。字符串不包含任何字符時，為空串，長度為0，所以，選項B和選項D的說法錯誤。8、字符串computer中長度為3的子串有______個。A、4B、5C、6D、7標(biāo)準(zhǔn)答案：B知識點解析：子串是字符串中任意長度的連續(xù)字符構(gòu)成的序列。對于字符串computer，長度為3的子串有：com、omp、mpu、put、ute、ter。共有6個。選項B為本題正確答案。9、PUSH和POP命令常用于______操作。A、隊列B、數(shù)組C、棧D、記錄標(biāo)準(zhǔn)答案：C知識點解析：棧是先進后出的線性表。其基本運算是入棧和出棧操作，也就是PUSH和POP。本題的正確答案為選項C。10、n個元素依次全部進入棧后，再陸續(xù)出棧并經(jīng)過一個隊列輸出。那么，______。A、元素的出隊次序與進棧次序相同B、元素的出隊次序與進棧次序相反C、元素的進棧次序與進隊次序相同D、元素的出棧次序與出隊次序相反標(biāo)準(zhǔn)答案：B知識點解析：棧的特點是先進后出，出棧后，元素逆序。隊列的特點是先進先出，元素經(jīng)過隊列，不會更改其順序，也就是說，出隊順序與入隊順序相同，與出棧順序相同，與入棧順序相反。所以，選項B的說法正確，為本題正確答案，其他選項的說法錯誤。11、若一個棧以向量V[1..n)存儲，且空棧的棧頂指針top為n+1，則將元素x入棧的正確操作是______。A、top=top+1；V[top]=x；B、V[top]=x；top=top+1；C、top=top-1；V[top]=x；D、V[top]=x；top=top-1；標(biāo)準(zhǔn)答案：C知識點解析：棧是運算受限的線性表，只允許在棧頂進行插入和刪除操作。棧頂指針為n+1，說明該數(shù)組將棧頂放在了下標(biāo)大的一端，所以，在進行入棧操作時，top指針應(yīng)該進行減1操作。通常元素進棧的操作為：先移動棧頂指針，后存入元素。移動棧頂指針的操作是“top=top-1；”，存入元素的操作是“V[top]=x；”。本題正確答案為選項C。12、設(shè)初始棧為空，s表示入棧操作，x表示出棧操作，則______是合法的操作序列。A、sxxsssxxxB、xxssxxssC、sxsxssxxD、xssssxxx標(biāo)準(zhǔn)答案：C知識點解析：棧是操作受限的線性表，其特點是后進先出。應(yīng)用中可將棧看作一個桶狀的容器，當(dāng)棧中有元素時，棧頂元素先出棧，棧為空時進行出棧操作是不正確的。因此，對于一個關(guān)于初始為空的棧的操作序列，要求序列中任何一個操作之前，入棧操作的次數(shù)要大于等于出棧操作的次數(shù)。題目選項中僅操作序列sxsxssxx滿足該要求。本題正確答案為選項C。13、若push、pop分別表示入棧、出棧操作，初始棧為空且元素1、2、3依次進棧，則經(jīng)過操作序列push、push、pop、pop、push、pop之后，得到的出棧序列為______。A、321B、213C、231D、123標(biāo)準(zhǔn)答案：B知識點解析：棧的運算特點是先進后出。對于元素1、2、3，經(jīng)過操作序列push、push、pop、pop、push、pop的過程如圖8-3(a～g)所示。通過圖可以看出，出棧序列為213。本題正確答案為選項B。14、設(shè)棧S初始狀態(tài)為空。元素a、b、c、d、e、f依次通過棧S，若出棧的順序為c、f、e、d、b、a，則棧S的容量至少應(yīng)該為______。A、6B、5C、4D、3標(biāo)準(zhǔn)答案：B知識點解析：根據(jù)題中給定的條件，可做如下模擬操作：①元素a、b、c進棧，棧中有3個元素，分別為a、b、c；②元素c出棧后，元素d、e、f進棧，棧中有5個元素，分別為a、b、d、e、f；③元素f、e、d、a、b出棧，棧為空?？梢钥闯觯M棧的順序為a、b、c、d、e、f，出棧的順序為c、f、e、d、b、a，滿足題中所提出的要求。在每一次進棧操作后，棧中最多有3個元素，因此，為了順利完成這些操作，棧的容量應(yīng)至少為5。本題答案為B。15、一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i(1≤i≤n)個元素是______。A、不確定B、n-i+lC、iD、n-i標(biāo)準(zhǔn)答案：B知識點解析：棧的特點是先進后出，若輸入序列為123…n，輸出的第一個元素是n，則表明，所有元素都已入棧，則出棧順序為：第1個元素為n，第2個元素為n-1，第3個元素為n-2，…，第i個元素是n-i+1。16、以下數(shù)據(jù)結(jié)構(gòu)中屬于線性數(shù)據(jù)結(jié)構(gòu)的是______。A、集合B、線性表C、二叉樹D、圖標(biāo)準(zhǔn)答案：B知識點解析：所謂的線性結(jié)構(gòu)是指：如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件，即：①有且只有一個根結(jié)點。②每一個結(jié)點最多有一個前件，也最多有一個后件。同時滿足兩個條件的只有線性表，而其他三種數(shù)據(jù)結(jié)構(gòu)的結(jié)點可能存在多個前件或后件，所以不是線性結(jié)構(gòu)。故本題正確答案為B。17、設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是______。A、6B、4C、3D、2標(biāo)準(zhǔn)答案：C知識點解析：棧的特點是先進后出，隊列的特點是先進先出。所以，如果一個元素序列先進入棧，再進入隊列，那么，出隊的序列，與入棧序列是逆序。隊列不影響元素順序。所以，下面使用圖來模擬輸入和輸出順序，只給出棧的變化。①根據(jù)題意，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的序列是e2、e4、e3、e6、e5、e1，那么，通過出隊次序可以看出，首先是e2，說明e1、e2順序入棧。后來e2出棧，e1還在棧中。如圖8-4所示。②第2個輸出元素是e4，那么，說明此時在棧中，還有e1、e3。如圖8-5所示。③第3個輸出元素是e3，直接出棧即可。如圖8-6所示。④第4個輸出元素是e6，說明在e3出棧后，e5、e6順序入棧。e6出棧后，棧中剩下e5和e1。順序出棧即可。如圖8-7所示。根據(jù)前面對入棧、出棧過程的模擬，可以看出，棧s的容量至少為3。選項C為正確答案。18、某循環(huán)隊列的容量為M，隊頭指針指向隊頭元素，隊尾指針指向隊尾元素之后，如圖8-8所示(M=8)，則隊列中的元素數(shù)目為______(MOD表示整除取余運算)。A、rear-frontB、front-rearC、(rear-front+M)MODMD、(front-rear+M)MODM標(biāo)準(zhǔn)答案：C知識點解析：隊列是僅在表頭刪除元素、在表尾插入元素的操作受限的線性表，其特點是先入先出。隊列采用順序存儲結(jié)構(gòu)(一維數(shù)組，順序隊列)時，為了降低運算的復(fù)雜度，元素入隊時，只需修改隊尾指針rear(rear+1→rear)；元素出隊時，只需修改隊頭指針front(front+1→front)。由于順序隊列的存儲空間是提前設(shè)定的，所以隊尾指針會有一個上限值，當(dāng)隊尾指針達到其上限時，就不能只通過修改隊尾指針來實現(xiàn)新元素的入隊操作了。此時，可將順序隊列假想成一個環(huán)狀結(jié)構(gòu)，稱為循環(huán)隊列。隊列容量為M時，隊頭指針front和隊尾指針rear的值循環(huán)地在0～M-1之間變化，當(dāng)rear＞front時，隊列中元素數(shù)目為rear-front；當(dāng)rear＜front時，隊列中元素數(shù)目為rear-front+M。綜上，隊列中元素數(shù)目為(rear-front+M)MODM。本題正確答案為選項C。19、棧和隊列的共同點是______。A、都是先進先出B、都是先進后出C、只允許在端點處插入和刪除元素D、沒有共同點標(biāo)準(zhǔn)答案：C知識點解析：棧和隊列都是運算受限的線性表，只允許在表端點處進行操作。本題正確答案為選項C。20、______是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)。A、列表B、高維數(shù)組C、雙端隊列D、二叉樹標(biāo)準(zhǔn)答案：A知識點解析：列表是樹形結(jié)構(gòu)，高維數(shù)組和二叉樹為非線性結(jié)構(gòu)。雙端隊列是線性結(jié)構(gòu)。本題正確答案為選項C。21、鏈表不具備的特點是______。A、可隨機訪問任何一個元素B、插入、刪除操作不需要移動元素C、無需事先估計存儲空間大小D、所需存儲空間與線性表長度成正比標(biāo)準(zhǔn)答案：A知識點解析：鏈表是線性表的鏈?zhǔn)酱鎯?，是用結(jié)點來存儲數(shù)據(jù)元素。線性表采用鏈表作為存儲結(jié)構(gòu)時，不能進行數(shù)據(jù)元素的隨機訪問，其優(yōu)點是插入和刪除操作不需要移動元素。所以，本題應(yīng)該選擇A。22、與單向鏈表相比，雙向鏈表______。A、需要較少的存儲空間B、遍歷元素需要的時間較長C、較易于訪問相鄰結(jié)點D、較易于插入和刪除元素標(biāo)準(zhǔn)答案：D知識點解析：在單向鏈表中，只能沿著一個方向訪問結(jié)點。在雙向鏈表中，可以向前訪問結(jié)點，也可以向后訪問結(jié)點。所以，雙向鏈表的插入和刪除操作更為容易。選項D為正確答案。23、若in、out分別表示入、出隊操作，初始隊列為空且元素a、b、c依次入隊，則經(jīng)過操作序列in、in、out、out、in、out之后，得到的出隊序列為______。A、cbaB、bacC、bcaD、abe標(biāo)準(zhǔn)答案：D知識點解析：隊列的運算特點是先進先出。初始隊列為空且元素a、b、c依次入隊，則經(jīng)過操作序列in、in、out、out、in、out的過程，如圖8-9的(a)～(g)所示。通過圖可知，出隊序列為abc，所以，本題正確答案為選項D。24、在鏈表結(jié)構(gòu)中，采用______可以用最少的空間代價和最高的時間效率實現(xiàn)隊列結(jié)構(gòu)。A、僅設(shè)置尾指針的單向循環(huán)鏈表B、僅設(shè)置頭指針的單向循環(huán)鏈表C、僅設(shè)置尾指針的雙向鏈表D、僅設(shè)置頭指針的雙向鏈表標(biāo)準(zhǔn)答案：A知識點解析：從空間的角度考慮，采用鏈表作為存儲結(jié)構(gòu)，應(yīng)當(dāng)使用單鏈表，沒有必要采用雙向鏈表從兩個方向遍歷元素。所以排除選項C和選項D。隊列的特點是，先進先出。從時間效率的角度考慮，同時具有頭指針和尾指針的話，入隊和出隊操作最為簡單。但題目中僅僅給出了只有頭指針或者只有尾指針的情況。那么：①如果僅僅設(shè)置頭指針，那么，刪除元素時，只要修改第一個元素的指向即可。如果要插入元素，則需要遍歷整個鏈表，才能到達尾指針的位置。②如果僅僅設(shè)置尾指針，那么，如果要實現(xiàn)刪除操作，可以取尾指針域的值，直接獲得頭指針。如果要執(zhí)行插入操作，那么，修改兩個尾指針的指針域以及新插入結(jié)點的指針域即可。通過比較，僅僅設(shè)置尾指針，更節(jié)省時間。選項A是正確答案。25、判斷“鏈?zhǔn)疥犃袨榭铡钡臈l件是______(front為頭指針，rear為尾指針)。A、front==NULLB、rear==NULLC、front==rearD、front!=rear標(biāo)準(zhǔn)答案：C知識點解析：隊列的鏈?zhǔn)酱鎯σ卜Q為鏈隊列。為了便于操作，鏈隊列有一個頭結(jié)點，并令頭指針指向頭結(jié)點。因此，隊列為空的判定條件是：頭指針和尾指針的值相同，且均為指向頭結(jié)點。所以，本題應(yīng)該選擇C。二、中文選擇題（含2小題）(本題共2題，每題1.0分，共2分。)可以用棧來檢查算術(shù)表達式中的括號是否匹配。分析算術(shù)表達式時，初始棧為空，從左到右掃描字符，遇到字符“(”就將其入棧，遇到“)”就執(zhí)行出棧操作。對算術(shù)表達式“(a+b*(a+b))/c)+(a+b)”，檢查時，(1)；對算術(shù)表達式“((a+b/(a+b)-c/a)/b”，檢查時，(2)。這兩種情況都表明所檢查的算術(shù)表達式括號不匹配。26、可以用棧來檢查算術(shù)表達式中的括號是否匹配。分析算術(shù)表達式時，初始棧為空，從左到右掃描字符，遇到字符“(”就將其入棧，遇到“)”就執(zhí)行出棧操作。對算術(shù)表達式“(a+b*(a+b))/c)+(a+b)”，檢查時，(1)；對算術(shù)表達式“((a+b/(a+b)-c/a)/b”，檢查時，(2)。這兩種情況都表明所檢查的算術(shù)表達式括號不匹配。A、棧為空卻要進行出棧操作B、棧已滿卻要進行入棧操作C、表達式處理已結(jié)束，棧中仍留下有字符“(”D、表達式處理已結(jié)束，棧中仍留下有字符“)”標(biāo)準(zhǔn)答案：A知識點解析：暫無解析27、A、棧為空卻要進行出棧操作B、棧已滿卻要進行入棧操作C、表達式處理已結(jié)束，棧中仍留下有字符“(”D、表達式處理已結(jié)束，棧中仍留下有字符“)”標(biāo)準(zhǔn)答案：C知識點解析：棧是先進后出的線性表。對算術(shù)表達式“(a/b*(a+b))/c)+(a+b)”進行括號檢查時，操作順序為：①遇到第1個左括號，進行入棧操作。棧中有1個左括號。②遇到第2個左括號，進行入棧操作。棧中有2個左括號。③遇到第1個右括號，進行出棧操作。棧中有1個左括號。④遇到第2個右括號，進行出棧操作。棧中沒有左括號。⑤遇到第3個右括號，進行出棧操作。但此時為空棧，無法進行出棧操作。表達式檢查結(jié)束。第1空的正確答案為選項A。對算術(shù)表達式“((a+b/(a+b)-c/a)幾”進行括號檢查時，操作順序為：①遇到第1個左括號，進行入棧操作。棧中有1個左括號。②遇到第2個左括號，進行入棧操作。棧中有2個左括號。③遇到第3個左括號，進行入棧操作。棧中有3個左括號。④遇到第1個右括號，進行出棧操作。棧中有2個左括號。⑤遇到第2個右括號，進行出棧操作。棧中有1個左括號。表達式檢查結(jié)束。棧中依然還有左括號，表示表達式不匹配，第2空的正確答案為選項C。數(shù)據(jù)結(jié)構(gòu)練習(xí)試卷第4套一、中文選擇題(本題共25題，每題1.0分，共25分。)二叉樹(1)。在完全的二叉樹中，若一個結(jié)點沒有(2)，則它必定是葉結(jié)點。每棵樹都能唯一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個結(jié)點N的左子結(jié)點是N在原樹里對應(yīng)結(jié)點的(3)，而N的右子結(jié)點是它在原樹里對應(yīng)結(jié)點的(4)。1、二叉樹(1)。在完全的二叉樹中，若一個結(jié)點沒有(2)，則它必定是葉結(jié)點。每棵樹都能唯一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹里，一個結(jié)點N的左子結(jié)點是N在原樹里對應(yīng)結(jié)點的(3)，而N的右子結(jié)點是它在原樹里對應(yīng)結(jié)點的(4)。A、是特殊的樹B、不是樹的特殊形式C、是兩棵樹的總稱D、是只有兩個根結(jié)點的樹形結(jié)構(gòu)標(biāo)準(zhǔn)答案：B知識點解析：暫無解析2、A、左子結(jié)點B、右子結(jié)點C、左子結(jié)點或者沒有右子結(jié)點D、兄弟標(biāo)準(zhǔn)答案：A知識點解析：暫無解析3、A、最左子結(jié)點B、最右子結(jié)點C、最鄰近的右兄弟D、最鄰近的左兄弟標(biāo)準(zhǔn)答案：A知識點解析：暫無解析4、A、最左子結(jié)點B、最右子結(jié)點C、最鄰近的右兄弟D、最鄰近的左兄弟標(biāo)準(zhǔn)答案：C知識點解析：樹是結(jié)點的有限集合，它有且僅有1個根結(jié)點。二叉樹有0個或1個根結(jié)點，二者是兩個不同的概念。所以，第1空的正確答案為選項B。在完全二叉樹中，如果一個結(jié)點沒有左子結(jié)點，那么必然沒有右子結(jié)點，所以就一定是葉結(jié)點。第2空的正確答案為選項A。樹中每個結(jié)點最多只有一個最左邊的孩子(長子)和一個右鄰的兄弟。按照這種關(guān)系很自然地就能將樹轉(zhuǎn)換成相應(yīng)的二叉樹：①在所有兄弟結(jié)點之間加一連線；②對每個結(jié)點，除了保留與其長子的連線外，去掉該結(jié)點與其他孩子的連線。因為樹根沒有兄弟，所以，樹轉(zhuǎn)換為二叉樹之后，二叉樹的根結(jié)點的右子樹必然為空。在由樹轉(zhuǎn)換成的二叉樹中，一個結(jié)點N的左一個結(jié)點N的左子結(jié)點是N在原樹里對應(yīng)結(jié)點的最左子結(jié)點，而N的右子結(jié)點是它在原樹里對應(yīng)結(jié)點的最鄰近的右兄弟。所以，第3空的正確答案為選項A，第4空的正確答案為選項C。5、在一棵非空二叉樹中，葉子節(jié)點的總數(shù)比度為2的節(jié)點總數(shù)多(43)個。A、-1B、0C、1D、2標(biāo)準(zhǔn)答案：C知識點解析：根據(jù)二叉樹的第3條性質(zhì)“對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1”，所以本題應(yīng)該選擇C。如果對二叉樹的性質(zhì)不熟悉，也可以用特例來解答此類題目。因為從題目的意思不難理解，這種情況對任何一顆非空二叉樹都存在。所以，可以例舉一棵最簡單的二叉樹——只有3個結(jié)點的滿二叉樹，它只有1個根，2個葉子。則度為2的結(jié)點只有1個根結(jié)點，所以葉子結(jié)點的總數(shù)比度為2的結(jié)點總數(shù)多1個。6、某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有______個葉子結(jié)點。A、18B、19C、8D、20標(biāo)準(zhǔn)答案：B知識點解析：二叉樹具有如下性質(zhì)：在任意一棵二叉樹中，度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。根據(jù)題意，度為2的結(jié)點為18個，那么，葉子結(jié)點就應(yīng)當(dāng)是19個。因此，本題的正確答案為選項B。7、設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為______。A、ACBEGFDB、ABCDEFGC、ACBEDFGD、ABCEDFG標(biāo)準(zhǔn)答案：A知識點解析：基本思路如下：①確定根結(jié)點。在前序遍歷中，首先訪問根結(jié)點，因此可以確定前序序列DBACFEG中的第一個結(jié)點D為二叉樹的根結(jié)點。②劃分左子樹和右子樹。在中序遍歷中，訪問根結(jié)點的次序為居中，首先訪問訪問左子樹上的結(jié)點，最后訪問右子樹上的結(jié)點，可知，在中序序列ABCDEFG中，以根結(jié)點D為分界線，子序列ABC在左子樹中，子序列EFG在右子樹中。如圖8-22所示。③確定左子樹的結(jié)構(gòu)。對于左子樹ABC，位于前序序列最前面的一個結(jié)點為子樹的根結(jié)點，根據(jù)前序遍歷結(jié)果，B為該子樹的根結(jié)點，中序序列中位于該根結(jié)點前面的結(jié)點構(gòu)成左子樹上的結(jié)點子序列，位于該根結(jié)點后面的結(jié)點構(gòu)成右子樹上的結(jié)點子序列，所以A為該左子樹的左結(jié)點，C為右結(jié)點。現(xiàn)在可確定左子樹結(jié)構(gòu)如圖8-23所示。④確定右子樹的結(jié)構(gòu)。同理，可知右子樹的結(jié)構(gòu)。本二叉樹恢復(fù)的結(jié)果如圖8-24所示。根據(jù)后序遍歷的原則，該二叉樹后序遍歷的結(jié)果為ACBEGFD。8、假設(shè)一棵二叉樹的后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，則其前序遍歷序列為______。A、ABCDEFGHIJB、ABDEGHJCFIC、ABDEGHJFICD、ABDEGJHCFI標(biāo)準(zhǔn)答案：B知識點解析：這類題目，可以根據(jù)所給條件，還原二叉樹，然后再進行前序遍歷。還原二叉樹的要點是首先確定根結(jié)點，再確定左子樹的組成結(jié)點和右子樹的組成結(jié)點。然后再針對每個左子樹和右子樹，繼續(xù)確定其根結(jié)點以及左右子樹。重點是，根據(jù)后序遍歷的特點是，最后一個結(jié)點必然為根。中序遍歷中，根結(jié)點的左邊，是左子樹的結(jié)點，右邊是右子樹的結(jié)點。分析過程如下：①首先，根據(jù)后序遍歷為DGJHEBIFCA，說明這棵二叉樹的根為A。再根據(jù)中序遍歷的結(jié)果：DBGEHJACIF，說明DBGEHJ在根結(jié)點A的左邊，為左子樹上的結(jié)點。CIF在根結(jié)點A的右邊，是右子樹上的結(jié)點。如圖8