一些算法真题选集,仅供参考,暂停更,开始手撕。
1. 统计出单链表HL中结点的值等于给定值X的结点数
int CountX(LNode *HL, ElementType X){ LNode *p; int count = 0; if(HL == NULL) return 0; p = HL->next; while(p != NULL){ if(p->data == X) ++count; p = p->next; } return count; }
2.设有一组初始记录关键字序列(K1,K2,… Kn),要求设计一个算法能够在 O(n) 的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于 Ki ,右半部分的每个关键字均大于等于 Ki
void quickpass(int r[], int s,int t) { int i=s, j=t, x=r[s]; while(i<j){ while (i<j &&r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]<x) i=i+1;if (i<j) {r[j]=r[i];j=j-1;} } r[i]=x; }
3. 设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示
typedef struct node { int data; struct node *next; }lklist; void intersection(lklist*ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) { if (q->data==p->data) break; } if(q!=0) { t=(lklist*)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t; } } }
4. 设计在单链表中删除值相同的多余结点的算法
typedef int datatype; typedef struct node { datatype data; struct node *front, *next; }lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head; p!=0; p=p->next) { for(q=p->next, s=q; q!=0;) { if(q->data==p->data) { s->next=q->next; free(q); q=s->next; }else{ s=q; q=q->next; } } } }
5. 设计一个求结点 x 在二叉树中的双亲结点算法
typedef struct node { datatype data; struct node *lchild,*rchild; } bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else { r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) { if (q[i]->lchild->data==x || q[i]->rchild->data) break; } if (flag==0) printf("not found x "); else if (i<=r) printf("%c",bt->data); else printf("not parent"); }
6. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符
typedef char datatype; typedef struct node { datatype data; struct node *next; }lklist; void split(lklist *head,lklist*&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha;ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } }
7. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法
typedef struct node { int data; struct node *lchild,*rchild; }Bitree; void swapbitree(Bitree *bt) { Bitree *p; if(bt==0) { return; } swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; }
8. 在链式存储结构上建立一颗二叉排序树
#define n10 typedef struct node { int key; struct node *lchild,*rchild; }bitree; void bstinsert(bitree *&bt,int key) { if (bt==0) { bt=(bitree*)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0; } else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); } void createbsttree(bitree *&bt) { int i; for(i=1;i<=n;i++)bstinsert(bt,random(100)); }
9. 设计判断两个二叉树是否相同的算法
typedef struct node { datatype data; struct node *lchild, *rchild; }bitree; //二叉链表存储结构 int judgebitree(bitree *bt1,bitree *bt2)//判断两个二叉树是否相同。 { if (bt1==0 && bt2==0)//两棵树对应位置都为空返回1 return 1; else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) //两棵树的当前节点只有一个为空或者两棵树的当前节点的值不同。 return 0; else return judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild); }
10. 设计两个有序单链表的合并排序算法
Typedef struct Lnode{ Datatype data; Struct Lnode *next; }Lnode,*linklist; void Merge_List(Linklist &la,linklist &b){ LNode *pa=la->next,*pb=lb->next,*r; //r指针防止断链 la->next=null; while(pa&&pb){ if(pa->data >= pb->data){ r=pa->next; pa->next=la->next; la->next=pa; pa=r; //pa重新指向未排序位置 } if(pa->data <= pb->data){ r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } if(pa) pb=pa; while(pb){ r=pb->next; pb->next=la->next; la->next=pb; pb=r; } free(lb); //释放掉lb的空闲空间 }
11. 设计在顺序有序表中实现二分(折半)查找的算法
struct record { int key; int others; }; int bisearch(struct record r[], int k) { int low=0, mid, high=n-1; while(low<=high) { mid=(low+high)/2; if(r[mid].key==k) { return (mid+1); } else if(r[mid].key>k) { high=mid-1; }else{ low=mid+1; } } return 0; }
12. 设计判断二叉树是否为二叉排序树的算法
//递归方式 KeyType predt=-32767; int JudgeBST(BisTree bt) { int b1, b2; if(bt==NULL) { return 1; }else{ b1=JudgeBST(bt->lchild); //递归 if(b1==0 || predt>=bt->data) return 0; predt=bt->data; b2=JudgeBST(bt->rchild); return b2; } } //非递归方式 int InOrderTraverse(BiTree T) { BiTree p; p=T; while(p||!StackEmpty(S)) { if(p) { Push(S,p); if(p->data>p->lchild->data) p=p->lchild; else return 0; } else { Pop(S,p); cout<<p->data<<" "; if(p->data<p->rchild->data) p=p->rchild; else return 0; } } return 1; }
13. 在链式存储结构上设计直接插入排序
void straightinsertsort(lklist *&head) { lklist *s,*p,*q; int t; if(head==0 || head->next==0) return ; else for(q=head, p=head->next; p!=0; p=q->next) { for(s=head; s!=q->next; s=s->next) { if(s->data > p->data) break; if(s==q->next) q=p; else{ q->next=p->next; p->next=s->next; s->next=p; t=p->data; p->data=s->data; s->data=t; } } } }
14. 设计在链式结构上实现简单选择排序
typedef struct LNode { int data; struct LNode *next }*Linklist; void simpleselectSort(Linklist *&head) { Linklist *p,*q,*s; int min,t; if(head==0 || head->next==0) { return; } for(q=head;q!=0;q=q->next) { min=q->data; s=q; for(p=q->next;p!=0;p=p->next) { if(min>p->data) { min=p->data; s=p; } } if(s!=q) { t=s->data; s->data=q->data; q->data=t; } } }
15.设计求结点在二叉排序树中层次的算法
int lev=0; typedef struct node { int key; struct node *lchild,*rchild; }bitree; void level(bitree *bt, int x) { if(bt!=0) { lev++; if(bt->key==x) { return; } else if(bt->key>x) { level(bt->lchild, x); } } else{ level(bt->rchild, x); } }
16. 设计一个在链式存储结构上统计二叉树中结点个数的算法
void countnode(bitree *bt,int &count) { if(bt!=0) { count++; countnode(bt->lchild,count); countnode(bt->rchild,count); } }
17. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法
typedef struct { int vertex[m]; int edge[m][m]; }gadjmatrix; typedef structnode1 { int info; int adjvertex; struct node1 *nextarc; }glinklistnode; typedef structnode2 { int vertexinfo; glinklistnode *firstarc; }glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) { int i,j;glinklistnode *p; for(i=0;i<=n-1;i++)g2[i].firstarc=0; for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++) if(g1.edge[i][j]==1) { p=(glinklistnode*)malloc(sizeof(glinklistnode)); p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode*)malloc(sizeof(glinklistnode)); p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } }
18. 设计计算二叉树中所有结点值之和的算法
void sum(bitree *bt,int &s) { if(bt!=0) { s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s); } }
19. 设计将所有奇数移到所有偶数之前的算法
void quickpass(int r[], int s, int t) { int i=s,j=t,x=r[s]; while(i<j) { while (i<j && r[j]%2==0) j=j-1; if (i<j) {r[i]=r[j];i=i+1;} while (i<j && r[i]%2==1) i=i+1; if (i<j) {r[j]=r[i];j=j-1;} } r[i]=x; }
20. 设计判断单链表中元素是否是递增的算法
int isriselk(lklist *head) { if(head==0||head->next==0)return(1); else for(q=head,p=head->next;p!=0; q=p,p=p->next) if(q->data>p->data) return(0); return(1); }
21. 设计在链式存储结构上合并排序的算法
void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data<hb->data) { if(s==0) hc=s=ha; else {s->next=ha; s=ha;}; ha=ha->next; } else { if(s==0) hc=s=hb; else {s->next=hb; s=hb;}; hb=hb->next; } if(ha==0) s->next=hb; else s->next=ha; }
22. 设计在二叉排序树上查找结点X的算法
bitree *bstsearch1(bitree *t, int key) { bitree *p=t; while(p!=0) if (p->key==key)return(p); else if (p->key>key) p=p->lchild; else p=p->rchild; return(0); }
23. 设关键字序列(k1,k2,…,kn-1)是堆,设计算法将关键字序列(k1,k2,…,kn-1,x)调整为堆
void adjustheap(int r[ ],int n) { int j=n,i=j/2,temp=r[j-1]; while (i>=1) if(temp>=r[i-1])break; else{ r[j-1]=r[i-1]; j=i; i=i/2; } r[j-1]=temp; }
24.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一个算法,求该二叉树中叶子结点的个数
int leaves(int h) //求深度为h以顺序结构存储的二叉树的叶子结点 { int BT[]; int len=2^h-1,count=0; for(int i=1;i<=len;i++) { if(BT[i]!=0) //假定二叉树结点值是整数,“虚结点”用0补充 { if((i*2)>len) count++; //第i个结点没有子女肯定是叶子结点 else if(BT[2*i]==0&&2*i+1<=len&&BT[2*i+1]==0) count++; //无左右子女结点为叶子 } } return count; }
25、建立二叉树
typedef struct node { int data; struct node *lchild; struct ndoe *rchild; }btree; void createbitree(bitree *&bt) { scanf("%c",&ch); if(ch=='#') bt=0; else { bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); } }
26、利用尾部插入的方法建立单链表
typedef struct node { int data; struct node *next; }lklist; void lklistcreate(lklist *&head) { for(i=1;i<=n;i++) { p=(lklist*)malloc(sizeof(lklist));scanf("%d",&(p->data));p->next=0; if(i==1) head=q=p; else{q->next=p;q=p;} } }
27、n个元素采用顺序存储,设计直接插入排序算法
void insertsort() { //a为顺序存储所需数组,n为元素个数 for(int i=1;i<n;i++) { int key=a[i]; int j=i-1; while(j>=0&&a[j]>key) { a[j+1]=a[j]; j--; } a[j+1]=key; } }
28、对含有n个互不相同元素的线性表,设计一个算法同时找最大元素和最小元素
void getMaxandMin(int A[],int n,int &max,int &min) //O(n) { int i; max=min=A[0]; for(i=0;i<n;i++) { if(A[i]>max) max=A[i]; if(A[i]<min) min=A[i]; } }
29、编写一个算法,完成对n叉树各节点的层次遍历
// 定义n叉树的节点结构体 typedef struct node_t { char* name; // 节点名 int n_children; // 子节点个数 int level; // 记录该节点在多叉树中的层数 struct node_t** children; // 指向其自身的子节点,children一个数组,该数组中的元素时node_t*指针 } NODE; // 对结构体重命名 // 将多叉树中的节点,按照深度进行输出,实质上实现的是层次优先遍历 void levelOrder(NODE* head) { NODE* p = NULL; QUEUE* q = NULL; // 定义一个队列 STACK* s = NULL; // 定义一个栈 int i = 0; q = QUEUEinit(100); // 将队列初始化大小为100 s = STACKinit(100); // 将栈初始化大小为100 head->level = 0; // 根节点的深度为0 // 将根节点入队列 QUEUEenqueue(q, head); // 对多叉树中的节点的深度值level进行赋值 // 采用层次优先遍历方法,借助于队列 while (QUEUEempty(q) == 0) // 如果队列q不为空 { QUEUEdequeue(q, &p); // 出队列 for (i = 0; i < p->n_children; ++i) { p->children[i]->level = p->level + 1; // 对子节点深度进行赋值:父节点深度加1 QUEUEenqueue(q, p->children[i]); // 将子节点入队列 } STACKpush(s, p); // 将p入栈 } while (STACKempty(s) == 0) // 不为空 { STACKpop(s, &p); // 弹栈 fprintf(stdout, " %d %s ", p->level, p->name); } QUEUEdestroy(q); // 消毁队列 STACKdestroy(s); // 消毁栈 }
29、设 h 是带表头结点的单链表的头指针,请设计一个逆置这个单链表的程序。
typedef struct node { int data; struct node *link }LNode; void invert(LNode *h) { LNode *s,*p; p=h->link; //p指针用于记录当前访问节点 h->link=NULL; //h置为NULL是为了重新建立一个逆序链表而准备的头节点 while(p!=NULL) { s=p; //s用于记录当前访问的节点 p=p->link; //p用于指向后面断开链表的第一个节点 s->link=h->link; //将s指向的节点插入到头节点后面 h->link=s; //将头节点指针指向第一个节点s } }
30、以二叉链表为二叉树的存储结构,写一算法计算叶子结点个数
typedef struct BiTNode { TDataType data; struct BiTNode *lchild,*rchild; }BiTree; void countLeaf(BiTNode *t,int &count) { if(t!=NULL) //不空的情况下 { if(t->lchild==NULL && t-rchild==NULL) { count++; countLeaf(t->lchild); countLeaf(t->rchild); } } }
31、设有一个带头结点的单链表h,数据项递减有序。写一算法,重新排列链表,使数据项递增有序,要求时间复杂度O(n)
//本质上是将单链表逆置,不同的问法罢了 typedef struct node { int data; struct node *link }LNode; void invert(LNode *h) { LNode *s,*p; p=h->link; //p指针用于记录当前访问节点 h->link=NULL; //h置为NULL是为了重新建立一个逆序链表而准备的头节点 while(p!=NULL) { s=p; //s用于记录当前访问的节点 p=p->link; //p用于指向后面断开链表的第一个节点 s->link=h->link; //将s指向的节点插入到头节点后面 h->link=s; //将头节点指针指向第一个节点s } }
32、设计二叉树先序、中序、后序遍历的递归算法
//先序 void preOrder(BTNode *b) { if(b!=NULL) { printf("%c",b->data); preOrder(b->lchild); preOrder(b->rchild); } } //中序 void inOrder(BTNode *b) { if(b!=NULL) { inOrder(b->lchild); printf("%c",b->data); inOrder(b->rchild); } } //后序 void postOrder(BTNode *b) { if(b!=NULL) { postOrder(b->lchild); postOrder(b->rchild); printf("%c",b->data); } }
33、设计二叉树先序、中序、后序遍历的非递归算法
//先序 void preOrder(BTNode *b) { BTNode *p; SqStack *st; //定义栈指针st InitStack(st); //初始化栈 if(b!=NULL) { Push(st,b); //根节点进栈 while(!StackEmpty(st)) //栈不为空时循环 { Pop(st,p); //退栈结点p并访问 printf("%c",p->data); if(p->rchild!=NULL) //有右孩子进栈 Push(st,p->rchild); if(p->lchild!=NULL) //有左孩子进栈 Push(st,p->lchild); } printf(" "); } DestroyStack(st); } //中序 void inOrder(BTNode *b) { BTNode *p; SqStack *st; InitStack(st); p=b; while(!SatckEmpty(st)||p!=NULL) { while(p!=NULL) //扫描结点p的所有左下结点并进栈 { Push(st,p); //结点p进栈 p=p->lchild; //移动到左孩子 } if(!StackEmpty(st)) { Pop(st,p); //出栈结点p printf("%c",p->data); //访问结点p p=p->rchild; //转向处理其右子树 } } printf(" "); DestroyStack(st); } //后序 void postOrder(BTNode *b) { BTNode *p,*r; bool flag; SqStack *st; InitStack(st); p=b; do { while(p!=NULL) //扫描结点p的所有左下结点并进栈 { Push(st,p); //结点p进栈 p=p->lchild; //移动到左孩子 } r=NULL; //r指向刚访问的结点,初始时为空 flag=true; //flag为真表示正在处理栈顶结点 while(!StackEmpty(st)&&flag) { GetTop(st,p); //取出当前栈顶结点p if(p->rchild==r) //若结点p的右孩子为空或为刚刚访问过的结点 { printf("%c",p->data); //访问结点p Pop(st,p); r=p; //r指向刚访问过的结点 } else { p=p->rchild; //转向处理其右子树 flag=false; //表示当前不是处理栈顶结点 } } }while(!StackEmpty(st)); //栈不空循环 printf(" "); DestroyStack(st); }
34、设计二叉树的层序遍历
void levelOrder(BTNode *b) { BTNode *p; SqQuene *qu; InitQueue(qu); enQuenu(qu,b); //根节点指针进入队列 while(!QueueEmpty(qu)) //队不为空循环 { deQueue(qu,p); //出队结点p printf("%c",p->data); //访问结点p if(p->lchild!=NULL) //有左孩子时将其进队 enQueue(qu,p->lchild); if(p->rchild!=NULL) //有右孩子时将其进队 enQueue(qu,p->rchild); } }
35、线性表的插入和删除操作
typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; //插入 Status insert(LinkList &L,int i,ElemType e) { p=L; j=0; while(p&&j<i-1); { p=p->next; ++j; } if(!p||j>i-1) { return ERROR; } s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return OK; } //删除 Status delete(LinkList &L,int i,ElemType &e) { p=L; j=0; while(p->next&&j<i-1) { p=p->next; ++j; } if(p->next||j>i-1) return ERROR; q=p->next; p->next=q->next; e=q->data; free(q); return OK; }