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

1、一、選擇題（1）數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互聯(lián)系。A.存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)B.存儲和抽象C.聯(lián)系和抽象D.聯(lián)系與邏輯（2）在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：（C）。A.動態(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)（3）數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈?zhǔn)酱鎯Y(jié)（4）算法分析的兩個主要方面是（A）

2、。A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（5）下列時間復(fù)雜度中最壞的是（D）。A.O（1）B.O（n）C.O（log2n）D.O（n2）（6）等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點運算，需平均移動結(jié)點的數(shù)目為（C）。AnB(n1)2Cn2D(n1)2（7）設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出站順序為(D)A1234B1243C1324D14

3、23（8）如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時（B）A必須判別棧是否滿B必須判別棧是否空C必須判別棧元素類型D隊棧可不做任何判別（9）鏈棧與順序棧相比，有一個比較明顯的優(yōu)點是（B）。A插入操作更加方便B通常不會出現(xiàn)棧滿的情況。C不會出現(xiàn)棧空的情況D刪除操作根加方便（10）插入和刪除只能在一端進(jìn)行的線性表，稱為(C)。A隊列B循環(huán)隊列C棧D循環(huán)棧（11）若進(jìn)隊的序列為：A，B，C，D，則出隊的序列是（C）。AB，C，D，ABA，C，B

4、，DCA，B，C，DDC，B，D，A（12）若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為(B)。A5和1B4和2C2和4D1和5（13）S=“mning“，執(zhí)行求子串函數(shù)SubStr(S22)后的結(jié)果為(B)。A“mo“B““C“in“D“ng“（14）S1=“good“，S2=“mning“，執(zhí)行串連接函數(shù)ConcatStr(

5、S1S2)后的結(jié)果為(A)。A“goodmning“B“goodmning“C“GOODMNING“D“GOODMNING“A鄰接矩陣表示法B鄰接表表示法C逆鄰接表表示法D鄰接表和逆鄰接表表示法（29）對有14個元素的有序表A[1..14]作二分查找，查找元素A[4]時的被比較元素依次為（C）。AA[1]，A[2]，A[3]，A[4]BA[1]，A[14]，A[7]，A[4]CA[7]，A[3]，A[5]，A[4]DA[7]，A[5]，

6、A[3]，A[4]（30）不可能生成下圖二叉排序樹的關(guān)鍵字的序列是（A）。A45312B42531C45213D42315（31）排序方法中，從無序序列中選擇關(guān)鍵字最小的記錄，將其與無序區(qū)（初始為空）的第一個記錄交換的排序方法，稱為(D)。A希爾排序B歸并排序C插入排序D.選擇排序（32）每次把待排序方的區(qū)間劃分為左、右兩個區(qū)間，其中左區(qū)間中元素的值不大于基準(zhǔn)元素的值，右區(qū)間中元素的值不小于基準(zhǔn)元素的值，此種排序方法叫做（C）。A冒泡排

7、序B堆排序C快速排序D.歸并排序（33）直接插入排序的方法是從第（B）個元素開始，插入到前邊適當(dāng)位置的排序方法。A1B2C3Dn（34）堆的形狀是一棵（C）。A二叉排序樹B滿二叉樹C完全二叉樹D平衡二叉樹（35）一組記錄的排序碼為(25，48，16，35，79，82，23，40)，其中含有4個長度為2的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為：（A）。A，16253548234079823672B1625354879822

8、3364072C16254835798223364072D16253548792336407282（36）一個數(shù)據(jù)序列的關(guān)鍵字為：（46，79，56，38，40，84），采用快速排序，并以第一個數(shù)為基準(zhǔn)得到第一次劃分的結(jié)果為：（C）A（38，40，46，56，79，84）B（40，38，46，79，56，84）C（40，38，46，56，79，84）D（40，38，46，79，56，84）二、填空題（1）若一個算法中的語句頻度之和為T（