数据结构题目

1、数据结构题目,设有一组初始记录关键字序列( K1,K2,，Kn),要求设计一个算法能够在 O(n)的时间复杂度内将线性 表划分成两部分，其中左半部分的每个关键字均小于 Ki,右半部分的 每个关键字均大于等于Ki。void quickpass(int r, int s, int t)(int i=s, j=t, x=rs;while(i<j)while (i<j && rj>x) j=j-1; if (i<j) ri=rj;i=i+1;while (i<j &&

2、ri<x) i=i+1; if (i<j) rj=ri;j=j-1; ri=x;设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)， 要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) (lklist

3、*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&am

4、p;lt;='9') p->next=hb; hb=p; elsep->next=hc; hc=p;? 7.已知由一个线性链表表示的线性表中含有3类字符的数据元素(如，字母、数字和其他字符)，试编写算法将该线性表分割为 3个循环链表，其中每个循环链表表示的线性表中均只含一类字符? Status LinkList_Divide ( LinkList L, CiList &A,CiList &B,CiList &C)? 把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链

5、表类型? 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 <= 'z' |?'A' <=s->data&&a

6、mp;amp; s->data<= 2 )? p->next=s;p=s; else if( '0' <=s->data && s->data <= '9' )? q->next=s; q=s;else r->next=s; r=s;?s=s->next; /whilep->next=A;q->next=B;r->next=C;?/完成循环链表? Li

7、nkList_Divide6、写一个利用层次遍历方法遍历任意一棵用二叉链表存储的二叉树 的算法。算法思想：设存储于二叉链表的二叉树T,并设置循环队列Q。若T非空则根结点进队。从T的根结点开始，反复做：当队列非空，则出 队访问该结点*p。若*p有左子树，则*p的左子结点进队，若*p有右 子树，则*p的右子结点进队。算法：设置指针变量p指向当前处理的结点，Q为循环队列。void lever( BrTree T)SQueue Q;if(T) EnQueue(Q, T); /T不空，则根结点进队p=T;while(!Empty(Q) 当Q不空反复做下列操作DeQueue(Q, p); /队首元素出队存

8、于pprintf(*p); / 访问结点 *pif (p->llink) EnQueue(Q,p->llink); 若*p 有左子树，贝U *p 的左子 结点进队if (p->rlink) EnQueue(Q,p->rlink);/ 若*p有右子树，则*p的右子结点进队试写一个算法，在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的、长度为k的路径数。数据结构如下typedef int VRType;typedef struct ArcCell(VRType adj;/VRType是顶点关系类型，对无权图，用1或0表示相邻否；对

9、带权图，则为权值类型InfoType *info;/该弧相关信息的指针ArcCell,*AdjMatrix;typedef struct(VertexType *vexs;/ 顶点向量AdjMatrix arcs;/ 邻接矩阵int vexnum,arcnum;图的当前顶点数和弧数MGraph;2、设有5个数据do,for,if,repeat,while排在一个有序表中，其查找概率分别为 p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01而查找它们之间不存 在 数 据 的 概 率 分 别 为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5

10、=0.01doforifrepeat whileq0 p1 q1 p2 q2 p3 q3 p4 q4 p5q5(1)试分别画出对该有序表采用顺序查找和折半查找时的判定树(2)分别计算顺序查找和折半查找时查找成功和不成功的平均概率。图鉴原图?顺序查找成功的平均概率：(0.2x 1+0.15X 2+0.1 x 3+0.03X 4+0.01 X 5) /(1+2+3+4+5)=0.97/15=0.06失败的平均概率：(0.2X 1+0.15X 2+0.1 x 3+0.03X 4+0.02X 5+0.01 X 5)/(1+2+3+4+5+5)= 1.07/20=0.05?折半查找成功的平均概率：(0.

11、2X 2+0.15X 3+0.1 x 1+0.03X 2+0.01X3) /(1+2+2+3+3)=1.04/11=0.09失败的平均概率：(0.2X 2+0.15X 3+0.1 x 3+0.03X 2+0.02X 3+0.01 X 3) /(2+2+3+3+3+3) =1.30/16=0.081、应用直接插入排序算法，对键值序列49, 38, 65, 97, 76, 13,27, 59从小到大进行排序，试写出每趟排序的结果。解：第一趟：38,49,65,97,76,13,27,59第二趟：38,49,65,97,76,13,27,59第三趟：38,49,65,97,76,13,27,59第四

12、趟：38,49,65,76,97,13,27,59第五趟：13,38,49,65,76,97,27,59第六趟：13,27,38,49,65,76,97,59第七趟：13,27,38,49,59,65,76,972、设待排序记录的关键字分别为28, 13, 72, 85, 39, 41, 6, 20按二分法插入排序已使前七个记录有序，中间结果如下:613283941728520?1 =1m=4r=7试在此基础上，沿用上述表达方式，给出继续采用二分法插入第8个 记录的比较过程。解：(6132839417285 )20?l =1m=4r=7(6132839417285 )20?l =1m=2r=3

13、(6132839417285 )20?l =3m=3r=3(6132839417285 )20r=2l=33、有一随机数序列25, 84, 21, 46, 13, 27, 68, 35, 20,现采用某种方法对它们进行排序，其每趟排序的结果如下，该排序方法是 什么？初 始：25,84,21,46,13,27,68,35,20第一趟：20,13,21,25,46,27,68,35,84第二趟：13,20,21,25,35,27,46,68,84第三趟：13,20,21,25,27,35,46,68,84答：是快速排序4、若对序列(tang,deng,an, wan, shi, bai, fang

14、, liu)按字典顺序进行排序，分别给出：(1)冒泡排序第一趟的结果(2)初始步长为4的希尔排序第一趟的结果(3)以第一个元素为分界元素的快速排序第一趟的结果(4)堆排序的初始堆解：(1) deng an tang shi bai fang liu wan2 2) shi bai an liu tang deng fang wan(3)( liu deng an fang shi bai ) tang (wan)(4)an deng bai liu shi tang fang wan5、给出关键字序列29,18,25,47,58,12,51,10汾别写出按下列各种排序方法进行排序时的变化过程(

15、1)归并排序：每归并一次写一个序列(2)快速排序：每划分一次写一个序列(3)堆排序：先建成一个堆，然后每次从堆顶取下一个元素后将堆调整一次(4)基数排序的分配和收集过程解：(1)归并初始：29,18,25,47,58,12,51,10第一趟归并：18,29,25,47,12,58,10,51第二趟归并：18,25,29,47,10,12,51,58第三趟归并：10,12,18,25,29,47,51,58(2)快速初始：29,18,25,47,58,12,51,10第一趟：10,18,25,12,29,58,51,47x:29第二趟：10,18,25,12,29,47,51,58x:10和58

16、第三趟：10,12,18,25,29,47,51,58x:18和47(3)堆(最小)初始：29,18,25,47,58,12,51,10建堆：10,18,12,29,58,25,51,47取堆顶 10,调整：12,18,25,29,58,47,51,10取堆顶 12,调整：18,29,25,51,58,47,12,10取堆顶 18,调整：25,29,47,51,58,18,12,10取堆顶 25,调整：29,51,47,58,25,18,12,10取堆顶 29,调整：47,51,58,29,25,18,12,10取堆顶 47,调整：51,58,47,29,25,18,12,10取堆顶 51,调

17、整：58,51,47,29,25,18,12,10取堆顶 58:58,51,47,29,25,18,12,10(3)堆(最大)初始：29,18,25,47,58,12,51,10建堆：58,47,51,29,18,12,25,10取堆顶 58,调整：51,47,25,29,18,12,10,58取堆顶 51,调整：47,29,25,10,18,12,51,58取堆顶 47,调整：29,18,25,10,12,47,51,58取堆顶 29,调整：25,18,12,10,29,47,51,58取堆顶 25,调整：18,10,12,25,29,47,51,58取堆顶 18,调整：12,10,18,2

18、5,29,47,51,58取堆顶 12,调整：10,12,18,25,29,47,51,58(4)基数初始：29,18,25,47,58,12,51,10第一趟分配：队列01234567891051122547182958第一趟收集：10, 51, 12, 25, 47, 18, 58, 29第二趟分配：队列012347891025475112295818第二趟收集：10, 12, 18, 25, 29, 47, 51,58二叉树先序遍历算法如下:void Preorder (BiTree T,void( *visit)(TElemType& e) /先序遍历二叉树if (T) if(visit(T->data);/ 访问结点if(Preorder(T->lchild, visit); / 遍历左子树 if(Preorder(T->rchild, visit);/ 遍历右子树 return error;else return ok;已知n为大于等于零的整数，试写出技术下列递归函数f(n)的递归和非递归算法#include <stdio.h>递归：int