数据结构题目

《数据结构题目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半 部分的每个关键字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(ix)j=j-1;if(i

2、[i]=x;}设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){he

3、ad=p->next;p->next=0;if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;}elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;}} }?7.已知由一个线性链表表示的线性表中含有3类字符的数据元素（如，字母、数字和其他字符），试编写算法将该线性表分割为3个循环链表，其中每个循环链表表示的线 性表中均只含一类字符?StatusLinkList_Divide(L

4、inkListL,CiList&A,CiList&B,CiList&C)?//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型?{s=L->next;?A=(CiList*)malloc(sizeof(CiLNode));p=A; ?B=(CiList*)malloc(sizeof(CiLNode));q=B; ?C=(CiList*)malloc(sizeof(CiLNode));r=C; ?//建立头结点??while(s){if(‘a’<=s->data&&s->data<=

5、‘z’

6、

7、 ?‘A’<=s->data&&s->data<=‘Z’) ?{p->next=s;p=s;}　elseif(‘0’<=s->data&&s->data<=‘9’)?{q->next=s;q=s;}　else{r->next=s;r=s;}?s=s->next;}//while　p->next=A;q->next=B;r->next=C; ?//完成循环链表?}//LinkList_Divide6、写一个利用层次遍历方法遍历任意一棵用二叉链表存储的二叉树的算法。算法思想：设存储于二叉链表的二叉树T，并

8、设置循环队列Q。若T非空则根结点进队。从T的根结点开始，反复做：当队列非空，则出队访问该结点*p。若*p有左子树，则*p的左子结点进队，若*p有右子树，则*p的右子结点进队。算法：设置指针变量p指向当前处理的结点，Q为循环队列。voidlever(BrTreeT){SQueueQ;if(T)EnQueue(Q,T);//T不空，则根结点进队p=T;while(!Empty(Q)){//当Q不空反复做下列操作 DeQueue(Q,p);//队首元素出队存于pprintf(*p);//访问结点*pif(p->lli

9、nk)EnQueue(Q,p->llink);//若*p有左子树，则*p的左子结点进队if(p->rlink)EnQueue(Q,p->rlink);//若*p有右子树，则*p的右子结点进队}}试写一个算法，在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的、长度为k的路径数。数据结构如下typedefintVRType;typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型，对无权图，用1或0表示相邻否；对带权图，则为权值类型InfoType*info;//该弧

10、相关信息的指针}ArcCell,**AdjMatrix;typedefstruct{VertexType*vexs;//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数}MGraph;2、设有5个数据do,for,if,repeat,while排在一个有序表中，其查找概率分别为p1=0.2,p2 =0.15,p3=0.1,p4=