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

【MOOC】數(shù)據(jù)結(jié)構(gòu)與算法Python版-北京大學(xué)中國大學(xué)慕課MOOC答案第一周測驗1、【單選題】以下關(guān)于基于有窮觀點的能行方法說法錯誤的是：本題答案：【由有限數(shù)量的任意指令構(gòu)成】2、【單選題】以下關(guān)于ADT抽象數(shù)據(jù)類型說法錯誤的是：本題答案：【同一ADT只有唯一的數(shù)據(jù)結(jié)構(gòu)可以實現(xiàn)?！?、【單選題】關(guān)于“圖靈機”，下列說法不正確的個數(shù)為：1）圖靈機給出的是計算機的理論模型；2）圖靈機的狀態(tài)轉(zhuǎn)移函數(shù)q,X,Y,R(或L或N),p，其實就是一條指令，即在q狀態(tài)下，當(dāng)輸入為X時，輸出為Y，讀寫頭向右(R)、向左(L)移動一格或不動(N)，狀態(tài)變?yōu)閜；3）圖靈機是一種離散的、有窮的、構(gòu)造性的問題求解思路；4）凡是能用算法方法解決的問題也一定能用圖靈機解決，凡是圖靈機解決不了的問題算法也解決不了。本題答案：【0】4、【單選題】下列哪個項目是抽象的邏輯功能？本題答案：【電視機使用手冊；】5、【單選題】邏輯功能接口和實現(xiàn)方法的關(guān)系？本題答案：【邏輯功能接口是穩(wěn)定的，可以用不同方法來實現(xiàn)；】6、【多選題】一個圖靈機應(yīng)該由以下哪些部分組成？本題答案：【無限長的分格紙帶#讀寫頭#狀態(tài)寄存器#有限的控制規(guī)則】7、【多選題】一般來說我們可以把生活中常見的問題分為哪幾類？本題答案：【分類問題#證明問題#過程問題】8、【多選題】以下哪些方法不是以算法的概念來解決問題？本題答案：【智慧眾包#星象占卜】OJ的適應(yīng)性測試第二周測驗1、【單選題】判斷下列代碼段，關(guān)于的大O級別：test=0foriinrange(n):forjinrange(n):forkinrange(i):test=test+i*j本題答案：【O(n^3)】2、【單選題】判斷下列代碼段的大O級別：test=0foriinrange(n):test=test+1forjinrange(n):test=test-1forkinrange(n):test=test*1本題答案：【O(n)】3、【單選題】判斷下列代碼段的大O級別：foriinrange(n):forjinrange(i):k=2+2本題答案：【O(n^2)】4、【單選題】判斷下列代碼段的大O級別：deffunction(n):return2本題答案：【O(1)】5、【單選題】以下是一個快速冪算法：defpow(x,n):ifn==0:return1elifn==1:returnxelifn%2==0:returnpow(x*x,n//2)else:returnpow(x*x,n//2)*x問它對于n的大O級別。本題答案：【O(logn)】6、【多選題】下面的列表操作中哪些是O(1)的？（假設(shè)列表alist足夠長，不導(dǎo)致任何報錯）本題答案：【alist.pop()#alist.append(10)#alist[10:16]】7、【多選題】下面的字典操作中哪些是O(1)的？本題答案：【''inmy_dict#delmy_dict['']#my_dict['']==10#my_dict['']+=1】8、【多選題】令n為問題規(guī)模，其中解決本問題的三個算法稱為A,B,C，他們需要的總運算次數(shù)分別是：A:96+108n+24n^2+12n^3B:16+3n^48C:10080+168n+7n^2*log(n)三個算法的時間復(fù)雜度的大O級別中，以下表述正確的有：本題答案：【B算法比A算法的時間復(fù)雜度更大#C算法的時間復(fù)雜度最小】第三周作業(yè)第三周測驗1、【單選題】假設(shè)你執(zhí)行了下列的棧操作：s=Stack()s.push(1)s.push(3)s.push(5)s.pop()s.push(7)現(xiàn)在棧內(nèi)還有哪些元素？本題答案：【1,3,7】2、【單選題】將以下中綴表達(dá)式：(5-3)*(2+4)轉(zhuǎn)換為后綴表達(dá)式，結(jié)果為？本題答案：【53-24+*】3、【單選題】給定后綴表達(dá)式36+52-/求值結(jié)果為？本題答案：【3】4、【單選題】使用括號匹配算法判斷以下表達(dá)式：([()[]{]})結(jié)果是否匹配？匹配過程中棧內(nèi)元素最多有多少個？本題答案：【否，3】5、【單選題】判斷以下函數(shù)的功能deffunc(str1):s=Stack()forcharinstr1:s.push(char)str2=''whilenots.isEmpty():str2+=s.pop()returnstr2本題答案：【將給定的字符串反轉(zhuǎn)輸出】6、【多選題】以下哪些關(guān)于棧的說法是正確的？本題答案：【棧的特性是后進先出(LIFO)#括號匹配算法需要棧結(jié)構(gòu)的參與#在Python中棧結(jié)構(gòu)可以由list來實現(xiàn)】7、【多選題】以下未完成的函數(shù)可實現(xiàn)不同的功能deffunc(lst1):s1,s2=Stack(),Stack()foriteminlst1:s1.push(item)lst2=[]whilenots1.isEmpty():###在此進行代碼填空###returnlst2#測試print(func([1,3,5,7,9]))在下列選項中，填空內(nèi)容與分別對列表[1,3,5,7,9]調(diào)用結(jié)果相對應(yīng)的選項有？H、foriinrange(s1.pop()):s2.push(i)lst2.append(s2.size())[1,4,9,16,25]本題答案：【lst2.append(s1.pop())[9,7,5,3,1]#whilenots1.isEmpty():s2.push(s1.pop())lst2.append(s2.pop())whilenots2.isEmpty():s1.push(s2.pop())[1,3,5,7,9]#lst2.append(s1.peek())死循環(huán)，無法運行#foriinrange(s1.pop()):s2.push(i)lst2.append(s2.size())[9,16,21,24,25]】8、【多選題】以下哪些算法適合用棧來實現(xiàn)？本題答案：【實現(xiàn)UNDO和REDO功能的算法#HTML標(biāo)簽匹配算法】第四周作業(yè)第四周測驗1、【單選題】下列敘述正確的是？本題答案：【隊列可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)的雙向鏈表實現(xiàn)#棧可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)的單鏈表實現(xiàn)】2、【單選題】用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時本題答案：【隊頭、隊尾指針都可能要修改，但不必然都修改】3、【單選題】遞歸過程或函數(shù)調(diào)用時，處理參數(shù)或返回地址，用以下哪種數(shù)據(jù)結(jié)構(gòu)最合適？本題答案：【棧】4、【單選題】設(shè)有序單鏈表的關(guān)鍵字序列為{1,4,6,11,19,35,52,54,57,71,78,86,92,96}，當(dāng)查找關(guān)鍵字為21的結(jié)點時，經(jīng)()次比較后查找失敗？本題答案：【6】5、【單選題】設(shè)某順序表中第一個元素的起始存儲地址為a,每個元素的長度為b,則第c個元素的起始地址是？（a,b,c均為非負(fù)整數(shù)）本題答案：【a+b*(c-1)】6、【多選題】以下哪些不是單鏈表的特點？本題答案：【隨機存取#插入刪除元素時需要移動表中元素】7、【多選題】以下哪些是順序表的特點？本題答案：【隨機存取#插入刪除元素時需要移動表中元素】8、【多選題】設(shè)一個隊列的入隊順序是1，2，3，4，5，那下列哪些是不能存在的出隊順序？本題答案：【1，2，3，5，4#3，4，5，1，2#5，4，3，2，1#1，2，5，4，3#2，3，4，5，1】第五周作業(yè)第五周測驗1、【單選題】以下哪項不是遞歸的三定律之一？本題答案：【對函數(shù)運行結(jié)果進行緩存】2、【單選題】遞歸函數(shù)的實現(xiàn)與哪種數(shù)據(jù)結(jié)構(gòu)直接相關(guān)？本題答案：【棧】3、【單選題】使用進制轉(zhuǎn)換函數(shù)：deftoStr2(n,base):convertString='0123456789ABCDEF'ifn==0:return''returntoStr2(n//base,base)+convertString[n%base]將數(shù)字135轉(zhuǎn)換為三進制“12000”的過程中，函數(shù)共被調(diào)用了多少次（包含初始調(diào)用）？本題答案：【6】4、【單選題】若定義實心等邊三角形為0階謝爾賓斯基三角，現(xiàn)給定一個邊長為1的4階謝爾賓斯基三角，請問它的面積更接近以下哪個數(shù)字？本題答案：【0.137】5、【單選題】以下是使用遞歸方式實現(xiàn)的圓括號匹配函數(shù)：defmatch(s,n=0):ifs:ifs[0]=='(':n+=1else:n-=1ifn0:returnFalsereturnmatch(s[1:],n)else:returnn==0請問以下哪個輸入中可能出現(xiàn)參數(shù)為match(((())),3)的函數(shù)調(diào)用？本題答案：【(((()((()))】6、【多選題】給定繪制分形樹函數(shù)：deftree(branch_len):t.pendown()t.forward(branch_len)t.penup()ifbranch_len5:t.left(20)tree(branch_len-5)t.right(40)tree(branch_len-5)t.left(20)t.backward(branch_len)其中t為海龜畫筆對象。在調(diào)用函數(shù)tree(50)時，下列哪些說法是正確的？H、樹梢共256個本題答案：【畫線的長度總和為10180#組成樹的線段共1023條#樹梢與樹根的路徑距離為275#樹梢共512個】7、【多選題】以下函數(shù)用于可用于求方程的近似解，其中參數(shù)f為一個輸入、輸出均為數(shù)字的函數(shù)defsolve(f,x1,x2):mid=(x1+x2)/2iff(mid)==0orabs(x1-x2)1e-8:return#Aeliff(mid)*f(x1)0:return#Belse:return#C如何補全該函數(shù)使其可以正常使用？H、C處應(yīng)填：midI、C處應(yīng)填：solve(f,mid,x2)本題答案：【A處應(yīng)填：mid#B處應(yīng)填：solve(f,mid,x2)#C處應(yīng)填：solve(f,x1,mid)】8、【多選題】以下哪些問題不能用遞歸算法求解？本題答案：【圖像、語義識別#計算兩個數(shù)的差】第六周作業(yè)第六周測驗1、【單選題】下列哪個算法使用到了分治策略？本題答案：【二分查找】2、【單選題】函數(shù)值緩存最適合使用哪種Python中的數(shù)據(jù)類型？本題答案：【字典】3、【單選題】已知數(shù)列G(x)滿足：G(1)=G(2)=G(3)=G(4)=1G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4)(x≥5)根據(jù)遞推式寫出求數(shù)列值的遞歸算法，問原始算法與采用函數(shù)值緩存的算法時間復(fù)雜度分別為多少？本題答案：【O(4^n);O(n)】4、【單選題】博物館大盜問題中，若共有8件寶物，背包總重為25單位，使用動態(tài)規(guī)劃算法求解時需要建立多大的數(shù)組？H、9x27I、8x27本題答案：【9x26】5、【單選題】以下哪個說法是錯誤的？本題答案：【相比于函數(shù)值緩存，動態(tài)規(guī)劃的優(yōu)勢在于不需要額外的存儲空間】6、【多選題】以下是使用遞歸算法對N皇后問題求解的不完整代碼：defsolveNQueen(N):pool=#Adefqueen(cur=0):ifcur==len(pool):return#Xres=#Yforcolinrange(len(pool)):pool[cur],flag=col,Trueforrowinrange(cur):ifpool[row]==colorabs(col-pool[row])==cur-row:flag=Falsebreakifflag:res+=queen(cur+1)returnresreturnqueen(0)#testprint(solveNQueen(8))閱讀代碼，選出正確的選項H、該算法時間復(fù)雜度為O(N)I、該算法時間復(fù)雜度為O(N^2)本題答案：【A處可以填“[None]*N”#若X處填[list(pool)]，Y處填[]，該函數(shù)可返回N皇后問題的所有解#若X處填1，Y處填0，該函數(shù)可返回N皇后問題解的個數(shù)】7、【多選題】以下哪些問題可用動態(tài)規(guī)劃算法解決？本題答案：【斐波那契數(shù)列求值#單詞最短編輯距離】8、【多選題】以下哪些說法是錯誤的？H、動態(tài)規(guī)劃不能減少算法的時間復(fù)雜度本題答案：【函數(shù)值緩存不能減少算法的時間復(fù)雜度#函數(shù)值緩存可以減少算法的空間復(fù)雜度#動態(tài)規(guī)劃可以減少算法的空間復(fù)雜度#動態(tài)規(guī)劃不能減少算法的時間復(fù)雜度】第七周作業(yè)第七周測驗1、【單選題】以下關(guān)于冒泡和選擇排序算法的敘述何者正確？本題答案：【其它選項皆不正確。】2、【單選題】以下關(guān)于歸并和快速排序算法的敘述何者正確？本題答案：【空間復(fù)雜度上，快速排序的復(fù)雜度較低】3、【單選題】設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，利用冒泡排序進行升序排序，則第一趟冒泡排序的結(jié)果為以下何者？本題答案：【2，5，3，6，8】4、【單選題】設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，利用插入排序進行升序排序，則第二次插入排序的結(jié)果為以下何者？本題答案：【2，5，6，3，8】5、【單選題】給定兩個已分別排序好的列表mylst1,mylst2，兩者的長度分別為mn為已知，現(xiàn)要查找兩表合并后的中位數(shù)，問最好的查找方式的時間復(fù)雜度？（可以理解為，查找alist=sorted(mylst1+mylst2)的中位數(shù)的時間復(fù)雜度）本題答案：【O(logm)】6、【多選題】所謂排序算法的穩(wěn)定性是指：排序前，2個相等的數(shù)，其在序列的前后位置順序，和排序后它們兩個的前后位置順序相同。以下哪些排序算法是穩(wěn)定的？本題答案：【冒泡排序#插入排序#歸并排序】7、【多選題】現(xiàn)在有一個幾乎順序排列的，非常大的列表。問以下哪些算法有可能得到時間復(fù)雜度O(N)?本題答案：【冒泡排序#插入排序#歸并排序】8、【多選題】以下哪些排序方式，其最壞情況的時間復(fù)雜度O(N^2)的？本題答案：【快速排序#選擇排序#冒泡排序#插入排序】第八周作業(yè)第八周測驗1、【單選題】假設(shè)你將下列數(shù)據(jù)：113,117,97,100,114,108,116,105,99根據(jù)開放定址的線性探測法，按順序填入長度為11的散列表中，且散列函數(shù)選為h(n)=n%11哪一個選項最好地表達(dá)了填入數(shù)據(jù)之后散列表的狀況？本題答案：【99,100,__,113,114,__,116,117,105,97,108】2、【單選題】對于一個有13個槽的散列表，選取散列函數(shù)為h(n)=n%13，沖突解決方案選為開放定址的線性探測，以首個槽為0號，末個槽為12號。26，130和27按順序填入，問他們的填入槽號分別為？本題答案：【0，1，2】3、【單選題】對于一個有13個槽的散列表，選取散列函數(shù)為h(n)=n%13，沖突解決方案選為數(shù)據(jù)項鏈方法，以首個槽為0號，末個槽為12號。26，130和27按順序填入，問他們的填入槽號分別為？本題答案：【0，0，1】4、【單選題】以下是一個槽數(shù)為7的散列表，采用開放定址的線性探測：7，14，21，__，25，18，11查找數(shù)據(jù)項21時需要經(jīng)過幾次比對（計算槽號次數(shù)不計）？本題答案：【3】5、【單選題】以下是一個槽數(shù)為7的散列表，采用開放定址的線性探測：7，14，21，__，25，18，11查找數(shù)據(jù)項24時需要經(jīng)過幾次數(shù)據(jù)比對（計算槽號次數(shù)不計）？本題答案：【0】6、【多選題】下列關(guān)于一個數(shù)據(jù)項數(shù)量為N的完美散列的敘述何者正確？本題答案：【散列查找的時間復(fù)雜度在O(1)#散列的存儲一般需要比順序存儲使用更多存儲空間#python中的字典數(shù)據(jù)類型是散列的一種應(yīng)用】7、【多選題】假設(shè)你想為全學(xué)院畢業(yè)班同學(xué)共350人做通訊錄，且打算將11位手機號存儲在某采用開放定址的線性探測的散列表。以下散列方案中合適為？本題答案：【選取手機號末三碼#選取手機號對607（607是一個質(zhì)數(shù)）的余數(shù)】8、【多選題】以下關(guān)于散列算法分析的敘述何者錯誤？本題答案：【如果采用數(shù)據(jù)鏈來解決沖突，負(fù)載因子0.8，成功的查找，平均需要比對次數(shù)約為3#如果采用數(shù)據(jù)鏈來解決沖突，負(fù)載因子8，失敗的查找，平均需要比對次數(shù)約為5】第九周作業(yè)第九周測驗1、【單選題】按照課件”603樹的嵌套列表實現(xiàn)“的函數(shù)定義進行以下操作：x=BinaryTree('a')insertLeft(x,'b')insertRight(x,'c')insertRight(getRightChild(x),'d')insertLeft(getRightChild(getRightChild(x)),'e')樹x的結(jié)果是？本題答案：【['a',['b',[],[]],['c',[],['d',['e',[],[]],[]]]]】2、【單選題】設(shè)x是一個完全二叉樹，x共有33個節(jié)點，并以非嵌套列表的形式給所有節(jié)點編號1~33（此部分可參考”608優(yōu)先隊列和二叉堆“）。選出錯誤的選項。本題答案：【整個樹的左子樹比右子樹多1個節(jié)點#27號節(jié)點的父節(jié)點是14號】3、【單選題】此處規(guī)定二叉樹中，左子節(jié)點與右子節(jié)點地位不同（即某個父節(jié)點只有一個子節(jié)點時，也要區(qū)分它是左子節(jié)點還是右子節(jié)點）。定義一個函數(shù)c(n)，為按照此方法，構(gòu)建一個包含n個節(jié)點的，符合規(guī)則的樹的方法數(shù)。問c(1),c(2),c(3),c(4)的值。本題答案：【1，2，5，14】4、【單選題】以下關(guān)于空樹說法何者正確？本題答案：【是一個樹，也是一個二叉樹】5、【單選題】四叉樹是一種樹狀結(jié)構(gòu)，常用于圖像或空間索引，典型體現(xiàn)為快速加載低清圖像或地圖，并隨著讀入數(shù)據(jù)的量的增加，逐漸提高解析度。四叉樹的每個節(jié)點，恰有0或4個子節(jié)點，且每個子節(jié)點的地位也不同（在圖像或空間信息處理上，子節(jié)點的地位通常表示相對位置）。以下關(guān)于非空的四叉樹的說法，何者錯誤？本題答案：【若某個四叉樹有n個節(jié)點，則樹的高度有ceil(log_4(n))層】6、【多選題】關(guān)于樹myTree=['a',['b',['d',[],[]],['e',[],[]]],['c',['f',[],[]],[]]]的說法，何者正確？本題答案：【左子樹是['b',['d',[],[]],['e',[],[]]]#左子樹的根是'b'#右子樹是['c',['f',[],[]],[]]】7、【多選題】設(shè)x是一個完全二叉樹，x共有5個深度為3的節(jié)點，并以非嵌套列表的形式給所有節(jié)點編號（此部分可參考”608優(yōu)先隊列和二叉堆“）。選出正確的選項。本題答案：【x共有12個節(jié)點#6號節(jié)點有子節(jié)點12#7號節(jié)點沒有子節(jié)點】8、【多選題】設(shè)一個二叉樹有p個出度（此處可以理解為子節(jié)點的個數(shù)）為0的節(jié)點，q個出度為1的節(jié)點，r個出度為2的節(jié)點，問下列敘述何者正確？本題答案：【此樹的總節(jié)點數(shù)為p+q+r#葉節(jié)點有p個#p=r+1】第十周作業(yè)第十周測驗1、【單選題】如下哪個樹正確地顯示了按順序插入鍵值5，30，2，40，25，4后的二叉搜索樹？本題答案：【】2、【單選題】對以下這棵樹：本題答案：【12，2】3、【單選題】下圖有兩棵樹，其中a（）平衡二叉樹，b（）平衡二叉樹。本題答案：【不是，是】4、【單選題】對下面這棵樹查找元素77，在查找失敗前需要進行幾次比對？本題答案：【3】5、【單選題】高度為4的平衡二叉樹最少有（）個節(jié)點。本題答案：【12】6、【單選題】考慮規(guī)模為n的二叉搜索樹中，put,get,del,in四個方法的時間復(fù)雜度數(shù)量級。四個方法中，有（）個方法在最差情況下，具有O(n)的時間復(fù)雜度本題答案：【4】7、【多選題】將鍵值1，2，3，4，5，6，7，8，9，10的10個元素以某種順序插入某二叉搜索樹后，發(fā)現(xiàn)這個樹的根是3。問這個樹的高度可能為多少？（規(guī)定僅有根的樹的高度為0）本題答案：【3#4#5#6#7】8、【多選題】這是一棵右重樹，圈內(nèi)寫出其點的名稱和其平衡因子：本題答案：【T的根是C#T的根是B#根的左子節(jié)點是A#根的右子節(jié)點是D】第十一周作業(yè)第十一周測驗1、【單選題】設(shè)無向圖的頂點個數(shù)為n，且任何邊的兩端不是相同頂點，則該圖最少有(??)條邊。本題答案：【0】2、【單選題】設(shè)無向圖的頂點個數(shù)為n，且任何邊的兩端不是相同頂點，則該圖最多有(??)條邊。本題答案：【n(n-1)/2】3、【單選題】在一個有向圖中，若兩不同頂點之間的路徑長度為k，則該路徑上的頂點數(shù)（含頭尾）為本題答案：【k+1】4、【單選題】有一個無向圖的鄰接矩陣如下圖所示。問此無向圖有（）條邊，（）個連通分支。本題答案：【6，2】5、【單選題】下面關(guān)于圖的存儲的敘述中，哪一個是正確的？本題答案：【用鄰接矩陣存儲圖，占用的存儲空間只與圖中頂點數(shù)有關(guān)，而與邊數(shù)無關(guān)】6、【多選題】設(shè)無向圖的頂點個數(shù)為n，且任何邊的兩端不是相同頂點，問關(guān)于這個無向圖的連通分量的數(shù)量敘述哪些正確？本題答案：【至少有1個連通分量#至多有n個連通分量】7、【多選題】設(shè)無向圖的頂點個數(shù)為n，且任何邊的兩端不是相同頂點，以下關(guān)于這個無向圖的頂點的度數(shù)敘述，哪些錯誤？本題答案：【各頂點的度數(shù)最少為1（指頂點的度數(shù)可能為1，但不可能少于1；其它選項同理）#各頂點的度數(shù)最多為n】8、【多選題】假設(shè)圖G是有4個頂點的有向圖，且不同的邊不同時具有有相同的起點與終點（即：給定起點與終點，圖中最多只有一條邊符合條件）。以下敘述何者正確？本題答案：【邊的數(shù)量的最大可能值為12#如果G是無圈圖，那么邊的數(shù)量的最大可能值為6】第十二周作業(yè)第十二周測驗1、【單選題】下列關(guān)于Dijkstra算法的說法錯誤的有本題答案：【當(dāng)圖中存在負(fù)權(quán)邊時，Dijkstra算法必定不能求出源點到所有點的最短路#Dijkstra算法不適用于無向圖】2、【單選題】下列說法錯誤的是本題答案：【一個無環(huán)有向圖的拓?fù)渑判蛐蛄斜匚ㄒ弧?、【單選題】下圖中的強連通分支的個數(shù)為多少個？本題答案：【3】4、【單選題】無向圖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)}，對該圖進行深度優(yōu)先遍歷（優(yōu)先訪問編號小的結(jié)點），得到的頂點序列為？本題答案：【abedfc】5、【單選題】請使用Prim算法從結(jié)點0出發(fā)求下圖的最小生成樹，依次寫出每次被加入到最小生成樹中邊的編號（如果同時存在多條邊滿足要求，選擇編號最小的）。頂點a到頂點b(ab)之間的邊編號為ab，例如圖中權(quán)值為1的邊編號為02。本題答案：【0225351214】6、【多選題】在有向圖G的拓?fù)湫蛄兄?，若頂點在頂點之前，則下列情形可能出現(xiàn)的有本題答案：【G中有邊(，)#G中沒有邊(，)#G中有一條從到的路徑】7、【多選題】選出正確的敘述。本題答案：【將有向圖的一個強連通分量中的邊全部反向仍然是強連通分量#對于無向圖，所有結(jié)點的度數(shù)加起來一定是偶數(shù)#對于有向圖，所有結(jié)點的入度和，與所有結(jié)點的出度和，相加一定是偶數(shù)】8、【多選題】有向圖G具有四個頂點1~4和三條邊1-3,2-4,3-4，選出它可能的拓?fù)渑判?。本題答案：【1234#1324#2134】客觀題部分1、【單選題】計算下列代碼運行以后s的值：n=10s=0forkinrange(1,n-1):forjinrange(n,k-2,-1):s+=1本題答案：【60】2、【單選題】現(xiàn)有6個不同的元素，按給定順序輸入到一個原本為空的雙端隊列，可以得到多少種不同的排列？本題答案：【32】3、【單選題】假設(shè)一棵二叉樹中，度為2的結(jié)點有100個，度為1的結(jié)點有102個，度為0的結(jié)點有多少個？本題答案：【101】4、【單選題】某二叉樹中序序列為ABCDEFG，前序序列為EACBDGF，則其后序序列是？本題答案：【以上皆非】5、【單選題】對二叉搜索樹進行（）遍歷，可以得到該樹所有結(jié)點構(gòu)成的順序排序序列。本題答案：【中序#其它選項都不對】6、【單選題】用相鄰矩陣A表示圖，判定任意兩個頂點Vi和Vj之間，是否有長度不超過3的路徑相連，則只要檢查（）的第i行第j列的元素是否有非零元素即可。本題答案：【其它選項都不對】7、【單選題】下圖有9個點和12條有向邊，問這些點構(gòu)成幾個強連通分支？本題答案：【2】8、【單選題】某項任務(wù)有五個子任務(wù)ABCDE，其中進行A之前需要先完成BD，進行B之前需要先完成CE，進行D之前需要先完成E，且每次只可進行一個子任務(wù)。問完成任務(wù)的要求下，子任務(wù)的進行順序有幾種可能？本題答案：【5】9、【多選題】已知有六個代碼，以下給出它們對應(yīng)的時間復(fù)雜度：(1)100*n^13+100*n(2)1000000*n+n^13(3)n^50+1(4)-n^20+n!(5)(logn)^1000(6)2^(n^1.5)問關(guān)于各個時間復(fù)雜度的比較，下列哪些正確？本題答案：【(4)(3)(2)#(4)(1)(5)#(6)(3)(2)】10、【多選題】順序棧是用一段連續(xù)的空間存儲內(nèi)容，本質(zhì)是順序表。鏈?zhǔn)綏t是采用單鏈表的方式存儲。下列關(guān)于這兩種存儲方式的說法正確的是：本題答案：【順序棧的壓棧（入棧）和出棧操作只需常數(shù)時間。#鏈?zhǔn)綏５膲簵＃ㄈ霔＃┖统鰲２僮髦恍璩?shù)時間。#順序棧需要指定一個具體的長度】11、【多選題】一個階為4的B樹符合以下條件：(1)若一個節(jié)點非葉節(jié)點，那么它有2，3或4個子節(jié)點；(2)所有的葉節(jié)點到根節(jié)點的距離均相同。已知T是一個階為4的B樹，且T有8個葉節(jié)點。問T的總節(jié)點數(shù)可能是多少（包含根節(jié)點和剛剛的8個葉節(jié)點）？本題答案：【11#12#13#15】12、【多選題】已知一個棧的輸出是按ABCD的順序，問以下何者為不可能的入棧順序？本題答案：【BCAD#CADB#CDAB】13、【多選題】下面的排序算法哪些是不穩(wěn)定的?本題答案：【快速排序#選擇排序#希爾排序(Shell'sSort)#堆排序】14、【多選題】設(shè)G是由4個頂點組成的有向圖，其中G恰好有2個強連通分支，且G的任意兩條不同邊都不具有完全相同的始點和終點。選出G的可能的總邊數(shù)的最小值和最大值（即選出一個值作為可能邊數(shù)量的最小值，選出另一個