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

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=1；j=h；

while(i while(i=x)j--；

while(i=x)i++；

if(i           {  t=a[j]；a[j]=a[i]；a[i]=t；}

      }

if(a[i]         else  return i－1；

      }

 （1）写出该函数的功能；

 （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个

数。

【答案】

（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。

      （2）int f(int b[],int n)                      或   int f(int b[],int n)

              {                                                     {

   int p,q；                                         int p,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)；

   return q－p；                                  return p－q；

   }                                              }

3. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。

【答案】

void algo1(LNode *h,int k,ElemType y){

q=h; P=h->next; j=1;

while( p!=h && j 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中值小于a的结点个数。

【答案】

int  f34(BSTree  root)

{

   int count;

   BSTNode *p;

   p=root;

if ( p && p->data f34(p->lchild);

   return count;

}

5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左

至右次序编号）

【答案】

BTNode * Firstleaf(BTNode *bt)

    { InitQueue(Q); //初始化队列Q

      if(bt){

       EnQueue(Q,bt);;

       while(!EmptyQueue(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(“ %c is  a  root\\n”, bt[1]);

else  printf(“ %c’s parent  is %c\\n”, bt[k], bt[k/2]);

if(2*k<=n) printf(“ %c’s lchild is %c\\n”, bt[k], bt[2*k]);

      else printf(“ %c is  not  lchild\\n”, bt[k]));

if(2*k+1<=n) printf(“ %c’s rchild is %c\\n”, bt[k], bt[2*k+1]);

else printf(“ %c is  not  rchild\\n”, bt[k]));

return 1;

  }

7. 编写算法，将非空单链表hb插入到单链表ha的第i(0【答案】

int  algo1(LNode *ha, LNode *hb,int i){   

for(p=hb;p->next; p=p->next);

for(j=1,q=ha;jnext;

p->next=q->next;

q->next=hb->next ；

     free(hb);

  }

8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结构。顺序表T定义如下：

struct tree{

   int no;           /* 结点按完全二叉树的编号*/

   ElEMTP  data;    /* 数据域 */

  }T[N];            /* N为二叉树T的结点数*/

【答案】

 BTNode *creat_tree(struct tree T[N])

     { BTNode *p[MAX]; 

       t=NULL;

for(i=0;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;

else p[j]->rchild=s;

              }//slse

        }//for

     return t;

  }// creat_tree

9. 编写算法判断带表头结点的单链表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（n≥3）项构成，试以带表头结点的单链表作该线性表的存储结构，设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得：

             1              (n=1)    

f(n)=  1              (n=2)

       f(n-2)+f(n-1)  (n≥3)

【答案】

 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 *)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);

    }

  }

12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。

【答案】

void Insertlist(LNode *h,int k,ElemType y)

{

q=h; P=h->next; j=1;

while( p!=h && jq=p; p=p->next; j++;

}

s=(LNode *)malloc(sizeof(Lnode));

s->data=y;

q->next=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 && p->data<=x )

{ 

q=p; p=p->next;

}

s->next=p; q->next=s;

}

14. 二叉排序树的类型定义如下：

typedef struct BSTNode {∥ 二叉排序树的结点结构

int    data;    ∥数据域

struct  BSTNode  *lchild, *rchild; ∥左、右孩子指针

}BSTNode,*BSTree;

设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。

【答案】

int  f34(BSTree  root)

{

   int count;

   BSTNode *p;

   p=root;

if ( p && p->data f34(p->lchild);

   return count;

}

15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。

【答案】

 void Del_digit (LNode *h){

for(p=h;p->next;){

q=p->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型，试设计一个算法，若结点左孩子的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);

    }

  }  

18. 设二叉树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（0～M-1），哈希函数的构造方法为“除留余数法”，处理冲突的方法为“线性探测法”，设计算法将元素e填入到哈希表中。

【答案】

void hash-insert(hashTable  h[],int m,ElemType e){

  j=e%p;

  if(h[j]!=NULL)  h[j]=e;

  else{ 

do

{ j=(j+1) %m;

}while(h[j]!=NULL );

h[j]=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”不是回文。试写一个算法，要求利用栈的基本运算识别一个以@为结束符的字符序列是否是回文。

【答案】

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->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【答案】

void fun(LNode *ha, LNode *hb,int i)   

{ for(p=hb;p->next; p=p->next);

for(j=1,q=ha;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中删除所有和有序表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<=’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) 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=G[i].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){

if(bt->data>=’A’&& bt->data<=’Z’)

        count++;

algo2(bt->lchild);

algo2(bt->rchild);

    }

  }

30. 假设带表头结点的双向循环链表定义如下：

typedef struct dunode{

        char  data;

         struct  dunode  *prior, *next;

       }DuNode;     

现用该链表存放字符串，编写一个算法，判断该字符串是否中心对称关系。例如字符串“xyzzyx”和“xyzyx”  都是中心对称的。

【答案】

int  fun(DuNode *h )   

{ p=h->next;q=h->prior;

while(p!=q && p->prior!=q)

{ 

if(q->data==p->data)

{ p=p->next;q=q->prior;}

else return 0;

}

  return 1;               

 }

31. 假设以带头结点的单链表表示线性表，单链表的类型定义如下：

typedef int DataType;

typedef struct node {

   DataType data;

   struct node * next;

} LinkNode, * LinkList;

编写算法，删除线性表中最大元素(假设最大值唯一存在)。函数原型为：

void  f34(LinkList head) ;

【答案】

void f34(LinkList head)

     {

         int e;

         LinkList  p,q,s,spre;  //s指向最大值的那个结点

spre=head; s=head->next;

q=s; p=s->next;

         while (p)

         {

if(s->datadata)

            {   s=p;  spre=q; }

            q=p;

p=p->next;

          }

e=s->data;

spre->next=s->next;

          free(s);

      }