超星爾雅學(xué)習(xí)通《數(shù)據(jù)結(jié)構(gòu)與算法》章節(jié)測(cè)試答案

1、超星爾雅學(xué)習(xí)通數(shù)據(jù)結(jié)構(gòu)與算法章節(jié)測(cè)試答案課程簡(jiǎn)介：數(shù)據(jù)結(jié)構(gòu)是一門(mén)面向設(shè)計(jì)，且處于計(jì)算機(jī)學(xué)科核心地位的技術(shù)基礎(chǔ)和主干必修課，也是算法分析與課程簡(jiǎn)介：數(shù)據(jù)結(jié)構(gòu)是一門(mén)面向設(shè)計(jì)，且處于計(jì)算機(jī)學(xué)科核心地位的技術(shù)基礎(chǔ)和主干必修課，也是算法分析與設(shè)計(jì)、操作系統(tǒng)、編譯技術(shù)、計(jì)算機(jī)圖形與圖像處理等專(zhuān)業(yè)課程的先修課程。引論1.【單選題】1.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( )。A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案：C2.【單選題】2. 在數(shù)據(jù)結(jié)構(gòu)中,從存儲(chǔ)結(jié)構(gòu)上可以將之分為( )。A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、順序存儲(chǔ)和非順序存儲(chǔ)C、緊湊結(jié)構(gòu)和非緊

2、湊結(jié)構(gòu)D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)答案：B3.【單選題】3. 某算法的時(shí)間復(fù)雜度是O(n2),表明該算法的( )。A、執(zhí)行時(shí)間與n2成正比B、問(wèn)題規(guī)模是n2C、執(zhí)行時(shí)間等于n2D、問(wèn)題規(guī)模與n2成正比答案：A4.【單選題】4. 在下面的程序段中,x=x+1;的語(yǔ)句頻度為( )。 for( i=1;i<=n;i+) for( j=1;j<=n;j+) x=x+1;A、O(2n)B、O(n)C、O(n2)D、O(log2n)答案：C5.【單選題】5. 以下數(shù)據(jù)結(jié)構(gòu)中,( )是非線性數(shù)據(jù)結(jié)構(gòu)。A、樹(shù)B、字符串C、隊(duì)D、棧答案：A6.【單選題】6. 順序存儲(chǔ),存儲(chǔ)單元的地址( )。A、一定連續(xù)

3、B、一定不連續(xù)C、不一定連續(xù)D、部分連續(xù),部分不連續(xù)答案：A7.【單選題】7.評(píng)價(jià)一個(gè)算法性能好壞的重要標(biāo)準(zhǔn)是( )。A、算法的正確性B、算法易于調(diào)試C、算法的時(shí)間和空間復(fù)雜度D、算法易于理解答案：C8.【單選題】8. 若需要利用形式參數(shù)直接訪問(wèn)修改實(shí)參值,則應(yīng)將形參說(shuō)明為( )參數(shù)。A、值參數(shù)B、實(shí)地址C、指針D、地址參數(shù)答案：C9.【判斷題】9. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入、刪除運(yùn)算效率高。答案：×10.【判斷題】10. 數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是算法的時(shí)間復(fù)雜度和空間復(fù)雜度。答案：線性表1.【單選題】1. 下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)()。A、可方便地用于

4、各種邏輯結(jié)構(gòu)的存儲(chǔ)表示B、插入運(yùn)算方便C、刪除運(yùn)算方便D、存儲(chǔ)密度大答案：D2.【單選題】2. 若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算,則利用()存儲(chǔ)方式最節(jié)省時(shí)間。A、順序表B、雙鏈表C、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D、單循環(huán)鏈表答案：A3.【單選題】3. 設(shè)某順序表中第一個(gè)元素的地址是se(下標(biāo)從1開(kāi)始),每個(gè)結(jié)點(diǎn)占m個(gè)單元,則第i個(gè)結(jié)點(diǎn)的地址為()。A、se+(i-1)×mB、se+(i+1)×mC、se+i×mD、se-i×m答案：A4.【單選題】4. 某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元

5、素,則采用()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A、單鏈表B、僅有尾指針的單循環(huán)鏈表C、僅有頭指針的單循環(huán)鏈表D、雙鏈表答案：B5.【單選題】5. 若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu),在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為()。A、O(n)B、O(0)C、O(1)D、O(n2)答案：A6.【單選題】6. 在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn),正確的操作是()。A、s->next=p->next;p->next=s;B、p->next=s;s->next=p->next;C、p->next=s;p->next=s->next;D、p-

6、>next=s->next;p->next=s;答案：A7.【單選題】7. 對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表,判定該表為空表的條件是()。A、headnext=NULL;B、head=NULL;C、headnext=he;D、head!=NULL;答案：A8.【判斷題】8. 靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類(lèi)似,不需做元素的移動(dòng)。答案：9.【判斷題】9. 順序表適宜于順序存取,而鏈表適宜于隨機(jī)存取。答案：×10.【判斷題】10. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。答案：棧和隊(duì)列1.【單選題】1. 棧和隊(duì)列都是( )

7、。A、限制存取點(diǎn)的非線性結(jié)構(gòu)B、順序存儲(chǔ)的線性結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)D、限制存取點(diǎn)的線性結(jié)構(gòu)答案：D2.【單選題】2. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空,元素e1,e2,e3,e4,e5和e6依次通過(guò)棧S,一個(gè)元素出棧后隨即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1,則棧S的容量至少應(yīng)該是( )。A、3B、6C、4D、2答案：A3.【單選題】3. 設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否匹配出現(xiàn)的算法,采用( )的數(shù)據(jù)結(jié)構(gòu)最佳。A、棧B、順序表C、隊(duì)列D、單鏈表答案：A4.【單選題】4. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是( )。A、abc*+d-B、cb+a*d-C、ab

8、c+*d-D、abcd+*-答案：C5.【單選題】5. 遞歸過(guò)程或函數(shù)調(diào)用時(shí),處理參數(shù)及返回地址需要用一種( )的數(shù)據(jù)結(jié)構(gòu)。A、棧B、隊(duì)列C、多維數(shù)組D、線性表答案：A6.【單選題】6. 最大容量為n的循環(huán)隊(duì)列,隊(duì)尾指針為rear,隊(duì)頭指針為front,則隊(duì)空的條件是( )。A、rear=frontB、(rear+1)%n=frontC、rear+1=frontD、(rear-l)%n=front答案：A7.【單選題】7. 用帶頭結(jié)點(diǎn)的單鏈表表示隊(duì)長(zhǎng)大于1的隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn),則在進(jìn)行刪除操作時(shí)( )。A、僅修改隊(duì)頭指針B、僅修改隊(duì)尾指針C、隊(duì)頭、隊(duì)尾指針都

9、要修改D、隊(duì)頭,隊(duì)尾指針都可能要修改答案：A8.【單選題】8. 對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度和在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度分別為( )。A、O(1),O(n)B、O(n),O(n)C、O(1),O(1)D、O(n),O(1)答案：A9.【判斷題】9. 兩順序棧共享空間,也存在空間溢出問(wèn)題。答案：10.【判斷題】10.在對(duì)不帶頭結(jié)點(diǎn)的鏈隊(duì)列作出隊(duì)操作時(shí),不會(huì)改變頭指針的值。答案：×數(shù)據(jù)結(jié)構(gòu)與算法 完整 超星爾雅答案 可首頁(yè)在線搜題串1.【單選題】1. 串是一種特殊的線性表,其特殊性體現(xiàn)在( )。AA、數(shù)據(jù)元素是字符B、順序

10、存儲(chǔ)C、鏈?zhǔn)酱鎯?chǔ)D、邏輯結(jié)構(gòu)是線性結(jié)構(gòu)2.【單選題】2. 若串S= software,其前綴真子串的數(shù)目是( )。AA、7B、10C、9D、83.【單選題】3. 設(shè)有兩個(gè)串p和q ,其中q是p的子串,求q在p中首次出現(xiàn)的位置的算法稱(chēng)為( )。AA、串的模式匹配B、求子串C、串聯(lián)接D、求串長(zhǎng)4.【單選題】4. 已知串 S=aaab,其next函數(shù)值為( )。AA、0123B、1123C、1231D、12115.【單選題】5. 函數(shù)strcmp(stcabuc,stbabuc)的返回值是( )。DA、0B、-1C、2D、16.【判斷題】6. KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)回溯。7

11、.【判斷題】7. 模式串 P=abaabcac的next函數(shù)值序列為01122312。8.【判斷題】8. 串的存儲(chǔ)結(jié)構(gòu)有順序串、堆串和塊鏈串三種。9.【判斷題】9. 子串的定位運(yùn)算稱(chēng)為串的模式匹配。10.【判斷題】10. 串student和Student相等。多維數(shù)組和廣義表1.【單選題】1. 假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array1100,1100,設(shè)每個(gè)數(shù)組元素占2個(gè)存儲(chǔ)單元,基地址為10,則LOC5,5=( )。AA、818B、B 808C、1010D、10202.【單選題】2. 若對(duì)n階對(duì)稱(chēng)矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B1(n

12、(n+1)/2中,則在B中確定aij(i AA、j(j-1)/2+iB、i(i-1)/2+jC、i(i+1)/2+jD、j(j+1)/2+i3.【單選題】3. 設(shè)廣義表L=(a,b,c),則L的長(zhǎng)度和深度分別為( )。AA、1和2B、1和1C、1和3D、2和34.【單選題】4. 在稀疏矩陣的三元組順序表中,每個(gè)三元組表示( )。DA、矩陣中數(shù)據(jù)元素的行號(hào)、列號(hào)和數(shù)據(jù)值B、矩陣中非零元素的數(shù)據(jù)值C、矩陣中數(shù)據(jù)元素的行號(hào)和列號(hào)D、矩陣中非零元素的行號(hào)、列號(hào)和數(shù)據(jù)值5.【判斷題】5. 多維數(shù)組可以看作是一種特殊的線性表。正確6.【判斷題】6. 一個(gè)稀疏矩陣Am,n采用三元組順序表形式表示,若把三元組

13、中有關(guān)行下標(biāo)與列下標(biāo)的值互換,并把m和n的值互換,則就完成了Am,n的轉(zhuǎn)置運(yùn)算。X7.【判斷題】7.廣義表B = (a, B) = (a, (a, (a, ) ) ) 的長(zhǎng)度為無(wú)窮大。正確8.【判斷題】8. 一個(gè)廣義表可以為其它廣義表所共享。正確9.【判斷題】9. 稀疏矩陣中非零元素的個(gè)數(shù)遠(yuǎn)小于矩陣中元素的總數(shù)。正確10.【判斷題】10. tail(head(a,b,c,d,e)=(a,b,c,d,e)。X樹(shù)1.【單選題】1.樹(shù)最適合用來(lái)表示的結(jié)構(gòu)是( )。AA、元素間具有分支及層次關(guān)系的結(jié)構(gòu)B、元素間的有序結(jié)構(gòu)C、元素間的無(wú)序結(jié)構(gòu)D、元素間無(wú)聯(lián)系的結(jié)構(gòu)2.【單選題】2.任意一棵二叉樹(shù)的葉子結(jié)

14、點(diǎn)在其先序、中序、后序序列中的相對(duì)位置( )。BA、肯定發(fā)生變化B、肯定不發(fā)生變化C、有時(shí)發(fā)生變化D、無(wú)法確定3.【單選題】3.判斷線索二叉樹(shù)中某結(jié)點(diǎn)P有左孩子的條件是( )。DA、p->LTag=1B、p!=NULLC、p->lchild!=NULLD、p->LTag=04.【單選題】4.設(shè)森林T中有4棵樹(shù),其結(jié)點(diǎn)個(gè)數(shù)分別為n1,n2,n3,n4,那么當(dāng)森林T轉(zhuǎn)換成一棵二叉樹(shù)后,則根結(jié)點(diǎn)的右子樹(shù)上有( )個(gè)結(jié)點(diǎn)。AA、n2+n3+n4B、n1-1C、n1D、n1+n2+n35.【單選題】5.以數(shù)據(jù)集4,5,6,7,10,12,18為葉結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹(shù),其帶權(quán)路徑長(zhǎng)度

15、為( )。CA、155B、160C、165D、1706.【單選題】6.以下屬于前綴編碼的是( )。A、0,1101,1110,1100,1111B、0,1,01,010,110C、00,01,10,11,101D、01,00,10,001,110,1017.【單選題】7.一棵具有N個(gè)結(jié)點(diǎn)的二叉樹(shù)采用二叉鏈表進(jìn)行存儲(chǔ),其中空指針域有( )個(gè)。AA、N+1B、NC、N-1D、不確定8.【單選題】8.已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn),3個(gè)度為2的結(jié)點(diǎn),4個(gè)度為3的結(jié)點(diǎn),則該樹(shù)中有( )個(gè)葉子結(jié)點(diǎn)。CA、10B、11C、12D、139.【判斷題】9. 滿(mǎn)二叉樹(shù)一定完全是二叉樹(shù)。10.【判斷題】10

16、.二叉樹(shù)的遍歷結(jié)果不是唯一的。圖1.【單選題】1.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖最多有( )邊。AA、n(n-1)/2B、n(n-1)C、nD、2n2.【單選題】2.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,若采用鄰接表表示,則占用的存儲(chǔ)空間為( )。DA、n+eB、eC、2eD、n+2e3.【單選題】3.如果含有n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán),則它有( )棵生成樹(shù)。AA、nB、n-1C、n+1D、不確定4.【單選題】4.任何一個(gè)無(wú)向連通網(wǎng)的最小生成樹(shù)( )。AA、有一棵或多棵B、只有1棵C、一定有多棵D、可能不存在5.【單選題】5.判斷一個(gè)有向圖是否存在回路,可以用( )。DA、廣度優(yōu)先遍歷算法B、求關(guān)鍵路徑

17、的方法C、Dijkstra方法D、深度優(yōu)先遍歷算法6.【單選題】6.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中( )。AA、從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑B、最長(zhǎng)回路C、從源點(diǎn)到匯點(diǎn)的最短路徑D、最短回路7.【單選題】7.深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的( )。AA、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷8.【單選題】8.廣度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的( )。DA、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷9.【判斷題】9.迪杰斯特拉算法求最短路徑時(shí),是按照路徑長(zhǎng)度遞增的順序求解的。10.【判斷題】10.任何一個(gè)有向圖都一定存在拓?fù)湫蛄?。X查找1.【單選題】1. 具有12個(gè)關(guān)鍵字的有序表,折半查找的平均查找長(zhǎng)度( )。D

18、A、10/12B、25C、25/12D、37/122.【單選題】2. 如果要求用線性表既能較快地查找,又能適應(yīng)動(dòng)態(tài)變化的要求,則可采用( )查找方法。AA、分塊查找B、順序查找C、折半查找D、基于屬性3.【單選題】3. 已知一如下10個(gè)記錄的表,其關(guān)鍵字序列為(2,15,19,25,30,34,44,55,58,80),用折半查找法查找關(guān)鍵字為55的記錄,比較次數(shù)是( )。BA、1次B、2次C、3次D、4次4.【單選題】4. 如果按關(guān)鍵碼值遞增的順序依次將99個(gè)關(guān)鍵碼值插入到二叉排序樹(shù)中,則對(duì)這樣的二叉排序樹(shù)檢索時(shí),在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度ASL為( )。AA、50B、48C、4

19、5D、475.【單選題】5. 對(duì)包含n個(gè)元素的散列表進(jìn)行查找,平均查找長(zhǎng)度為( )。AA、不直接依賴(lài)于nB、O(n2)C、O(log2n)D、O(n)6.【單選題】6. 衡量查找算法效率的主要標(biāo)準(zhǔn)是( )。AA、平均查找長(zhǎng)度B、元素個(gè)數(shù)C、所需的存儲(chǔ)量D、算法難易程度7.【判斷題】7. Hash表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。X8.【判斷題】8. 在二叉樹(shù)排序樹(shù)中插入一個(gè)新結(jié)點(diǎn),總是插入到葉結(jié)點(diǎn)下面。9.【判斷題】9. 哈希表是一種將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法。10.【判斷題】10.在二叉排序樹(shù)上刪除一個(gè)結(jié)點(diǎn)時(shí),不必移動(dòng)其它結(jié)點(diǎn),只要將該結(jié)點(diǎn)的父結(jié)點(diǎn)的相應(yīng)的指針域置空即可。X排序1.

20、【單選題】1. 有一組數(shù)據(jù)(15,9,7,8,20,-1,7,4),用堆排序的篩選方法建立的初始小根堆為( )。AA、-1,4,7,8,20,15,7,9B、-1,4,8,9,20,7,15,7C、-1,7,15,7,4,8,20,9D、A,B,C均不對(duì)。2.【單選題】2. 一組記錄的關(guān)鍵字為(46,79,56,38,40,84),則利用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為( )。AA、(40, 38, 46, 56, 79, 84)B、(38, 40, 46, 56, 79, 84)C、(40, 38, 46, 79, 56, 84)D、(40, 38, 46, 84, 56, 79)3.【單選題】3. 對(duì)下列整數(shù)序列使用基數(shù)排序,一趟分配收集之后的結(jié)果是( )。(179,208,93,306,55,859,984,9,271,33)