数据结构算法设计题复习题Word文件下载.doc

1、 （2）写一个调用上述函数实现下列功能的算法：对一整型数组bn中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（1）该函数的功能是：调整整数数组a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x的元素均落在ai1.h上。 （2）int f（int b,int n） 或 int f（int b,int n） int p,q； int p,q； p=arrange（b,0,n1,0）； p=arrange（b,0,n1,1）； q= arrange（b,p+1,n1,1）； q= arra

2、nge（b,0,p,0）； return qp； return pq； 3. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。void algo1（LNode *h,int k,ElemType y）q=h; P=h-next; j=1;while（ p!=h & j j+;s=（LNode *）malloc（sizeof（Lnode）;s-data=y;q-next=s;next=q; 4. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct

3、 BSTNode *lchild, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。int f34（BSTree root） int count; BSTNode *p; p=root; if （ p & p-data return count;5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左至右次序编号）BTNode * Firstleaf（BTNode *bt） InitQueue（Q）; /初始化队列Q if（bt） EnQueue（Q,bt）; whi

4、le（!EmptyQueue（Q） DeQueue（Q,p）; if（!p-lchild & !rchild） return p; if（p-lchild） EnQueue（Q,p-rchild） EnQueue（Q,p- 6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和孩子结点。 int algo2（char bt,int n,int k） if （kn） return 0;if（ k=1） printf（“ %c is a rootn”, bt1）;else printf（“ %cs parent is %cn”, btk,

5、 btk/2）; if（2*k=n） printf（“ %cs lchild is %cn”, btk, bt2*k）; else printf（“ %c is not lchildn”, btk）; if（2*k+1=n） printf（“ %cs rchild is %cn”, btk, bt2*k+1）;else printf（“ %c is not rchildn”, btk）;return 1;7. 编写算法，将非空单链表hb插入到单链表ha的第i（0i表长）个结点前。int algo1（LNode *ha, LNode *hb,int i） for（p=hb;next）; for（

6、j=1,q=ha;j p-next=q- q-next=hb-next ； free（hb）;8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构。顺序表T定义如下：struct tree int no; /* 结点按完全二叉树的编号*/ ElEMTP data; /* 数据域 */ TN; /* N为二叉树T的结点数*/ BTNode *creat_tree（struct tree TN） BTNode *pMAX; t=NULL; for（i=0;idata=Ti.data; lchild=s-rchild=NULL; m=Ti.no; p

7、m=s; if（m=1） t=s; else j=m/2; if（m%2=0） pj-lchild=s; else pj-rchild=s; /slse /for return t; / creat_tree9. 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。int algo1 （LNode *L） if（!L-next） return 1; p=L- while（p-next） if（p-data next-data） p=p- else return 0; return 1;10. 假设一线性表由Fibonacci数列的前n（n3）项构成，试以带表头结点的单链表作

8、该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得： 1 （n=1） f（n）= 1 （n=2） f（n-2）+f（n-1） （n3） LNode * Creatlist（LNode *h,int n） h=（LNode *）malloc（sizeof（Lnode）; h-data=n;next=p=（LNode *）malloc（sizeof（Lnode）; p-next=q=（LNode *）malloc（sizeof（Lnode）;data= q-data=1; for（i=3;=n; q-next=s=（LNode *）malloc

9、（sizeof（Lnode）; s-data=p-data+q-data; s-next=NULL; p=q;q=s; return h;11. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。 void algo2（BTNode *bt） if（bt-data=a& bt-=z） bt-data-=32;12. 假设线性表以带表头结点的循环单链表表示。void Insertlist（LNode *h,int k,ElemType y） q=h; while（ p!q=p; s- q-13. 有一带表头结点的单链表，其结点的元

10、素值以非递减有序排列，编写一个算法在该链表中插入一个元素x，使得插入后的单链表仍有序。void algo1 （LNode *H, ElemTp x） s=（LNode *） malloc （sizeof（LNode）;data=x; q=H; p=H-while （ p &=x ） q=p;next=p; q- 14. 二叉排序树的类型定义如下：15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。 void Del_digit （LNode *h） for（p=h;） q=p- if（q-=0&=9） p- free（q）; else p=q;

11、 16. 利用栈的基本运算，编写一个算法，实现将整数转换成二进制数输出。void returnDtoO（int num）initStack（s）;while（n） k=n%2;n=n/2; push（s,k）;while（EmptyStack（s） pop（s,k）; printf（“%d”,k）;17. 设二叉树T采用二叉链表结构存储，数据元素为int型，试设计一个算法，若结点左孩子的data域的值大于右孩子的data域的值，则交换其左、右子树。void algo2（bitreptr bt） bitreptr x; if （bt-lchild &rchild） & （bt-lchild -r

12、child-data） ） x= bt-lchild ; bt-lchild= bt-rchild;rchild=x; 18. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。int Deep（BTNode *bt） if （bt=NULL） return 0; left=Deep（bt- right=Deep（bt-return （leftright?left:right）+1;19. 设给定的哈希表存储空间为H（0M-1），哈希函数的构造方法为“除留余数法”，处理冲突的方法为“线性探测法”，设计算法将元素e填入到哈希表中。void hash-insert（hashTable h

13、,int m,ElemType e） j=e%p; if（hj!=NULL） hj=e; else do j=（j+1） %m;while（hj!=NULL ）;hj=e; 20. 对于给定的十进制正整数,打印出对应的八进制正整数。（利用栈）void DecToOct（int num） /初始化栈 k=n%8;n=n/8;while（EmptyStack（s） /判断栈是否为空21. 一个正读和反读都相同的字符序列称为“回文”。例如“abcba”和“1221”是回文，而“abcde”不是回文。试写一个算法，要求利用栈的基本运算识别一个以为结束符的字符序列是否是回文。int Pair（char

14、*str ） InitStack（s）； p=str for （ ; *p!=; p+ ） Push（s,*p）; while（StackEmpty（s） Pop（s,y）;if（y!=*str+ ） return 0; return 1;22. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法删除该链表中多余的元素值相同的结点（值相同的结点只保留一个）。 void Delsame （LNode *h） if（h-next） for（p=h- q=p- if（p-data=q-data） p- free（q）; else p=q;23. 编写一个算法，判断带表头结点的单链表

15、是否递增有序。int fun（LNode *h ） p=h- while（p-next） q=p-next ;if（q-data） return 0;p=q; return 1; 24. 假设有两个带表头结点的单链表HA和HB，设计算法将单链表HB插入到单链表HA的第i（0 ; p- q-next= hb-next ； free（hb）;25. 假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node DataType data; struct node *next LinkNode, *LinkList; 编写算法，从有序表A中删除所有和有序表B中元素

16、相同的结点。（空）26. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法分别求出二叉链表中data域为英文字母和数字字符的结点个数。int letter=0，digit=0； /*全局变量*/ void algo2（BTNode *bt）=A&=Z| bt-=z） letter +;=9） digit +;27. 假设以单链表表示线性表,单链表的类型定义如下:typedef struct node DataType data; struct node *next; LinkNode, *LinkList; 编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头

17、指针仍为head的单向循环链表,并分析算法的时间复杂度。LinkList f34（LinkList head） LinkList p,s; p=head; while （p-next） p=p- s=（LinkList）malloc（sizeof（LinkNode）;next=head; head=s; return head; 时间复杂度为:O（n）28. 假设有向图以邻接表方式存储，编写一个算法判别顶点vi到顶点vj是否存在弧。int IsArcs（ALgraph G,int i,int j） /* 判断有向图G中顶点i到顶点j是否有弧,是则返回1,否则返回0*/ p=Gi.firstarc; while （p!=NULL） if（p-adjvex =j） return 1; p=p-nextarc; return 0;29. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法求出二叉链表中data域为大写字母的结点个数。int count=0；/* count为全局变量*/=Z） count+;30. 假设带表头结点的双向循环链表定义如下：typedef struct dunode char data; struct dunode *prior, *next; DuNod