word數(shù)據(jù)結(jié)構(gòu)課程習(xí)題集 第 1 頁(yè) 共 25 頁(yè)一、. 選擇題 . 1. 算法的計(jì)算量的大小稱為計(jì)算的 。A效率 B. 復(fù)雜性 C. 現(xiàn)實(shí)性 D. 難度.2. 算法的時(shí)間復(fù)雜度取決于 .A問(wèn)題的規(guī)模 B. 待處理數(shù)據(jù)的初態(tài) C. A和B D. 難確定.3. 下面關(guān)于算法說(shuō)法錯(cuò)誤的答案是 A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn) C. 算法的可行性是指指令不能有二義性 D. 以上幾個(gè)都是錯(cuò)誤的.4從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為 兩大類。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. 二叉樹(shù) 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線性表采用存儲(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ī)訪問(wèn)任一元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比.11. 設(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. 僅修改尾指針 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)在 ( )A可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符 C可以存儲(chǔ) D數(shù)據(jù)元素可以是多個(gè)字符.17關(guān)于空串與空格串，下面說(shuō)法正確的答案是( )。 A空串與空格串是一樣的 B空串與空格串長(zhǎng)度是一樣的 C空格串中存放的都是空格D空串中存放的都是NULL. 18圖中有關(guān)路徑的定義是 。 A由頂點(diǎn)和相鄰頂點(diǎn)序偶構(gòu)成的邊所形成的序列 B由不同頂點(diǎn)所形成的序列C由不同邊所形成的序列 D上述定義都不是.19設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，如此該圖最多有 條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2.20一個(gè)n個(gè)頂點(diǎn)的連通無(wú)向圖，其邊的個(gè)數(shù)至少為 。An-1 Bn Cn+1 Dnlogn；.21某內(nèi)排序方法的穩(wěn)定性是指( )。 A該排序算法不允許有一樣的關(guān)鍵字記錄 B該排序算法允許有一樣的關(guān)鍵字記錄C平均時(shí)間為0n log n的排序方法 D以上都不對(duì) .22如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的局部排序的序列，用 方法最快。A起泡排序 B快速排列 CShell排序 D堆排序 E簡(jiǎn)單項(xiàng)選擇擇排序 .23排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是( )排序法。A插入 B. 選擇 C. 冒泡 D. 都不是.24下面給出的四種排序方法中，排序過(guò)程中的比擬次數(shù)與排序方法無(wú)關(guān)的是。( )A選擇排序法 B. 插入排序法 C. 快速排序法 D. 都不是.25對(duì)序列15，9，7，8，20，-1，4進(jìn)展排序，進(jìn)展一趟后數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15；如此采用的是 排序。A. 選擇 B. 快速 C. 希爾 D. 冒泡.26. 設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 如此T中的葉子數(shù)為 A5 B6 C7 D8.27一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是 A 250 B 500 C254 D505 E以上答案都不對(duì) .28. 有關(guān)二叉樹(shù)如下說(shuō)法正確的答案是 . A二叉樹(shù)的度為2 B一棵二叉樹(shù)的度可以小于2 C二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 D二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為2.29二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為 .A2I B 2I-1-1 C 2I-1 D2I -1.30對(duì)于有n 個(gè)結(jié)點(diǎn)的二叉樹(shù), 其高度為 .Anlog2n Blog2n Cëlog2nû|+1 D不確定.31對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(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. 從根開(kāi)始按層次遍歷.32. 對(duì)N個(gè)元素的表做順序查找時(shí)，假如查找每個(gè)元素的概率一樣，如此平均查找長(zhǎng)度為( ) AN+1/2 B. N/2 C. N D. 1+N*N /2.33. 對(duì)線性表進(jìn)展二分查找時(shí)，要求線性表必須 A.以順序方式存儲(chǔ) B.以順序方式存儲(chǔ),且數(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. 哈希法查找二、填空題.1. 對(duì)于長(zhǎng)度為255的表，采用分塊查找，每塊的最優(yōu)長(zhǎng)度為_(kāi)。.2. 順序查找n個(gè)元素的順序表，假如查找成功，如此比擬關(guān)鍵字的次數(shù)最多為_(kāi) _次；當(dāng)使用監(jiān)視哨時(shí)，假如查找失敗，如此比擬關(guān)鍵字的次數(shù)為_(kāi) _。.3在有序表A1.12中，采用二分查找算法查等于A12的元素，所比擬的元素下標(biāo)依次為_(kāi)。.4. 在一棵二叉樹(shù)中，第5層上的結(jié)點(diǎn)數(shù)最多為個(gè)。.5.、n(n>0)個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，葉結(jié)點(diǎn)最多有個(gè)，最少有個(gè)。假如二叉樹(shù)有m個(gè)葉結(jié)點(diǎn)，如此度為2的結(jié)點(diǎn)有個(gè)。.6二叉樹(shù)中某一結(jié)點(diǎn)左子樹(shù)的深度減去右子樹(shù)的深度稱為該結(jié)點(diǎn)的_。.7. 假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18，如此它的最小深度為，最大深度為；.8. 在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n 0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為 n 2，如此有n0=。.9. 現(xiàn)有按中序遍歷二叉樹(shù)的結(jié)果為abc，問(wèn)有_種不同形態(tài)的二叉樹(shù)可以得到這一遍歷結(jié)果，這些二叉樹(shù)分別是_。.10假如不考慮基數(shù)排序，如此在排序過(guò)程中，主要進(jìn)展的兩種根本操作是關(guān)鍵字的_和記錄的_。.11直接插入排序用監(jiān)視哨的作用是_。.12. 不受待排序初始序列的影響，時(shí)間復(fù)雜度為O(N2)的排序算法是_，在排序算法的最后一趟開(kāi)始之前，所有元素都可能不在其最終位置上的排序算法是_。_。.14具有10個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為_(kāi)。.15假如用n表示圖中頂點(diǎn)數(shù)目，如此有_條邊的無(wú)向圖成為完全圖。.16空格串是指_ _，其長(zhǎng)度等于_ _。.17設(shè)T和P是兩個(gè)給定的串，在T中尋找等于P的子串的過(guò)程稱為_(kāi) _，又稱P為_(kāi) _。.18串的兩種最根本的存儲(chǔ)方式是_ _、_ _；兩個(gè)串相等的充分必要條件是_ _。 .19. 鏈隊(duì)列的頭尾指針?lè)謩e是f和r，如此將值x入隊(duì)的操作序列是_。.20.向棧中壓入元素的操作是_。.21.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。.22用S表示入棧操作，X表示出棧操作，假如元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為_(kāi)。.23. 單鏈表是_的存儲(chǔ)表示。 .24. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_，另一個(gè)指向_。.25存儲(chǔ)的特點(diǎn)是利用_來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。.26.順序存儲(chǔ)結(jié)構(gòu)是通過(guò)_表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過(guò)_表示元素之間的關(guān)系的。.27線性表L=a1,a2,an用數(shù)組表示，假定刪除表中任一元素的概率一樣，如此刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是_。.28根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_。.29數(shù)據(jù)的物理結(jié)構(gòu)包括的表示和的表示。.30抽象數(shù)據(jù)類型的定義僅取決于它的一組_ _，而與_ _無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的_ _不變，都不影響其外部使用。.31數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是.32. 數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的_和_ ，以與它們之間的相互關(guān)系，并對(duì)與這種結(jié)構(gòu)定義相應(yīng)的，設(shè)計(jì)出相應(yīng)的 _。.三程序填空題 1 單鏈表H為一個(gè)用帶頭結(jié)點(diǎn)的鏈表表示的線性表，如下算法是將其倒置。請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。 P46template<class T>void Line_ListLink<T>：Reverse ( ) Line_ListNode<T> *p，*head=new Line_ListNode<T>( )； while(first! =NULL) p=first；first=first>link； p>link=head - >link；head>link=p； first=head>link； delete head；2在順序表中隨機(jī)存取的數(shù)據(jù)，很容易在順序表中實(shí)現(xiàn)按序號(hào)查找元素。代碼如下所示，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。 template<class T> bool Line_ListSqu<T>：Find(_ ，T& x) const /在線性表中查找第i個(gè)元素并用x返回 if (_ ) return false； x=elemi1； return _ ； 3線性表的插入操作是指在線性表的第m1個(gè)數(shù)據(jù)元素和第m個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素x，其結(jié)果是使長(zhǎng)度為n的線性表(a1, a2 , am1, am, an)變成長(zhǎng)度為n+1的線性表(a1, a2 , am1, x, am, an)，并且數(shù)據(jù)元素am1和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)谙聞澗€處填上正確的語(yǔ)句。template<class T>Line_ListSqu<T>& Line_ListSqu<T>：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個(gè)數(shù)據(jù)元素，循環(huán)進(jìn)展n 趟如下的排序過(guò)程，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。void BubbleSort(DataType a , int n) 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ù)元素，具體實(shí)現(xiàn)代碼如下，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。 template<class T> int Line_ListSqu<T>：Search(const T& x) const int_ ； if (IsEmpty( ) return 0；/線性表為空時(shí)返回0 while(_ ) i+； if (elemi= =x) return +i； else return _ ； .6.線性表的刪除操作是使長(zhǎng)度為n的線性表(a1, a2, am1, am,an)變?yōu)殚L(zhǎng)度為n1的線性表(a1, a2, am1, am+1,an)，并且數(shù)據(jù)元素am1、am和am+1之間的邏輯關(guān)系也會(huì)發(fā)生變化，需要把第m+1n個(gè)元素共nm個(gè)元素依次向前移動(dòng)一個(gè)位置來(lái)反映這種變化。具體實(shí)現(xiàn)步驟如下：判斷刪除位置i是否合法，合法如此將該位置元素放入x中，否如此拋出異常；將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減1。具體算法如下，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。template<class T> Line_ListSqu<T>& Line_ListSqu<T>：Delete(_ ，T& x) if (Find(i，x) for(_ ；j<length；j+) elem_ =elemj； length ； return _ else throw OutOfBounds( )； .7. 假設(shè)以數(shù)組am存放循環(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)谙聞澗€處填上正確的語(yǔ)句。#define m 100 int enqueue(int a, int rear, int length, int x) if(_) printf(“queue 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個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i1個(gè)結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算法代碼如下所,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。template<class T>Line_ListLink<T>& Line_ListLink<T>：Delete(int i，T& x) if (_| !first) throw OutOfBounds( )；/刪除位置不合法 Line_ListNode<T> *p=first； if (_) first=first>link； else Line_ListNode<T> *q=first； int j=1； /查找第i個(gè)結(jié)點(diǎn) while(_j<i) q=q>link；+j； if (!q | _) throw OutOfBounds( )；/沒(méi)有第i個(gè)結(jié)點(diǎn) p=q>link；q>link=p>link； .9. 刪除運(yùn)算是將單鏈表的第i個(gè)結(jié)點(diǎn)刪去。先在單鏈表中找到第i1個(gè)結(jié)點(diǎn)，再刪除其后的結(jié)點(diǎn)。具體算法代碼 如下所示：請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。template<class T>Line_ListLink<T>& Line_ListLink<T>：Delete(int i，T& x) if (_) throw OutOfBounds( )；/刪除位置不合法 Line_ListNode<T> *p=first； if (_) first=first>link； else Line_ListNode<T> *q=first； int j=1； /查找第i個(gè)結(jié)點(diǎn) while(q && j<i) q=q>link；+j； if (!q | _) throw OutOfBounds( )；/沒(méi)有第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)谙聞澗€處填上正確的語(yǔ)句。string Sub_String(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.chi1至S.chi1+j復(fù)制到串Sub中Sub.chp i +1 = S.chp;Sub.chj ='0' _ = j;return Sub; 四閱讀理解題(描述算法思路,再綜合出其功能)此題說(shuō)明:算法思路指的是對(duì)某種數(shù)據(jù)結(jié)構(gòu)(如,記錄序列), 進(jìn)展操作(如,移動(dòng)位置), 的處理步驟(如,1,2,3.).算法功能指的是要達(dá)到的處理目標(biāo)(如,合并成有序的單鏈表.).1. 閱讀如下算法代碼：描述算法思路,再綜合出其功能.main() int i,max,a10;printf(“請(qǐng)輸入10個(gè)整數(shù):);for(i=0;i<=10;i+) scanf(“%d,&ai);max=a0;i=1;while(i<10)if(ai>max) max=ai;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; if(p=NULL) printf("未找到x！n"); else if(q=head) printf("x為第一個(gè)結(jié)點(diǎn)，無(wú)前趨！n"); else q->data=x; q->next=p->next; free(p); .3. 閱讀如下算法代碼：描述算法思路,再綜合出其功能. int InsertPosList(struct List *L, int 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->listi+1=L->listi;L->listpos-1=x; L->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 ; / 比擬并移動(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;/p指向第一個(gè)不大于min結(jié)點(diǎn)的直接前趨，q指向第一個(gè)大于min的結(jié)點(diǎn)while(q &&q->data<max)s=q;q=q->next;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"); Elsecount+;temp = (front+count)%n;Queuetemp=x;int dequeue() int temp;if(count=0) printf("隊(duì)列下溢出n");else temp=Queuefront; front=(front+1)%n; count-; 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為計(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; /無(wú)法插入 if(!(s = (LinkLinst) malloc(sizeof(LNode) /申請(qǐng)?jiān)豦的結(jié)點(diǎn)空間 return OVERFLOW; /內(nèi)存無(wú)空閑單元，無(wú)法申請(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為記錄序列的下界和上界*/int i，j； struct Recordnode x； i=low； j=high； x=rlow； while(i<j) /*在序列的右端掃描*/ while(i<j&&rj.key>=x.key) j-; if(i<j) ri=rj;i+;/*在序列的左端掃描*/while(i<j&&ri.key<x.key) i+;if(i<j) rj=ri;j-; ri=x; /*使用遞歸*/ if(low<i) Quicksort(r,low,i-1); if(i<high) 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) /查找成功返回元素的下標(biāo) return mid; else if(K<Amid.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(i<j) while(ai<0 && i<j) i+; while(aj>=0 && i<j) j-; if(i<j) temp=ai; ai=aj; aj=temp; i+; j-; .11. 閱讀如下算法代碼：描述算法思路,再綜合出其功能.string Concat_Str(string &S, string T)int i;if (S.length + T.length < MaxLength) /連接后串的長(zhǎng)度小于串的最大長(zhǎng)度f(wàn)or(i = 0; i < T.length; i+) S.chS.length+i = T.chi;S.chS.length+T.length ='0'S.length += T.length;else /連接后串的長(zhǎng)度大于串的最大長(zhǎng)度，for(i = 0; i < MaxLength1S.length; i+) S.chS.length+i = T.chi;S.chMaxLength 1 ='0'S.length = MaxLength;return S; .12. 閱讀如下算法代碼：描述算法思路,再綜合出其功能.void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) / 兩個(gè)非遞減單鏈表La、Lb ，且 Lc非遞減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); 五編程題。 .1. 設(shè)一循環(huán)隊(duì)列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)內(nèi)含元素個(gè)數(shù)的計(jì)數(shù)器，用一個(gè)循環(huán)數(shù)組Queue0,n-1表示該循環(huán)隊(duì)列,頭指針為front,計(jì)數(shù)器count用來(lái)記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。請(qǐng)寫出其入隊(duì)、出隊(duì)操作功能的算法代碼。 .2. 插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到單鏈表的第i個(gè)結(jié)點(diǎn)之前的位置上。先在單鏈表中找到第i1個(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)鍵字為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。這里把這樣的一次過(guò)程稱作一次快速排序，在第一次快速排序中，確定了所選取的基準(zhǔn)記錄ri在序列中的最終排列位置，同時(shí)也把剩余的記錄分成了兩個(gè)序列，然后對(duì)每個(gè)序列再進(jìn)展分割，重復(fù)上述過(guò)程，直到所有記錄全部排好序?yàn)橹埂?8. 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)求二叉樹(shù)高度的算法代碼。.9.單鏈表查找第i個(gè)結(jié)點(diǎn)，也是從頭指針開(kāi)始，依次后移到第i個(gè)結(jié)點(diǎn)，請(qǐng)寫出具體算法代碼。.10.線性表的插入操作是指在線性表的第m1個(gè)數(shù)據(jù)元素和第m個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素x，其結(jié)果是使長(zhǎng)度為n的線性表(a1, a2 , am1, am, an)變成長(zhǎng)度為n+1的線性表(a1, a2 , am1, x, am, an)，并且數(shù)據(jù)元素am1和am之間的邏輯關(guān)系發(fā)生了變化。請(qǐng)寫出具體算法代碼。25 / 25