程序填空题,算法设计题
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;