MOOC 數(shù)據(jù)結(jié)構(gòu)與算法-西安郵電大學(xué) 中國大學(xué)慕課答案

MOOC數(shù)據(jù)結(jié)構(gòu)與算法-西安郵電大學(xué)中國大學(xué)慕課答案測驗11、問題：數(shù)據(jù)的邏輯結(jié)構(gòu)有幾種？選項：A、4B、3C、2D、1正確答案:【4】2、問題：數(shù)據(jù)的存儲結(jié)構(gòu)包括？選項：A、線性結(jié)構(gòu)和非線性結(jié)構(gòu)B、靜態(tài)結(jié)構(gòu)和非靜態(tài)結(jié)構(gòu)C、順序結(jié)構(gòu)和非順序結(jié)構(gòu)D、動態(tài)結(jié)構(gòu)和非動態(tài)結(jié)構(gòu)正確答案:【順序結(jié)構(gòu)和非順序結(jié)構(gòu)】測驗11、問題：數(shù)據(jù)的邏輯結(jié)構(gòu)包括？選項：A、線性結(jié)構(gòu)和非線性結(jié)構(gòu)B、順序結(jié)構(gòu)和非順序結(jié)構(gòu)C、靜態(tài)結(jié)構(gòu)和非靜態(tài)結(jié)構(gòu)D、動態(tài)結(jié)構(gòu)和非動態(tài)結(jié)構(gòu)正確答案:【線性結(jié)構(gòu)和非線性結(jié)構(gòu)】測驗1、問題：數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及相關(guān)運算。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：數(shù)據(jù)的邏輯結(jié)構(gòu)和機器無關(guān)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：時間復(fù)雜度和頻度是一樣的。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：一個算法包含的循環(huán)嵌套的層數(shù)越多，該算法的時間復(fù)雜度越高。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)1在線練習(xí)11、問題：在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）的結(jié)構(gòu)。選項：A、邏輯B、存儲C、邏輯和存儲D、物理正確答案:【邏輯】2、問題：數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指（）。選項：A、數(shù)據(jù)的存儲結(jié)構(gòu)B、數(shù)據(jù)結(jié)構(gòu)C、數(shù)據(jù)的邏輯結(jié)構(gòu)D、數(shù)據(jù)元素之間的關(guān)系正確答案:【數(shù)據(jù)的存儲結(jié)構(gòu)】3、問題：在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將之分為（）結(jié)構(gòu)。選項：A、動態(tài)和靜態(tài)結(jié)構(gòu)B、緊湊和非緊湊結(jié)構(gòu)C、線性和非線性結(jié)構(gòu)D、內(nèi)部和非內(nèi)部結(jié)構(gòu)正確答案:【線性和非線性結(jié)構(gòu)】4、問題：在數(shù)據(jù)結(jié)構(gòu)中，從存儲上可以將之分為（）結(jié)構(gòu)。選項：A、動態(tài)和靜態(tài)結(jié)構(gòu)B、緊湊和非緊湊結(jié)構(gòu)C、順序和非順序結(jié)構(gòu)D、線性和非線性結(jié)構(gòu)正確答案:【順序和非順序結(jié)構(gòu)】5、問題：算法的時間復(fù)雜度取決于（）。選項：A、問題的規(guī)模B、待處理數(shù)據(jù)的初態(tài)C、問題的規(guī)模以及待處理數(shù)據(jù)的初態(tài)D、沒有正確答案正確答案:【問題的規(guī)模以及待處理數(shù)據(jù)的初態(tài)】6、問題：某算法的時間復(fù)雜度是O(n^2)，表明該算法的（）。選項：A、執(zhí)行時間與n^2成正比B、問題規(guī)模是n^2C、執(zhí)行時間等于n^2D、問題規(guī)模與n^2成正比正確答案:【執(zhí)行時間與n^2成正比】7、問題：衡量算法效率優(yōu)劣的不包括（）。選項：A、正確性和可讀性B、健壯性/魯棒性C、高效率與低存儲D、現(xiàn)實性正確答案:【現(xiàn)實性】8、問題：算法指（）。選項：A、計算方法B、排序方法C、解決問題的步驟序列D、調(diào)度方法正確答案:【解決問題的步驟序列】9、問題：下面的程序段時間復(fù)雜度為（）。for(i=1;in;i++)for(j=1;jn;j++)x=x+1;選項：A、O(2n)B、O(n)C、O(n^2)D、O(log2n)正確答案:【O(n^2)】10、問題：算法效率分析的兩個主要方面是（）。選項：A、空間復(fù)雜度和時間復(fù)雜度B、正確性和簡明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性正確答案:【空間復(fù)雜度和時間復(fù)雜度】11、問題：有如下遞歸函數(shù)fact(n)，分析其時間復(fù)雜度為（）。intfact(intn){if(n=1)return1;elsereturn(n*fact(n-1));}選項：A、O(n)B、O(1)C、O(n^2)D、O(logn)正確答案:【O(n)】12、問題：下面程序段的時間復(fù)雜度為（）。for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;選項：A、O(n*m)B、O(n^2)C、O(m^2)D、O(1)正確答案:【O(n*m)】13、問題：下面程序段的時間復(fù)雜度為（）。voidsum(intn)//n為正整數(shù){intp=1,sum=0,i;for(i=1;i=n;i++){p*=i;sum+=p;}}選項：A、O()B、O(n)C、O(1)D、O(n^2)正確答案:【O(n)】14、問題：順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。選項：A、正確B、錯誤正確答案:【錯誤】15、問題：算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實際上就是程序了。選項：A、正確B、錯誤正確答案:【錯誤】16、問題：鏈?zhǔn)酱鎯Φ膬?yōu)點是可以隨機存儲。選項：A、正確B、錯誤正確答案:【錯誤】17、問題：在相同的數(shù)據(jù)規(guī)模n下，復(fù)雜度為O(n)的算法在時間上總是優(yōu)于復(fù)雜度為O()的算法。選項：A、正確B、錯誤正確答案:【正確】18、問題：數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合。選項：A、正確B、錯誤正確答案:【正確】19、問題：數(shù)據(jù)的存儲結(jié)構(gòu)表示的是數(shù)據(jù)元素之間的邏輯關(guān)系。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：順序表是指按照順序方式進行存儲的線性表。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：單鏈表的插入、刪除效率優(yōu)于順序表。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：單鏈表的頭插建立算法也稱為反向建立單鏈表。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：帶尾指針的循環(huán)鏈表比帶頭指針的循環(huán)鏈表更便于運算。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在雙向鏈表中查找某一結(jié)點的前驅(qū)或者后繼，都非常方便。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)2在線練習(xí)21、問題：下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點（）。選項：A、隨機存取B、插入運算方便C、刪除運算方便D、可方便地用于各種邏輯結(jié)構(gòu)的存儲表示正確答案:【隨機存取】2、問題：下面關(guān)于線性表敘述中錯誤的是（）。選項：A、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B、線性表采用順序存儲，便于進行插入和刪除操作。C、線性表采用鏈?zhǔn)酱鎯Γ槐卣加靡黄B續(xù)的存儲單元。D、線性表采用鏈?zhǔn)酱鎯?，便于插入和刪除操作。正確答案:【線性表采用順序存儲，便于進行插入和刪除操作?！?、問題：若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。選項：A、順序表B、雙鏈表C、帶頭結(jié)點的雙循環(huán)鏈表D、單循環(huán)鏈表正確答案:【順序表】4、問題：設(shè)某順序表中第一個元素的存儲地址是Base，下限值為1，每個結(jié)點占m個單元，則第i個結(jié)點的存儲地址為（）。選項：A、Base+(i+1)×mB、Base+i×mC、Base+(i-1)×mD、Base-i×m正確答案:【Base+(i-1)×m】5、問題：某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。選項：A、單鏈表B、僅有頭指針的單循環(huán)鏈表C、雙鏈表D、僅有尾指針的單循環(huán)鏈表正確答案:【僅有尾指針的單循環(huán)鏈表】6、問題：設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用()最節(jié)省時間。選項：A、單鏈表B、帶尾指針的單循環(huán)鏈表C、單循環(huán)鏈表D、帶頭結(jié)點的雙循環(huán)鏈表正確答案:【帶頭結(jié)點的雙循環(huán)鏈表】7、問題：鏈表不具有的特點是（）。選項：A、插入、刪除不需要移動元素B、可隨機訪問任意元素C、不必事先估計存儲空間D、所需空間與線性長度成正比正確答案:【可隨機訪問任意元素】8、問題：線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（）。選項：A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)或不連續(xù)都可以正確答案:【連續(xù)或不連續(xù)都可以】9、問題：靜態(tài)鏈表中指針表示的是（）。選項：A、內(nèi)存地址B、數(shù)組下標(biāo)C、下一元素在數(shù)組中的下標(biāo)D、左、右孩子地址正確答案:【下一元素在數(shù)組中的下標(biāo)】10、問題：若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（）。選項：A、O(0)B、O(1)C、O(n)D、O()正確答案:【O(n)】11、問題：對于順序表，訪問結(jié)點和刪除結(jié)點的時間復(fù)雜度分別為（）。選項：A、O(n)O(n)B、O(n)O(1)C、O(1)O(n)D、O(1)O(1)正確答案:【O(1)O(n)】12、問題：在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是（）。選項：A、p-next=s;s-next=p-next;B、s-next=p-next;p-next=s;C、p-next=s;p-next=s-next;D、p-next=s-next;p-next=s;正確答案:【s-next=p-next;p-next=s;】13、問題：對于一個帶頭結(jié)點的單鏈表，其頭指針為head，判定該表為空表的條件是（）。選項：A、head==NULLB、head→next==headC、head→next==NULLD、head!=NULL正確答案:【head→next==NULL】14、問題：將兩個各有n個元素的有序表合并成一個有序表，其最少的比較次數(shù)是（）。選項：A、nB、2n-1C、2nD、n-1正確答案:【n】15、問題：在雙向鏈表中，在p所指向的結(jié)點前插入一個q所指向的結(jié)點，相應(yīng)的操作語句是（）。注：雙向鏈表的結(jié)點結(jié)構(gòu)為(prior，data，next)。選項：A、p-prior=q;q-next=p;p-prior-next=q;q-prior=q;B、p-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior;C、q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q;D、q-prior=p-prior;q-next=q;p-prior=q;p-prior=q;正確答案:【q-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q;】16、問題：線性表（a1,a2,…,an）以鏈?zhǔn)椒绞酱鎯r，訪問第i個元素的時間復(fù)雜度為（）選項：A、O（i）B、O（1）C、O（n）D、O（i-1）正確答案:【O（n）】17、問題：頭指針為H的循環(huán)單鏈表中尾結(jié)點P的特點是（）。選項：A、P-next=HB、P-next=H-nextC、P=HD、P=H-next正確答案:【P-next=H】18、問題：兩個指針P和Q，分別指向單鏈表的兩個結(jié)點，P是Q的前驅(qū)結(jié)點的條件是（）。選項：A、P-next==Q-nextB、P-next==QC、Q-next==PD、P==Q正確答案:【P-next==Q】19、問題：在單鏈表中，增加頭結(jié)點的目的是（）。選項：A、使單鏈表至少有一個結(jié)點B、標(biāo)志表中首結(jié)點的位置C、鏈表判空、插入第一個結(jié)點以及刪除第一個結(jié)點等運算方便D、說明該單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)正確答案:【鏈表判空、插入第一個結(jié)點以及刪除第一個結(jié)點等運算方便】20、問題：下面關(guān)于線性表的敘述中，錯誤的是（）。選項：A、順序表必須占一片地址連續(xù)的存儲單元B、順序表可以隨機存取任一元素C、鏈表不必占用一片地址連續(xù)的存儲單元D、鏈表可以隨機存取任一元素正確答案:【鏈表可以隨機存取任一元素】21、問題：設(shè)p為指向長度為n的單循環(huán)鏈表上某結(jié)點的指針，則找到p的直接前驅(qū)（）。選項：A、找不到B、時間復(fù)雜度為O（1）C、時間復(fù)雜度為O（n）D、次數(shù)約為n正確答案:【時間復(fù)雜度為O（n）】22、問題：以下關(guān)于線性表的論述，不正確的是（）。選項：A、線性表中的元素可以是數(shù)字、字符、記錄等不同類型。B、順序表中包含的元素個數(shù)是有限的。C、線性表中的每個結(jié)點都有且僅有一個直接前趨和一個直接后繼。D、存在這樣的線性表，即表中沒有任何結(jié)點。正確答案:【線性表中的每個結(jié)點都有且僅有一個直接前趨和一個直接后繼?！?3、問題：在（）的運算中，使用順序表比鏈表好。選項：A、插入B、根據(jù)序號查找C、刪除D、根據(jù)元素查找正確答案:【根據(jù)序號查找】24、問題：靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。選項：A、正確B、錯誤正確答案:【正確】25、問題：線性表的特點是每個元素都有一個前驅(qū)和一個后繼。選項：A、正確B、錯誤正確答案:【錯誤】26、問題：若長度為n的線性表采用順序存儲結(jié)構(gòu)，找到其中第i個元素的時間復(fù)雜度為O(n)。選項：A、正確B、錯誤正確答案:【錯誤】27、問題：已知帶頭結(jié)點的雙向循環(huán)鏈表L，判斷其為空表的條件是L-next==LL-prior==L。選項：A、正確B、錯誤正確答案:【正確】28、問題：順序表的插入、刪除運算更方便。選項：A、正確B、錯誤正確答案:【錯誤】29、問題：鏈表的性能優(yōu)于順序表。選項：A、正確B、錯誤正確答案:【錯誤】30、問題：順序表適宜于順序存取，而鏈表適宜于隨機存取。選項：A、正確B、錯誤正確答案:【錯誤】31、問題：順序表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。選項：A、正確B、錯誤正確答案:【錯誤】32、問題：插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。選項：A、正確B、錯誤正確答案:【錯誤】33、問題：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：棧的特點是先進先出。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：雙端棧有效地共享了存儲空間。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：漢諾塔問題可以使用遞歸算法來完成。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：迷宮問題的非遞歸實現(xiàn)借助的是棧這種結(jié)構(gòu)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：隊列的特點是先進后出。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：采用鏈?zhǔn)浇Y(jié)構(gòu)存儲的隊列稱之為鏈隊列。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在表達式求值問題中，我們使用運算符棧和運算數(shù)棧協(xié)同工作完成整個表達式的求解過程。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)3單元測試11、問題：棧和隊列的共同點是（）。選項：A、都是先進先出B、都是先進后出C、只允許在端點處插入和刪除元素D、沒有共同點正確答案:【只允許在端點處插入和刪除元素】2、問題：棧和隊都是（）。選項：A、順序存儲的線性結(jié)構(gòu)B、鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)C、限制存取點的線性結(jié)構(gòu)D、限制存取點的非線性結(jié)構(gòu)正確答案:【限制存取點的線性結(jié)構(gòu)】3、問題：依照六個元素6，5，4，3，2，1的順序進棧，下列哪一個出棧序列不可能（）。選項：A、543612B、453216C、346521D、234156正確答案:【346521】4、問題：設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個元素出棧后隨即進入隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是()。選項：A、6B、4C、3D、2正確答案:【3】5、問題：設(shè)計一個判別表達式中括號是否匹配出現(xiàn)的算法，采用（）的數(shù)據(jù)結(jié)構(gòu)最佳。選項：A、順序表B、隊列C、單鏈表D、棧正確答案:【?！?、問題：表達式a*(b+c)-d的后綴表達式是(）。選項：A、bc+a*d-B、abc+*d-C、ab*c+d-D、dabc+*-正確答案:【abc+*d-】7、問題：函數(shù)遞歸調(diào)用時，處理參數(shù)及返回地址需要用一種（）的數(shù)據(jù)結(jié)構(gòu)。選項：A、隊列B、多維數(shù)組C、棧D、線性表正確答案:【?！?、問題：若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為3和1，當(dāng)從隊列中刪除一個元素再加入兩個元素后，rear和front的值為()。選項：A、0和5B、2和4C、5和2D、5和1正確答案:【5和2】9、問題：最大容量為n的循環(huán)隊列，隊尾指針為rear，隊頭指針為front，則隊空的條件是（）。選項：A、(rear+1)%n==frontB、rear==frontC、rear+1==frontD、(rear-l)%n==front正確答案:【rear==front】10、問題：假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素,其頭、尾指針分別為front和rear，front指示實際的隊頭元素，rear指向?qū)嶋H隊尾元素的下一個元素位置，則當(dāng)前隊列中的元素個數(shù)為（）。選項：A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front+1)%m正確答案:【(rear-front+m)%m】11、問題：用帶頭結(jié)點的表長大于1的單鏈表表示隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時()。選項：A、僅修改隊頭指針B、僅修改隊尾指針C、隊頭、隊尾指針都要修改D、隊頭,隊尾指針都可能要修改正確答案:【僅修改隊頭指針】12、問題：下列說法正確的是（）。(1)只有使用了局部變量的遞歸函數(shù)在轉(zhuǎn)換成非遞歸函數(shù)時才必須使用棧。(2)隊列是插入與刪除操作在表的兩端進行的線性表，具有先進后出的特點。(3)隊列是一端進行刪除另外一端進行插入的線性表。(4)循環(huán)隊列也存在空間溢出問題。選項：A、(1)(2)(4)B、(1)(2)(3)C、(3)(4)D、(1)(2)正確答案:【(3)(4)】13、問題：以下程序的輸出結(jié)果為（）。intf(intx){return(x0)?x*f(x-1):2;}voidmain(){inti;i=f(f(1));printf(%d,i);}選項：A、2B、4C、8D、無限遞歸正確答案:【4】14、問題：若一個棧以數(shù)組V[0..n-1]存儲，初始棧頂指針top為n，則下面關(guān)于元素x進棧的正確操作是()。選項：A、top=top+1;V[top]=x;B、V[top]=x;top=top+1;C、top=top-1;V[top]=x;D、V[top]=x;top=top-1;正確答案:【top=top-1;V[top]=x;】15、問題：一個遞歸算法必須包括（）。選項：A、遞歸體B、遞歸條件和遞歸體C、迭代部分D、終止條件和迭代部分正確答案:【遞歸條件和遞歸體】16、問題：輸入序列為ABC，想要得到CBA的輸出結(jié)果，可以經(jīng)過的棧操作為（）。選項：A、push,pop,push,pop,push,popB、push,push,push,pop,pop,popC、push,push,pop,pop,push,popD、push,pop,push,push,pop,pop正確答案:【push,push,push,pop,pop,pop】17、問題：一個棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（）。選項：A、23415B、54132C、23145D、15432正確答案:【54132】18、問題：一個棧的輸入序列為1,2,3,…,n，若輸出序列的第一個元素是i，則輸出第j（1=j=i）個元素是（）。選項：A、i-j-1B、i-j+1C、j-i+1D、不確定的正確答案:【i-j+1】19、問題：在雙向鏈表（結(jié)點包括：data,prior,next）中，刪除指針p所指向的結(jié)點時須修改指針（）。選項：A、p-prior-next=p-next;p-next-prior=p-prior;B、p-prior=p-prior-prior;p-prior-next=p;C、p-next-prior=p;p-next=p-next-next;D、p-next=p-prior-prior;p-prior=p-next-next;正確答案:【p-prior-next=p-next;p-next-prior=p-prior;】20、問題：以下說法錯誤的是（）。選項：A、對循環(huán)鏈表來說，從表中任意結(jié)點出發(fā)都能通過前后操作而掃描到整個循環(huán)鏈表。B、對單鏈表來說，只有從頭結(jié)點開始才能掃描表中全部結(jié)點。C、雙向鏈表的特點是找結(jié)點的前趨和后繼都很容易。D、對雙向鏈表來說，結(jié)點*P的存儲位置既存放在其前驅(qū)結(jié)點的后繼指針域中，也存放在它的后繼結(jié)點的前趨指針域中。正確答案:【對循環(huán)鏈表來說，從表中任意結(jié)點出發(fā)都能通過前后操作而掃描到整個循環(huán)鏈表。】21、問題：對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度和在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度分別為（）。選項：A、O(n),O(n)B、O(1),O(n)C、O(1),O(1)D、O(n),O(1)正確答案:【O(1),O(n)】22、問題：循環(huán)隊列存儲在數(shù)組A[0..m-1]中，則入隊時rear應(yīng)該變化為（）。選項：A、rear++;B、rear=(rear+1)mod(m+1);C、rear=(rear+1)modm;D、rear=(rear+1)mod(m-1);正確答案:【rear=(rear+1)modm;】23、問題：當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top=n表示棧空，則每次向這個棧插入一個元素時，首先應(yīng)執(zhí)行（）語句修改top指針。選項：A、top++;B、top--;C、top=0;D、top=n;正確答案:【top--;】24、問題：若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。選項：A、順序表B、雙鏈表C、帶頭結(jié)點的雙循環(huán)鏈表D、單循環(huán)鏈表正確答案:【順序表】25、問題：鏈表不具有的特點是（）。選項：A、插入、刪除不需要移動元素B、可隨機訪問任意元素C、不必事先估計存儲空間D、所需空間與線性長度成正比正確答案:【可隨機訪問任意元素】26、問題：設(shè)某順序表中第一個元素的地址是Base，下標(biāo)從1開始，每個結(jié)點占m個單元，則第i個結(jié)點的地址為（）。選項：A、Base+(i+1)×mB、Base+i×mC、Base+(i-1)×mD、Base-i×m正確答案:【Base+(i-1)×m】27、問題：在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;in;i++)for(j=1;jn;j++)x=x+1;選項：A、O(2n)B、O(n)C、O(n^2)D、O(log2n)正確答案:【O(n^2)】28、問題：數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指（）。選項：A、數(shù)據(jù)的存儲結(jié)構(gòu)B、數(shù)據(jù)結(jié)構(gòu)C、數(shù)據(jù)的邏輯結(jié)構(gòu)D、數(shù)據(jù)元素之間的關(guān)系正確答案:【數(shù)據(jù)的存儲結(jié)構(gòu)】29、問題：消除遞歸不一定需要使用棧，此說法（）。選項：A、正確B、錯誤正確答案:【正確】30、問題：兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）選項：A、正確B、錯誤正確答案:【正確】31、問題：順序棧因為是順序存儲，所以可以隨機存取棧中任意元素。（）選項：A、正確B、錯誤正確答案:【錯誤】32、問題：任何一個遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）選項：A、正確B、錯誤正確答案:【正確】33、問題：兩順序棧共享空間，也存在空間溢出問題。（?）選項：A、正確B、錯誤正確答案:【正確】34、問題：棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。（）選項：A、正確B、錯誤正確答案:【正確】35、問題：棧和隊列的存儲方式，既可以是順序方式，也可以是鏈?zhǔn)椒绞?。（）選項：A、正確B、錯誤正確答案:【正確】36、問題：線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。選項：A、正確B、錯誤正確答案:【正確】37、問題：順序表適宜于順序存取，而鏈表適宜于隨機存取。選項：A、正確B、錯誤正確答案:【錯誤】38、問題：順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：串是一種特殊的線性表。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：串的簡單模式匹配算法的時間復(fù)雜度達到平方階。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：KMP算法最終只需要討論模式串本身就可以。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：模式串a(chǎn)babc對應(yīng)的next值為01123。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)4在線練習(xí)41、問題：下面關(guān)于串的敘述不正確的是（）。選項：A、串是字符的有限序列B、模式匹配是串的一種重要運算C、空串是由空格構(gòu)成的串D、串可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯φ_答案:【空串是由空格構(gòu)成的串】2、問題：串是一種特殊的線性表，其特殊性體現(xiàn)在（）。選項：A、順序存儲B、數(shù)據(jù)元素是字符C、鏈?zhǔn)酱鎯、邏輯結(jié)構(gòu)是線性結(jié)構(gòu)正確答案:【數(shù)據(jù)元素是字符】3、問題：若串S='software',其前綴真子串的數(shù)目是（）。選項：A、10B、9C、8D、7正確答案:【7】4、問題：串的長度是指（）。選項：A、串中所含不同字母的個數(shù)B、串中所含字符的個數(shù)C、串中所含不同字符的個數(shù)D、串中所含非空格字符的個數(shù)正確答案:【串中所含字符的個數(shù)】5、問題：兩個串相等的充要條件是（）。選項：A、兩個字符串中對應(yīng)位置上的字符相等B、兩個字符串存儲形式相同C、兩個字符串的長度相等D、兩個字符串的長度相等且對應(yīng)位置上的字符也相等正確答案:【兩個字符串的長度相等且對應(yīng)位置上的字符也相等】6、問題：設(shè)有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）。選項：A、求子串B、串聯(lián)接C、串的模式匹配D、求串長正確答案:【串的模式匹配】7、問題：已知串S=‘a(chǎn)aab',其next函數(shù)值為（）。選項：A、0123B、1123C、1231D、1211正確答案:【0123】8、問題：模式串‘a(chǎn)babaaababaa'的next函數(shù)值為（）。選項：A、012345678999B、012121111212C、011234223456D、0123012322345正確答案:【011234223456】9、問題：函數(shù)strcmp('stcabuc','stbabuc')的返回值是（）。選項：A、-1B、2C、0D、1正確答案:【1】10、問題：模式串t=‘a(chǎn)bcaabbcabcaabdab'，該模式串的next函數(shù)值為（）。選項：A、01112211123456712B、01102131011021701C、01110013101100701D、01112231123456712正確答案:【01112231123456712】11、問題：假設(shè)空串是任何串的子串，則串S='Computer'的子串個數(shù)是（）。選項：A、9B、36C、37D、8正確答案:【37】12、問題：StrIndex（‘DATASTRUCTURE'，1,‘STR'）=（）。選項：A、3B、7C、5D、9正確答案:【5】13、問題：設(shè)正文串長度為n，模式串長度為m，則模式匹配的KMP算法的時間復(fù)雜度為（）。選項：A、O(m*n)B、O(m+n)C、O(m)D、O(n)正確答案:【O(m+n)】14、問題：StrIndex(‘IndexofString’,1,‘Str’）=()。選項：A、10B、8C、6D、12正確答案:【10】15、問題：SubStr('IlikeUniversity',8,3)的返回值是（）。選項：A、ikeB、UniC、verD、ers正確答案:【Uni】16、問題：設(shè)S=，則LenStr(S)=（）。選項：A、0B、1C、2D、3正確答案:【0】17、問題：設(shè)目標(biāo)串T=aabaababaabaa，模式P=abab，樸素匹配算法的外層循環(huán)進行了()次。選項：A、1B、9C、4D、5正確答案:【5】18、問題：S1='good'，S2='morning'，執(zhí)行函數(shù)SubStr(S2,4,LenStr(S1))后的結(jié)果為()。選項：A、'good'B、'ning'C、'go'D、'morn'正確答案:【'ning'】19、問題：若串S='SOFT'，其子串的數(shù)目最多是（）。選項：A、9B、10C、11D、12正確答案:【11】20、問題：以下論述正確的是（）。選項：A、空串與空格串是相同的B、'tel'是'Telephone'的一個子串C、空串是零個字符的串D、空串的長度等于1正確答案:【空串是零個字符的串】21、問題：設(shè)串S1='IAM'，S2='ASTUDENT'，則ConcatStr(S1,S2)=()。選項：A、'IAM'B、'ASTUDENT'C、'IAMASTUDENT'D、'IAMASTUDENT'正確答案:【'IAMASTUDENT'】22、問題：設(shè)串S1='ABCDEFG'，S2='PQRST',則ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的結(jié)果串為()。選項：A、'BCDEF'B、'BCDEFG'C、'BCPQRST'D、'BCDEFEF'正確答案:【'BCDEFEF'】23、問題：設(shè)有三個串S1、S2和S3，則StrReplace(S1,S2,S3)運算稱作()。選項：A、串連接B、模式匹配C、求子串D、串替換正確答案:【串替換】24、問題：以下論斷正確的是()。選項：A、是空串，空格串B、BEIJING是BEIJING的子串C、something=SomethingD、BIT=BITE正確答案:【是空串，空格串】25、問題：某串的長度小于一個常數(shù)，則采用（）存儲方式最節(jié)省空間。選項：A、鏈?zhǔn)紹、順序C、堆結(jié)構(gòu)D、無法確定正確答案:【順序】26、問題：串是一種數(shù)據(jù)對象特殊的線性表。選項：A、正確B、錯誤正確答案:【正確】27、問題：KMP算法的特點是在模式匹配時指示主串的指針不會回溯。選項：A、正確B、錯誤正確答案:【正確】28、問題：設(shè)模式串的長度為m,目標(biāo)串的長度為n，當(dāng)n≈m且處理只匹配一次的模式時，樸素的匹配（即子串定位函數(shù)）算法所花的時間代價可能會更為節(jié)省。選項：A、正確B、錯誤正確答案:【正確】29、問題：模式串P=‘a(chǎn)baabcac'的next函數(shù)值序列為01122312選項：A、正確B、錯誤正確答案:【正確】30、問題：串的存儲結(jié)構(gòu)有順序串、堆串和塊鏈串三種。選項：A、正確B、錯誤正確答案:【正確】31、問題：如果一個串中所有的字母均在另一個串中出現(xiàn)，則說明前者是后者的子串。選項：A、正確B、錯誤正確答案:【錯誤】32、問題：串中任意個字符組成的子序列稱為該串的子串。選項：A、正確B、錯誤正確答案:【錯誤】33、問題：如果兩個串含有相同的字符，則說明它們相等。選項：A、正確B、錯誤正確答案:【錯誤】34、問題：子串的定位運算稱為串的模式匹配。選項：A、正確B、錯誤正確答案:【正確】35、問題：串'student'和'Student'相等。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：n維數(shù)組可以看成是由“n-1維數(shù)組”的數(shù)組元素構(gòu)成的一維數(shù)組。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：為了節(jié)省存儲空間，我們經(jīng)常對特殊矩陣和稀疏矩陣進行壓縮存儲。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：采用三元組順序表存儲的稀疏矩陣，利用快速轉(zhuǎn)置算法，時間復(fù)雜度可以達到線性階。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：任何一個非空的廣義表其表尾一定還是一個廣義表。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)5在線練習(xí)51、問題：設(shè)有一個10階的對稱矩陣A，采用下三角的壓縮存儲方式，以行序為主序，a[1][1]為第一元素，其存儲地址為1，每個元素占一個地址空間，則a[8][5]的地址為（）。選項：A、13B、33C、18D、40正確答案:【33】2、問題：設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主序存放時，元素A[5][8]的存儲首地址為()。選項：A、BA+141B、BA+180C、BA+222D、BA+225正確答案:【BA+180】3、問題：假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設(shè)每個數(shù)組元素占2個存儲單元，基地址為10，則arry[5][5]的地址為（）。選項：A、808B、818C、1010D、1020正確答案:【818】4、問題：二維數(shù)組A的每個元素都是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放A至少需要（）個字節(jié)。選項：A、90B、180C、240D、540正確答案:【540】5、問題：二維數(shù)組A的元素都是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則A的第8列和第5行共占（）個字節(jié)。選項：A、108B、114C、54D、150正確答案:【108】6、問題：二維數(shù)組A的每個元素都是6個字符組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則如果A按行存放元素A[8][5]的起始地址與A按列存放時元素（）的起始地址一致。選項：A、A[8][5]B、A[3][10]C、A[5][8]D、A[0][9]正確答案:【A[3][10]】7、問題：若對n階對稱矩陣A，下標(biāo)從1開始，以行序為主序方式將其下三角形的元素依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定a[i][j](1≤i，j≤n，且i≤j)的位置k的計算公式為()。選項：A、i(i-1)/2+jB、j(j-1)/2+iC、i(i+1)/2+jD、j(j+1)/2+i正確答案:【j(j-1)/2+i】8、問題：若對n階對稱矩陣A，下標(biāo)從1開始，以列序為主序方式將其上三角形的元素依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定a[i][j](1≤i，j≤n，且i≤j)的位置k的計算公式為()。選項：A、i(i-l)/2+jB、j(j-l)/2+iC、j(j-l)/2+i-1D、i(i-l)/2+j-1正確答案:【j(j-l)/2+i】9、問題：設(shè)二維數(shù)組A[1..m，1..n]（即m行n列）按行存儲在數(shù)組B[1..m*n]中，則二維數(shù)組中元素A[i][j]在一維數(shù)組B中的下標(biāo)為()。選項：A、（i-1）n+jB、（i-1）n+j-1C、i（j-1）D、jm+i-1正確答案:【（i-1）n+j】10、問題：有一個100*90的稀疏矩陣，非零元素（int型）有10個，假設(shè)int型占2個字節(jié)，則用三元組順序表表示該矩陣時所需的字節(jié)數(shù)是（）。選項：A、60B、66C、18000D、33正確答案:【66】11、問題：對稀疏矩陣進行壓縮存儲的目的是（）。選項：A、便于進行矩陣運算B、便于輸入和輸出C、節(jié)省存儲空間D、降低運算的時間復(fù)雜度正確答案:【節(jié)省存儲空間】12、問題：已知廣義表L=（（x,y,z），a，（u，t，w）），從L表中取出原子項t的運算是（）。選項：A、head（tail（tail（L）））B、head（tail（head（tail（L））））C、tail（head（head（tail（L））））D、head（tail(head（tail（tail（L）））））正確答案:【head（tail(head（tail（tail（L）））））】13、問題：廣義表A=(a,b,(c,d),(e,(f,g))),則Head(Tail(Head(Tail(Tail(A)))))的值為（）。選項：A、(g)B、(d)C、cD、d正確答案:【d】14、問題：設(shè)廣義表L=（（a,b,c）），則L的長度和深度分別為（）。選項：A、1和1B、1和3C、1和2D、2和3正確答案:【1和2】15、問題：下面說法不正確的是()。選項：A、廣義表的表頭總是一個廣義表B、一個非空廣義表的表尾總是一個廣義表C、廣義表難以用順序存儲結(jié)構(gòu)進行存儲D、廣義表可以是一個多層次的結(jié)構(gòu)正確答案:【廣義表的表頭總是一個廣義表】16、問題：廣義表運算式Tail(((a,b),(c,d)))的操作結(jié)果是（）。選項：A、(c,d)B、c,dC、((c,d))D、d正確答案:【((c,d))】17、問題：廣義表（a,(b,c),d,e）的表頭為（）。選項：A、aB、a,(b,c)C、(a,(b,c))D、(a)正確答案:【a】18、問題：廣義表（（a,b,c,d））的表尾是（）。選項：A、aB、（）C、（a,b,c,d）D、（b,c,d）正確答案:【（）】19、問題：數(shù)組A[0..4,-3..-1,5..7]中含有元素的個數(shù)（）。選項：A、55B、45C、36D、16正確答案:【45】20、問題：數(shù)組A[0..5,0..6]的每個元素占5個字節(jié)，將其按列序為主序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5][5]的地址是()。選項：A、1175B、1180C、1205D、1210正確答案:【1175】21、問題：將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，元素A[66][65]在B數(shù)組中的位置K為（）。選項：A、198B、195C、197D、196正確答案:【195】22、問題：已知廣義表:A=(a,b),B=(A,A),C=(a,(b,A),B),求tail(head(tail(C)))=()。選項：A、(a)B、(b)C、bD、((a,b))正確答案:【((a,b))】23、問題：在稀疏矩陣的三元組順序表中，每個三元組表示（）。選項：A、矩陣中非零元素的數(shù)據(jù)值B、矩陣中數(shù)據(jù)元素的行號和列號C、矩陣中數(shù)據(jù)元素的行號、列號和數(shù)據(jù)值D、矩陣中非零元素的行號、列號和數(shù)據(jù)值正確答案:【矩陣中非零元素的行號、列號和數(shù)據(jù)值】24、問題：對矩陣進行壓縮存儲后，（）矩陣會失去隨機存取的優(yōu)點。選項：A、對稱矩陣B、三角矩陣C、三對角矩陣D、稀疏矩陣正確答案:【稀疏矩陣】25、問題：經(jīng)常對數(shù)組進行的兩種基本操作是____。選項：A、建立與刪除B、索引和修改C、查找和修改D、查找與索引正確答案:【查找和修改】26、問題：假設(shè)整型數(shù)組A[1..8，-2..6，0..6]，按行優(yōu)先存儲，第一個元素的首地址是78，每個數(shù)組元素占用4個存儲單元，那么元素A[4][2][3]的存儲首地址為____。選項：A、955B、958C、950D、900正確答案:【958】27、問題：tail（head（（（a,b,c,d,e））））=__________。選項：A、aB、bcC、ΦD、(b,c,d,e)正確答案:【(b,c,d,e)】28、問題：從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個元素均屬于n個向量。選項：A、正確B、錯誤正確答案:【正確】29、問題：多維數(shù)組可以看作是一種特殊的線性表。選項：A、正確B、錯誤正確答案:【正確】30、問題：數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。選項：A、正確B、錯誤正確答案:【錯誤】31、問題：一個稀疏矩陣Am*n采用三元組順序表形式表示，若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運算。選項：A、正確B、錯誤正確答案:【錯誤】32、問題：廣義表B=(a,B)=(a,(a,(a,×××,)))的長度為無窮大。選項：A、正確B、錯誤正確答案:【錯誤】33、問題：一個廣義表可以為其它廣義表所共享。選項：A、正確B、錯誤正確答案:【正確】34、問題：一個廣義表的表尾一定還是個廣義表。選項：A、正確B、錯誤正確答案:【錯誤】35、問題：稀疏矩陣中非零元素的個數(shù)遠小于矩陣中元素的總數(shù)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在任何一棵二叉樹中，度為0的結(jié)點數(shù)等于度為2的結(jié)點數(shù)-1。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：完全二叉樹采用順序存儲是比較方便的。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：二叉樹的按層次遍歷算法可以采用遞歸算法實現(xiàn)。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：根據(jù)二叉樹的前序和后序遍歷結(jié)果可以恢復(fù)出一棵二叉樹。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：二叉樹的非遞歸遍歷算法借助了棧這種結(jié)構(gòu)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在線索二叉樹中，有n+1個線索。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在中序線索樹中找結(jié)點的直接前驅(qū)，實際是找左子樹中“最右下端”的結(jié)點。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：樹的雙親表示法采用的是順序存儲結(jié)構(gòu)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：樹的后序遍歷結(jié)果和對應(yīng)的二叉樹的中序遍歷結(jié)果相同。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：哈夫曼樹中葉子結(jié)點數(shù)為n，那么內(nèi)部結(jié)點數(shù)為n+1。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：哈夫曼編碼是前綴編碼。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：哈夫曼編碼是從葉子到根進行編碼的。選項：A、正確B、錯誤正確答案:【正確】單元測試21、問題：樹最適合用來表示的結(jié)構(gòu)是（）。選項：A、元素間的有序結(jié)構(gòu)B、元素間具有分支及層次關(guān)系的結(jié)構(gòu)C、元素間的無序結(jié)構(gòu)D、元素間無聯(lián)系的結(jié)構(gòu)正確答案:【元素間具有分支及層次關(guān)系的結(jié)構(gòu)】2、問題：設(shè)一棵二叉樹的結(jié)點個數(shù)為18，則它的高度至少為（）。選項：A、4B、5C、6D、18正確答案:【5】3、問題：任意一棵二叉樹的葉子結(jié)點在其先序、中序、后序序列中的相對位置（）。選項：A、肯定發(fā)生變化B、有時發(fā)生變化C、肯定不發(fā)生變化D、無法確定正確答案:【肯定不發(fā)生變化】4、問題：判斷線索二叉樹中某結(jié)點p有左孩子的條件是（）。選項：A、p!=NULLB、p-lchild!=NULLC、p-LTag==0D、p-LTag==1正確答案:【p-LTag==0】5、問題：設(shè)森林T中有4棵樹，其結(jié)點個數(shù)分別為n1,n2,n3,n4，那么當(dāng)森林T轉(zhuǎn)換成一棵二叉樹后，則根結(jié)點的右子樹上有（）個結(jié)點。選項：A、n1-1B、n1C、n1+n2+n3D、n2+n3+n4正確答案:【n2+n3+n4】6、問題：由權(quán)值分別為9、2、5、7、4的5個葉子結(jié)點構(gòu)造一棵哈夫曼樹，則該樹的帶權(quán)路徑長度為（）。選項：A、45B、55C、60D、65正確答案:【60】7、問題：設(shè)T是一棵哈夫曼樹，有8個葉結(jié)點，則樹T的高度最高可以是（）。選項：A、4B、6C、8D、10正確答案:【8】8、問題：以下屬于前綴編碼的是（）。選項：A、{0,1101,1110,1100,1111}B、{0,1,01,010,110}C、{00,01,10,11,101}D、{01,00,10,001,110,101}正確答案:【{0,1101,1110,1100,1111}】9、問題：算術(shù)表達式a+b*（c+d/e）轉(zhuǎn)為后綴表達式為（）。選項：A、ab+cde/*B、abcde/+*+C、abcde/*++D、abcde*/++正確答案:【abcde/+*+】10、問題：設(shè)樹T的度為4，其中度為1,2,3和4的結(jié)點個數(shù)分別為4,2,1,1，則T中的葉子數(shù)為（）。選項：A、5B、6C、7D、8正確答案:【8】11、問題：一棵哈夫曼樹共有215個結(jié)點，對其進行哈夫曼編碼，共能得到（）個不同的碼字。選項：A、107B、108C、214D、215正確答案:【108】12、問題：一棵具有N個結(jié)點的二叉樹采用二叉鏈表進行存儲，其中空指針域有()個。選項：A、NB、N+1C、N-1D、不確定正確答案:【N+1】13、問題：深度為K的二叉樹中結(jié)點總數(shù)（）。選項：A、B、C、D、正確答案:【】14、問題：已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹中有（）個葉子結(jié)點。選項：A、10B、12C、11D、13正確答案:【12】15、問題：以數(shù)據(jù)集{4，5，6，7，10，12，18}為葉結(jié)點權(quán)值所構(gòu)造的哈夫曼樹，其帶權(quán)路徑長度為（）。選項：A、165B、155C、160D、170正確答案:【165】16、問題：已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）。選項：A、-A+B*C/DEB、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE正確答案:【-+A*BC/DE】17、問題：若一個具有n個結(jié)點k條邊的無向圖是一個森林（nk），則該森林必有（）棵樹。選項：A、kB、nC、n-kD、n+k正確答案:【n-k】18、問題：一棵二叉樹結(jié)點的（）可唯一確定一棵二叉樹。選項：A、前序序列和中序序列B、前序序列和后序序列C、中序序列D、后序序列正確答案:【前序序列和中序序列】19、問題：設(shè)a=6,b=4,c=2,d=3,e=2，則后綴表達式abc-/de*+的值為（）。選項：A、12B、5.5C、9D、10正確答案:【9】20、問題：若二叉樹有n個結(jié)點，當(dāng)執(zhí)行中序遍歷的遞歸程序時，在最壞情況下為處理遞歸調(diào)用所設(shè)的棧需要（）個單元。選項：A、n-1B、nC、n/2D、n+1正確答案:【n-1】21、問題：具有64個結(jié)點的完全二叉樹的深度為（）。選項：A、5B、6C、7D、8正確答案:【7】22、問題：A，B為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，A在B前的條件是（）。選項：A、A在B右方B、A是B祖先C、A在B左方D、A是B子孫正確答案:【A在B左方】23、問題：把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（）。選項：A、唯一的B、有多種C、有多種，但根結(jié)點都沒有左孩子D、有多種，但根結(jié)點都沒有右孩子正確答案:【唯一的】24、問題：下列陳述正確的是（）。選項：A、二叉樹是度為2的有序樹B、二叉樹中結(jié)點只有一個孩子時無左右之分C、二叉樹中必有度為2的結(jié)點D、二叉樹中最多只有兩棵子樹，且有左右子樹之分正確答案:【二叉樹中最多只有兩棵子樹，且有左右子樹之分】25、問題：在哈夫曼樹中，若編碼長度只允許小于等于4，則除了已確定兩個字符的編碼為0和10外，還可以最多對個字符進行編碼。選項：A、3B、4C、5D、6正確答案:【4】26、問題：若串S='software',其前綴真子串的數(shù)目是（）。選項：A、10B、9C、8D、7正確答案:【7】27、問題：模式串‘a(chǎn)babaaababaa'的next函數(shù)值為（）。選項：A、012345678999B、012121111212C、011234223456D、0123012322345正確答案:【011234223456】28、問題：StrIndex(‘IndexofString’,1,‘Str’）=()。選項：A、10B、9C、8D、7正確答案:【10】29、問題：設(shè)串S1='IAM'，S2='ASTUDENT'，則ConcatStr(S1,S2)=()。選項：A、'IAM'B、'ASTUDENT'C、'IAMASTUDENT'D、'IAMASTUDENT'正確答案:【'IAMASTUDENT'】30、問題：設(shè)有三個串S1、S2和S3，則StrReplace(S1,S2,S3)運算稱作()。選項：A、串連接B、模式匹配C、求子串D、串替換正確答案:【串替換】31、問題：假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100，1..100]，設(shè)每個數(shù)組元素占2個存儲單元，基地址為10，則LOC[5，5]=（）。選項：A、808B、818C、1010D、1020正確答案:【818】32、問題：有一個100*90的稀疏矩陣，非零元素（int型）有10個，假設(shè)int型占2個字節(jié)，則用三元組順序表表示該矩陣時所需的字節(jié)數(shù)是（）。選項：A、60B、66C、18D、33正確答案:【66】33、問題：廣義表（a,(b,c),d,e）的表頭為（）。選項：A、aB、a,(b,c)C、(a,(b,c))D、(a)正確答案:【a】34、問題：數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)（）。選項：A、55B、45C、35D、25正確答案:【45】35、問題：對下述矩陣進行壓縮存儲后，失去隨機存取功能的是（）。選項：A、對稱矩陣B、三角矩陣C、三對角矩陣D、稀疏矩陣正確答案:【稀疏矩陣】36、問題：完全二叉樹一定存在度為1的結(jié)點。選項：A、正確B、錯誤正確答案:【錯誤】37、問題：一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。選項：A、正確B、錯誤正確答案:【錯誤】38、問題：在葉子數(shù)目和權(quán)值相同的所有二叉樹中，帶權(quán)路徑長度最小的樹一定是完全二叉樹。選項：A、正確B、錯誤正確答案:【錯誤】39、問題：給定二叉樹先、中和后序遍歷序列中的兩個，可以唯一確定一棵二叉樹。選項：A、正確B、錯誤正確答案:【錯誤】40、問題：滿二叉樹一定完全是二叉樹。選項：A、正確B、錯誤正確答案:【正確】41、問題：一棵二叉樹中，中序遍歷序列的最后一個結(jié)點，必定是該二叉樹前序遍歷的最后一個結(jié)點。選項：A、正確B、錯誤正確答案:【錯誤】42、問題：在完全二叉樹中，若一個結(jié)點沒有左孩子，則它必然是葉子結(jié)點。選項：A、正確B、錯誤正確答案:【正確】43、問題：具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點。選項：A、正確B、錯誤正確答案:【正確】44、問題：串的存儲結(jié)構(gòu)有順序串、堆串和塊鏈串三種。選項：A、正確B、錯誤正確答案:【正確】45、問題：串中任意個字符組成的子序列稱為該串的子串。選項：A、正確B、錯誤正確答案:【錯誤】46、問題：串'student'和'Student'相等。選項：A、正確B、錯誤正確答案:【錯誤】47、問題：一個廣義表的表頭一定還是個廣義表。選項：A、正確B、錯誤正確答案:【錯誤】48、問題：稀疏矩陣中非零元素的個數(shù)遠小于矩陣中元素的總數(shù)。選項：A、正確B、錯誤正確答案:【正確】49、問題：數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進行插入，刪除等操作。選項：A、正確B、錯誤正確答案:【錯誤】50、問題：多維數(shù)組可以看作是一種特殊的線性表。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：圖中任意兩個頂點之間有路徑相通我們稱之為完全圖。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：圖的鄰接矩陣是順序存儲方式。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：圖的深度優(yōu)先遍歷算法還可以應(yīng)用于檢查回路問題。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：圖的廣度優(yōu)先算法可以使用遞歸完成。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：prim算法適合在稠密圖中求解最小生成樹。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：prim算法的時間代價主要取決于頂點個數(shù)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：Kruskal算法適合在稀疏圖中求解最小生成樹。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：拓撲排序可以用于檢查圖中是否有回路。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在AOE網(wǎng)中，從源點到匯點的最長路徑長度的路徑被稱為關(guān)鍵路徑。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：Dijkstra算法思想屬于典型的貪心算法。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：Dijkstra算法需要對圖中每條邊至少檢查一次。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)7在線練習(xí)71、問題：一個具有n個頂點的無向圖最多有（）邊。選項：A、n(n-1)/2B、n(n-1)C、nD、2n正確答案:【n(n-1)/2】2、問題：一個具有n個頂點的有向圖中，要連通全部頂點至少需要（）條弧。選項：A、nB、n-1C、n+1D、2n正確答案:【n】3、問題：在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。選項：A、2B、1/2C、1D、4正確答案:【2】4、問題：在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。選項：A、1B、1/2C、2D、4正確答案:【1】5、問題：對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則占用的存儲空間為（）。選項：A、n+2eB、nC、2eD、n+e正確答案:【n+2e】6、問題：如果含有n個頂點的圖形成一個環(huán)，則它有（）棵生成樹。選項：A、nB、n-1C、n+1D、不確定正確答案:【n】7、問題：任何一個無向連通網(wǎng)的最小生成樹（）。選項：A、有一棵或多棵B、只有1棵C、一定有多棵D、可能不存在正確答案:【有一棵或多棵】8、問題：判斷一個有向圖是否存在回路，可以用（）。選項：A、深度優(yōu)先遍歷算法B、求關(guān)鍵路徑的方法C、Dijkstra方法D、廣度優(yōu)先遍歷算法正確答案:【深度優(yōu)先遍歷算法】9、問題：設(shè)圖G有n個頂點和e條邊，采用鄰接表存儲，則拓撲排序算法的時間復(fù)雜度為（）。選項：A、O(n+e)B、O(n)C、O(e)D、O(n*e)正確答案:【O(n+e)】10、問題：下面不正確的說法是（）。選項：A、任何一個關(guān)鍵活動提前完成，將使整個工程提前完成B、關(guān)鍵活動不按期完成就會影響整個工程的完成時間C、所有關(guān)鍵活動都提前完成，則整個工程提前完成D、某些關(guān)鍵活動若提前完成，將使整個工程提前完成正確答案:【任何一個關(guān)鍵活動提前完成，將使整個工程提前完成】11、問題：關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（）。選項：A、從源點到匯點的最長路徑B、最長回路C、從源點到匯點的最短路徑D、最短回路正確答案:【從源點到匯點的最長路徑】12、問題：圖G是一個非連通無向圖，共有28條邊，則該圖至少有（）個頂點。選項：A、9B、8C、10D、11正確答案:【9】13、問題：已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發(fā)的弧方法是（）。選項：A、將矩陣第i行上的元素全部置0B、將矩陣第i列上的元素全部置0C、將矩陣第i行刪除，后序行上移D、將矩陣第i列刪除，后序列左移正確答案:【將矩陣第i行上的元素全部置0】14、問題：深度優(yōu)先遍歷類似于二叉樹的（）。選項：A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷正確答案:【先序遍歷】15、問題：廣度優(yōu)先遍歷類似于二叉樹的()。選項：A、層次遍歷B、先序遍歷C、中序遍歷D、后序遍歷正確答案:【層次遍歷】16、問題：在圖的表示法中，表示形式唯一的是（）。選項：A、鄰接矩陣表示法B、鄰接表表示法C、逆鄰接表表示法D、鄰接表和逆鄰接表表示法正確答案:【鄰接矩陣表示法】17、問題：連通分量是（）的極大連通子圖。選項：A、無向圖B、樹C、圖D、有向圖正確答案:【無向圖】18、問題：最小生成樹的構(gòu)造可使用（）算法。選項：A、prim算法B、卡爾算法C、哈夫曼算法D、迪杰斯特拉算法正確答案:【prim算法】19、問題：在一個具有n個頂點e條邊的圖中，所有頂點的度數(shù)之和等于（）。選項：A、2nB、nC、eD、2e正確答案:【2e】20、問題：下面關(guān)于圖的存儲結(jié)構(gòu)的敘述中正確的是（）。選項：A、用鄰接矩陣存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)B、用鄰接矩陣存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點數(shù)無關(guān)C、用鄰接表存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)D、鄰接表存儲圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點數(shù)無關(guān)正確答案:【用鄰接矩陣存儲圖，占用空間大小只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)】21、問題：有8個結(jié)點的有向完全圖有()條邊。選項：A、56B、14C、28D、112正確答案:【56】22、問題：下圖中，度為3的結(jié)點是（）。選項：A、V2B、V1C、V3D、V4正確答案:【V2】23、問題：下圖是（）。選項：A、連通圖B、強連通圖C、生成樹D、無環(huán)圖正確答案:【連通圖】24、問題：如下圖所示，從頂點a出發(fā)，按深度優(yōu)先進行遍歷，則可能得到的一種頂點序列為（）。選項：A、a，e，d，f，c，bB、a，b，e，c，d，fC、a，c，f，e，b，dD、a，e，b，c，f，d正確答案:【a，e，d，f，c，b】25、問題：如下圖所示，從頂點a出發(fā)，按廣度優(yōu)先進行遍歷，則可能得到的一種頂點序列為（)。選項：A、a，b，e，c，d，fB、a，c，f，e，b，dC、a，e，b，c，f，dD、a，e，d，f，c，b正確答案:【a，b，e，c，d，f】26、問題：圖可以沒有邊，但不能沒有頂點。選項：A、正確B、錯誤正確答案:【錯誤】27、問題：關(guān)鍵路徑上的活動都是關(guān)鍵活動，它們是否按時完成會影響工期。選項：A、正確B、錯誤正確答案:【正確】28、問題：求稀疏圖的最小生成樹，用克魯斯卡爾算法來求解較好。選項：A、正確B、錯誤正確答案:【正確】29、問題：迪杰斯特拉算法求最短路徑時，是按照路徑長度遞增的順序求解的。選項：A、正確B、錯誤正確答案:【正確】30、問題：任何一個有向圖都一定存在拓撲序列。選項：A、正確B、錯誤正確答案:【錯誤】31、問題：稠密圖更適合采用鄰接矩陣存儲。選項：A、正確B、錯誤正確答案:【正確】32、問題：若一個無向圖以頂點V1為起點進行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。選項：A、正確B、錯誤正確答案:【正確】33、問題：若從一個無向圖中任一頂點出發(fā)，進行一次深度優(yōu)先遍歷，就可以訪問圖中所有的頂點，則該圖一定是連通的。選項：A、正確B、錯誤正確答案:【正確】34、問題：存儲無向圖的鄰接矩陣是對稱的，因此只要存儲鄰接矩陣的上三角（或下三角）部分就可以了。選項：A、正確B、錯誤正確答案:【正確】35、問題：有向圖不能進行廣度優(yōu)先遍歷。選項：A、正確B、錯誤正確答案:【錯誤】測驗1、問題：對表長為n的線性表進行順序查找，平均查找長度為(n+1)/2選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：折半查找只適合關(guān)鍵字有序并且順序存儲的查找表。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：二叉排序樹的形態(tài)與輸入序列的順序有關(guān)。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：在二叉排序樹中，按照中序進行遍歷，可以得到一個有序序列。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：哈希查找的理想情況是平均查找長度為0。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：構(gòu)造哈希函數(shù)時盡可能減少地址沖突，但又不可能避免。選項：A、正確B、錯誤正確答案:【正確】測驗1、問題：處理沖突實際就是為了產(chǎn)生沖突的地址尋找下一個散列地址。選項：A、正確B、錯誤正確答案:【正確】單元作業(yè)8在線練習(xí)81、問題：在關(guān)鍵字隨機分布的情況下，用二叉排序樹的方法進行查找，其查找長度與（）數(shù)量級相當(dāng)。選項：A、折半查找B、順序查找C、分塊查找D、哈希查找正確答案:【折半查找】2、問題：關(guān)于折半查找，以下說法正確的是(）。選項：A、待查找表必須有序，且只能以順序方式存儲B、待查找表必須有序，可以順序方式存儲，也可以鏈表方式存儲C、待查找表必須有序且表中數(shù)據(jù)必須是整型D、待查找表必須有序，而且必須從小到大排列正確答案:【待查找表必須有序，且只能以順序方式存儲】3、問題：具有12個關(guān)鍵字的有序表，折半查找的平均查找長度()。選項：A、37/12B、25C、25/12D、10/12正確答案:【37/12】4、問題：分別以下列序列構(gòu)造二叉排序樹，與用其他三個序列所構(gòu)造的結(jié)果不同的是（）。選項：A、（100，60，80，90，120，110，130）B、（100，80，90，60，120，110，130）C、（100，120，110，130，80，60，90）D、（100，80，60，90，120，130，110）正確答案:【（100，60，80，90，120，110，130）】5、問題：折半查找適合于存儲結(jié)構(gòu)為（）的線性表。選項：A、順序B、散列存儲C、壓縮存儲D、索引存儲正確答案:【順序】6、問題：如果要求用線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，則可采用（）查找方法。選項：A、分塊查找B、順序查找C、折半查找D、基于屬性正確答案:【分塊查找】7、問題：以下適合用分塊查的數(shù)據(jù)集是（）。選項：A、數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序B、數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同C、數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)必須有序，塊間不必有序D、數(shù)據(jù)分成大小相等的若干塊，塊內(nèi)數(shù)據(jù)有序正確答案:【數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序】8、問題：已知一如下10個記錄的表，其關(guān)鍵字序列為（2，15，19，25，30，34，44，55，58，80），用折半查找法查找關(guān)鍵字為55的記錄，比較次數(shù)是（）。選項：A、1次B、2次C、3次D、4次正確答案:【2次】9、問題：關(guān)于哈希查找，以下說法不正確的是（）。選項：A、哈希查找的ASL一定可以達到0B、裝填因子越小，越容易產(chǎn)生沖突C、哈希查找有兩個關(guān)鍵問題：哈希函數(shù)的選擇和處理沖突的方法D、鏈地址法和線性探測再散列都是解決沖突的方法正確答案:【哈希查找的ASL一定可以達到0】10、問題：由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹()。選項：A、形態(tài)和平均查找長度都不一定相同B、形態(tài)和平均查找長度都相同C、形態(tài)相同，但平均查找長度不一定相同D、形態(tài)不一定相同，但平均查找長度相同正確答案:【形態(tài)和平均查找長度都不一定相同】11、問題：對二叉排序樹進行()遍歷，可以得到各結(jié)點鍵值的非遞減序列。選項：A、中序B、層次C、后序D、先序正確答案:【中序】12、問題：如果按關(guān)鍵碼值遞增的順序依次將99個關(guān)鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，在等概率情況下查找成功時的平均查找長度ASL為(）。選項：A、50B、48C、45D、47正確答案:【50】13、問題：在有N個元素的順序表中順序查找，則等概率情況下查找成功的平均查找長度為（）。選項：A、(N+1)/2B、N/2C、N+1D、N(N+1)/2正確答案:【(N+1)/2】14、問題：對線性表進行折半查找時，要求線性表()。選項：A、關(guān)鍵字有序并按順序方式存儲B、有序C、順序存儲D、沒有正確答案正確答案:【關(guān)鍵字有序并按順序方式存儲】15、問題：順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。選項：A、順序存儲或鏈接存儲B、散列存儲C、壓縮存儲D、索引存儲正確答案:【順序存儲或鏈接存儲】16、問題：一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點時，()次比較后查找成功。選項：A、4B、2C、3D、5正確答案:【4】17、問題：下列（）不是利用比較進行查找的方法。選項：A、散列查找B、平衡二叉樹C、有序表的查找D、二叉排序樹的查找正確答案:【散列查找】18、問題：設(shè)哈希表長m=14，哈希函數(shù)H（key）=key％11。表中已有4個結(jié)點：addr(15)=4addr(38)=5addr(