华师网络学院作业答案-数据结构写作题

设计一个递归算法，求二叉树t中度为1的结点数。设二叉链表类型定义如下。 typedef int datatype; //结点的数据类型，假设为int typedef struct NODE *pointer; //结点指针类型 struct NODE { datatype data;

pointer lchild,rchild; };

typedef pointer bitree; //根指针类型 答案:

int sum1(bitree t) { int L,R;

if(t==NULL) return 0; L=sum1(t->lchild); R=sum1(t->rchild);

if((t->lchild==NULL && t->rchild!=NULL) ,, (t->lchild!=NULL && t->rchild==NULL)) return L+R+1; else

return L+R; }

设计递归算法，判断二叉树t中是否所有结点都为正数。 二叉链表的类型定义如下：

typedef int datatype; //结点的数据类型，假设为int typedef struct NODE *pointer; //结点指针类型 struct NODE { datatype data;

pointer lchild,rchild; };

typedef pointer bitree; //根指针类型

答案:

int detect(bitree t) { int L,R;

if(t==NULL) return 1; if(t->data<=0) return 0;

return detect(t->lchild) && detect(t->rchild); }

设计算法将顺序表L中所有的小写字符都移动到表的前端，要求元素的移动次数尽量少。 顺序表类型定义如下：

typedef char datatype; //结点的数据类型，假设为char const int maxsize=100; //最大表长，假设为100

typedef struct {

datatype data[maxsize]; //线性表的存储向量，第一个结点是data[0] int n; //线性表的当前长度 } sqlist; //顺序表类型

答案:

void moves(sqlist *L) { int i,j; datatype x; i=1;j=L->n; while(i< j) {

while((L->data[i]>='a' && L->data[i]<='z') && i< j) i++; while((L->data[j]<'a' ,, L->data[i]>'z') && i< j) j--; if(i< j) {

x=L->data[i];L->data[i]=L->data[j];L->data[j]=x; i++;j--; } } }

设计算法，将顺序表L中所有的负数都移动到表的后端，要求移动次数尽量少。 顺序表类型定义如下：

typedef int datatype; //结点的数据类型，假设为int const int maxsize=100; //最大表长，假设为100 typedef struct {

datatype data[maxsize]; //线性表的存储向量，第一个结点是data[0] int n; //线性表的当前长度 } sqlist; //顺序表类型 答案:

void moves(sqlist *L) { int i,j; datatype x; i=1;j=L->n; while(i< j) {

while(L->data[i]>＝0 && i< j) i++;

while(L->data[j]< 0 && i< j) j??; if(i< j) {

x=L->data[i];L->data[i]=L->data[j];L->data[j]=x; i++;j??; } } }

设计算法将顺序表L中所有的正数都删除，要求元素的移动次数尽量少。 顺序表类型定义如下：

typedef int datatype; //结点的数据类型，假设为int const int maxsize=100; //最大表长，假设为100 typedef struct {

datatype data[maxsize]; //线性表的存储向量，第一个结点是data[0] int n; //线性表的当前长度 } sqlist; //顺序表类型

答案:

void dels(sqlist *L) { int s,i; s=0;

for(i=0;in;i++)

if(L->data[i]>0) s++;

else if(s>0) L->data[i-s]=l->data[i]; L->n=L->n-s; }

设计算法将顺序表L中所有的数字字符都移动到表的后端，要求元素的移动次数尽量少。 顺序表类型定义如下：

typedef char datatype; //结点的数据类型，假设为char const int maxsize=100; //最大表长，假设为100 typedef struct {

datatype data[maxsize]; //线性表的存储向量，第一个结点是data[0] int n; //线性表的当前长度 } sqlist; //顺序表类型

答案:

void moves(sqlist *L) { int i,j; datatype x; i=1;j=L->n; while(i< j) {

while((L->data[i]<'0' ,, L->data[i]>'9') && i< j) i++; while((L->data[i]>='0' && L->data[i]<='9') && i< j) j--; if(i< j) {

x=L->data[i];L->data[i]=L->data[j];L->data[j]=x; i++;j--; } } }

设计递归算法，判断二叉树t是否满足小根堆的特点。二叉链表的类型定义如下： typedef int datatype; //结点的数据类型，假设为int typedef struct NODE *pointer; //结点指针类型 struct NODE { datatype data;

pointer lchild,rchild; };

typedef pointer bitree; //根指针类型 答案:

int detect(bitree t) {

if(t==NULL) return 1; //空树看成真

if((t->lchild!=NULL && t->lchild->data>t-data) ,, (t->rchild!=NULL && t->rchild->data>t-data)) return 0; //左孩子>根，或右孩子>根，为假 else

return detect(t->rchild) && detect(t->rchild); }

设计算法将顺序表L中所有的负数都移动到表的前端，要求移动次数尽量少。 顺序表类型定义如下：

typedef int datatype; //结点的数据类型，假设为int const int maxsize=100; //最大表长，假设为100 typedef struct {

datatype data[maxsize]; //线性表的存储向量，第一个结点是data[0] int n; //线性表的当前长度 } sqlist; //顺序表类型

答案:

void moves(sqlist *L) { int i,j; datatype x; i=1;j=L->n; while(i< j) {

while(L->data[i]< 0 && i< j) i++; while(L->data[j]>=0 && i< j) j--; if(i< j) {

x=L->data[i];L->data[i]=L->data[j];L->data[j]=x; i++;j--; } } }

设计递归算法，求二叉排序树t的高度。二叉链表的类型定义如下： typedef int datatype; //结点的数据类型，假设为int typedef struct NODE *pointer; //结点指针类型 struct NODE { datatype data;

pointer lchild,rchild; };

typedef pointer bitree; //根指针类型 答案:

int high(bitree t) { int L,R;

if(t==NULL) return 0; L=high(t->lchild); R=high(t->rchild); return L>R?L+1:R+1; }

设计递归算法，求二叉排序树t的叶子数。二叉链表的类型定义如下： typedef int datatype; //结点的数据类型，假设为int typedef struct NODE *pointer; //结点指针类型 struct NODE { datatype data;

pointer lchild,rchild; };

typedef pointer bitree; //根指针类型

答案:

int leaf(bitree t) { int L,R;

if(t==NULL) return 0;

if(t->child==NULL && t->rchild==NULL) return 1; L=leaf(t->lchild); R=leaf(t->rchild); return L+R; }

设计一个递归算法，求二叉树t中度为2的结点数。设二叉链表类型定义如下。 typedef int datatype; //结点的数据类型，假设为int typedef struct NODE *pointer; //结点指针类型 struct NODE { datatype data;

pointer lchild,rchild;

};

typedef pointer bitree; //根指针类型 答案:

int sum2(bitree t) { int L,R;

if(t==NULL) return 0; L=sum1(t->lchild); R=sum1(t->rchild);

if(t->lchild!=NULL && t->rchild!=NULL) return L+R+1; else

return L+R; }

设计算法将顺序表L中所有的负数都删除，要求元素的移动次数尽量少。 顺序表类型定义如下：

typedef int datatype; //结点的数据类型，假设为int const int maxsize=100; //最大表长，假设为100 typedef struct {

datatype data[maxsize]; //线性表的存储向量，第一个结点是data[0] int n; //线性表的当前长度 } sqlist; //顺序表类型 答案:

void dels(sqlist *L) { int s,i; s=0;

for(i=0;i< n;i++)

if(L->data[i]<0) s++;

else if(s>0) L->data[i-s]=L->data[i]; L->n=L->n-s; }

本文来源：https://www.bwwdw.com/article/cs1w.html