【MOOC】數(shù)據(jù)結(jié)構(gòu)-華中農(nóng)業(yè)大學(xué) 中國大學(xué)慕課MOOC答案

【MOOC】數(shù)據(jù)結(jié)構(gòu)-華中農(nóng)業(yè)大學(xué)中國大學(xué)慕課MOOC答案緒論1、【單選題】在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成________。本題答案：【線性結(jié)構(gòu)和非線性結(jié)構(gòu)】2、【單選題】算法分析的目的是________。本題答案：【分析算法的效率以求改進(jìn)】3、【單選題】算法分析的兩個(gè)主要方面是________。本題答案：【空間復(fù)雜度和時(shí)間復(fù)雜度】4、【單選題】計(jì)算機(jī)算法指的是解決問題的有限運(yùn)算序列，它必須具備輸入、輸出和________等5個(gè)特性。本題答案：【可行性、確定性和有窮性】5、【單選題】下面程序段的時(shí)間復(fù)雜度為____________。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;本題答案：【O(m*n)】6、【單選題】執(zhí)行下面程序段時(shí)，執(zhí)行S語句的次數(shù)為____________。for(inti=1;i=n;i++)for(intj=1;j=i;j++)S;本題答案：【n(n+1)/2】7、【單選題】下面算法的時(shí)間復(fù)雜度為____________。intf(unsignedintn){if(n==0||n==1)return1;elsereturnn*f(n-1);}本題答案：【O(n)】8、【單選題】下面程序段的時(shí)間復(fù)雜性的量級(jí)為____________。for(i=1;i＜＝n;i++)for(j=1;j＜＝m;j++){c[i][j]=0;for(k=1;k＜＝w;k++)c[i][j]+=a[i][k]*b[k][j]}本題答案：【O(n*m*w)】9、【單選題】下面關(guān)于算法說法錯(cuò)誤的是____________。本題答案：【算法的可行性是指指令不能有二義性】10、【多選題】數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的①以及它們之間的②和運(yùn)算等的學(xué)科。本題答案：【數(shù)據(jù)元素#關(guān)系】線性表1、【單選題】線性表是_______。本題答案：【一個(gè)有限序列，可以為空】2、【單選題】對(duì)順序存儲(chǔ)的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的。插入一個(gè)元素時(shí)平均要移動(dòng)表中的_______個(gè)元素。本題答案：【n/2】3、【單選題】線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址_______。本題答案：【連續(xù)與否均可以】4、【單選題】用鏈表表示線性表的優(yōu)點(diǎn)是_______。本題答案：【便于插入和刪除】5、【單選題】某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采用_______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。本題答案：【帶頭結(jié)點(diǎn)的雙循環(huán)鏈表】6、【單選題】循環(huán)鏈表的主要優(yōu)點(diǎn)是_______。本題答案：【從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表】7、【單選題】下面關(guān)于線性表的敘述錯(cuò)誤的是_______。本題答案：【線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作】8、【單選題】單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了_______。本題答案：【方便運(yùn)算的實(shí)現(xiàn)】9、【單選題】若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用_______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。本題答案：【僅有尾指針的單循環(huán)鏈表】10、【單選題】若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用_______存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。本題答案：【順序表】11、【單選題】一個(gè)向量(一種順序表)第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是_______。本題答案：【108】12、【單選題】不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是______。本題答案：【head==NULL;】13、【單選題】帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是______。本題答案：【head-next==NULL;】14、【單選題】在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行____。本題答案：【s-next=p-next;p-next=s;】15、【單選題】在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行______。本題答案：【q-next=s;s-next=p;】16、【單選題】從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_____個(gè)結(jié)點(diǎn)。本題答案：【(n+1)/2】17、【單選題】給定有n個(gè)結(jié)點(diǎn)的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度_______。本題答案：【O(n^2)】18、【單選題】順序存儲(chǔ)結(jié)構(gòu)是一種___的存儲(chǔ)結(jié)構(gòu)。本題答案：【隨機(jī)存取】19、【單選題】在以下的敘述中，正確的是___。本題答案：【線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況】20、【單選題】非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足____。本題答案：【p-next==head】21、【單選題】在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行____。本題答案：【p-next=p-next-next；】22、【單選題】在一個(gè)長度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移____個(gè)元素。本題答案：【n-i+1】23、【單選題】在一個(gè)長度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1≤i≤n+1)時(shí)，需要從前向后依次前移____個(gè)元素。本題答案：【n-i】24、【單選題】在一個(gè)長度為n的線性表中順序查找值為x的元素時(shí)，查找時(shí)的平均查找長度（即x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為____。本題答案：【(n+1)/2】25、【單選題】在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行____。本題答案：【p-next=HL;HL=p;】26、【單選題】一個(gè)帶頭結(jié)點(diǎn)head的循環(huán)單鏈表為空的判斷條件是____。本題答案：【head-next==head】27、【單選題】在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行____。本題答案：【p=q-next;q-next=p-next;】28、【單選題】將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，在最壞的情況下，其比較次數(shù)是____。本題答案：【2n-1】29、【判斷題】線性表的邏輯順序與存儲(chǔ)順序總是一致的。本題答案：【錯(cuò)誤】30、【判斷題】順序存儲(chǔ)的線性表可以按序號(hào)隨機(jī)存取。本題答案：【正確】31、【判斷題】順序表的插入和刪除一個(gè)數(shù)據(jù)元素，每次操作平均只有近一半的元素需要移動(dòng)。本題答案：【正確】32、【判斷題】線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對(duì)象。本題答案：【正確】33、【判斷題】在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。本題答案：【錯(cuò)誤】34、【判斷題】在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。本題答案：【正確】35、【判斷題】線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。本題答案：【錯(cuò)誤】36、【判斷題】在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。本題答案：【正確】37、【判斷題】線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中數(shù)據(jù)元素的。本題答案：【正確】38、【判斷題】在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。本題答案：【錯(cuò)誤】39、【判斷題】線性表中，每一個(gè)元素均存在前驅(qū)。本題答案：【錯(cuò)誤】40、【判斷題】線性表中，每一個(gè)元素均存在后繼。本題答案：【錯(cuò)誤】41、【判斷題】線性表中，存在唯一一個(gè)被稱為第一元素的元素。本題答案：【正確】42、【判斷題】線性表中，存在唯一一個(gè)被稱為最后一個(gè)元素的元素。本題答案：【正確】43、【判斷題】線性結(jié)構(gòu)是一種一對(duì)一的結(jié)構(gòu)。本題答案：【正確】棧和隊(duì)列1、【單選題】一個(gè)棧的入棧序列a，b，c，d，e，則棧的不可能的輸出序列是____。本題答案：【dceab】2、【單選題】若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為____。本題答案：【n-i+1】3、【單選題】棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是____。本題答案：【順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)】4、【單選題】判定一個(gè)順序棧ST（最多元素為m0）為空的條件是____。本題答案：【top==0】5、【單選題】判定一個(gè)順序棧ST（最多元素為m0）為棧滿的條件是____。本題答案：【top==m0-1】6、【單選題】隊(duì)列操作的原則是____。本題答案：【先進(jìn)先出】7、【單選題】向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行____。(不帶空的頭結(jié)點(diǎn))本題答案：【s—＞next=HS;HS=s;】8、【單選題】從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行____。(不帶空的頭結(jié)點(diǎn))本題答案：【x=HS—＞data;】9、【單選題】一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1，2，3，4，則隊(duì)列的出隊(duì)時(shí)輸出序列是____。本題答案：【1，2，3，4】10、【單選題】判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m）為空的條件是____。本題答案：【front==rear】11、【單選題】判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m,m==Maxsize-1）為滿隊(duì)列的條件是____。本題答案：【((rear-front)+Maxsize)%Maxsize==m】12、【單選題】循環(huán)隊(duì)列用數(shù)組A[0，m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是____。本題答案：【(rear-front+m)%m】13、【單選題】棧和隊(duì)列的共同點(diǎn)是____。本題答案：【只允許在端點(diǎn)處插入和刪除元素】14、【單選題】棧操作的原則是____。本題答案：【后進(jìn)先出】15、【單選題】在順序棧中，判斷棧s為空的條件是____。本題答案：【st.top==st.base】16、【單選題】在順序棧中，判斷棧s滿的條件是____。本題答案：【st.top-st.base=st.stacksize】17、【單選題】當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行語句修改top指針____。本題答案：【top--】18、【單選題】當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度為____。本題答案：【N-1】19、【單選題】從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，首先需要____。本題答案：【后移一位隊(duì)首指針】20、【單選題】假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件是____。本題答案：【f==r】21、【單選題】假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件是____。本題答案：【front==NULL】串1、【單選題】以下敘述中正確的是____。本題答案：【串是一種特殊的線性表】2、【單選題】串是一中特殊的線性表，其特殊性體現(xiàn)在____。本題答案：【數(shù)據(jù)元素是一個(gè)字符】3、【單選題】設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作____。本題答案：【模式匹配】4、【單選題】設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是____。本題答案：【BCDEFEF】5、【單選題】設(shè)串的長度為n，則它的子串個(gè)數(shù)為____。本題答案：【n(n+1)/2】6、【單選題】下列那些為空串____。本題答案：【S=“”】7、【單選題】S1=“ABCD”，S2=“CD”則S2在S3中的位置是____。本題答案：【3】8、【單選題】串是一種特殊的線性表，其特殊性體現(xiàn)在____。本題答案：【數(shù)據(jù)元素是一個(gè)字符】9、【單選題】串的長度是____。本題答案：【串中所含的字符的個(gè)數(shù)】10、【單選題】若某串的長度小于一個(gè)常數(shù)，則采用____存儲(chǔ)方式最為節(jié)省空間。本題答案：【順序表】11、【判斷題】空串是由空白字符組成的串。本題答案：【錯(cuò)誤】12、【判斷題】串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，按照預(yù)定義的大小，為每個(gè)定義的串變量分配一個(gè)固定長度的存儲(chǔ)區(qū)。本題答案：【正確】13、【判斷題】串的堆分配存儲(chǔ)表示是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列，但它們的存儲(chǔ)空間是在程序執(zhí)行過程中動(dòng)態(tài)分配得到的。本題答案：【正確】14、【判斷題】如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。本題答案：【錯(cuò)誤】15、【判斷題】串是由有限個(gè)字符構(gòu)成的連續(xù)序列，串長度為串中字符的個(gè)數(shù)，子串是主串中字符構(gòu)成的有限序列。本題答案：【錯(cuò)誤】16、【判斷題】空串的長度為零。本題答案：【正確】17、【判斷題】串是不少于一個(gè)字符的序列。本題答案：【錯(cuò)誤】18、【判斷題】兩個(gè)串相等當(dāng)且僅當(dāng)兩個(gè)串的長度相等并且各個(gè)對(duì)應(yīng)位置上的字符都想等。本題答案：【正確】19、【判斷題】KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小。本題答案：【正確】20、【判斷題】設(shè)模式串的長度為m,目標(biāo)串的長度為n，當(dāng)n≈m且處理只匹配一次的模式時(shí)，樸素的匹配（即子串定位函數(shù)）算法所花的時(shí)間代價(jià)可能會(huì)更為節(jié)省。本題答案：【錯(cuò)誤】數(shù)組廣義表測(cè)驗(yàn)題1、【單選題】常對(duì)數(shù)組進(jìn)行的兩種基本操作是本題答案：【查找與修改】2、【單選題】稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)本題答案：【非零元素】3、【單選題】數(shù)組A中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為本題答案：【SA+222】4、【單選題】若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij(ij)的位置k的關(guān)系為本題答案：【j*(j-1)/2+i】5、【單選題】有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是本題答案：【66】6、【單選題】數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)本題答案：【45】7、【單選題】對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是本題答案：【節(jié)省存儲(chǔ)空間】8、【單選題】已知廣義表LS＝((a,b,c),(d,e,f)),運(yùn)用head和tail函數(shù)取出LS中原子e的運(yùn)算是本題答案：【head(tail(head(tail(LS)))】9、【單選題】廣義表A=(a,b,(c,d),(e,(f,g))),則下面式子的值為本題答案：【d】10、【單選題】下面說法不正確的是本題答案：【廣義表的表頭總是一個(gè)廣義表】11、【判斷題】數(shù)組不適合作為任何二叉樹的存儲(chǔ)結(jié)構(gòu)。本題答案：【錯(cuò)誤】12、【判斷題】從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個(gè)元素均屬于n個(gè)向量。本題答案：【正確】13、【判斷題】稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。本題答案：【正確】14、【判斷題】數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入，刪除等操作。本題答案：【錯(cuò)誤】15、【判斷題】廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。本題答案：【錯(cuò)誤】樹和二叉樹測(cè)驗(yàn)題1、【單選題】已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為本題答案：【-+A*BC/DE】2、【單選題】設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1則T中的葉子數(shù)為本題答案：【8】3、【單選題】設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是本題答案：【m-n】4、【單選題】若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是本題答案：【11】5、【單選題】在一棵三元樹中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為本題答案：【6】6、【單選題】設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是本題答案：【M2+M3】7、【單選題】具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有幾個(gè)度為2的結(jié)點(diǎn)本題答案：【9】8、【單選題】一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是本題答案：【以上答案都不對(duì)】9、【單選題】設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為本題答案：【2n-1】10、【單選題】有關(guān)二叉樹下列說法正確的是本題答案：【一棵二叉樹的度可以小于2】11、【單選題】一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為本題答案：【11至1025之間】12、【單選題】一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有多少結(jié)點(diǎn)本題答案：【2h-1】13、【單選題】一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是本題答案：【?logn?+1】14、【單選題】利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是本題答案：【空】15、【單選題】在下列存儲(chǔ)形式中，哪一個(gè)不是樹的存儲(chǔ)形式？本題答案：【順序存儲(chǔ)表示法】16、【判斷題】二叉樹是度為2的有序樹。本題答案：【錯(cuò)誤】17、【判斷題】完全二叉樹一定存在度為1的結(jié)點(diǎn)。本題答案：【錯(cuò)誤】18、【判斷題】二叉樹的遍歷結(jié)果不是唯一的本題答案：【正確】19、【判斷題】二叉樹的遍歷只是為了在應(yīng)用中找到一種線性次序。本題答案：【正確】20、【判斷題】對(duì)一棵二叉樹進(jìn)行層次遍歷時(shí)，應(yīng)借助于一個(gè)棧。本題答案：【錯(cuò)誤】21、【判斷題】中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。本題答案：【正確】22、【判斷題】任何一棵二叉樹都可以不用棧實(shí)現(xiàn)前序線索樹的前序遍歷。本題答案：【正確】23、【判斷題】由一棵二叉樹的前序序列和后序序列可以唯一確定它。本題答案：【錯(cuò)誤】24、【判斷題】完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是樹葉。本題答案：【正確】25、【判斷題】當(dāng)一棵具有n個(gè)葉子結(jié)點(diǎn)的二叉樹的WPL值為最小時(shí)，稱其樹為哈夫曼樹，且其二叉樹的形狀必是唯一的。本題答案：【錯(cuò)誤】圖測(cè)試題1、【單選題】圖中有關(guān)路徑的定義是（）本題答案：【由相鄰頂點(diǎn)序偶所形成的序列】2、【單選題】設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（）條邊本題答案：【n(n-1)/2】3、【單選題】n個(gè)節(jié)點(diǎn)的完全有向圖含有邊的數(shù)目為（）本題答案：【n(n-1)】4、【單選題】一個(gè)有n個(gè)節(jié)點(diǎn)的無向圖，最多有（）個(gè)連通分量本題答案：【n】5、【單選題】一個(gè)有n個(gè)節(jié)點(diǎn)的無向圖，最少有（）個(gè)連通分量本題答案：【1】6、【單選題】下列（）的鄰接矩陣是對(duì)稱矩陣本題答案：【無向圖】7、【單選題】下列說法不正確的是（）本題答案：【圖的深度優(yōu)先遍歷不適用于有向圖?！?、【單選題】無向圖G=（V，E），其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},以頂點(diǎn)a為源，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）本題答案：【a,e,d,f,c,b】9、【單選題】如圖所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？（）(1)a,e,b,d,f,c;(2)a,c,f,d,e,b;(3)a,e,d,f,c,b;(4)a,e,f,d,c,b;(5)a,e,f,d,b,c本題答案：【2個(gè)】10、【單選題】求解最短路徑的弗洛伊德算法的時(shí)間復(fù)雜度為（）本題答案：【O（n*n*n）】11、【單選題】已知有向圖G=（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E={V1,V2,V1,V3V1,V4V2,V5V3,V5V3,V6V4,V6V5,V7V6,V7},G的拓?fù)湫蛄惺牵ǎ┍绢}答案：【V1，V3，V4，V6，V2，V5，V7】12、【單選題】在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（）本題答案：【G中有一條Vj到Vi的路徑】13、【單選題】關(guān)鍵路徑是事件結(jié)點(diǎn)圖中（）本題答案：【從源點(diǎn)到匯點(diǎn)的最長路徑】14、【單選題】下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）本題答案：【任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成】15、【單選題】帶權(quán)有向圖G用鄰域矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（）本題答案：【第i列非∞且非零的元素個(gè)數(shù)】16、【單選題】無向圖的鄰接矩陣是一個(gè)（）本題答案：【對(duì)稱矩陣】17、【單選題】如果從無向圖的任一頂點(diǎn)出發(fā)，進(jìn)行一次深度優(yōu)先搜索即可訪問所有的頂點(diǎn)，則該圖一定是（）本題答案：【連通圖】18、【單選題】圖的深度優(yōu)先遍歷算法類似于二叉樹的（）算法本題答案：【先序遍歷】19、【單選題】對(duì)于圖進(jìn)行從頂點(diǎn)1開始的深度優(yōu)先搜索遍歷，可得到頂點(diǎn)訪問序列（）本題答案：【1,2,4,3,5,7,6】20、【單選題】對(duì)圖從頂點(diǎn)1進(jìn)行廣度優(yōu)先搜索遍歷，可得頂點(diǎn)訪問序列為（）本題答案：【1,3,2,4,5,6,7】21、【單選題】對(duì)于含有n個(gè)頂點(diǎn)的帶權(quán)連通圖，它的最小生成樹是指圖中任意一個(gè)（）本題答案：【由n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的連通子圖】22、【單選題】一個(gè)有向圖中的頂點(diǎn)不能排成一個(gè)拓?fù)湫蛄校瑒t斷定該有向圖（）本題答案：【含有頂點(diǎn)數(shù)目大于1的強(qiáng)連通分量】23、【單選題】下列關(guān)于無向連通圖特性的敘述中，正確的是（）I所有頂點(diǎn)的度之和為偶數(shù)II邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III至少有一個(gè)頂點(diǎn)的度為1本題答案：【只有I】24、【單選題】下列關(guān)于圖的敘述中，正確的是（）1回路是簡單路徑2存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間3若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路本題答案：【僅3】25、【單選題】對(duì)有n個(gè)頂點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先搜索遍歷，其算法時(shí)間復(fù)雜度是（）本題答案：【存在，且唯一】26、【單選題】下列關(guān)于最小生成樹的敘述中，正確的是（）最小生成樹的代價(jià)唯一所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中使用普里姆算法從不同頂點(diǎn)開始得到的最小生成樹一定相同使用普里姆算法和克魯斯卡爾算法得到的最小生成樹總不相同本題答案：【僅I】27、【單選題】設(shè)圖的鄰接矩陣A如下圖所示，則各頂點(diǎn)的度依次是（）本題答案：【3,4,2,3】28、【單選題】若對(duì)下圖所示的無向圖進(jìn)行遍歷，不是廣度優(yōu)先遍歷序列的是（）本題答案：【a,b,c,d,h,e,f,g】29、【單選題】下圖所示的AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程。通過同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短整個(gè)工期的工程。下列選項(xiàng)中，加快其進(jìn)度就可以縮短工程工期的是（）本題答案：【f和d】30、【單選題】對(duì)下面的有向圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)湫蛄锌赡苁牵ǎ┍绢}答案：【3,1,4,2,6,5】31、【判斷題】含有n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為n-1。本題答案：【正確】32、【判斷題】要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要n+1條邊。本題答案：【錯(cuò)誤】33、【判斷題】在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2倍本題答案：【正確】34、【判斷題】深度優(yōu)先遍歷可以判斷出一個(gè)有向圖是否有環(huán)。本題答案：【正確】35、【判斷題】當(dāng)各邊上的權(quán)值均相等時(shí)，BFS算法可以用來解決單源最短路徑問題本題答案：【正確】36、【判斷題】若一個(gè)有向圖的鄰接矩陣中，主對(duì)角線以下的元素均為零，則該圖的拓?fù)溆行蛐蛄幸欢ú淮嬖?。本題答案：【錯(cuò)誤】37、【判斷題】一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄惺俏ㄒ坏?。本題答案：【錯(cuò)誤】38、【判斷題】對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是n*n本題答案：【正確】39、【判斷題】對(duì)圖進(jìn)行廣度優(yōu)先搜索遍歷類似于二叉樹的先序遍歷算法。本題答案：【錯(cuò)誤】40、【判斷題】用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是拓?fù)溆行虻摹１绢}答案：【錯(cuò)誤】查找測(cè)試題1、【單選題】順序查找法適合于存儲(chǔ)結(jié)構(gòu)為____的線性表。本題答案：【順序存儲(chǔ)或鏈接存儲(chǔ)】2、【單選題】對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須____。本題答案：【以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序】3、【單選題】采用順序查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為____。本題答案：【(n+1)/2】4、【單選題】采用二分查找方法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為____。本題答案：【O(log2n)】5、【單選題】從具有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素時(shí)，最壞情況下的時(shí)間復(fù)雜度為____。本題答案：【O(n)】6、【單選題】有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值82為的結(jié)點(diǎn)時(shí)，需要____次比較后才能查找成功。本題答案：【4】7、【單選題】設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7。如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是____。本題答案：【9】8、【單選題】有一個(gè)長度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為____。本題答案：【37/12】9、【單選題】有數(shù)據(jù){53,30,37,12,45,24,96}，從空二叉樹開始逐個(gè)插入數(shù)據(jù)來形成二叉排序樹，若希望樹的高度最小，則應(yīng)選擇下面哪個(gè)序列輸入____。本題答案：【37,24,12,30,53,45,96】10、【單選題】對(duì)于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式為_______。本題答案：【從第n個(gè)元素往開始前查找該數(shù)據(jù)元】11、【單選題】采用線性探測(cè)法解決沖突問題，所產(chǎn)生的一系列后繼散列地址______。本題答案：【可以大于或小于但不能等于原散列地址】12、【單選題】對(duì)于查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于_______。本題答案：【動(dòng)態(tài)查找表】13、【單選題】散列表的平均查找長度_______。本題答案：【與處理沖突方法有關(guān)而與表的長度有關(guān)】14、【單選題】一棵深度為k的平衡二叉樹，其每個(gè)非終端結(jié)點(diǎn)的平衡因子均為0，則該樹共有____個(gè)結(jié)點(diǎn)。本題答案：【2^k-1】15、【單選題】分塊查找中，若索引表對(duì)各塊內(nèi)均采用順序查找，有900個(gè)元素的線性表若分成25塊，其平均查找長度為_____。本題答案：【31.5】16、【單選題】已知一棵5階B樹有53個(gè)關(guān)鍵字，