算法题目及答案.docx

1根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素。算法如下ListNode * Merge ( ListNode * L1, ListNode * L2 ) /根据两个带表头结点的有序单链表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设有一个线性表 (e0, e1, , en-2, en-1) 存放在一个一维数组Aarraysize中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (en-1, en-2, , e1, e0)。数组原地逆置算法参数表中给出数组A 及指定的数组中前n个元素，函数执行后从A 中得到数组原地逆置后的结果。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设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以从小到大的升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以从小到大的升序排列。合并两个升序排列的顺序表的算法参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。算法中用到顺序表的4个共有函数：Length( ) 求表的当前长度；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个结点的完全二叉树以顺序方式存储在数组A中，设计一个算法构造该二叉树的二叉链存储结构。算法如下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，统计在一个输入字符串中各个不同字符出现的频度。算法返回两个数组：A 记录字符串中有多少种不同的字符，C 记录每一种字符的出现次数。此外，还要返回不同字符数。求输入字符串中各种不同字符出现频度的算法由于需要返回多种信息，参数表中引入引用参数：A 中记录字符串中有多少种不同的字符，C 中记录每一种字符的出现次数，k返回不同字符数。#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已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。Int BTreeCount ( BinTreeNode* BT );算法如下int BTreeCount ( BinTreeNode* BT ) if ( BT = NULL ) return 0; else return BTreeCount ( BT-leftChild ) + BTreeCount ( BT-rightChild ) + 1;9已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。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已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出删除一棵二叉树中所有结点的算法，并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。Void ClearBinTree ( BinTreeNode*& BT);算法如下void ClearBinTree ( BinTreeNode*& BT ) if ( BT!=NULL )/ ClearBinTree ( BT-leftChild ); /递归删除左子树，ClearBinTree ( BT-rightChild ); /递归删除右子树， delete BT; /回收根结点，BT = NULL; /置根指针为空， 11已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出复制一棵二叉树的算法，并返回复制得到的二叉树的树根指针。算法中参数BT初始指向待复制二叉树的根结点。BinTreeNode* BTreeCopy ( BinTreeNode* BT );算法如下BinTreeNode* BtreeCopy ( BinTreeNode* BT )if ( BT = NULL ) return NULL;/1分else BinTreeNode* pt = new BinTreeNode; /得到新结点，pt-data = BT-data; /复制根结点值， pt-leftChild = BtreeCopy ( BT-leftChild ); /复制左子树， pt-rightChild = BTreeCopy ( BT-rightChild );/复制右子树， return pt; /返回新树的树根指针， 12已知二叉树中的结点类型用BinTreeNode表示，被定义为:struct BinTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出从一棵二叉树中求出结点值大于x的结点个数的算法，并返回所求结果。算法中参数BT初始指向二叉树的根结点。Int BTreeCount ( BinTreeNode* BT, ElemType x );算法如下/统计出二叉树中大于给定值x的结点个数，该统计值由函数返回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试编写函数用邻接表存储结构实现template int AdjTable :GetFirstNeighbor ( int v );/给出顶点位置为v 的第一个邻接顶点的位置，如果找不到，则函数返回-1算法实现如下template int AdjTable :GetFirstNeighbor ( int v ) /给出顶点位置为v 的第一个邻接顶点的位置，如果找不到，则函数返回-1if ( v != -1 )Edge *p = NodeTable (v).adj; if ( p != NULL ) return p-dest; return 1;14试编写函数用邻接表存储结构实现template int AdjTable :GetNextNeighbor ( int v, int w );给出顶点v的邻接顶点w的下一个邻接顶点的位置，若没有下一个邻接顶点，则函数返回-1算法实现如下template int AdjTable :GetNextNeighbor ( int v, int w ) /*给出顶点v的邻接顶点w的下一个邻接顶点的位置，若没有下一个邻接顶点，则函数返回-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的一维数组Rn 中保存着按关键码升序排列的n个对象，对象的关键码域key的类型为KeyType，试按照下面的函数声明编写一个非递归算法，从一维数组Rn中用折半搜索法找出关键码等于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 ) /循环条件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试设计一个算法，改造一个带表头结点的双向循环链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。算法如下void OrderedList ( DblNode * L ) /利用左链域llink把所有结点按照其值从小到大的顺序连接起来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编写一个程序实现直接插入排序算法。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; /*将关键字大于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编写一个程序实现冒泡排序算法。#include #define MaxSize 20typedef int KeyType; /*定义关键字类型*/typedef char InfoType10;typedef struct /*记录类型*/KeyType key; /*关键字项*/InfoType data; /*其他数据项,类型为InfoType*/ RecType;/*排序的记录类型定义*/void BubbleSort1(RecType R,int n)int i,j,k,exchange;RecType tmp;for (i=0;ii;j-)/*比较,找出最小关键字的记录*/if (Rj.keyRj-1.key)tmp=Rj; /*Rj与Rj-1进行交换,将最小关键字记录前移*/Rj=Rj-1;Rj-1=tmp;exchange=1;printf(i=%d: ,i);for (k=0;kadjlistv.firstarc; /*p指向顶点v的第一条弧的弧头结点*/while (p!=NULL) if (visitedp-adjvex=0)/*若p-adjvex顶点未访问,递归访问它*/DFS(G,p-adjvex); p=p-nextarc; /*p指向顶点v的下一条弧的弧头结点*/21编写算法实现图G的邻接矩阵的存储结构。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编写程序实现二叉树的先序、中序、后序遍历的递归算法。void PreOrder(BTNode *b) /*先序遍历的递归算法*/if (b!=NULL) printf(%c ,b-data); /*访问根结点*/PreOrder(b-lchild);PreOrder