數(shù)據(jù)結(jié)構(gòu)習題123章

1、第一章 緒論一選擇題1數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K，R），其中K是的有限集合，R是K上的的有限集合。 A算法 B數(shù)據(jù)元素 C數(shù)據(jù)操作 D邏輯結(jié)構(gòu) A操作 B映象 C存儲 D關(guān)系2算法分析的目的是，算法分析的兩個主要方面是。 A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 C分析算法的效率以求改進 D分析算法的易懂性和文檔性 A空間復(fù)雜性和時間復(fù)雜性 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3算法復(fù)雜度通常是表達算法在最壞情況下所需要的計算量，O(1)的含義是（ ）A算法執(zhí)行一步就完成 B算法執(zhí)行1秒鐘就完成C算法執(zhí)行常數(shù)步就完成 D算法執(zhí)行可變步數(shù)就完成4數(shù)據(jù)結(jié)構(gòu)研究

2、的內(nèi)容是（ ）。 A數(shù)據(jù)的邏輯結(jié)構(gòu) B數(shù)據(jù)的存儲結(jié)構(gòu) C建立在相應(yīng)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)上的算法 D包括以上三個方面5一個正確的算法應(yīng)該具有 5 個特性，除輸入、輸出特性外，另外 3 個特性是（ ）。 A確定性、可行性、有窮性 B易讀性、確定性、有效性 C有窮性、穩(wěn)定性、確定性 D可行性、易讀性、有窮性 6以下關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中正確的是（ ）。 A數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述 B數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計算機中的存儲方式 C數(shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈式結(jié)構(gòu) D數(shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu) 7下列時間復(fù)雜度中最壞的是（ ）AO(1) BO(n) CO(log2n） DO(n

3、2)8算法的時間復(fù)雜度取決于（ ）A待處理數(shù)據(jù)的初態(tài) B問題的規(guī)模C程序本身所占的空間 D問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)二填空題1數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括3個方面的內(nèi)容，分別是 、 和 。2數(shù)據(jù)的邏輯結(jié)果被分為 、 、 和 。3在下列程序段中，s=s+p語句的執(zhí)行次數(shù)為 ， p*=j語句的執(zhí)行次數(shù)為 ，該程序段的時間復(fù)雜度為 。 int i=0,s=0;while(+i<=n)p=1;for(j=1;j<=i;j+)p*=j;s=s+p;三算法分析題（指出下列算法的功能并分析時間復(fù)雜度）1 double demo1(int n)double p

4、=1,sum=0;for(int i=1;i<=n;+i)p*=i;sum+=p;return(sum);2double demo2(int n)double sum=0,p;int i,j;for(i=1;i<=n;+i)p=1;for(j=1;j<=i;+j)p*=i;sum+=p;return(sum);四解答設(shè)有一數(shù)據(jù)的邏輯結(jié)構(gòu)為：B=(D, S)，其中：D=d1, d2, , d9S=<d1,d3>, <d1, d8>, <d2, d3>, <d2, d4>, <d2, d5>, <d3, d9>

5、;, <d4, d7>, <d4, d6>, <d5, d6>, <d8, d9>, <d9, d7> 畫出這個邏輯結(jié)構(gòu)示意圖。第二章 線性表一選擇題1下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（ ）A存儲密度大 B插入運算方便 C刪除運算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示2下面關(guān)于線性表的敘述中，錯誤的是哪一個？（ ）A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D線性表采用鏈接存儲，便于插入和刪除操作。3若某線性表最常用的操作是存取任

6、一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點的雙循環(huán)鏈表 D單循環(huán)鏈表4某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表5在一個長度為n的順序表中刪除第i個元素(1<=i<=n)時，需向前移動（ ）個元素An-iBn-i+lCn-i-1Di6從一個具有n個結(jié)點的單鏈表中查找其值等于x的結(jié)點時，在查找成功的情況下，需平均比較（ ）個元素結(jié)點An/2 BnC（n+1）/2D（n-1）/27設(shè)單鏈表

7、中指針p指向結(jié)點m，若要刪除m之后的結(jié)點（若存在），則需修改指針的操作為（ ）Ap->next=p->next->next; Bp=p->next;Cp=p->next->next; Dp->next=p;8在一個單鏈表中，已知q結(jié)點是p結(jié)點的前趨結(jié)點，若在q和p之間插入s結(jié)點，則須執(zhí)行（ ）As->next=p->next; p->next=sBq->next=s; s->next=pCp->next=s->next; s->next=pDp->next=s; s->next=q9線性表的順

8、序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A隨機存取B順序存取C索引存取D散列存取二填空1在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過 決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過 決定的。2在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向 結(jié)點，另一個指向 結(jié)點。3當對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用 存儲結(jié)構(gòu)為宜。相反，當經(jīng)常進行的是插入和刪除操作時，則采用 存儲結(jié)構(gòu)為宜。三算法設(shè)計1設(shè)有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試編寫能實現(xiàn)下列功能的算法（要求用最少的時間和最小的空間）確定在序列中比正整數(shù)x大的數(shù)有幾個（相同

9、的數(shù)只計算一次）將單鏈表中比正整數(shù)x小的偶數(shù)從單鏈表中刪除2設(shè)有一個表頭指針為h的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針h指向原鏈表的最后一個結(jié)點。phh3設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A的元素類型為整型，要求B、C表利用A表的結(jié)點）。4. 假設(shè)鏈表A、B分別表示一個集合，試設(shè)計算法以判斷集合A是否是集合B的子集，若是，則返回1，否則返回0，并分析算法的時間復(fù)雜度。5設(shè)有一單循環(huán)鏈表la，其結(jié)點有三個域：p

10、rior、data與next，其中data為數(shù)據(jù)域,，next域指向直接后繼，prior域應(yīng)指向直接前驅(qū)，但目前空著。試寫一算法將此單循環(huán)鏈表改造為雙向循環(huán)鏈表。第三章 棧和隊列一選擇題1已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為（ ）A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6D.1，4，6，5，2，32在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（ ）Atop不變 Btop=0 Ctop- Dtop+3在具有n個單元的順序

11、存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為（ ）Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front4在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊空的條件為（ ） Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front5在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結(jié)點的操作為（ ）Afront=front-&g

12、t;next Brear=rear->nextCrear=front->next Dfront=rear->next6某堆棧的輸入序列為1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素為（ ）Ai Bn-i Cn-i+1 D哪個元素無所謂7用不帶頭結(jié)點的單鏈表存儲隊列時,其隊頭指針指向隊頭結(jié)點,其隊尾指針指向隊尾結(jié)點，則在進行刪除操作時( )。A僅修改隊頭指針 B. 僅修改隊尾指針 C. 隊頭、隊尾指針都要修改 D. 隊頭,隊尾指針都可能要修改二填空題1線性表、棧和隊列都是 結(jié)構(gòu)。線性表可以在 插入和刪除元素；棧只能在 插入和刪除元素；隊列只能在 插入元素和 刪除元

13、素。2假設(shè)以S和X分別表示進棧和退棧運算，則對輸入序列a,b,c,d,e進行一系列棧運算SSXSXSSXXX之后，得到的輸出序列為 。3設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a,b,c,d,e,f依次通過棧S，一個元素出棧后即進入隊列Q。若這6個元素出隊列的順序是b,d,c,f,e,a，則棧S的容量至少應(yīng)該是 。三解答題1一個雙向棧S是在同一向量空間內(nèi)實現(xiàn)的兩個棧，它們的棧底分別設(shè)在向量空間的兩端。 試為此雙向棧設(shè)計初始化InitStack ( S ) 、入棧Push( S , i , x) 和出棧Pop( S , i )等算法， 其中i為0 或1， 用以表示棧號。2利用兩個棧S1、S2模擬一個隊列時，如何使用棧的運輸實