文档库

最新最全的文档下载
当前位置:文档库 > 数据结构-程序填空题

数据结构-程序填空题

程序填空题,算法设计题

1、1.下列是用尾插法建立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句。

NODE *create1(n)

/* 对线性表(1,2,.....,n),建立带头结点的单向链表*/

{

NODE *head,*p,*q;

int i;

p=(NODE *)malloc(sizeof(NODE));

head=p; q=p; p->next=NULL;

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

{

p=(NODE *)malloc(sizeof(NODE));

(1)p->data=i ;

(2)p->next=NULL ;

(3)q->next=p ;

(4)q=p ;

}

return(head);

}

2.下列是用头插法建立带头结点的且有n个结点的单向链表的算法,请在空格内填上适当的语句。

NODE *create2(n)

/*对线性表(n,n-1,.....,1),建立带头结点的线性链表*/

{

NODE *head,*p,*q;

int i;

p=(NODE *)malloc(sizeof(NODE));

(1)head=p ;

p->next=NULL;

(2)q=p ;

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

{

p=(NODE *)malloc(sizeof(NODE));

p->data=i;

if(i==1)

(3)p->next=NULL ;

else

(4)p->next=q->next ;

(5)q->next=p ;

}

return(head);

}

3.下列是在具有头结点单向列表中删除第i个结点,请在空格内填上适当的语句。

int delete(NODE *head,int i)

{

NODE *p,*q;

int j;

q=head;

j=0;

while((q!=NULL)&&(j

{

q=q->next;

j++;

}

if(q==NULL)

return(0);

(1)p=q->next ;

(2)q->next=p->next ;

free(p);

return(1);

}

1.在下面空格处填写适当的语句,以使下面的链式队列取出元素的算法完整。

int write(LinkQueue *q)

{QueueNode *p;

if (q->front==q->rear) /*队空*/

{printf(“underflow”);

exit(0);}

while (q->front->next != NULL)

{p=q->front->next;

(1) q->front->next=p->next;

printf(“%4d”,p->data);

(2) free(p);

}

(3) q->rear=q->front ; /*队空时,头尾指针指向头结点*/ }

1.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是多少?

答:出队序列是e2,e4,e3,e6,e5,e1的过程:

⑴ e1入栈(栈底到栈顶元素是e1)

⑵ e2入栈(栈底到栈顶元素是e1,e2)

⑶ e2出栈(栈底到栈顶元素是e1)

⑷ e3入栈(栈底到栈顶元素是e1,e3)

⑸ e4入栈(栈底到栈顶元素是e1,e3,e4)

⑹ e4出栈(栈底到栈顶元素是e1,e3)

⑺ e3出栈(栈底到栈顶元素是e1)

⑻ e5入栈(栈底到栈顶元素是e1,e5)

⑼ e6入栈(栈底到栈顶元素是e1,e5,e6)

⑽ e6出栈(栈底到栈顶元素是e1,e5)

⑾ e5出栈(栈底到栈顶元素是e1)

⑿ e1出栈(栈底到栈顶元素是空)

栈中最多时有3个元素,所以栈S的容量至少是3。

2.假设用循环单链表实现循环队列,该队列只使用一个尾指针rear,其相应的存储结构和基本算法如下;(1)初始化队列initqueue(Q):建立一个新的空队列Q。

(2)入队列enqueue(Q,x):将元素x插入到队列Q中。

(3)出队列delqueue(Q):从队列Q中退出一个元素。

(4)取队首元素gethead(Q):返回当前队首元素。

(5)判断队列是否为空:emptyqueue(Q)。

(6)显示队列中元素:dispqueue(Q)。

算法设计如下:

/*只有一个指针rear的链式队的基本操作*/

#include

typedef char elemtype;

struct node /*定义链队列结点*/

{

elemtype data;

struct node *next;

};

typedef struct queue /*定义链队列数据类型*/

{

struct node *rear;

} LinkQueue;

void initqueue(LinkQueue *Q)/*初始化队列*/

{

Q=(struct queue *)malloc(sizeof(struct queue));

Q->rear=NULL;

}

void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/

{

struct node *s,*p;

s=(struct node *)malloc(sizeof(struct node));

s->data=x;

if (Q->rear==NULL) /*原为空队时*/

{

Q->rear=s;

s->next=s;

}

else /*原队不为空时*/

{

p=Q->rear->next; /*p指向第一个结点*/

Q->rear->next=s; /*将s链接到队尾*/

Q->rear=s; /*Q->rear指向队尾*/

s->next=p;

}

}

void delqueue(LinkQueue *Q) /*出队算法*/

{

struct node *t;

if (Q->rear==NULL)

{

printf("队列为空!\n");

return(0);

}

else if (Q->rear->next==Q->rear) /*只有一个结点时*/

{

t=Q->rear;

Q->rear=NULL;

}

else /*有多个结点时*/

{

t=Q->rear->next; /*t指向第一个结点*/

Q->rear->next=t->next; /*引成循环链*/

}

free(t);

}

elemtype gethead(LinkQueue *Q) /*取队首元素算法*/

{

if (Q->rear==NULL)

printf("队列为空!\n");

else

return(Q->rear->next->data);

}

int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/

{

if (Q->rear==NULL) return(1); /*为空,则返回true*/

else return(0); /*不为空,则返回flase*/

}

void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/

{

struct node *p=Q->rear->next;

printf("队列元素:");

while (p!=Q->rear)

{

printf("%c ",p->data);

p=p->next;

}

printf("%c\n",p->data);

}

1. 下面函数的功能是返回二叉树BT中值为X的结点所在的层号,请在划有横线的地方填写合适内容。 int NodeLevel(struct BinTreeNode* BT, char X)

{

if(BT==NULL) return 0; /*空树的层号为0*/

else if(BT->data==X) return 1; /*根结点的层号为1*/

/*向子树中查找X结点*/

else {

int c1=NodeLevel(BT->left,X);

if(c1>=1) ___(1) return c1+1___________;

int c2=______(2) NodeLevel(BT->right,X)________ __;

if ___(3)_ (c2>=1) return c2+1_________________;

//若树中不存在X结点则返回0

else return 0;

}

}

2. 下面函数的功能是按照图的深度优先搜索遍历的方法,输出得到该图的生成树中的各条边,请在划有横线的地方填写合适内容。

void dfstree(adjmatrix GA, int i, int n)

{

int j;

visited[i]=1;

(1) for(j=0; j

if(GA[i][j]!=0 && GA[i][j]!=MaxValue && !visited[j])

{

printf("(%d,%d)%d,",i,j,GA[i][j]);

(2) dfstree(GA,j,n);

}

}

五、算法设计题

1.写一个将一棵二叉树复制给另一棵二叉树的算法。

define NULL 0

typedef struct btnode

{

elemtype data;

struct btnode *lchild, *rchild;

}bitnode, *bitree;

bitree *CopyTree( bitnode *p )

{

/*复制一棵二叉树*/

bitnode *t;

if ( p!=NULL )

{

t=(bitnode *)malloc (sizeof (bitnode));

t->data=p->data;

t->lchild=CopyTree(p->lchild);

t->rchild=CopyTree(p->rchild);

return(t);

}

else

return(NULL);

}/*CopyTree*/

2.根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法,该总数值由函数返回。假定参数BT初始指向二叉树的根结点。

int BTreeLeafCount(struct BTreeNode* BT);

int BTreeLeafCount(struct BTreeNode* BT)

{

if(BT==NULL) return 0;

else if(BT->left==NULL && BT->right==NULL) return 1;

else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);

}

1.以下直接输入排序算法对存放在a[0],a[1],···,a[n-1]中,长度为n的记录序列按关键字key由小到大排序,完成程序中的空格部分。

void disort (NODE a[ ], int n)

{ int I,j;

NODE temp; /*工作单位*/

for (i=1;i

{ temp=a[i];

j=j-1;

while (__①_ j>=0___&&temp.key

{ a[j+1]=__ _②_ a[j]_ ___

_____③_ j--_____

}

a[j+1]=____④__ temp __;

}

}

2.以下冒泡法程序对存放在a[1],a[2],……,a[n]中的序列进行冒泡排序完成程序中的空格部分,其中n是元素个数,程序按升序排列。

V oid bsort (NODE a[ ], int)

{ NODE temp;

int i,j,flag;

for(j=1; (1)j<=n-1 ;j++);

{flag=0;

for(i=1; (2)i<=n-j ;i++)

if(a[i].key>a[i+1].key)

{flag=1;

temp=a[i];

(3)a[i]=a[i+1] ;

(4)a[i+1]=temp ;

}

if(flag= =0)break;

}

}

程序中flag的功能是(5)当某趟冒泡中没有出现交换则已排好序结束循环

五、算法设计题

1.写出在二叉树中删除一个结点的算法,且使删除后仍为二叉树,设删除的结点由指针p所指,其双亲结点由指针f所指,并假设被删除结点是其双亲结点的右孩子。

折半查找算法如下;

int Binary_Search(NODE a[],int n, int k)

/* 在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-1 */ {

int low,mid,high;

low=0;

high=n-1;

while(low<=high)

{

mid=(low+high)/2;

if(a[mid].key==k)

return mid; /*查找成功,返回查找到的记录的下标*/

else if(a[mid].key

low=mid+1; /*取后半查找区间*/

else high=mid-1; /*取前半查找区间*/

}

return -1; /*查找失败*/

}

2.编写顺序查找算法。

顺序查找算法如下:

int search(NODE a[],int n, int k)

/*在a[0]~a[n-1]中顺序查找关键字等于k的记录。查找成功时返回该记录的下标,失败时返回-1*/ {

int i=0;

while(i

i++;

if(a[i].key=k) /*查找成功*/

return i;

else return -1; /*查找失败*/

}