(完整)数据结构算法设计题

1、(完整)数据结构算法设计题(完整)数据结构算法设计题第 PAGE 15第15页万维试题库系统一、算法设计题1。 设二叉树bt的个数。【答案】int count=0；void algo2(BTNode *bt)if (bt)if（bt-lchild | btrchild) printf（btdata);count+；algo2（bt-lchild； algo2（btrchild）;2。 阅读下列函数arrange(）int arrange（int a,int 1，int h,int x）/1和h分别为数据区的下界和上界int i，j，t；i=1；j=h； while(iwhile（i=x）i+;

2、 if(ij) t=j；aj=ai；ai=；if(aix) return else return i1;写出该函数的功能；写一个调用上述函数实现下列功能的算法:对一整型数组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，1，1；q

3、=arrange（b，0,p,0)；return qp;return pq;3。 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k,则插在表尾。【答案】void algo1(LNode h，int k，ElemType y） q=h; P=hnext; j=1;while（ p！=h & jdata a）count+； f34（plchild);return count;5。 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点（从上往下，自左至右次序编号）【答案】BTNode * Firstleaf（BTNo

4、de *bt) InitQueue(Q）; /初始化队列Q if(bt)EnQueue（Q，bt); while(！EmptyQueue(Q) DeQueue（Q,p);if(！plchild & !p-rchild） return if(p- lchild） EnQueue(Q，p-lchild）; if（p-rchild） EnQueue(Q，prchild）;6。 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型，编写算法打印出编号为k的结点的双亲和孩子结点。【答案】int algo2（charbt，int n，int k if (k1|kn) return 0；i

5、f( k=1） printf(“ %c is a rootn”,bt1)；else printf(“%csparent iscn”， btk，btk/2； if(2knext; p=p- next)； for（j=1，q=ha；ji; j+)q=qnext； p-next=qnext;qnext=hbnextfree（hb；8。 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构.顺序表T定义如下:struct treeintno；/*结点按完全二叉树的编号/ ElEMTP data;/ 数据域 */TN；/N为二叉树T的结点数*/【答案】BTNo

6、de creat_tree（struct tree TN） BTNode pMAX； t=NULL；for(i=0;iN；i+)s=BTNode c（f（) s-data=Ti.data；slchild=s-rchild=NULL； m=Ti.no；pm=s; if（m=1) t=s;else j=m/2；if（m%2=0） pjlchild=s; else pjrchild=s;/slse/for return t；/ creat_tree9。 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。【答案】intalgo1 （LNode L)if(!L-next) retu

7、rn 1； p=L- next; while(pnext)if（p-data next-data) p=pnext； else return 0;return 1;10。 假设一线性表由Fibonacci数列的前nFibonacci1（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); hdata=n；h-next=p=(LNode*）malloc（sizeof（Lnode）; pnext=q=(LNode ）c（fe） p-data= q-d

8、ata=1for(i=3；inext=s=(LNode *)malloc （sizeof(Lnode); sdata=pdata+q-data； snext=NULL； p=q；q=s； returnh；11. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。【答案】voidalgo2BTNodet if(btif（bt-data=a bt-data=z)bt-data=32;algo2(btlchild)； algo2（bt-rchild)；12。 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素

9、前插入新元素y。假如表长小于k，则插在表尾。【答案】void Insertlist(LNode *h，int k，ElemType y）q=h； P=h-next; j=1； while（p！=hjq=p;p=pnext;j+；s=(LNode ）fe sdata=y;qnext=s; s-next=q;13. x,使得插入后的单链表仍有序。【答案】void algo1 (LNode *H， ElemTp x）s=(LNode ） malloc (sizeof(LNode）); s-data=x;q=H； p=H-next;while ( p pdata=x ）q=p; p=pnext;sne

10、xt=p; q-next=s；14。 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结intdata；数据域struct BSTNode *lchild， rchild； 左、右孩子指针BSTNode，BSTree;设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。【答案】int f34(BSTree root）int count； BSTNode p； p=root;if ( p & p datanext;if(q-data=0& q-data =9）p-next=qnext；free（q）;elsep=q;16. 利用栈的基本运算，编写一个算

11、法，实现将整数转换成二进制数输出。【答案】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)if (bt-lchild & btrchild) & (btlchild data bt

12、rchild-data） ） x= btlchild ；btlchild= btrchild； bt-rchild=x；algo2(bt-lchild); algo2(bt-rchild);18. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。【答案】int Deep（BTNode bt)if （bt=NULL） return 0； left=Deep（bt-lchild）; right=Deep（bt-rchild）;return (leftright？left：right)+1；19。 设给定的哈希表存储空间为H（0M1）,哈希函数的构造方法为“除留余数法”，处理冲突的方法为

13、“线性探测法”，设计算法将元素e填入到哈希表中。【答案】void hashinsert（hashTable h,int m，ElemType e) j=ep;if(hj!=NULL) hj=e； elsedo j=(j+1) %m；while(hj!=NULL )； hj=e;（利用栈）【答案】void DecToOct（int num）initStack（s；/ while(n) k=n%8；n=n/8；push(s，k);while（EmptyStack（s）/判断栈是否为空 pop(sk； printf（“d”,k)；“abcba”和“1221”“abcde为结束符的字符序列是否是回文。

14、【答案】int Pair(char str ) InitStack(s； p=strfor （ ; *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=ht；t） q=pnext；if(pdata=q-a p-next=qnext;free(q);else p=q;23. 编写一个算法，判断带表头结点的单链表是否递增有序。【答案】int fun(LNode *h ) p=

15、h-next； while（p- q=p-next ; if（qdatapdata）return p=q；return 1；24。 假设有两个带表头结点的单链表HA和HBHBHA的第i（0i表长）结点前。【答案】void fun（LNode *ha, LNode *hb,int i) for(p=hb；p-next； p=pnext）; for(j=1，q=ha；ji; j+）q=qnext; ； p-next=qnext;q-next=hb-nextfree（hb);25。 typedef struct nodeDataType data; struct node *nextLinkNode

16、, *LinkList；编写算法,从有序表A中删除所有和有序表B中元素相同的结点.【答案】（空)设二叉树Tdata字母和数字字符的结点个数.【答案】int letter=0，digit=0；/全局变量void algo2(BTNode btif (btif(btdata=A& =Z| btdata=a& bt-datadata=0& bt-data=9) digit +；algo2(btlchild）; algo2(bt-rchild);typedef struct node DataType data; struct node LinkNode, *LinkList；编写算法,将一个头指针为

17、head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。【答案】LinkList f34（LinkList head）LinkList p，s； p=head；while (p-next)p=p- next; s=（LinkList)malloc（sizeof（LinkNode); s-next=head；pnext=s； head=s; return head；时间复杂度为:O(n）28。 假设有向图以邻接表方式存储,编写一个算法判别顶点v 到顶点v 是否存在弧。ij【答案】int IsArcs(ALgraph G,int i,int j)

18、/ 判断有向图G中顶点i到顶点j是否有弧,是则返回1，否则返回0*/ p=Gi.firstarc;while (p！=NULL) if(padjvex =j)return 1; p=p-nextarc;return 0；设二叉树Tdata的结点个数。【答案】int count=0；/* count为全局变量*/void algo2(BTNode *bt) if (bt）if(bt-data=A&btdatarchild）;typedef struct dunodechar data;struct dunode prior， *next;DuNode；现用该链表存放字符串，编写一个算法 ,判断该字符串是否中心对称关系。例如字符串“xyzzyx”和“xyzyx” 都是中心对称的。【答案】int fun(DuNode *h ) p=hnext；q=hprior； while(p!=q & pprior!=q)if（q-data=p-data) r else return 0；return