2024年高等教育工學類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試考試歷年高頻考點試題摘選含答案

2024年高等教育工學類自考-02331數(shù)據(jù)結(jié)構(gòu)筆試考試歷年高頻考點試題摘選含答案第1卷一.參考題庫(共75題)1.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復雜度為（） A、AB、BC、CD、D2.已知單鏈表上一結(jié)點的指針為p，則在該結(jié)點之后插入新結(jié)點*s的正確操作語句為（）A、?p-＞next=s；?s-＞next=p->next；B、?s-＞next=p-＞next；?p-＞next=s；C、?p-＞next=s；?p-＞next=s-＞next；D、?p-＞next=s-＞next；?p-＞next=s；3.將如圖所示的二叉樹轉(zhuǎn)換為樹。 4.已知k階斐波那契序列的定義為： f0=0，f1=0，…，fk-2=0，fk-1=0； fn=fn-1+fn-2+…+fn-k，n=k，k+1，… 試編寫求k階斐波那契序列的第m項值的函數(shù)算法，k和m均以值調(diào)用的形式在函數(shù)參數(shù)表中出現(xiàn)。5.對完全二叉樹敘述正確的是（）。A、完全二叉樹就是滿二叉樹B、完全二叉樹和滿二叉樹編號不對應(yīng)C、完全二叉樹同一層上左子樹未滿不會有右子樹D、以上都不正確6.設(shè)計一個算法，其功能為：利用中序線索求結(jié)點的中序后繼。請將代碼補充完整。 7.以下函數(shù)為直接選擇排序算法，對a[1],a[2],…a[n]中的記錄進行直接選擇排序，完成程序中的空格。 8.分別采用堆排序，快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表，則最省時間的是冒泡算法，最費時間的是（）算法。9.在深度為6的完全二叉樹中（）。A、最少有31個結(jié)點，最多有64個結(jié)點B、最少有32個結(jié)點，最多有64個結(jié)點C、最少有31個結(jié)點，最多有63個結(jié)點D、最少有32個結(jié)點，最多有63個結(jié)點10.在一個有向圖的拓撲序列中，若頂點a在頂點b之前，則圖中必有一條弧。11.二叉樹就是結(jié)點度為2的樹。12.數(shù)據(jù)結(jié)構(gòu)里，二叉樹的形態(tài)可以是（）。A、只有根結(jié)點和左子樹B、只有根結(jié)點和右子樹C、既有左子樹又有右子樹D、只有根結(jié)點13.在順序棧中進行退棧操作時，（）。A、誰先誰后都可以B、先移動棧頂指針，后取出元素C、不分先后，同時進行D、先取出元素，后移動棧頂指針14.設(shè)數(shù)組S[n]作為兩個棧S1和S2的存儲空間，對任何一個棧只有當S[n]全滿時才不能進行進棧操作。為這兩個棧分配空間的最佳方案是（）。A、S1的棧底位置為0，S2的棧底位置為n-1B、S1的棧底位置為0，S2的棧底位置為n/2C、S1的棧底位置為0，S2的棧底位置為nD、S1的棧底位置為0，S2的棧底位置為115.在一個單鏈表中刪除p所指結(jié)點的后繼結(jié)點時，應(yīng)執(zhí)行以下操作：q=p->next；p->next=（）；16.表達式求值是（）應(yīng)用的一個典型例子。17.如果從一個頂點出發(fā)又回到該頂點，則此路徑叫做（）。18.在線性表的散列存儲中，處理沖突有（）和（）兩種方法。19.二維數(shù)組M[i，j]的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下列j的范圍從0到5。M按行存儲時元素M[3，5]的起始地址與M按列存儲時元素（）的起始地址下同。A、M[2，4]B、M[3，4]C、M[3，5]D、M[4，4]20.已知哈希表地址空間為A[0..8]，哈希函數(shù)為H（k）=k?mod?7，采用線性探測再散列處理沖突。若依次將數(shù)據(jù)序列：76，45，88，21，94，77，17存入該散列表中則元素17存儲的下標為（）。A、0B、1C、2D、3E、4F、5G、6H、721.將下面圖5-16所示的樹轉(zhuǎn)換為二叉樹，圖5-17所示的二叉樹轉(zhuǎn)換為樹或森林。 22.以下表中可以隨機訪問的是（）A、單向鏈表B、雙向鏈表C、單向循環(huán)鏈表D、順序表23.給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。24.若需在O（nlog2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A、快速排序B、堆排序C、歸并排序D、直接插入排序25.當待排序記錄已經(jīng)從小到大排序或者已經(jīng)從大到小排序時，快速排序的執(zhí)行時間最省。26.設(shè)數(shù)據(jù)集合a={1，12，5，8，3，10，7，13，9} （1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 （2）說明如何依據(jù)此二叉樹得到a的有序序列。 （3）對該二叉樹進行查找，成功查找到7要進行多少次元素間的比較？ （4）給出對該二叉樹后序遍歷的序列。27.數(shù)據(jù)結(jié)構(gòu)里，棧是后進先出的線性結(jié)構(gòu)，應(yīng)用于表達式求值、括號匹配、進制轉(zhuǎn)換等算法中幫助算法完成。28.以鏈表作為棧的存儲結(jié)構(gòu)，出棧操作必須判別?？盏那闆r。29.設(shè)數(shù)據(jù)集合a={62，74，30，15，56，48} （1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 （2）為了成功查找到48需要進行多少次元素間的比較？ （3）給出對該二叉樹后序遍歷的序列。30.數(shù)組元素的下標值越大，存取時間越長31.數(shù)據(jù)結(jié)構(gòu)里，用算法的時間復雜度來衡量算法的效率高低。32.推到和估算算法的時間復雜度屬于（）。A、事前分析估算的方法B、事后統(tǒng)計方法C、運行后計算時間D、都不對33.設(shè)要將序列（Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X）中的關(guān)鍵碼按升序排列，則（）是起泡排序一趟掃描的結(jié)果，（）是增量為4的希爾排序一趟掃描的結(jié)果，（）二路歸并排序一趟掃描的結(jié)果，（）是以第一個元素為軸值的快速排序一趟掃描的結(jié)果，（）是堆排序初始建堆的結(jié)果。34.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。35.在一個長度為n的順序表中刪除第i個元素（0A、n-iB、n-i+lC、n-i-1D、i36.設(shè)有一個棧，按A、B、C、D的順序進棧，則下列（）為可能的出棧序列。A、DCABB、CDABC、DBACD、ACDB37.串是一中特殊的線性表，其特殊性體現(xiàn)在（）A、可以順序存儲B、數(shù)據(jù)元素是一個字符C、可以鏈接存儲D、數(shù)據(jù)元素可以是多個字符38.用數(shù)組Q表示一個環(huán)形隊列，f為當前對頭元素的錢一位置，r為隊尾元素的位置。假定隊列中元素個數(shù)總小于n，求隊列中元素個數(shù)公式是（）。39.數(shù)據(jù)結(jié)構(gòu)里，將順序表s的下標為i的元素修改為e，哪個語句正確（）。A、s[i]=e；B、s=e；C、s（i）=e；D、s=ei；40.n個結(jié)點的完全有向圖含有邊的數(shù)目（）。A、n*nB、n（n＋1）C、n/2D、n（n－1）41.數(shù)據(jù)結(jié)構(gòu)里，線性結(jié)構(gòu)是（）。A、一對一關(guān)系B、一對多關(guān)系C、多對多關(guān)系D、沒有關(guān)系42.順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。43.無向圖G中極大連通子圖稱為G的（）。44.在一個長度為n的順序存儲線性表中，向第i個元素（1≤i≤n+1）之前插入一個新元素時，需要從后向前依次后移（）個元素。A、n-iB、n-i+1C、n-i-1D、i45.intgetLength（intn） { if（n>=0） { returnn； } else { return-1； } }該程序的時間復雜度為：（）。A、O（n）B、O（nn）C、O（1）D、O（log2n）46.m階B—樹中每個結(jié)點的子樹個數(shù)都大于或等于[m/2]。47.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。48.設(shè)rear是指向非空、帶頭結(jié)點的循環(huán)單鏈表的尾指針，則該鏈表首結(jié)點的存儲位置是（）49.帶頭結(jié)點的單鏈表head為空的判定條件是（）。A、head==NULLB、head->next==NULLC、head->next!=NULLD、head!=NULL50.數(shù)據(jù)結(jié)構(gòu)里，結(jié)構(gòu)體變量的定義需要給變量加‘’號。51.算法的特性包含輸入、輸出、有窮性、確定性、（）。A、正確性B、可行性C、輸入D、模糊性52.若一個元素序列基本有序，則選用（）排序較快。A、堆排序B、快速排序C、直接插入法D、直接選擇排序53.下面關(guān)于二叉樹敘述正確的是（）。A、二叉樹是特殊的樹B、二叉樹等價于度為2的樹C、完全二叉樹必為滿二叉樹D、二叉樹的左右子樹有次序之分54.n個頂點的連通圖至少有（）邊。55.在對n個元素進行堆排序的過程中，時間復雜度為（）A、?O（1）B、?O（log2n）C、?O（n2）D、?O（nlog2n）56.二叉樹必須有左子樹和右子樹，不能只有右子樹。57.矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。58.邊數(shù)很少的稀疏圖，適宜用鄰接表表示。59.以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格。 60.（）是元素之間的關(guān)系的集合。61.串“ababaabab”的nextval為（）。A、010104101B、010102101C、010100011D、01010101162.堆的形狀是一棵（）。A、二叉排序樹B、滿二叉樹C、完全二叉樹D、一般的二叉樹63.為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。A、隊列B、棧C、?線性表D、有序表64.在一個單鏈表中，若刪除p所指向結(jié)點的后續(xù)結(jié)點，則執(zhí)行（）。A、p->next=p->next->next；B、p=p->next；p->next=p->next->next；C、p=p->next；D、p=p->next->next；65.設(shè)待處理問題的規(guī)模為n，若一個算法的時間復雜度為一個常數(shù)，則表示成數(shù)量級的形式為（），若為n*log25n，則表示成數(shù)量級的形式為（）。66.下面（）是C語言中“abcd321ABCD”的子串。A、abcdB、321ABC、“abcAB”D、“21AB”67.求從某源點到其余各頂點的Dijkstra算法，當圖的頂點數(shù)為10，用鄰接矩陣表示圖時計算時間約為10ms，則當圖的頂點數(shù)為40時，計算時間約為（）ms。68.在樹的概念中，樹中某結(jié)點的直接前驅(qū)稱為該結(jié)點的（）A、雙親B、孩子C、兄弟D、堂兄弟69.為什么說棧是一種后進先出表？70.假設(shè)有一個循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點也無頭指針，已知p為指向鏈表中某結(jié)點的指針，設(shè)計在鏈表中刪除p所指結(jié)點的前趨結(jié)點的算法。71.在樹中除根結(jié)點外，其余結(jié)點分成m（m≥0）個（）的集合T1，T2，T3...Tm，每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點（1≤i≤m）。A、互不相交B、可以相交C、葉結(jié)點可以相交D、樹枝結(jié)點可以相交72.一組記錄為{46，79，56，38，84，40}，則采用冒泡排序法按升序排列時第一趟排序結(jié)果是（）A、46，79，56，38，40，84B、46，56，38，79，40，84C、38，40，46，56，84，79D、38，46，79，56，40，8473.若進棧序列為1，2，3，4，則不可能得到的出棧序列是（）。A、3，2，1，4B、3，2，4，1C、4，2，3，1D、2，3，4，174.解決哈希沖突的主要方法有（）。A、數(shù)字分析法、除余法、平方取中法B、數(shù)字分析法、除余法、線性探測法C、數(shù)字分析法、線性探測法、再哈希法D、線性探測法、再哈希法、鏈地址法75.單鏈表要求內(nèi)存中可用存儲單元的地址（）A、必須是連續(xù)的B、一定是不連續(xù)的C、部分地址必須是連續(xù)的D、可以是連續(xù)的，也可以是不連續(xù)的第2卷一.參考題庫(共75題)1.如果待排序序列中兩個數(shù)據(jù)元素具有相似的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的，（）就是不穩(wěn)定的排序算法。A、起泡排序B、歸并排序C、Shell排序D、直接插入排序E、簡單選擇排序2.帶權(quán)連通圖中某一頂點到圖中另一定點的最短路徑不一定唯一。3.簡述二叉樹的常用操作及各操作的含義。4.對于一個具有n個結(jié)點的單鏈表中，在已知的結(jié)點后插入一個新結(jié)點的時間復雜度為（）在給定值為X的結(jié)點后插入一個新結(jié)點的時間復雜度為（）。5.下述幾種排序方法中，（）是穩(wěn)定的排序方法。A、希爾排序B、快速排序C、歸并排序D、堆排序6.在索引順序結(jié)構(gòu)的搜索中，對索引表既可以采取順序搜索，也可以采用折半搜索。7.下面計算正確的敘述是（）A、計算fact（n）需要執(zhí)行n次遞B、fact（7）=5040C、此遞歸算法最多只能計算到fact（8）D、以上結(jié)論都不對8.模式串T=’abcaabbcabcaabdab’，該模式串的next數(shù)組值為（），nexrval數(shù)組的值為（）9.數(shù)據(jù)結(jié)構(gòu)里，算法具有模糊性，相同的情況可能產(chǎn)生不同的結(jié)果。10.長度為n的串s1與長度為2n的串s2的比較運算的時間復雜度是（）。11.有一個20階的對稱矩陣A（第一個元素為a1，1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素a6，2在一維數(shù)組B中的下標是（）。A、24B、17C、16D、2312.鏈表不具備的特點是（）。A、可隨機訪問任一結(jié)點B、插入刪除不需要移動元素C、不必事先估計存儲空間D、所需空間與其長度成正比13.在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則對該隊列進行出隊操作中并把結(jié)點的值保存在變量e中，其運算為和（） A、AB、BC、CD、D14.具有n個結(jié)點的滿二叉樹，其葉結(jié)點的個數(shù)為（n+1）/2。15.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A、1/2B、1C、2D、416.在散列查找中，平均查找長度主要與（）有關(guān)。A、散列表長度B、散列元素個數(shù)C、裝填因子D、處理沖突方法17.簡述索引文件的構(gòu)成。18.通常將鏈接方式存儲的線性表稱為（），它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。19.對于一個圖G，若邊集E（G）為無向邊的集合，則該圖為（）。20.凡是遞歸定義的數(shù)據(jù)結(jié)構(gòu)都可以用遞歸算法來實現(xiàn)它的操作。21.判定一個棧ST（最多元素為m0）為空的條件是（）A、ST->top0B、ST->top=0C、ST->topm0D、ST->top=m022.某完全二叉樹按層次編號后，某結(jié)點是i，若有左孩子，則左孩子的編號是（）。A、2iB、2i+1C、2i-1D、i/223.有向圖頂點V的度等于其（）之和。24.在一個有向圖中，若存在弧，則在其拓撲序列中，頂點vi，vj，vk的相對次序為（）。25.若一個圖的邊集為{，，，，，}，則從頂點1開始對該圖進行廣度優(yōu)先搜索，得到的頂點序列可能為（）。A、?1，2，3，4，5B、?1，2，4，3，5C、?1，2，4，5，3D、?1，4，2，5，326.將某完全二叉樹的結(jié)點按層次編號后，某結(jié)點的編號是i，它的右孩子（存在）的編號是（）。A、2i+1B、2i-1C、i/2D、i*3/227.S1="good"，S2="morning"，執(zhí)行函數(shù)SubStr（S2，4，LenStr（S1））后的結(jié)果為（）。A、"good"B、"ning"C、"go"D、"morn"28.下列選項中關(guān)于算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系描述正確的是（）。A、程序=數(shù)據(jù)結(jié)構(gòu)+算法B、算法與數(shù)據(jù)結(jié)構(gòu)是緊密聯(lián)系不可分割，必須在一起才能最終解決問題C、數(shù)據(jù)結(jié)構(gòu)就是編程的思維，編程的靈魂，算法的精髓所在D、算法與數(shù)據(jù)結(jié)構(gòu)是相互獨立的，算法和C語言有一定的聯(lián)系29.一個算法一該具有（）這五種特性。30.設(shè)無向圖的頂點個數(shù)為n，則該圖可以有（）條邊。A、n-1B、n（n-1）/2C、n（n+1）/2D、nn31.若要在單鏈表結(jié)點*P后插入一結(jié)點*S，執(zhí)行的語句（）。32.關(guān)于特殊二叉樹的遍歷，下列選項中說法正確的是（）。A、完全二叉樹不能進行遍歷B、完全二叉樹可以進行遍歷C、完全二叉樹不可以進行遍歷D、滿二叉樹不是完全二叉樹33.試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，且樹中結(jié)點的關(guān)鍵字均不同。34.將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為（）A、98B、99C、50D、4835.設(shè)散列表容量為7（散列地址空間0..6），給定表（30，36，47，52，34），散列函數(shù)H（K）=Kmod6，采用線性探測法解決沖突，要求：（1）構(gòu)造散列表；（2）求查找數(shù)34需要比較的次數(shù)。36.二叉查找樹的查找效率與二叉樹的樹型有關(guān)，在（）時其查找效率最低。A、結(jié)點太多B、完全二叉樹C、呈單枝樹D、結(jié)點太復雜37.變更磁盤上順序文件的記錄內(nèi)容時，不一定要復制整個文件。38.對于右圖所示的樹： 寫出先根遍歷得到的結(jié)點序列。39.設(shè)有一個14階的對稱矩陣A（第一個元素為a1，1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素a4，3在一維數(shù)組B中的下標是（）。A、9B、10C、11D、840.在一個單向鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（）。A、p->next=s；s->next=p->nextB、p->next=s->next；C、p=s->nextD、s->next=p->next；?p->next=s；41.樹的帶權(quán)路徑長度最小的二叉樹中必定沒有度為1的結(jié)點。42.一個隊列的入隊序列是1，2，3，4，則隊列的出隊序列是（）。A、1，2，3，4B、4，3，2，1C、1，4，3，2D、3，4，1，243.一棵高度為10的滿二叉樹中的結(jié)點總數(shù)為（）個，其中葉子結(jié)點數(shù)為（）44.數(shù)據(jù)結(jié)構(gòu)里，順序表中，查找下標為i的元素的時間復雜度是（）。A、O（1）B、O（n）C、O（nn）D、O（log2n）45.對于一個具有n個頂點和e條邊的無向圖，當分別采用鄰接矩陣和鄰接表表示時，求任一頂點度數(shù)的時間復雜度分別為（）和（）46.下面關(guān)于線性表的敘述中，錯誤的是（）A、線性表采用順序存儲，必須占用一片連續(xù)的存儲空間。B、線性表采用順序存儲，進行插入和刪除操作，不需要進行數(shù)據(jù)元素間的移動。C、線性表采用鏈式存儲，不必占用連續(xù)的存儲空間。D、線性表采用鏈式存儲，進行插入刪除操作，不需要移動元素。47.已知某森林的二叉樹如下所示，試畫出它所表示的森林。 48.數(shù)據(jù)結(jié)構(gòu)里，下列選項中關(guān)于算法設(shè)計要求的正確性描述正確的是（）。A、正確性是算法應(yīng)當滿足具體問題的需求B、正確性是為了便于閱讀、理解和交流C、正確性是算法應(yīng)該能對輸入數(shù)據(jù)不合法的形況做出適當?shù)奶幚鞤、正確性是指算法正確的執(zhí)行時間49.線性結(jié)構(gòu)的特點是什么？非線性結(jié)構(gòu)的特點是什么？50.評價排序算法優(yōu)劣的主要標準是（）和（）51.（1）一組記錄的關(guān)鍵字序列為（36，69，46，28，30，35），給出利用堆排序（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述?）。 （2）對關(guān)鍵字序列（36，69，46，28，30，74）采用快速排序，給出以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。 （3）設(shè)有數(shù)據(jù)集合{30，73，101，4，8，9，2，81}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。52.對于記錄序列A[1]~A[n]可按如下如下方法實現(xiàn)奇偶交換排序：第一趟對所有的奇數(shù)i，將A[i]和A[i+1]進行比較，第二趟對所有的偶數(shù)i，將A[i]和A[i+1]進行比較，每次比較時若A[i]>A[i+1]，則將二者交換，然后重復上述排序過程，直至整個數(shù)組有序。編寫算法實現(xiàn)上述奇偶交換排序。53.對矩陣進行壓縮存儲是為了（）。A、方便運算B、方便存儲C、提高運算速度D、減少存儲空間54.中序遍歷二叉排序樹得到的序列是（）序列（填有序或無序）。55.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。56.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。57.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個結(jié)點包含有（）個域，在相應(yīng)的十字鏈接存儲中，每個結(jié)點包含有（）個域。58.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的（）、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算這三個方面的內(nèi)容。59.根據(jù)插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序樹。 若仍以該插入次序建立平衡二叉樹。圖（）是最終變化的結(jié)果。A、aB、bC、cD、d60.如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是（）。A、1B、2C、3D、461.一個棧的輸入序列為1、2、3，試給出全部可能的出棧序列。62.從存儲結(jié)構(gòu)上可以把數(shù)據(jù)結(jié)構(gòu)分為（）兩大類。A、動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B、順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C、線性結(jié)構(gòu)、非線性結(jié)構(gòu)D、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)63.對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復雜度為O（n）。64.算法分析的兩個方面是（）A、空間復雜性和時間復雜性B、正確性和簡明性C、可讀性和文檔性D、數(shù)據(jù)復雜性和程序復雜性65.表達式求值算法需要兩個棧，它們分別是下列哪些（），分別用于存儲數(shù)據(jù)和符號。A、數(shù)據(jù)棧B、符號棧C、中間結(jié)果棧D、漢字棧66.序表中邏輯上相鄰的元素的物理位置（）67.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為（）68.棧是一個（）線性表結(jié)構(gòu)。A、不加限制的B、加了限制的C、推廣了的D、非69.排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是（）。A、直接插入排序B、簡單選擇排序C、快速排序D、歸并排序70.文件中每個記錄最多只有一個后繼記錄和一個前驅(qū)記錄，而文件的第一個記錄只有后繼而沒有前驅(qū)，最后一個記錄只有前驅(qū)卻沒有后繼；因此，文件可看成是一種線性結(jié)構(gòu)。71.樹最適合用來表示：（）A、有序數(shù)據(jù)元素B、無序數(shù)據(jù)元素C、元素之間具有分支層次關(guān)系的數(shù)據(jù)D、元素之間無聯(lián)系的數(shù)據(jù)72.一個隊列的入隊順序是1，2，3，4，則隊列的輸出順序是（）。A、4321B、1234C、1432D、324173.表長為n的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動的元素平均個數(shù)為（），刪除一個元素所需移動的平均個數(shù)為。A、（n-1）/2B、nC、n+1D、n-1E、n/274.直接選擇排序是一種不穩(wěn)定的排序方法。75.數(shù)據(jù)結(jié)構(gòu)里，單鏈表是指（）。A、有兩個指針域的鏈表。B、只有一個指針域的鏈表。C、有三個指針域的鏈表。D、沒有指針域的鏈表。第1卷參考答案一.參考題庫1.參考答案：B2.參考答案：B3.參考答案：第一步，加線。第二步，抹線。第三步，調(diào)整。過程如圖所示。4.參考答案：5.參考答案：C6.參考答案：7.參考答案：8.參考答案：快速9.參考答案：D10.參考答案：錯誤11.參考答案：錯誤12.參考答案：A,B,C,D13.參考答案：D14.參考答案：A15.參考答案：q->next16.參考答案：棧17.參考答案：環(huán)/回路18.參考答案：開放定址；鏈接19.參考答案：B20.參考答案：F21.參考答案：圖5-16所示樹轉(zhuǎn)換的二叉樹如圖5-18所示，圖5-17所示二叉樹轉(zhuǎn)換的森林如圖5-19所示。 22.參考答案：D23.參考答案：24.參考答案：C25.參考答案：錯誤26.參考答案：（1）如圖 （2）中序遍歷1，3，5，7，8，9，10，12，13 （3）5次 （4）3，7，9，10，8，5，13，12，1 27.參考答案：正確28.參考答案：正確29.參考答案：（1）如圖 （2）4次 （3）15，48，56，30，74，62 30.參考答案：錯誤31.參考答案：正確32.參考答案：A33.參考答案：（H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y）；（P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y）；（H，Q，C，Y，A，P，M，S，D，R，F(xiàn)，X）；（F，H，C，D，P，A，M，Q，R，S，Y，X）；（A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X）34.參考答案：正確35.參考答案：A36.參考答案：D37.參考答案：B38.參考答案：（r-f+n）%n39.參考答案：A40.參考答案：D41.參考答案：A42.參考答案：錯誤43.參考答案：連通分量44.參考答案：B45.參考答案：C46.參考答案：錯誤47.參考答案：錯誤48.參考答案：rear-＞next-＞next49.參考答案：B50.參考答案：錯誤51.參考答案：B52.參考答案：C53.參考答案：D54.參考答案：n-1條55.參考答案：D56.參考答案：錯誤57.參考答案：正確58.參考答案：正確59.參考答案：60.參考答案：結(jié)構(gòu)61.參考答案：A62.參考答案：C63.參考答案：A64.參考答案：A65.參考答案：Ο（1）；Ο（nlog2n）66.參考答案：D67.參考答案：16068.參考答案：A69.參考答案：棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂（top），另一端為棧底（bottom）；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進先出表（LIFO--LastINFirstOut表）。70.參考答案：71.參考答案：A72.參考答案：B73.參考答案：C74.參考答案：D75.參考答案：D第2卷參考答案一.參考題庫1.參考答案：C,E2.參考答案：正確3.參考答案：創(chuàng)建一棵空二叉樹：創(chuàng)建一棵沒有任何結(jié)點的二叉樹。在順序表示中，根據(jù)樹的深度為結(jié)點分配內(nèi)存；在二叉鏈表表示中，將指向根結(jié)點的指針賦值為NULL。 刪除一棵二叉樹：將二叉樹各結(jié)點所占據(jù)的內(nèi)存釋放。 清空二叉樹：將二叉樹的所有結(jié)點刪除，使之成為一棵空二叉樹。 以指定元素值創(chuàng)建根結(jié)點：創(chuàng)建根結(jié)點，并以指定值作為根結(jié)點的元素值。 將一個結(jié)點作為指定結(jié)點的左孩子插入：根據(jù)指定元素值生成一個新結(jié)點，并將其作為指定結(jié)點的左孩子。 將一個結(jié)點作為指定結(jié)點的右孩子插入：根據(jù)指定元素值生成一個新結(jié)點，并將其作為指定結(jié)點的右孩子。 先序遍歷二叉樹：也稱為先根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問其根結(jié)點，再訪問根結(jié)點的左、右子樹；對于左、右子樹中的結(jié)點仍然是按照先序遍歷方式訪問，即先訪問根結(jié)點，再訪問根結(jié)點的左、右子樹。 中序遍歷二叉樹：也稱為中根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點左子樹，再訪問根結(jié)點，最后訪問右子樹；對于左、右子樹中的結(jié)點仍然是按照中序遍歷方式訪問。 后序遍歷二叉樹：也稱為后根遍歷，其訪問方式遞歸定義如下：對于一棵二叉樹，先訪問根結(jié)點的左子樹，后訪問右子樹，最后訪問根結(jié)點；對于左、右子樹中的結(jié)點仍然是按照后序遍歷方式訪問。 逐層遍歷二叉樹：從