数据结构算法设计题

1、一、算法设计题1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。【答案】int count=0;void algo2(BTNode *bt) if (bt) if(bt->lchild | bt->rchild) printf(bt->data); count+; algo2(bt->lchild); algo2(bt->rchild); 2. 阅读下列函数arrange() int arrange(int a,int 1,int h,int x) /1和h分别为数据区的下界和上界 int i,j,t； i=

2、1；j=h； while(i<j) while(i<j && aj>=x)j-； while(i<j && aj>=x)i+； if(i<j) t=aj；aj=ai；ai=t； if(ai<x) return i； else return i1； （1）写出该函数的功能； （2）写一个调用上述函数实现下列功能的算法：对一整型数组bn中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。【答案】（1）该函数的功能是：调整整数数组a中的元

3、素并返回分界值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= arrange(b,0,p,0)； return qp； return pq； 3. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。【答案】void algo1(LNode *h,

4、int k,ElemType y)q=h; P=h->next; j=1;while( p!=h && j<k) q=p; p=p->next; j+;s=(LNode *)malloc(sizeof(Lnode);s->data=y;q->next=s;s->next=q; 4. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct BSTNode *lchild, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T

5、中值小于a的结点个数。【答案】int f34(BSTree root) int count; BSTNode *p; p=root; if ( p && p->data<a) count+; f34(p->lchild); return count;5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左至右次序编号）【答案】BTNode * Firstleaf(BTNode *bt) InitQueue(Q); /初始化队列Q if(bt) EnQueue(Q,bt); while(!EmptyQueu

6、e(Q) DeQueue(Q,p); if(!p->lchild && !p->rchild) return p; if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); 6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和孩子结点。【答案】 int algo2(char bt,int n,int k) if (k<1|k>n) return 0;if( k=1) printf(“

7、%c is a rootn”, bt1);else printf(“ %cs parent is %cn”, btk, 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(

8、0<i表长)个结点前。【答案】int algo1(LNode *ha, LNode *hb,int i) for(p=hb;p->next; p=p->next); for(j=1,q=ha;j<i; j+) q=q->next; p->next=q->next; q->next=hb->next ； free(hb); 8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构。顺序表T定义如下：struct tree int no; /* 结点按完全二叉树的编号*/ ElEMTP data;

9、/* 数据域 */ TN; /* N为二叉树T的结点数*/【答案】 BTNode *creat_tree(struct tree TN) BTNode *pMAX; t=NULL; for(i=0;i<N;i+) s=(BTNode *)malloc(sizeof(BTNode); s->data=Ti.data; s->lchild=s->rchild=NULL; m=Ti.no; pm=s; if(m=1) t=s; else j=m/2; if(m%2=0) pj->lchild=s; else pj->rchild=s; /slse /for ret

10、urn t; / creat_tree9. 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。【答案】int algo1 (LNode *L) if(!L->next) return 1; p=L->next; while(p->next) if(p->data < p->next->data) p=p->next; else return 0; return 1;10. 假设一线性表由Fibonacci数列的前n（n3）项构成，试以带表头结点的单链表作该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。F

11、ibonacci数列根据下式求得： 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; h->next=p=(LNode *)malloc(sizeof(Lnode); p->next=q=(LNode *)malloc(sizeof(Lnode); p->data= q->data=1; for(i=3;i<=n;i+) q->next=s=(LNode *)

12、malloc(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) if(bt->data>=a&& bt->data<=z) bt->data-=32; algo2(bt->lchild); algo2(bt->rchild);

13、12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。【答案】void Insertlist(LNode *h,int k,ElemType y) q=h; P=h->next; j=1; while( p!=h && j<k)q=p; p=p->next; j+;s=(LNode *)malloc(sizeof(Lnode); s->data=y; q->next=s; s->next=q; 13. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法

14、在该链表中插入一个元素x，使得插入后的单链表仍有序。【答案】void algo1 (LNode *H, ElemTp x) s=(LNode *) malloc (sizeof(LNode); s->data=x; q=H; p=H->next;while ( p && p->data<=x ) q=p; p=p->next;s->next=p; q->next=s; 14. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct BSTNode *lchild

15、, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。【答案】int f34(BSTree root) int count; BSTNode *p; p=root; if ( p && p->data<a) count+; f34(p->lchild); return count;15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。【答案】 void Del_digit (LNode *h) for(p=h;p->next;) q=p-

16、>next; if(q->data>=0&& q->data <=9) p->next=q->next; free(q); else p=q; 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型，试设计一个算法，若结点左孩子的

17、data域的值大于右孩子的data域的值，则交换其左、右子树。【答案】void algo2(bitreptr bt) bitreptr x; if (bt) if (bt->lchild && bt->rchild) && (bt->lchild ->data> bt->rchild->data) ) x= bt->lchild ; bt->lchild= bt->rchild; bt->rchild=x; algo2(bt->lchild); algo2(bt->rchild); 1

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

19、; if(hj!=NULL) hj=e; else do j=(j+1) %m;while(hj!=NULL );hj=e; 20. 对于给定的十进制正整数,打印出对应的八进制正整数。（利用栈）【答案】void DecToOct(int num)initStack(s); /初始化栈while(n) k=n%8;n=n/8; push(s,k); while(EmptyStack(s) /判断栈是否为空 pop(s,k); printf(“%d”,k);21. 一个正读和反读都相同的字符序列称为“回文”。例如“abcba”和“1221”是回文，而“abcde”不是回文。试写一个算法，要求利用栈

20、的基本运算识别一个以为结束符的字符序列是否是回文。【答案】int Pair(char *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->next;p->

21、next;) q=p->next; if(p->data=q->data) p->next=q->next; free(q); else p=q; 23. 编写一个算法，判断带表头结点的单链表是否递增有序。【答案】int fun(LNode *h ) p=h->next; while(p->next) q=p->next ;if(q->data>p->data) return 0;p=q; return 1; 24. 假设有两个带表头结点的单链表HA和HB，设计算法将单链表HB插入到单链表HA的第i(0<i表长)个结点前。

22、【答案】void fun(LNode *ha, LNode *hb,int i) for(p=hb;p->next; p=p->next); for(j=1,q=ha;j<i; j+) q=q->next; ; p->next=q->next; q->next= hb->next ； free(hb); 25. 假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node DataType data; struct node *next LinkNode, *LinkList; 编写算法，从有序表A中删除所有和

23、有序表B中元素相同的结点。【答案】(空)26. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法分别求出二叉链表中data域为英文字母和数字字符的结点个数。【答案】int letter=0，digit=0； /*全局变量*/ void algo2(BTNode *bt) if (bt) if(bt->data>=A&& bt->data<=Z| bt->data>=a&& bt->data<=z) letter +; if(bt->data>=0&& bt->data&

24、lt;=9) digit +; algo2(bt->lchild); algo2(bt->rchild); 27. 假设以单链表表示线性表,单链表的类型定义如下:typedef struct node DataType data; struct node *next; LinkNode, *LinkList; 编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。【答案】LinkList f34(LinkList head) LinkList p,s; p=head; while (p->next)

25、p=p->next; s=(LinkList)malloc(sizeof(LinkNode); s->next=head; p->next=s; 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为全局变量*/ void algo2(BTNode *bt) if (bt) i