资源描述：
《数据结构 程序填空题.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、程序填空题,算法设计题1、1．下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create1(n)/*对线性表(1,2,.....,n),建立带头结点的单向链表*/{NODE*head,*p,*q;inti;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=N
2、ULL;（3）q->next=p;（4）q=p;}return(head);}2．下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE*create2(n)/*对线性表(n,n-1,.....,1),建立带头结点的线性链表*/{NODE*head,*p,*q;inti;p=(NODE*)malloc(sizeof(NODE));（1）head=p;p->next=NULL;（2）q=p;for(i=1;i<=n;i++){p=(NODE*)malloc(sizeo
3、f(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个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(jnext;j++;}if(q==N
4、ULL)return(0);（1）p=q->next;（2）q->next=p->next;free(p);return(1);}1．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。intwrite(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=
5、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出栈（栈底到栈顶
6、元素是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，其相应的存储结构和基本算法如下；
7、（1）初始化队列initqueue(Q):建立一个新的空队列Q。（2）入队列enqueue(Q,x):将元素x插入到队列Q中。（3）出队列delqueue(Q):从队列Q中退出一个元素。（4）取队首元素gethead(Q):返回当前队首元素。（5）判断队列是否为空：emptyqueue(Q)。（6）显示队列中元素：dispqueue(Q)。算法设计如下：/*只有一个指针rear的链式队的基本操作*/#includetypedefcharelemtype;structnode/*定义链队
8、列结点*/{elemtypedata;structnode*next;};typedefstructqueue/*定义链队列数据类型*/{structnode*rear;}LinkQueue;voidinitqueue(LinkQueue*Q)/*初始化队列*/{Q=(structqueue*)malloc(sizeof(structqueue));Q->rear=NULL;}voidenqueue(LinkQueue*Q,elemtype
