数据结构-程序填空题

程序填空题,算法设计题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=NULL;（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(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个结点，请在空格内填上适当的语句。intdelete(NODE*head,inti){NODE*p,*q;intj;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．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。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=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的链式队的基本操作*/#includestdio.htypedefcharelemtype;structnode/*定义链队列结点*/{elemtypedata;structnode*next;};typedefstructqueue/*定义链队列数据类型*/{structnode*rear;}LinkQueue;voidinitqueue(LinkQueue*Q)/*初始化队列*/{Q=(structqueue*)malloc(sizeof(structqueue));Q-rear=NULL;}voidenqueue(LinkQueue*Q,elemtypex)/*入队算法*/{structnode*s,*p;s=(structnode*)malloc(sizeof(structnode));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;}}voiddelqueue(LinkQueue*Q)/*出队算法*/{structnode*t;if(Q-rear==NULL){printf(队列为空!\n);return(0);}elseif(Q-rear-next==Q-rear)/*只有一个结点时*/{t=Q-rear;Q-rear=NULL;}else/*有多个结点时*/{t=Q-rear-next;/*t指向第一个结点*/Q-rear-next=t-next;/*引成循环链*/}free(t);}elemtypegethead(LinkQueue*Q)/*取队首元素算法*/{if(Q-rear==NULL)printf(队列为空!\n);elsereturn(Q-rear-next-data);}intemptyqueue(LinkQueue*Q)/*判断队列是否为空算法*/{if(Q-rear==NULL)return(1);/*为空,则返回true*/elsereturn(0);/*不为空,则返回flase*/}voiddispqueue(LinkQueue*Q)/*显示队列中元素算法*/{structnode*p=Q-rear-next;printf(队列元素:);while(p!=Q-rear){printf(%c,p-data);p=p-next;}printf(%c\n,p-data);}1.下面函数的功能是返回二叉树BT中值为X的结点所在的层号，请在划有横线的地方填写合适内容。intNodeLevel(structBinTreeNode*BT,charX){if(BT==NULL)return0;/*空树的层号为0*/elseif(BT-data==X)return1;/*根结点的层号为1*//*向子树中查找X结点*/else{intc1=NodeLevel(BT-left,X);if(c1=1)___(1)returnc1+1___________;intc2=______(2)NodeLevel(BT-right,X)__________;if___(3)_(c2=1)returnc2+1_________________;//若树中不存在X结点则返回0elsereturn0;}}2.下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。voiddfstree(adjmatrixGA,inti,intn){intj;visited[i]=1;(1)for(j=0;jn;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．写一个将一棵二叉树复制给另一棵二叉树的算法。defineNULL0typedefstructbtnode{elemtypedata;structbtnode*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);}elsereturn(NULL);}/*CopyTree*/2．根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。intBTreeLeafCount(structBTreeNode*BT);intBTreeLeafCount(structBTreeNode*BT){if(BT==NULL)return0;elseif(BT-left==NULL&&BT-right==NULL)return1;elsereturnBTreeLeafCount(BT-left)+BTreeLeafCount(BT-right);}1．以下直接输入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序，完成程序中的空格部分。voiddisort(NODEa[],intn){intI,j;NODEtemp;/*工作单位*/for(i=1;in;i++){temp=a[i];j=j-1;while(__①_j=0___&&temp.keya[j].key){a[j+1]=___②_a[j]_________③_j--_____}a[j+1]=____④__temp__;}}2．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，程序按升序排列。Voidbsort(NODEa[],int){NODEtemp;inti,j,flag;for(j=1;（1）j=n-1;j++);{flag=0;for(i=1;（2）i=n-j;i++)if(a[i].keya[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所指，并假设被删除结点是其双亲结点的右孩子。折半查找算法如下；intBinary_Search(NODEa[],intn,intk)/*在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1*/{intlow,mid,high;low=0;high=n-1;while(low=high){mid=(low+high)/2;if(a[mid].key==k)returnmid;/*查找成功，返回查找到的记录的下标*/elseif(a[mid].keyk)low=mid+1;/*取后半查找区间*/elsehigh=mid-1;/*取前半查找区间*/}return-1;/*查找失败*/}2．编写顺序查找算法。顺序查找算法如下：intsearch(NODEa[],intn