MOOC 計(jì)算機(jī)軟件基礎(chǔ)-常州工學(xué)院 中國大學(xué)慕課答案

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