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

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

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

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

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

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

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

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

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

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

10、習資料分享-WORD格式-可編寫-專業(yè)資料-D.p-next=s-next；p-next=s；15.在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（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.若已知一個棧的入棧序列是1,2

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

12、現(xiàn)的地址的算法稱為（C）A.求子串B.聯(lián)接C.般配D.求串長3.已知串S=aaab，其Next數(shù)組值為（A）4.串a(chǎn)babaaababaa的next數(shù)組為（C）5.串的長度是指（B）A.串中所含不相同字母的個數(shù)B.串中所含字符的個數(shù)C.傳中所含不相同字符的個數(shù)D.串中所含非空格字符的個數(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.設有一個10階的對稱矩陣A，采用壓縮儲藏方式，以行序為主儲藏，a11為第一元素，其儲藏地址

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

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