數(shù)據(jù)結構(本科)期末綜合練習(算法設計題).DOC

1、數(shù)據(jù)結構(本科)期末綜合練習(算法設計題)1. 設有一個線性表 (e 0, e 1, , , e n-2, e n-1) 存放在一個一維數(shù)組 AarraySize 中的前 n 個數(shù) 組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前 n 個元素內容置換為 (e n-1, en-2 , , , e 1, e 0) 。函數(shù)的原型為：template<class Type>void inverse ( Type A , int n );2. 試編寫一個函數(shù)，在一個順序表A 中找出具有最大值和最小值的整數(shù)。函數(shù)的原型如下所示，原型的參數(shù)表中給出順序表對象為A,通過算法執(zhí)行，從參數(shù)

2、表中的引用參數(shù)Max中得到表中的最大整數(shù)，Min中得到表中的最小整數(shù)。注意，函數(shù)中可使用順序表的兩個公有函數(shù)：Length( ) 求表的長度；getData(int k) 提取第 k 個元素的值。#include “SeqList.h ”template <class T> void FindMaxMin ( SeqList<int>& A, int& Max, int& Min );3. 設有兩個整數(shù)類型的順序表 A (有m個元素)和B (有n個元素)，其元素均以升序排列。 試編寫一個函數(shù)，將這兩個順序表合并成一個順序表C,要求C的元素也以升序

3、排列(表中允許元素重復)。函數(shù)的原型如下所示。原型中的參數(shù)表給出參加運算的三個順序表A、B與G從C中得到執(zhí)行結果。函數(shù)中用到順序表的 4 個公有函數(shù)：Length( ) 求表的當前長度；maxLength( ) 求表的最大允許長度； getData(int k)提取第 k 個元素的值；setData(int k, int val)修改第 k 個元素的值為 val 。template<class T>void merge(SeqList<int>& A, SeqList<int>& B, SeqList<int>& C);4

4、. 編寫一個函數(shù) frequency ，統(tǒng)計在一個輸入字符串中各個不同字符出現(xiàn)的頻度。 函數(shù)返回兩 個數(shù)組： A 記錄字符串中有多少種不同的字符， C 記錄每一種字符的出現(xiàn)次數(shù)。此外，還要通 過整數(shù) k 返回不同字符數(shù)。函數(shù)的原型如下所示：#include <iostream.h>#include <string.h>void frequency( char* s, char A , int C , int &k );5. 根據(jù)兩個有序單鏈表生成一個新的有序單鏈表，原有單鏈表保持不變。要求新生成的鏈表 中不允許有重復元素，并要求返回新表的表頭指針。填寫程序中缺少

5、的部分。ListNode * Merge ( ListNode *L1, ListNode *L2 ) / 根據(jù)兩個有序單鏈表 L1 和 L2, 生成一個新的有序單鏈表ListNode *p1 = L1->link, *p2 = L2->link;ListNode *first=new ListNode;ListNode *p=first;while ( p1 != NULL && p2 != NULL ) / 當兩個鏈表都未檢測完時while ( p1 != NULL ) / 繼續(xù)處理 p1 鏈表中剩余的結點。p=p->link = new ListNode

6、; p->data = p1->data; p1 = p1->link;while ( p2 != NULL ) / 繼續(xù)處理 p2 鏈表中剩余的結點。p=p->link = new ListNode; p->data = p2->data; p2 = p2->link;p->link = NULL;return first->link;6. 假定在一個帶表頭結點的單鏈表 L 中所有結點的值按遞增順序排列，試補充下面函數(shù)，功 能是刪除表L中所有其值大于等于min，同時小于等于max的結點。void rangeDelete ( ListNod

7、e * L, ElemType min, ElemType max )ListNode *q = L, *p = L->link;7. 已知一個帶表頭附加結點的單鏈表 LA 中包含有三類字符： 數(shù)字字符； 字母字符； 其他字符。 試編寫一個 while 循環(huán)補充下面 Separate 函數(shù)，其功能是構造三個新的單鏈表，使 LA,LB,LC 單鏈 表各自指向同一類字符。要求使用原表的結點空間。 Separate 函數(shù)將調用如下兩個函數(shù)：bool isdigit(char ch); / bool isalpha(char ch); /判斷字符是否為數(shù)字，若是則返回“真” ，否則返回“假” 判

8、斷字符是否為字母，若是則返回“真” ，否則返回“假”void Separate ( ListNode *& LA, ListNode *& LB, ListNode *& LC ) / 原來的單鏈表是 LA, 新的三個單鏈表是 LA,LB,LC ，它們均需要帶表頭附加結點 ListNode *pa=LA;ListNode *pb=new ListNode, *pc=new ListNode;LB=pb; LC=pc;ListNode *p=LA->link; /p 指向待處理的結點/ 添加的 while 循環(huán)位置pa->link = NULL; pb->

9、;link = NULL; pc->link = NULL; 8. 已知 first 為單鏈表的表頭指針 能寫出遞歸算法。int Max(LinkNode *f); / 請把 while 循環(huán)內容寫在此行下面結點結構為 (data,link )，試根據(jù)下列每個函數(shù)聲明和算法功遞歸算法 : 求鏈表中的最大值，若鏈表為空則返回 03#int Num(LinkNode *f); /遞歸算法 : 求鏈表中結點個數(shù)#9. 請分別寫出在循環(huán)隊列上進行插入和刪除操作的算法。 循環(huán)隊列定義如下：struct CyclicQueue ElemType elemM; /M int rear,front ;

10、/ rear int tag ;為已定義過的整型常量，表示隊列長度指向隊尾元素后一個位置， front 指向隊頭元素/ 當 front=rear 且 tag=0 時，隊列空，當 front=rear 且 tag=1 時，隊列滿 ;bool EnCQueue( CyclicQueue& Q, ElemType x )/ Q 是一個循環(huán)隊列，最多可存儲 M 個元素，若隊列不滿，/ 將 x 插入至隊尾并返回 true ；否則返回 false 。bool DelCQueue( CyclicQueue& Q, ElemType& x )/ Q 是一個循環(huán)隊列，若隊列不空，則刪除隊

11、頭元素并由 x 帶回， / 且返回 true ，否則返回 false10. Q 是一個由其尾指針和隊列長度標識的循環(huán)隊列，請寫出插入和刪除一個元素的算法。 struct CyclicQueue / 循環(huán)隊列定義ElemType elemM; /M 為已定義過的整型常量4int rear; int len gth;/ rear/ le ngth指向隊尾元素的后一個位置指示隊列中元素個數(shù)5；bool En CQueue( CyclicQueue & Q, ElemType x )/Q是一個循環(huán)隊列，若隊列不滿，則將x插入并返回true ;否則返回falsebool DelCQueue( C

12、yclicQueue & Q, ElemType & x )/Q是一個循環(huán)隊列，若隊列不空，則刪除隊頭元素并由x帶回,/ 且返回true ;否則返回false+ a n-1 x + a n通常使用的方法是一種11.計算多項式 Pn (x) = a 0 xn + a 1 xn-1 + a 2 xn-2 +遞推的方法。它可以描述為如下的遞推形式：pn (x) = x * p n-1 (x) + a n (n >0)此處n-1n-2Ri-1 (x) = a o x + a 1 x + ”+ a n-2 x + a n-1F0=an這也是問題的遞歸形式。多項式的遞歸求解形式為：p

13、oly(x, 0) = A0poly(x, n) = x * poly(x, n-1) + A n, n > 0試編寫一個遞歸函數(shù)，計算這樣的多項式的值。float poly ( float x, float A, i nt n ) 12.從n個自然數(shù)1,2, 3,n中任取k個數(shù)的所有組合數(shù)用C(n, k)表示。求C(n, k)的遞歸公式為1 0 Ii(n<=0, n<k)(n>0, k=0或 k=n)nI(n >0, k=1)C(n-1, k) + C(n-1, k-1) (n >1, 0<k <n)試寫出計算C(n, k)的遞歸函數(shù)：int

14、comb ine ( int n, int k) 13. 已知二叉樹中的結點類型 BinTreeNode定義為：struct Bi nTreeNode char data;Bin TreeNode *left, *right;其中data為結點值域，left和right分別為指向左、右子女結點的指針域。根據(jù)下面函數(shù)聲 明編寫出求一棵二叉樹高度的算法，該高度由函數(shù)返回。假定樹根的層次為0,參數(shù)BT初始指向這棵二叉樹的根結點。int BTreeHeight(B in TreeNode* BT);14. 已知二叉樹中的結點類型BinTreeNode定義為：struct Bi nTreeNode ch

15、ar data;Bin TreeNode *left, *right;其中data為結點值域，left和right分別為指向左、右子女結點的指針域，根據(jù)下面函數(shù)聲 明編寫出求一棵二叉樹中結點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結點。int BTreeCount(BinTreeNode* BT);15. 已知二叉樹中的結點類型BinTreeNode定義為：Bin TreeNode *left, *right;struct Bin TreeNode char data;其中 data 為結點值域， left 和 right 分別為指向左、右子女結點的指針域，根據(jù)下面函

16、數(shù)聲 明編寫出求一棵二叉樹中葉子結點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù) BT 初始指向這棵 二叉樹的根結點。int BTreeLeafCount(BinTreeNode* BT);16. 已知二叉樹中的結點類型 BinTreeNode 定義為 : struct BinTreeNode char data; BinTreeNode *left, *right; 其中 data 為結點值域， left 和 right 分別為指向左、右子女結點的指針域，根據(jù)下面函數(shù)聲 明編寫出刪除一棵二叉樹中所有結點的算法，并使樹根指針為空。假定引用參數(shù) BT 初始指向這棵 二叉樹的根結點。void Clea

17、rBTree(BinTreeNode*& BT);17. 已知二叉樹中的結點類型 BinTreeNode 定義為 :struct BinTreeNode char data; BinTreeNode *left, *right;其中 data 為結點值域， left 和 right 分別為指向左、右子女結點的指針域，根據(jù)下面函數(shù)聲 明編寫出判斷兩棵二叉樹是否相等的算法，若相等則返回1否則返回0。算法中參數(shù)T1和T2為分別指向這兩棵二叉樹根結點的指針。當兩棵樹的結構完全相同并且對應結點的值也相同時才被認為 相等。int BTreeEqual(BinTreeNode* T1,BinTree

18、Node* T2);18. 已知二叉樹中的結點類型用 BinTreeNode 表示，被定義為 : struct BinTreeNode char data;BinTreeNode *left, *right;其中 data 為結點值域， left 和 right 分別為指向左、右子女結點的指針域，根據(jù)下面函數(shù)聲 明編寫出交換一棵二叉樹中所有結點的左、右指針域值的算法，算法中參數(shù)BT 初始指向這棵二叉樹的根結點。void BTreeSwop(BinTreeNode* BT)19. 已知二叉樹中的結點類型用 BinTreeNode 表示，被定義為 :struct BinTreeNode char

19、data;BinTreeNode *left, *right;其中 data 為結點值域， left 和 right 分別為指向左、右子女結點的指針域，根據(jù)下面函數(shù)聲 明編寫出復制一棵二叉樹的算法，并返回復制得到的二叉樹的根結點指針。算法中參數(shù)BT 初始指向待復制二叉樹的根結點。BinTreeNode* BTreeCopy(BinTreeNode* BT);20. 已知二叉樹中的結點類型 BinTreeNode 定義為 :struct BinTreeNode char data;BinTreeNode *left, *right;其中 data 為結點值域， left 和 right 分別為指

20、向左、右子女結點的指針域，根據(jù)下面函數(shù)聲 明編寫出從一棵二叉樹中求出結點值大于 X 的結點個數(shù)的算法，并返回所求結果。算法中參數(shù) BT 初始指向一棵二叉樹的根結點。int BTreeCount(BinTreeNode* BT, ElemType x);21. 假定元素類型為 ElemType 的一維數(shù)組 Rn 中保存著按關鍵碼升序排列的 n 個記錄，記錄 的關鍵碼域key的類型為KeyType,試按照下面的函數(shù)聲明編寫一個非遞歸算法，從一維數(shù)組Rn中折半搜索出關鍵碼等于K的記錄，若搜索成功則返回記錄位置(即元素下標)，否則返回-1。int BinSearch(ElemType R, int n

21、, KeyType K);22. 已知二叉搜索樹中的結點類型 BinTreeNode 定義為 :struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data為結點值域，left和right分別為指向左、右子女結點的指針域。參數(shù)BST指向一棵二叉搜索樹的根結點。試根據(jù)下面的函數(shù)聲明編寫一個非遞歸算法，從BST樹中搜索出具有item參數(shù)值的結點,若搜索成功則返回該結點的地址,否則返回NULL。BinTreeNode* Find(BinTreeNode* BST, const ElemType& item);23. 已知二

22、叉搜索樹中的結點類型 BinTreeNode 定義為 :struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data為結點值域，left和right分別為指向左、右子女結點的指針域。參數(shù)BST指向一棵二叉搜索樹的根結點。試根據(jù)下面的函數(shù)聲明編寫一個遞歸算法，向BST樹中插入值為item的結點,若樹中不存在 item 結點則進行插入并返回 1 表示插入成功,若樹中已存在 item 結點則不插 入并返回 0 表示插入失敗。Int Insert(BinTreeNode*& BST, const ElemType&

23、item);24. 已知二叉搜索樹中的結點類型 BinTreeNode 定義為 :struct BinTreeNode ElemType data;BinTreeNode *left, *right;其中data為結點值域，left和right分別為指向左、右子女結點的指針域。參數(shù)BST指向一棵二叉搜索樹。試根據(jù)下面的函數(shù)聲明編寫一個非遞歸算法，向BST樹中插入值為item的結點，若樹中不存在 item 結點則進行插入并返回 1 表示插入成功,若樹中已存在 item 結點則不插入并返 回 0 表示插入失敗。Int Insert(BinTreeNode*& BST, const Elem

24、Type& item);25. 有一種簡單的排序算法,叫做計數(shù)排序( count sorting )。這種排序算法對一個數(shù)據(jù)互不 相同的表進行排序,并將排序結果存放到另一個新表中。針對表中的每個數(shù)據(jù),計數(shù)算法都要掃描一趟表，統(tǒng)計出表中有多少個數(shù)據(jù)比它小。假設針對某個數(shù)據(jù)，統(tǒng)計出的計數(shù)值為C,則這個數(shù)據(jù)在新表中的合適存放位置應為 c。在下面的函數(shù)模板 Countsort 中，數(shù)組 srC 中存放的是要排序的數(shù)據(jù)；數(shù)組 dest 用于存放排 序的結果； size 為這兩個數(shù)組的大小。請補充完整 Countsort 的函數(shù)體中遺漏部分，使其能夠完成 計數(shù)排序任務。template<Cl

25、ass T>void Countsort(T srC, T dest, int size) int i, j, C;for(i=0; i<size; i+) / 此處遺漏了若干語句，請將這些語句插入到下面destC=srCi;26. 假定函數(shù) reArrange 通過掃描一遍 data 數(shù)組達到重新排列數(shù)據(jù)的目的 , 使得所有負值數(shù) 據(jù)位于所有非負值和 0 值數(shù)據(jù)之前。請補充完整 reArrange 函數(shù)體中遺漏部分，使其能夠完成所要 求的功能。 ( 提示：從兩端向中間掃描 )template<Class T>void reArrange(T data,int size

26、)int i=0,j=size-1;T temp;while(i<j)/此處遺漏了若干語句，請將它們插入到下面算法設計題參考解答1. template<Class Type> void inverse(Type A, int n)Type tmp; / 變量名任意for(int i=0; i<=(n-1)/2; i+) / 或把 i<=(n-1)/2 改為 i<n/2 tmp=Ai; Ai=An-i-1; An-i-1=tmp;2. #include “SeqList.h ” template <class T> void FindMaxMin

27、( SeqList<int>& A, int& Max, int& Min ) Max = Min = A.getData(0);for ( int i = 1; i < A.Length( ); i+ ) if ( A.getData(i) > Max ) Max = A.getData(i); else if ( A.getData(i) < Min ) Min = A.geyData(i); 3. template<class T> void merge(SeqList<int>& A, SeqList

28、<int>& B, SeqList<int>& C) int m=A.Length(), n=B.Length(), mpn=m+n; if(mpn>C.maxLength()cerr<< “合并后表的長度超出表 C 的最大允許長度 ”<<endl; exit(1);int i=0, j=0, k=0, av=A.getData(i), bv=B.getData(j); while(i<m && j<n) if(av<=bv) C.setData(k+, av); av=A.getData(

29、+i); if(av>=bv)C.setData(k+, bv); bv=B.getData(+j); if(i<m) while(k<mpn)C.setData(k+, av); av=A.getData(+i); elsewhile(k<mpn)C.setData(k+, bv); bv=B.getData(+j); 4. #include <iostream.h> #include "string1.h" void frequency( char* s, char A , int C , int &k ) int i, j,

30、 len =strlen(s);if ( !len ) cout << "The string is empty. " << endl; k = 0; return; A0 = s0; C0 = 1; k = 1;for ( i = 1; i < len; i+ ) Ci = 0; for ( i = 1; i < len; i+ ) for ( j = 0; j < k && Aj != si; j+ );if ( j = k ) Ak = si; Ck+; k+; else Cj+;5. p=p->link

31、 = new ListNode;if ( p1->data = p2->data ) p->data = p1->data; p1 = p1->link; p2 = p2->link; else if ( p1->data < p2->data ) p->data = p1->data; p1 = p1->link; else p->data = p2->data; p2 = p2->link; 6. while ( p != NULL) /2 分 if(p->data >= min &

32、;& p->data <=max) q->link=p->link; delete p; p=q->link; /4 分 else q=p; p=p->link;/2 分7. while(p!=NULL) if(isdigit(p->data) pa->link=p; pa=p;else if(isalpha(p->data) pb->link=p; pb=p;else pc->link=p; pc=p;p=p->link;8. int Max(LinkNode *f) / 遞歸算法 : 求鏈表中的最大值 if(f

33、=NULL) return 0;if(f->link=NULL) return f->data;int temp=Max(f->link); if(f->data>temp) return f->data;else return temp;int Num(LinkNode *f); / 遞歸算法 : 求鏈表中結點個數(shù) if(f=NULL) return 0; return 1+Num(f->link);9. / 將 x 插入至隊尾if (Q.rear = Q.front && Q.tag = 1) return false; Q.ele

34、mQ.rear = x;Q.rear = (Q.rear+1) % M;if (Q.rear = Q.front) Q.tag = 1;return true;/ 刪除隊頭元素if (Q.front = Q.rear && Q.tag = 0) return false; x = Q.elemQ.front;Q.front = (Q.front+1) % M; if (Q.front = Q.rear) Q.tag = 0;return true;10. / 將 x 插入至隊尾 if(Q.length=M) return false; Q.elemQ.rear=x;Q.rear

35、=(Q.rear+1)%M; Q.length+;return true;/ 刪除隊頭元素 if(Q.length=0) return false; x=Q.elem(Q.rear-Q.length+M)%M; Q.length-;return true;11. float poly ( float x, float A , int n ) if ( ! n ) return A0;else return x * poly( x, A, n-1 ) + An; 12.int combine (int n, int k) if(n<=0 | n<k) return 0; if(k=0

36、 | k=n) return 1; if(k=1) return n;return combine (n-1,k)+ combine (n-1,k-1); 13. int BTreeHeight(BinTreeNode* BT) if(BT=NULL)/ 對于空樹，返回 -1 并結束遞歸 return ;else/ 計算左子樹的高度int h1=BTreeHeight(BT->left);/計算右子樹的高度int h2=BTreeHeight(BT->right);/返回樹的高度if(h1>h2) return h1+1;else return h2+1;說明：函數(shù)體中的兩個

37、 else 可以沒有14. int BTreeCount(BinTreeNode* BT) if(BT=NULL) return 0; elsereturn BTreeCount(BT->left)+BTreeCount(BT->right)+1;15. int BTreeLeafCount(BinTreeNode* BT) if(BT=NULL) return 0; else if(BT->left=NULL && BT->right=NULL) return 1; else return BTreeLeafCount(BT->left)+BTr

38、eeLeafCount(BT->right);說明：函數(shù)體中的兩個 else 可以沒有16. void ClearBTree(BinTreeNode*& BT) if(BT!=NULL)/ 遞歸刪除左子樹 ClearBTree(BT->left);/遞歸刪除右子樹ClearBTree(BT->right);/回收根結點delete BT;/ 置根指針為空BT=NULL;17. int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)/ 若兩棵樹均為空則返回 1 表示相等if(T1=NULL && T2=NULL)

39、return 1;/ 若一棵為空一棵不為空則返回 0 表示不等else if(T1=NULL | T2=NULL) return 0;/ 若根結點值相等并且左、右子樹對應相等則兩棵樹相等else if(T1->data=T2->data && BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right) ) return 1;/ 若根結點值不等或左、右子樹對應不等則兩棵樹不等elsereturn 0;另一個參考答案：int BTreeEqual(BinTr

40、eeNode* T1,BinTreeNode* T2)/ 若兩棵樹均為空或實際上是同一棵樹時返回 1 表示相等 if(T1=T2) return 1;/ 若一棵為空一棵不為空則返回 0 表示不等 if(T1=NULL | T2=NULL) return 0;/ 若根結點值不等返回 0 表示不等if(T1->data!=T2->data) return 0;/ 若根結點值相等則兩棵樹是否相等取決于它們的左、右子樹是否對應相等 return BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right,

41、T2->right); 18. void BTreeSwop(BinTreeNode* BT)if(BT!=NULL) / 交換左右子女指針域的值BinTreeNode* pt=BT->left;BT->left=BT->right;BT->right=pt;/ 對左子樹進行同樣處理BTreeSwop(BT->left);/ 對右子樹進行同樣處理BTreeSwop(BT->right);19. BinTreeNode* BTreeCopy(BinTreeNode* BT)if(BT=NULL) return NULL;else / 得到新結點BinTr

42、eeNode* pt=new BinTreeNode;/ 復制根結點值pt->data=BT->data;/ 復制左子樹 pt->left=BTreeCopy(BT->left);/ 復制右子樹 pt->right=BTreeCopy(BT->right);/ 返回新樹的樹根指針return pt; 說明：函數(shù)體中的 else 可以沒有20. / 統(tǒng)計出二叉樹中大于給定值 x 的結點個數(shù)，該統(tǒng)計值由函數(shù)返回 int BTreeCount(BinTreeNode* BT, ElemType x)if(BT=NULL) return 0;else if( BT->data>x)return BTreeCount( BT->left, x)+BTreeCount( BT->right, x)+1; elsereturn BTreeCount( BT->left, x)+BTreeCount( BT->right, x); /3 說明：函數(shù)體中