MOOC數據結構-西北大學中國大學慕課答案數據結構的基礎概念隨堂測驗1、問題：一個抽象類型包括數據對象、和一組處理數據的操作。選項：A、數據對象中各元素間的結構關系B、數據元素集C、接口D、數據對象集正確答案:【數據對象中各元素間的結構關系】2、填空題：抽象數據類型具有、信息隱蔽的特點。正確答案:【數據抽象】第2講數據結構的內容隨堂測驗1、問題：線性結構只能用順序結構來存放，非線性結構只能用非順序結構來存放。（）選項：A、正確B、錯誤正確答案:【錯誤】2、填空題：1、數據結構的邏輯結構分為集合、線性、層次和四種。正確答案:【網狀】3、填空題：2、數據結構的存儲結構分為和非順序兩種。正確答案:【順序】4、填空題：3、在線性結構、樹形結構和圖結構中，數據元素之間分別存在著一對一、一對多和聯系。正確答案:【多對多】第3講數據結構與C語言表示隨堂測驗1、問題：當需要用一個形式參數直接改變對應實參的值時，該形式參數應說明為。選項：A、與實參同類型指針參數B、不需要參數C、與實參同類型的參數D、全局變量正確答案:【與實參同類型指針參數】第4講算法性能評價隨堂測驗1、問題：1、執行下面的程序段的時間復雜度為。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;選項：A、O()B、O()C、O(m*n)D、O(m+n)正確答案:【O(m*n)】2、問題：2、執行下面程序段時，語句S的執行次數為。for(inti=0;i=n;i++)for(intj=0;ji;j++)S;選項：A、B、C、n(n+1)D、正確答案:【】第5講算法與算法描述隨堂測驗1、問題：算法設計的要求是：正確性、可讀性、和高效率和低存儲。選項：A、確定性B、健壯性C、可行性D、有限性正確答案:【健壯性】2、問題：算法具有有限性、確定性、、輸入、輸出五大特性。選項：A、可行性B、可讀性C、健壯性D、正確性正確答案:【可行性】第一章單元測試1、問題：下面程序段的時間復雜度為（）。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;選項：A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)正確答案:【O(m*n)】2、問題：執行下面程序段時，語句S的執行次數為（）。for(inti=0;i=n;i++)for(intj=0;j=i;j++)S;選項：A、n*nB、n*n/2C、(n+1)*(n+2)/2D、n(n+1)/2正確答案:【(n+1)*(n+2)/2】3、問題：評價一個算法性能好壞的最重要標準是（）。選項：A、算法的魯棒性B、算法的可讀性C、算法的時間復雜度和空間復雜度D、算法的正確性正確答案:【算法的時間復雜度和空間復雜度】4、問題：算法的時間復雜度與（）有關。選項：A、問題規模B、計算機硬件性能C、編譯程序質量D、程序設計語言正確答案:【問題規模】5、問題：算法分析的主要任務是分析（）。選項：A、算法是否具有較好的可讀性B、算法中是否存在語法錯誤C、算法的功能是否符合要求D、算法的執行時間與所需空間與問題規模的關系正確答案:【算法的執行時間與所需空間與問題規模的關系】6、問題：算法分析的目的是()。選項：A、找出數據結構的合理性B、研究算法中輸入和輸出的關系C、分析算法的時空效率以求改進D、分析算法的可讀性正確答案:【分析算法的時空效率以求改進】7、問題：數據的最小單位是（）。選項：A、數據項B、數據類型C、數據元素D、數據變量正確答案:【數據項】8、問題：某算法的時間復雜度是O（n*n）,表明該算法的（）。選項：A、問題規模是n*nB、問題規模與n*n正比C、執行時間與n*n正比D、執行時間等于n*n正確答案:【執行時間與n*n正比】9、問題：如下程序段:for(i=1;i=n-1;i++)for(j=i+1;j=n;j++)x=x+1;其中語句x=x+1執行的語句頻度為（）。選項：A、n*nB、n*(n-1)/2C、n*(n+1)/2D、n*(n-1)正確答案:【n*(n-1)/2】10、問題：以下算法的時間復雜度為（）。if(n=0){for(inti=0;in;i++)for(intj=0;jn;j++)printf(輸入數據大于等于零\n);}else{for(intj=0;jn;j++)printf(輸入數據小于零\n);}選項：A、O(1)B、O(n*n+n)C、O(n)D、O(n*n)正確答案:【O(n*n)】11、問題：在數組A[0..n-1]中查找給定值K的算法大致如下：i=n-1;while(i=0(A[i]!=k))i--;returni;該算法的時間復雜度為（）。選項：A、O(n-i+1)B、O(n-i)C、O(n)D、無法確定正確答案:【O(n)】12、問題：下面算法的時間復雜度為（）。x=100;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;選項：A、O(n)B、O(100)C、O(1)D、O(n*n)正確答案:【O(1)】13、問題：假設sqrt(n)函數中涉及的算法時間復雜度為O(1)，那么下面的算法是判斷n是否為素數，其時間復雜度為（）。voidprime(intn){for(i=2;isqrt(n)(n%i)!=0;i++);if(isqrt(n))printf(%disaprimenumber,n);elseprintf(%disnotaprimenumber,n);}選項：A、O(n)B、O(1)C、O(sqrt(n))sqrt表示對n取根方D、O(n-i)正確答案:【O(sqrt(n))sqrt表示對n取根方】14、問題：某算法中，執行頻率最高的語句的執行次數為則該算法的時間復雜度應該是（）。選項：A、T(n)=O(n*n*n)B、T(n)=O(n*n)C、T(n)=O((n*n*n+n*n+n)/n)D、T(n)=O(n*n+n)正確答案:【T(n)=O(n*n)】15、問題：數據結構中，數據處理的最小單位是（）。選項：A、數據B、數據對象C、數據元素D、數據項正確答案:【數據元素】16、問題：以下屬于數據元素間基本邏輯結構的是（）。選項：A、集合B、線性C、樹D、圖正確答案:【集合#線性#樹#圖】17、問題：以下屬于算法特性的是（）。選項：A、0個或多個輸入；至少1個輸出B、正確性C、確定性D、可行性和有限性正確答案:【0個或多個輸入；至少1個輸出#確定性#可行性和有限性】18、問題：算法設計的要求包括（）。選項：A、正確性B、可讀性C、健壯性D、高效率和低存儲正確答案:【正確性#可讀性#健壯性#高效率和低存儲】19、問題：數據元素在計算機內存中的存儲映像包括（）。選項：A、順序存儲B、非順序存儲C、圖結構D、樹結構正確答案:【順序存儲#非順序存儲】20、問題：抽象數據類型包括了（）。選項：A、一個數據對象B、元素的存儲結構C、元素間的關系D、一組操作正確答案:【一個數據對象#元素間的關系#一組操作】21、問題：具有線性結構的元素只能用順序存儲，具有非線性結構的元素只能非順序存儲。選項：A、正確B、錯誤正確答案:【錯誤】22、問題：算法就是程序。選項：A、正確B、錯誤正確答案:【錯誤】23、問題：算法的優劣與算法描述的語言無關。選項：A、正確B、錯誤正確答案:【正確】24、問題：算法的可行性是指每一條指令具有明確含義。選項：A、正確B、錯誤正確答案:【錯誤】25、問題：健壯的算法不會因為非法輸入數據而出現莫名其妙的執行結果。選項：A、正確B、錯誤正確答案:【正確】26、問題：算法設計的要求就是要設計高效率和低存儲的算法。選項：A、正確B、錯誤正確答案:【錯誤】27、問題：數據類型就是變量。選項：A、正確B、錯誤正確答案:【錯誤】28、問題：數據元素的存儲結構分為順序存儲和非順序存儲。選項：A、正確B、錯誤正確答案:【正確】29、問題：數據元素的順序存儲結構優于非順序存儲。選項：A、正確B、錯誤正確答案:【錯誤】30、問題：元素間的邏輯關系可分為線性和非線性關系兩種。選項：A、正確B、錯誤正確答案:【錯誤】第1講線性表的概念隨堂測驗1、問題：線性表是具有n個（）的有限序列（n0）選項：A、數據對象B、數據元素C、字符D、數據項正確答案:【數據元素】2、問題：線性表是一個（）。選項：A、有限序列，可以為空B、有限序列，不可以為空C、無限序列，可以為空D、無限序列，可以為空正確答案:【有限序列，可以為空】3、問題：線性表的特點是每個元素都有一個前驅和一個后繼。（）選項：A、正確B、錯誤正確答案:【錯誤】第2講線性表的順序存儲隨堂測驗1、問題：若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（）(1=i=n+1)。選項：A、O(1)B、O(n)C、O(n*n)D、O（）正確答案:【O(n)】2、問題：若長度為n的線性表采用順序存儲結構，刪除第i個位置的元素，需要移動的元素個數為（）。選項：A、iB、n-iC、n-i+1D、n-i-1正確答案:【n-i】第3講隨堂測驗1、問題：對一個長度為n的順序表，假設在任何位置上插入一個元素的概率是相等的，那么插入一個元素時要移動表中的（）個元素。選項：A、nB、n+1C、D、正確答案:【】2、問題：線性表的順序存儲是指將表中元素按照從大到小或從小到大存儲。選項：A、正確B、錯誤正確答案:【錯誤】第4講線性表的鏈式存儲隨堂測驗1、問題：通過表達式可以獲取帶頭結點的單鏈表L中首元素結點的數據值。選項：A、L-nextB、(L-next)-dataC、L-dataD、L-next正確答案:【(L-next)-data】2、問題：單鏈表中必須設有頭結點。（）選項：A、正確B、錯誤正確答案:【錯誤】第5講單鏈表的基本運算隨堂測驗1、問題：下列選項中，項是鏈表不具有的特點。選項：A、插入和刪除運算不需要移動元素B、所需要的存儲空間與線性表的長度成正比C、不必事先估計存儲空間大小D、可以隨機訪問表中的任意元素正確答案:【可以隨機訪問表中的任意元素】2、問題：有一個帶頭結點的單鏈表HEAD，則判斷其是否為空鏈表的表達式是選項：A、HEAD==NULLB、HEAD-〉NEXT==NULLC、HEAD-〉NEXT==HEADD、HEAD！=NULL正確答案:【HEAD-〉NEXT==NULL】3、問題：在一個單鏈表中P所指結點后插入一個S所指結點時，應執行語句：。選項：A、P-next=S;S-next=P-next;B、S-next=P-next;P-next=S;C、S-next=P-next;P=S;D、S-next=P;P-next=S;正確答案:【S-next=P-next;P-next=S;】第6講隨堂測驗1、問題：設指針變量p指向單鏈表中結點A的直接前驅，若刪除單鏈表中結點A，則需要修改指針的操作序列為（）。選項：A、q=p-next；p-next=q-next；free(q)；B、q=p-next；p-next=q-next；C、p-next=p-next-next；D、q=p-next；p-data=q-data；free(q)；正確答案:【q=p-next；p-next=q-next；free(q)；】2、問題：對鏈表進行插入和刪除操作時不必移動鏈表中結點。()選項：A、正確B、錯誤正確答案:【正確】3、問題：在單鏈表中，可以從頭結點出發，查找到表中所有結點。（）選項：A、正確B、錯誤正確答案:【正確】第二章單元測試（1）1、問題：在長度為n的順序表中的第i(1=i=n+1)個位置上插入一個元素，其算法時間復雜度為（）。選項：A、O(logn)(以2為底)B、O(1)C、O(n)D、O(n*n)正確答案:【O(n)】2、問題：在長度為n的順序表中的第i(1=i=n+1)個位置上插入一個元素，需要移動的元素個數為（）。選項：A、n-iB、iC、n-i+1D、n-i-1正確答案:【n-i+1】3、問題：鏈表不具有的特點是（）。選項：A、插入、刪除不需要移動元素B、可隨機訪問任一元素C、不必事先估計存儲空間D、所需存儲空間與線性表程度成正比正確答案:【可隨機訪問任一元素】4、問題：在一單鏈表中，刪除指針p所指的后繼結點，以下語句正確的是（）。選項：A、p-next=p-next-next;free(p-next);B、free(p-next);p-next=p-next-next;C、p=p-next;D、s=p-next;p-next=s-next;free(s);正確答案:【s=p-next;p-next=s-next;free(s);】5、問題：假設刪除長度為n的順序表中的每個元素的概率相同，則刪除一個元素平均要移動的元素個數是（）。選項：A、nB、(n+1)/2C、(n-1)/2D、n/2正確答案:【(n-1)/2】6、問題：設某順序表中第一個元素的地址是Base，每個結點占m個單元，則第i個結點的地址為（）。選項：A、Base+(i-1)×mB、Base+i×mC、Base-i×mD、Base+(i+1)×m正確答案:【Base+(i-1)×m】7、問題：長度為n的非空線性表采用順序存儲結構，在表的第i個位置插入一個數據元素，i的合法值應該是（）。選項：A、i0B、1≤i≤n+1C、1≤i≤n-1D、0≤i≤n+1正確答案:【1≤i≤n+1】8、問題：非空單鏈表結點結構為【data,next】，若指針p所指結點是尾結點，則（）表達式為真。選項：A、p==NULLB、p-next==NULLC、p-next==PD、p-next!=NULL正確答案:【p-next==NULL】9、問題：某順序表的第一個元素的存儲地址是500，每個元素占4個單元，則第8個元素的起始地址是()。選項：A、504B、508C、516D、528正確答案:【528】10、問題：在長度為n的順序表中刪除第i(1=i=n)個位置上的元素，需要移動的元素個數為（）。選項：A、n-iB、n-i+1C、n-i-1D、i正確答案:【n-i】11、問題：在長度為n的順序表中的的末尾位置上插入一個元素，其算法時間復雜度為（）。選項：A、O(1)B、O(n)C、O(logn）（以2為底）D、O(nlogn)正確答案:【O(1)】12、問題：以下算法的功能是在一個非遞減的順序存儲線性表中，刪除所有值相等的多余元素。時間復雜度為O(n)，空間復雜度為O(1)。劃線部分應填入的語句是（）。voidDelRepeatData(SeqList*L){i=0;j=1;while(j=L-last){if(L-elem[i]==L-elem[j]);else{L-elem[i+1]=L-elem[j];i++;j++;}}L-last=i;}選項：A、i++B、j++C、i--D、j--正確答案:【j++】13、問題：以下算法是刪除帶頭結點單鏈表L中的最小的元素，橫線處應填入的語句是（）。voidDelMinNode(LinkListL){p=L-next;pre=L;if(L==NULL)return;while(p-next!=NULL)//pre指向最小元素的前驅元素，開始默認第一個結點最小，pre指向頭結點{if(p-next-datapre-next-data)pre=p;}//刪除pre后面的結點p=pre-next;;}選項：A、free(p);pre-next=p-next;B、free(p-next);pre-next=p-next;C、pre-next=p-next;free(p);D、p-next=pre-next;free(p);正確答案:【pre-next=p-next;free(p);】14、問題：單鏈表中增加頭結點的目的是存儲鏈表的長度。選項：A、正確B、錯誤正確答案:【錯誤】15、問題：線性表在鏈式存儲時，查找第i個元素的時間同i的值無關。選項：A、正確B、錯誤正確答案:【錯誤】16、問題：線性表在順序存儲時，查找第i個元素的時間同i的值成正比。選項：A、正確B、錯誤正確答案:【錯誤】17、問題：線性表的特點是每個元素都有一個前驅和一個后繼。選項：A、正確B、錯誤正確答案:【錯誤】18、問題：線性表的鏈式存儲結構優于順序存儲。選項：A、正確B、錯誤正確答案:【錯誤】19、問題：順序存儲方式的優點是存儲密度大，插入、刪除效率高。選項：A、正確B、錯誤正確答案:【錯誤】20、問題：順序表的每個結點只能是一個基本類型，而鏈表的每個結點可以是一個構造類型。選項：A、正確B、錯誤正確答案:【錯誤】21、問題：插入和刪除操作是線性表的基本操作。這兩種操作在數組中也經常使用。選項：A、正確B、錯誤正確答案:【錯誤】22、問題：在順序表中，邏輯上相鄰的兩個元素物理存儲上也一定也相鄰。選項：A、正確B、錯誤正確答案:【正確】23、問題：在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理存儲上并不一定緊鄰。選項：A、正確B、錯誤正確答案:【正確】24、問題：線性表采用順序存儲，必須占用一段地址連續的存儲單元。選項：A、正確B、錯誤正確答案:【正確】25、問題：順序表結構適宜進行隨機訪問，而鏈表適宜進行插入、刪除。選項：A、正確B、錯誤正確答案:【正確】第7講循環鏈表隨堂測驗1、問題：有一個帶頭結點的循環單鏈表HEAD，則判斷其是否為空鏈表的條件是。選項：A、HEAD==NULLB、HEAD-〉NEXT==NULLC、HEAD-〉NEXT==HEADD、HEAD！=NULL正確答案:【HEAD-〉NEXT==HEAD】2、問題：在單向循環鏈表中，從表中任意結點出發都可以順著next域訪問到表中所有元素（）選項：A、正確B、錯誤正確答案:【正確】第8講雙向鏈表--隨堂測驗1、問題：與單鏈表相比，雙向鏈表的優點之一是。選項：A、插入刪除操作更加方便?B、可以進行隨機訪問C、可以省略表頭指針和表尾指針?D、訪問前后相鄰結點更方便。正確答案:【訪問前后相鄰結點更方便。】2、問題：在雙向鏈表L中，可以從任一結點p出發沿同一方向的指針域查找到表中所有元素。（）選項：A、正確B、錯誤正確答案:【錯誤】第9講靜態鏈表--隨堂測驗1、問題：靜態鏈表中與動態鏈表的插入和刪除運算類似，不需要做元素的移動。（）選項：A、正確B、錯誤正確答案:【正確】2、問題：靜態鏈表既有順序存儲結構的優點，又有動態鏈表的優點。所以，它存取表中第ｉ個元素的時間與位置序號ｉ無關，可以實現隨機存取。（）選項：A、正確B、錯誤正確答案:【錯誤】第10講鏈式結構小結--隨堂檢測1、問題：已知單鏈表的頭指針為head且該鏈表不帶頭結點，則該單鏈表為空的條件是。選項：A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL正確答案:【head==NULL】2、問題：設指針變量p指向單鏈表中某結點的直接前驅，若刪除單鏈表中該結點，需要修改指針的操作序列為。選項：A、q=p-next；p-next=q-next；free(q)；B、q=p-next；free(q)；C、p-next=p-next-next；free(p-next)；D、q=p-next；free(q)；正確答案:【q=p-next；p-next=q-next；free(q)；】3、問題：設帶有頭結點的單向循環鏈表的頭指針變量為head，則其判空條件是。選項：A、head==NULLB、head-next==NULLC、head-next==headD、head!=NULL正確答案:【head-next==head】4、問題：在雙向循環鏈表中，可以從任一結點p出發沿同一方向的指針域查找到表中所有元素。（）選項：A、正確B、錯誤正確答案:【正確】第12講隨堂測驗1、問題：下列選項中，項是鏈表不具有的特點。選項：A、插入和刪除運算不需要移動元素B、所需要的存儲空間與線性表的長度成正比C、不必事先估計存儲空間大小D、可以隨機訪問表中的任意元素正確答案:【可以隨機訪問表中的任意元素】2、問題：在線性表中最常用的操作是存取第i個元素及其前趨的值，可采用存儲方式最省時間？選項：A、順序表B、帶頭指針的雙向循環鏈表C、帶頭指針的單向循環鏈表D、帶頭指針的單向鏈表正確答案:【順序表】3、問題：下面關于線性表的敘述錯誤的是（）。選項：A、線性表采用順序存儲必須占用一片連續的存儲空間B、線性表采用鏈式存儲不必占用一片連續的存儲空間C、線性表采用鏈式存儲便于插入和刪除操作的實現D、線性表采用順序存儲便于插入和刪除操作的實現正確答案:【線性表采用順序存儲便于插入和刪除操作的實現】總結與提高隨堂測驗1、問題：某線性表中最常用的操作是存取序號為i的元素和在最后進行插入和刪除運算，則采用存儲方式時間性能最好。選項：A、雙向鏈表B、雙向循環鏈表C、單向循環鏈表D、順序表正確答案:【順序表】2、問題：已知一個帶頭結點的非空循環單鏈表，其尾指針是R，則其首元素結點的地址為：選項：A、R-nextB、*(R-next-next)C、(R-next-next)D、R-next-next正確答案:【R-next-next】3、問題：線性表的順序存儲優于鏈式存儲結構。（）選項：A、正確B、錯誤正確答案:【錯誤】4、填空題：在帶頭結點的非空單鏈表中，頭結點的存儲位置由指示正確答案:【頭指針】第1講隨堂測驗1、問題：棧操作的特性是（）選項：A、FIFOB、LIFOC、FCFSD、插入和刪除操作限制在表的兩端進行正確答案:【LIFO】2、問題：棧中，允許進行插入和刪除的一端稱為（）選項：A、棧頂B、棧底C、棧頭D、棧尾正確答案:【棧頂】3、問題：棧是線性結構，是操作受限制的線性表。（）選項：A、正確B、錯誤正確答案:【正確】第2講隨堂測驗1、問題：1、已知順序棧的地址為s,此時棧不滿且棧頂指示器top指向真實棧頂,執行元素x進棧操作正確的語句是（）選項：A、s-top++;s-elem[s-top]=x;B、s-top=s-top+1;s-elem[s-top]=x;C、s-elem[++s-top]=x;D、s-elem[s-top]=x;s-top++;正確答案:【s-top++;s-elem[s-top]=x;#s-top=s-top+1;s-elem[s-top]=x;#s-elem[++s-top]=x;】2、問題：2、已知順序棧的地址為s,此時棧不空且棧頂指示器top指向真實棧頂，執行出棧操作并將出棧元素賦值給x所指向的單元，則下列語句中，正確的是（）選項：A、s-top--;*x=s-elem[s-top];B、*x=s-elem[s-top];s-top=s-top-1;C、*x=s-elem[s-top--];D、*x=s-elem[s-top];s-top--;正確答案:【*x=s-elem[s-top];s-top=s-top-1;#*x=s-elem[s-top--];#*x=s-elem[s-top];s-top--;】3、問題：1、已知順序棧的地址為s,此時棧不空且棧頂指示器top指向真實棧頂，執行取棧頂操作的語句是*x=s-elem[s-top--];()選項：A、正確B、錯誤正確答案:【錯誤】第3講隨堂測驗1、問題：已知一個雙端棧的地址為dS，則該雙端棧不滿時，，元素x進1號棧（高端棧）操作的語句是（）選項：A、dS-stack[--dS-top[1]]=x;B、dS-stack[dS-top[1]]=x;dS-top[1]--;C、dS-top[1]--;dS-stack[dS-top[1]]=x;D、dS-stack[++dS-top[1]]=x;正確答案:【dS-top[1]--;dS-stack[dS-top[1]]=x;】2、問題：已知一個雙端棧dStack,則判斷該雙端棧棧滿的條件是（）選項：A、dStack.top[0]+1==dStack.top[1]B、dStack.top[0]==dStack.top[1]C、dStack.top[0]-1==dStack.top[1]D、dStack.top[0]==dStack.top[1]-1正確答案:【dStack.top[0]+1==dStack.top[1]#dStack.top[0]==dStack.top[1]-1】3、問題：已知一個雙端棧的地址為dS，則該雙端棧不空時，1號棧（高端棧）出棧操作的語句是*x=dS-stack[dS-top[1]--]（）選項：A、正確B、錯誤正確答案:【錯誤】第4講隨堂測驗1、問題：已知帶頭結點的鏈棧top,則該鏈棧不空時,出棧操作的語句是()選項：A、top-next=top-next-next;*x=top-next-data;B、*x=top-next-data;top-next=top-next-next;free(top-next);C、*x=top-data;p=top;top=p-next;free(p);D、*x=top-next-data;p=top-next;top-next=p-next;free(p);正確答案:【*x=top-next-data;p=top-next;top-next=p-next;free(p);】2、問題：已知帶頭結點的鏈棧top,則該鏈棧為空的條件是()選項：A、top==NULLB、top-next==NULLC、top-next-next==NULLD、top-next==top正確答案:【top-next==NULL】3、問題：已知帶頭結點的鏈棧top,則元素x對應的新結點s進棧操作的語句是（）選項：A、s-next=top-next;top-next=s;B、top-next=s;s-next=top-next;C、s-next=top;top=s;D、top=s;s-next=top;正確答案:【s-next=top-next;top-next=s;】第5講棧的應用1、問題：在括號匹配算法中，當正掃描檢測的符號是右括號，此時的棧是空棧，則（）。選項：A、右括號進棧；B、繼續向下掃描；C、取出棧頂元素做匹配檢查；D、此時出現“右括號多了”的不匹配現象。正確答案:【此時出現“右括號多了”的不匹配現象。】2、問題：在算術表達式求值的算法中，若當前正掃描的符號是運算符s，且s的優先級比運算符棧棧頂元素的優先級高，則（）選項：A、運算符棧出棧，運算數出棧，做運算；B、s進運算符棧；C、取運算符棧棧頂，運算數棧頂，做運算；D、s進運算數棧；正確答案:【s進運算符棧；】3、填空題：在括號匹配算法中，當正掃描的符號是左括號時，則該做左括號（）。正確答案:【進棧】第6講隨堂測驗1、問題：遞歸進層（i→i+1層）系統需要做三件事是（）選項：A、保留本層參數與返回地址；B、保留下層參數和函數地址；C、為被調用函數的局部變量分配存儲區，給下層參數賦值；D、將程序轉移到被調函數的入口。正確答案:【保留本層參數與返回地址；#為被調用函數的局部變量分配存儲區，給下層參數賦值；#將程序轉移到被調函數的入口。】2、問題：從被調用函數返回調用函數之前，遞歸退層（i←i+1層）系統也應完成三件工作是（）選項：A、保存被調函數的計算結果；B、釋放被調函數的數據區，恢復上層參數；C、保存返回上層函數的地址；D、依照被調函數保存的返回地址，將控制轉移回調用函數。正確答案:【保存被調函數的計算結果；#釋放被調函數的數據區，恢復上層參數；#依照被調函數保存的返回地址，將控制轉移回調用函數。】3、問題：遞歸是指在定義自身的同時又出現了對自身的引用。（）選項：A、正確B、錯誤正確答案:【正確】4、填空題：系統需設立一個遞歸工作棧作為整個遞歸函數運行期間使用的數據存儲區。每層遞歸所需信息構成一個（）。正確答案:【工作記錄】第三章單元測驗（1）1、問題：棧的特點是（）。選項：A、先進先出B、先進后出C、后進后出D、沒有順序正確答案:【先進后出】2、問題：隊列的特點是（）。選項：A、先進先出B、先進后出C、后進先出D、沒有順序正確答案:【先進先出】3、問題：棧之說以叫限定性線性表，是因為（）。選項：A、棧的操作位置受限制B、棧中的元素類型受限制C、棧的應用范圍受限制D、棧的存儲結構受限制正確答案:【棧的操作位置受限制】4、問題：輸入序列為123，若進棧、出棧操作可以交替進行，則不能得到的出棧序列是（）。選項：A、321B、312C、123D、132正確答案:【312】5、問題：以下會用到棧的應用是（）。選項：A、遞歸B、子程序調用C、括號匹配D、以上選項均有可能正確答案:【以上選項均有可能】6、問題：循環隊列存儲在數組A[0..m-1]中，則入隊時rear應該變化為（）選項：A、rear++B、rear=(rear+1)mod(m-1)C、rear=(rear+1)modmD、rear=(rear+1)mod(m+1)正確答案:【rear=(rear+1)modm】7、問題：循環隊列A[0..n-1]存放其元素值，F表示隊頭元素所在的位置，R表示隊尾元素的下一個位置。則當前隊列中的元素數是()。選項：A、(R-F+n)%nB、R-F+1C、R-F-1D、R-F正確答案:【(R-F+n)%n】8、問題：棧和隊列的共同點是（）。選項：A、都是先進先出B、都是先進后出C、只允許在端點處插入和刪除元素D、它們沒有共同點正確答案:【只允許在端點處插入和刪除元素】9、問題：當利用大小為n的數組(下標從1到n)順序存儲一個棧時，假定用top==n表示棧空，則每次向這個棧插入一個元素時，首先應執行（）語句修改top指針。選項：A、top++;B、top--;C、top=0;D、top=n;正確答案:【top--;】10、問題：設棧S和隊列Q的初始狀態均為空，元素a,b,c,d,e,f,g依次進入棧S。如果每個元素出棧后立即進入隊列Q，且7個元素出隊的順序為b,d,e,f,c,a,g，則棧S的容量至少是（)。選項：A、1B、2C、3D、4正確答案:【3】11、問題：以下屬于遞歸求解問題的前提條件的是（）。選項：A、原問題可層層分解為子問題，且子問題比原問題規模小B、子問題的解法與原問題解法相同C、最小的子問題有解D、其他選項均是正確答案:【其他選項均是】12、問題：以下屬于消除遞歸的主要原因是（）。選項：A、遞歸程序不容易理解B、遞歸程序時空效率較差C、遞歸程序容易寫錯D、其他選項均是正確答案:【遞歸程序時空效率較差】13、問題：一個棧的輸入序列為123……n，若輸出序列的第一個元素是n，輸出第i（1=i=n）個元素是（）選項：A、iB、n-iC、n-i+1D、不確定正確答案:【n-i+1】14、問題：凡是元素的保存次序與使用順序相反的，都可以使用（）。選項：A、棧B、隊列C、順序表D、鏈表正確答案:【棧】15、問題：若棧采用順序存儲方式存儲，現兩棧共享空間S[1~N]，top[i]代表第i個棧(i=1,2)棧頂。棧1的底在S[1]，棧2的底在S[N]，則棧滿的條件是（）。選項：A、top[1]+top[2]==NB、top[1]+1==top[2]C、top[1]+top[2]==N-1D、top[2]-top[1]==0正確答案:【top[1]+1==top[2]】16、問題：消除遞歸肯定要用到棧，否則無法完成。選項：A、正確B、錯誤正確答案:【錯誤】17、問題：若輸入序列為1234,則通過一個棧可以得到輸出序列3124。選項：A、正確B、錯誤正確答案:【錯誤】18、問題：若輸入序列為1234,則通過棧只能得到4321的輸出序列。選項：A、正確B、錯誤正確答案:【錯誤】19、問題：有些問題，比如漢諾塔問題等，只能用遞歸來解，無法轉換成非遞歸算法。選項：A、正確B、錯誤正確答案:【錯誤】20、問題：順序棧因為是順序存儲，所以可以隨機存取棧中任意元素。選項：A、正確B、錯誤正確答案:【錯誤】21、問題：兩順序棧共享空間，也存在空間溢出問題。選項：A、正確B、錯誤正確答案:【正確】22、問題：棧和隊列都是限制插入和刪除位置的線性結構。選項：A、正確B、錯誤正確答案:【正確】23、問題：函數或過程調用需要用到棧。選項：A、正確B、錯誤正確答案:【正確】第7講隨堂測驗1、問題：遞歸算法具有兩個特性分別是（）選項：A、遞歸算法求解問題，方法簡單。B、遞歸算法效率高C、遞歸算法求解問題，方法復雜D、遞歸算法的效率較低正確答案:【遞歸算法求解問題，方法簡單。#遞歸算法的效率較低】2、問題：下列可以直接用循環結構即可將遞歸轉換為非遞歸的是（）選項：A、斐波那契數列問題B、N!問題C、漢諾塔問題D、尾遞歸問題正確答案:【斐波那契數列問題#N!問題#尾遞歸問題】第8講隨堂測驗1、問題：已知帶頭結點的鏈隊列指針Q，則該隊列做新元素結點s進隊操作的語句是（）選項：A、Q-rear-next=s;Q-rear=s;B、s-next=Q-front-next;Q-front-next=s;C、Q-next=s;Q=s;D、s-next=Q-next;Q-next=s;正確答案:【Q-rear-next=s;Q-rear=s;】2、問題：已知帶頭結點的鏈隊列指針Q，則該非空隊列取隊頭元素操作的語句是（）選項：A、*x=Q-next-data;B、*x=Q-front-data;C、*x=Q-front-next-data;D、*x=Q-rear-data;正確答案:【*x=Q-front-next-data;】3、問題：隊列操作的特性是LIFO。（）選項：A、正確B、錯誤正確答案:【錯誤】4、問題：隊列允許做插入的一端稱為隊頭，允許刪除的一端稱為隊尾（）選項：A、正確B、錯誤正確答案:【錯誤】第9講隨堂測驗1、問題：已知循環隊列Q-element[MAXSIZE],隊頭指示器為Q-front，隊尾指示器為Q-rear（指向真實隊尾的下一個位置），則該隊列中元素個數為：（）選項：A、Q-rear-Q-frontB、Q-rear-Q-front+1C、（Q-rear-Q-front+MAXSIZE）%MAXSIZED、（Q-rear-Q-front+1+MAXSIZE）%MAXSIZE正確答案:【（Q-rear-Q-front+MAXSIZE）%MAXSIZE】2、問題：已知循環隊列Q-element[MAXSIZE],隊頭指示器為Q-front，隊尾指示器為Q-rear（指向真實隊尾的下一個位置），則該隊列為空隊列的條件為（）選項：A、Q-rear==Q-frontB、Q-rear+1==Q-frontC、（Q-rear+1）%MAXSIZE==Q-frontD、（Q-rear-1）%MAXSIZE==Q-front正確答案:【Q-rear==Q-front】3、問題：已知循環隊列Q-element[MAXSIZE],隊頭指示器為Q-front，隊尾指示器為Q-rear（指向真實隊尾的下一個位置），則該隊列為滿隊列的條件為（）（采用少用一個空間的方法）選項：A、Q-rear==Q-frontB、Q-rear+1==Q-frontC、（Q-rear+1）%MAXSIZE==Q-frontD、（Q-rear-1）%MAXSIZE==Q-front正確答案:【（Q-rear+1）%MAXSIZE==Q-front】第10講隨堂測驗1、問題：在打印楊輝三角形前N行的算法中，需要申請一個N*N的二維數組存放楊輝三角形N行數據。（）選項：A、正確B、錯誤正確答案:【錯誤】第三章單元測驗（2）1、問題：隊列對數據的操作順序是（）。選項：A、先進先出B、先進后出C、隨機存取D、其余三個均正確正確答案:【先進先出】2、問題：設rear是非空循環單鏈表的尾指針，則刪除表中第一個元素結點的操作可表示為（）（該鏈表不帶頭結點）。選項：A、p=rear-next;rear-next=p-next;free(p);B、p=rear-next;free(p);rear-next=p-next;C、free(rear-next);rear-next=rear-next-next;D、p=rear-next;free(p);rear-next=rear-next;正確答案:【p=rear-next;rear-next=p-next;free(p);】3、問題：設棧S和隊列Q的初始狀態均為空，元素a,b,c,d,e,f,g依次進入棧S（進棧和出棧可交替進行）。如果每個元素出棧后立即進入隊列Q，且7個元素出隊的順序為b,d,e,f,c,a,g，則棧S的容量至少是（）。選項：A、1B、2C、3D、4正確答案:【3】4、問題：以下應用可能會用到棧的是（）。選項：A、遞歸調用B、表達式求值C、函數調用D、其余三個答案均正確正確答案:【其余三個答案均正確】5、問題：一個隊列的元素入隊順序是1,2,3,4，則出隊順序為（）。選項：A、1,2,3,4B、4,3,2,1C、2,1,3,4D、3,4,2,1正確答案:【1,2,3,4】6、問題：某循環隊列用數組A[0..n-1]表示，指示器為front指向隊頭元素，指示器rear指向隊尾后的空單元。則當前隊列中的元素個數為（）。選項：A、(rear-front+n)%nB、rear-frontC、（rear-front+n+1)%nD、(rear-front+n-1)%n正確答案:【(rear-front+n)%n】7、問題：以下函數的功能是（）。voidfun(Queue*Q){StackS;intd;InitStack(S);while(!EmptyQueue(*Q)){DeleteQueue(Q,d);Push(S,d);}while(!EmptyStack(S)){Pop(S,d);EnterQueue(Q，d);}}選項：A、將隊列Q中的元素逆置。B、將隊列Q中的元素放入棧中。C、將隊列Q中的元素放入棧中，然后再從棧中取出來放入隊列中。D、刪除隊列Q中的元素正確答案:【將隊列Q中的元素逆置。】8、問題：棧和隊列都是限制存取位置的線性結構。選項：A、正確B、錯誤正確答案:【正確】9、問題：循環隊列用數組A[0..n-1]表示，則入隊時的隊尾指針變換語句為：rear=(rear+1)%n;選項：A、正確B、錯誤正確答案:【正確】10、問題：一般的緩沖區用隊列做為數據結構。選項：A、正確B、錯誤正確答案:【正確】11、問題：循環隊列因為是順序存儲，因此可以隨機存取。選項：A、正確B、錯誤正確答案:【錯誤】12、問題：判斷表達式中的括號是否匹配，采用隊列數據結構最佳。選項：A、正確B、錯誤正確答案:【錯誤】第1講隨堂測驗1、問題：設s=‘abcd’,s1=‘123’，則執行語句StrInsert(s,2,s1)后，s=.選項：A、‘123abcd’B、‘a123bcd’C、‘ab123cd’D、‘abc123d’正確答案:【‘a123bcd’】2、問題：設s=‘abcd’，則執行語句StrDelete(s,2,2)后，s=.選項：A、‘abcd’B、‘abc’C、‘ad’D、‘a’正確答案:【‘ad’】第2講隨堂測驗1、填空題：假設主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法從主串的第6個字符開始模式匹配，需要做趟匹配，方能找到匹配串。正確答案:【4】2、填空題：假設主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法從主串的第6個字符開始模式匹配，在第2趟匹配中，要做次比較。正確答案:【4】第3講隨堂測驗1、問題：用帶頭結點的單鏈表來表示串s,則串s為空串的條件是（）選項：A、s-next==NULLB、s==NULLC、s-next==sD、s-next-next==NULL正確答案:【s-next==NULL】隨堂測驗1、問題：假設有6行8列的二維數組A(下標從1開始),每個元素占用6個字節,存儲器按字節編址。已知A的基地址為1000,計算按行存儲時元素A36的地址是;選項：A、1126B、1138C、1192D、無法確定正確答案:【1126】2、問題：假設有6行8列的二維數組A(下標從1開始),每個元素占用6個字節,存儲器按字節編址。已知A的基地址為1000,計算按列存儲時元素A36的地址是;選項：A、1192B、1126C、1138D、無法確定正確答案:【1192】隨堂測驗1、問題：已知一個n行n列的三對角帶狀矩陣A，其中非零元素的個數是（）。選項：A、3n-2B、3n+2C、3nD、n*n正確答案:【3n-2】2、問題：若將n階上三角矩陣A按列優先壓縮存放在一維數組B中，第一個非零元素存放在B[0]中，則非零元素aij存放在B[k]中，則k=()。選項：A、B、C、D、正確答案:【】第3講隨堂測驗1、問題：對稀疏矩陣進行壓縮存儲的目的是（）選項：A、便于進行矩陣運算B、便于輸入和輸出C、節省存儲空間D、減低運算的時間復雜度正確答案:【節省存儲空間】2、問題：稀疏矩陣壓縮存儲后，不會失去（）功能輸入輸出選項：A、順序存儲B、隨機存取C、輸入輸出D、輸入輸出正確答案:【隨機存取】第4講隨堂測驗1、填空題：對于一個m行n列的稀疏矩陣中有len個非零元素，則用十字鏈表存儲時，需要（）個頭指針。正確答案:【m+n】2、填空題：對于一個m行n列的稀疏矩陣中有len個非零元素，則用十字鏈表存儲時，需要（）個三元組結點。正確答案:【len】第5講隨堂測驗1、問題：任意一個廣義表都可以表示為由表頭和表尾構成（）。選項：A、正確B、錯誤正確答案:【錯誤】2、問題：非空的廣義表的表尾可能是單個元素也可能是表元素（）。選項：A、正確B、錯誤正確答案:【錯誤】3、填空題：已知廣義表L=((x,y,z),a,(u,t,w)),則head(head(tail(tail(L))))的結果是（）。正確答案:【u】4、填空題：已知數組M[1..10,-1..6,0..3],)若數組以行序為主序存儲,起始地址為1000,且每個數據元素占用3個存儲單元,則M[2,4,2]的地址為（）正確答案:【1162】第1講隨堂測驗1、問題：樹最適合用來表示（）選項：A、有序數據元素B、無序數據元素C、元素之間具有分支層次關系的數據D、元素之間無聯系的數據正確答案:【元素之間具有分支層次關系的數據】2、填空題：若一棵樹的廣義表法表示為：A（B（E,F），C（G（H,I,J,K），L），D（M（N）））則該樹的度為（）；正確答案:【4】3、填空題：若一棵樹的廣義表法表示為：A（B（E,F），C（G（H,I,J,K），L），D（M（N）））該樹的深度為（）；正確答案:【4】4、填空題：若一棵樹的廣義表法表示為：A（B（E,F），C（G（H,I,J,K），L），D（M（N）））該樹中葉子結點的個數為：（）正確答案:【8】第2講隨堂測驗1、問題：按照二叉樹的定義，具有3個結點的二叉樹有（）種選項：A、3B、4C、5D、6正確答案:【5】2、問題：若一棵二叉樹有10個度為2的結點，5個度為1的結點，則度為0的結點有（）個。選項：A、9B、11C、15D、不確定正確答案:【11】3、問題：一個高度為h的完全二叉樹至少有（）個結點選項：A、B、C、D、正確答案:【】4、問題：二叉樹就是結點度不大于2的樹。（）選項：A、正確B、錯誤正確答案:【錯誤】5、問題：不存在這樣的二叉樹：它有n個度為0的結點，n-1個度為1的結點，n-2個度為2的結點。（）選項：A、正確B、錯誤正確答案:【正確】6、填空題：具有n個結點的二叉樹采用二叉鏈表存儲結構，共有（）非空的指針域。正確答案:【n-1】7、填空題：擁有100個結點的完全二叉樹的最大層數是（）正確答案:【7】第3講隨堂測驗1、問題：某二叉樹的先序序列和中序序列正好相同，則該二叉樹一定是（）選項：A、空樹或只有一個結點B、完全二叉樹C、每個結點都沒有左子D、高度等于其結點數正確答案:【每個結點都沒有左子】2、問題：在二叉樹中，p所指向的結點為度為1的分支點的條件是（）選項：A、p-lchild==NULL||p-rchild==NULLB、!(p-lchild!=NULLp-rchild!=NULL)C、!(p-lchild==NULLp-rchild==NULL)D、(p-lchild==NULLp-rchild!=NULL)||(p-lchild!=NULLp-rchild==NULL)正確答案:【(p-lchild==NULLp-rchild!=NULL)||(p-lchild!=NULLp-rchild==NULL)】3、問題：已知二叉樹的先序和后序遍歷序列可以唯一確定該二叉樹。（）選項：A、正確B、錯誤正確答案:【錯誤】第六章單元測驗11、問題：已知一算術表達式的中綴形式為A-B/C+D*E，前綴形式為+-A/BC*DE，其后綴形式為()。選項：A、ABCDE/-*+B、AB/C-D*E+C、ABC/-DE*+D、A-BC/DE*+正確答案:【ABC/-DE*+】2、問題：有關二叉樹下列說法正確的是（）。選項：A、二叉樹中每個結點的度都為2B、一棵二叉樹的度可以小于2C、二叉樹中至少有一個結點的度為2D、二叉樹中任何一個結點的度都為2正確答案:【一棵二叉樹的度可以小于2】3、問題：在一棵高度為k的滿二叉樹中，結點總數為（）。選項：A、-1B、2kC、D、正確答案:【-1】4、問題：某二叉樹中有60個葉子結點，則該二叉樹中度為2的結點個數為（）。選項：A、59B、60C、61D、不確定正確答案:【59】5、問題：100個結點的完全二叉樹采用順序存儲，從1開始按層次編號，則編號最小的葉子結點的編號應該是（）。選項：A、100B、49C、50D、51正確答案:【51】6、問題：高度為7的完全二叉樹，最少有（）個結點。選項：A、64B、127C、63D、128正確答案:【64】7、問題：高度為7的二叉樹，最少有（）個結點。選項：A、7B、13C、64D、127正確答案:【7】8、問題：對任意一棵有n個結點的樹，這n個結點的度之和為()。選項：A、n-1B、nC、n+2D、2*n正確答案:【n-1】9、問題：完全二叉樹一定存在度為1的結點。選項：A、正確B、錯誤正確答案:【錯誤】10、問題：完全二叉樹中，若一個結點沒有左孩子，則它必是葉子。選項：A、正確B、錯誤正確答案:【正確】11、問題：二叉樹只能用二叉鏈表表示。選項：A、正確B、錯誤正確答案:【錯誤】12、問題：樹形結構中，每個元素都有一個前驅，0個或多個后繼。選項：A、正確B、錯誤正確答案:【錯誤】第4講隨堂檢測1、問題：設二叉樹采用二叉鏈表方式存儲，root指向根結點，r所指結點為二叉樹中任一給定的結點。則可以通過改寫（）算法，求出從根結點到結點r之間的路徑。選項：A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷正確答案:【后序遍歷】2、問題：已知二叉樹用二叉鏈表存儲，則若實現二叉樹實現左右子樹交換，可以借助改寫（）遍歷算法實現。選項：A、先序遍歷B、中序遍歷C、后序遍歷D、以上三種都可以正確答案:【先序遍歷#后序遍歷】第5講隨堂測驗1、問題：在中序遍歷非遞歸算法中，在進入子樹進行訪問前，需要在自定義棧中保存（）選項：A、本層根結點指針B、本層根結點的右孩子指針C、本層根結點的左孩子指針D、無需保留任何信息正確答案:【本層根結點指針】第6講隨堂測驗1、問題：引入線索二叉樹的目的是()選項：A、加快查找指定遍歷過程中結點的直接前驅和直接后繼B、為了能在二叉樹中方便地插入和刪除結點C、為了方便找到結點的雙親D、使二叉樹遍歷結果唯一正確答案:【加快查找指定遍歷過程中結點的直接前驅和直接后繼】2、問題：若判斷線索二叉樹中的p結點有右孩子結點則下列（）表達式為真。選項：A、p!=NULLB、p-rchild!=NULLC、p-rtag==0D、p-rtag==1正確答案:【p-rtag==0】3、問題：若線索二叉樹中的p結點沒有左孩子結點則下列（）表達式為真。選項：A、p==NULLB、p-lchild==NULLC、p-ltag==0D、p-ltag==1正確答案:【p-ltag==1】第7講隨堂測驗1、問題：一棵二叉樹的后序序列是：CBEFDA,中序序列是：CBAEDF,則該二叉樹的先序序列是（）選項：A、ABCDEFB、ABCEDFC、ABDEFCD、ABFECD正確答案:【ABCDEF】2、問題：一棵二叉樹的先序序列是：CEDBA,中序序列是：DEBAC,則該二叉樹的后序序列是（）選項：A、DABECB、DCBAEC、DEABCD、CBADE正確答案:【DABEC】第8講隨堂測驗1、問題：如圖所示的二叉樹BT是由森林T1轉換而來的二叉樹，那么森林T1中有（）葉子結點。選項：A、4B、5C、6D、7正確答案:【6】2、填空題：與樹等價的二叉樹，根沒有（）子樹。正確答案:【右】第9講隨堂測驗1、問題：有13個葉子結點的哈夫曼樹，該樹中結點總數為（）選項：A、13B、26C、12D、25正確答案:【25】2、問題：在哈夫曼樹中，權值相同的葉子點一定在同一層上。（）選項：A、正確B、錯誤正確答案:【錯誤】3、問題：在哈夫曼樹中，權值較大的葉子點一般離根比較近。（）選項：A、正確B、錯誤正確答案:【正確】4、填空題：若以{4,5,6,7,8}作為葉子點構造哈夫曼樹，則其帶全路徑長度為（）正確答案:【69】第10講隨堂測驗1、問題：在哈夫曼編碼中，當兩個字符出現的頻率相等時，則兩個字符的哈夫曼編碼也相同。（）選項：A、正確B、錯誤正確答案:【錯誤】第六章單元測驗21、問題：已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為（）。選項：A、CBEFDAB、FEDCBAC、CBEDFAD、不確定正確答案:【CBEFDA】2、問題：線索二叉樹中，判斷p所指向的結點為葉子結點的條件是（）。選項：A、p-LC==NULLp-RC==NULLB、p-LTag==1C、p-LC==NULLp-LTag==0D、p-LTag==0p-RTag==0正確答案:【p-LTag==0p-RTag==0】3、問題：以下屬于前綴編碼的是（）。選項：A、{0,1,01,010,110}B、{00,01,10,11,101}C、{0,1101,1110,1100,1111}D、{01,00,10,001,110,101}正確答案:【{0,1101,1110,1100,1111}】4、問題：在下列存儲形式中，（）不是樹的存儲形式。選項：A、雙親表示法B、孩子鏈表表示法C、孩子-兄弟表示法D、順序存儲表示法正確答案:【順序存儲表示法】5、問題：對二叉樹中的結點進行編號，要求根結點的編號最小，左孩子結點編號比右孩子結點編號小。則應該采用（）遍歷方法對其進行編號。選項：A、先序B、中序C、后序D、層次正確答案:【先序】6、問題：已知某二叉樹的后序遍歷序列是CEFDBA，中序遍歷序列是CBEDFA。與該二叉樹對應的樹或森林中，葉子的數目是（）個。選項：A、1B、2C、3D、4正確答案:【3】7、問題：某二叉樹中有60個葉子結點，則該二叉樹中度為2的結點個數為（）。選項：A、59B、60C、61D、不一定正確答案:【59】8、問題：某二叉樹的邏輯結構如下圖所示，則其擴展先序序列為（）。選項：A、ABB、DFE、CF、EH、（I、表示空）J、ABK、DFN、CO、E（P、表示空）Q、ABDFCER、ABCDEF正確答案:【AB#DF###C#E##（#表示空）】9、問題：樹的后根遍歷，相當于對應二叉樹的（）遍歷。選項：A、中序B、先序C、后序D、層次正確答案:【中序】10、問題：哈夫曼樹的帶權路徑長度等于其中所有結點的帶權路徑之和。選項：A、正確B、錯誤正確答案:【錯誤】11、問題：給定二叉樹的先序、中序和后序遍歷序列中的任意兩個，就可以唯一確定一棵二叉樹。選項：A、正確B、錯誤正確答案:【錯誤】12、問題：在葉子數目和權值相同的所有二叉樹中，帶權路徑長度最小的樹一定是哈夫曼樹。選項：A、正確B、錯誤正確答案:【正確】13、問題：將一棵樹轉成二叉樹，根結點一定沒有右子樹。選項：A、正確B、錯誤正確答案:【正確】14、填空題：有10個葉子結點的哈夫曼樹，總結點個數是。正確答案:【19】15、填空題：將一棵樹轉換為二叉樹時，遵循的規則是左孩子、。正確答案:【右兄弟】16、填空題：用權值{1,2,3,4,5}構造一棵哈夫曼樹，則該樹的帶權路徑長度為。正確答案:【33】17、填空題：假設T是一棵高度為5的二叉樹,T中只有度為0和度為2的結點，那么T樹最少應該有個結點。正確答案:【9】第1講隨堂測驗1、問題：一個有n個頂點的有向圖最多有邊選項：A、nB、n(n-1)C、n(n-1)/2D、2n正確答案:【n(n-1)】2、問題：具有n個頂點的有向圖至少應有弧才能確保是一個強連通圖。選項：A、n-1B、nC、n(n-1)D、n(n-1)/2正確答案:【n】3、填空題：在一個無向圖中，所有頂點的度之和等于邊條數的倍。正確答案:【2】4、填空題：具有6個頂點的無向圖至少應有條邊才能確保是一個連通圖。正確答案:【5】5、填空題：一個有向圖G中所有頂點的入度之和是所有頂點出度之和的倍。正確答案:【1】第2講隨堂測驗1、問題：對于一個n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）選項：A、nB、n(n-1)C、D、正確答案:【】2、問題：有向圖的鄰接矩陣一定是對稱矩陣。（）選項：A、正確B、錯誤正確答案:【錯誤】3、問題：用鄰接矩陣存儲無向圖G時，其第i行中1的個數與第i列中1的個數相等。（）選項：A、正確B、錯誤正確答案:【正確】4、填空題：對于一個有n個頂點，e條邊的無向圖，若采用鄰接表表示，則表頭結點數組的大小為。正確答案:【n】5、填空題：對于一個有n個頂點，e條邊的無向圖，若采用鄰接表表示，則邊結點有個。正確答案:【2e##%_YZPRLFH_%##2*e】6、填空題：用鄰接矩陣存儲有向圖G時，其第i列的所有元素之和等于該頂點的。正確答案:【入度】第3講隨堂測驗1、問題：如果從一個無向圖的任意一個頂點出發進行一次深度優先搜索即可訪問所有頂點,則該圖一定是()選項：A、完全圖B、連通圖C、有回路D、森林正確答案:【連通圖】2、問題：圖的深度優先遍歷類似于樹的（）遍歷選項：A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷正確答案:【先序遍歷】3、問題：圖的廣度優先遍歷類似于樹的（）遍歷選項：A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷正確答案:【層次遍歷】第4講隨堂測驗1、問題：任何一個連通圖（）生成樹。選項：A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在正確答案:【有一棵或多棵】2、問題：Prim算法適合求（）的最小生成樹。選項：A、邊稠密連通網B、邊稀疏連通網C、邊稠密無向網D、邊稀疏無向網正確答案:【邊稠密連通網】3、問題：對于n個頂點的連通圖G來說，如果其中的某個子圖有n個頂點，n-1條邊，則該子圖一定是G的生成樹。（）選項：A、正確B、錯誤正確答案:【錯誤】4、填空題：對于n個頂點的連通圖而言，它的生成樹一定有條邊。正確答案:【n-1】第5講隨堂測驗1、問題：若一個有向圖中的頂點不能排成一個拓撲序列，則可斷定該有向圖（）選項：A、是個有向無環圖B、是個含有回路的有向圖C、含有多個入度為0的頂點D、是個強連通圖正確答案:【是個含有回路的有向圖】2、問題：任何有向無環圖的頂點都可以排成拓撲排序序列，且拓撲排序序列唯一（）選項：A、正確B、錯誤正確答案:【錯誤】3、填空題：在ＡＯＶ網中，頂點表示。正確答案:【活動】第6講隨堂測驗1、問題：關鍵路徑是ＡＯE網中（?）選項：A、從源點到匯點的最長路徑B、從源點到匯點的最短路徑C、最長回路D、最短回路正確答案:【從源點到匯點的最長路徑】2、問題：關鍵活動若不能按期完成就會影響整個工程的完成時間，若某些關鍵活動能提前完成，將可能使整個工程提前完成。（）選項：A、正確B、錯誤正確答案:【正確】3、填空題：在ＡＯE網中，關鍵路徑上的活動稱為。正確答案:【關鍵活動】第7講隨堂測驗1、問題：求最短路徑的Dijkstra算法的時間復雜度為（）n為圖中頂點數，e為圖中邊數。選項：A、O（n）B、O（n+e）C、O（）D、O(ne)正確答案:【O（）】2、問題：求最短路徑的Dijkstra算法不適用于有回路的有向網（）選項：A、正確B、錯誤正確答案:【錯誤】第七章單元測驗1、問題：在一個圖中，所有頂點的度之和是所有邊數的()倍。選項：A、1/2B、1C、2D、3正確答案:【2】2、問題：在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的()倍。選項：A、1/2B、1C、2D、4正確答案:【1】3、問題：一個有n個頂點的無向圖最多有()條邊。選項：A、nB、n*(n-1)C、(n*(n-1))/2D、2*n正確答案:【(n*(n-1))/2】4、問題：在一個具有n個頂點的無向圖中，要連通全部頂點至少需要()條邊。選項：A、nB、n+`C、n-1D、n/2正確答案:【n-1】5、問題：對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是()。選項：A、nB、n*nC、2*(n-1)D、n-1正確答案:【n*n】6、問題：對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表存儲，則鄰接表中的結點總數是()。選項：A、e/2B、2C、2*eD、n+e正確答案:【2*e】7、問題：以下說法錯誤的是()。選項：A、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結點個數有關，而與圖的邊數無關。B、鄰接表只能用于有向圖的存儲，而鄰接矩陣對于有向圖和無向圖的存儲都適用。C、存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（或上）三角部分就可以了D、用鄰接矩陣M表示圖，判定任意兩個結點Vi和Vj之間是否有長度為n的路徑相連，則只要檢查M的n次方后，第i行第j列的元素是否為0即可。正確答案:【鄰接表只能用于有向圖的存儲，而鄰接矩陣對于有向圖和無向圖的存儲都適用。】8、問題：已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發的方法是（）。選項：A、將矩陣第i行刪除，后序行上移B、將矩陣第i列刪除，后序列左移C、將矩陣第i行上的元素全部置0D、將矩陣第i列上的元素全部置0正確答案:【將矩陣第i行上的元素全部置0】9、問題：某圖的鄰接表存儲結構如下圖所示，則從6號點出發，深度優先遍歷的序列是（）選項：A、6-5-2-1-4-3B、6-5-1-2-4-3C、6-5-1-4-3-2D、6-5-2-1-4-3正確答案:【6-5-1-2-4-3】10、問題：某圖的鄰接矩陣存儲結構如下圖所示，則從6號點出發，廣度優先遍歷的序列是（）選項：A、6-1-2-5-4-3B、6-1-2-4-5-3C、6-5-1-4-3-2D、6-5-2-1-4-3正確答案:【6-1-2-5-4-3】11、問題：對具有n個頂點的連通圖，其生成樹有且僅有()條邊。選項：A、n-1B、nC、n*nD、不確定正確答案:【n-1】12、問題：稀疏圖采用（）存儲較省空間。選項：A、鄰接表B、鄰接矩陣C、鄰接多重表D、以上都可以正確答案:【鄰接表】13、問題：關鍵路徑是從源點到匯點的（）路徑。選項：A、最長的B、最短的C、結點個數最少的D、結點個數最多的正確答案:【最長的】14、問題：在有向圖的鄰接矩陣上，第i行中的非零且非無窮元素個數是第i個結點的（）。選項：A、出度B、入度C、度D、鄰接點個數正確答案:【出度】15、問題：關鍵路徑上的活動都是關鍵活動，它們是否按時完成會影響工期。選項：A、正確B、錯誤正確答案:【正確】16、問題：求稀疏圖的最小生成樹，用克魯斯卡爾算法來求解較高效。選項：A、正確B、錯誤正確答案:【正確】17、問題：求稠密圖的最小生成樹，用普里姆算法來求解較好。選項：A、正確B、錯誤正確答案:【正確】18、問題：迪杰斯特拉算法求最短路徑時，是按照路徑長度遞增的順序求解的。選項：A、正確B、錯誤正確答案:【正確】19、問題：一個有向圖的拓撲排序只有一個。選項：A、正確B、錯誤正確答案:【錯誤】20、問題：每一個有向圖肯定至少有一個拓撲排序。選項：A、正確B、錯誤正確答案:【錯誤】21、問題：具有6個頂點的無向圖至少應有6條邊才能確保是一個連通圖。選項：A、正確B、錯誤正確答案:【錯誤】22、問題：非關鍵活動，可以無限期延遲。選項：A、正確B、錯誤正確答案:【錯誤】第1講隨堂測驗1、問題：采用順序查找法查找長度為n的線性表時，平均查找長度為。選項：A、nB、C、D、正確答案:【】2、問題：通常將作為衡量一個查找算法效率優劣的標準。選項：A、平均查找長度B、比較次數C、WPLD、ASL正確答案:【平均查找長度#ASL】3、問題：順序查找方法只能在順序存儲結構上進行。（）選項：A、正確B、錯誤正確答案:【錯誤】4、填空題：順序查找含n個元素的順序表，若查找成功，則比較關鍵字的次數最多為次。正確答案:【n】5、填空題：順序查找含n個元素的順序表，若查找不成功，則比較關鍵字的次數為次。正確答案:【n+1】第2講隨堂測驗1、問題：對列表進行折半查找時，要求列表必須。選項：A、順序存儲B、鏈式存儲C、順序存儲且元素按關鍵字有序存儲D、鏈式存儲且元素按關鍵字有序存儲正確答案:【順序存儲且元素按關鍵字有序存儲】2、問題：當采用分塊查找時，數據的組織方式要求。選項：A、數據分成若干塊，每塊內元素有序B、數據分成若干塊，每塊內元素不必有序，但塊間必須有序，且每塊內最大（或最小）的數據組成索引塊；C、數據分成若干塊D、數據分成若干塊，每塊（除最后一塊外）中元素個數相等。正確答案:【數據分成若干塊，每塊內元素不必有序，但塊間必須有序，且每塊內最大（或最小）的數據組成索引塊；】3、問題：有一個有序表{1,3,9,12,32,41，45,62,75,77,82,95,99}當采用折半查找法查找關鍵字為82的元素時，需經過次比較后查找成功。選項：A、1B、2C、4D、8正確答案:【4】4、問題：折半查找可以在有序的雙向鏈表上進行。（）選項：A、正確B、錯誤正確答案:【錯誤】第3講隨堂測驗1、問題：如圖所示的二叉排序樹，，起查找成功時的平均查找長度是。選項：A、B、C、D、正確答案:【】2、問題：在一棵平衡二叉樹中，每個結點的平衡因子的取值范圍是。選項：A、-1——1B、-2——2C、1——2D、0——1正確答案:【-1——1】3、問題：查找效率最高的二叉排序樹