|
第一章 緒論（總時長：56分26秒，共6講） 第1講 數(shù)據(jù)結構的基礎概念（總時長12分鐘）隨堂測驗 1、一個抽象類型包括數(shù)據(jù)對象、 和一組處理數(shù)據(jù)的操作。 A、數(shù)據(jù)對象中各元素間的結構關系 B、數(shù)據(jù)元素集 C、接口 D、數(shù)據(jù)對象集 2、抽象數(shù)據(jù)類型具有 、信息隱蔽的特點。 第2講 數(shù)據(jù)結構的內容（總時長5分29秒）隨堂測驗 1、線性結構只能用順序結構來存放，非線性結構只能用非順序結構來存放。（ ） 2、1、數(shù)據(jù)結構的邏輯結構分為集合、線性、層次和 四種。 3、2、數(shù)據(jù)結構的存儲結構分為 和非順序 兩種。 4、3、在線性結構、樹形結構和圖結構中，數(shù)據(jù)元素之間分別存在著一對一、一對多和 聯(lián)系。 第3講 數(shù)據(jù)結構與c語言表示（總時長7分32秒）隨堂測驗 1、當需要用一個形式參數(shù)直接改變對應實參的值時，該形式參數(shù)應說明為 。 A、與實參同類型指針參數(shù) B、不需要參數(shù) C、與實參同類型的參數(shù) D、全局變量 第4講 算法性能評價（總時長8分06秒）隨堂測驗 1、1、執(zhí)行下面的程序段的時間復雜度為 。 for(int i=0;i A、O(http://img1.ph.126.net/49RGNd8jmCbrs0moUzfndQ==/6608475000770992294.png) B、O(http://img2.ph.126.net/M6JqsehvN6UBbvuGOAL_2g==/6608661917747811041.png) C、O(m*n) D、O (m+n) 2、2、執(zhí)行下面程序段時，語句S的執(zhí)行次數(shù)為 。 for(int i=0;i<=n;i++) for(int j=0;j <i;j++) s; A、http://img2.ph.126.net/M6JqsehvN6UBbvuGOAL_2g==/6608661917747811041.png B、http://img2.ph.126.net/nfjL0zUG2kiZyqv53zZAbA==/6630622463490960689.png C、n(n+1) D、http://img2.ph.126.net/NeptcPlilnnLxdt-QmBqcw==/6619406345374724696.png 第5講 算法與算法的描述（總時長14分59秒）隨堂測驗 1、算法設計的要求是：正確性、可讀性 、 和高效率和低存儲 。 A、確定性 B、健壯性 C、可行性 D、有限性 2、算法具有 有限性、確定性、 、輸入、輸出五大特性。 A、可行性 B、可讀性 C、健壯性 D、正確性 MOOC第一章單元測試題 1、執(zhí)行下面的程序段的時間復雜度為（ ）。 for(int i=0;i A、O(m2) B、O(n2) C、O(m*n) D、O(m+n) 2、執(zhí)行下面程序段時，語句S的執(zhí)行次數(shù)為（ ）。 for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) S; A、n*n B、n*n/2 C、(n+1)*(n+2)/2 D、n(n+1)/2 3、評價一個算法性能好壞的重要標準是（ ）。 A、算法易于調試 B、算法易于理解 C、算法的正確性 D、算法的時間復雜度 4、算法的時間復雜度與（ ）有關。 A、問題規(guī)模 B、計算機硬件性能 C、編譯程序質量 D、程序設計語言 5、算法分析的主要任務是分析（ ）。 A、算法是否具有較好的可讀性 B、算法中是否存在語法錯誤 C、算法的功能是否符合要求 D、算法的執(zhí)行時間與所需空間與問題規(guī)模的關系 6、算法分析的目的是( )。 A、找出數(shù)據(jù)結構的合理性 B、研究算法中輸入和輸出的關系 C、分析算法的效率以求改進 D、分析算法的可讀性 7、數(shù)據(jù)的最小單位是（ ）。 A、數(shù)據(jù)項 B、數(shù)據(jù)類型 C、數(shù)據(jù)元素 D、數(shù)據(jù)變量 8、某算法的時間復雜度是O（n^2）,表明該算法的（ ）。 A、問題規(guī)模是n^2 B、問題規(guī)模與n^2正比 C、執(zhí)行時間與n^2正比 D、執(zhí)行時間等于n^2 9、若需要利用形式參數(shù)直接訪問修改實參值，則應將形參說明為（ ）參數(shù)。 A、指針 B、值參數(shù) C、實地址 D、地址參數(shù) 10、如下程序段: for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) x=x+1; 其中語句x=x+1執(zhí)行的語句頻度為（ ）。 A、n*n B、n*(n-1)/2 C、n*(n+1)/2 D、n*(n-1) 11、以下算法的時間復雜度為（ ）。 if (n >= 0) { for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) printf("輸入數(shù)據(jù)大于等于零\n"); } else { for(int j = 0; j < n; j++) printf("輸入數(shù)據(jù)小于零\n"); } A、O(1) B、O(n*n+n) C、O(n) D、O(n*n) 12、在數(shù)組A[0..n-1]中查找給定值K的算法大致如下： i=n-1; while(i>=0&&(A[i]!=k)) i--; return i; 該算法的時間復雜度為（ ）。 A、O(n-i+1) B、O(n-i) C、O(n) D、無法確定 13、下面算法的時間復雜度為（ ）。 x=100; y=100; while(y>0) if(x>100) {x=x-10; y--;} else x++; A、O(n) B、O(100) C、O(1) D、O(n*n) 14、下面的算法是判斷n是否為素數(shù)，其算法時間復雜度為（ ）。 void prime(int n) { 判斷n是否是素數(shù) */ for (i=2; isqrt(n)) printf("%d is a prime number", n); else printf("%d is not a prime number", n); } A、O(n) B、O(1) C、O(sqrt(n)) sqrt表示對n取根方 D、O（n-i） 15、一個抽象數(shù)據(jù)類型包括（ ）。 A、數(shù)據(jù)對象 B、數(shù)據(jù)對象中各元素間的關系 C、數(shù)據(jù) D、一組基本操作 16、以下屬于數(shù)據(jù)元素間基本邏輯結構的是（ ）。 A、集合 B、線性 C、樹 D、圖 17、以下屬于算法特性的是（ ）。 A、0個或多個輸入 B、至少一個輸出 C、正確性和有限性 D、可行性 18、算法設計的要求包括（ ）。 A、正確性 B、可讀性 C、健壯性 D、高效率和低存儲 19、數(shù)據(jù)元素在計算機的存儲映像包括（ ）。 A、順序存儲 B、非順序存儲 C、圖結構 D、樹結構 20、具有線性結構的數(shù)據(jù)元素只能順序存儲，非線性結構的元素只能非順序存儲。 21、算法就是程序。 22、算法的優(yōu)劣與算法描述的語言無關。 23、算法的可行性是指每一條指令具有明確含義。 24、健壯的算法不會因為非法輸入而出現(xiàn)莫名的執(zhí)行結果。 25、高效率和低存儲是衡量一個算法的唯一標準。 26、數(shù)據(jù)類型就是一組性質相同的值的集合和在該集合上的一組操作的總稱。 27、數(shù)據(jù)元素的存儲結構分為順序存儲和非順序存儲。 28、數(shù)據(jù)元素的順序存儲優(yōu)于非順序存儲。 29、一個數(shù)據(jù)結構在存儲時，只需要存儲數(shù)據(jù)元素即可。 MOOC第一章單元作業(yè) 1、計算下列程序段中x++的語句頻度： x=1; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) x++; 2、（1）簡述數(shù)據(jù)元素間的四類基本邏輯結構。 （2）抽象數(shù)據(jù)類型定義。 （3）數(shù)據(jù)元素及其關系的兩類存儲結構與特點。 第二章 線性表（一）（總時長：72分22秒，共6講） 第1講 線性表的概念（總時長9分20秒）隨堂測驗 1、線性表是具有n個（ ）的有限序列（n>0） A、數(shù)據(jù)對象 B、數(shù)據(jù)元素 C、字符 D、數(shù)據(jù)項 2、線性表是一個（ ）。 A、有限序列，可以為空 B、有限序列，不可以為空 C、無限序列，可以為空 D、無限序列，可以為空 3、線性表的特點是每個元素都有一個前驅和一個后繼。（） 第2講 線性表的順序存儲（總時長13分）隨堂測驗 1、若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為（ ）(1<=i<=n+1)。 A、O(1) B、O(n) C、O(n*n) D、O（http://img2.ph.126.net/7nSo5-ole5MYKByN95JmhQ==/6619166651839422470.png） 2、若長度為n的線性表采用順序存儲結構，刪除第i個位置的元素，需要移動的元素個數(shù)為（ ）。 A、i B、n-i C、n-i+1 D、n-i-1 第3講 線性表順序結構應用示例及小結（總時長7分57秒）隨堂測驗 1、對一個長度為n的順序表，假設在任何位置上插入一個元素的概率是相等的，那么插入一個元素時要移動表中的（ ）個元素。 A、n B、n+1 C、http://img2.ph.126.net/OLtuq-gj-j5MI-DYRqhUQQ==/6631956171093983699.png D、http://img1.ph.126.net/spfuqF6ITsyWgltixK9GcA==/6630709324909673185.png 2、線性表的順序存儲是指將表中元素按照從大到小或從小到大存儲。 第4講 線性表的鏈式存儲（總時長10分20秒）隨堂測驗 1、通過表達式 可以獲取帶頭結點的單鏈表L中首元素結點的數(shù)據(jù)值。 A、L->next B、(L->next)->data C、L->data D、L->next 2、單鏈表中必須設有頭結點。（） 第5講 單鏈表的基本運算（總時長20分58秒）隨堂測驗 1、下列選項中， 項是鏈表不具有的特點。 A、插入和刪除運算不需要移動元素 B、所需要的存儲空間與線性表的長度成正比 C、不必事先估計存儲空間大小 D、可以隨機訪問表中的任意元素 2、有一個帶頭結點的單鏈表HEAD，則判斷其是否為空鏈表的表達式是 A、HEAD= =NULL B、HEAD-〉NEXT= =NULL C、HEAD-〉NEXT= =HEAD D、HEAD！=NULL 3、在一個單鏈表中P所指結點后插入一個S所指結點時， 應執(zhí)行語句： 。 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; 第6講 單鏈表運算的應用示例及小結（總時長10分47秒）隨堂測驗 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)； 2、對鏈表進行插入和刪除操作時不必移動鏈表中結點。( ) 3、在單鏈表中，可以從頭結點出發(fā)，查找到表中所有結點。（ ） 第二章 第一次單元測驗 1、在長度為n的順序表中的第i( 1 =< i <= n+1 )個位置上插入一個元素，其算法時間復雜度為（ ）。 A、O(logn)(以2為底) B、O(1) C、O(n) D、O(n*n) 2、在長度為n的順序表中的第i( 1 =< i <= n+1 )個位置上插入一個元素，需要移動的元素個數(shù)為（ ）。 A、n-i B、i C、n-i+1 D、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); 5、假設刪除長度為n的順序表中的每個元素的概率相同，則刪除一個元素平均要移動的元素個數(shù)是（ ）。 A、n B、(n+1)/2 C、(n-1)/2 D、n/2 6、設某順序表中第一個元素的地址是Base，每個結點占m個單元，則第i個結點的地址為（ ）。 A、Base+(i-1)×m B、Base+i×m C、Base-i×m D、Base+(i+1)×m 7、長度為n的非空線性表采用順序存儲結構，在表的第i個位置插入一個數(shù)據(jù)元素，i的合法值應該是（ ）。 A、i>0 B、1≤i≤n+1 C、1≤i≤n-1 D、0≤i≤n+1 8、非空單鏈表結點結構為【data,next】，若指針p所指結點是尾結點，則（ ）表達式為真。 A、p==NULL B、p->next==NULL C、p->next==P D、p->next!=NULL 9、某順序表的第一個元素的存儲地址是500，每個元素占4個單元，則第8個元素的起始地址是( )。 A、504 B、508 C、516 D、528 10、在長度為n的順序表中刪除第i(1<=i<=n)個位置上的元素，需要移動的元素個數(shù)為（ ）。 A、n-i B、n-i+1 C、n-i-1 D、i 11、單鏈表中增加頭結點的目的是存儲鏈表的長度。 12、靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。 13、線性表在鏈式存儲時，查找第i個元素的時間同i的值無關。 14、線性表在順序存儲時，查找第i個元素的時間同i 的值成正比。 15、線性表的特點是每個元素都有一個前驅和一個后繼。 16、線性表的鏈式存儲結構優(yōu)于順序存儲。 17、順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。 18、順序表的每個結點只能是一個基本類型，而鏈表的每個結點可以是一個構造類型。 19、插入和刪除操作是線性表的基本操作。這兩種操作在數(shù)組中也經常使用。 20、在順序表中，邏輯上相鄰的兩個元素物理存儲上也一定也相鄰。 21、在線性表的鏈式存儲結構中，邏輯上相鄰的兩個元素在物理存儲上并不一定相鄰。 22、線性表采用順序存儲，必須占用一段地址連續(xù)的存儲單元。 23、順序表結構適宜進行隨機訪問，而鏈表適宜進行插入、刪除。 24、若某線性表經常做插入、刪除操作，易采用 結構存儲?！菊?zhí)?順序 或 鏈式】 第二章 第一次作業(yè) 1、描述以下三個概念及其關系：頭指針，頭結點，首元素結點。 2、長度為n的順序表中，假設在任何位置插入元素的概率均相等，則插入一個元素平均需要移動多少個元素？ 3、簡述順序表優(yōu)缺點。 4、編寫算法，從順序表中刪除自第i個元素開始的k個元素。若不夠k個元素時，將i后面的元素全部刪除。 第二章 線性表（二）（總時長：59分37秒） 第7講 循環(huán)鏈表（總時長7分05秒）隨堂測驗 1、有一個帶頭結點的循環(huán)單鏈表HEAD，則判斷其是否為空鏈表的條件是 。 A、HEAD==NULL B、HEAD-〉NEXT==NULL C、HEAD-〉NEXT==HEAD D、HEAD！=NULL 2、在單向循環(huán)鏈表中，從表中任意結點出發(fā)都可以順著next域訪問到表中所有元素（） 第8講 雙向鏈表（總時長7分47秒）隨堂測驗 1、與單鏈表相比，雙向鏈表的優(yōu)點之一是 。 A、插入刪除操作更加方便 B、可以進行隨機訪問 C、可以省略表頭指針和表尾指針 D、訪問前后相鄰結點更方便。 2、在雙向鏈表L中，可以從任一結點p出發(fā)沿同一方向的指針域查找到表中所有元素。（） 第9講 靜態(tài)鏈表（總時長6分24秒）隨堂測驗 1、靜態(tài)鏈表中與動態(tài)鏈表的插入和刪除運算類似，不需要做元素的移動。（） 2、靜態(tài)鏈表既有順序存儲結構的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第ｉ個元素的時間與位置序號ｉ無關，可以實現(xiàn)隨機存取。（） 第10講 鏈式結構小結（總時長7分32）隨堂測驗 1、已知單鏈表的頭指針為head且該鏈表不帶頭結點，則該單鏈表為空的條件是 。 A、head== NULL B、head->next==NULL C、head->next==head D、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)； 3、設帶有頭結點的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是 。 A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 4、在雙向循環(huán)鏈表中，可以從任一結點p出發(fā)沿同一方向的指針域查找到表中所有元素。（） 第12講 順序表與鏈表的綜合比較（總時長6分08秒）隨堂測驗 1、下列選項中， 項是鏈表不具有的特點。 A、插入和刪除運算不需要移動元素 B、所需要的存儲空間與線性表的長度成正比 C、不必事先估計存儲空間大小 D、可以隨機訪問表中的任意元素 2、在線性表中最常用的操作是存取第i個元素及其前趨的值，可采用 存儲方式最省時間？ A、順序表 B、帶頭指針的雙向循環(huán)鏈表 C、帶頭指針的單向循環(huán)鏈表 D、帶頭指針的單向鏈表 3、下面關于線性表的敘述錯誤的是（ ）。 A、線性表采用順序存儲必須占用一片連續(xù)的存儲空間 B、線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間 C、線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn) D、線性表采用順序存儲便于插入和刪除操作的實現(xiàn) 總結與提高（總時長15分15秒）隨堂測驗 1、某線性表中最常用的操作是存取序號為i的元素和在最后進行插入和刪除運算，則采用 存儲方式時間性能最好。 A、雙向鏈表 B、雙向循環(huán)鏈表 C、單向循環(huán)鏈表 D、順序表 2、已知一個帶頭結點的非空循環(huán)單鏈表，其尾指針是R，則其首元素結點的地址為： A、R->next B、*( R->next->next ) C、&( R->next->next ) D、R->next->next 3、線性表的順序存儲優(yōu)于鏈式存儲結構。（） 4、在帶頭結點的非空單鏈表中，頭結點的存儲位置由 指示 第二章 第二次單元測試 1、非空循環(huán)單鏈表L中，p指針指向尾結點，則以下表達式成立的是（ ）。 A、p->next==NULL B、p==NULL C、p->next==L D、p==L 2、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。 A、順序表 B、雙向鏈表 C、帶頭結點的雙循環(huán)鏈表 D、單循環(huán)鏈表 3、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。 A、單鏈表 B、僅有頭指針的單循環(huán)鏈表 C、雙鏈表 D、僅有尾指針的單循環(huán)鏈表 4、對于雙向循環(huán)鏈表，在兩個結點之間插入一個新結點需修改的指針共（ ）個。 A、2 B、3 C、4 D、5 5、將帶頭指針的長度為m的單鏈表，鏈接到同樣帶頭指針的長度為n的單鏈表末尾。該算法的時間復雜度為( )。 A、O(m) B、O(n) C、O(m+n) D、O(m*n) 6、靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。 7、循環(huán)單鏈表中，每個結點都有一個前驅和后繼，因此循環(huán)單鏈表不是線性結構。 8、靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。 9、靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。 10、線性表在順序存儲時，查找第i個元素的時間同i的值無關。 11、線性表在順序存儲時，刪除第i個元素的時間同i的值無關。 12、靜態(tài)鏈表因為采用的是一段連續(xù)的空間來存儲元素，因此查找第i個元素的時間和i無關。 13、在帶頭指針的長度為n的雙向循環(huán)鏈表的末尾插入一個元素，其時間復雜度為O( )。（填寫阿拉伯數(shù)字或字母） 14、某雙向鏈表中，結點結構為【prior,data,next】。那么刪除p指針所指結點時，需要執(zhí)行語句：p->next->prior=p->prior; ; free(p); 15、在某雙向鏈表中刪除一個結點，需要改動 個指針域（填寫阿拉伯數(shù)字） 第二章 第二次作業(yè) 1、以下算法是求取某帶頭結點的單鏈表的長度，請補充完整代碼。 int LinkLength(LinkList L) { Node* p=L->next; int i=0; ...... //補充此處代碼 return i; //返回鏈表長度 } 2、帶頭結點的單鏈表L，編寫算法實現(xiàn)就地逆置。 3、某一元多項式采用帶頭結點的單鏈表存儲，編寫算法求其導數(shù)。函數(shù)聲明：void Derivative(PolyNode *PL)，參數(shù)為一元多項式的頭指針，該多項式按照冪次遞增的次序排列，結果仍為PL所指的鏈表。 第三章 棧與隊列（一）（總時長53分23秒） 第1講 棧的定義與實現(xiàn)（總時長6分59秒）隨堂測驗 1、棧操作的特性是（ ） A、FIFO B、LIFO C、FCFS D、插入和刪除操作限制在表的兩端進行 2、棧中，允許進行插入和刪除的一端稱為（） A、棧頂 B、棧底 C、棧頭 D、棧尾 3、棧是線性結構，是操作受限制的線性表。（） 第2講 棧的順序結構（總時長10分54秒）隨堂測驗 1、1、 已知順序棧的地址為s,此時棧不滿且棧頂指示器top指向真實棧頂,執(zhí)行元素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++; 2、2、 已知順序棧的地址為s ,此時棧不空且棧頂指示器top指向真實棧頂，執(zhí)行出棧操作并將出棧元素賦值給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--; 3、1、 已知順序棧的地址為s ,此時棧不空且棧頂指示器top指向真實棧頂，執(zhí)行取棧頂操作的語句是 *x= s->elem[s->top--];( ) 第3講 順序棧的兩棧共享（總時長13分19秒）隨堂測驗 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; 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 3、已知一個雙端棧的地址為dS，則該雙端棧不空時，1號棧（高端棧）出棧操作的語句是*x= dS->stack[dS->top[1]--]（） 第4講 棧的鏈式實現(xiàn)（總時長8分01秒）隨堂測驗 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); 2、已知帶頭結點的鏈棧top, 則該鏈棧為空的條件是( ) A、top==NULL B、top->next= =NULL C、top->next->next= =NULL D、top->next= =top 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; 第5講 棧的應用（總時長8分34秒）隨堂測驗 1、在括號匹配算法中，當正掃描檢測的符號是右括號，此時的棧是空棧，則（）。 A、右括號進棧； B、繼續(xù)向下掃描； C、取出棧頂元素做匹配檢查； D、此時出現(xiàn)“右括號多了”的不匹配現(xiàn)象。 2、在算術表達式求值的算法中，若當前正掃描的符號是運算符s，且s的優(yōu)先級比運算符棧棧頂元素的優(yōu)先級高，則（ ） A、運算符棧出棧，運算數(shù)出棧，做運算； B、s 進運算符棧； C、取運算符棧棧頂，運算數(shù)棧頂，做運算； D、s 進運算數(shù)棧； 3、在括號匹配算法中，當正掃描的符號是左括號時，則該做左括號（ ）。 第6講 棧與遞歸（上）（總時長10分43秒）隨堂測驗 1、遞歸進層（i→i +1層）系統(tǒng)需要做三件事是（ ） A、保留本層參數(shù)與返回地址； B、保留下層參數(shù)和函數(shù)地址； C、為被調用函數(shù)的局部變量分配存儲區(qū)，給下層參數(shù)賦值； D、將程序轉移到被調函數(shù)的入口。 2、從被調用函數(shù)返回調用函數(shù)之前，遞歸退層（i←i +1層）系統(tǒng)也應完成三件工作是（ ） A、保存被調函數(shù)的計算結果； B、釋放被調函數(shù)的數(shù)據(jù)區(qū)，恢復上層參數(shù)； C、保存返回上層函數(shù)的地址； D、依照被調函數(shù)保存的返回地址，將控制轉移回調用函數(shù)。 3、遞歸是指在定義自身的同時又出現(xiàn)了對自身的引用。（ ） 4、系統(tǒng)需設立一個遞歸工作棧作為整個遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。每層遞歸所需信息構成一個（ ）。 第三章 單元測驗 1、棧的特點是（ ）。 A、先進先出 B、先進后出 C、后進后出 D、沒有順序 2、隊列的特點是（ ）。 A、先進先出 B、先進后出 C、后進先出 D、沒有順序 3、棧之說以叫限定性線性表，是因為（ ）。 A、棧的操作位置受限制 B、棧中的元素類型受限制 C、棧的應用范圍受限制 D、棧的存儲結構受限制 4、輸入序列為123，若進棧出棧可以交替進行，則不能可以得到的出棧序列是（ ）。 A、321 B、312 C、123 D、132 5、以下會用到棧的應用的是（ ）。 A、遞歸 B、子程序調用 C、括號匹配 D、其他選項均有可能 6、循環(huán)隊列存儲在數(shù)組A[0..m-1]中，則入隊時rear應該變化為（ ） A、rear++ B、rear=(rear+1) mod (m-1) C、rear=(rear+1) mod m D、rear=(rear+1) mod (m+1) 7、循環(huán)隊列A[0..n-1]存放其元素值，用F和R分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是( )。 A、(R-F+n)%n B、R-F+1 C、R-F-1 D、R-F 8、棧和隊列的共同點是（ ）。 A、都是先進先出 B、都是先進后出 C、只允許在端點處插入和刪除元素 D、它們沒有共同點 9、當利用大小為n的數(shù)組(下標從1到n)順序存儲一個棧時，假定用top==n表示?？眨瑒t每次向這個棧插入一個元素時，首先應執(zhí)行（ ）語句修改top指針。 A、top++; B、top--; C、top=0; D、top=n; 10、設棧S和隊列Q的初始狀態(tài)均為空，元素a,b,c,d,e,f,g依次進入棧S。如果每個元素出棧后立即進入隊列Q，且7個元素出隊的順序為b,d,e,f,c,a,g，則棧S的容量至少是（ )。 A、1 B、2 C、3 D、4 11、以下屬于遞歸求解問題的前提條件的是（ ）。 A、原問題可層層分解為子問題，且子問題比原問題規(guī)模小 B、子問題的解法與原問題解法相同 C、最小的子問題有解 D、其他選項均是 12、以下屬于消除遞歸的主要原因是（ ）。 A、遞歸程序不容易理解 B、遞歸程序時空效率較差 C、遞歸程序容易寫錯 D、其他選項均是 13、一個棧的輸入序列為123……n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（ ） A、i B、n-i C、n-i+1 D、不確定 14、消除遞歸肯定要用到棧，否則無法完成。 15、若輸入序列為1234,則通過一個?？梢缘玫捷敵鲂蛄?124。 16、若輸入序列為1234,則通過棧只能得到4321的輸出序列。 17、有些問題，比如漢諾塔問題等，只能用遞歸來解，無法轉換成非遞歸算法。 18、順序棧因為是順序存儲，所以可以隨機存取棧中任意元素。 19、兩順序棧共享空間，也存在空間溢出問題。 20、棧與隊列是一種特殊操作的線性表。 21、棧和隊列都是限制插入和刪除位置的線性結構。 22、函數(shù)或過程調用需要用到棧。 23、棧中將允許操作的一端稱作 。 24、棧中將不允許操作的一端稱作 。 25、凡是對元素的保存次序與使用順序相反的，都可以使用 。 26、若棧采用單鏈表結構實現(xiàn)，則鏈表的頭指針的位置，表示的是棧的 。（請?zhí)顥ｍ敾驐５祝? 27、若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間S[1~N]，top[i]代表第i個棧( i =1,2)棧頂。棧1的底在v[1]，棧2的底在V[N]，則棧滿的條件是 。(請?zhí)顃op[1]+top[2]==N 或者 top[1]+1==top[2] 或者top[1]==top[2] ) 28、123按順序進棧，如果進棧出棧操作可以交替，則不可能得到的出棧序列是 。(數(shù)字中間不要加空格) 第三章 作業(yè) 1、以下算法是利用棧的先進后出特性，編寫的將一個十進制的數(shù)n，轉換為t進制。 請在橫線位置補充代碼。 //參考代碼 void Conversion(int n,int t) { Stack S; int x,temp=n; InitStack(&S); //將n轉換為t進制 while(n>0) { x=n%t; Push(&S, x); ; } //以下為從棧中依次出棧并輸出 while(!IsEmpty(&S)) { Pop(&S,&x); if(x<=9) printf("%d",x); //小于10的，按數(shù)值打印 else ; //大于10的，按字符打印 } } 2、給出棧的兩種存儲結構形式名稱，在這兩種棧的存儲結構中如何判別棧滿？ 第三章 棧與隊列（二）（總時長：52分54秒） 第7講 棧與遞歸（下）（總時長：8分40秒）隨堂測驗 1、遞歸算法具有兩個特性分別是（ ） A、遞歸算法求解問題，方法簡單。 B、遞歸算法效率高 C、遞歸算法求解問題，方法復雜 D、遞歸算法的效率較低 2、下列可以直接用循環(huán)結構即可將遞歸轉換為非遞歸的是（ ） A、斐波那契數(shù)列問題 B、N!問題 C、漢諾塔問題 D、尾遞歸問題 第8講 隊列的定義與實現(xiàn)（總時長：13分32秒）隨堂測驗 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; 2、已知帶頭結點的鏈隊列指針Q，則該非空隊列取隊頭元素操作的語句是（ ） A、*x=Q->next->data; B、*x=Q->front->data; C、*x=Q->front->next->data; D、*x=Q->rear->data; 3、隊列操作的特性是LIFO。（） 4、隊列允許做插入的一端稱為隊頭，允許刪除的一端稱為隊尾（ ） 第9講 序列的順序存儲（循環(huán)隊列）（總時長：11分08秒）隨堂測驗 1、已知循環(huán)隊列Q-> element[MAXSIZE],隊頭指示器為Q->front，隊尾指示器為Q->rear（指向真實隊尾的下一個位置），則該隊列中元素個數(shù)為：（） A、Q->rear-Q->front B、Q->rear-Q->front+1 C、（Q->rear-Q->front+ MAXSIZE）% MAXSIZE D、（Q->rear-Q->front+1+ MAXSIZE）% MAXSIZE 2、已知循環(huán)隊列Q-> element[MAXSIZE],隊頭指示器為Q->front，隊尾指示器為Q->rear（指向真實隊尾的下一個位置），則該隊列為空隊列的條件為（ ） A、Q->rear= =Q->front B、Q->rear+1= =Q->front C、（Q->rear+1）% MAXSIZE = =Q->front D、（Q->rear-1）% MAXSIZE = =Q->front 3、已知循環(huán)隊列Q-> element[MAXSIZE],隊頭指示器為Q->front，隊尾指示器為Q->rear（指向真實隊尾的下一個位置），則該隊列為滿隊列的條件為（ ）（采用少用一個空間的方法） A、Q->rear= =Q->front B、Q->rear+1= =Q->front C、（Q->rear+1）% MAXSIZE = =Q->front D、（Q->rear-1）% MAXSIZE = =Q->front 第10講 隊列的應用（總時長：7分08秒）隨堂測驗 1、在打印楊輝三角形前N行的算法中，需要申請一個N*N的二維數(shù)組存放楊輝三角形N行數(shù)據(jù)。（） 第四章 串（總時長：51分45秒） 第1講 串的基本概念（總時長：8分38秒）隨堂測驗 1、設s=‘abcd’,s1=‘123’，則執(zhí)行語句StrInsert( s,2,s1)后，s= . A、‘123abcd’ B、‘a123bcd’ C、‘ab123cd’ D、‘abc123d’ 2、設s=‘abcd’，則執(zhí)行語句StrDelete( s,2,2)后，s= . A、‘abcd’ B、‘abc’ C、‘ad’ D、‘a’ 第2講 串的順序存儲結構（總時長：21分04秒）隨堂測驗 1、假設主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法從主串的第6個字符開始模式匹配，需要做 趟匹配，方能找到匹配串。 2、假設主串S=‘aaabbbababaabb’,模式串T=‘abaa’,用串匹配算法從主串的第6個字符開始模式匹配，在第2趟匹配中，要做 次比較。 第3講 串的鏈式存儲及串的應用（總時長：22分03秒）隨堂測驗 1、用帶頭結點的單鏈表來表示串s,則串s 為空串的條件是（ ） A、s->next==NULL B、s==NULL C、s->next==s D、s->next->next==NULL 第五章 數(shù)組與廣義表（上）（總時長：38分01秒） 第1講 數(shù)組的定義與順序存儲（總時長：19分57秒）隨堂測驗 1、數(shù)組的維數(shù)和維度一旦確定，數(shù)組中元素的個數(shù)就確定了，不能增加不能減少。（ ） 2、數(shù)組的維數(shù)n決定了數(shù)組中的元素受n個線性關系的約束。（ ） 3、數(shù)組如同一般的線性表，可以做的基本運算包括存取指定位置的元素，插入，刪除等。( ) 4、假設有6行8列的二維數(shù)組A(下標從1開始),每個元素占用6個字節(jié),存儲器按字節(jié)編址。已知A的基地址為1000，數(shù)組A共占用 字節(jié); 5、假設有6行8列的二維數(shù)組A(下標從1開始),每個元素占用6個字節(jié),存儲器按字節(jié)編址。已知A的基地址為1000 ,計算數(shù)組A的最后一個元素的地址是 。 6、假設有6行8列的二維數(shù)組A(下標從1開始),每個元素占用6個字節(jié),存儲器按字節(jié)編址。已知A的基地址為1 000 ,計算按行存儲時元素A36的地址是 ; 7、假設有6行8列的二維數(shù)組A(下標從1開始),每個元素占用6個字節(jié),存儲器按字節(jié)編址。已知A的基地址為1 000 ,計算按列存儲時元素A36的地址是 。 第2講 規(guī)律分布特殊矩陣的壓縮存儲（總時長：18分04秒）隨堂測驗 1、已知一個n行n列的帶狀矩陣A，其中非零元素的個數(shù)是（ ） A、3n B、3n-2 C、3n+2 D、http://img2.ph.126.net/M6JqsehvN6UBbvuGOAL_2g==/6608661917747811041.png 2、若將n階上三角矩陣A按列優(yōu)先雅朵存放在一維數(shù)組B中，第一個非零元素存放在B[0]中，則非零元素aij存放在B[k]中，則k=( ) A、http://img0.ph.126.net/vcrkFjarpE6JaaHmtIZnAg==/6632100207117464256.png B、http://img1.ph.126.net/NT3Vsc-m8PZJnN3QdSEo0Q==/6632072719326768856.png C、http://img0.ph.126.net/GFiyQNJexTgtu76GvSiARA==/6631731870725247903.png D、http://img1.ph.126.net/gSSM1SPlOuSEXJAjDw6frw==/6631454793795065827.png 3、所謂的n階下三角矩陣A是指當i<j時（i為元素的行標，j 為元素的列標）元素aij為0或常數(shù)c="" .(="" ) 4、所謂的n階（n>3）三對角矩陣（帶狀矩陣）是指非零元素只出現(xiàn)在矩陣的兩條對角線上。（ ） 第五章 數(shù)組與廣義表（下）（總時長：57分05秒） 第3講 稀疏矩陣的壓縮存儲（上）（總時長：17分54秒）隨堂測驗 1、對稀疏矩陣進行壓縮存儲的目的是（ ） A、便于進行矩陣運算 B、便于輸入和輸出 C、節(jié)省存儲空間 D、減低運算的時間復雜度 2、稀疏矩陣壓縮存儲后，不會失去（ ）功能 輸入輸出 A、順序存儲 B、隨機存取 C、輸入輸出 D、輸入輸出 第4講 稀疏矩陣的壓縮存儲（下）（總時長：19分16秒）隨堂測驗 1、對于一個m行n列的稀疏矩陣中有l(wèi)en個非零元素，則用十字鏈表存儲時，需要（ ）個頭指針。 2、對于一個m行n列的稀疏矩陣中有l(wèi)en個非零元素，則用十字鏈表存儲時，需要（ ）個三元組結點。 第5講 廣義表及本章小結（總時長：19分55秒）隨堂測驗 1、任意一個廣義表都可以表示為由表頭和表尾構成（ ）。 2、非空的廣義表的表尾可能是單個元素也可能是表元素（ ）。 3、已知廣義表L=(( x,y,z), a,( u,t,w)),則head( head( tail( tail( L))))的結果是（ ）。 4、已知數(shù)組M[ 1 ..10 ,-1 ..6 ,0 ..3 ], )若數(shù)組以行序為主序存儲,起始地址為1 000 ,且每個數(shù)據(jù)元素占用3個存儲單元,則M[ 2 ,4 ,2 ]的地址為（ ） 第六章 樹和二叉樹（上）（總時長：48分02秒） 第1講 樹的基本概念（總時長：17分07秒）隨堂測驗 1、樹最適合用來表示（ ） A、有序數(shù)據(jù)元素 B、無序數(shù)據(jù)元素 C、元素之間具有分支層次關系的數(shù)據(jù) D、元素之間無聯(lián)系的數(shù)據(jù) 2、若一棵樹的廣義表法表示為：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 則該樹的度為（ ）； 3、若一棵樹的廣義表法表示為：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 該樹的深度為（ ）； 4、若一棵樹的廣義表法表示為：A（B（E,F），C（G（H,I,J,K），L），D（M（N））） 該樹中葉子結點的個數(shù)為：（ ） 第2講 二叉樹（總時長：18分04秒）隨堂測驗 1、按照二叉樹的定義，具有3個結點的二叉樹有（ ）種 A、3 B、4 C、5 D、6 2、若一棵二叉樹有10個度為2的結點，5個度為1的結點，則度為0的結點有（ ）個。 A、9 B、11 C、15 D、不確定 3、一個高度為h的完全二叉樹至少有（ ）個結點 A、http://img1.ph.126.net/eILza_9vIzsxkBOyt9XNYA==/6631692288306728188.png B、http://img1.ph.126.net/o6G_Rm_dnRl08Y6nuDCosw==/6631582337143954492.png C、http://img1.ph.126.net/NnXiazwur8V8qlSWv88q_A==/6631620820050922027.png D、http://img1.ph.126.net/Oz6WP6vN4J4TQD71z0h2Yw==/6631953972071042965.png 4、二叉樹就是結點度不大于2的樹。（） 5、不存在這樣的二叉樹：它有n個度為0的結點，n-1個度為1的結點，n-2個度為2的結點。（ ） 6、具有n個結點的二叉樹采用二叉鏈表存儲結構，共有（ ）非空的指針域。 7、擁有100個結點的完全二叉樹的最大層數(shù)是（ ） 第3講 二叉樹的遍歷（總時長：12分51秒）隨堂測驗 1、某二叉樹的先序序列和中序序列正好相同，則該二叉樹一定是 （ ） A、空樹或只有一個結點 B、完全二叉樹 C、每個結點都沒有左子 D、高度等于其結點數(shù) 2、在二叉樹中，p所指向的結點為度為1的分支點的條件是（ ） A、p->lchild= =NULL ||p->rchild= =NULL B、!( p->lchild! =NULL &&p->rchild!=NULL) C、!(p->lchild= =NULL &&p->rchild= =NULL) D、(p->lchild= =NULL &&p->rchild! =NULL)|| (p->lchild! =NULL &&p->rchild= =NULL) 3、已知二叉樹的先序和后序遍歷序列可以唯一確定該二叉樹。（ ） 第六章 單元測驗1 1、已知一算術表達式的中綴形式為 A-B/C+D*E，前綴形式為+-A/BC*DE，其后綴形式為( )。 A、ABCDE/-*+ B、AB/C-D*E+ C、ABC/-DE*+ D、A-BC/DE*+ 2、有關二叉樹下列說法正確的是（ ）。 A、二叉樹中每個結點的度都為2 B、一棵二叉樹的度可以小于2 C、二叉樹中至少有一個結點的度為2 D、二叉樹中任何一個結點的度都為2 3、在一棵高度為k的滿二叉樹中，結點總數(shù)為（ ）。 A、http://img2.ph.126.net/_FERaO8srW4EqFXkJxS0Lw==/6608732286492058466.png-1 B、2k C、http://img0.ph.126.net/FnoDs-EmEIHOVFlnY7di_g==/6631229393910571560.png D、http://img0.ph.126.net/2EyOEyX5zu9TketxiBnVqA==/6631626317609074248.png 4、某二叉樹中有60個葉子結點，則該二叉樹中度為2的結點個數(shù)為（ ）。 A、59 B、60 C、61 D、不確定 5、100個結點的完全二叉樹采用順序存儲，從1開始按層次編號，則編號最小的葉子結點的編號應該是（ ）。 A、100 B、49 C、50 D、51 6、完全二叉樹一定存在度為1的結點。 7、完全二叉樹中，若一個結點沒有左孩子，則它必是葉子。 8、二叉樹只能用二叉鏈表表示。 9、樹形結構中，每個元素都有一個前驅，0個或多個后繼。 10、由3 個結點可以構造出 種形態(tài)不同的無序樹。 11、由3 個結點可以構造出 種形態(tài)不同的二叉樹。 12、對任意一棵有n個結點的樹，這n個結點的度之和為 。 13、高度為7的完全二叉樹，最少有 個結點。 第六章 樹和二叉樹（下）（總時長：112分28秒） 第4講 遍歷算法應用（總時長：19分50秒）隨堂測驗 1、設二叉樹采用二叉鏈表方式存儲，root指向根結點，r所指結點為二叉樹中任一給定的結點。則可以通過改寫（ ）算法，求出從根結點到結點r之間的路徑。 A、先序遍歷 B、中序遍歷 C、后序遍歷 D、層次遍歷 2、已知二叉樹用二叉鏈表存儲，則若實現(xiàn)二叉樹實現(xiàn)左右子樹交換，可以借助改寫（ ）遍歷算法實現(xiàn)。 A、先序遍歷 B、中序遍歷 C、后序遍歷 D、以上三種都可以 第5講 基于棧的遞歸消除（總時長：14分27秒）隨堂測驗 1、在中序遍歷非遞歸算法中，在進入子樹進行訪問前，需要在自定義棧中保存（ ） A、本層根結點指針 B、本層根結點的右孩子指針 C、本層根結點的左孩子指針 D、無需保留任何信息 第6講 線索二叉樹（總時長：17分35秒）隨堂測驗 1、引入線索二叉樹的目的是( ) A、加快查找指定遍歷過程中結點的直接前驅和直接后繼 B、為了能在二叉樹中方便地插入和刪除結點 C、為了方便找到結點的雙親 D、使二叉樹遍歷結果唯一 2、若判斷線索二叉樹中的p結點有右孩子結點則下列（）表達式為真。 A、p!=NULL B、p->rchild!=NULL C、p->rtag= =0 D、p->rtag= =1 3、若線索二叉樹中的p結點沒有左孩子結點則下列（ ）表達式為真。 A、p==NULL B、p->lchild==NULL C、p->ltag= =0 D、p->ltag= =1 第7講 由遍歷序列確定的二叉樹（總時長：7分48秒）隨堂測驗 1、一棵二叉樹的后序序列是：CBEFDA,中序序列是：CBAEDF,則該二叉樹的先序序列是（ ） A、ABCDEF B、ABCEDF C、ABDEFC D、ABFECD 2、一棵二叉樹的先序序列是：CEDBA,中序序列是：DEBAC ,則該二叉樹的后序序列是（ ） A、DABEC B、DCBAE C、DEABC D、CBADE 第8講 樹、森林和二叉樹的關系（總時長：17分33秒）隨堂測驗 1、如圖所示的二叉樹BT是由森林T1轉換而來的二叉樹，那么森林T1中有（ ）葉子結點。 http://nos./edu-image/365A12AF8BBBA3061A0C97B299C2B87C.JPG?imageView&thumbnail=520x520&quality=100 A、4 B、5 C、6 D、7 2、與樹等價的二叉樹，根沒有（ ）子樹。 第9講 哈夫曼樹及其應用——哈夫曼樹（總時長：12分46秒）隨堂測驗 1、有13個葉子結點的哈夫曼樹，該樹中結點總數(shù)為（ ） A、13 B、26 C、12 D、25 2、在哈夫曼樹中，權值相同的葉子點一定在同一層上。（ ） 3、在哈夫曼樹中，權值較大的葉子點一般離根比較近。（ ） 4、若以{4,5,6,7,8}作為葉子點構造哈夫曼樹，則其帶全路徑長度為（ ） 第10講 哈夫曼樹及其應用——哈夫曼編碼（總時長：14分35秒）隨堂測驗 1、在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相等時，則兩個字符的哈夫曼編碼也相同。（ ） 第六章 單元測驗2 1、已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為（ ）。 A、CBEFDA B、FEDCBA C、CBEDFA D、不確定 2、線索二叉樹中，判斷p所指向的結點為葉子結點的條件是（ ）。 A、p->LC==NULL && p->RC==NULL B、p->LTag==1 C、p->LC==NULL && p->LTag==0 D、p->LTag==1 && p->RTag==1 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} 4、在下列存儲形式中，（ ）不是樹的存儲形式。 A、雙親表示法 B、孩子鏈表表示法 C、孩子-兄弟表示法 D、順序存儲表示法 5、對二叉樹中的結點進行編號，要求根結點的編號最小，左孩子結點編號比右孩子結點編號小。則應該采用（ ）遍歷方法對其進行編號。 A、先序 B、中序 C、后序 D、層次 6、已知某二叉樹的后序遍歷序列是CEFDBA，中序遍歷序列是CBEDFA。與該二叉樹對應的樹或森林中，葉子的數(shù)目是（ ）個。 A、1 B、2 C、3 D、4 7、某二叉樹中有60個葉子結點，則該二叉樹中度為2的結點個數(shù)為（ ）。 A、59 B、60 C、61 D、不一定 8、哈夫曼樹的帶權路徑長度等于其中所有結點的帶權路徑之和。 9、給定二叉樹的先序、中序和后序遍歷序列中的兩個，就可以唯一確定一棵二叉樹。 10、在葉子數(shù)目和權值相同的所有二叉樹中，帶權路徑長度最小的樹一定是哈夫曼樹。 11、將一棵樹轉成二叉樹，根結點一定沒有右子樹。 12、一棵哈夫曼樹中不存在度為1的結點。 13、在葉子數(shù)目和權值相同的所有二叉樹中，帶權路徑長度最小的樹一定是完全二叉樹。 14、先序線索二叉樹中，某結點的后繼一定在左子樹上。 15、有10個葉子結點的哈夫曼樹，總結點個數(shù)是 。 16、將一棵樹轉換為二叉樹時，遵循的規(guī)則是左孩子、 。 17、用權值{1,2,3,4,5}構造一棵哈夫曼樹，則該樹的帶權路徑長度為 。 18、假設T是一棵高度為5的二叉樹,T中只有度為0和度為2的結點，那么T樹最少應該有 個結點。 19、樹的后根遍歷，相當于對應二叉樹的 遍歷。 20、含有100個結點的樹有 條邊。 第七章 圖（總時長：102分26秒） 第1講 圖的基本概念（總時長：12分20秒）隨堂測驗 1、一個有n個頂點的有向圖最多有 邊 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有n個頂點的有向圖至少應有 弧才能確保是一個強連通圖。 A、n-1 B、n C、n(n-1) D、n(n-1)/2 3、在一個無向圖中，所有頂點的度之和等于邊條數(shù)的 倍。 4、具有6個頂點的無向圖至少應有 條邊才能確保是一個連通圖。 5、一個有向圖G中所有頂點的入度之和是所有頂點出度之和的 倍。 第2講 圖的存儲結構（總時長：12分28秒）隨堂測驗 1、對于一個n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（） A、n B、n(n-1) C、http://img2.ph.126.net/M6JqsehvN6UBbvuGOAL_2g==/6608661917747811041.png D、http://img1.ph.126.net/wFOgLwacOK2bc2CF_bv7Sw==/6631367932373803222.png 2、有向圖的鄰接矩陣一定是對稱矩陣。（） 3、用鄰接矩陣存儲無向圖G時，其第i行中1的個數(shù)與第i列中1的個數(shù)相等。（） 4、對于一個有n個頂點，e條邊的無向圖，若采用鄰接表表示，則表頭結點數(shù)組的大小為 。 5、對于一個有n個頂點，e條邊的無向圖，若采用鄰接表表示，則邊結點有 個。 6、用鄰接矩陣存儲有向圖G時，其第i列的所有元素之和等于該頂點的 。 第3講 圖的遍歷（總時長：17分05秒）隨堂測驗 1、如果從一個無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索即可訪問所有頂點,則該圖一定是( ) A、完全圖 B、連通圖 C、有回路 D、森林 2、圖的深度優(yōu)先遍歷類似于樹的（ ）遍歷 A、先序遍歷 B、中序遍歷 C、后序遍歷 D、層次遍歷 3、圖的廣度優(yōu)先遍歷類似于樹的（ ）遍歷 A、先序遍歷 B、中序遍歷 C、后序遍歷 D、層次遍歷 第4講 圖的連通性（總時長：11分36秒）隨堂測驗 1、任何一個連通圖（ ）生成樹。 A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 2、Prim算法適合求（ ）的最小生成樹。 A、邊稠密連通網 B、邊稀疏連通網 C、邊稠密無向網 D、邊稀疏無向網 3、對于n個頂點的連通圖G來說，如果其中的某個子圖有n個頂點，n-1條邊，則該子圖一定是G的生成樹。（ ） 4、對于n個頂點的連通圖而言，它的生成樹一定有 條邊。 第5講 有向無環(huán)圖應用——拓撲排序（總時長：12分37秒）隨堂測驗 1、若一個有向圖中的頂點不能排成一個拓撲序列，則可斷定該有向圖（ ） A、是個有向無環(huán)圖 B、是個含有回路的有向圖 C、含有多個入度為0的頂點 D、是個強連通圖 2、任何有向無環(huán)圖的頂點都可以排成拓撲排序序列，且拓撲排序序列唯一（ ） 3、在ＡＯＶ網中，頂點表示 。 第6講 有向無環(huán)圖應用——關鍵路徑（總時長：15分21秒）隨堂測驗 1、關鍵路徑是ＡＯE網中（?。? A、從源點到匯點的最長路徑 B、從源點到匯點的最短路徑 C、最長回路 D、最短回路 2、關鍵活動若不能按期完成就會影響整個工程的完成時間，若某些關鍵活動能提前完成，將可能使整個工程提前完成。（） 3、在ＡＯE網中，關鍵路徑上的活動稱為 。 第7講 最短路徑（總時長：16分28秒）隨堂測驗 1、求最短路徑的Dijkstra算法的時間復雜度為（ ） n為圖中頂點數(shù)，e為圖中邊數(shù)。 A、O（n） B、O（n+e） C、O（http://img2.ph.126.net/M6JqsehvN6UBbvuGOAL_2g==/6608661917747811041.png） D、O(ne) 2、求最短路徑的Dijkstra算法不適用于有回路的有向網（ ） 第七章 單元測驗 1、在一個圖中，所有頂點的度之和是所有邊數(shù)的 ( )倍。 A、1/2 B、1 C、2 D、3 2、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的( )倍。 A、1/2 B、1 C、2 D、4 3、一個有n個頂點的無向圖最多有( )條邊。 A、n B、n*(n-1) C、( n*(n-1) ) / 2 D、2*n 4、在一個具有n個頂點的無向圖中，要連通全部頂點至少需要 ( )條邊。 A、n B、n+` C、n-1 D、n/2 5、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是( )。 A、n B、n*n C、2*(n-1) D、n-1 6、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表示，鄰接表中的結點總數(shù)是( )。 A、e/2 B、2 C、2*e D、n+e 7、以下說法錯誤的是( )。 A、用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結點個數(shù)有關，而與圖的邊數(shù)無關。 B、鄰接表只能用于有向圖的存儲，而鄰接矩陣對于有向圖和無向圖的存儲都適用。 C、存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的下（或上）三角部分就可以了 D、用鄰接矩陣M表示圖，判定任意兩個結點Vi和Vj之間是否有長度為n的路徑相連，則只要檢查M的n次方后，第 i行第j列的元素是否為0即可。 8、已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發(fā)的方法是（ ）。 A、將矩陣第i行刪除，后序行上移 B、將矩陣第i列刪除，后序列左移 C、將矩陣第i行上的元素全部置0 D、將矩陣第i列上的元素全部置0 9、某圖的鄰接表存儲結構如下圖所示， 則從6號點出發(fā)，深度優(yōu)先遍歷的序列是（ ） http://nos./edu-image/D2DD40A2A51F30042A38EB4444A3A1EC.png?imageView&thumbnail=520x520&quality=100 A、6-5-2-1-4-3 B、6-5-1-2-4-3 C、6-5-1-4-3-2 D、6-5-2-1-4-3 10、某圖的鄰接矩陣存儲結構如下圖所示， 則從6號點出發(fā)，廣度優(yōu)先遍歷的序列是（ ） http://nos./edu-image/BF593EA8983E495C7C1D1672D80B8ACD.png?imageView&thumbnail=520x520&quality=100 A、6-1-2-5-4-3 B、6-1-2-4-5-3 C、6-5-1-4-3-2 D、6-5-2-1-4-3 11、關鍵路徑上的活動都是關鍵活動，它們是否按時完成會影響工期。 12、求稀疏圖的最小生成樹，用克魯斯卡爾算法來求解較好。 13、求稠密圖的最小生成樹，用普里姆算法來求解較好。 14、迪杰斯特拉算法求最短路徑時，是按照路徑長度遞增的順序求解的。 15、一個有向圖的拓撲排序只有一個。 16、每一個有向圖肯定至少有一個拓撲排序。 17、具有6個頂點的無向圖至少應有6條邊才能確保是一個連通圖。 18、非關鍵活動，可以無限期延遲。 19、圖的存儲結構主要有鄰接矩陣和________兩種。 20、對具有n個頂點的圖其生成樹有且僅有________條邊。 21、在有向圖的鄰接矩陣上，第i行中的非零且非無窮元素個數(shù)是第i個結點的 。 22、如果n個頂點的圖是一個環(huán)，則它有 棵生成樹。 23、關鍵路徑是從源點到匯點的 路徑。 24、稠密圖采用 存儲較省空間 25、稀疏圖采用 存儲較省空間。 第八章 查找（總時長：73分53秒） 第1講 查找的基本概念（總時長：10分31秒）隨堂測驗 1、采用順序查找法查找長度為n的線性表時，平均查找長度為 。 A、n B、http://img2.ph.126.net/-M_9Da8fEUz6G9tE-XsKZQ==/1367968386914100383.png C、http://img1.ph.126.net/HMfttKVyCDmu9c37BmrHkQ==/6608646524585872888.png D、http://img2.ph.126.net/iZ7VTXlsFLHkQrfz8Gu5ZA==/6630450939676396550.png 2、通常將 作為衡量一個查找算法效率優(yōu)劣的標準。 A、平均查找長度 B、比較次數(shù) C、WPL D、ASL 3、順序查找方法只能在順序存儲結構上進行。（ ） 4、順序查找含n個元素的順序表，若查找成功，則比較關鍵字的次數(shù)最多為 次。 5、順序查找含n個元素的順序表，若查找不成功，則比較關鍵字的次數(shù)為 次。 第2講 基于線性表的查找法（總時長：10分44秒）隨堂測驗 1、對列表進行折半查找時，要求列表必須 。 A、順序存儲 B、鏈式存儲 C、順序存儲且元素按關鍵字有序存儲 D、鏈式存儲且元素按關鍵字有序存儲 2、當采用分塊查找時，數(shù)據(jù)的組織方式要求 。 A、數(shù)據(jù)分成若干塊，每塊內元素有序 B、數(shù)據(jù)分成若干塊，每塊內元素不必有序，但塊間必須有序，且每塊內最大（或最?。┑臄?shù)據(jù)組成索引塊； C、數(shù)據(jù)分成若干塊 D、數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中元素個數(shù)相等。 3、有一個有序表{1,3,9,12,32,41，45,62,75,77,82,95,99}當采用折半查找法查找關鍵字為82的元素時，需經過 次比較后查找成功。 A、1 B、2 C、4 D、8 4、折半查找可以在有序的雙向鏈表上進行。（ ） 第3講 樹表式查找方法——二叉排序樹（總時長：12分08秒）隨堂測驗 1、如圖所示的二叉排序樹，，起查找成功時的平均查找長度是 。 http://nos./edu-image/31F70518C081A3CD1353C5390AD57C07.PNG?imageView&thumbnail=520x520&quality=100 A、http://img1.ph.126.net/jjYLOzFUhr270fsiwjBxzA==/6630759902444154709.png B、http://img2.ph.126.net/b-eaZs-XKCyN-P8zijOonw==/6619460221445259131.png C、http://img2.ph.126.net/aFDjsedD2YYrCpRddBCSpA==/6619454723887166129.png D、http://img2.ph.126.net/uOO2qS8CnjGqMT06WaVEmA==/6631922086234108544.png 2、在一棵平衡二叉樹中，每個結點的平衡因子的取值范圍是 。 A、-1——1 B、-2——2 C、1——2 D、0——1 3、查找效率最高的二叉排序樹是平衡二叉排序樹。（ ） 4、在二叉排序樹中新插入的結點總是作為葉子結點來插入的。（ ） 5、在二叉排序樹中新插入的結點總是處于最底層。（ ） 6、每個結點的關鍵字都比左孩子關鍵字大，比右孩子關鍵字小，這樣的二叉樹都是二叉排序樹。（ ） 第4講 計算式查找法——哈希表的構造（總時長：16分27秒）隨堂測驗 1、將10個元素散列到10000000個單元的哈希表中，則 產生沖突。 A、一定會 B、一定不會 C、仍可能會 D、以上都不對 2、在哈希查找中，可用 來處理沖突。 A、除留余數(shù)法 B、數(shù)字分析法 C、線性探測散列法 D、數(shù)字分析法 3、設哈希表長度m=12，哈希函數(shù)為H（key）=key mod 11.表中已經有4個結點分別為H（15）=4，H(38)=5, H（61）=6，H(84)=7,其余地址為空。如果用二次探測再散列處理沖突，則關鍵字為49的結點地址為 。 A、8 B、3 C、5 D、9 4、設哈希表長度m=14,哈希函數(shù)H（key）=key mod p,則p最好取 。 第5講 哈希法的性能分析（總時長：9分02秒）隨堂測驗 1、若采用鏈地址法構造哈希表并處理沖突，哈希函數(shù)為H（key）=key mod 17，則需要 個鏈表。 A、17 B、16 C、13 D、不確定 2、假設有k個關鍵字互為同義詞，若用線性探測再散列法將這k個關鍵字存入哈希表中，至少要進行 次定址。 A、k-1 B、k C、k+1 D、k(k+1)/2 3、哈希表的查找性能 。 A、與處理沖突的方法有關而與表的長度無關 B、與處理沖突的方法無關而與表的長度有關 C、與處理沖突的方法無關而與裝填因子有關 D、與處理沖突的方法有關，與裝填因子有關 題目來源 中國大學mooc答案題庫
|
|
|
