數(shù)據(jù)結(jié)構(gòu)選擇判斷復(fù)習(xí)題

1、-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-數(shù)據(jù)結(jié)構(gòu)期中期末選擇判斷復(fù)習(xí)題判斷題：U1-U31.（）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。2.（）強(qiáng)壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)平白無(wú)故的狀態(tài)。3.（）數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。4.（）數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的次序關(guān)系，它依賴(lài)于計(jì)算機(jī)的儲(chǔ)藏結(jié)構(gòu)。5.（）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)質(zhì)儲(chǔ)藏形式。6.（）數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與詳盡實(shí)現(xiàn)有關(guān)。7.（）次序儲(chǔ)藏方式的優(yōu)點(diǎn)是儲(chǔ)藏密度大，且插入，刪除運(yùn)算效率高。8.（）次序儲(chǔ)藏方式插入和刪除時(shí)的效率太低，在這方面它不如鏈?zhǔn)絻?chǔ)藏方式好。9.（）次序儲(chǔ)藏結(jié)構(gòu)的主要缺點(diǎn)是不利于插入和刪除操

2、作。10.（）對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)絻?chǔ)藏結(jié)構(gòu)必然優(yōu)于次序儲(chǔ)藏結(jié)構(gòu)。11.（）取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān)。12.（）線性表、棧和隊(duì)列都是線性結(jié)構(gòu)。13.（）鏈表是采用鏈?zhǔn)絻?chǔ)藏結(jié)構(gòu)的線性表，進(jìn)行插入、刪除操作時(shí)，在鏈表中比在次序儲(chǔ)藏結(jié)構(gòu)中效率高。14.（）線性表中每一個(gè)元素均存在唯一一個(gè)前驅(qū)和唯一一個(gè)后繼。15.（）循環(huán)鏈表不是線性表。16.（）線性表的長(zhǎng)度是線性表所占用的儲(chǔ)藏空間的大小。17.（）在單鏈表表示的線性表中，取線性表的第i個(gè)元素操作的時(shí)間復(fù)雜度為O(1)。18.（）刪除帶頭結(jié)點(diǎn)單鏈表的第一個(gè)元素結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1)。19.（）棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。2

3、0.（）棧是一種插入與刪除操作都限制在表的一端進(jìn)行的線性表。21.（）若輸入序列為1,2,3,4,5,6,則經(jīng)過(guò)一個(gè)?？梢暂敵鲂蛄?,2,5,6,4,1。22.（）在次序儲(chǔ)藏結(jié)構(gòu)表示的棧中刪除一個(gè)元素時(shí)可能會(huì)引起棧內(nèi)數(shù)據(jù)元素的搬動(dòng)。23.（）棧既可以采用次序儲(chǔ)藏結(jié)構(gòu)表示也可以采用鏈?zhǔn)絻?chǔ)藏結(jié)構(gòu)表示。24.（）隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。25.（）無(wú)論隊(duì)列采用次序儲(chǔ)藏結(jié)構(gòu)還是采用鏈?zhǔn)絻?chǔ)藏結(jié)構(gòu)，入隊(duì)列和出隊(duì)列操作的時(shí)間復(fù)雜度均為O(1)。26.（）循環(huán)隊(duì)列就是用循環(huán)鏈表表示的隊(duì)列。27.（）隊(duì)列和棧都是運(yùn)算受限的線性表，只贊同在表的兩端進(jìn)行運(yùn)算。U4-U

4、51.（）串是一種數(shù)據(jù)對(duì)象和操作都特其他線性表。2.（）KMP算法的特點(diǎn)是在模式般配時(shí)指示主串的指針不會(huì)變小。3.（）設(shè)模式串的長(zhǎng)度為m，目標(biāo)串的長(zhǎng)度為n，當(dāng)nm且辦理只般配一次的模-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-式時(shí)，樸素的般配（即子串定位函數(shù)）算法所花的時(shí)間代價(jià)可能會(huì)更為節(jié)約。4.（）數(shù)組可看作線性結(jié)構(gòu)的一種實(shí)行，因此與線性表相同，可以對(duì)它進(jìn)行插入，刪除等操作。5.（）數(shù)組不適合作為任何二叉樹(shù)的儲(chǔ)藏結(jié)構(gòu)。6.（）從邏輯結(jié)構(gòu)上看，n維數(shù)組的每個(gè)元素均屬于n個(gè)向量。7.（）稀罕矩陣壓縮儲(chǔ)藏后，必會(huì)失去隨機(jī)存取功能。8.（）一個(gè)稀罕矩陣Am*n采用三元組形式表示，若把三元組

5、中有關(guān)行下標(biāo)與列下標(biāo)的值互換，并把m和n的值互換，則就完成了Am*n的轉(zhuǎn)置運(yùn)算。（這一塊缺少答案，就麻煩各位自己找一下了）U6-U101.（）選擇排序是一種牢固的排序方法。2.（）一個(gè)有向無(wú)環(huán)圖拓?fù)渑判蚩赡懿晃ㄒ弧?.（）一棵二叉排序樹(shù)的先序序列必然是有序序列。4.（）在n個(gè)結(jié)點(diǎn)的無(wú)向圖中，若邊數(shù)大于n-1，則該圖必是連通圖。5.（）完滿(mǎn)二叉樹(shù)中必然不存在度為1的結(jié)點(diǎn)。6.（）有向圖中第i個(gè)極點(diǎn)的出度等于其毗鄰矩陣中第i行非0元素的個(gè)數(shù)。7.（）簡(jiǎn)單項(xiàng)選擇擇排序的比較次數(shù)與待排序列的初始排序次序沒(méi)關(guān)。8.（）二叉排序樹(shù)的中序序列必然是一個(gè)有序序列。9.（）快速排序是牢固排序。10.（）當(dāng)初始待

6、排要點(diǎn)字排列為正序時(shí)，簡(jiǎn)單項(xiàng)選擇擇排序的比較次數(shù)達(dá)到最少。11.（）當(dāng)初始待排要點(diǎn)字排列為正序時(shí)，直接插入排序的比較次數(shù)達(dá)到最少。12.（）二叉樹(shù)只能用鏈?zhǔn)浇Y(jié)構(gòu)儲(chǔ)藏，無(wú)法用次序儲(chǔ)藏結(jié)構(gòu)儲(chǔ)藏。13.（）B-樹(shù)中的所有葉子結(jié)點(diǎn)均在同一層上。14.（）一棵9階B-樹(shù)中的所有非終端結(jié)點(diǎn)的分支數(shù)必然大于4。15.（）所謂動(dòng)向查找是指查找表在查找后可能會(huì)發(fā)生變化。16.（）平衡二叉樹(shù)是指二叉樹(shù)根結(jié)點(diǎn)的左子樹(shù)深度和右子樹(shù)深度之差的絕對(duì)值不大于1.17.（）在二叉排序樹(shù)中刪除結(jié)點(diǎn)時(shí)，只能刪除樹(shù)中的葉子結(jié)點(diǎn)。18.（）完滿(mǎn)二叉樹(shù)必然是一棵平衡二叉樹(shù)。19.（）擁有n個(gè)極點(diǎn)和最少n-1條邊無(wú)向圖必然是一個(gè)連通圖。

7、20.（）用毗鄰矩陣法儲(chǔ)藏一個(gè)圖所需的儲(chǔ)藏單元數(shù)目與圖的邊數(shù)有關(guān)。選擇題：U1-U31.一個(gè)算法應(yīng)該是（B）。A.程序B.問(wèn)題求解步驟的描述C.要滿(mǎn)足五個(gè)基本特點(diǎn)D.A和C2.以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)構(gòu)-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-A.樹(shù)B.字符串C.隊(duì)列D.棧3.下面關(guān)于線性表的描述中，錯(cuò)誤的選項(xiàng)是（B）？A.線性表采用次序儲(chǔ)藏，必定占用一片連續(xù)的儲(chǔ)藏單元。B.線性表采用次序儲(chǔ)藏，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接儲(chǔ)藏，不用占用一片連續(xù)的儲(chǔ)藏單元。D.線性表采用鏈接儲(chǔ)藏，便于插入和刪除操作。4.在一個(gè)長(zhǎng)度為n的次序表中，在第i（0i=n+1）個(gè)元素

8、從前插入一個(gè)元素時(shí)，需向后搬動(dòng)（B）個(gè)元素。A.n-iB.n-i+15.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）儲(chǔ)藏方式最節(jié)約時(shí)間。A.次序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表6.設(shè)一個(gè)鏈表最常用的操作是在尾端插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則采用（D）最節(jié)約時(shí)間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表7.鏈表不擁有的特點(diǎn)是（B）A.插入、刪除不需要搬動(dòng)元素B.可隨機(jī)接見(jiàn)任一元素C.不用早先估計(jì)儲(chǔ)藏空間D.所需空間與線性長(zhǎng)度成正比8.線性表（a1，a2，.，an）以鏈接方式儲(chǔ)藏時(shí)，接見(jiàn)第i地址元素的時(shí)間復(fù)雜性為

9、C）A.O（i）B.O（1）C.O（n）D.O(i-1)9.若長(zhǎng)度為n的線性表采用次序儲(chǔ)藏結(jié)構(gòu)，在其第i個(gè)地址插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（C）（1=inext=headB.p-next=NULLC.p=NULLD.p=head13.帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的條件是（C）A.L=NULLB.L-next=NULLC.L-next=LD.L-next=L-next14.在單鏈表指針為p的結(jié)點(diǎn)此后插入指針為s的結(jié)點(diǎn)，正確的操作是（B）A.p-next=s；s-next=p-next；B.s-next=p-next；p-next=s；C.p-next=s；p-next=s-next；-完滿(mǎn)版學(xué)

10、習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-D.p-next=s-next；p-next=s；15.在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是（C）A.p-Llink=q；q-Rlink=p；p-Llink-Rlink=q；q-Llink=q；B.p-Llink=q；p-Llink-Rlink=q；q-Rlink=p；q-Llink=p-Llink；C.q-Rlink=p；q-Llink=p-Llink；p-Llink-Rlink=q；p-Llink=q；D.q-Llink=p-Llink；q-Llink=q；p-Llink=q；p-Llink=q；16.若已知一個(gè)棧的入棧序列是1,2

11、,3，.，n，其輸出序列為p1，p2，p3，.，pN，若pN是n，則pi是（D）C.n-i+1D.不確定17.一個(gè)棧的輸入序列為1,2,3，.，n，若輸出序列的第一個(gè)元素是n，輸出第i1=i0)?x*f(x-1):2);printf(“%d”,y);returny;Inti;I=f(f(1);-完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-A.2B.4C.8D.無(wú)量遞歸U4-U51.下面關(guān)于串的表達(dá)中，哪一個(gè)是不正確的？（B）A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.模式般配是串的一種重要資源D.串既可以采用次序儲(chǔ)藏，也可以采用鏈?zhǔn)絻?chǔ)藏2.設(shè)有兩個(gè)串p和q的子串，求q在p中第一出

12、現(xiàn)的地址的算法稱(chēng)為（C）A.求子串B.聯(lián)接C.般配D.求串長(zhǎng)3.已知串S=aaab，其N(xiāo)ext數(shù)組值為（A）4.串a(chǎn)babaaababaa的next數(shù)組為（C）5.串的長(zhǎng)度是指（B）A.串中所含不相同字母的個(gè)數(shù)B.串中所含字符的個(gè)數(shù)C.傳中所含不相同字符的個(gè)數(shù)D.串中所含非空格字符的個(gè)數(shù)6字符串a(chǎn)babaabab的nextval為（A）A.（0,1,0,1,0,4,1,0,1）B.（0,1,0,1,0,2,1,0,1）C.（0,1,0,1,0,0,0,1,1）D.（0,1,0,1,0,1,0,1,1）7.設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮儲(chǔ)藏方式，以行序?yàn)橹鲀?chǔ)藏，a11為第一元素，其儲(chǔ)藏地址

13、為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（B）D.408.假設(shè)以行序?yàn)橹餍騼?chǔ)藏二維數(shù)組A=array1.100,1.100，設(shè)每個(gè)數(shù)據(jù)元素占兩個(gè)儲(chǔ)藏單元，基地址為10，則LOC5,5=（B）D.1020U6-U101.以下排序方法中，不牢固的排序算法是（C）A.冒泡排序B.歸并排序C.快速排序D.直接插入排序2.擁有n個(gè)極點(diǎn)的無(wú)向圖用毗鄰矩陣表示，若該圖為連通圖，則其毗鄰矩陣中最少有（A）個(gè)非零元素。A.2(n-1)B.n-1C.n*nD.n(n-1)3.要連通擁有n個(gè)極點(diǎn)的有向圖，最少需要（B）條邊A.n-1B.nC.n+1D.2n4.快速排序在最壞情況下的時(shí)間復(fù)雜度為（C）A.O(1

14、)B.O(n)22C.O(nlogn)D.O(n)5.在長(zhǎng)度為12的有序表中，按折半查找法對(duì)表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（C）A.43/12B.39/12C.37/12D.35/126.下面那一方法可以判斷出一個(gè)有向圖可否有環(huán)（回路）（B）A.深度優(yōu)先遍歷B.拓?fù)渑判?完滿(mǎn)版學(xué)習(xí)資料分享-WORD格式-可編寫(xiě)-專(zhuān)業(yè)資料-C.求最短路徑D.求要點(diǎn)路徑7.若對(duì)給定的要點(diǎn)字序列利用折半查找方法進(jìn)行查找，則要點(diǎn)字序列需滿(mǎn)足的條件是（A）A.次序儲(chǔ)藏且有序B.次序儲(chǔ)藏且升序C.鏈?zhǔn)絻?chǔ)藏且有序D.有序8.以下排序方法中，某一趟結(jié)束后選出一個(gè)元素不用然能放在其最后地址上的是D）A.堆排序B.冒泡排序C.快速排序D.直接插入排序9.以下四個(gè)序列中，滿(mǎn)足堆的條件的是（C）A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,1510.以下排序方法中，時(shí)間效率最高的排序算法