【MOOC】數(shù)據(jù)結(jié)構(gòu)-西北大學(xué) 中國大學(xué)慕課MOOC答案

【MOOC】數(shù)據(jù)結(jié)構(gòu)-西北大學(xué)中國大學(xué)慕課MOOC答案數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)概念隨堂測驗(yàn)1、【單選題】一個(gè)抽象類型包括數(shù)據(jù)對象、和一組處理數(shù)據(jù)的操作。本題答案：【數(shù)據(jù)對象中各元素間的結(jié)構(gòu)關(guān)系】2、【填空題】抽象數(shù)據(jù)類型具有、信息隱蔽的特點(diǎn)。本題答案：【數(shù)據(jù)抽象】第2講數(shù)據(jù)結(jié)構(gòu)的內(nèi)容隨堂測驗(yàn)1、【判斷題】線性結(jié)構(gòu)只能用順序結(jié)構(gòu)來存放，非線性結(jié)構(gòu)只能用非順序結(jié)構(gòu)來存放。（）本題答案：【錯(cuò)誤】2、【填空題】1、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)分為集合、線性、層次和四種。本題答案：【網(wǎng)狀】3、【填空題】2、數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)分為和非順序兩種。本題答案：【順序】4、【填空題】3、在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖結(jié)構(gòu)中，數(shù)據(jù)元素之間分別存在著一對一、一對多和聯(lián)系。本題答案：【多對多】第3講數(shù)據(jù)結(jié)構(gòu)與C語言表示隨堂測驗(yàn)1、【單選題】當(dāng)需要用一個(gè)形式參數(shù)直接改變對應(yīng)實(shí)參的值時(shí)，該形式參數(shù)應(yīng)說明為。本題答案：【與實(shí)參同類型指針參數(shù)】第4講算法性能評價(jià)隨堂測驗(yàn)1、【單選題】1、執(zhí)行下面的程序段的時(shí)間復(fù)雜度為。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;本題答案：【O(m*n)】2、【單選題】2、執(zhí)行下面程序段時(shí)，語句S的執(zhí)行次數(shù)為。for(inti=0;i=n;i++)for(intj=0;ji;j++)S;本題答案：【】第5講算法與算法描述隨堂測驗(yàn)1、【單選題】算法設(shè)計(jì)的要求是：正確性、可讀性、和高效率和低存儲。本題答案：【健壯性】2、【單選題】算法具有有限性、確定性、、輸入、輸出五大特性。本題答案：【可行性】第一章單元測試1、【單選題】下面程序段的時(shí)間復(fù)雜度為（）。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;本題答案：【O(m*n)】2、【單選題】執(zhí)行下面程序段時(shí)，語句S的執(zhí)行次數(shù)為（）。for(inti=0;i=n;i++)for(intj=0;j=i;j++)S;本題答案：【(n+1)*(n+2)/2】3、【單選題】評價(jià)一個(gè)算法性能好壞的最重要標(biāo)準(zhǔn)是（）。本題答案：【算法的時(shí)間復(fù)雜度和空間復(fù)雜度】4、【單選題】算法的時(shí)間復(fù)雜度與（）有關(guān)。本題答案：【問題規(guī)模】5、【單選題】算法分析的主要任務(wù)是分析（）。本題答案：【算法的執(zhí)行時(shí)間與所需空間與問題規(guī)模的關(guān)系】6、【單選題】算法分析的目的是()。本題答案：【分析算法的時(shí)空效率以求改進(jìn)】7、【單選題】數(shù)據(jù)的最小單位是（）。本題答案：【數(shù)據(jù)項(xiàng)】8、【單選題】某算法的時(shí)間復(fù)雜度是O（n*n）,表明該算法的（）。本題答案：【執(zhí)行時(shí)間與n*n正比】9、【單選題】如下程序段:for(i=1;i=n-1;i++)for(j=i+1;j=n;j++)x=x+1;其中語句x=x+1執(zhí)行的語句頻度為（）。本題答案：【n*(n-1)/2】10、【單選題】以下算法的時(shí)間復(fù)雜度為（）。if(n=0){for(inti=0;in;i++)for(intj=0;jn;j++)printf(輸入數(shù)據(jù)大于等于零\n);}else{for(intj=0;jn;j++)printf(輸入數(shù)據(jù)小于零\n);}本題答案：【O(n*n)】11、【單選題】在數(shù)組A[0..n-1]中查找給定值K的算法大致如下：i=n-1;while(i=0(A[i]!=k))i--;returni;該算法的時(shí)間復(fù)雜度為（）。本題答案：【O(n)】12、【單選題】下面算法的時(shí)間復(fù)雜度為（）。x=100;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;本題答案：【O(1)】13、【單選題】假設(shè)sqrt(n)函數(shù)中涉及的算法時(shí)間復(fù)雜度為O(1)，那么下面的算法是判斷n是否為素?cái)?shù)，其時(shí)間復(fù)雜度為（）。voidprime(intn){for(i=2;isqrt(n)(n%i)!=0;i++);if(isqrt(n))printf(%disaprimenumber,n);elseprintf(%disnotaprimenumber,n);}本題答案：【O(sqrt(n))sqrt表示對n取根方】14、【單選題】某算法中，執(zhí)行頻率最高的語句的執(zhí)行次數(shù)為則該算法的時(shí)間復(fù)雜度應(yīng)該是（）。本題答案：【T(n)=O(n*n)】15、【單選題】數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)處理的最小單位是（）。本題答案：【數(shù)據(jù)元素】16、【多選題】以下屬于數(shù)據(jù)元素間基本邏輯結(jié)構(gòu)的是（）。本題答案：【集合#線性#樹#圖】17、【多選題】以下屬于算法特性的是（）。本題答案：【0個(gè)或多個(gè)輸入；至少1個(gè)輸出#確定性#可行性和有限性】18、【多選題】算法設(shè)計(jì)的要求包括（）。本題答案：【正確性#可讀性#健壯性#高效率和低存儲】19、【多選題】數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)存中的存儲映像包括（）。本題答案：【順序存儲#非順序存儲】20、【多選題】抽象數(shù)據(jù)類型包括了（）。本題答案：【一個(gè)數(shù)據(jù)對象#元素間的關(guān)系#一組操作】21、【判斷題】具有線性結(jié)構(gòu)的元素只能用順序存儲，具有非線性結(jié)構(gòu)的元素只能非順序存儲。本題答案：【錯(cuò)誤】22、【判斷題】算法就是程序。本題答案：【錯(cuò)誤】23、【判斷題】算法的優(yōu)劣與算法描述的語言無關(guān)。本題答案：【正確】24、【判斷題】算法的可行性是指每一條指令具有明確含義。本題答案：【錯(cuò)誤】25、【判斷題】健壯的算法不會因?yàn)榉欠ㄝ斎霐?shù)據(jù)而出現(xiàn)莫名其妙的執(zhí)行結(jié)果。本題答案：【正確】26、【判斷題】算法設(shè)計(jì)的要求就是要設(shè)計(jì)高效率和低存儲的算法。本題答案：【錯(cuò)誤】27、【判斷題】數(shù)據(jù)類型就是變量。本題答案：【錯(cuò)誤】28、【判斷題】數(shù)據(jù)元素的存儲結(jié)構(gòu)分為順序存儲和非順序存儲。本題答案：【正確】29、【判斷題】數(shù)據(jù)元素的順序存儲結(jié)構(gòu)優(yōu)于非順序存儲。本題答案：【錯(cuò)誤】30、【判斷題】元素間的邏輯關(guān)系可分為線性和非線性關(guān)系兩種。本題答案：【錯(cuò)誤】第1講線性表的概念隨堂測驗(yàn)1、【單選題】線性表是具有n個(gè)（）的有限序列（n0）本題答案：【數(shù)據(jù)元素】2、【單選題】線性表是一個(gè)（）。本題答案：【有限序列，可以為空】3、【判斷題】線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（）本題答案：【錯(cuò)誤】第2講線性表的順序存儲隨堂測驗(yàn)1、【單選題】若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（）(1=i=n+1)。本題答案：【O(n)】2、【單選題】若長度為n的線性表采用順序存儲結(jié)構(gòu)，刪除第i個(gè)位置的元素，需要移動的元素個(gè)數(shù)為（）。本題答案：【n-i】第3講隨堂測驗(yàn)1、【單選題】對一個(gè)長度為n的順序表，假設(shè)在任何位置上插入一個(gè)元素的概率是相等的，那么插入一個(gè)元素時(shí)要移動表中的（）個(gè)元素。本題答案：【】2、【判斷題】線性表的順序存儲是指將表中元素按照從大到小或從小到大存儲。本題答案：【錯(cuò)誤】第4講線性表的鏈?zhǔn)酱鎯﹄S堂測驗(yàn)1、【單選題】通過表達(dá)式可以獲取帶頭結(jié)點(diǎn)的單鏈表L中首元素結(jié)點(diǎn)的數(shù)據(jù)值。本題答案：【(L-next)-data】2、【判斷題】單鏈表中必須設(shè)有頭結(jié)點(diǎn)。（）本題答案：【錯(cuò)誤】第5講單鏈表的基本運(yùn)算隨堂測驗(yàn)1、【單選題】下列選項(xiàng)中，項(xiàng)是鏈表不具有的特點(diǎn)。本題答案：【可以隨機(jī)訪問表中的任意元素】2、【單選題】有一個(gè)帶頭結(jié)點(diǎn)的單鏈表HEAD，則判斷其是否為空鏈表的表達(dá)式是本題答案：【HEAD-〉NEXT==NULL】3、【單選題】在一個(gè)單鏈表中P所指結(jié)點(diǎn)后插入一個(gè)S所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行語句：。本題答案：【S-next=P-next;P-next=S;】第6講隨堂測驗(yàn)1、【單選題】設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A的直接前驅(qū)，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。本題答案：【q=p-next；p-next=q-next；free(q)；】2、【判斷題】對鏈表進(jìn)行插入和刪除操作時(shí)不必移動鏈表中結(jié)點(diǎn)。()本題答案：【正確】3、【判斷題】在單鏈表中，可以從頭結(jié)點(diǎn)出發(fā)，查找到表中所有結(jié)點(diǎn)。（）本題答案：【正確】第二章單元測試（1）1、【單選題】在長度為n的順序表中的第i(1=i=n+1)個(gè)位置上插入一個(gè)元素，其算法時(shí)間復(fù)雜度為（）。本題答案：【O(n)】2、【單選題】在長度為n的順序表中的第i(1=i=n+1)個(gè)位置上插入一個(gè)元素，需要移動的元素個(gè)數(shù)為（）。本題答案：【n-i+1】3、【單選題】鏈表不具有的特點(diǎn)是（）。本題答案：【可隨機(jī)訪問任一元素】4、【單選題】在一單鏈表中，刪除指針p所指的后繼結(jié)點(diǎn)，以下語句正確的是（）。本題答案：【s=p-next;p-next=s-next;free(s);】5、【單選題】假設(shè)刪除長度為n的順序表中的每個(gè)元素的概率相同，則刪除一個(gè)元素平均要移動的元素個(gè)數(shù)是（）。本題答案：【(n-1)/2】6、【單選題】設(shè)某順序表中第一個(gè)元素的地址是Base，每個(gè)結(jié)點(diǎn)占m個(gè)單元，則第i個(gè)結(jié)點(diǎn)的地址為（）。本題答案：【Base+(i-1)×m】7、【單選題】長度為n的非空線性表采用順序存儲結(jié)構(gòu)，在表的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該是（）。本題答案：【1≤i≤n+1】8、【單選題】非空單鏈表結(jié)點(diǎn)結(jié)構(gòu)為【data,next】，若指針p所指結(jié)點(diǎn)是尾結(jié)點(diǎn)，則（）表達(dá)式為真。本題答案：【p-next==NULL】9、【單選題】某順序表的第一個(gè)元素的存儲地址是500，每個(gè)元素占4個(gè)單元，則第8個(gè)元素的起始地址是()。本題答案：【528】10、【單選題】在長度為n的順序表中刪除第i(1=i=n)個(gè)位置上的元素，需要移動的元素個(gè)數(shù)為（）。本題答案：【n-i】11、【單選題】在長度為n的順序表中的的末尾位置上插入一個(gè)元素，其算法時(shí)間復(fù)雜度為（）。本題答案：【O(1)】12、【單選題】以下算法的功能是在一個(gè)非遞減的順序存儲線性表中，刪除所有值相等的多余元素。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。劃線部分應(yīng)填入的語句是（）。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;}本題答案：【j++】13、【單選題】以下算法是刪除帶頭結(jié)點(diǎn)單鏈表L中的最小的元素，橫線處應(yīng)填入的語句是（）。voidDelMinNode(LinkListL){p=L-next;pre=L;if(L==NULL)return;while(p-next!=NULL)//pre指向最小元素的前驅(qū)元素，開始默認(rèn)第一個(gè)結(jié)點(diǎn)最小，pre指向頭結(jié)點(diǎn){if(p-next-datapre-next-data)pre=p;}//刪除pre后面的結(jié)點(diǎn)p=pre-next;;}本題答案：【pre-next=p-next;free(p);】14、【判斷題】單鏈表中增加頭結(jié)點(diǎn)的目的是存儲鏈表的長度。本題答案：【錯(cuò)誤】15、【判斷題】線性表在鏈?zhǔn)酱鎯r(shí)，查找第i個(gè)元素的時(shí)間同i的值無關(guān)。本題答案：【錯(cuò)誤】16、【判斷題】線性表在順序存儲時(shí)，查找第i個(gè)元素的時(shí)間同i的值成正比。本題答案：【錯(cuò)誤】17、【判斷題】線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。本題答案：【錯(cuò)誤】18、【判斷題】線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲。本題答案：【錯(cuò)誤】19、【判斷題】順序存儲方式的優(yōu)點(diǎn)是存儲密度大，插入、刪除效率高。本題答案：【錯(cuò)誤】20、【判斷題】順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)基本類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)構(gòu)造類型。本題答案：【錯(cuò)誤】21、【判斷題】插入和刪除操作是線性表的基本操作。這兩種操作在數(shù)組中也經(jīng)常使用。本題答案：【錯(cuò)誤】22、【判斷題】在順序表中，邏輯上相鄰的兩個(gè)元素物理存儲上也一定也相鄰。本題答案：【正確】23、【判斷題】在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理存儲上并不一定緊鄰。本題答案：【正確】24、【判斷題】線性表采用順序存儲，必須占用一段地址連續(xù)的存儲單元。本題答案：【正確】25、【判斷題】順序表結(jié)構(gòu)適宜進(jìn)行隨機(jī)訪問，而鏈表適宜進(jìn)行插入、刪除。本題答案：【正確】第7講循環(huán)鏈表隨堂測驗(yàn)1、【單選題】有一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表HEAD，則判斷其是否為空鏈表的條件是。本題答案：【HEAD-〉NEXT==HEAD】2、【判斷題】在單向循環(huán)鏈表中，從表中任意結(jié)點(diǎn)出發(fā)都可以順著next域訪問到表中所有元素（）本題答案：【正確】第8講雙向鏈表--隨堂測驗(yàn)1、【單選題】與單鏈表相比，雙向鏈表的優(yōu)點(diǎn)之一是。本題答案：【訪問前后相鄰結(jié)點(diǎn)更方便?！?、【判斷題】在雙向鏈表L中，可以從任一結(jié)點(diǎn)p出發(fā)沿同一方向的指針域查找到表中所有元素。（）本題答案：【錯(cuò)誤】第9講靜態(tài)鏈表--隨堂測驗(yàn)1、【判斷題】靜態(tài)鏈表中與動態(tài)鏈表的插入和刪除運(yùn)算類似，不需要做元素的移動。（）本題答案：【正確】2、【判斷題】靜態(tài)鏈表既有順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)，又有動態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第ｉ個(gè)元素的時(shí)間與位置序號ｉ無關(guān)，可以實(shí)現(xiàn)隨機(jī)存取。（）本題答案：【錯(cuò)誤】第10講鏈?zhǔn)浇Y(jié)構(gòu)小結(jié)--隨堂檢測1、【單選題】已知單鏈表的頭指針為head且該鏈表不帶頭結(jié)點(diǎn)，則該單鏈表為空的條件是。本題答案：【head==NULL】2、【單選題】設(shè)指針變量p指向單鏈表中某結(jié)點(diǎn)的直接前驅(qū)，若刪除單鏈表中該結(jié)點(diǎn)，需要修改指針的操作序列為。本題答案：【q=p-next；p-next=q-next；free(q)；】3、【單選題】設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是。本題答案：【head-next==head】4、【判斷題】在雙向循環(huán)鏈表中，可以從任一結(jié)點(diǎn)p出發(fā)沿同一方向的指針域查找到表中所有元素。（）本題答案：【正確】第12講隨堂測驗(yàn)1、【單選題】下列選項(xiàng)中，項(xiàng)是鏈表不具有的特點(diǎn)。本題答案：【可以隨機(jī)訪問表中的任意元素】2、【單選題】在線性表中最常用的操作是存取第i個(gè)元素及其前趨的值，可采用存儲方式最省時(shí)間？本題答案：【順序表】3、【單選題】下面關(guān)于線性表的敘述錯(cuò)誤的是（）。本題答案：【線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)】總結(jié)與提高隨堂測驗(yàn)1、【單選題】某線性表中最常用的操作是存取序號為i的元素和在最后進(jìn)行插入和刪除運(yùn)算，則采用存儲方式時(shí)間性能最好。本題答案：【順序表】2、【單選題】已知一個(gè)帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表，其尾指針是R，則其首元素結(jié)點(diǎn)的地址為：本題答案：【R-next-next】3、【判斷題】線性表的順序存儲優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。（）本題答案：【錯(cuò)誤】4、【填空題】在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲位置由指示本題答案：【頭指針】第1講隨堂測驗(yàn)1、【單選題】棧操作的特性是（）本題答案：【LIFO】2、【單選題】棧中，允許進(jìn)行插入和刪除的一端稱為（）本題答案：【棧頂】3、【判斷題】棧是線性結(jié)構(gòu)，是操作受限制的線性表。（）本題答案：【正確】第2講隨堂測驗(yàn)1、【多選題】1、已知順序棧的地址為s,此時(shí)棧不滿且棧頂指示器top指向真實(shí)棧頂,執(zhí)行元素x進(jìn)棧操作正確的語句是（）本題答案：【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,此時(shí)棧不空且棧頂指示器top指向真實(shí)棧頂，執(zhí)行出棧操作并將出棧元素賦值給x所指向的單元，則下列語句中，正確的是（）本題答案：【*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,此時(shí)棧不空且棧頂指示器top指向真實(shí)棧頂，執(zhí)行取棧頂操作的語句是*x=s-elem[s-top--];()本題答案：【錯(cuò)誤】第3講隨堂測驗(yàn)1、【單選題】已知一個(gè)雙端棧的地址為dS，則該雙端棧不滿時(shí)，，元素x進(jìn)1號棧（高端棧）操作的語句是（）本題答案：【dS-top[1]--;dS-stack[dS-top[1]]=x;】2、【多選題】已知一個(gè)雙端棧dStack,則判斷該雙端棧棧滿的條件是（）本題答案：【dStack.top[0]+1==dStack.top[1]#dStack.top[0]==dStack.top[1]-1】3、【判斷題】已知一個(gè)雙端棧的地址為dS，則該雙端棧不空時(shí)，1號棧（高端棧）出棧操作的語句是*x=dS-stack[dS-top[1]--]（）本題答案：【錯(cuò)誤】第4講隨堂測驗(yàn)1、【單選題】已知帶頭結(jié)點(diǎn)的鏈棧top,則該鏈棧不空時(shí),出棧操作的語句是()本題答案：【*x=top-next-data;p=top-next;top-next=p-next;free(p);】2、【單選題】已知帶頭結(jié)點(diǎn)的鏈棧top,則該鏈棧為空的條件是()本題答案：【top-next==NULL】3、【單選題】已知帶頭結(jié)點(diǎn)的鏈棧top,則元素x對應(yīng)的新結(jié)點(diǎn)s進(jìn)棧操作的語句是（）本題答案：【s-next=top-next;top-next=s;】第5講棧的應(yīng)用1、【單選題】在括號匹配算法中，當(dāng)正掃描檢測的符號是右括號，此時(shí)的棧是空棧，則（）。本題答案：【此時(shí)出現(xiàn)“右括號多了”的不匹配現(xiàn)象?！?、【單選題】在算術(shù)表達(dá)式求值的算法中，若當(dāng)前正掃描的符號是運(yùn)算符s，且s的優(yōu)先級比運(yùn)算符棧棧頂元素的優(yōu)先級高，則（）本題答案：【s進(jìn)運(yùn)算符棧；】3、【填空題】在括號匹配算法中，當(dāng)正掃描的符號是左括號時(shí)，則該做左括號（）。本題答案：【進(jìn)?！康?講隨堂測驗(yàn)1、【多選題】遞歸進(jìn)層（i→i+1層）系統(tǒng)需要做三件事是（）本題答案：【保留本層參數(shù)與返回地址；#為被調(diào)用函數(shù)的局部變量分配存儲區(qū)，給下層參數(shù)賦值；#將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口?！?、【多選題】從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，遞歸退層（i←i+1層）系統(tǒng)也應(yīng)完成三件工作是（）本題答案：【保存被調(diào)函數(shù)的計(jì)算結(jié)果；#釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)，恢復(fù)上層參數(shù)；#依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)?！?、【判斷題】遞歸是指在定義自身的同時(shí)又出現(xiàn)了對自身的引用。（）本題答案：【正確】4、【填空題】系統(tǒng)需設(shè)立一個(gè)遞歸工作棧作為整個(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲區(qū)。每層遞歸所需信息構(gòu)成一個(gè)（）。本題答案：【工作記錄】第三章單元測驗(yàn)（1）1、【單選題】棧的特點(diǎn)是（）。本題答案：【先進(jìn)后出】2、【單選題】隊(duì)列的特點(diǎn)是（）。本題答案：【先進(jìn)先出】3、【單選題】棧之說以叫限定性線性表，是因?yàn)椋ǎ?。本題答案：【棧的操作位置受限制】4、【單選題】輸入序列為123，若進(jìn)棧、出棧操作可以交替進(jìn)行，則不能得到的出棧序列是（）。本題答案：【312】5、【單選題】以下會用到棧的應(yīng)用是（）。本題答案：【以上選項(xiàng)均有可能】6、【單選題】循環(huán)隊(duì)列存儲在數(shù)組A[0..m-1]中，則入隊(duì)時(shí)rear應(yīng)該變化為（）本題答案：【rear=(rear+1)modm】7、【單選題】循環(huán)隊(duì)列A[0..n-1]存放其元素值，F(xiàn)表示隊(duì)頭元素所在的位置，R表示隊(duì)尾元素的下一個(gè)位置。則當(dāng)前隊(duì)列中的元素?cái)?shù)是()。本題答案：【(R-F+n)%n】8、【單選題】棧和隊(duì)列的共同點(diǎn)是（）。本題答案：【只允許在端點(diǎn)處插入和刪除元素】9、【單選題】當(dāng)利用大小為n的數(shù)組(下標(biāo)從1到n)順序存儲一個(gè)棧時(shí)，假定用top==n表示?？?，則每次向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行（）語句修改top指針。本題答案：【top--;】10、【單選題】設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進(jìn)入棧S。如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序?yàn)閎,d,e,f,c,a,g，則棧S的容量至少是（)。本題答案：【3】11、【單選題】以下屬于遞歸求解問題的前提條件的是（）。本題答案：【其他選項(xiàng)均是】12、【單選題】以下屬于消除遞歸的主要原因是（）。本題答案：【遞歸程序時(shí)空效率較差】13、【單選題】一個(gè)棧的輸入序列為123……n，若輸出序列的第一個(gè)元素是n，輸出第i（1=i=n）個(gè)元素是（）本題答案：【n-i+1】14、【單選題】凡是元素的保存次序與使用順序相反的，都可以使用（）。本題答案：【?！?5、【單選題】若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間S[1~N]，top[i]代表第i個(gè)棧(i=1,2)棧頂。棧1的底在S[1]，棧2的底在S[N]，則棧滿的條件是（）。本題答案：【top[1]+1==top[2]】16、【判斷題】消除遞歸肯定要用到棧，否則無法完成。本題答案：【錯(cuò)誤】17、【判斷題】若輸入序列為1234,則通過一個(gè)?？梢缘玫捷敵鲂蛄?124。本題答案：【錯(cuò)誤】18、【判斷題】若輸入序列為1234,則通過棧只能得到4321的輸出序列。本題答案：【錯(cuò)誤】19、【判斷題】有些問題，比如漢諾塔問題等，只能用遞歸來解，無法轉(zhuǎn)換成非遞歸算法。本題答案：【錯(cuò)誤】20、【判斷題】順序棧因?yàn)槭琼樞虼鎯?，所以可以隨機(jī)存取棧中任意元素。本題答案：【錯(cuò)誤】21、【判斷題】兩順序棧共享空間，也存在空間溢出問題。本題答案：【正確】22、【判斷題】棧和隊(duì)列都是限制插入和刪除位置的線性結(jié)構(gòu)。本題答案：【正確】23、【判斷題】函數(shù)或過程調(diào)用需要用到棧。本題答案：【正確】第7講隨堂測驗(yàn)1、【多選題】遞歸算法具有兩個(gè)特性分別是（）本題答案：【遞歸算法求解問題，方法簡單。#遞歸算法的效率較低】2、【多選題】下列可以直接用循環(huán)結(jié)構(gòu)即可將遞歸轉(zhuǎn)換為非遞歸的是（）本題答案：【斐波那契數(shù)列問題#N!問題#尾遞歸問題】第8講隨堂測驗(yàn)1、【單選題】已知帶頭結(jié)點(diǎn)的鏈隊(duì)列指針Q，則該隊(duì)列做新元素結(jié)點(diǎn)s進(jìn)隊(duì)操作的語句是（）本題答案：【Q-rear-next=s;Q-rear=s;】2、【單選題】已知帶頭結(jié)點(diǎn)的鏈隊(duì)列指針Q，則該非空隊(duì)列取隊(duì)頭元素操作的語句是（）本題答案：【*x=Q-front-next-data;】3、【判斷題】隊(duì)列操作的特性是LIFO。（）本題答案：【錯(cuò)誤】4、【判斷題】隊(duì)列允許做插入的一端稱為隊(duì)頭，允許刪除的一端稱為隊(duì)尾（）本題答案：【錯(cuò)誤】第9講隨堂測驗(yàn)1、【單選題】已知循環(huán)隊(duì)列Q-element[MAXSIZE],隊(duì)頭指示器為Q-front，隊(duì)尾指示器為Q-rear（指向真實(shí)隊(duì)尾的下一個(gè)位置），則該隊(duì)列中元素個(gè)數(shù)為：（）本題答案：【（Q-rear-Q-front+MAXSIZE）%MAXSIZE】2、【單選題】已知循環(huán)隊(duì)列Q-element[MAXSIZE],隊(duì)頭指示器為Q-front，隊(duì)尾指示器為Q-rear（指向真實(shí)隊(duì)尾的下一個(gè)位置），則該隊(duì)列為空隊(duì)列的條件為（）本題答案：【Q-rear==Q-front】3、【單選題】已知循環(huán)隊(duì)列Q-element[MAXSIZE],隊(duì)頭指示器為Q-front，隊(duì)尾指示器為Q-rear（指向真實(shí)隊(duì)尾的下一個(gè)位置），則該隊(duì)列為滿隊(duì)列的條件為（）（采用少用一個(gè)空間的方法）本題答案：【（Q-rear+1）%MAXSIZE==Q-front】第10講隨堂測驗(yàn)1、【判斷題】在打印楊輝三角形前N行的算法中，需要申請一個(gè)N*N的二維數(shù)組存放楊輝三角形N行數(shù)據(jù)。（）本題答案：【錯(cuò)誤】第三章單元測驗(yàn)（2）1、【單選題】隊(duì)列對數(shù)據(jù)的操作順序是（）。本題答案：【先進(jìn)先出】2、【單選題】設(shè)rear是非空循環(huán)單鏈表的尾指針，則刪除表中第一個(gè)元素結(jié)點(diǎn)的操作可表示為（）（該鏈表不帶頭結(jié)點(diǎn)）。本題答案：【p=rear-next;rear-next=p-next;free(p);】3、【單選題】設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進(jìn)入棧S（進(jìn)棧和出?？山惶孢M(jìn)行）。如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序?yàn)閎,d,e,f,c,a,g，則棧S的容量至少是（）。本題答案：【3】4、【單選題】以下應(yīng)用可能會用到棧的是（）。本題答案：【其余三個(gè)答案均正確】5、【單選題】一個(gè)隊(duì)列的元素入隊(duì)順序是1,2,3,4，則出隊(duì)順序?yàn)椋ǎ?。本題答案：【1,2,3,4】6、【單選題】某循環(huán)隊(duì)列用數(shù)組A[0..n-1]表示，指示器為front指向隊(duì)頭元素，指示器rear指向隊(duì)尾后的空單元。則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。本題答案：【(rear-front+n)%n】7、【單選題】以下函數(shù)的功能是（）。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);}}本題答案：【將隊(duì)列Q中的元素逆置?！?、【判斷題】棧和隊(duì)列都是限制存取位置的線性結(jié)構(gòu)。本題答案：【正確】9、【判斷題】循環(huán)隊(duì)列用數(shù)組A[0..n-1]表示，則入隊(duì)時(shí)的隊(duì)尾指針變換語句為：rear=(rear+1)%n;本題答案：【正確】10、【判斷題】一般的緩沖區(qū)用隊(duì)列做為數(shù)據(jù)結(jié)構(gòu)。本題答案：【正確】11、【判斷題】循環(huán)隊(duì)列因?yàn)槭琼樞虼鎯?，因此可以隨機(jī)存取。本題答案：【錯(cuò)誤】12、【判斷題】判斷表達(dá)式中的括號是否匹配，采用隊(duì)列數(shù)據(jù)結(jié)構(gòu)最佳。本題答案：【錯(cuò)誤】第1講隨堂測驗(yàn)1、【單選題】設(shè)s=‘a(chǎn)bcd’,s1=‘123’，則執(zhí)行語句StrInsert(s,2,s1)后，s=.本題答案：【‘a(chǎn)123bcd’】2、【單選題】設(shè)s=‘a(chǎn)bcd’，則執(zhí)行語句StrDelete(s,2,2)后，s=.本題答案：【‘a(chǎn)d’】第2講隨堂測驗(yàn)1、【填空題】假設(shè)主串S=‘a(chǎn)aabbbababaabb’,模式串T=‘a(chǎn)baa’,用串匹配算法從主串的第6個(gè)字符開始模式匹配，需要做趟匹配，方能找到匹配串。本題答案：【4】2、【填空題】假設(shè)主串S=‘a(chǎn)aabbbababaabb’,模式串T=‘a(chǎn)baa’,用串匹配算法從主串的第6個(gè)字符開始模式匹配，在第2趟匹配中，要做次比較。本題答案：【4】第3講隨堂測驗(yàn)1、【單選題】用帶頭結(jié)點(diǎn)的單鏈表來表示串s,則串s為空串的條件是（）本題答案：【s-next==NULL】隨堂測驗(yàn)1、【單選題】假設(shè)有6行8列的二維數(shù)組A(下標(biāo)從1開始),每個(gè)元素占用6個(gè)字節(jié),存儲器按字節(jié)編址。已知A的基地址為1000,計(jì)算按行存儲時(shí)元素A36的地址是;本題答案：【1126】2、【單選題】假設(shè)有6行8列的二維數(shù)組A(下標(biāo)從1開始),每個(gè)元素占用6個(gè)字節(jié),存儲器按字節(jié)編址。已知A的基地址為1000,計(jì)算按列存儲時(shí)元素A36的地址是;本題答案：【1192】隨堂測驗(yàn)1、【單選題】已知一個(gè)n行n列的三對角帶狀矩陣A，其中非零元素的個(gè)數(shù)是（）。本題答案：【3n-2】2、【單選題】若將n階上三角矩陣A按列優(yōu)先壓縮存放在一維數(shù)組B中，第一個(gè)非零元素存放在B[0]中，則非零元素aij存放在B[k]中，則k=()。本題答案：【】第3講隨堂測驗(yàn)1、【單選題】對稀疏矩陣進(jìn)行壓縮存儲的目的是（）本題答案：【節(jié)省存儲空間】2、【單選題】稀疏矩陣壓縮存儲后，不會失去（）功能輸入輸出本題答案：【隨機(jī)存取】第4講隨堂測驗(yàn)1、【填空題】對于一個(gè)m行n列的稀疏矩陣中有l(wèi)en個(gè)非零元素，則用十字鏈表存儲時(shí)，需要（）個(gè)頭指針。本題答案：【m+n】2、【填空題】對于一個(gè)m行n列的稀疏矩陣中有l(wèi)en個(gè)非零元素，則用十字鏈表存儲時(shí)，需要（）個(gè)三元組結(jié)點(diǎn)。本題答案：【len】第5講隨堂測驗(yàn)1、【判斷題】任意一個(gè)廣義表都可以表示為由表頭和表尾構(gòu)成（）。本題答案：【錯(cuò)誤】2、【判斷題】非空的廣義表的表尾可能是單個(gè)元素也可能是表元素（）。本題答案：【錯(cuò)誤】3、【填空題】已知廣義表L=((x,y,z),a,(u,t,w)),則head(head(tail(tail(L))))的結(jié)果是（）。本題答案：【u】4、【填空題】已知數(shù)組M[1..10,-1..6,0..3],)若數(shù)組以行序?yàn)橹餍虼鎯?起始地址為1000,且每個(gè)數(shù)據(jù)元素占用3個(gè)存儲單元,則M[2,4,2]的地址為（）本題答案：【1162】第1講隨堂測驗(yàn)1、【單選題】樹最適合用來表示（）本題答案：【元素之間具有分支層次關(guān)系的數(shù)據(jù)】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）））該樹中葉子結(jié)點(diǎn)的個(gè)數(shù)為：（）本題答案：【8】第2講隨堂測驗(yàn)1、【單選題】按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種本題答案：【5】2、【單選題】若一棵二叉樹有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)有（）個(gè)。本題答案：【11】3、【單選題】一個(gè)高度為h的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)本題答案：【】4、【判斷題】二叉樹就是結(jié)點(diǎn)度不大于2的樹。（）本題答案：【錯(cuò)誤】5、【判斷題】不存在這樣的二叉樹：它有n個(gè)度為0的結(jié)點(diǎn)，n-1個(gè)度為1的結(jié)點(diǎn)，n-2個(gè)度為2的結(jié)點(diǎn)。（）本題答案：【正確】6、【填空題】具有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲結(jié)構(gòu)，共有（）非空的指針域。本題答案：【n-1】7、【填空題】擁有100個(gè)結(jié)點(diǎn)的完全二叉樹的最大層數(shù)是（）本題答案：【7】第3講隨堂測驗(yàn)1、【單選題】某二叉樹的先序序列和中序序列正好相同，則該二叉樹一定是（）本題答案：【每個(gè)結(jié)點(diǎn)都沒有左子】2、【單選題】在二叉樹中，p所指向的結(jié)點(diǎn)為度為1的分支點(diǎn)的條件是（）本題答案：【(p-lchild==NULLp-rchild!=NULL)||(p-lchild!=NULLp-rchild==NULL)】3、【判斷題】已知二叉樹的先序和后序遍歷序列可以唯一確定該二叉樹。（）本題答案：【錯(cuò)誤】第六章單元測驗(yàn)11、【單選題】已知一算術(shù)表達(dá)式的中綴形式為A-B/C+D*E，前綴形式為+-A/BC*DE，其后綴形式為()。本題答案：【ABC/-DE*+】2、【單選題】有關(guān)二叉樹下列說法正確的是（）。本題答案：【一棵二叉樹的度可以小于2】3、【單選題】在一棵高度為k的滿二叉樹中，結(jié)點(diǎn)總數(shù)為（）。本題答案：【-1】4、【單選題】某二叉樹中有60個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為（）。本題答案：【59】5、【單選題】100個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲，從1開始按層次編號，則編號最小的葉子結(jié)點(diǎn)的編號應(yīng)該是（）。本題答案：【51】6、【單選題】高度為7的完全二叉樹，最少有（）個(gè)結(jié)點(diǎn)。本題答案：【64】7、【單選題】高度為7的二叉樹，最少有（）個(gè)結(jié)點(diǎn)。本題答案：【7】8、【單選題】對任意一棵有n個(gè)結(jié)點(diǎn)的樹，這n個(gè)結(jié)點(diǎn)的度之和為()。本題答案：【n-1】9、【判斷題】完全二叉樹一定存在度為1的結(jié)點(diǎn)。本題答案：【錯(cuò)誤】10、【判斷題】完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是葉子。本題答案：【正確】11、【判斷題】二叉樹只能用二叉鏈表表示。本題答案：【錯(cuò)誤】12、【判斷題】樹形結(jié)構(gòu)中，每個(gè)元素都有一個(gè)前驅(qū)，0個(gè)或多個(gè)后繼。本題答案：【錯(cuò)誤】第4講隨堂檢測1、【單選題】設(shè)二叉樹采用二叉鏈表方式存儲，root指向根結(jié)點(diǎn)，r所指結(jié)點(diǎn)為二叉樹中任一給定的結(jié)點(diǎn)。則可以通過改寫（）算法，求出從根結(jié)點(diǎn)到結(jié)點(diǎn)r之間的路徑。本題答案：【后序遍歷】2、【多選題】已知二叉樹用二叉鏈表存儲，則若實(shí)現(xiàn)二叉樹實(shí)現(xiàn)左右子樹交換，可以借助改寫（）遍歷算法實(shí)現(xiàn)。本題答案：【先序遍歷#后序遍歷】第5講隨堂測驗(yàn)1、【單選題】在中序遍歷非遞歸算法中，在進(jìn)入子樹進(jìn)行訪問前，需要在自定義棧中保存（）本題答案：【本層根結(jié)點(diǎn)指針】第6講隨堂測驗(yàn)1、【單選題】引入線索二叉樹的目的是()本題答案：【加快查找指定遍歷過程中結(jié)點(diǎn)的直接前驅(qū)和直接后繼】2、【單選題】若判斷線索二叉樹中的p結(jié)點(diǎn)有右孩子結(jié)點(diǎn)則下列（）表達(dá)式為真。本題答案：【p-rtag==0】3、【單選題】若線索二叉樹中的p結(jié)點(diǎn)沒有左孩子結(jié)點(diǎn)則下列（）表達(dá)式為真。本題答案：【p-ltag==1】第7講隨堂測驗(yàn)1、【單選題】一棵二叉樹的后序序列是：CBEFDA,中序序列是：CBAEDF,則該二叉樹的先序序列是（）本題答案：【ABCDEF】2、【單選題】一棵二叉樹的先序序列是：CEDBA,中序序列是：DEBAC,則該二叉樹的后序序列是（）本題答案：【DABEC】第8講隨堂測驗(yàn)1、【單選題】如圖所示的二叉樹BT是由森林T1轉(zhuǎn)換而來的二叉樹，那么森林T1中有（）葉子結(jié)點(diǎn)。本題答案：【6】2、【填空題】與樹等價(jià)的二叉樹，根沒有（）子樹。本題答案：【右】第9講隨堂測驗(yàn)1、【單選題】有13個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，該樹中結(jié)點(diǎn)總數(shù)為（）本題答案：【25】2、【判斷題】在哈夫曼樹中，權(quán)值相同的葉子點(diǎn)一定在同一層上。（）本題答案：【錯(cuò)誤】3、【判斷題】在哈夫曼樹中，權(quán)值較大的葉子點(diǎn)一般離根比較近。（）本題答案：【正確】4、【填空題】若以{4,5,6,7,8}作為葉子點(diǎn)構(gòu)造哈夫曼樹，則其帶全路徑長度為（）本題答案：【69】第10講隨堂測驗(yàn)1、【判斷題】在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相等時(shí)，則兩個(gè)字符的哈夫曼編碼也相同。（）本題答案：【錯(cuò)誤】第六章單元測驗(yàn)21、【單選題】已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié)果為（）。本題答案：【CBEFDA】2、【單選題】線索二叉樹中，判斷p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是（）。本題答案：【p-LTag==0p-RTag==0】3、【單選題】以下屬于前綴編碼的是（）。本題答案：【{0,1101,1110,1100,1111}】4、【單選題】在下列存儲形式中，（）不是樹的存儲形式。本題答案：【順序存儲表示法】5、【單選題】對二叉樹中的結(jié)點(diǎn)進(jìn)行編號，要求根結(jié)點(diǎn)的編號最小，左孩子結(jié)點(diǎn)編號比右孩子結(jié)點(diǎn)編號小。則應(yīng)該采用（）遍歷方法對其進(jìn)行編號。本題答案：【先序】6、【單選題】已知某二叉樹的后序遍歷序列是CEFDBA，中序遍歷序列是CBEDFA。與該二叉樹對應(yīng)的樹或森林中，葉子的數(shù)目是（）個(gè)。本題答案：【3】7、【單選題】某二叉樹中有60個(gè)葉子結(jié)點(diǎn)，則該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為（）。本題答案：【59】8、【單選題】某二叉樹的邏輯結(jié)構(gòu)如下圖所示，則其擴(kuò)展先序序列為（）。H、（I、表示空）J、ABK、DFN、CO、E（P、表示空）Q、ABDFCER、ABCDEF本題答案：【AB#DF###C#E##（#表示空）】9、【單選題】樹的后根遍歷，相當(dāng)于對應(yīng)二叉樹的（）遍歷。本題答案：【中序】10、【判斷題】哈夫曼樹的帶權(quán)路徑長度等于其中所有結(jié)點(diǎn)的帶權(quán)路徑之和。本題答案：【錯(cuò)誤】11、【判斷題】給定二叉樹的先序、中序和后序遍歷序列中的任意兩個(gè)，就可以唯一確定一棵二叉樹。本題答案：【錯(cuò)誤】12、【判斷題】在葉子數(shù)目和權(quán)值相同的所有二叉樹中，帶權(quán)路徑長度最小的樹一定是哈夫曼樹。本題答案：【正確】13、【判斷題】將一棵樹轉(zhuǎn)成二叉樹，根結(jié)點(diǎn)一定沒有右子樹。本題答案：【正確】14、【填空題】有10個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，總結(jié)點(diǎn)個(gè)數(shù)是。本題答案：【19】15、【填空題】將一棵樹轉(zhuǎn)換為二叉樹時(shí)，遵循的規(guī)則是左孩子、。本題答案：【右兄弟】16、【填空題】用權(quán)值{1,2,3,4,5}構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長度為。本題答案：【33】17、【填空題】假設(shè)T是一棵高度為5的二叉樹,T中只有度為0和度為2的結(jié)點(diǎn)，那么T樹最少應(yīng)該有個(gè)結(jié)點(diǎn)。本題答案：【9】第1講隨堂測驗(yàn)1、【單選題】一個(gè)有n個(gè)頂點(diǎn)的有向圖最多有邊本題答案：【n(n-1)】2、【單選題】具有n個(gè)頂點(diǎn)的有向圖至少應(yīng)有弧才能確保是一個(gè)強(qiáng)連通圖。本題答案：【n】3、【填空題】在一個(gè)無向圖中，所有頂點(diǎn)的度之和等于邊條數(shù)的倍。本題答案：【2】4、【填空題】具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有條邊才能確保是一個(gè)連通圖。本題答案：【5】5、【填空題】一個(gè)有向圖G中所有頂點(diǎn)的入度之和是所有頂點(diǎn)出度之和的倍。本題答案：【1】第2講隨堂測驗(yàn)1、【單選題】對于一個(gè)n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）本題答案：【】2、【判斷題】有向圖的鄰接矩陣一定是對稱矩陣。（）本題答案：【錯(cuò)誤】3、【判斷題】用鄰接矩陣存儲無向圖G時(shí)，其第i行中1的個(gè)數(shù)與第i列中1的個(gè)數(shù)相等。（）本題答案：【正確】4、【填空題】對于一個(gè)有n個(gè)頂點(diǎn)，e條邊的無向圖，若采用鄰接表表示，則表頭結(jié)點(diǎn)數(shù)組的大小為。本題答案：【n】5、【填空題】對于一個(gè)有n個(gè)頂點(diǎn)，e條邊的無向圖，若采用鄰接表表示，則邊結(jié)點(diǎn)有個(gè)。本題答案：【2e##%_YZPRLFH_%##2*e】6、【填空題】用鄰接矩陣存儲有向圖G時(shí)，其第i列的所有元素之和等于該頂點(diǎn)的。本題答案：【入度】第3講隨堂測驗(yàn)1、【單選題】如果從一個(gè)無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn),則該圖一定是()本題答案：【連通圖】2、【單選題】圖的深度優(yōu)先遍歷類似于樹的（）遍歷本題答案：【先序遍歷】3、【單選題】圖的廣度優(yōu)先遍歷類似于樹的（）遍歷本題答案：【層次遍歷】第4講隨堂測驗(yàn)1、【單選題】任何一個(gè)連通圖（）生成樹。本題答案：【有一棵或多棵】2、【單選題】Prim算法適合求（）的最小生成樹。本題答案：【邊稠密連通網(wǎng)】3、【判斷題】對于n個(gè)頂點(diǎn)的連通圖G來說，如果其中的某個(gè)子圖有n個(gè)頂點(diǎn)，n-1條邊，則該子圖一定是G的生成樹。（）本題答案：【錯(cuò)誤】4、【填空題】對于n個(gè)頂點(diǎn)的連通圖而言，它的生成樹一定有條邊。本題答案：【n-1】第5講隨堂測驗(yàn)1、【單選題】若一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄校瑒t可斷定該有向圖（）本題答案：【是個(gè)含有回路的有向圖】2、【判斷題】任何有向無環(huán)圖的頂點(diǎn)都可以排成拓?fù)渑判蛐蛄校彝負(fù)渑判蛐蛄形ㄒ唬ǎ┍绢}答案：【錯(cuò)誤】3、【填空題】在ＡＯＶ網(wǎng)中，頂點(diǎn)表示。本題答案：【活動】第6講隨堂測驗(yàn)1、【單選題】關(guān)鍵路徑是ＡＯE網(wǎng)中（）本題答案：【從源點(diǎn)到匯點(diǎn)的最長路徑】2、【判斷題】關(guān)鍵活動若不能按期完成就會影響整個(gè)工程的完成時(shí)間，若某些關(guān)鍵活動能提前完成，將可能使整個(gè)工程提前完成。（）本題答案：【正確】3、【填空題】在ＡＯE網(wǎng)中，關(guān)鍵路徑上的活動稱為。本題答案：【關(guān)鍵活動】第7講隨堂測驗(yàn)1、【單選題】求最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為（）n為圖中頂點(diǎn)數(shù)，e為圖中邊數(shù)。本題答案：【O（）】2、【判斷題】求最短路徑的Dijkstra算法不適用于有回路的有向網(wǎng)（）本題答案：【錯(cuò)誤】第七章單元測驗(yàn)1、【單選題】在一個(gè)圖中，所有頂點(diǎn)的度之和是所有邊數(shù)的()倍。本題答案：【2】2、【單選題】在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的()倍。本題答案：【1】3、【單選題】一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有()條邊。本題答案：【(n*(n-1))/2】4、【單選題】在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要()條邊。本題答案：【n-1】5、【單選題】對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是()。本題答案：【n*n】6、【單選題】對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表存儲，則鄰接表中的結(jié)點(diǎn)總數(shù)是()。本題答案：【2*e】7、【單選題】以下說法錯(cuò)誤的是()。本題答案：【鄰接表只能用于有向圖的存儲，而鄰接矩陣對于有向圖和無向圖的存儲都適用?！?、【單選題】已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)頂點(diǎn)出發(fā)的方法是（）。本題答案：【將矩陣第i行上的元素全部置0】9、【單選題】某圖的鄰接表存儲結(jié)構(gòu)如下圖所示，則從6號點(diǎn)出發(fā)，深度優(yōu)先遍歷的序列是（）本題答案：【6-5-1-2-4-3】10、【單選題】某圖的鄰接矩陣存儲結(jié)構(gòu)如下圖所示，則從6號點(diǎn)出發(fā)，廣度優(yōu)先遍歷的序列是（）本題答案：【6-1-2-5-4-3】11、【單選題】對具有n個(gè)頂點(diǎn)的連通圖，其生成樹有且僅有()條邊。本題答案：【n-1】12、【單選題】稀疏圖采用（）存儲較省空間。本題答案：【鄰接表】13、【單選題】關(guān)鍵路徑是從源點(diǎn)到匯點(diǎn)的（）路徑。本題答案：【最長的】14、【單選題】在有向圖的鄰接矩陣上，第i行中的非零且非無窮元素個(gè)數(shù)是第i個(gè)結(jié)點(diǎn)的（）。本題答案：【出度】15、【判斷題】關(guān)鍵路徑上的活動都是關(guān)鍵活動，它們是否按時(shí)完成會影響工期。本題答案：【正確】16、【判斷題】求稀疏圖的最小生成樹，用克魯斯卡爾算法來求解較高效。本題答案：【正確】17、【判斷題】求稠密圖的最小生成樹，用普里姆算法來求解較好。本題答案：【正確】18、【判斷題】迪杰斯特拉算法求最短路徑時(shí)，是按照路徑長度遞增的順序求解的。本題答案：【正確】19、【判斷題】一個(gè)有向圖的拓?fù)渑判蛑挥幸粋€(gè)。本題答案：【錯(cuò)誤】20、【判斷題】每一個(gè)有向圖肯定至少有一個(gè)拓?fù)渑判?。本題答案：【錯(cuò)誤】21、【判斷題】具有6個(gè)頂點(diǎn)的無向圖至少應(yīng)有6條邊才能確保是一個(gè)連通圖。本題答案：【錯(cuò)誤】22、【判斷題】非關(guān)鍵活動，可以無限期延遲。本題答案：【錯(cuò)誤】第1講隨堂測驗(yàn)1、【單選題】采用順序查找法查找長度為n的線性表時(shí)，平均查找長度為。本題答案：【】2、【多選題】通常將作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。本題答案：【平均查找長度#ASL】3、【判斷題】順序查找方法只能在順序存儲結(jié)構(gòu)上進(jìn)行。（）本題答案：【錯(cuò)誤】4、【填空題】順序查找含n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為次。本題答案：【n】5、【填空題】順序查找含n個(gè)元素的順序表，若查找不成功，則比較關(guān)鍵字的次數(shù)為次。本題答案：【n+1】第2講隨堂測驗(yàn)1、【單選題】對列表進(jìn)行折半查找時(shí)，要求列表必須。本題答案：【順序存儲且元素按關(guān)鍵字有序存儲】2、【單選題】當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式要求。本題答案：【數(shù)據(jù)分成若干塊，每塊內(nèi)元素不必有序，但塊間必須有序，且每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊；】3、【單選題】有一個(gè)有序表{1,3,9,12,32,41，45,62,75,77,82,95,99}當(dāng)采用折半查找法查找關(guān)鍵字為82的元素時(shí)，需經(jīng)過次比較后查找成功。本題答案：【4】4、【判斷題】折半查找可以在有序的雙向鏈表上進(jìn)行。（）本題答案：【錯(cuò)誤】第3講隨堂測驗(yàn)1、【單選題】如圖所示的二叉排序樹，，起查找成功時(shí)的平均查找長度是。本題答案：【】2、【單選題】在一棵平衡二叉樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是。本題答案：【-1——1】3、【判斷題】查找效率最高的二叉排序樹是平衡二叉排序樹。（）本題答案：【正確】4、【判斷題】在二叉排序樹中新插入的結(jié)點(diǎn)總是作為葉子結(jié)點(diǎn)來插入的。（）本題答案：【正確】5、【判斷題】在二叉排序樹中新插入的結(jié)點(diǎn)總是處于最底層。（）本題答案：【錯(cuò)誤】6、【判斷題】每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小，這樣的二叉樹都是二叉排序樹。（）本題答案：【錯(cuò)誤】第4講隨堂測驗(yàn)1、【單選題】將10個(gè)元素散列到10000000個(gè)單元的哈希表中，則產(chǎn)生沖突。本題答案：【仍可能會】2、【單選題】在哈希查找中，可用來處理沖突。本題答案：【線性探測散列法】3、【單選題】設(shè)哈希表長度m=12，哈希函數(shù)為H（key）=keymod11.表中已經(jīng)有4個(gè)結(jié)點(diǎn)分別為H（15）=4，H(38)=5,H（61）=6，H(84)=7,其余地址為空。如果用二次探測再散列處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)地址為。本題答案：【9】4、【填空題】設(shè)哈希表長度m=14,哈希函數(shù)H（key）=keymodp,則p最好取。本題答案：【13】第5講隨堂測驗(yàn)1、【單選題】若采用鏈地址法構(gòu)造哈希表并處理沖突，哈希函數(shù)為H（key）=keymod17，則需要個(gè)鏈表。本題答案：【17】2、【單選題】假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探測再散列法將這k個(gè)關(guān)鍵字存入哈希表中，至少要進(jìn)行次定址。本題答案：【k(k+1)/2】3、【多選題】哈希表的查找性能。本題答案：【與處理沖突的方法有關(guān)而與表的長度無關(guān)#與處理沖突的方法有關(guān)，與裝填因子有關(guān)】第八章單元測驗(yàn)1、【單選題】關(guān)于折半查找，以下說法正確的是()。本題答案：【待查找表必須有序，且只能以順序方式存儲】2、【單選題】具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長度（）。本題答案：【37/12】3、【單選題】以下適合用分塊查的數(shù)據(jù)集是()。本題答案：【數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序】4、【單選題】分別以下列序列構(gòu)造二叉排序樹，以下哪一個(gè)和其他三個(gè)不同()。本題答案：【（90,100,65,25,87,85,110,107）】5、【單選題】關(guān)于哈希查找，以下說法不正確的是()。本題答案：【哈希查找中，記錄的存儲地址是計(jì)算出來的，因而不需要比較】6、【單選題】對長度為4的順序表