MOOC 計算機軟件基礎-常州工學院 中國大學慕課答案

MOOC計算機軟件基礎-常州工學院中國大學慕課答案線性表單元測驗1、問題：數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為（）選項：A、存儲結構B、邏輯結構C、順序存儲結構D、鏈式存儲結構正確答案:【順序存儲結構】2、問題：一個順序表第一個元素的順序存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）選項：A、110B、108C、100D、120正確答案:【108】3、問題：循環(huán)隊列的人隊操作應為()。選項：A、sq.rear=sq.rear+1；sq.data[sq.rear]=x；B、sq.data[sq.rear]=x；sq.rear=sq.rear+1；C、sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear]=x；D、sq.data[sq.rear]=x；sq.rear=(sq.rear+1)%maxsize；正確答案:【sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear]=x；】4、問題：假設用一維數組變量sq[0..n-1]實現循環(huán)隊列，front和rear分別是隊頭和隊尾指針，則出隊的操作是（）。選項：A、sq.front=(sq.ftont+1)%maxsizeB、sq.front=sq.front+1C、sq.rear=（sq.rear+1）%maxsizeD、sq.rear=sq.rear+1正確答案:【sq.front=(sq.ftont+1)%maxsize】5、問題：若已知一個棧的入棧序列是1，2，3，，，，n，其輸出序列為pl，p2，p3，?，pn，若p1=n，則pi為（）選項：A、iB、n-iC、n-i+1D、不確定正確答案:【n-i+1】6、問題：若入棧序列是a,b,c,d,e，則不可能的出棧序列是（）。選項：A、edcbaB、decbaC、dceabD、abcde正確答案:【dceab】7、問題：假設以數組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數為（)選項：A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正確答案:【(rear-front+m)%m】8、問題：最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（)選項：A、(rear+l)MODn=frontB、rear=frontC、rear+l=frontD、(rear-1)MODn=front正確答案:【rear=front】9、問題：順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。（）選項：A、正確B、錯誤正確答案:【錯誤】10、問題：順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）選項：A、正確B、錯誤正確答案:【錯誤】11、問題：鏈表的物理存儲結構具有同鏈表一樣的順序。（）選項：A、正確B、錯誤正確答案:【錯誤】12、問題：鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。（）選項：A、正確B、錯誤正確答案:【錯誤】13、問題：線性表在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上相鄰。（）選項：A、正確B、錯誤正確答案:【正確】14、問題：棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。選項：A、正確B、錯誤正確答案:【正確】15、問題：對于不同的使用者，一個表結構既可以是棧，也可以是隊列，也可以是線性表。選項：A、正確B、錯誤正確答案:【正確】16、問題：棧和隊列是一種非線性數據結構選項：A、正確B、錯誤正確答案:【錯誤】17、問題：棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。選項：A、正確B、錯誤正確答案:【正確】18、問題：隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。選項：A、正確B、錯誤正確答案:【錯誤】19、問題：一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。選項：A、正確B、錯誤正確答案:【錯誤】20、問題：棧和隊列邏輯上都是線性表。選項：A、正確B、錯誤正確答案:【正確】21、問題：棧和隊列都是限制存取點的線性結構。選項：A、正確B、錯誤正確答案:【正確】22、填空題：在有n個元素的順序表中刪除一個元素，需要平均移動____個元素.正確答案:【n/2##%_YZPRLFH_%##一半】23、填空題：向一個長度為n的的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動個元素正確答案:【n-i+1】24、填空題：一個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動個元素。正確答案:【n-i】樹和二叉樹單元測驗1、問題：不含任何結點的空樹選項：A、是一棵樹B、是一棵二叉樹C、是一棵樹也是一棵二叉樹D、既不是樹也不是二叉樹正確答案:【是一棵樹也是一棵二叉樹】2、問題：二叉樹是非線性數據結構，所以選項：A、它不能用順序存儲結構存儲B、它不能用鏈式存儲結構存儲C、順序存儲結構和鏈式存儲結構都能存儲D、順序存儲結構和鏈式存儲結構都不能使用正確答案:【順序存儲結構和鏈式存儲結構都能存儲】3、問題：具有n(n0)個結點的完全二叉樹的深度為選項：A、log2(n)B、?log2(n)?C、?log2(n)?+1D、log2(n)+1正確答案:【?log2(n)?+1】4、問題：假定在一棵二叉樹中，雙分支結點數為15,單分支結點數為30個，則葉子結點數為選項：A、15B、16C、17D、47正確答案:【16】5、問題：按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有______種選項：A、3B、4C、5D、6正確答案:【5】6、問題：按照樹的定義，具有3個不同數據結點的不同的樹有幾種？選項：A、2B、3C、4D、5正確答案:【2】7、問題：深度為7的二叉樹至多有_____個結點選項：A、64B、128C、127D、14正確答案:【127】8、問題：任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序選項：A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對正確答案:【不發(fā)生改變】9、問題：某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是選項：A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca正確答案:【gdbehfca】10、問題：在一非空二叉樹的中序遍歷序列中，根結點的右邊選項：A、只有右子樹上的所有結點B、只有右子樹上的部分結點C、只有左子樹上的部分結點D、只有左子樹上的所有結點正確答案:【只有右子樹上的所有結點】11、問題：二叉樹中每個結點的兩棵子樹的高度差等于1選項：A、正確B、錯誤正確答案:【錯誤】12、問題：二叉樹中每個結點的兩棵子樹是有序的選項：A、正確B、錯誤正確答案:【正確】13、問題：二叉樹中每個結點有兩棵非空子樹或有2棵空子樹選項：A、正確B、錯誤正確答案:【錯誤】14、問題：選項：A、正確B、錯誤正確答案:【錯誤】15、問題：具有20個結點的完全二叉樹有9個度為2的結點選項：A、正確B、錯誤正確答案:【正確】16、問題：二叉樹中所有結點，如果不存在非空左子樹，則不存在非空右子樹選項：A、正確B、錯誤正確答案:【錯誤】17、問題：二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法選項：A、正確B、錯誤正確答案:【正確】18、填空題：寫出下面這棵二叉樹的先序遍歷正確答案:【FBADCEGIH】19、填空題：寫出下面這棵二叉樹的中序遍歷正確答案:【ABCDEFGHI】20、填空題：寫出下面這棵二叉樹的后序遍歷正確答案:【ACEDBHIGF】21、填空題：寫出下面這棵二叉樹的先序遍歷正確答案:【ABDEGCF】22、填空題：寫出下面這棵二叉樹的中序遍歷正確答案:【DBGEACF】23、填空題：寫出下面這棵二叉樹的后序遍歷正確答案:【DGEBFCA】24、填空題：假設用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構成，這8個字母在電文中出現的概率分別為{a(0.07)，b(0.19)，c(0.02)，d(0.06)，e(0.32)，f(0.03)，g(0.21)，h(0.10)}。試構造哈夫曼編碼，問：每個字符的編碼長度是多少？答案格式為：a?b?c?d?e?f?g?h?問號改為相應的字符編碼長度正確答案:【a4b2c5d4e2f5g2h4】25、填空題：按423056702580365060754590這樣的順序輸入構造一個二叉排序樹，問：元素305060708090各在二叉樹的第幾層？注：答案中不要有空格和換行正確答案:【234345】圖單元測驗1、問題：圖中有關路徑的定義是（）選項：A、由頂點和相鄰頂點序偶構成的邊所形成的序列B、由不同頂點所形成的序列C、由不同邊所形成的序列D、上述定義都不是正確答案:【由頂點和相鄰頂點序偶構成的邊所形成的序列】2、問題：設無向圖的頂點個數為n，則該圖最多有（）條邊。選項：A、n-1B、n(n-1)/2C、n(n+1)/2D、n正確答案:【n(n-1)/2】3、問題：—個n個頂點的連通無向圖，其邊的個數至少為（）選項：A、n-1B、nC、n+1D、nlogn正確答案:【n-1】4、問題：要連通具有n個頂點的有向圖，至少需要（）條邊。選項：A、n-1B、nC、n+1D、2n正確答案:【n】5、問題：n個結點的完全有向圖含有邊的數目（）選項：A、n*nB、n(n+1)C、n/2D、n*(n-1)正確答案:【n*(n-1)】6、問題：在一個無向圖中，所有頂點的度數之和等于所有邊數（）倍選項：A、1/2B、2C、1D、4正確答案:【2】7、問題：在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（）倍選項：A、1/2B、2C、1D、4正確答案:【1】8、問題：下列說法不正確的是（）選項：A、圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次B、遍歷的基本算法有兩種：深度遍歷和廣度遍歷C、圖的深度遍歷不適用于有向圖D、圖的深度遍歷是一個遞歸過程正確答案:【圖的深度遍歷不適用于有向圖】9、問題：無向圖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)先遍歷，得到的頂點序列正確的是（）選項：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,e,d,f,c,b】10、問題：關鍵路徑是是事件結點網絡中（）選項：A、從源點到匯點的最長路徑B、從源點到匯點的最短路徑C、最長回路D、最短回路正確答案:【從源點到匯點的最長路徑】11、問題：有e條邊的無向圖，在鄰接表中有e個結點選項：A、正確B、錯誤正確答案:【錯誤】12、問題：有向圖中頂點V的度等于其鄰接矩陣中第V行中的1的個數選項：A、正確B、錯誤正確答案:【錯誤】13、問題：強連通圖的各頂點間均可達選項：A、正確B、錯誤正確答案:【正確】14、問題：有n個頂點的無向圖，采用鄰接矩陣表示，圖中的邊數等于鄰接矩陣中非零元素之和的一半。選項：A、正確B、錯誤正確答案:【正確】15、問題：無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣一定是非對稱矩陣。選項：A、正確B、錯誤正確答案:【錯誤】16、問題：鄰接矩陣適用于有向圖和無向圖的存儲，但不能存儲帶權的有向圖和無向圖，而只能使用鄰接表存儲形式來存儲它選項：A、正確B、錯誤正確答案:【錯誤】17、問題：用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點個數有關，而與圖的邊數無關。選項：A、正確B、錯誤正確答案:【正確】18、問題：不同的求最小生成樹的方法最后得到的生成樹是相同的.選項：A、正確B、錯誤正確答案:【錯誤】19、問題：連通圖上各邊權值均不相同，則該圖的最小生成樹是唯一的。選項：A、正確B、錯誤正確答案:【正確】20、問題：樹中的結點和圖中的頂點就是指數據結構中的數據元素選項：A、正確B、錯誤正確答案:【正確】查找單元測驗1、問題：用折半查找法的查找速度比用順序查找法的查找速度_________.選項：A、必然慢B、必然快C、速度相等D、快慢不定正確答案:【快慢不定】2、問題：適合折半查找的表的存貯方式及元素排列要求為()選項：A、鏈式存貯元素無序B、鏈式存貯元素有序C、順序存貯元素無序D、順序存貯元素有序正確答案:【順序存貯元素有序】3、問題：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（）比較大小，查找結果是失敗。選項：A、20，70，30，50B、30，88，70，50C、20，50D、30，88，50正確答案:【20，70，30，50】4、問題：折半搜索與二叉搜索樹的時間性能（）選項：A、相同B、完全不同C、有時不相同D、數量級都是O（log2n）正確答案:【數量級都是O（log2n）】5、問題：將10個元素散列到100000個單元的哈希表中，則（????）產生沖突。選項：A、一定會B、一定不會C、仍可能會D、以上都不對正確答案:【仍可能會】6、問題：若查找每個元素的概率相等，則在長度為n的順序表上查找任一元素的平均查找長度為(??)。選項：A、nB、n+1C、（n-1）/2D、（n+1）/2正確答案:【（n+1）/2】7、問題：對于長度為9的順序存儲的有序表，若采用折半查找，在等概率情況下的平均查找長度為(??)。選項：A、20/9B、18/9C、25/9D、22/9正確答案:【25/9】8、問題：對于長度為18的順序存儲的有序表，若采用折半查找，則查找第15個元素的比較次數為(??)。選項：A、3B、4C、5D、6正確答案:【4】9、問題：對于順序存儲的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，則查找元素26的比較次數為(??)。選項：A、2B、3C、4D、5正確答案:【4】10、問題：對具有n個元素的有序表采用折半查找，則算法的時間復雜度為(??)。選項：A、O(n)B、O()C、O（1）D、O（log2(n)）正確答案:【O（log2(n)）】11、問題：若采用鏈地址法解決沖突，散列函數為H（key）=key?MOD?17，則需?(（1）)?個鏈表。這些鏈的鏈首指針構成一個指針數組，數組的下標范圍為（（2））選項：A、13B、16C、17D、任意E、0至16F、1至16G、0至17H、1至17正確答案:【17#0至16】12、問題：執(zhí)行折半查找法要求查找表必須為順序結構的有序表。選項：A、正確B、錯誤正確答案:【正確】13、問題：100個元素的有序表中，折半查找成功的最大查找長度為8選項：A、正確B、錯誤正確答案:【正確】14、問題：二叉判定樹是一棵完全二叉樹選項：A、正確B、錯誤正確答案:【錯誤】15、問題：在二叉排序樹中插入一個結點，總是插入到葉子結點的下面選項：A、正確B、錯誤正確答案:【錯誤】16、問題：在二叉排序樹中插入一個新的結點，那么它必定是葉子結點選項：A、正確B、錯誤正確答案:【正確】17、填空題：在對有二十個數據有序表作二分查找時有___________個結點的查找長度是4正確答案:【8】18、填空題：折半查找有序表（4、6、12、20、28、38、50、70、88、100），若查找表中元素20，它將依次與表中元素（）比較大小。注意：答案中數據之間全部用英文逗號分隔或全部用全角逗號分隔，不能加空格，數字用半角英文格式正確答案:【28,6,12,20##%_YZPRLFH_%##28，6，12，20】19、填空題：設哈希（Hash）表的地址范圍為0～17，哈希函數為：H（K）＝KMOD16。K為關鍵字，用線性探測法再散列法處理沖突，輸入關鍵字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問題：（1）若查找關鍵字63，需要依次與哪些關鍵字進行比較？（2）假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。注意：（1）答案中數據之間全部用英文逗號分隔或全部用全角逗號分隔，不能加空格，數字及除號用半角英文格式（2）2個題之間用分號分隔答案格式如：3，4；2/5正確答案:【31，46，47，32，17，63；21/11##%_YZPRLFH_%##31,46,47,32,17,63;21/11】20、填空題：已知一個順序存儲的有序表為（13，24，32，37，42，55，59，60，75，81）共10個元素，按折半查找算法，求其平均查找長度正確答案:【2.9##%_YZPRLFH_%##29/10】排序單元測驗1、填空題：已知一組記錄為(4938659776132750)，給出采用快速排序法進行排序時的第一趟的排序結果格式要求：數字之間用空格分隔，如：1122334455667788正確答案:【2738134976976550】2、填空題：已知一組記錄為(4938659776132750)，給出采用冒泡排序法進行排序時的第4趟的排序結果格式要求：數字之間用空格分隔，如：1122334455667788正確答案:【3813274950657697】3、填空題：已知一組記錄為(4938659776132750)，給出采用直接選擇排序法進行排序時的第4趟的排序結果格式要求：數字之間用空格分隔，如：1122334455667788正確答案:【1327384976976550】4、填空題：已知一