算法題目及答案.docx

1根據(jù)兩個有序單鏈表生成一個新的有序單鏈表，原有單鏈表保持不變。要求新生成的鏈表中不允許有重復(fù)元素。算法如下ListNode * Merge ( ListNode * L1, ListNode * L2 ) /根據(jù)兩個帶表頭結(jié)點的有序單鏈表L1和L2, 生成一個新的有序單鏈表ListNode *first = new ListNode;ListNode *p1 = L1-link, *p2 = L2-link, *p = first, *q;while ( p1 != NULL & p2 != NULL ) q = new ListNode;if ( p1-data = p2-data ) q-data = p1-data; p2 = p2-link; p1 = p1-link; else if ( p1-data data ) q-data = p1-data; p1 = p1-link; else q-data = p2-data; p2 = p2-link; p-link = q; p = q;while ( p1 != NULL ) q = new ListNode; q-data = p1-data; p1 = p1-link;p-link = q; p = q;while ( p2 != NULL ) q = new ListNode; q-data = p2-data; p2 = p2-link;p-link = q; p = q;p-link = NULL; return first;2設(shè)有一個線性表 (e0, e1, , en-2, en-1) 存放在一個一維數(shù)組Aarraysize中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為 (en-1, en-2, , e1, e0)。數(shù)組原地逆置算法參數(shù)表中給出數(shù)組A 及指定的數(shù)組中前n個元素，函數(shù)執(zhí)行后從A 中得到數(shù)組原地逆置后的結(jié)果。Template void inverse ( T A , int n )T tmp;for ( int I = 0; I = ( n-1 ) / 2; I+ ) tmp = AI; AI = An-I-1; An-I-1 = tmp;3設(shè)有兩個整數(shù)類型的順序表A（有 m個元素）和B（有n個元素），其元素均以從小到大的升序排列。試編寫一個函數(shù)，將這兩個順序表合并成一個順序表C，要求C的元素也以從小到大的升序排列。合并兩個升序排列的順序表的算法參數(shù)表給出參加運算的三個順序表A、B與C。從C中得到執(zhí)行結(jié)果。算法中用到順序表的4個共有函數(shù)：Length( ) 求表的當(dāng)前長度；maxLength( ) 求表的最大允許長度；getData(k) 提取第k個元素的值；setData(k) 修改第k個元素的值。Template void merge ( SeqList& A, SeqList& B, SeqList& C ) int m = A.Length( ), n = B.Length( ), mpn = m + n;if ( mpn C.maxLength( ) ) cerr “合并后表的長度超出表的最大允許長度” 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(+I); else C.setData(k+, bv); B.getData(+j); if ( I m ) while ( k mpn ) C.setData(k+, av); av = A.getData(+I); else while ( k link;ListNode * pa = LA, * pb = LB, * pc = LC;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;pa-link = NULL; pb-link = NULL; pc-link = NULL;5一顆具有n個結(jié)點的完全二叉樹以順序方式存儲在數(shù)組A中，設(shè)計一個算法構(gòu)造該二叉樹的二叉鏈存儲結(jié)構(gòu)。算法如下void ctree(BTNode *&t,ElemType a,int i,int n) if(in) t=NULL; else t=(BTNode*)malloc(sizeof(BTNode); t-data=ai-1; ctree(t-lchild,a,2*i,n); ctree(t-rchild,a,2*i+1,n); 6編寫一個算法frequency，統(tǒng)計在一個輸入字符串中各個不同字符出現(xiàn)的頻度。算法返回兩個數(shù)組：A 記錄字符串中有多少種不同的字符，C 記錄每一種字符的出現(xiàn)次數(shù)。此外，還要返回不同字符數(shù)。求輸入字符串中各種不同字符出現(xiàn)頻度的算法由于需要返回多種信息，參數(shù)表中引入引用參數(shù)：A 中記錄字符串中有多少種不同的字符，C 中記錄每一種字符的出現(xiàn)次數(shù)，k返回不同字符數(shù)。#include #include string1.hvoid frequency( String& s, char A , int C , int &k )int I, j, len = s.Length( );if ( !len ) cout The string is empty. endl; k = 0; return; else A0 = s0; C0 = 1; k = 1; for ( I = 1; I len; I+ ) CI = 0; for ( I = 1; I len; I+ ) for ( j = 0; j leftChild ); /計算左子樹的高度，int h2 = BTreeHeight (BT-rightChild );/計算右子樹的高度， if ( h1 h2 ) return h1+1; else return h2+1; /返回樹的高度， 8已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點。Int BTreeCount ( BinTreeNode* BT );算法如下int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0; else return BTreeCount ( BT-leftChild ) + BTreeCount ( BT-rightChild ) + 1;9已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中葉子結(jié)點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點。Int BTreeLeafCount ( BinTreeNode* BT );算法如下int BTreeLeafCount ( BinTreeNode* BT )if ( BT = NULL ) return 0; else if (BT-leftChild = NULL & BT-rightChild = NULL) return 1; else return BTreeLeafCount ( BT-leftChild ) + BTreeLeafCount ( BT-rightChild ); 10已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出刪除一棵二叉樹中所有結(jié)點的算法，并使樹根指針為空。假定引用參數(shù)BT初始指向這棵二叉樹的根結(jié)點。Void ClearBinTree ( BinTreeNode*& BT);算法如下void ClearBinTree ( BinTreeNode*& BT ) if ( BT!=NULL )/ ClearBinTree ( BT-leftChild ); /遞歸刪除左子樹，ClearBinTree ( BT-rightChild ); /遞歸刪除右子樹， delete BT; /回收根結(jié)點，BT = NULL; /置根指針為空， 11已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出復(fù)制一棵二叉樹的算法，并返回復(fù)制得到的二叉樹的樹根指針。算法中參數(shù)BT初始指向待復(fù)制二叉樹的根結(jié)點。BinTreeNode* BTreeCopy ( BinTreeNode* BT );算法如下BinTreeNode* BtreeCopy ( BinTreeNode* BT )if ( BT = NULL ) return NULL;/1分else BinTreeNode* pt = new BinTreeNode; /得到新結(jié)點，pt-data = BT-data; /復(fù)制根結(jié)點值， pt-leftChild = BtreeCopy ( BT-leftChild ); /復(fù)制左子樹， pt-rightChild = BTreeCopy ( BT-rightChild );/復(fù)制右子樹， return pt; /返回新樹的樹根指針， 12已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出從一棵二叉樹中求出結(jié)點值大于x的結(jié)點個數(shù)的算法，并返回所求結(jié)果。算法中參數(shù)BT初始指向二叉樹的根結(jié)點。Int BTreeCount ( BinTreeNode* BT, ElemType x );算法如下/統(tǒng)計出二叉樹中大于給定值x的結(jié)點個數(shù)，該統(tǒng)計值由函數(shù)返回int BtreeCount ( BinTreeNode* BT, ElemType x ) if ( BT = NULL ) return 0; else if ( BT-data x ) return BtreeCount ( BT-leftChild, x ) + BtreeCount ( BT-rightChild, x ) + 1;elsereturn BtreeCount ( BT-leftChild, x ) + BtreeCount ( BT-rightChild, x );13試編寫函數(shù)用鄰接表存儲結(jié)構(gòu)實現(xiàn)template int AdjTable :GetFirstNeighbor ( int v );/給出頂點位置為v 的第一個鄰接頂點的位置，如果找不到，則函數(shù)返回-1算法實現(xiàn)如下template int AdjTable :GetFirstNeighbor ( int v ) /給出頂點位置為v 的第一個鄰接頂點的位置，如果找不到，則函數(shù)返回-1if ( v != -1 )Edge *p = NodeTable (v).adj; if ( p != NULL ) return p-dest; return 1;14試編寫函數(shù)用鄰接表存儲結(jié)構(gòu)實現(xiàn)template int AdjTable :GetNextNeighbor ( int v, int w );給出頂點v的鄰接頂點w的下一個鄰接頂點的位置，若沒有下一個鄰接頂點，則函數(shù)返回-1算法實現(xiàn)如下template int AdjTable :GetNextNeighbor ( int v, int w ) /*給出頂點v的鄰接頂點w的下一個鄰接頂點的位置，若沒有下一個鄰接頂點，則函數(shù)返回-1*/if ( v != -1 ) Edge * p = NodeTablev.adj;while ( p != NULL ) if (p-dest = w & p-link != NULL )return p-link-dest;else p = p-link;return 1;15假定元素類型為ElemType的一維數(shù)組Rn 中保存著按關(guān)鍵碼升序排列的n個對象，對象的關(guān)鍵碼域key的類型為KeyType，試按照下面的函數(shù)聲明編寫一個非遞歸算法，從一維數(shù)組Rn中用折半搜索法找出關(guān)鍵碼等于k的對象，若搜索成功則返回對象位置（即元素下標），否則返回-1。Int BinSearch ( ElemType R , int n, KeyType k );算法如下：int BinSearch ( ElemType R , int n, KeyType k ) int low = 0, high = n-1; /賦初值2分while ( low = high ) /循環(huán)條件1分int mid = (low + high) / 2;/中點位置1分if ( k = Rmid.key ) return mid;/成功返回1分else if ( k data ) return BST; /成功返回2分else if ( x data ) BST = BST-leftChild; /向左孩子查找2分else BST = BST-rightChild; /向右孩子查找2分return NULL; /失敗返回1分17試設(shè)計一個算法，改造一個帶表頭結(jié)點的雙向循環(huán)鏈表，所有結(jié)點的原有次序保持在各個結(jié)點的右鏈域rLink中，并利用左鏈域lLink把所有結(jié)點按照其值從小到大的順序連接起來。算法如下void OrderedList ( DblNode * L ) /利用左鏈域llink把所有結(jié)點按照其值從小到大的順序連接起來DblNode * endp = L, * pr, * p, *s, *q = L-llink;s = q-llink; q-llink = endp;/2分while ( s != endp ) pr = endp; p = pr-llink; /2分while ( p != endp )if ( p-data s-data ) break; elsepr = p; p = p-llink; q = s-llink; pr-llink = s; s-llink = p;/3分s = q; /1分18編寫一個程序?qū)崿F(xiàn)直接插入排序算法。void InsertSort(RecType R,int n) /*對R0.n-1按遞增有序進行直接插入排序*/int i,j,k;RecType tmp;for (i=1;i=0 & tmp.keyRj.key) Rj+1=Rj; /*將關(guān)鍵字大于Ri.key的記錄后移*/j-;Rj+1=tmp; /*在j+1處插入Ri*/printf(i=%d: ,i);for (k=0;kn;k+)printf(%d ,Rk.key);printf(n);19編寫一個程序?qū)崿F(xiàn)冒泡排序算法。#include #define MaxSize 20typedef int KeyType; /*定義關(guān)鍵字類型*/typedef char InfoType10;typedef struct /*記錄類型*/KeyType key; /*關(guān)鍵字項*/InfoType data; /*其他數(shù)據(jù)項,類型為InfoType*/ RecType;/*排序的記錄類型定義*/void BubbleSort1(RecType R,int n)int i,j,k,exchange;RecType tmp;for (i=0;ii;j-)/*比較,找出最小關(guān)鍵字的記錄*/if (Rj.keyRj-1.key)tmp=Rj; /*Rj與Rj-1進行交換,將最小關(guān)鍵字記錄前移*/Rj=Rj-1;Rj-1=tmp;exchange=1;printf(i=%d: ,i);for (k=0;kadjlistv.firstarc; /*p指向頂點v的第一條弧的弧頭結(jié)點*/while (p!=NULL) if (visitedp-adjvex=0)/*若p-adjvex頂點未訪問,遞歸訪問它*/DFS(G,p-adjvex); p=p-nextarc; /*p指向頂點v的下一條弧的弧頭結(jié)點*/21編寫算法實現(xiàn)圖G的鄰接矩陣的存儲結(jié)構(gòu)。MGraph creat_mg()int i,j,k,h;char b,t;MGraph mg;printf(input vex and arc:);scanf(%d,%d,&i,&j);mg.n=i;mg.e=j;for (i=0;img.n;i+)printf(number %d verinfo:,i);getchar();scanf(%d,&mg.vexsi);for (i=0;img.n;i+)for (j=0;jmg.n;j+)mg.edgesij=0;for (k=1;k=mg.e;k+)printf(num %d adge:,k);scanf(%d,%d,&i,&j);while (img.n|jmg.n)printf(input error,repeat input:);scanf(%d,%d,&i,&j);printf(the value is:);scanf(%d,&h);mg.edgesij=h;return mg;22編寫程序?qū)崿F(xiàn)二叉樹的先序、中序、后序遍歷的遞歸算法。void PreOrder(BTNode *b) /*先序遍歷的遞歸算法*/if (b!=NULL) printf(%c ,b-data); /*訪問根結(jié)點*/PreOrder(b-lchild);PreOrder