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

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

1、word數(shù)據(jù)結(jié)構(gòu)課程習(xí)題集 第 1 頁 共 25 頁一、. 選擇題 . 1. 算法的計算量的大小稱為計算的 。A效率 B. 復(fù)雜性 C. 現(xiàn)實性 D. 難度.2. 算法的時間復(fù)雜度取決于 .A問題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B D. 難確定.3. 下面關(guān)于算法說法錯誤的答案是 A算法最終必須由計算機(jī)程序?qū)崿F(xiàn) C. 算法的可行性是指指令不能有二義性 D. 以上幾個都是錯誤的.4從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 兩大類。A動態(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)中，哪一個是線性結(jié)構(gòu) ？A廣義表 B. 二叉樹 C. 稀疏矩陣 D

2、. 串.6下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點(diǎn)？ A存儲密度大 B插入運(yùn)算方便 C刪除運(yùn)算方便 D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示.7下面關(guān)于線性表的表示中，錯誤的答案是哪一個？ A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B線性表采用順序存儲，便于進(jìn)展插入和刪除操作。C線性表采用存儲，不必占用一片連續(xù)的存儲單元。D線性表采用存儲，便于插入和刪除操作。.8假如某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)展插入和刪除運(yùn)算，如此利用 存儲方式最節(jié)省時間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表.9設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，如此選用( )最節(jié)省時

3、間。.10. 鏈表不具有的特點(diǎn)是 . A插入、刪除不需要移動元素 B可隨機(jī)訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比.11. 設(shè)一個棧的輸入序列是 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,下面的四個序列中，不可能是它的輸出序列的是 。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b.13. 用方式存儲的隊列，在進(jìn)展刪除運(yùn)算時 。A. 僅修改頭指針 B. 僅

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

5、，下面說法正確的答案是( )。 A空串與空格串是一樣的 B空串與空格串長度是一樣的 C空格串中存放的都是空格D空串中存放的都是NULL. 18圖中有關(guān)路徑的定義是 。 A由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 B由不同頂點(diǎn)所形成的序列C由不同邊所形成的序列 D上述定義都不是.19設(shè)無向圖的頂點(diǎn)個數(shù)為n，如此該圖最多有 條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2.20一個n個頂點(diǎn)的連通無向圖，其邊的個數(shù)至少為 。An-1 Bn Cn+1 Dnlogn；.21某內(nèi)排序方法的穩(wěn)定性是指( )。 A該排序算法不允許有一樣的關(guān)鍵字記錄 B該排序算法允許有一樣的關(guān)鍵字記錄C平

6、均時間為0n log n的排序方法 D以上都不對 .22如果只想得到1000個元素組成的序列中第5個最小元素之前的局部排序的序列，用 方法最快。A起泡排序 B快速排列 CShell排序 D堆排序 E簡單項選擇擇排序 .23排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是( )排序法。A插入 B. 選擇 C. 冒泡 D. 都不是.24下面給出的四種排序方法中，排序過程中的比擬次數(shù)與排序方法無關(guān)的是。( )A選擇排序法 B. 插入排序法 C. 快速排序法 D. 都不是.25對序列15，9，7，8，20，-1，4進(jìn)展排序，進(jìn)展一趟后數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15；如此采用的是 排序。A. 選

7、擇 B. 快速 C. 希爾 D. 冒泡.26. 設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個數(shù)分別為4，2，1，1 如此T中的葉子數(shù)為 A5 B6 C7 D8.27一棵完全二叉樹上有1001個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是 A 250 B 500 C254 D505 E以上答案都不對 .28. 有關(guān)二叉樹如下說法正確的答案是 . A二叉樹的度為2 B一棵二叉樹的度可以小于2 C二叉樹中至少有一個結(jié)點(diǎn)的度為2 D二叉樹中任何一個結(jié)點(diǎn)的度都為2.29二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為 .A2I B 2I-1-1 C 2I-1 D2I -1.30對于有n 個結(jié)點(diǎn)的二叉樹, 其高度為 .Anlog2n B

8、log2n Clog2n|+1 D不確定.31對二叉樹的結(jié)點(diǎn)從1開始進(jìn)展連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( )次序的遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷.32. 對N個元素的表做順序查找時，假如查找每個元素的概率一樣，如此平均查找長度為( ) AN+1/2 B. N/2 C. N D. 1+N*N /2.33. 對線性表進(jìn)展二分查找時，要求線性表必須 A.以順序方式存儲 B.以順序方式存儲,且數(shù)據(jù)元素有序 C.以方式存儲 D.以方式存儲,且數(shù)據(jù)元素有序.34當(dāng)在一個有序的順序存儲

9、表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度( ). A必定快 B.不一定 C. 在大局部情況下要快 D. 取決于表遞增還是遞減.35. 具有12個關(guān)鍵字的有序表，折半查找的平均查找長度 .A. 3.1 B. 4 C. 2.5 D. 5.36. 既希望較快的查找又便于線性表動態(tài)變化的查找方法是 ( ) A順序查找 B. 折半查找 C. 索引順序查找 D. 哈希法查找二、填空題.1. 對于長度為255的表，采用分塊查找，每塊的最優(yōu)長度為_。.2. 順序查找n個元素的順序表，假如查找成功，如此比擬關(guān)鍵字的次數(shù)最多為_ _次；當(dāng)使用監(jiān)視哨時，假如查找失敗，如此比擬關(guān)鍵字

10、的次數(shù)為_ _。.3在有序表A1.12中，采用二分查找算法查等于A12的元素，所比擬的元素下標(biāo)依次為_。.4. 在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為個。.5.、n(n0)個結(jié)點(diǎn)構(gòu)成的二叉樹，葉結(jié)點(diǎn)最多有個，最少有個。假如二叉樹有m個葉結(jié)點(diǎn)，如此度為2的結(jié)點(diǎn)有個。.6二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深度稱為該結(jié)點(diǎn)的_。.7. 假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，如此它的最小深度為，最大深度為；.8. 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個數(shù)為n 0，度為2的結(jié)點(diǎn)的個數(shù)為 n 2，如此有n0=。.9. 現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有_種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是

11、_。.10假如不考慮基數(shù)排序，如此在排序過程中，主要進(jìn)展的兩種根本操作是關(guān)鍵字的_和記錄的_。.11直接插入排序用監(jiān)視哨的作用是_。.12. 不受待排序初始序列的影響，時間復(fù)雜度為O(N2)的排序算法是_，在排序算法的最后一趟開始之前，所有元素都可能不在其最終位置上的排序算法是_。_。.14具有10個頂點(diǎn)的無向圖，邊的總數(shù)最多為_。.15假如用n表示圖中頂點(diǎn)數(shù)目，如此有_條邊的無向圖成為完全圖。.16空格串是指_ _，其長度等于_ _。.17設(shè)T和P是兩個給定的串，在T中尋找等于P的子串的過程稱為_ _，又稱P為_ _。.18串的兩種最根本的存儲方式是_ _、_ _；兩個串相等的充分必要條件是

12、_ _。 .19. 鏈隊列的頭尾指針分別是f和r，如此將值x入隊的操作序列是_。.20.向棧中壓入元素的操作是_。.21.在具有n個單元的循環(huán)隊列中，隊滿時共有_個元素。.22用S表示入棧操作，X表示出棧操作，假如元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_。.23. 單鏈表是_的存儲表示。 .24. 在雙鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向_，另一個指向_。.25存儲的特點(diǎn)是利用_來表示數(shù)據(jù)元素之間的邏輯關(guān)系。.26.順序存儲結(jié)構(gòu)是通過_表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過_表示元素之間的關(guān)系的。.27線性表L=a1,a2,an用數(shù)組表示，假定刪除表中任

13、一元素的概率一樣，如此刪除一個元素平均需要移動元素的個數(shù)是_。.28根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點(diǎn)包含的指針個數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_。.29數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。.30抽象數(shù)據(jù)類型的定義僅取決于它的一組_ _，而與_ _無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_ _不變，都不影響其外部使用。.31數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是.32. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_和_ ，以與它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的，設(shè)計出相應(yīng)的 _。.三程序填空題 1 單鏈表H為一個用帶頭結(jié)點(diǎn)的鏈表表示的線性表，如下算法是將其倒置。請在下劃線處

14、填上正確的語句。 P46templatevoid Line_ListLink：Reverse ( ) Line_ListNode *p，*head=new Line_ListNode( )； while(first! =NULL) p=first；first=firstlink； plink=head - link；headlink=p； first=headlink； delete head；2在順序表中隨機(jī)存取的數(shù)據(jù)，很容易在順序表中實現(xiàn)按序號查找元素。代碼如下所示，請在下劃線處填上正確的語句。 template bool Line_ListSqu：Find(_ ，T& x) const

15、/在線性表中查找第i個元素并用x返回 if (_ ) return false； x=elemi1； return _ ； 3線性表的插入操作是指在線性表的第m1個數(shù)據(jù)元素和第m個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素x，其結(jié)果是使長度為n的線性表(a1, a2 , am1, am, an)變成長度為n+1的線性表(a1, a2 , am1, x, am, an)，并且數(shù)據(jù)元素am1和am之間的邏輯關(guān)系發(fā)生了變化。 實現(xiàn)步驟如下：(1)合法性判斷：插入位置i是否合法?表是否已滿?(2)將第i至第n位的元素向后移動一個位置；(3)將要插入的元素寫到第i個數(shù)據(jù)元素的位置；(4)表長加1。具體算法如下，請

16、在下劃線處填上正確的語句。templateLine_ListSqu& Line_ListSqu：Insert(int i，T& x) if (_ ) throw OutOfBounds( )； if (length=MaxSize) throw NoMem( )； for(_ ；j=i1；j) elemj+1=elemj； elemi1= _ ； length+； return _ ； .4.-冒泡排序Bubble Sort的根本思想是：設(shè)數(shù)組a中存放了n個數(shù)據(jù)元素，循環(huán)進(jìn)展n 趟如下的排序過程，請在下劃線處填上正確的語句。void BubbleSort(DataType a , int n)

17、 int i, j, flag=1;DataType temp;for(i = 1; _ ; i+) flag = 0;for(j = 0; _ ; j+) if(_ ) flag = 1;temp = aj;aj = aj+1;aj+1 = temp; .5.按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素，具體實現(xiàn)代碼如下，請在下劃線處填上正確的語句。 template int Line_ListSqu：Search(const T& x) const int_ ； if (IsEmpty( ) return 0；/線性表為空時返回0 while(_ ) i+； if (elemi= =

18、x) return +i； else return _ ； .6.線性表的刪除操作是使長度為n的線性表(a1, a2, am1, am,an)變?yōu)殚L度為n1的線性表(a1, a2, am1, am+1,an)，并且數(shù)據(jù)元素am1、am和am+1之間的邏輯關(guān)系也會發(fā)生變化，需要把第m+1n個元素共nm個元素依次向前移動一個位置來反映這種變化。具體實現(xiàn)步驟如下：判斷刪除位置i是否合法，合法如此將該位置元素放入x中，否如此拋出異常；將第i+1至第n位的元素向前移動一個位置；表長減1。具體算法如下，請在下劃線處填上正確的語句。template Line_ListSqu& Line_ListSqu：De

19、lete(_ ，T& x) if (Find(i，x) for(_ ；jlength；j+) elem_ =elemj； length ； return _ else throw OutOfBounds( )； .7. 假設(shè)以數(shù)組am存放循環(huán)隊列的元素，同時設(shè)變量rear 和length分別作為隊尾指針和隊中元素個數(shù)，試給出判別此循環(huán)隊列的隊滿條件，并寫出相應(yīng)入隊和出隊的算法在出隊的算法中要返回隊頭元素。請在下劃線處填上正確的語句。#define m 100 int enqueue(int a, int rear, int length, int x) if(_) printf(“queue

20、is full); return 0; rear=(rear+1)% m; arear=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個結(jié)點(diǎn)刪去。先在單鏈表中找到第i1個結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算法代碼如下所,請在下劃線處填上正確的語句。templateLine_ListLink& Li

21、ne_ListLink：Delete(int i，T& x) if (_| !first) throw OutOfBounds( )；/刪除位置不合法 Line_ListNode *p=first； if (_) first=firstlink； else Line_ListNode *q=first； int j=1； /查找第i個結(jié)點(diǎn) while(_jlink；+j； if (!q | _) throw OutOfBounds( )；/沒有第i個結(jié)點(diǎn) p=qlink；qlink=plink； .9. 刪除運(yùn)算是將單鏈表的第i個結(jié)點(diǎn)刪去。先在單鏈表中找到第i1個結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算

22、法代碼 如下所示：請在下劃線處填上正確的語句。templateLine_ListLink& Line_ListLink：Delete(int i，T& x) if (_) throw OutOfBounds( )；/刪除位置不合法 Line_ListNode *p=first； if (_) first=firstlink； else Line_ListNode *q=first； int j=1； /查找第i個結(jié)點(diǎn) while(q & jlink；+j； if (!q | _) throw OutOfBounds( )；/沒有第i個結(jié)點(diǎn) p=qlink；qlink=plink； x=pdat

23、a；delete p； return *this；串S，1 pos Length_Str(S)且0 len Length_Str(S)pos+1，用串Sub返回S的自第i個字符起長度為j的子串。請在下劃線處填上正確的語句。string Sub_String(string &Sub, string S, int i, int j);int p;Sub.length = 0;if (i S.length | j= 0 |_)return Sub; /參數(shù)錯誤時，返回空串for(p = i 1; _; p+) /把S.chi1至S.chi1+j復(fù)制到串Sub中Sub.chp i +1 = S.chp

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

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

26、s, ElemType x) int i; if(posL-size+1) /*假如pos越界如此插入失敗*/ return 0; if(L-size=L-MaxSize) /*重新分配更大的存儲空間*/ againMalloc(L);for(i=L-size-1; i=pos-1; i-)L-listi+1=L-listi;L-listpos-1=x; L-size+;return 1; .4.閱讀如下算法代碼：描述算法思路,再綜合出其功能.void InsertIncreaseList( Seqlist *L , Datatype x )int i;if ( L-length=ListSi

27、ze)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i ; / 比擬并移動元素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 next;q=p-next;/p指向第一個不大于min結(jié)點(diǎn)的直接前趨，q指向第一個大

28、于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(隊列上溢出n); Elsecount+;temp = (front+count)%n;Queuetemp=x;int dequeue() int temp;if(count=0) printf(隊列下溢出n);else temp=Queuefront; front=(front+1)%n; coun

29、t-; return temp;.7.閱讀如下算法代碼：描述算法思路,再綜合出其功能.Status ListInsert_L(LinkList &L, int i, ElemType e) /在帶頭結(jié)點(diǎn)的單鏈表L. p = L; k = 0; /初始化，p指向頭結(jié)點(diǎn)，k為計數(shù)器 while (p & k next; + k; / 找到第i-1個元素所在結(jié)點(diǎn) if (!p | k i-1) return ERROR; /無法插入 if(!(s = (LinkLinst) malloc(sizeof(LNode) /申請元素e的結(jié)點(diǎn)空間 return OVERFLOW; /內(nèi)存無空閑單元，無法申請

30、到空間 s-data = e/ 申請一個結(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為記錄序列的下界和上界*/int i，j； struct Recordnode x； i=low； j=high； x=rlow； while(ij) /*在序列的右端掃描*/ while(i=x.key) j-; if(

31、ij) ri=rj;i+;/*在序列的左端掃描*/while(ij&ri.keyx.key) i+;if(ij) rj=ri;j-; ri=x; /*使用遞歸*/ if(lowi) Quicksort(r,low,i-1); if(ihigh) Quicksort(r,j+1,high); .9.閱讀如下算法代碼：描述算法思路,再綜合出其功能. int Binsch(ElemType A, int low, int high, KeyType K) if(low=high) int mid=(low+high)/2; /求出待查區(qū)間內(nèi)中點(diǎn)元素的下標(biāo) if(K=Amid.key) /查找成功返回

32、元素的下標(biāo) return mid; else if(KAmid.key) /在左子表上繼續(xù)查找 return Binsch(A,low,mid-1,K); else /在右子表上繼續(xù)查找 return Binsch(A,mid+1,high,K); else return -1; /查找區(qū)間為空，查找失敗返回-1.10. 閱讀如下算法代碼：描述算法思路,再綜合出其功能.void charge(int a, int n) int i, j, temp; i=0; j=n-1; while(ij) while(ai0 & i=0 & ij) j-; if(ij) temp=ai; ai=aj; a

33、j=temp; i+; j-; .11. 閱讀如下算法代碼：描述算法思路,再綜合出其功能.string Concat_Str(string &S, string T)int i;if (S.length + T.length MaxLength) /連接后串的長度小于串的最大長度for(i = 0; i T.length; i+) S.chS.length+i = T.chi;S.chS.length+T.length =0;S.length += T.length;else /連接后串的長度大于串的最大長度，for(i = 0; i next; pb = Lb-next; Lc = pc =

34、 La; while (pa & pb) if (pa-data if (pa-data 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); 五編程題。 .1. 設(shè)一循環(huán)隊列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個內(nèi)含元素個數(shù)的計數(shù)器，用一個循環(huán)數(shù)組Queue0,n-1表示該循環(huán)隊列,頭指針為front,計數(shù)器count用來記錄隊列中結(jié)點(diǎn)的個數(shù)。請寫出其入隊、出隊

35、操作功能的算法代碼。 .2. 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個結(jié)點(diǎn)之前的位置上。先在單鏈表中找到第i1個結(jié)點(diǎn)，再在其后插入新結(jié)點(diǎn)。請寫出具體算法代碼。.3.假設(shè)有n(=1)個整數(shù)a1, a2, , an. 要求對此數(shù)列由小到大進(jìn)展排序。請寫出具體算法代碼。.4.折半查找的函數(shù)算法，其功能是在線性表r中二分查找關(guān)鍵字為k的結(jié)點(diǎn)，查找到，如此返回其位置i；假如找不到返回0。請寫出具體算法代碼。.5將一個字符串中的所有字符按相反的次序重新放置。請寫出具體算法代碼。.6. 一個線性表中的元素按元素值非遞減有序排列，試設(shè)計算法刪除表中值一樣的多余元素。請寫出具體算法代碼。 .7.快速排序Q

36、uick Sort請寫出其操作功能的算法代碼。其排序的根本思想是：取記錄序列中一個適宜的關(guān)鍵字(通常選取序列中的第一個)，以此關(guān)鍵字取對應(yīng)的記錄ri作為基準(zhǔn)，把一個序列分割成兩個獨(dú)立的子序列，使得基準(zhǔn)位置前的所有記錄的關(guān)鍵字都小于ri key，而基準(zhǔn)位置后的所有記錄的關(guān)鍵字都大于ri.key。這里把這樣的一次過程稱作一次快速排序，在第一次快速排序中，確定了所選取的基準(zhǔn)記錄ri在序列中的最終排列位置，同時也把剩余的記錄分成了兩個序列，然后對每個序列再進(jìn)展分割，重復(fù)上述過程，直到所有記錄全部排好序為止。.8. 以二叉鏈表為存儲結(jié)構(gòu)，設(shè)計一個求二叉樹高度的算法代碼。.9.單鏈表查找第i個結(jié)點(diǎn)，也是從頭指針開始，依次后移到第i個結(jié)點(diǎn)，請寫出具體算法代碼。.10.線性表的插入操作是指在線性表的第m1個數(shù)據(jù)元素和第m個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素x，其結(jié)果是使長度為n的線性表(a1, a2 , am1, am, an)變成長度為n+1的線性表(a1, a2 , am1, x, am, an)，并且數(shù)據(jù)元素am1和am之間的邏輯關(guān)系發(fā)生了變化。請寫出具體算法代碼。25 / 25