2022年数据结构常用算法 .pdf

《2022年数据结构常用算法 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构常用算法 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 专升本考试计算机专业数据结构算法专题1设计一个算法，计算单链表中数据域值为x 的结点个数。逐个查找单链表中的结点x，并计数。int number(lnode*h,int x)int n=0；while(h)if(h-data=x)n+；h=h-next；return s；2设计一个用前插法建立带表头结点的单链表的算法。前插法建立带表头结点的单链表算法中的tag 为输人数据结束标志。Lnode*createhh(int tag)int x；Lnode*p，*h=(Lnode*)malloc(sizeof(Lnode)；h-next=NULL；printf(input x:)；scanf(%d

2、,&x);while(x!=tag)p=(Lnode*)malloc(sizeof(Lnode);p-data=x;p-next=h-next;h-next=p;scanf(%d,&x);return h;3解本题的基本思想是：先将顺序队列q 中所有元素出队，并依次进入顺序栈s 中，然后出栈，再依次入队。设队列中的元素为a1,a2,an，出队并进栈的序列为a1，a2，,，an，出栈并入队的序列为an，an-1，,，a1，可见顺序队列q 中所有元素已逆置了。顺序队列的类型定义为：#define MAX 100 typedef struct int dataMAX；int front,rear；S

3、queue；算法描述如下：void invert(Squeue*q)int sMAX,top=0;while(q-frontrear)stop+=q-data+q-front;q-front=-1;q-rear=0;while(top0)q-dataq-rear+=s-top;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 11 页 -2 4利用栈实现将十进制数x 转换成二进制数并输出结果。Void BNumber（int x）算法设计题：1.设计算法将一个带头结点的单循环链表A 分解为两个具有相同结构的链表B、C，其中：B 表中的结点为A 表中元素的顺序号为奇数的结点，而C 表

4、中的结点为A 表中元素的顺序号为偶数的结点。（要求利用原表结点。）2.已知S 为顺序栈。写出S 的存储结构类型描述。试编写算法实现将元素x 插入栈S 的入栈操作Push(S,x)和删除栈顶元素的出栈操作Pop(S)。3.已知队列Q 以循环队列存储。写出Q 的存储结构类型描述，并试编写算法实现将元素x 插入队列Q 的入队操作EnQueue(Q,x)和从队列Q 中获取队首元素的函数GetTop(Q)。4.假设线性表L=(a1,a2,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,a2,a1)。5.设有两个按升序排列的单

5、链表X 和 Y，其头指针分别为p,q 结点结构说明如下：typedef struct nodel int data;struct nodel*next node;试设计一个算法void concat(node*p,*q)将它们合并成一个以p 为头指针的单链表Z，使其仍然有序。6.设有序表r 长度为 n，欲在表中查找键值为Kn 的某元素。若查找成功，则返回该元素在有序表r 中的位置，若不成功，则返回0 值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下Typedef struct keytype key;Elemtype data;rec;Typede

6、f struct rec itemmaxsize+1;int n;sqtable;7、利用表达式的逆波兰式计算表达式的值。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 11 页 -3 提示：设栈S，顺序读表达式的逆波兰式，读一个操作数则入栈，读一个操作符则弹栈2 次，并计算此操作，将结果重新入栈。数据结构算法2003 年真题设计求二叉树深度的算法。int BTreeDepth(btree*b)int leftdep,rightdep;if(t=NULL)return 0;else leftdep=BTreeDepth(b-left);rightdep=BTreeDepth(b-

7、right);if(leftdeprightdep)return leftdep+1;else return rightdep+1;2005 年真题1、二叉树采用连接存储结构，试设计一个算法计算一棵给定二叉树的单孩子结点数。（只写算法函数）（11 分）int onechild(btree*b)btree*t=b;if(t=NULL)return 0;else if(t-lchild=NULL&t-rchild!=NULL|t-lchild!=NULL&t-rchild=NULL)return onechild(t-lchild)+onechild(t-rchild)+1;else return

8、 onechild(t-lchild)+onechild(t-rchild);2、已知线性表中的元素以值递增有序排列，并以单链表作为存储结构，试编写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删除结点空间，并分析你的算法的时间复杂度（10 分）void Delete_Equal(LNode*head)/时间复杂度O(n2)int x;LNode*q,*t,*p;p=head-next;while(p!=NULL)x=p-data;q=p;while(q-next!=NULL)if(x=q-next-data)名师资料总结-精品资料欢迎下载-

9、名师精心整理-第 3 页，共 11 页 -4 t=q-next;q-next=t-next;free(t);else q=q-next;p=p-next;void delinfo(LNode*h)/时间复杂度O(n)struct LNode*t,*p,*q;p=h-next;/删除重复元素t=p;while(t-next!=NULL)if(t-data=t-next-data)q=t-next;t-next=q-next;free(q);else t=t-next;void delinfo2(LNode*h)/时间复杂度O(n)LNode*p,*q;p=h-next;if(p=NULL)ret

10、urn;while(p-next!=NULL)if(p-data=p-next-data)q=p-next;p-next=p-next-next;free(q);else 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 11 页 -5 p=p-next;void fun(LNode*h)/时间复杂度O(n)LNode*p,*q;p=h-next;while(p!=NULL&p-next!=NULL)q=p-next;if(p-data!=q-data)p=p-next;else p-next=q-next;free(q);2007 年真题试编写一个在带头结点的双向循环链表中值为x

11、 的结点之前，插入值为y 的结点的算法。（要求：用 C 语言描述，结点类型定义为DlinkList）Status InsertPrior-L(DlinkList*L,int x,int y)/x之前插入 y 结点 DNode*s,*p;p=L-next;while(p!=L&p-data!=x)p=p-next;if(p!=L)s=(DNode*)malloc(sizeof(DNode);s-data=y;s-next=p;s-prior=p-prior;p-prior-next=s;p-prior=s;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 11 页 -6 2009 年

12、真题程序填空题：单链表中，无序单链表转化为有序单链表（10 分）void sort3(LNode*L)/无序链表排序，利用单链表就地逆置的思想 LNode*p,*q,*s;/s保存新摘结点，p 保存原有链表，q 在新链表中找位置if(L-next=NULL)return;p=L-next-next;/从第二个结点开始L-next-next=NULL;while(p!=NULL)s=p;p=p-next;/p 保存原有链表q=L;while(q-next!=NULL&s-dataq-next-data)/查找插入位置q=q-next;s-next=q-next;/插入结点q-next=s;voi

13、d sort4(LNode*L)/无序链表排序，利用直接选择排序思想 LNode*p,*q,*s;/p控制外层循环，q 保存最小结点，s 找位置int x;if(L-next=NULL)return;p=L-next;/第一个结点while(p!=NULL)q=p;/假设当前结点值是最小的s=p-next;/从第二个结点开始while(s!=NULL)/循环找最小的结点，由q 指向 if(s-datadata)q=s;s=s-next;x=p-data;/交换两个结点的数据域p-data=q-data;q-data=x;p=p-next;/下一个结点 /直接选择排序是每次从n-i+1 个结点中

14、选择码值最小者，与第i 个结点的码值进行交换，设p 指向第 i 个结点，/min 指向无序表中码值最小的结点，算法描述如下：void selesort1(Lnode*h)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 11 页 -7 Lnode*p,*q,*min;int x;p=h-next;while(p)min=p;q=p-next;while(q)if(q-keykey)m=q;q=q-next;if(min!=p)x=p-key;p-key=min-key;min-key=x;p=p-next;模拟二设 n 个整数存于数组x 中，写一算法将所有偶数移到奇数之前，要求时间

15、复杂度为O(n)。void change(int a,int n)int i=1,j=n;while(i=j)if(i%2=0)i+;else if(j%2!=0)j-;else a0=ai;ai=aj;aj=a0;i+;j-;模拟三1冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。void BubbleSort2(int a,int n)/相邻两趟向相反方向起泡的冒泡排序算法 int i,t,change,low,high;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 11 页 -8 change=1;

16、/有交换low=0;high=n;/冒泡的上下界while(lowhigh&change)change=0;/设不发生交换for(i=low;iai+1)t=ai;ai=ai+1;ai+1=t;change=1;/有交换，修改标志change high-;/修改上界for(i=high;ilow;i-)/从下向上起泡if(aiai-1)t=ai;ai=ai-1;ai-1=t;change=1;low+;/修改下界/while/BubbleSort2 模拟四1.设 n 个元素的线性表顺序存储在一维数组st1.maxlen的前 n 个位置上,试将新元素e 插入表中第i-1个和第i 个元素之间,写出

17、算法。void insert(ElemType st,ElemType e,int i,int n)/插入表元素 int j;if(n=maxlen)printf(数组已满,不能进行插入操作!n);return;if(in+1)printf(位置参数不正确,不能进行插入操作!n);return;n+;for(j=n;ji;j-)/*结点向后移动，腾出一个位置*/stj=stj-1;stj=e;2.设 Head 为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data 值)；否则输出:”Empty list！”。Void disp(LNode*Head)LNode

18、*p=Head;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 11 页 -9 If(p-next=NULL)Printf(“Empty list!”);Else Printf(“%c”,p-next-data);While(p-next!=NULL)P=p-next;Printf(“%c”,p-data);模拟五1.已知 S 为顺序栈。写出 S 的存储结构类型描述。试编写算法实现将元素 x 插入栈 S 的入栈操作 Push(S,x)和删除栈顶元素的出栈操作 Pop(S)。#define Max 50 typedef char ElemType;typedef struct St

19、ack ElemType stackMax;int top;SqStack;void initStack(SqStack*s)s-top=-1;void push(SqStack*s,ElemType x)if(s-top=Max-1)printf(栈上溢！);exit(0);s-top+;s-stacks-top=x;void pop(SqStack*s)if(s-top=-1)printf(空栈！n);return;s-top-;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 11 页 -10 2.假设线性表L=(a1,a2,an)用带头结点的单链表存储表示，试编写算法对其实

20、现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,a2,a1)。struct lNode int data;struct lNode*next;void lreserve1(struct lNode*head)struct lNode*p,*newhead=NULL,*s;p=head-next;while(p!=NULL)/*辅助空间为 2个*/s=p;p=p-next;s-next=newhead;newhead=s;head-next=newhead;void lreserve2(struct lNode*head)struct lNode*p,*newhea

21、d=NULL;p=head-next;while(p!=NULL)/辅助空间为 1个 head-next=p-next;p-next=newhead;newhead=p;p=head-next;head-next=newhead;模拟六设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置不变。（11 分）例如，原有字符串为：AbcDEfghiJKlmn 输出序列为：ADEJKbcfghilmn#include void change(char ch)int i,j;char t;i=0;while(chi!=0)if(chi=97)/小写，不移动i+；else/大写 t=chi;/大写字母暂存名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 11 页 -11 j=i-1;while(j=0&chj=97)/蒋大写字符前的小写字符后移 chj+1=chj;j-;chj+1=t;/找到大写字母的位置i+;名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 11 页 -