【MOOC】數據結構-華中科技大學 中國大學慕課MOOC答案

【MOOC】數據結構-華中科技大學中國大學慕課MOOC答案第一章緒論單元測試1、【單選題】______是數據的最小單位。本題答案：【數據項】2、【單選題】以下說法不正確的是______。本題答案：【數據項可由若干個數據元素構成】3、【單選題】數據結構是指______的集合以及它們之間的關系。本題答案：【數據元素】4、【單選題】計算機所處理的數據一般具備某種內在聯(lián)系，這是指______。本題答案：【元素和元素之間存在某種關系】5、【單選題】在數據結構中，與所使用的計算機無關的是數據的______結構。本題答案：【邏輯】6、【單選題】數據的邏輯結構可以分為______兩類。本題答案：【線性結構和非線性結構】7、【單選題】數據的邏輯結構是指______關系的整體。本題答案：【數據元素之間邏輯】8、【單選題】以下是數據結構中______屬非線性結構。本題答案：【平衡二叉樹】9、【單選題】以下屬于邏輯結構是______。本題答案：【有序表】10、【單選題】以下不屬于存儲結構是______。本題答案：【線性表】11、【單選題】在計算機中存儲數據時，通常不僅要存儲各數據元素的值，而且還有存儲______。本題答案：【數據元素之間的關系】12、【單選題】數據結構在計算機內存中的表示是指______。本題答案：【數據的存儲結構】13、【單選題】在數據的存儲中，一個節(jié)點通常存儲一個______。本題答案：【數據元素】14、【單選題】在決定選取任何類型的存儲結構時，一般不多考慮______。本題答案：【各節(jié)點的值如何】15、【單選題】數據在計算機的存儲器中表示時，邏輯上相鄰的兩個元素對應的物理地址也是相鄰的，這種存儲結構稱之為______。本題答案：【順序存儲結構】16、【單選題】數據采用鏈式存儲結構時，要求______。本題答案：【每個節(jié)點占用一片連續(xù)的存儲區(qū)域】17、【單選題】數據的運算______。本題答案：【與采用何種存儲結構有關】18、【單選題】_______不是算法的基本特性。本題答案：【在規(guī)定的時間內完成】19、【單選題】計算機中算法指的是解決某一問題的有限運算序列，它必須具備輸入、輸出、_______。本題答案：【可行性、有窮性和確定性】20、【單選題】一個算法具有________等設計目標。本題答案：【健壯性】21、【單選題】以下關于算法的說法正確的是____________。本題答案：【其他幾個都是錯誤的】22、【單選題】算法的時間復雜度與_______有關。本題答案：【問題規(guī)?！?3、【單選題】算法分析的主要任務之一是分析_______。本題答案：【算法的執(zhí)行時間和問題規(guī)模之間的關系】24、【單選題】算法的時間復雜度為O(n2)，表明該算法的_______。本題答案：【執(zhí)行時間與成正比】25、【單選題】算法分析的目的是_______。本題答案：【分析算法的效率以求改進】26、【單選題】以下函數中時間復雜度最小的是_______。本題答案：【T4(n)=20000log2n】27、【單選題】以下函數中時間復雜度最小的是_______。本題答案：【T1(n)=1000log2n】28、【單選題】以下說法中錯誤的是_______。（1）原地工作算法的含義是指不需要任何額外的輔助空間（2）在相同的問題規(guī)模下n下，時間復雜度為O(nlog2n)的算法在執(zhí)行時間上總是優(yōu)于時間復雜度為O()的算法（3）時間復雜度通常是指最壞情況下，估計算法執(zhí)行時間的一個上限（4）一個算法的時間復雜度與實現算法的語言無關本題答案：【（1）、（2）】29、【單選題】以下數據結構中哪一個是非線性結構？本題答案：【二叉樹】30、【單選題】下面程序的時間復雜為_______。for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}本題答案：【O()】31、【單選題】一個算法的時間復雜度為(+log2n+14n)/，其數量級表示為_______。本題答案：【O(n)】32、【單選題】取算法的時間復雜度為O（），當n=5時執(zhí)行時間為50s，當n=15時，執(zhí)行時間為_______。本題答案：【1350】33、【單選題】下面程序的時間復雜度為_______。voidfun(intn){inti=1;while(i=n)i=i*2}本題答案：【O(log2n)】34、【單選題】下面程序的時間復雜度為_______。voidfun(intn){inti=1;while(i=n)i=i*3}本題答案：【O(log3n)】35、【單選題】下面程序的時間復雜度為_______。voidfun(intn){inti=1,k=100;while(i=n){k++;i+=2;}}本題答案：【O(n)】36、【判斷題】數據元素是數據的最小單位。本題答案：【錯誤】37、【判斷題】數據對象就是一組任意數據元素的集合。本題答案：【錯誤】38、【判斷題】任何數據結構都具備3個基本運算：插入、刪除、和查找。本題答案：【錯誤】39、【判斷題】數據的邏輯結構與數據元素在計算機中如何存儲有關。本題答案：【錯誤】40、【判斷題】如果數據元素值發(fā)生改變，則數據的邏輯結構也隨之改變。本題答案：【錯誤】41、【判斷題】邏輯結構相同的數據，可以采用多種不同的存儲方法。本題答案：【正確】42、【判斷題】邏輯結構不相同的數據，必須采用多種不同的存儲方法。本題答案：【錯誤】43、【判斷題】邏輯結構相同的數據，在設計存儲結構時，它們的節(jié)點類型也一定相同。本題答案：【錯誤】44、【判斷題】數據的邏輯結構時指數據的各數據項之間的邏輯關系。本題答案：【錯誤】45、【判斷題】算法的優(yōu)劣與算法描述語言無關，但與所用的計算機有關。本題答案：【錯誤】46、【判斷題】算法可以用不同的語言描述，如果用C或PASCAL語言等高級語言來描述，則算法實際上就是程序了。本題答案：【錯誤】47、【判斷題】程序一定是算法。本題答案：【錯誤】48、【判斷題】算法最終必須由計算機程序實現.本題答案：【錯誤】49、【判斷題】算法的可行性是指指令不能有二義性。本題答案：【錯誤】50、【判斷題】健壯的算法不會因非法輸入數據而出現莫名其妙的狀態(tài)。本題答案：【正確】第二章線性表單元測試1、【單選題】線性表是具有n個______的有限序列。本題答案：【數據元素】2、【單選題】線性表是_______。本題答案：【一個有限序列，可以為空】3、【單選題】關于線性表的正確說法是_______。本題答案：【除第一個元素和最后一個元素外，其余元素有且僅有一個前驅和一個后繼元素】4、【單選題】線性表采用鏈表存儲時，其存放各個元素的單元地址是_______。本題答案：【連續(xù)與否均可以】5、【單選題】鏈表不具備的特點是_______。本題答案：【可隨機訪問任一節(jié)點】6、【單選題】線性表的靜態(tài)鏈表存儲結構與順序存儲結構相比，優(yōu)點是_______。本題答案：【便于插入和刪除】7、【單選題】線性表的順序存儲結構和鏈式存儲結構相比，優(yōu)點是_______。本題答案：【便于隨機存取】8、【單選題】設線性表有n個元素，以下操作中，_______在順序表上實現比在鏈表上實現效率高。本題答案：【輸入第i（1=i=n）個元素值】9、【單選題】對于一個線性表，既要求能夠較快地進行插入和刪除操作，又要求存儲結構能夠反映數據元素之間的邏輯關系，則應采用_______存儲結構。本題答案：【鏈式】10、【單選題】設線性表中有n個元素，以下操作，_______在單鏈表上實現要比在順序表上實現效率高。本題答案：【刪除指定位置元素的后一個元素】11、【單選題】以下屬于順序表的優(yōu)點是_______。本題答案：【存儲密度大】12、【單選題】要求線性表采用靜態(tài)空間分配方式，且插入和刪除操作時不需要移動元素，采用的存儲結構是_______。本題答案：【靜態(tài)鏈表】13、【單選題】如果最常用的操作時取第i個元素及前驅元素，則采用_______存儲方式最節(jié)省時間。本題答案：【順序表】14、【單選題】與單鏈表相比，雙鏈表的優(yōu)點之一是_______。本題答案：【訪問前后相鄰節(jié)點更方便】15、【單選題】在長度為n的順序表中插入一個元素的時間復雜度為_______。本題答案：【O(n)】16、【單選題】在長度為n的順序表中刪除一個元素的時間復雜度為_______。本題答案：【O(n)】17、【單選題】在兩個各有n個元素的遞增有序順序表歸并成一個有序順序表，其最少的比較次數為_______。本題答案：【n】18、【單選題】將兩個長度為n、m的遞增有序表歸并成一個有序順序表，其最少的比較次數是_______。（MIN表示取最小值）本題答案：【MIN(m,n)】19、【單選題】在帶頭節(jié)點的單鏈表L為空的判定條件是_______。本題答案：【L-NEXT==NULL】20、【單選題】對于一個具有n個元素的線性表，建立其單鏈表的時間復雜度為_______。本題答案：【O(n)】21、【單選題】在單鏈表中查找指定值的節(jié)點的時間復雜度是_______。本題答案：【O(n)】22、【單選題】以下關于單鏈表的敘述中，不正確的是_______。本題答案：【可以通過頭節(jié)點直接計算第i個節(jié)點的存儲地址】23、【單選題】在單鏈表中，增加一個頭節(jié)點的目的是為了_______。本題答案：【方便運算的實現】24、【單選題】在一個具有n個節(jié)點的有序單鏈表中插入一個新節(jié)點并仍然保持有序的時間復雜度是_______。本題答案：【O(n)】25、【單選題】將長度為m的單鏈表鏈接在長度為n的單鏈表之后的算法時間復雜度為_______。本題答案：【O(n)】26、【單選題】已知一個長度為n的單鏈表中所有節(jié)點是遞增有序的，以下敘述中正確的是_______。本題答案：【找最小值節(jié)點的算法的時間復雜度為O(1)】27、【單選題】在一個長度為n（n1）的帶頭節(jié)點的單鏈表上，另設有尾指針r（指向尾節(jié)點），執(zhí)行_______操作與鏈表的長度有關。本題答案：【刪除單鏈表的尾節(jié)點】28、【單選題】在一個雙鏈表中，在*p節(jié)點之后插入節(jié)點*q的操作是_______。本題答案：【q-next=p-next；p-next-prior=q；p-next=q；q-prior=p；】29、【單選題】在一個雙鏈表中，在*p節(jié)點之前插入節(jié)點*q的操作是_______。本題答案：【p-prior-next=q；q-next=p；q-prior=p-prior；p-prior=q；】30、【單選題】在一個雙鏈表中，刪除*p節(jié)點的操作是_______。本題答案：【p-prior–next=p-next；p-next-prior=p-prior；】31、【單選題】在一個雙鏈表中，刪除*p節(jié)點之后的一個節(jié)點，其時間復雜度為_______。本題答案：【O(1)】32、【單選題】非空的循環(huán)單鏈表L的尾節(jié)點（由p所指向）滿足_______。本題答案：【p-next==L】33、【單選題】帶表頭結點的雙循環(huán)鏈表L為空表的條件是_______。本題答案：【L-next==L】34、【單選題】某線性表最常用的操作是在尾元素之后插入一個元素和刪除尾元素，則采用_______存儲方式最節(jié)省運算時間。本題答案：【循環(huán)雙鏈表】35、【單選題】如果對含有n（n1）個元素的線性表的運算只有4種，即刪除第一個元素、刪除尾元素、在第一個元素前面插入新元素、在尾元素的后面插入新元素，則最好使用_______。本題答案：【只有開始數據節(jié)點指針沒有尾節(jié)點指針的循環(huán)雙鏈表】36、【單選題】在某線性表最常用的操作是在尾元素之后插入一個元素和刪除第一個元素。故采用_______存儲方式最節(jié)省時間。本題答案：【僅有尾指針的循環(huán)單鏈表】37、【單選題】兩個表長都為n、不帶表頭結點的單鏈表，結點類型都相同，頭指針分別為h1與h2，且前者是循環(huán)鏈表，后者是非循環(huán)鏈表，則_______。本題答案：【對于兩個鏈表來說，刪除尾節(jié)點的操作，其時間復雜度都是O(n)】38、【單選題】在長度為n的_______上，刪除第一個元素，其算法的時間復雜度為O(n)。本題答案：【只有表頭指針的不帶表頭節(jié)點的循環(huán)單鏈表】39、【單選題】下面關于線性表的敘述錯誤的是_______。本題答案：【線性表采用順序存儲便于插入和刪除操作的實現】40、【單選題】對于雙鏈表，在兩個節(jié)點之間插入一個新節(jié)點是，需要修改_______個指針域。本題答案：【4】41、【單選題】在單鏈表中，要刪除某一指定的節(jié)點，必須找到該節(jié)點的_______節(jié)點。本題答案：【前驅】42、【單選題】求一個單鏈表長度的算法的時間復雜度為_______。本題答案：【O(n)】43、【判斷題】線性表中每個元素都有一個前驅元素和一個后繼元素。本題答案：【錯誤】44、【判斷題】線性表中所有元素的排列順序必須從小到大或從大到小。本題答案：【錯誤】45、【判斷題】靜態(tài)鏈表既有順序存儲結構的優(yōu)點，又有動態(tài)鏈表的優(yōu)點，所以，利用它存取第i個元素的時間與元素個數n無關。本題答案：【錯誤】46、【判斷題】靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除方面類似，不需要做元素的移動。本題答案：【正確】47、【判斷題】線性表的順序存儲結構優(yōu)于鏈式存儲結構。本題答案：【錯誤】48、【判斷題】在循環(huán)單鏈表中，從表中任一節(jié)點出發(fā)都可以通過前后移動操作遍歷整個循環(huán)鏈表。本題答案：【錯誤】49、【判斷題】在單鏈表中，可以從頭節(jié)點開始查找任何一個節(jié)點。本題答案：【正確】50、【判斷題】在雙鏈表中，可以從任一節(jié)點開始沿著同一方向查找到任何其他節(jié)點。本題答案：【錯誤】第三章棧和隊列單元測試1、【單選題】元素A、B、C、D依次進棧后，棧頂元素是_______。本題答案：【D】2、【單選題】經過以下運算后，x的值是_______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x)本題答案：【a】3、【單選題】經過以下棧運算后，StackEmpty(s)的值是_______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)本題答案：【1】4、【單選題】已知一個棧的進棧序列是ABC，出棧序列為CBA，經過棧的操作是_______。本題答案：【push,push,push,pop,pop,pop】5、【單選題】若元素a、b、c、d、e、f依次進棧，允許進棧、退棧的操作交替進行，但不允許連續(xù)3次退棧工作，則不可能得到的出棧序列是_______。本題答案：【afedcb】6、【單選題】設一個棧的輸入序列為A、B、C、D，則借助一個棧所得的輸出序列不可能是_______。本題答案：【DABC】7、【單選題】一個棧的進棧序列是abcde，則棧的不可能的輸出序列是_______。本題答案：【dceab】8、【單選題】已知一個棧的進棧序列是1，2，3，…n，其輸出序列的第一個元素是i（1≤i≤n），則第j（1≤j≤n）個出棧元素是_______。本題答案：【不確定】9、【單選題】已知一個棧的進棧序列是1,2,3，…n，其輸出序列是p1,p2,…pn，若p1=n,則pi的值是_______。本題答案：【n-i+1】10、【單選題】設n個元素的進棧序列是p1,p2,…pn，其輸出序列是1,2,3，…n，若pn=1，則pi（1≤i≤n-1）的值是_______。本題答案：【n-i+1】11、【單選題】設n個元素的進棧序列是1,2,3，…n，其輸出序列是p1,p2,…pn，若p1=3，則p2的值是_______。本題答案：【不可能是1】12、【單選題】設n個元素的進棧序列是p1,p2,…pn，其輸出序列是1,2,3，…n，若p3=1，則p1的值是_______。本題答案：【不可能是2】13、【單選題】設n個元素的進棧序列是p1,p2,…pn，其輸出序列是1,2,3，…n，若p3=3，則p1的值是_______。本題答案：【可能是2】14、【單選題】設有5個元素的進棧序列是a，b，c，d，e，其輸出序列是c，e，d，b，a，則該棧的容量至少是_______。本題答案：【4】15、【單選題】在數據處理過程中常需要保存一些中間數據，如果后保存的數據先處理，則使用_______來保存這些數據。本題答案：【棧】16、【單選題】判定一個順序棧st為（元素個數最多為MaxSize）空的條件為_______。本題答案：【st.top==-1】17、【單選題】判定一個順序棧st為（元素個數最多為MaxSize）為棧滿的條件為_______。本題答案：【st.top==MaxSize-1】18、【單選題】表達式a*(b+c)-d的后綴表達式是_______。本題答案：【abc+*d-】19、【單選題】若一個棧用數組data[1..n]存儲，初始棧頂指針top為n+1，則以下元素x進入棧的正確操作是_______。本題答案：【top--;data[top]=x;】20、【單選題】若一個棧用數組data[1..n]存儲，初始棧頂指針top為n，則以下元素x進入棧的正確操作是_______。本題答案：【data[top]=x;top--;】21、【單選題】若一個棧用數組data[1..n]存儲，初始棧頂指針top為0，則以下元素x進入棧的正確操作是_______。本題答案：【top++;data[top]=x;】22、【單選題】若一個棧用數組data[1..n]存儲，初始棧頂指針top為1，則以下元素x進入棧的正確操作是_______。本題答案：【data[top]=x;top++;】23、【單選題】鏈棧與順序棧相比有一個明顯的優(yōu)點，即_______。本題答案：【通常不會出現棧滿的情況】24、【單選題】以下各鏈表均不帶有頭節(jié)點，其中最不合適用作鏈棧的鏈表是_______。本題答案：【只有表頭指針沒有表尾指針的循環(huán)單鏈表】25、【單選題】如果以鏈表作為棧的存儲結構，則退棧操作時_______。本題答案：【必須判斷鏈棧是否空】26、【單選題】向一個不帶頭節(jié)點的棧頂指針為lst的鏈棧中插入一個s所指向節(jié)點時，則執(zhí)行_______。本題答案：【s-next=lst;lst=s;】27、【單選題】從一個不帶頭節(jié)點的棧頂指針為lst的棧鏈中刪除一個節(jié)點時，用x保存被刪節(jié)點的值，則執(zhí)行_______。本題答案：【x=lst-data;lst=lst-next;】28、【單選題】棧和隊列的不同點是_______。本題答案：【棧只能在一端進行插入刪除操作，而隊列在不同端進行插入刪除操作】29、【單選題】經過下列運算后，隊頭的元素是_______。InitQueue(qu);Enqueue(qu,‘a’);EnQueue(qu,‘b’);EnQueue(qu,‘c’);DeQueue(qu);本題答案：【b】30、【單選題】若某循環(huán)隊列有隊首指針front和隊尾指針rear，在隊不滿時進隊操作僅會改變_______。本題答案：【rear】31、【單選題】循環(huán)隊列qu的隊滿條件（front隊首指針指向隊首元素的前一位置，rear隊尾指針指向隊尾元素）是_______。本題答案：【(qu.rear+1)%maxsize==qu.front】32、【單選題】設循環(huán)隊列中數組的下標是0~N-1，其隊頭、隊尾指針分別為f和r（f指向隊首元素的前一位置，r指向隊尾元素），則元素個數為_______。本題答案：【(r-f+N)%N】33、【單選題】最適合用做鏈隊列的不帶表頭節(jié)點的鏈表是_______。本題答案：【只帶尾節(jié)點指針的循環(huán)單鏈表】34、【單選題】假設用一個不帶表頭節(jié)點的單鏈表表示隊列，在進行刪除操作時，_______。本題答案：【頭、尾指針可能都要修改】35、【單選題】假設用一個不帶頭節(jié)點的單鏈表表示隊列，隊頭和隊尾指針分別為front和rear，則判斷隊空的條件是_______。本題答案：【front==NULL】36、【單選題】最不合適用做鏈隊的不帶頭節(jié)點的鏈表是_______。本題答案：【只帶隊首節(jié)點指針的非循環(huán)單鏈表】37、【單選題】假設用qu[0..M]實現循環(huán)隊列，f、r分別為隊首元素的前一個位置和隊尾位置。若用“(r+1)%(M+1)==f”作為隊滿的標志，則_______。本題答案：【可用“f==r”作為隊空的標志】38、【單選題】若用一個大小為6的數組來實現循環(huán)隊列，且當前rear和front的值分別是0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是_______。本題答案：【2和4】39、【判斷題】棧底元素是不能刪除的元素。本題答案：【錯誤】40、【判斷題】順序棧中元素值的大小是有序的。本題答案：【錯誤】41、【判斷題】n個元素依次進棧，它們的出棧順序和進棧順序一定正好相反。本題答案：【錯誤】42、【判斷題】棧頂元素和棧底有可能是同一元素。本題答案：【正確】43、【判斷題】若用s[0..m-1]表示順序棧的存儲空間，則對棧的進棧、出棧操作最多只能進行m次；本題答案：【錯誤】44、【判斷題】棧是一種對進棧、出棧操作總次數做了限制的線性表。本題答案：【錯誤】45、【判斷題】棧是一種對進棧、出棧操作的次序做了限制的線性表。本題答案：【錯誤】46、【判斷題】對順序棧進行進棧、出棧操作，不涉及元素的前、后移動問題。本題答案：【正確】47、【判斷題】空棧沒有棧頂指針。本題答案：【錯誤】48、【判斷題】棧和隊列都是限制存取端的。本題答案：【正確】49、【判斷題】隊列是一種對進隊、出隊操作的次序做了限制的線性表。本題答案：【錯誤】50、【判斷題】若用“隊首指針的值和隊尾指針的值相等”作為循環(huán)順序隊為空的標識，則在設置一個空隊列時，只需給隊首指針和隊尾指針賦同一個值，在順序表地址范圍內不管什么值都可以。本題答案：【正確】第五章數組與廣義表單元測試1、【單選題】以行序優(yōu)先順序存儲數組A[5][5]；假定A[0][0]的地址為1000,每個元素占4個字節(jié)，下標變量A[4][3]的地址是____。本題答案：【1092】2、【單選題】數組a[1．．6][1．．5]（無0行0列）以列序優(yōu)先順序存儲，第一個元素a[1][1]的地址為1000，每個元素占2個存儲單元，則a[3][4]的地址是____。本題答案：【1040】3、【單選題】設有一個5行4列的矩陣A，采用行序優(yōu)先存儲方式，A[0][0]為第一個元素，其存儲地址為1000，A[2][2]的地址為1040，則A[3][0]的地址為_________。本題答案：【1048】4、【單選題】設有一個10行10列的矩陣A，采用行序優(yōu)先存儲方式，存儲全部數據需要400個字節(jié)的空間。如果A[0][0]為第一個元素，其存儲地址為1000，則A[3][6]的地址為_________。本題答案：【1144】5、【單選題】設有一個10行10列的矩陣A，采用行序優(yōu)先存儲方式。如果A[0][0]為第一個元素，其存儲地址為1000，A[2][3]的存儲地址為1069，則存儲一個元素需要的單元數是_________。本題答案：【3】6、【單選題】不能夠對數據元素進行隨機訪問的物理結構是_________。本題答案：【三元組順序表】7、【單選題】對特殊矩陣采用壓縮存儲的目的主要是_________。本題答案：【減少不必要的存儲空間】8、【單選題】對n*n的對稱矩陣進行壓縮存儲，需要保存的數據元素的個數是_________。本題答案：【n(n+1)/2】9、【單選題】設10*10的對稱矩陣下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3]保存在SA[k]中，這里k等于_________。本題答案：【13】10、【單選題】對n行n列的三對角矩陣，需要保存的數據元素的個數是_________。本題答案：【3n-2】11、【單選題】設10*10三對角矩陣保存SA[1．．28]中，其中A[1][1]保存在SA[1]中，A[5][5]保存在SA[k]中，這里k等于_________。本題答案：【13】12、【單選題】某稀疏矩陣A采用三元組順序表作為存儲結構，對于矩陣元素的賦值運算Assign(A,e,i,j)，不可能_________。（在Assign(A,e,i,j)中，e是矩陣元素Ai,j的值，i和j分別為矩陣元素的行號和列號）。本題答案：【修改某個三元組的行號或列號】13、【單選題】對稀疏矩陣進行壓縮存儲方法一般有兩種，分別為________。本題答案：【三元組順序表和十字鏈表】14、【單選題】下列敘述中，不正確的是__________。本題答案：【除了插入與刪除操作外，數組的基本操作還有存取、修改、檢索和排序等】15、【單選題】某稀疏矩陣A采用十字鏈表作為存儲結構，對于矩陣元素的賦值運算Assign(A,e,i,j)，不可能_________。（在Assign(A,e,i,j)中，e是矩陣元素Ai,j的值，i和j分別為矩陣元素的行號和列號）本題答案：【修改稀疏矩陣的行列數】16、【單選題】使用三元組來保存稀疏矩陣中的非零元素，三元組不包括非零元素的__________。本題答案：【個數】17、【單選題】使用三元組順序表或十字鏈表作為稀疏矩陣中的物理結構，對元素的訪問形式只能是__________。本題答案：【順序訪問】18、【單選題】使用三元組順序表作為稀疏矩陣中的物理結構，要求對三元組按行序優(yōu)先的順序進行存放，原因是按行序優(yōu)先能__________。本題答案：【方便稀疏矩陣的運算】19、【單選題】表頭和表尾均為空義表的廣義表是__________。本題答案：【(())】20、【單選題】廣義表(a,(b,c),d)的表長是______。本題答案：【3】21、【單選題】廣義表((a,()),(b,(c)),(()))的深度是______。本題答案：【3】22、【單選題】廣義表((a,b),(c),(d))的表頭是______。本題答案：【(a,b)】23、【單選題】廣義表((a,b),(c),(d))的表尾是______。本題答案：【((c),(d))】24、【單選題】對廣義表G=((a,((),b)),(((),(c,d)),()))執(zhí)行tail(head(head(tail(G))))操作的結果是_________。本題答案：【((c,d))】25、【單選題】下列敘述中，不正確的是______。本題答案：【稀疏矩陣中大量值為0的元素分布有規(guī)律，因此可以采用三元組表方法存儲】26、【判斷題】在一維數組（向量）中，能很方便地通過增加數據元素使數組長度增加。本題答案：【錯誤】27、【判斷題】數組是一種復雜的數據結構，數據元素之間的關系既不是線性的，也不是樹型的。本題答案：【錯誤】28、【判斷題】數組是一個定長的線性表，所以不能有元素的增加與刪除操作。本題答案：【正確】29、【判斷題】數組的順序存儲結構中，按行序（或列序）優(yōu)先次序存放數組元素，是為了方便尋址公式的分析。本題答案：【正確】30、【判斷題】通過數組的順序存儲結構，按行序優(yōu)先次序保存了數組的全部數據元素，可以通過尋址公式對數組元素進行隨機訪問。本題答案：【正確】31、【判斷題】n維數組的存儲方案中，每一個數組元素都有n個方向的關系（約束）。本題答案：【正確】32、【判斷題】對對稱矩陣進行壓縮存儲，能提高存儲效率，其壓縮率可低至50%。（壓縮率為壓縮后的大小與壓縮前的大小之比）本題答案：【錯誤】33、【判斷題】對特殊矩陣進行壓縮存儲后，無法實現對其元素進行隨機訪問。本題答案：【錯誤】34、【判斷題】在特殊矩陣中，有很多值相同的元素并且有規(guī)律地分布，所以沒有必要重復存儲值相同的元素。本題答案：【正確】35、【判斷題】元素A[i][j]在對稱矩陣的下三角位置上的條件是ij。本題答案：【錯誤】36、【判斷題】元素A[i][j]在三對角矩陣的三對角位置上的條件是|i-j|≤1。本題答案：【正確】37、【判斷題】以三元組順序表存儲稀疏矩陣時，可以通過尋址公式對數據元素進行隨機訪問。本題答案：【錯誤】38、【判斷題】以三元組順序表存儲稀疏矩陣時，對元素A[i][j]賦值0，可能會在三元組順序表中引起三元組（i，j，A[i][j]）后面的三元組向前面移動。本題答案：【正確】39、【判斷題】以三元組順序表存儲稀疏矩陣時，對元素A[i][j]賦值一個非零值，只需要三元組順序表的最后添加新的三元組（i，j，A[i][j]）。本題答案：【錯誤】40、【判斷題】以十字鏈表存儲稀疏矩陣時，只能對數據元素進行順序訪問。本題答案：【正確】41、【判斷題】以十字鏈表存儲稀疏矩陣時，對元素A[i][j]賦值0，一定會在2個單鏈表中進行結點的刪除操作。本題答案：【錯誤】42、【判斷題】以十字鏈表存儲稀疏矩陣時，對元素A[i][j]賦值一個非零值，一定會在2個單鏈表中進行增加結點的操作。本題答案：【錯誤】43、【判斷題】當某稀疏矩陣經常進行元素的賦值運算時，十字鏈表比三元組表更適合作為其存儲結構。本題答案：【正確】44、【判斷題】一個廣義表的表頭不一定是一個廣義表。本題答案：【正確】45、【判斷題】一個非空廣義表的表尾總是一個廣義表。本題答案：【正確】46、【判斷題】廣義表的長度是指廣義表中括號嵌套的層數。本題答案：【錯誤】47、【判斷題】廣義表(a,(b,(c,d,((),()))))的深度為5。本題答案：【正確】48、【判斷題】廣義表(a,(b,(c,d,((),()))))的長度為6。本題答案：【錯誤】49、【判斷題】廣義表中的元素既可以是原子，也可以是廣義表。本題答案：【正確】50、【判斷題】通常廣義表的物理結構是鏈式的。本題答案：【正確】第六章樹單元測試1、【單選題】樹最適合用來表示。本題答案：【元素之間具有分支層次關系的數據】2、【單選題】在樹結構中，若結點A有三個兄弟，且B是A的雙親，則B的度是。本題答案：【4】3、【單選題】下列陳述中正確的是。本題答案：【二叉樹中每個結點最多只有兩棵子樹，并且有左右之分】4、【單選題】設深度為h的二叉樹中只有度為0和度為2的結點，則此類二叉樹中所包含結點數至少為。本題答案：【2h-1】5、【單選題】設深度為h的二叉樹中只有度為0和度為2的結點，則此類二叉樹中所包含結點數至多為。本題答案：【】6、【單選題】具有n(n0)個結點的完全二叉樹的深度為。本題答案：【?log2(n)?+1】7、【單選題】具有32個結點的完全二叉樹有個葉子結點。本題答案：【16】8、【單選題】一棵完全二叉樹的第6層上有23個葉子結點，則此二叉樹最多有結點。本題答案：【81】9、【單選題】具有3個結點的二叉樹有種。本題答案：【5】10、【單選題】若一棵二叉樹有9個度為2的結點，5個度為1的結點，則葉子結點的個數為。本題答案：【10】11、【單選題】一棵二叉樹有35個結點，則所有結點的度之和為。本題答案：【34】12、【單選題】二叉樹是非線性數據結構，所以。本題答案：【順序存儲結構和鏈式存儲結構都能存儲】13、【單選題】用順序存儲的方法將n個結點的完全二叉樹中所有結點按層逐個依從左至右的次序存放在一維數組R[1:n]中，若結點R[i]有左孩子，則左孩子是。本題答案：【R[2i]】14、【單選題】一棵深度為k且只有k個結點的二叉樹按照完全二叉樹順序存儲的方式存放于一個一維數組R[n]中，則n至少是才能確保正確存儲。本題答案：【】15、【單選題】以下存儲結構中，不是樹的存儲結構是。本題答案：【廣義表】16、【單選題】用二叉鏈表表示具有n個結點的二叉樹時，值為空的指針域的個數為。本題答案：【n+l】17、【單選題】二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定滿足的條件是。本題答案：【高度等于其結點數】18、【單選題】下列二叉樹，其后序遍歷序列與層次遍歷序列相同的非空二叉樹是。本題答案：【只有根結點的二叉樹】19、【單選題】對二叉樹的結點從1開始連續(xù)編號，要求每個結點的編號大于其左右子女的編號，同一結點的左、右子女中，其左子女的編號小于其右子女的編號，則可采用遍歷實現二叉樹的這種結點編號。本題答案：【后序】20、【單選題】在二叉樹中有兩個結點m和n，如果m是n的祖先，使用非遞歸過程更方便找到從m到n的路徑。本題答案：【后序遍歷】21、【單選題】不使用棧實現二叉樹后序遍歷的非遞歸算法，最佳方案是二叉樹的存儲結構采用表示。本題答案：【三叉鏈表】22、【單選題】在一個非空二叉樹的中序序列中，根結點的右邊是。本題答案：【只有右子樹上的所有結點】23、【單選題】設某棵二叉樹的中序遍歷序列為ABCD，先序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為。本題答案：【BADC】24、【單選題】先序遍歷序列為ABC，后序遍歷序列為CBA的二叉樹共有棵。本題答案：【4】25、【單選題】若二叉樹采用二叉鏈表存儲結構，要交換所有分支結點的左右子樹的位置，利用基于遍歷的遞歸算法最合適。本題答案：【后序】26、【單選題】一棵二叉樹的先序遍歷序列為EFHIGJK,中序遍歷序列為HFIEJKG,則該二叉樹根結點的右孩子為。本題答案：【G】27、【單選題】一棵二叉樹采用二叉鏈表存儲結構存儲，根指針為t，下列遞歸算法求其先序序列中第k（1≦k≦二叉樹中結點的個數）個結點的值，算法的畫線處應填的語句是。本題答案：【n++】28、【單選題】二叉樹采用二叉鏈表存儲結構存儲，根指針為t，下列遞歸算法求其葉子結點的個數,算法的畫線處應填的語句是。本題答案：【t-lchild==NULLt-rchild==NULL】29、【單選題】判斷線索二叉鏈表中*p結點有右孩子結點的條件是。本題答案：【p-rtag==0】30、【單選題】將下圖所示的二叉樹按中序線索化，結點c的左指針與結點h的右指針分別指向。本題答案：【a,g】31、【單選題】二叉樹線索化后，仍不能有效求解的問題是。本題答案：【后序線索二叉樹中求后序后繼】32、【單選題】基于中序線索化鏈表，其頭結點指針為head，對應的二叉樹為空的判斷條件是。本題答案：【head-lchild==headhead-rchild==head】33、【單選題】討論樹、森林和二叉樹的關系，目的是________。本題答案：【將樹、森林按二叉樹的存儲結構進行存儲，并利用二叉樹的算法解決樹與森林的有關問題】34、【單選題】設森林F有3棵樹，分別有9、8和7個結點，則F此排列次序轉換成二叉樹后根結點的右子樹上結點的個數是。本題答案：【15】35、【單選題】如果二叉樹T2是由一棵樹T1轉換而來的二叉樹，那么T1結點的先根遍歷序列對應T2的序列。本題答案：【先序遍歷】36、【單選題】給定一棵樹的二叉鏈表存儲結構，把這棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是。本題答案：【唯一的】37、【單選題】由樹轉換成的二叉樹里，一個結點N的左孩子是N在原樹里對應結點的。本題答案：【最左孩子結點】38、【單選題】用13個權值構造哈夫曼樹，則該哈夫曼樹共有個結點。本題答案：【25】39、【單選題】對n（n≧2）個權值不同的字符依哈夫曼算法構造哈夫曼樹，下面關于該哈夫曼樹的敘述中錯誤的是。本題答案：【該樹一定是一棵完全二叉樹】40、【單選題】設一組權值集合W=(2，4，5，7)，要求根據這些權值集合構造一棵哈夫曼樹，則這棵哈夫曼樹的帶權路徑長度為。本題答案：【35】41、【判斷題】樹中元素結點是多對多的關系。本題答案：【錯誤】42、【判斷題】樹與二叉樹是兩種不同的樹形結構。本題答案：【正確】43、【判斷題】一棵滿二叉樹中每棵子樹都是完全二叉樹。本題答案：【正確】44、【判斷題】完全二叉樹適合使用順序存儲結構本題答案：【正確】45、【判斷題】對于任意的二叉樹，如果其葉子結點數為n0，度為2的結點數為n2，則n2＝n0＋1。本題答案：【錯誤】46、【判斷題】對一棵樹進行先根遍歷與后根遍歷，其中葉子結點出現的相對次序是相同的。本題答案：【正確】47、【判斷題】由二叉樹的某種遍歷方式產生的結果是一個線性序列。本題答案：【正確】48、【判斷題】用二叉樹的先序序列和后序序列可以導出它的中序序列。本題答案：【錯誤】49、【判斷題】在某種遍歷的線索二叉鏈表中，進行這種遍歷時可以直接沿所有右指針一直搜索下去，從而訪問所有結點。本題答案：【錯誤】50、【判斷題】可以不用棧實現基于中序線索二叉鏈表對二叉樹進行中序遍歷。本題答案：【正確】51、【判斷題】將一棵含有兩個以上結點的樹轉換成二叉樹后，該二叉樹的根結點沒有左子樹。本題答案：【錯誤】52、【判斷題】樹有先根遍歷與中根遍歷兩種遍歷方法。本題答案：【錯誤】53、【判斷題】樹的孩子兄弟表示法是一種二叉鏈表表示法。本題答案：【正確】54、【判斷題】二叉樹的先序遍歷的遞歸算法的時間復雜度為線性級。本題答案：【正確】55、【判斷題】在哈夫曼樹中，權值較大的葉子結點一般離根結點較遠。本題答案：【錯誤】56、【判斷題】在哈夫曼編碼中，當兩個不同字符出現的頻率相同時，其編碼也相同。本題答案：【錯誤】第七章圖單元測試1、【單選題】設有5個結點的無向圖，該圖至少應有_________條邊才能確保是一個連通圖。本題答案：【7】2、【單選題】設圖G=(V,VR)，其中:V={A,B,C,D,G}，VR={(A,C),(A,D),(B,C),(B,D),(G,C),(B,G)}，則對應的圖形為_________。本題答案：【】3、【單選題】設某有向圖中有n個頂點，則該有向圖對應的鄰接表中有_________個表頭結點。本題答案：【n】4、【單選題】在一個無向圖中所有頂點的度數之和等于所有邊數的_________倍。本題答案：【2】5、【單選題】一個無向連通圖的生成樹是該連通圖的_____。本題答案：【極小連通子圖】6、【單選題】設某無向圖中有n個頂點，則該無向圖鄰接矩陣的大小是_________。本題答案：【】7、【單選題】設有n個頂點e條邊的無向圖，采用鄰接矩陣作為物理結構，則刪除與某頂點Vi關聯(lián)的所有邊算法的時間復雜度為_________。本題答案：【O(n）】8、【單選題】設有n個頂點e條弧的有向圖，采用鄰接表作為物理結構，則求某頂點Vi度的算法的時間復雜度為_________。本題答案：【O(n+e）】9、【單選題】設無向圖G=(V,E)和G'=(V',E')，如果G'是G的生成樹，則下列說法中錯誤的是_____。本題答案：【G'是G的連通分量】10、【單選題】設G是一個非連通的無向圖，共有10條邊，則該圖至少有_____個頂點。本題答案：【6】11、【單選題】n個頂點的有向圖為強連通圖時，至少含有________。本題答案：【n條弧】12、【單選題】如果從無向圖的一個頂點出發(fā)，進行一次深度優(yōu)先搜索能訪問所有頂點，則該無向圖是一個________。本題答案：【連通圖】13、【單選題】如圖所示的有向圖，共有________個強連通分量。本題答案：【2】14、【單選題】在下圖中，從頂點A出發(fā)進行深度優(yōu)先遍歷可得到的序列是_________。本題答案：【ABDCG】15、【單選題】對圖進行深度優(yōu)先搜索遍歷，需要借助的數據結構為________。本題答案：【?！?6、【單選題】對圖進行廣度優(yōu)先搜索遍歷，需要借助的數據結構為________。本題答案：【隊列】17、【單選題】最小生成樹是指________。本題答案：【連通網的所有生成樹中權值之和最小的生成樹】18、【單選題】在下圖中，從頂點A出發(fā)進行廣度優(yōu)先遍歷可得到的序列是_________。本題答案：【ADCBG】19、【單選題】對如圖所示的無向連通網，從頂點A出發(fā)，使用Prim算法得到的最小生成樹是________。本題答案：【】20、【單選題】可借助于_________判別有向圖中是否存在回路。本題答案：【拓撲排序算法】21、【單選題】如圖所示的DAG圖，其拓撲排序序列為_________。本題答案：【ADBGC】22、【單選題】下列關于工程計劃的AOE網的敘述中，不正確的是_________。本題答案：【任何一個關鍵活動的提前完成，整個工程的完成時間都會提前】23、【單選題】使用迪杰斯特拉最短路徑算法，求一個源點到其它各頂點的最短路徑，該算法的時間復雜度為________。本題答案：【O()】24、【單選題】使用弗洛伊德算法，求任意2個頂點的最短路徑，該算法的時間復雜度為________。本題答案：【】25、【單選題】某無向圖的鄰接矩陣如下所示，可以得出，該圖共有__________個頂點。本題答案：【3】26、【判斷題】如果n（n2）個頂點的有向圖有二個強連通分量，則至少有n-1條弧。本題答案：【正確】27、【判斷題】n個頂點的無向圖，至少需要n條邊才可能是連通圖。本題答案：【錯誤】28、【判斷題】連通分量是指無向圖的極小連通子圖。本題答案：【錯誤】29、【判斷題】無向圖的鄰接矩陣必然是對稱矩陣。本題答案：【正確】30、【判斷題】有n（n1）個頂點，-2n+2條弧的有向圖不一定是強連通圖。本題答案：【錯誤】31、【判斷題】圖的鄰接矩陣大小，不但與圖的頂點數有關，而且與圖的邊數也有關。本題答案：【錯誤】32、【判斷題】使用有向圖的十字鏈表，能非常方便地計算出任意一個頂點的出度和入度。本題答案：【正確】33、【判斷題】一個有n個頂點e條邊的無向圖的鄰接表中，有2e個表結點。本題答案：【正確】34、【判斷題】一個有n個頂點e條邊的無向圖的鄰接多重表中，有2e個表結點。本題答案：【錯誤】35、【判斷題】一個有n個頂點e條弧的有向圖的逆鄰接表中，有2e個表結點。本題答案：【錯誤】36、【判斷題】一個有向圖的鄰接表和逆鄰接表中的表結點個數一定相等。本題答案：【正確】37、【判斷題】有向圖有n個頂點e條弧，采用鄰接表存儲，則計算某頂點度的算法需要訪問n+e個單鏈表的表結點。本題答案：【錯誤】38、【判斷題】鄰接表的空間復雜度為，與邊（或弧）的條數無關。本題答案：【錯誤】39、【判斷題】對于一個連通圖，通過一次深度優(yōu)先遍歷，能訪問到所有頂點。本題答案：【正確】40、【判斷題】從無向圖的任一頂點出發(fā)，進行一次廣度優(yōu)先搜素，都能訪問到圖的所有頂點。本題答案：【錯誤】41、【判斷題】對于一個連通圖，有唯一的一棵深度優(yōu)先遍歷生成樹。本題答案：【錯誤】42、【判斷題】當無向連通網中的邊較少時，采用prim算法求其最小生成樹效率較高。本題答案：【錯誤】43、【判斷題】Kruskal算法適合求解邊稠密圖的最小生成樹。本題答案：【錯誤】44、【判斷題】某無向連通網只有唯一的一棵最小生成樹，則該無向連通網個邊上的權值互不相同。本題答案：【錯誤】45、【判斷題】可以借助于拓撲排序算法來判斷一個有向圖是否有回路。本題答案：【正確】46、【判斷題】在某AOV網中，頂點Vi到頂點Vj有路徑，則該AOV網的任何拓撲排序序列中，Vi一定排在Vj的前面。本題答案：【正確】47、【判斷題】需要借助于深度優(yōu)先遍歷算法來求得AOE網的關鍵路徑。本題答案：【錯誤】48、【判斷題】在某AOE網中，ak是從頂點Vi到頂點Vj的活動，則活動ak的最早開始時間等于Vi的最早發(fā)生時間。本題答案：【正確】49、【判斷題】使用迪杰斯特拉算法，能求出有向網中任意2個頂點的最短路徑。本題答案：【正確】50、【判斷題】在求出有向網中任意2個頂點的最短路徑時，FLOYED算法的時間效率優(yōu)于使用迪杰斯特拉算法。本題答案：【錯誤】第九章查找單元測試1、【單選題】對于查找表(13,27,38,49,50,65,76,97)采用順序查找，在等概率情況下查找成功的平均查找長度是（）。本題答案：【4.5】2、【單選題】在關鍵字序列（10,20,30,40,50）中采用折半查找20，依次與（）關鍵字進行了比較。本題答案：【30,10,20】3、【單選題】在關鍵字序列（8,12,20,25,33）中，采用二分查找25，關鍵字之間比較需要（）次。本題答案：【2】4、【單選題】對于長度為11的有序表，按折半查找，在等概率情況下查找成功時，其平均查找長度是（）。本題答案：【3】5、【單選題】對于長度為11的有序表，按折半查找，在查找失敗時，待查找值域表中關鍵字比較的次數是（）。本題答案：【3次或4次】6、【單選題】對于長度為n的有序表，按折半查找，在等概率情況下查找成功平均時間復雜度是（）。本題答案：【O(㏒n)】7、【單選題】索引順序查找也叫分塊查找，其查找過程分為是（）個步驟。本題答案：【2】8、【單選題】對于長度為n的關鍵字序列創(chuàng)建一顆二叉排序樹，該樹可能的最大高度是（）。本題答案：【n】9、【單選題】對于關鍵字序列(30,25,40,35,45)，按序列次序創(chuàng)建一顆二叉排序樹，在等概率情況下查找成功時，其平均查找長度是（）。本題答案：【11/5】10、【單選題】影響散列查找時間效率的主要因素（）。本題答案：【與散列表長和散列表中實際元素個數均相關】11、【單選題】一組關鍵字序列為(27，17，9，19，16，43，53，8，63)，用哈希函數H(key)=keyMOD8和鏈地址法處理沖突，查找關鍵字43，與散列表中關鍵字進行了（）次比較。本題答案：【3】12、【單選題】設哈希表下標為0~15，哈希函數為H(key)=keyMOD13，其中key為關鍵字，MOD為取余數運算，處理沖突方法為線性探查法，對于關鍵字序列為(22，18，38，39，48，35，9，64，29)，建立哈希表后，關鍵字9的在哈希表的位置是（）。本題答案：【13】13、【單選題】對于關鍵字序列(14,26,38,54,91)，按序列次序創(chuàng)建一顆平衡二叉排序樹，在等概率情況下查找成功時，其平均查找長度是（）。本題答案：【11/5】14、【單選題】對于關鍵字序列(63,72,88,68,66,38,43)，在按序列次序創(chuàng)建一顆平衡二叉排序樹上，查找71時依次與（）關鍵字進行了比較。本題答案：【66,72,68】15、【單選題】對包含n個元素的散列表進行檢索，平均查找長度為（）。本題答案：【不直接依賴于n】16、【單選題】折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90)，若查找元素75，與表中元素進行了（）次比較。本題答案：【4】17、【單選題】折半查找一個長度為56的有序表,若查找不成功,最少需要比較（）次關鍵字。本題答案：【5】18、【單選題】假設哈希函數h(k)=kmod29，那么（）為7的同義詞。本題答案：【36】19、【單選題】在下列查找算法中，（）屬于動態(tài)表上的查找法。本題答案：【哈希查找】20、【單選題】在二叉排序樹查找中，創(chuàng)建平衡二叉排序的目的是提高（）。本題答案：【查找時間效率】21、【單選題】高度為3的平衡二叉排序樹的形態(tài)共有（）種。本題答案：【15】22、【單選題】在下列查找算法中，（）算法要求關鍵字序列是有序的。本題答案：【折半查找】23、【單選題】假設查找表長為n，對于分塊查找，如過采用順序查找確定待查值可能所在的塊，那么每塊的關鍵字個數為（）時，分塊查找的平均查找長度可以達到最佳。本題答案：【】24、【單選題】對于表長為n的查找表，如果采用順序查找，查找失敗時的平均查找長度是（）。本題答案：【n】25、【單選題】若根據查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為（）。本題答案：【(d+1)%m】26、【判斷題】對長度為n的順序表做查找運算，在等概率條件下，查找成功的ASL為n/2。本題答案：【錯誤】27、【判斷題】如果含有n個記錄的HASH表中沒有同義詞，則查找成功的ASL為1。本題答案：【正確】28、【判斷題】高度為4的平衡二叉樹至少有4個結點。本題答案：【錯誤】29、【判斷題】分塊查找要求關鍵字序列一定是有序的。本題答案：【錯誤】30、【判斷題】對于二叉排序樹，中序遍歷的關鍵字序列一定是有序。本題答案：【正確】31、【判斷題】對于任何應用情況，如果采用哈希查找法，那么就無法避免沖突情況的發(fā)生。本題答案：【錯誤】32、【判斷題】分塊查找需要額外的輔助存儲空間。本題答案：【正確】33、【判斷題】含有n個關鍵字的二叉排序樹，其高度可以達到n。本題答案：【正確】34、【判斷題】如果一顆二叉樹的左右子樹高度差的絕對值不大于2，則該二叉樹是一顆平衡二叉樹。本題答案：【錯誤】35、【判斷題】如果關鍵字序列是有序的，則可以提高順序查找的效率。本題答案：【錯誤】36、【判斷題】在有序的單鏈表上不適合折半查找。本題答案：【正確】37、【判斷題】對于相同的關鍵字集，如果不同的初始序列，那么創(chuàng)建的二叉排序樹也不相同。本題答案：【錯誤】38、【判斷題】假定有k個關鍵字互為同義詞，若線性再散列處理沖突，查找這些同義詞其中的任意一個關鍵字，那么比較次數不會超過k次。本題答案：【錯誤】39、【判斷題】二分查找過程所對應的判定樹是一棵平衡的二叉排序樹。本題答案：【正確】40、【判斷題】對于相同的關鍵字集，如果不同的初始序列，那么創(chuàng)建的平衡二叉排序樹是相同的。本題答案：【錯誤】41、【判斷題】在二叉排序樹中插入一個新結點，總是作為葉子結點插入。本題答案：【正確】42、【判斷題】當采用分快查找時，數據的組織方式為數據分成若干塊，每塊（除最后一塊外）中數據個數需相同。本題答案：【錯誤】43、【判斷題】二叉排序樹查找法能適應查找表中數據的動態(tài)變化的要求。本題答案：【正確】44、【判斷題】用線性探測法解決突出時，同義詞在散列表中是相鄰的。本題答案：【錯誤】45、【判斷題】一顆完全二叉樹也是一顆平衡二叉樹。本題答案：【正確】46、【判斷題】對于散列表進行檢索，其平均查找長度取決于表中填入的記錄數與哈希表長之比。本題答案：【正確】47、【判斷題】含有12個結點的平衡二叉樹，其高度至多為5。本題答案：【正確】48、【判斷題】在HASH表中進行查找運算，根據HASH函數就能確定要查找的元素位置，不需要進行關鍵字的比較。本題答案：【錯誤】49、【判斷題】如果二叉樹的中序遍歷序列是遞增有序的，那么該二叉樹一定也是二叉排序樹。本題答案：【正確】50、【判斷題】基于“比較”運算的查找算法，其時間復雜度的下界為O(㏒n)。本題答案：【正確】第十章內部排序單元測試1、【單選題】對關鍵字序列（21,19,37,5,2），經直接插入排序法由小到大排序，第一趟后所得結果為（）。本題答案：【(19，21，37，5，2)】2、【單選題】對關鍵字序列（21,19,37,5,2），經冒泡排序法由小到大排序，第一趟后所得結果為（）。本題答案：【(19，21，5，2，37)】3、【單選題】對關鍵字序列（149,138,165,197,176,113,127），采用基數排序的第一趟之后所得結果為（）。本題答案：【(113，165，176，197，127，138，149)】4、【單選題】下列各項鍵值（）序列不是堆的。本題答案：【(5，23，68，16，94)】5、【單選題】假設一組待排序的關鍵字序列為（24,62,36,19），要求從小到大進行排序，（）是歸并排序的過程。本題答案：【(24，62，19，36)(19，24，36，62)】6、【單選題】在第一趟排序之后，不能確保將數據表中某一個元素放在其最終位置上的排序算法是（）。本題答案：【歸并排序】7、【單選題】對于下列排序，（）的時間效率與關鍵字初始序列有直接關系。本題答案：【直接插入排序】8、【單選題】對于下列排序，（）的最壞時間復雜度是O(n㏒n)。本題答案：【歸并排序】9、【單選題】假設兩個有序表長度分別為n和m，將其歸并成一個有序表最少需要（）次關鍵字之間的比較。本題答案：【min{n,m}】10、【單選題】對于下列排序，（）需要額外輔助存儲空間達到O(n)。本題答案：【歸并排序】11、【單選題】.對于關鍵字序列(49,38,65,97,76,13,27,49)，完成創(chuàng)建的大根堆是（）。本題答案：【(97,76,65,49,49,13,27,38)】12、【單選題】對關鍵字序列（30，26，18，16，5，66），進行2遍（）排序后得到序列（5，16，18，26，30，66）。本題答案：【選擇】13、【單選題】在下列排序算法中，（）排序算法可能出現如下情況：在最后一趟排序之前，所有元素均不在其最終的位置上。本題答案：【插入】14、【單選題】在下列排序方法中，（）排序方法的平均時間復雜度不是O（）.本題答案：【快速】15、【單選題】假設兩個有序表長度分別為n和m，將其歸并成一個有序表最多需要（）次關鍵字之間的比較。本題答案：【n+m-1】16、【單選題】下列排序算法中，（）排序算法是穩(wěn)定的。本題答案：【冒泡】17、【單選題】假設待排序的表長為n，那么下列排序算法中，（）排序算法需要O(n)的輔助空間。本題答案：【歸并】18、【單選題】假設待排序的表長為n，那么快速排序算法需要（）的輔助空間。本題答案：【O(㏒n)】19、【單選題】在下列排序算法中，（）排序算法可以避免在排序過程中移動數據元素。本題答案：【表插入】20、【單選題】假設待排序的表長為n，那么創(chuàng)建堆需要時間復雜度為（）。本題答案：【O(n)】21、【單選題】在下列排序算法中，在待排序序列為有序的情況下，（）的時間復雜度是O()，其中n為待排序序列的數據元素個數。本題答案：【快速排序】22、【單選題】下列四種排序中，（）的輔助空間復雜度是最高的。本題答案：【快速排序】23、【單選題】設哈希表為HT[0..16]，哈希函數H(key)=key%13，采用線性探測開放地址法處理沖突，且HT中已有關鍵字為11、28、47和18這4個數據元素，現插入關鍵字為24的數據元素，其實際存儲的地址是（）。本題答案：【12】24、【單選題】對順序表中的n個記錄進行直接插入排序，在最好情況下需要比較（）次關鍵字。本題答案：【n-1】25、【單選題】排序算法的穩(wěn)定性是指（）。本題答案：【經過排序后，能使原來關鍵字值相同的數據保持原有順序中的相對位置不變】26、【判斷題】簡單插入排序算法是不穩(wěn)定的。本題答案：【錯誤】27、【判斷題】待排序記錄關鍵字出現有序的初始排列時，快速排序的時間復雜性達到最壞情況。本題答案：【正確】28、【判斷題】相對于簡單插入排序而言，半插入排序減少了關鍵字比較和移動的次數。本題答案：【錯誤】29、【判斷題】對順序表中的n個記錄進行直接插入排序，在初始關鍵字序列為逆序的情況下，需要關鍵字比較的次數最少。本題答案：【錯誤】30、【判斷題】對順序表中的n個記錄進行簡單選擇排序，至多需要關鍵字交換n-1次。本題答案：【正確】31、【判斷題】堆排序是一種選擇排序。本題答案：【正確】32、【判斷題】對長度為8的表，作2路歸并排序，關鍵字之間最多需要21次比較。本題答案：【錯誤】33、【判斷題】快速排序方法的每一趟都能將一個元素把它放到最終的位置上。本題答案：【正確】34、【判斷題】因為堆排序的算法時間復雜度為O(n㏒n)，冒泡排序的算法復雜度為O(n2)，所以堆排序一定比冒泡排序的速度快。本題答案：【錯誤】35、【判斷題】對有n個記錄的表作直接插入排序，在最壞的情況下，需比較關鍵字（不含與哨兵的比較）的次數為n(n-1)/2。本題答案：【正確】36、【判斷題】在快速排序、堆排序和歸并排序中，快速排序需要的輔助空間最多。本題答案：【錯誤】37、【判斷題】如果冒泡排序的某趟過程中沒有出現數據交換情況，那么說明關鍵字序列已經有序。本題答案：【正確】38、【判斷題】排序的穩(wěn)定性是指排序算法中的比較次數保持不變，且算法能夠終止。本題答案：【錯誤】39、【判斷題】在初始數據表已經有序時，快速排序算法的時間復雜度為O(n㏒n)。本題答案：【錯誤】40、【判斷題】如果關鍵字序列是堆，則關鍵字序列對應的二叉樹是一棵二叉排序樹。本題答案：【錯誤】41、【判斷題】在用堆排序算法排序時，如果要進行增序排序，則需要采用“大根堆”。本題答案：【正確】42、【判斷題】在任何情況下，歸并排序都比簡單插入排序快。本題答案：【錯誤】43、【判斷題】排序要求數據一定要以順序方式存儲。本題答案：【錯誤】44、【判斷題】直接選擇排序的比較次數與關鍵字序列的初始狀態(tài)無關。本題答案：【正確】45、【判斷題】因為接插入排序是穩(wěn)定的，而Shell排序是調用若干趟直接插入排序，所以也是穩(wěn)定的。本題答案：【錯誤】46、【判斷題】以中序方式遍歷一個堆序列對應的二叉樹，則得到一個有序序列。本題答案：【錯誤】47、【判斷題】二路歸并排序的核心操作是把兩個有序序列合并為一個有序序列。本題答案：【正確】48、【判斷題】如果關鍵字序列采用單鏈表存儲，那么基數排序過程可以避免大量數據移動。本題答案：【正確】49、【判斷題】基數排序是一種基于最高位優(yōu)先(MSD)的多關鍵字排序法。本題答案：【錯誤】50、【判斷題】基于“比較”運算的排序算法，其時間復雜度的下界為O(n㏒n)。本題答案：【正確】數據結構綜合測試1、【單選題】下列術語中描述數據邏輯結構的名稱是_______。本題答案：【廣義表】2、【單選題】下列術語中與數據元素不是同一個層面的名稱是_______。本題答案：【抽象數據類型中的數據對象】3、【單選題】下面程序的時間復雜度為_______。i=0;j=1;while（i+j=n）{if(ij)i++；elsej++；}本題答案：【】4、【單選題】下列陳述中正確的是_______。本題答案：【非線性關系一般可以用順序結構與鏈式結構表示】5、【單選題】線性表L采用順序結構存儲，每個元素占用5個存儲單元，首元素a1的存儲地址是2000，則a20的后繼元素的起始存儲地址是_______。本題答案：【2100】6、【單選題】表長127的線性表采用順序結構存儲，刪除其中一個元素，平均要移動_____個元素。本題答案：【63】7、【單選題】只設尾指針tail的帶頭結點的非空循環(huán)單鏈表,指向首元素結點的指針p滿足的條件是_______。本題答案：【p==tail-next-next】8、【單選題】在一個帶頭結點且頭指針為head的非空雙向循環(huán)雙鏈表中，刪除尾結點的操作是_______。本題答案：【p=head-prior；p-prior-next=head；head-prior=p-prior；free(p)；】9、【單選題】設棧S和隊列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過棧S，一個元素出棧后即入隊列Q，若6個元素出隊列的順序是a3，a5，a4，a6，a2，a1，則棧S至少應該容納_______個元素。本題答案：【4】10、【單選題】下列表述正確的是_______。本題答案：【鏈式棧的入棧一般不必判斷棧滿】11、【單選題】下列表述錯誤的是_______。本題答案：【圖的深度優(yōu)先遍歷使用棧只保存未被訪問的頂點】12、【單選題】設循環(huán)隊列的容量為40（序號從0到39），隊列中始終少用一個單元，現經過一系列的入隊和出隊運算后，有①front=11，rear=19;②front=19，rear=11；在這兩種情況下，循環(huán)隊列中分別有_______個元素。本題答案：【8；32】13、【單選題】下列敘述中，不正確的是__________。本題答案：【數組只能用順序結構存儲】14、【單選題】設有一個二維數組A[m][n]，采用行序優(yōu)先存儲方式，假設A[0][0]存放位置在210，A[2][2]存放位置在242，每個元素占1個單元，問A[3][3]存放的位置是_______。本題答案：【258】15、【單選題】給定如下稀疏矩陣，采用三元組順序表進行壓縮存儲（數組0號單元存放矩陣