2022年数据结构算法设计答案 .pdf
1. 有一个有序单链表（从小到大排列） ，表头指针为head，设计一个算法向该单链表中插入一个元素为x 的结点，插入后使该链仍然有序。先建立一个待插入的结点，然后依次与链表中的各结点数据域比较大小，找到插入该结点的位置，最后插入该结点。 Void insnode(SNode *&head,ElemType x) SNode *s,*p,*q; s=( SNode *)malloc(sizeof(SNode);/ 建立一个待插入的结点s-data=x;s-next=NULL; if(head=NULL|xdata)/若单链表为空或小于第一个结点 data s-next=head; /则把 s 结点插入到表头后面 Head=s; Else q=head;/寻找插入位置， p 指向待比较的结点， q 指向 p 的前驱 p=q-next; while(p!=NULL&xp-data)/若 x 小于 p 所指结点的 data 域 q=p; p=p-next; s-next=p;/将 s 插入q-next=s; 2. 有一个循环双链表，每个结点有两个指针（prior和 next ）及关键字（data ）构成， p 指向其中某一点，设计一个算法从该链表中删除p 所指的结点。假设是不带头节点的循环双链表。*p 结点的前驱和后继分别由p-prior和 p-next 指向。Void delnode(DNode *&p) DNode *q; If(p-prior=p)/只有一个结点 free(q); p=NULL; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 9 页 - - - - - - - - - Else p-prior-next=p-next;/ 将 *p 前驱的 next 指向 *p 的后继p- next - prior =p- prior;/ 将 *p 后继的 prior指向 *p 的前驱q=p; p=p-prior; free(q); 3. 有两个栈三 s1 和 s2 共享存储空间 c1.MaxSize,其中一个栈底设在c1处，另一个设在 cMaxSize 处，分别编写 s1、s2 的进栈 push（i ，x） 、退栈 pop（i ）和设置栈空 setnull（i ）的函数，其中i=1 ，2. 注意：仅当整个空间占满时，才产生上溢。top1、top2 分别是栈 1、栈 2 的栈指针，当 top2=top1+1 时上溢，当 top1=0时栈 1 下溢，当 top2=MaxSize+1 时栈 2 下溢。算法如下：Int push （ElemType x, int i） If(top1=top2-1)/上溢出Return 0; Else if(i=1)/对第一个栈进行进栈操作 Top1+; Ctop1=x; Else /对第二个栈进行进栈操作 Top2+; Ctop2=x; Return 1; Int pop(int I,ElemType &x) If(i=1)/ 对第一个栈进行出栈操作 If(top1=0)/栈 1 下溢Return 0; Else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 9 页 - - - - - - - - - X=ctop1; Top1-; Else / 对第二个栈进行出栈操作 If(top2= MaxSize+1)/栈 2 下溢Return 0; Else X=ctop2; Top2+; Return 1; Void setnull(int i) If(i=1) Top1=0; Else Top2=MaxSize+1; 4. 假定用一个循环单链表表示队列（称为循环连队），该队列只设一个队尾指针rear ，不设队头指针，设计如下算法：（1） 向循环链队中插入一个元素为x 的结点。（2） 从循环连队中删除一个结点。定义本题队列的类型如下：Typedef struct Snode *rear; QType2; (1) 队列插入一个结点的操作是在队尾进行的，所以应在尾部插入一个结点EnQueue(QTtpe *&qu,ElemType x) SNode *s; s=( SNode *)malloc(sizeof(SNode);/建立一个新节点s-data=x; if （qu-rear=NULL）/ 若队列为空，则建立一个只有头节点的队列 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 9 页 - - - - - - - - - qu-rear=s; qu-rear-next=s; else /对列不为空，将 *s 插入后面 s-next=qu-rear-next; qu-rear-next=s; qu-rear=s; (2) 队列的删除节点是在队头进行的，所以应删除队列的第一个节点int DeQueue(QType *&qu,ElemType &x) SNode *p; if(qu-rear=NULL)/队列下溢出return 0; else p=qu-rear-next; x=p-data; if(p=qu-rear)/队列只有一个节点，删除qu-rear=NULL; else qu-rear-next=p-next;/否则删除第一个节点free(q);/释放对头节点return 1; 5. 试编写算法， 以一为数组作存储结构， 实现线性表的就地逆置， 即在原表的存储空间内将线性表（ a0,a1, an-1）逆置为（ an-1,a1,a0 ）. 扫描 A的前一半数组元素，将Ai 与 An-i-1交换。 void reverse(ElemType A,int n) int i; ElemType tmp; for(i=0;i0)/非 0 矩阵才做转置 q=1; for(col=0;coln;col+)/按列转置for(p=1;p-1) p=Sttop; top-; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 9 页 - - - - - - - - - printf(%c,p-data); if(p-rchild!=NULL) top+; Sttop=p-rchild; if(p-lchild!=NUll) top+; Sttop=p-lchild; 8. 设计一个算法判断一颗二叉树是否为完全树。满足：某节点没左孩子，一定没右孩子；若某节点无左孩子或右孩子，则其后继一定无孩子#define Max 100 int fullbtreel(BTree *b) BTree *QuMax,*p; int first=0,rear=0,bj=1,cm=1; if(b!=NULL) rear+; Qurear=b; while(first!=rear) first+; p=Qufirst; if(p-lchild=NULL) bj=0; if(p-rchild!=NULL) cm=0; else cm=bj; rear+; Qurear=p-lchild; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 9 页 - - - - - - - - - if(p-rchild=NULL) bj=0; else rear+; Qurear=p-rchild; return cm; return 1; 算法二：#define Max 100 typedef char SbtreeMaxNum; int fullbtree2(Sbtree A,int n) int i; for(i=0;i=n;i+) if(Ai= ) return 0; return 1; 9. 假设图用邻接矩阵表示， 设计一个算法， 输出从定点 vi 到 vj 的所有简单路径。算法如下：int visitedMAXVERX; int pMAXVERX; void path(AdjMaxix adj,int i,int j,int k) int s; if(pk=j) for(s=0;s=k;s+) printf(%d,ps); printf(n); else s=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 9 页 - - - - - - - - - while(sadj.n) if(adj.edgespks=1&visiteds=0) visiteds=1; pk+1=s; path(adj,i,j,k+1); visiteds=0; s+; void disppath(AdjMaxix adj,int i,int j) int k; p0=i; for(k=0;kMAXVEX;k+) visitedi=0; path(adj,i,j,0); 10. 设计一个算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。算法如下：void bininsert(sqlist r,int x,int n) int low=0,high=n-1,mid,inplace,i,find=0; while(low=high&!find) mid=(low+high)/2; if(xrmid.key)low=mid+1; else i=mid; find=1; if(find) inplace=mid; else inplace=low; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 9 页 - - - - - - - - - for(i=n;i=inplace;i-) ri+1.key=ri.key; rinplace.key=x; 11. 设计一个算法，修改冒泡排序过程以实现双向冒泡排序。算法如下：void dbubble(sqlist r) int j,i=1,b=1; struct rec t; while(b) b=0; for(j=n-i+1;j=i+1;j-) if(rj.keyrj-1.key) b=1; t=rj; rj=rj-1; rj-1=t; for(j=i+1;jrj+1.key) b=1; t=rj; rj=rj+1; rj+1=t; i+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 9 页 - - - - - - - - -
