数据结构算法设计题复习题

算法设计题1.设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。【答案】intcount=0;voidalgo2(BTNode*bt){if(bt){if(bt->lchild||bt->rchild){printf(bt->data);count++;}algo2(bt->lchild);algo2(bt->rchild);}}2.阅读下列函数arrange()intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(i<j){while(i<j&&a[j]>=x)j--；while(i<j&&a[j]>=x)i++；if(i<j){t=a[j]；a[j]=a[i]；a[i]=t；}}if(a[i]<x)returni；elsereturni－1；}（1）写出该函数的功能；（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。【答案】（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。（2）intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p；returnp－q；}}3.假设线性表以带表头结点的循环单链表表达。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。【答案】voidalgo1(LNode*h,intk,ElemTypey){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.二叉排序树的类型定义如下：typedefstructBSTNode{∥二叉排序树的结点结构intdata;∥数据域structBSTNode*lchild,*rchild;∥左、右孩子指针}BSTNode,*BSTree;设计递归算法，记录一棵二叉排序树T中值小于a的结点个数。【答案】intf34(BSTreeroot){intcount;BSTNode*p;p=root;if(p&&p->data<a)count++;f34(p->lchild);returncount;}5.设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左至右顺序编号）【答案】BTNode*Firstleaf(BTNode*bt){InitQueue(Q);//初始化队列Qif(bt){EnQueue(Q,bt);;while(!EmptyQueue(Q)){DeQueue(Q,p);if(!p->lchild&&!p->rchild)returnp;if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}}6.已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和孩子结点。【答案】intalgo2(charbt[],intn,intk){if(k<1||k>n)return0;if(k==1)printf(“%cisaroot\n”,bt[1]);elseprintf(“%c’sparentis%c\n”,bt[k],bt[k/2]);if(2*k<=n)printf(“%c’slchildis%c\n”,bt[k],bt[2*k]);elseprintf(“%cisnotlchild\n”,bt[k]));if(2*k+1<=n)printf(“%c’srchildis%c\n”,bt[k],bt[2*k+1]);elseprintf(“%cisnotrchild\n”,bt[k]));return1;}7.编写算法，将非空单链表hb插入到单链表ha的第i(0<i≤表长)个结点前。【答案】intalgo1(LNode*ha,LNode*hb,inti){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定义如下：structtree{intno;/*结点按完全二叉树的编号*/ElEMTPdata;/*数据域*/}T[N];/*N为二叉树T的结点数*/【答案】BTNode*creat_tree(structtreeT[N]){BTNode*p[MAX];t=NULL;for(i=0;i<N;i++){s=(BTNode*)malloc(sizeof(BTNode));s->data=T[i].data;s->lchild=s->rchild=NULL;m=T[i].no;p[m]=s; if(m==1)t=s; else{j=m/2; if(m%2==0)p[j]->lchild=s;elsep[j]->rchild=s;}//slse}//forreturnt;}//creat_tree9.编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。【答案】intalgo1(LNode*L){if(!L->next)return1;p=L->next;while(p->next){if(p->data<p->next->data)p=p->next;elsereturn0;}return1;}10.假设一线性表由Fibonacci数列的前n（n≥3）项构成，试以带表头结点的单链表作该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得：1(n=1)f(n)=1(n=2)f(n-2)+f(n-1)(n≥3)【答案】LNode*Creatlist(LNode*h,intn){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*)malloc(sizeof(Lnode));s->data=p->data+q->data;s->next=NULL;p=q;q=s;}returnh;}11.设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。【答案】voidalgo2(BTNode*bt){if(bt){if(bt->data>=’a’&&bt->data<=’z’)bt->data-=32;algo2(bt->lchild);algo2(bt->rchild);}}12.假设线性表以带表头结点的循环单链表表达。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。【答案】voidInsertlist(LNode*h,intk,ElemTypey){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.有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x，使得插入后的单链表仍有序。【答案】voidalgo1(LNode*H,ElemTpx){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.二叉排序树的类型定义如下：typedefstructBSTNode{∥二叉排序树的结点结构intdata;∥数据域structBSTNode*lchild,*rchild;∥左、右孩子指针}BSTNode,*BSTree;设计递归算法，记录一棵二叉排序树T中值小于a的结点个数。【答案】intf34(BSTreeroot){intcount;BSTNode*p;p=root;if(p&&p->data<a)count++;f34(p->lchild);returncount;}15.有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。【答案】voidDel_digit(LNode*h){for(p=h;p->next;){q=p->next;if(q->data>=’0’&&q->data<=’9’){p->next=q->next;free(q);}elsep=q;}}16.运用栈的基本运算，编写一个算法，实现将整数转换成二进制数输出。【答案】voidreturnDtoO(intnum){ 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域的值，则互换其左、右子树。【答案】voidalgo2(bitreptrbt){bitreptrx;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);}}18.设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。【答案】intDeep(BTNode*bt){if(bt==NULL)return0;left=Deep(bt->lchild);right=Deep(bt->rchild);return(left>right?left:right)+1;}19.设给定的哈希表存储空间为H（0～M-1），哈希函数的构造方法为“除留余数法”，解决冲突的方法为“线性探测法”，设计算法将元素e填入到哈希表中。【答案】voidhash-insert(hashTableh[],intm,ElemTypee){j=e%p;if(h[j]!=NULL)h[j]=e;else{do{j=(j+1)%m;}while(h[j]!=NULL);h[j]=e;}}20.对于给定的十进制正整数,打印出相应的八进制正整数。（运用栈）【答案】voidDecToOct(intnum){ 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”不是回文。试写一个算法，规定运用栈的基本运算辨认一个以@为结束符的字符序列是否是回文。【答案】intPair(char*str){InitStack(s)；p=strfor(;*p!=’@’;p++)Push(s,*p);while(StackEmpty(s)){Pop(s,y);if(y!=*str++)return0;}return1;}22.有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法删除该链表中多余的元素值相同的结点(值相同的结点只保存一个)。【答案】voidDelsame(LNode*h){if(h->next){for(p=h->next;p->next;){q=p->next;if(p->data==q->data){p->next=q->next;free(q);}elsep=q;}}23.编写一个算法，判断带表头结点的单链表是否递增有序。【答案】intfun(LNode*h){p=h->next;while(p->next){q=p->next;if(q->data>p->data)return0;p=q;}return1;}24.假设有两个带表头结点的单链表HA和HB，设计算法将单链表HB插入到单链表HA的第i(0<i≤表长)个结点前。【答案】voidfun(LNode*ha,LNode*hb,inti){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.假设以带头结点的单链表表达有序表，单链表的类型定义如下：typedefstructnode{DataTypedata;structnode*next}LinkNode,*LinkList;编写算法，从有序表A中删除所有和有序表B中元素相同的结点。【答案】(空)26.设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法分别求出二叉链表中data域为英文字母和数字字符的结点个数。【答案】intletter=0，digit=0；/*全局变量*/voidalgo2(BTNode*bt){if(bt){if(bt->data>=’A’&&bt->data<=’Z’||bt->data>=’a’&&bt->data<=’z’)letter++;if(bt->data>=’0’&&bt->data<=’9’)digit++;algo2(bt->lchild);algo2(bt->rchild);}}27.假设以单链表表达线性表,单链表的类型定义如下:typedefstructnode{DataTypedata;structnode*next;}LinkNode,*LinkList;编写算法,将一个头指针为head且不带头结点的单链表改造为一个含头结点且头指针仍为head的单向循环链表,并分析算法的时间复杂度。【答案】LinkListf34(LinkListhead){LinkListp,s;p=head;while(p->next)p=p->next;s=(LinkList)malloc(sizeof(LinkNode));s->next=head;p->next=s;head=s;returnhead;}时间复杂度为:O(n)28.假设有向图以邻接表方式存储，编写一个算法判别顶点vi到顶点vj是否存在弧。【答案】intIsArcs(ALgraphG,inti,intj){/*判断有向图G中顶点i到顶点j是否有弧,是则返回1,否则返回0*/p=G[i].firstarc;while(p!=NULL){if(p->adjvex==j)return1;p=p->nextarc;}return0;}29.设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法求出二叉链表中data域为大写字母的结点个数。【答案】intcount=0；/*count为全局变量*/voidalgo2(BTNode*bt){if(bt){if(bt->data>=’A’&&bt->data