《大數(shù)據(jù)結(jié)構(gòu)》課程習(xí)題集

《《大數(shù)據(jù)結(jié)構(gòu)》課程習(xí)題集》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)》課程習(xí)題集（25頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、word 《數(shù)據(jù)結(jié)構(gòu)》課程習(xí)題集 第 1 頁 〔共 25 頁〕 一、. 選擇題 . 1. 算法的計(jì)算量的大小稱為計(jì)算的〔 〕。 A．效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度 .2. 算法的時(shí)間復(fù)雜度取決于〔 〕. A．問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B D. 難確定 .3. 下面關(guān)于算法說法錯(cuò)誤的答案是〔 〕 A．算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的 .4．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為〔

2、〕兩大類。 A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu) .5．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)〔 〕？ A．廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串 .6．下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？〔 〕 A．存儲(chǔ)密度大 B．插入運(yùn)算方便 C．刪除運(yùn)算方便 D．可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示 .7．下面關(guān)于線性表的表示中，錯(cuò)誤的答案是哪一個(gè)？〔 〕 A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 B．線性表采用順序存儲(chǔ)，便于進(jìn)展插入和刪除操作。 C

3、．線性表采用存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。 D．線性表采用存儲(chǔ)，便于插入和刪除操作。 .8．假如某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)展插入和刪除運(yùn)算，如此利用〔 〕存儲(chǔ)方式最節(jié)省時(shí)間。 A．順序表 B．雙鏈表 C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表 .9．設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，如此選用( )最節(jié)省時(shí)間。 .10. 鏈表不具有的特點(diǎn)是〔 〕. A．插入、刪除不需要移動(dòng)元素 B．可隨機(jī)訪問任一元素 C．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與線性長(zhǎng)度成正比 .11

4、. 設(shè)一個(gè)棧的輸入序列是 1，2，3，4，5,如此如下序列中，是棧的合法輸出序列的是〔 〕。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 .12. 某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它的輸出序列的是〔 〕。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b .13. 用方式存儲(chǔ)的隊(duì)列，在進(jìn)展刪除運(yùn)算時(shí)〔 〕。 A. 僅修改頭指針 B. 僅修改尾指針

5、 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 .14. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，如此在進(jìn)展刪除操作時(shí)( )。 A．僅修改隊(duì)頭指針 B. 僅修改隊(duì)尾指針 C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改 .15．下面關(guān)于串的的表示中，哪一個(gè)是不正確的？〔 〕 A．串是字符的有限序列 B．空串是由空格構(gòu)成的串 C．模式匹配是串的一種重要運(yùn)算 D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ) .16． 串是一種特殊的線性表，其特殊性表現(xiàn)在 (

6、 ) A．可以順序存儲(chǔ) B．?dāng)?shù)據(jù)元素是一個(gè)字符 C．可以存儲(chǔ) D．?dāng)?shù)據(jù)元素可以是多個(gè)字符 .17．關(guān)于空串與空格串，下面說法正確的答案是( )。 A．空串與空格串是一樣的 B．空串與空格串長(zhǎng)度是一樣的 C．空格串中存放的都是空格 D．空串中存放的都是NULL . 18．圖中有關(guān)路徑的定義是〔 〕。 A．由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 B．由不同頂點(diǎn)所形成的序列 C．由不同邊所形成的序列 D．上述定義都不是 .19．設(shè)無向圖的頂點(diǎn)個(gè)數(shù)

7、為n，如此該圖最多有〔 〕條邊。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 .20．一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為〔 〕。 A．n-1 B．n C．n+1 D．nlogn； .21．某內(nèi)排序方法的穩(wěn)定性是指( )。 A．該排序算法不允許有一樣的關(guān)鍵字記錄 B．該排序算法允許有一樣的關(guān)鍵字記錄 C．平均時(shí)間為0〔n log n〕的排序方法 D．以上都不對(duì) .22．如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素

8、之前的局部排序的序列，用〔 〕方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．簡(jiǎn)單項(xiàng)選擇擇排序 .23．排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是( )排序法。 A．插入 B. 選擇 C. 冒泡 D. 都不是 .24．下面給出的四種排序方法中，排序過程中的比擬次數(shù)與排序方法無關(guān)的是。( ) A．選擇排序法 B. 插入排序法 C. 快速排序法 D. 都不是 .25．對(duì)序列{15，9，7，8，20，-1，4}進(jìn)展排序，進(jìn)展一趟后數(shù)據(jù)的排列變?yōu)閧4，9，-1，8，20，7，15}；如此采用的是〔 〕

9、排序。 A. 選擇 B. 快速 C. 希爾 D. 冒泡 .26. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 如此T中的葉子數(shù)為〔 〕 A．5 B．6 C．7 D．8 .27．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是〔 〕 A． 250 B． 500 C．254 D．505 E．以上答案都不對(duì) .28. 有關(guān)二叉樹如下說法正確的答案是〔 〕. A．二叉樹的度為2

10、 B．一棵二叉樹的度可以小于2 C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2 D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為2 .29．二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為〔 〕. A．2I B． 2I-1-1 C． 2I-1 D．2I -1 .30．對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹, 其高度為〔 〕. A．nlog2n B．log2n C．?log2n?|+1 D．不確定 .31．對(duì)二

11、叉樹的結(jié)點(diǎn)從1開始進(jìn)展連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用( )次序的遍歷實(shí)現(xiàn)編號(hào)。 A．先序 B. 中序 C. 后序 D. 從根開始按層次遍歷 .32. 對(duì)N個(gè)元素的表做順序查找時(shí)，假如查找每個(gè)元素的概率一樣，如此平均查找長(zhǎng)度為( ) A．〔N+1〕/2 B. N/2 C. N D. [〔1+N〕*N ]/2 .33. 對(duì)線性表進(jìn)展二分查找時(shí)，要求線性表必須〔 〕 A.以順序方式存儲(chǔ) B.以順序方式存儲(chǔ),

12、且數(shù)據(jù)元素有序 C.以方式存儲(chǔ) D.以方式存儲(chǔ),且數(shù)據(jù)元素有序 .34．當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度( ). A．必定快 B.不一定 C. 在大局部情況下要快 D. 取決于表遞增還是遞減 .35. 具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度〔 〕 . A. 3.1 B. 4 C. 2.5 D. 5 .36. 既希望較快的查找又便于線性表動(dòng)態(tài)變化的查找方法是 ( ) A．順序查找 B. 折半查找 C. 索引順序查找 D. 哈希法查找 二

13、、填空題 .1. 對(duì)于長(zhǎng)度為255的表，采用分塊查找，每塊的最優(yōu)長(zhǎng)度為__________。 .2. 順序查找n個(gè)元素的順序表，假如查找成功，如此比擬關(guān)鍵字的次數(shù)最多為__ __次；當(dāng)使用監(jiān)視哨時(shí)，假如查找失敗，如此比擬關(guān)鍵字的次數(shù)為__ __。 .3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比擬的元素下標(biāo)依次為__________。 .4.. 在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為個(gè)。 .5.、n(n>0)個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，葉結(jié)點(diǎn)最多有個(gè)，最少有個(gè)。假如二叉樹有m個(gè)葉結(jié)點(diǎn)，如此度為2的結(jié)點(diǎn)有個(gè)。 .6．二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深

14、度稱為該結(jié)點(diǎn)的____。 .7. 假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，如此它的最小深度為，最大深度為； .8. 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n 2，如此有n0=。 .9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有____種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是____。 .10．假如不考慮基數(shù)排序，如此在排序過程中，主要進(jìn)展的兩種根本操作是關(guān)鍵字的______和記錄的_____。 .11．直接插入排序用監(jiān)視哨的作用是_______。 .12. 不受待排序初始序列的影響，時(shí)間復(fù)雜度為O(N2)的排序算法是_____，在排序算法的最后一趟

15、開始之前，所有元素都可能不在其最終位置上的排序算法是_____。 ______。 .14．具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為______。 .15．假如用n表示圖中頂點(diǎn)數(shù)目，如此有_______條邊的無向圖成為完全圖。 .16．空格串是指__ _，其長(zhǎng)度等于__ __。 .17．設(shè)T和P是兩個(gè)給定的串，在T中尋找等于P的子串的過程稱為_ __，又稱P為__ __。 .18．串的兩種最根本的存儲(chǔ)方式是__ __、__ __；兩個(gè)串相等的充分必要條件是_ __。 .19. 鏈隊(duì)列的頭尾指針分別是f和r，如此將值x入隊(duì)的操作序列是_______。 .20.向棧中壓入元素的操作

16、是____。 .21.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有___個(gè)元素。 .22．用S表示入棧操作，X表示出棧操作，假如元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_______。 .23. 單鏈表是____的存儲(chǔ)表示。 .24. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向____，另一個(gè)指向____。 .25．存儲(chǔ)的特點(diǎn)是利用________來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 .26.順序存儲(chǔ)結(jié)構(gòu)是通過________表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過________表示元素之間的關(guān)系的。 .27．線性表L=〔a1,a2,…,an〕用數(shù)組

17、表示，假定刪除表中任一元素的概率一樣，如此刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是________。 .28．根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成________和_______；而又根據(jù)指針的連接方式，鏈表又可分成________和________。 .29．?dāng)?shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。 .30．抽象數(shù)據(jù)類型的定義僅取決于它的一組__ _，而與_ _無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_ _不變，都不影響其外部使用。 .31．?dāng)?shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是 .32. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_和_ ，以與它們之間的相互關(guān)系，

18、并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的，設(shè)計(jì)出相應(yīng)的 _。 .三．程序填空題 ．1． 單鏈表H為一個(gè)用帶頭結(jié)點(diǎn)的鏈表表示的線性表，如下算法是將其倒置。 請(qǐng)?jiān)谙聞澗€處填上正確的語句。 P46 template void Line_ListLink：：Reverse ( ) { Line_ListNode *p，*head=new Line_ListNode( )； while(first! =NULL) { p=first；first=first–>link； p–>link=head - >lin

19、k；head–>link=p； } first=head–>link； delete head；} ．2．在順序表中隨機(jī)存取的數(shù)據(jù)，很容易在順序表中實(shí)現(xiàn)按序號(hào)查找元素。代碼如下所示，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 template bool Line_ListSqu：：Find(____________ ，T& x) const //在線性表中查找第i個(gè)元素并用x返回 { if (____________ ) return false； x=elem[i–1]；

20、return ____________ ； } ．3．線性表的插入操作是指在線性表的第m–1個(gè)數(shù)據(jù)元素和第m個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素x，其結(jié)果是使長(zhǎng)度為n的線性表(a1, a2 ,…, am–1, am,…, an)變成長(zhǎng)度為n+1的線性表(a1, a2 ,…, am–1, x, am,…, an)，并且數(shù)據(jù)元素am–1和am之間的邏輯關(guān)系發(fā)生了變化。 實(shí)現(xiàn)步驟如下：(1)合法性判斷：插入位置i是否合法?表是否已滿?(2)將第i至第n位的元素向后移動(dòng)一個(gè)位置；(3)將要插入的元素寫到第i個(gè)數(shù)據(jù)元素的位置；(4)表長(zhǎng)加1。 具體算法如下，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 t

21、emplate Line_ListSqu& Line_ListSqu：：Insert(int i，T& x) { if (____________ ) throw OutOfBounds( )； if (length==MaxSize) throw NoMem( )； for(____________ ；j>=i–1；j––) elem[j+1]=elem[j]； elem[i–1]= ____________ ； length++； return ____________ ； } .

22、4.-冒泡排序〔Bubble Sort〕的根本思想是：設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，循環(huán)進(jìn)展n 趟如下的排序過程，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 void BubbleSort(DataType a[ ], int n) { int i, j, flag=1; DataType temp; for(i = 1; ____________ ; i++) { flag = 0; for(j = 0; ____________ ; j++) { if(____________ ) {

23、 flag = 1; temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } } .5.按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素，具體實(shí)現(xiàn)代碼如下，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 template int Line_ListSqu：：Search(const T& x) const { int____________ ； if (IsEmpty( )) return 0；//線性表為空時(shí)返回

24、0 while(____________ ) i++； if (elem[i]= =x) return ++i； else return ____________ ； } .6.線性表的刪除操作是使長(zhǎng)度為n的線性表(a1, a2,…, am–1, am,…,an)變?yōu)殚L(zhǎng)度為n–1的線性表(a1, a2,…, am–1, am+1,,…,an)，并且數(shù)據(jù)元素am–1、am和am+1之間的邏輯關(guān)系也會(huì)發(fā)生變化，需要把第m+1～n個(gè)元素〔共n–m個(gè)元素〕依次向前移動(dòng)一個(gè)位置來反映這種變化。具體實(shí)現(xiàn)步驟如下：①判斷刪除位置i是否合法，合

25、法如此將該位置元素放入x中，否如此拋出異常；②將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；③表長(zhǎng)減1。 具體算法如下，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 template Line_ListSqu& Line_ListSqu：：Delete(____________ ，T& x) { if (Find(i，x)) { for(____________ ；j

26、throw OutOfBounds( )； } } .7. 假設(shè)以數(shù)組a[m]存放循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量rear 和length分別作為隊(duì)尾指針和隊(duì)中元素個(gè)數(shù)，試給出判別此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)入隊(duì)和出隊(duì)的算法〔在出隊(duì)的算法中要返回隊(duì)頭元素〕。請(qǐng)?jiān)谙聞澗€處填上正確的語句。 #define m 100 int enqueue(int a[], int rear, int length, int x) { if(___________) {printf(“queue is full〞); return 0;}

27、 rear=(rear+1)% m; a[rear]=x; length ___________; return length; } int dequeue(int a[], int rear, int length, int *x) { if(___________) {printf(“queueempty〞); return 0;} *x= a [(rear- length +m)%m]; Length ___________; return length; 刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到

28、第i–1個(gè)結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算法代碼如下所,請(qǐng)?jiān)谙聞澗€處填上正確的語句。 template Line_ListLink& Line_ListLink：：Delete(int i，T& x) { if (__________|| !first) throw OutOfBounds( )；//刪除位置不合法 Line_ListNode *p=first； if (___________) first=first–>link； else { Line_ListNode *q=first； int j=1；

29、 //查找第i個(gè)結(jié)點(diǎn) while(___________jlink；++j；} if (!q || ___________) throw OutOfBounds( )；//沒有第i個(gè)結(jié)點(diǎn) p=q–>link；q–>link=p–>link； } .9. 刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i–1個(gè)結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算法代碼 如下所示：請(qǐng)?jiān)谙聞澗€處填上正確的語句。 template

30、s T> Line_ListLink& Line_ListLink：：Delete(int i，T& x) { if (___________) throw OutOfBounds( )；//刪除位置不合法 Line_ListNode *p=first； if (___________) first=first–>link； else { Line_ListNode *q=first； int j=1； //查找第i個(gè)結(jié)點(diǎn) while(q && j

31、=q–>link；++j；} if (!q || ___________) throw OutOfBounds( )；//沒有第i個(gè)結(jié)點(diǎn) p=q–>link；q–>link=p–>link； } x=p–>data；delete p； return *this；} 串S，1 ≤ pos ≤ Length_Str(S)且0 ≤ len ≤Length_Str(S)–pos+1，用串Sub返回S的自第i個(gè)字符起長(zhǎng)度為j的子串。請(qǐng)?jiān)谙聞澗€處填上正確的語句。 string Sub_Str

32、ing(string &Sub, string S, int i, int j); { int p; Sub.length = 0; if (i <= 0 || i > S.length || j<= 0 ||___________) return Sub; //參數(shù)錯(cuò)誤時(shí)，返回空串 for(p = i – 1; ___________; p++) //把S.ch[i–1]至S.ch[i–1+j]復(fù)制到串Sub中 Sub.ch[p – i +1] = S.ch[p]; Sub.ch[j] ='\0'; ___________ = j; retu

33、rn Sub; } } ．四．閱讀理解題(描述算法思路,再綜合出其功能) 此題說明: 算法思路指的是對(duì)某種數(shù)據(jù)結(jié)構(gòu)(如,記錄序列), 進(jìn)展操作(如,移動(dòng)位置), 的處理步驟(如,1,2,3….). 算法功能指的是要達(dá)到的處理目標(biāo)(如,合并成有序的單鏈表.) .1. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. main(){ int i,max,a[10]; printf(“請(qǐng)輸入10個(gè)整數(shù):〞); for(i=0;i<=10;i++) scanf(“%d〞,&a[i]); max=a[0]; i=1; while(i<10) {

34、if(a[i]>max) max=a[i]; i++;} printf(“值為:〞,max);} .2. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. void delete(node *head,int x) { node *p,*q; q=head; p=head->next; while((p!=NULL) && (p->data!=x)) { q=p; p=p->next;

35、 } if(p==NULL) printf("未找到x！\n"); else if(q==head) printf("x為第一個(gè)結(jié)點(diǎn)，無前趨！\n"); else { q->data=x; q->next=p->next; free(p); } } .3. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. int InsertPosList(struct List *L, int

36、 pos, ElemType x) { int i; if(pos<1 || pos>L->size+1) /*假如pos越界如此插入失敗*/ return 0; if(L->size==L->MaxSize) /*重新分配更大的存儲(chǔ)空間*/ againMalloc(L); for(i=L->size-1; i>=pos-1; i--) L->list[i+1]=L->list[i]; L->list[pos-1]=x; L-

37、>size++; return 1; } .4.閱讀如下算法代碼：描述算法思路,再綜合出其功能. 　　　　void InsertIncreaseList( Seqlist *L , Datatype x ) 　　　　　{?　　　　　　int i; 　　　　　　if ( L->length>=ListSize) 　　　　　　　Error(“overflow"); 　　　　　　for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--) 　　　　　　　L->data[ i ]=L->data[ i ] ; //

38、 比擬并移動(dòng)元素 　　　　　　L->data[ i ] =x; 　　　　　　L -> length++;　　　　　} .5.閱讀如下算法代碼：描述算法思路,再綜合出其功能. 　　void DeleteList ( LinkList L, DataType min , DataType max ) 　　　{　　　　ListNode *p , *q , *s; 　　　　p=L; 　　　　while( p->next && p->next->data <=min )? 　　　　//找比min大的前一個(gè)元素位置 　　　　　p=p->next; 　　　　q=p->next;/

39、/p指向第一個(gè)不大于min結(jié)點(diǎn)的直接前趨，q指向第一個(gè)大于min的結(jié)點(diǎn) 　　　　while(q &&q->datanext; 　　　　　　free(s);//刪除結(jié)點(diǎn)，釋放空間　　　　　} 　　　　p->next=q;//將*p結(jié)點(diǎn)的直接后繼指針指向*q結(jié)點(diǎn)　　　} .6.閱讀如下算法代碼：描述算法思路,再綜合出其功能. void enqueue(int x) { int temp; if(count==n) printf("隊(duì)列上溢出\n"); Else

40、{ count++; temp = (front+count)%n; Queue[temp]=x; }} int dequeue() { int temp;if(count==0) printf("隊(duì)列下溢出\n"); else { temp=Queue[front]; front=(front+1)%n; count--; return temp; }} .7.．閱讀如下算法代碼：描述算法思路,再綜合出其功能. Status ListInsert_L(LinkList &L, int i, ElemTy

41、pe e) { //在帶頭結(jié)點(diǎn)的單鏈表L. p = L; k = 0; //初始化，p指向頭結(jié)點(diǎn)，k為計(jì)數(shù)器 while (p && k < i-1) {//逐步移動(dòng)指針p，直到p指向第i-1個(gè)元素或p為空 p = p->next; ++ k; } // 找到第i-1個(gè)元素所在結(jié)點(diǎn) if (!p || k > i-1) return ERROR; //無法插入 if(!(s = (LinkLinst) malloc(sizeof(LNode)))) //申

42、請(qǐng)?jiān)豦的結(jié)點(diǎn)空間 return OVERFLOW; //內(nèi)存無空閑單元，無法申請(qǐng)到空間 s->data = e// 申請(qǐng)一個(gè)結(jié)點(diǎn)s； s->next = p->next; // 修改s的指針域指向p的下一結(jié)點(diǎn) p->next = s;// 修改p的指針域指向s return OK;} //LinstInsert_L .8.下閱讀如下算法代碼：描述算法思路,再綜合出其功能. Quicskort(Recordnode r[]，int low，int high) /*low和high為記錄序列的

43、下界和上界*/ {int i，j； struct Recordnode x； i=low； j=high； x=r[low]； while(i=x.key) j--; if(i

44、使用遞歸*/ if(low

45、 if(K==A[mid].key) //查找成功返回元素的下標(biāo) return mid; else if(K

46、 else return -1; //查找區(qū)間為空，查找失敗返回-1 .10. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. void charge(int a[], int n) { int i, j, temp; i=0; j=n-1; while(i=0 && i

47、mp; i++; j--;} } } .11. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. string Concat_Str(string &S, string T) { int i; if (S.length + T.length < MaxLength) //連接后串的長(zhǎng)度小于串的最大長(zhǎng)度 { for(i = 0; i < T.length; i++) S.ch[S.length+i] = T.ch[i]; S.ch[S.length+T.length] ='\0'; S.length += T.length; } else //

48、連接后串的長(zhǎng)度大于串的最大長(zhǎng)度， { for(i = 0; i < MaxLength–1–S.length; i++) S.ch[S.length+i] = T.ch[i]; S.ch[MaxLength – 1] ='\0'; S.length = MaxLength; } return S; } .12.. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) { / 兩個(gè)非遞減單鏈表La、Lb ，且 L

49、c非遞減 pa = pa = La->next; pb = Lb->next; Lc = pc = La; while (pa && pb) { if (pa->data if (pa->data <= Pb->data) Pb->data) { pc->next = pa; pc = pa; pa = pa->next;} Else{ pc->next = pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa? pa : pb; free(Lb); }

50、．五．編程題。 .1. 設(shè)一循環(huán)隊(duì)列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)內(nèi)含元素個(gè)數(shù)的計(jì)數(shù)器，用一個(gè)循環(huán)數(shù)組Queue[0,n-1]表示該循環(huán)隊(duì)列,頭指針為front,計(jì)數(shù)器count用來記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。請(qǐng)寫出其入隊(duì)、出隊(duì)操作功能的算法代碼。 .2. 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個(gè)結(jié)點(diǎn)之前的位置上。先在單鏈表中找到第i–1個(gè)結(jié)點(diǎn)，再在其后插入新結(jié)點(diǎn)。請(qǐng)寫出具體算法代碼。 .3.假設(shè)有n(>=1)個(gè)整數(shù)a1, a2, …, an. 要求對(duì)此數(shù)列由小到大進(jìn)展排序。請(qǐng)寫出具體算法代碼。 .4.折半查找的函數(shù)算法，其功能是在線性表r中二分查找關(guān)鍵字

51、為k的結(jié)點(diǎn)，查找到，如此返回其位置i；假如找不到返回0。請(qǐng)寫出具體算法代碼。 ..5．將一個(gè)字符串中的所有字符按相反的次序重新放置。請(qǐng)寫出具體算法代碼。 .6. 一個(gè)線性表中的元素按元素值非遞減有序排列，試設(shè)計(jì)算法刪除表中值一樣的多余元素。請(qǐng)寫出具體算法代碼。 .7.快速排序〔Quick Sort〕請(qǐng)寫出其操作功能的算法代碼。 其排序的根本思想是：取記錄序列中一個(gè)適宜的關(guān)鍵字(通常選取序列中的第一個(gè))，以此關(guān)鍵字取對(duì)應(yīng)的記錄ri作為基準(zhǔn)，把一個(gè)序列分割成兩個(gè)獨(dú)立的子序列，使得基準(zhǔn)位置前的所有記錄的關(guān)鍵字都小于ri key，而基準(zhǔn)位置后的所有記錄的關(guān)鍵字都大于ri.key。這里把這樣

52、的一次過程稱作一次快速排序，在第一次快速排序中，確定了所選取的基準(zhǔn)記錄ri在序列中的最終排列位置，同時(shí)也把剩余的記錄分成了兩個(gè)序列，然后對(duì)每個(gè)序列再進(jìn)展分割，重復(fù)上述過程，直到所有記錄全部排好序?yàn)橹埂? .8. 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)求二叉樹高度的算法代碼。 .9.單鏈表查找第i個(gè)結(jié)點(diǎn)，也是從頭指針開始，依次后移到第i個(gè)結(jié)點(diǎn)，請(qǐng)寫出具體算法代碼。 .10.線性表的插入操作是指在線性表的第m–1個(gè)數(shù)據(jù)元素和第m個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素x，其結(jié)果是使長(zhǎng)度為n的線性表(a1, a2 ,…, am–1, am,…, an)變成長(zhǎng)度為n+1的線性表(a1, a2 ,…, am–1, x, am,…, an)，并且數(shù)據(jù)元素am–1和am之間的邏輯關(guān)系發(fā)生了變化。請(qǐng)寫出具體算法代碼。 25 / 25