数据结构 程序填空题.docxVIP

程序填空题,算法设计题 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)(ji-1)) /*找到要删除结点的直接前驱，并使 q 指向它*/ { 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; 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 stdio.h typedef char elemtype; struct node /*定义链队列结点*/ { elemtype data