1、數據結構與算法復習題一、選擇題。1在數據結構中，從邏輯上可以把數據結構分為 C 。A動態結構和靜態結構 B緊湊結構和非緊湊結構C線性結構和非線性結構 D內部結構和外部結構2數據結構在計算機內存中的表示是指A。A數據的存儲結構B數據結構C數據的邏輯結構 D數據元素之間的關系3在數據結構中，與所使用的計算機無關的是數據的 A 結構。A邏輯B存儲C邏輯和存儲D物理4在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲 C 。A數據的處理方法B數據元素的類型C數據元素之間的關系D數據的存儲方法5在決定選取何種存儲結構時，一般不考慮 A 。A各結點的值如何B結點個數的多少C對數據有哪些運算D所用的編

2、程語言實現這種結構是否方便。6以下說法正確的是D 。A數據項是數據的基本單位B數據元素是數據的最小單位C數據結構是帶結構的數據項的集合D一些表面上很不相同的數據可以有相同的邏輯結構7算法分析的目的是C ，算法分析的兩個主要方面是A 。（1）A找出數據結構的合理性 B研究算法中的輸入和輸出的關系C分析算法的效率以求改進 C分析算法的易讀性和文檔性（2）A空間復雜度和時間復雜度 B正確性和簡明性C可讀性和文檔性 D數據復雜性和程序復雜性8下面程序段的時間復雜度是O（n2）。s 0；for（ I 0； in； i）for（j0；jn；j）s Bij；sum s ；9下面程序段的時間復雜度是O（n*m

3、）。for（ i 0； in； i）for（j0；jm；j）Aij 0；10下面程序段的時間復雜度是O（log3n）。i 0；while（in）i i * 3；11在以下的敘述中，正確的是 B 。A線性表的順序存儲結構優于鏈表存儲結構B二維數組是其數據元素為線性表的線性表C棧的操作方式是先進先出D隊列的操作方式是先進后出12通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味著B 。A數據元素具有同一特點B不僅數據元素所包含的數據項的個數要相同，而且對應的數據項的類型要一致C每個數據元素都一樣D數據元素所包含的數據項的個數要相等13鏈表不具備的特點是A 。A可隨機訪問任一結點B插入刪除不

4、需要移動元素C不必事先估計存儲空間D所需空間與其長度成正比14不帶頭結點的單鏈表head為空的判定條件是 A。next NULLCheadnext headD head！NULL15帶頭結點的單鏈表head為空的判定條件是 B。next NULLCheadnext headD head！NULL16若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用D存儲方式最節省運算時間。A單鏈表 B給出表頭指針的單循環鏈表C雙鏈表 D帶頭結點的雙循環鏈表17需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是 B 。A單鏈表 B靜態鏈表C線性鏈表 D順序存儲結構18非空

5、的循環單鏈表head的尾結點（由p所指向）滿足C 。Apnext NULLBp NULLCpnext head Dp head19在循環雙鏈表的p所指的結點之前插入s所指結點的操作是 D 。AppriorpriorBppriorpriorCspriornext sDspriorprior s20如果最常用的操作是取第i個結點及其前驅，則采用D存儲方式最節省時間。A單鏈表 B雙鏈表C單循環鏈表D 順序表21在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是B 。AO（1） BO（n）CO（n2）DO（nlog2n）22在一個長度為n（n1）的單鏈表上，設有頭和尾兩個指針，

6、執行 B操作與鏈表的長度有關。A刪除單鏈表中的第一個元素B刪除單鏈表中的最后一個元素C在單鏈表第一個元素前插入一個新元素D在單鏈表最后一個元素后插入一個新元素23與單鏈表相比，雙鏈表的優點之一是D。A插入、刪除操作更簡單B可以進行隨機訪問C可以省略表頭指針或表尾指針D順序訪問相鄰結點更靈活24如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用 B 。A只有表頭指針沒有表尾指針的循環單鏈表B只有表尾指針沒有表頭指針的循環單鏈表C非循環雙鏈表D循環雙鏈表25在長度為n的順序表的第i個位置上插入一個元素（1 i n1），元素的移動次數為： A 。An i 1Bn

7、 iCiDi 126對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為 C。A順序表 B 用頭指針表示的循環單鏈表C用尾指針表示的循環單鏈表 D單鏈表27下述哪一條是順序存儲結構的優點? C。A插入運算方便 B可方便地用于各種邏輯結構的存儲表示C存儲密度大 D刪除運算方便28下面關于線性表的敘述中，錯誤的是哪一個? B。A線性表采用順序存儲，必須占用一片連續的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。29線性表是具有n個 B 的有限序列。A字符B數據元素 C數據項D表元素30在

8、n個結點的線性表的數組實現中，算法的時間復雜度是O（1）的操作是 A 。A訪問第i（1in）個結點和求第i個結點的直接前驅（1in）B在第i（1in）個結點后插入一個新結點C刪除第i（1in）個結點D以上都不對31若長度為n的線性表采用順序存儲結構，在其第i個位置插入一個新元素的算法的時間復雜度為C。AO（0） BO（1）CO（n）DO（n2）32對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為 C。AO（n） O（n） BO（n） O（1）CO（1） O（n）DO（1） O（1）33線性表（a1，a2， ，an）以鏈式方式存儲，訪問第i位置元素的時間復雜度為 C。AO（0） BO

9、（1）CO（n）DO（n2）34單鏈表中，增加一個頭結點的目的是為了C。A使單鏈表至少有一個結點 B標識表結點中首結點的位置C方面運算的實現 D說明單鏈表是線性表的鏈式存儲35在單鏈表指針為p的結點之后插入指針為s的結點，正確的操作是 B 。Apnextpnextpnexts；Cpnextsnextsnext；pnexts36線性表的順序存儲結構是一種A 。A隨機存取的存儲結構B順序存取的存儲結構C索引存取的存儲結構DHash存取的存儲結構37棧的特點是 B ，隊列的特點是A。A先進先出 B先進后出38棧和隊列的共同點是C 。A都是先進后出 B都是先進先出C只允許在端點處插入和刪除元素 D沒有

10、共同點39一個棧的進棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。AedcbaBdecbaCdceabDabcde40設有一個棧，元素依次進棧的順序為A、B、C、D、E。下列 C 是不可能的出棧序列。AA，B，C，D，E BB，C，D，E，ACE，A，B，C，D DE，D，C，B，A41以下 B 不是隊列的基本運算?A從隊尾插入一個新元素B從隊列中刪除第i個元素C判斷一個隊列是否為空D讀取隊頭元素的值42若已知一個棧的進棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1n，則pi為 C。Ai Bni Cni1 D不確定43判定一個順序棧st（最多元素為MaxSiz

11、e）為空的條件是B 。Asttop ！top 1Csttop ！top MaxSize44判定一個順序棧st（最多元素為MaxSize）為滿的條件是D 。Asttop ！top 1Csttop ！top MaxSize45一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是B 。A4，3，2，1 B1，2，3，4C1，4，3，2 D3，2，4，146判定一個循環隊列qu（最多元素為MaxSize）為空的條件是C 。Aqurear qurear qufront 1MaxSizeCqufront 147在循環隊列中，若front與rear 分別表示對頭元素和隊尾元素的位置，則判斷循環隊列空的條件

12、是 C。Afrontrear1 Brearfront1 Cfrontrear Dfront048向一個棧頂指針為h的帶頭結點的鏈棧中插入指針s所指的結點時，應執行D操作。Ahnexth ；Csnexthnexts ；49輸入序列為ABC，可以變為CBA時，經過的棧操作為B。Apush，pop，push，pop，push，popBpush，push，push，pop， pop， popCpush，push，pop， pop，push，popDpush，pop，push，push，pop， pop50若棧采用順序存儲方式存儲，現兩棧共享空間V1m，top1、top2分別代表第1和第2個棧的棧頂，棧

13、1的底在V1，棧2的底在Vm，則棧滿的條件是B。A|top2top1|0 B top11top2 Ctop1top2mDtop1top251設計一個判別表達式中左、右括號是否配對出現的算法，采用D 數據結構最佳。A線性表的順序存儲結構 B隊列 C線性表的鏈式存儲結構D棧52允許對隊列進行的操作有D。A對隊列中的元素排序B取出最近進隊的元素C在隊頭元素之前插入元素D刪除隊頭元素53對于循環隊列D 。A無法判斷隊列是否為空 B無法判斷隊列是否為滿C隊列不可能滿 D以上說法都不對54若用一個大小為6的數值來實現循環隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元

14、素后，rear和front的值分別為 B。A1和5 B2和4 C4和2D5和155隊列的“先進先出”特性是指 D 。A最早插入隊列中的元素總是最后被刪除B當同時進行插入、刪除操作時，總是插入操作優先C每當有刪除操作時，總是要先做一次插入操作D每次從隊列中刪除的總是最早插入的元素56和順序棧相比，鏈棧有一個比較明顯的優勢是A 。A通常不會出現棧滿的情況 B 通常不會出現棧空的情況C插入操作更容易實現 D刪除操作更容易實現57用不帶頭結點的單鏈表存儲隊列，其頭指針指向隊頭結點，尾指針指向隊尾結點，則在進行出隊操作時 C。A僅修改隊頭指針B僅修改隊尾指針C隊頭、隊尾指針都可能要修改D隊頭、隊尾指針都

15、要修改58若串Ssoftware，其子串的數目是 B 。A8 B37 C36D959串的長度是指B 。A串中所含不同字母的個數 B串中所含字符的個數C串中所含不同字符的個數 D串中所含非空格字符的個數60串是一種特殊的線性表，其特殊性體現在B 。A可以順序存儲B數據元素是一個字符C可以鏈式存儲D數據元素可以是多個字符61設有兩個串p和q，求q在p中首次出現的位置的運算稱為B。A連接 B 模式匹配 C求子串D求串長62數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開始連續存放的存儲器內，該數組按行存放，元素A85的起始地址為 C。ASA141B SA144

16、 CSA222DSA22563數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開始連續存放的存儲器內，該數組按行存放，元素A58的起始地址為 C 。ASA141B SA180 CSA222DSA22564若聲明一個浮點數數組如下： froat averagenew float30；假設該數組的內存起始位置為200， average15的內存地址是C。A214 B215 C260D25665設二維數組A1 m，1 n按行存儲在數組B中，則二維數組元素Ai，j在一維數組B中的下標為 A 。An*（i1）jB n*（i1）j1Ci*（j1） Dj*mi166有一

17、個10090的稀疏矩陣，非0元素有10，設每個整型數占2個字節，則用三元組表示該矩陣時，所需的字節數是B。A20 B 66C18 000 D3367數組A0 4，1 3，57中含有的元素個數是A 。A55 B 45C36 D1668對矩陣進行壓縮存儲是為了D。A方便運算B 方便存儲C提高運算速度 D減少存儲空間69設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a1，1為第一個元素，其存儲地址為1，每個元素占1個地址空間，則a8，5的地址為B。A13B 33 C18D4070稀疏矩陣一般的壓縮存儲方式有兩種，即C 。A二維數組和三維數組 B三元組和散列C三元組和十字鏈表 D散列和

18、十字鏈表71樹最適合用來表示 C。A有序數據元素B無序數據元素C元素之間具有分支層次關系的數據D元素之間無聯系的數據72深度為5的二叉樹至多有 C 個結點。A16B 32 C31 C 1073對一個滿二叉樹，m個葉子，n個結點，深度為h，則D 。An hm B hm 2n C m h1Dn 2h174任何一棵二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序 A 。A不發生改變 B發生改變C不能確定 D以上都不對75在線索化樹中，每個結點必須設置一個標志來說明它的左、右鏈指向的是樹結構信息，還是線索化信息，若0標識樹結構信息，1標識線索，對應葉結點的左右鏈域，應標識為_ D_。A00 B0

19、1C10D1176在下述論述中，正確的是 D 。只有一個結點的二叉樹的度為0；二叉樹的度為2；二叉樹的左右子樹可任意交換；深度為K的順序二叉樹的結點個數小于或等于深度相同的滿二叉樹。AB C D77設森林F對應的二叉樹為B，它有m個結點，B的根為p，p的右子樹的結點個數為n，森林F中第一棵樹的結點的個數是A 。Amn Bmn1 Cn1D不能確定78若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點的個數是B 。A9 B11 C15D不能確定79具有10個葉子結點的二叉樹中有 B 個度為2的結點。A8 B9 C10 D1180在一個無向圖中，所有頂點的度數之和等于所有邊數的C

20、倍。A1/2 B 1C 2 D481在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的B倍。A1/2 B 1C 2 D482某二叉樹結點的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結點數目為：CA3B2 C4D583已知一算術表達式的中綴形式為AB *CD/E，后綴形式為ABC *DE/，其前綴形式為 D。 AAB*C/DE BAB*CD/E C *ABC/DE DA*BC/DE84已知一個圖，如圖所示，若從頂點a出發按深度搜索法進行遍歷，則可能得到的一種頂點序列為_D_；按廣度搜索法進行遍歷，則可能得到的一種頂點序列為_A_；Aa，b，e，c，d，fBa，c，f

21、，e，b，dCa，e，b，c，f，d，Da，e，d，f，c，bAa，b，c，e，d，fBa，b，c，e，f，dCa，e，b，c，f，d，Da，c，f，d，e，b85采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的_A_。A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷86采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的_D_。A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷87具有n 個結點的連通圖至少有 A 條邊。An1B n C n（n1）/2 D 2n88廣義表（a），a）的表頭是 C，表尾是C。Aa B（）C （a） D （a）89廣義表（a）的表頭是 C，表尾是B。Aa B（）C （

22、a） D （a）90順序查找法適合于存儲結構為 B的線性表。A散列存儲 B順序存儲或鏈式存儲C壓縮存儲 D索引存儲91對線性表進行折半查找時，要求線性表必須B。A以順序方式存儲 B以順序方式存儲，且結點按關鍵字有序排列C以鏈式方式存儲 D以鏈式方式存儲，且結點按關鍵字有序排列92采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為D 。AO（n2） BO（nlog2n） CO（n）DO（log2n）93有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當折半查找值為82的結點時，C次比較后查找成功。A11 B5 C 4 D894二叉樹為二叉排序樹

23、的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法B 。A 正確 B 錯誤95下面關于B樹和B樹的敘述中，不正確的結論是 A。AB樹和B樹都能有效的支持順序查找 BB樹和B樹都能有效的支持隨機查找CB樹和B樹都是平衡的多叉樹 DB樹和B樹都可用于文件索引結構96以下說法錯誤的是 B。A散列法存儲的思想是由關鍵字值決定數據的存儲地址B散列表的結點中只包含數據元素自身的信息，不包含指針。C負載因子是散列表的一個重要參數，它反映了散列表的飽滿程度。D散列表的查找效率主要取決于散列表構造時選取的散列函數和處理沖突的方法。97查找效率最高的二叉排序樹是C。A所有結點的左子樹都為

24、空的二叉排序樹。B所有結點的右子樹都為空的二叉排序樹。C平衡二叉樹。D沒有左子樹的二叉排序樹。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為C。A希爾排序 B。冒泡排序 C插入排序 D。選擇排序99在所有的排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是D 。A希爾排序B冒泡排序 C直接插入排序 D直接選擇排序100堆是一種有用的數據結構。下列關鍵碼序列D 是一個堆。A94，31，53，23，16，72B94，53，31，72，16，23C16，53，23，94，31，72D16，31，23，94，53，72101堆排

25、序是一種B排序。A插入B選擇C交換D歸并102D 在鏈表中進行操作比在順序表中進行操作效率高。A順序查找B折半查找C分塊查找D插入103直接選擇排序的時間復雜度為 D 。（n 為元素個數）AO（n） BO（log2n） CO（nlog2n）D O（n2）二、填空題。1數據邏輯結構包括線性結構 、樹形結構和圖狀結構三種類型，樹形結構和圖狀結構合稱 非線性結構 。2數據的邏輯結構分為集合 、線性結構 、樹形結構和圖狀結構4種。3在線性結構中，第一個結點 沒有 前驅結點，其余每個結點有且只有 1個前驅結點；最后一個結點 沒有后續結點，其余每個結點有且只有1個后續結點。4線性結構中元素之間存在 一對一

26、 關系，樹形結構中元素之間存在 一對多 關系，圖形結構中元素之間存在多對多關系。5在樹形結構中，樹根結點沒有 前驅 結點，其余每個結點有且只有 1個前驅結點；葉子結點沒有后續結點，其余每個結點的后續結點可以任意多個。6數據結構的基本存儲方法是 順序、鏈式、 索引和 散列存儲 。7衡量一個算法的優劣主要考慮正確性、可讀性、健壯性和 時間復雜度與 空間復雜度 。8評估一個算法的優劣，通常從時間復雜度 和空間復雜度 兩個方面考察。9算法的5個重要特性是有窮性、確定性 、可行性、輸入和輸出。10在一個長度為n的順序表中刪除第i個元素時，需向前移動 ni1個元素。11在單鏈表中，要刪除某一指定的結點，必

27、須找到該結點的前驅結點。12在雙鏈表中，每個結點有兩個指針域，一個指向 前驅 結點，另一個指向 后繼結點 。13在順序表中插入或刪除一個數據元素，需要平均移動 n個數據元素，移動數據元素的個數與 位置 有關。14當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用順序 存儲結構。15根據線性表的鏈式存儲結構中每一個結點包含的指針個數，將線性鏈表分成單鏈表 和 雙鏈表 。16順序存儲結構是通過 下標 表示元素之間的關系的；鏈式存儲結構是通過指針 表示元素之間的關系的。17帶頭結點的循環鏈表L中只有一個元素結點的條件是LnextnextL 。18棧是限

28、定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出的原則。19空串是 零個字符的串，其長度等于 零。空白串是由一個或多個空格字符組成的串，其長度等于其包含的空格個數。20組成串的數據元素只能是 單個字符。21一個字符串中 任意個連續字符構成的部分 稱為該串的子串。22子串 ”str” 在主串 ”datastructure” 中的位置是 5。23二維數組M的每個元素是6個字符組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要 540個字節；M的第8列和第5行共占108個字節。24稀疏矩陣一般的壓縮存儲方法有兩種，即 三元組表和十字鏈表 。25廣義表（a），（b），

29、c），（d）的長度是3，深度是4。26在一棵二叉樹中，度為零的結點的個數為n0，度為2 的結點的個數為n2，則有n0 n21。27在有n個結點的二叉鏈表中，空鏈域的個數為_n1_。28一棵有n個葉子結點的哈夫曼樹共有_2n1_個結點。29深度為5的二叉樹至多有31 個結點。30若某二叉樹有20個葉子結點，有30個結點僅有一個孩子，則該二叉樹的總結點個數為 69 。31某二叉樹的前序遍歷序列是abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。32線索二叉樹的左線索指向其 遍歷序列中的前驅 ，右線索指向其遍歷序列中的后繼。33在各種查找方法中，平均查找長度與結點個數n無關

30、的查找方法是散列查找法 。34在分塊索引查找方法中，首先查找 索引表，然后查找相應的塊表。35一個無序序列可以通過構造一棵二叉排序 樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。36具有10個頂點的無向圖，邊的總數最多為_45_。37已知圖G的鄰接表如圖所示，其從頂點v1出發的深度優先搜索序列為_v1v2v3v6v5v4_，其從頂點v1出發的廣度優先搜索序列為_v1v2v5v4v3v6_。38索引是為了加快檢索速度而引進的一種數據結構。一個索引隸屬于某個數據記錄集，它由若干索引項組成，索引項的結構為關鍵字 和 關鍵字對應記錄的地址 。39Prim 算法生成一個最小生成樹每一步

31、選擇都要滿足 邊的總數不超過n1，當前選擇的邊的權值是候選邊中最小的 ， 選中的邊加入樹中不產生回路三項原則。40在一棵m階B樹中，除根結點外，每個結點最多有 m棵子樹，最少有 m/2 棵子樹。三、判斷題。1在決定選取何種存儲結構時，一般不考慮各結點的值如何。（）2抽象數據類型（ADT）包括定義和實現兩方面，其中定義是獨立于實現的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現。（ ）3抽象數據類型與計算機內部表示和實現無關。（ ）4順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。（ ）5線性表采用鏈式存儲結構時，結點和結點內部的存儲空間可以是不連續的。（ ）6對任何數據結構鏈式存儲結構一定優于順序存儲結構。（ ）7順序存儲方式只能用于存儲線性結構。（ ）8集合與線性表的區別在于是否按關鍵字排序。（ ）9線性表中每個元素都有一個直接前驅和一個直接后繼。（ ）10線性表就