数据结构-程序填空题

程序填空题，算法设计题

1、

1.下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句N0DE*create1n/*对线性表建立带头结点的单向链表

12..…,n,VNODE*head,*p,*q;int i;p=NODE*mallocsizeofNODE;head=p;q=p;p-next=NULL;fori=1;i=n;i++p=NODE*mallocsizeofNODE;1p-data=i;2-p-next=N ULI_____________;3q-next=p______________;-^U q=P；returnhead;下列是用头插法建立带头结点的且有个结点的单向链表的算法，请在空格内填上适当的语句

2.n NODE*create2n/*对线性表建立带头结点的线性链表*/n,n-1,.•…,1,NODE*head,*p,*q;int i;p=NODE*mallocsizeofNODE;—CO_head=p;p-next=NULL;—_q=P；刖fori=1;i=n;i++p=NODE*mallocsizeofNODE;p-data=i;==13p-next=NULI________________;else X4-----------------------------------------p-next=q-next;___q-next=p;returnhead;下列是在具有头结点单向列表中删除第个结点，请在空格内填上适当的语句

3.i intdeleteNODE*head,int iNODE*p,*q;intj;q=head;j=°；/*找到要删除结点的直接前驱，并使指向它*/whileq!=NULLji-1q q=q-next;j++；ifq==NULL return0;1p=q-next;2q-next=p-next;在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整freep;return1;

1.int/*队空*/writeLinkQueue*q{QueueNode*p;if q-front-q-rear{printf underflow”;exit0;}while q-front-next!=NULL{p=q-front-next;⑴q-front-next=p-next;printf a%4dv,p-data;2freep;_______________}/*队空时，头尾指针指向头结点*/£3J_Q-rear=q-front;.设栈和队列的初始状态为空，元素和挨次通过一个元素出栈后即进队列若个元1S Qe1,e2,e3,e4,e5e6S,Q,6素出队的序列是则栈的容量至少应该是多少？e2e4,e3e6e5,e1,S553答出队序列是的过程:e2,e4,e3,e6,e5,el⑴el入栈（栈底到栈顶元素是el）⑵e2入栈（栈底到栈顶元素是el,e2）⑶e2出栈（栈底到栈顶元素是el）

（4）e3入栈（栈底到栈顶元素是el,e3）⑸e4入栈（栈底到栈顶元素是el,e3,e4）

（6）e4出栈（栈底到栈顶元素是el,e3）⑺e3出栈（栈底到栈顶元素是el）

（8）e5入栈（栈底到栈顶元素是el,e5）

（9）e6入栈（栈底到栈顶元素是el,e5,e6））出栈（栈底到栈顶元素是）00e6el,e5（出栈（栈底到栈顶元素是）ID e5el出栈（栈底到栈顶元素是空）⑫el栈中最多时有个元素，所以栈的容量至少是3S3o假设用循环单链表实现循环队列，该队列只使用一个尾指针其相应的存储结构和基本算法如下;初始化队

2.rear,1列建立一个新的空队列initqueueQ:Q入队列将元素插入到队列中2enqueueQ,x:x Q出队列从队列中退出一个元素3delqueueQ:Q取队首元素返回当前队首元素4getheadQ:判断队列是否为空5emptyqueueQ显示队列中元素算法设计如下6dispqueueQo/*惟独一个指针的链式队的基本操作*/r ea r#include stdio.htypedef charelemtype;/*定义链队列结点*/struct nodeelemtypedata;struct node*next;；/*定义链队列数据类型*/typedef struct queue struct node*rear;}LinkQueue;初始化队列*/void initqueueLinkQueue*Q/*{Q=structqueue*mallocsizeofstruct queue;Q-rear=NULL;/*入队算法*/void enqueueLinkQueue*Q,elemtype xstructnode*s,*p;s=structnode*mallocsizeofstruct node;s-data=x;/*原为空队时*/if Q-rear==NULLQ-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*Qstruct node*t;i fQ-rear==NJLL〃队列为空！printf\n〃;return0;else if Q-rear-next==Q-rear/*惟独一个结点时*/t=Q-rear;Q-rear=NULL;/*有多个结点时*/else指向第一个结点*//*/*tt=Q-rear-next;引成循环链*/Q-rear-next=t-next;free t;}elemtype getheadLinkQueue*Q/*取队首元素算法*/if Q-rear==NULL〃队列为空！printf\n〃;elsereturnQ-rear-next-data;/*判断队列是否为空算法*/int emptyqueueLinkQueue*Q/*为空,则返回ifQ-rear==NULL return1;true*//*不为空，则返回else return0;flase*/}__/*显示队列中元素算法*/void dispqueueLinkQueue*Qstruct node*p=Q-rear-next;〃队列元素素;printfwhile p!=Q-rear{printf，z%c〃，p-data;p=p-next;printf//%c\n，/,p-data;下面函数的功能是返回二叉树中值为的结点所在的层号，请在划有横线的地方填写合适内容

1.BT XintNodeLevelstruct BinTreeNode*BT,char X/*空树的层号为ifBT==NULL return0;0*//*根结点的层号为else ifBT-data==X return1;1*//*向子树中查找结点*/X else{int cl=NodeLevelBT-left,X;ifcl=l_U returncl+1；int c2=2NodeLevel BT-right,X；if____3c2=l returnc2+l；〃若树中不存在结点则返回X0else return0;,下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方2填写合适内容void dfstreeadjmatrix GA,int i,int nintj;visited[i]=l;-Cl forj=0;jn;j++ifGA[i][j]!=0GA[i][j]!=MaxValue!visited[j]printf zz%d,%d%d,z，,i,j,GA[i][j];2dfstreeGA,j,n;

五、算法设计题写一个将一棵二叉树复制给另一棵二叉树的算法

1.define NULL0typedef struct btnode elemtypedata;structbtnode*lchild,*rchild;}bitnode,*bitree;/*复制一棵二叉树*/bitree*CopyTree bitnode*pbitnode*t;ifp!=NULLt=bitnode*malloc sizeofbitnode;t-data=p-data;t-1ch i1d=CopyTree p-1ch i1d;t-rchild=CopyTree p-rchiId;return t;else returnNULL;}/*CopyTree*/.根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回假定参数初始指向二2BT叉树的根结点int BTreeLeafCountstructBTreeNode*BT;int BTreeLeafCountstructBTreeNode^BT ifBT==NULL return0;=二else ifBT-left NULLBT-right==NULL return1;else returnBTreeLeafCountBT-left+BTreeLeafCountBT-right;以下直接输入排序算法对存放在中，长度为的记录序列按关键字由小到大排序，完成程序中

3.a

[0],a

[1],••n key的空格部份void disortNODE a[],int n{int l,j;/*工作单位*/NODE temp;for i=1;in;i++{temp=a[i];j=j-1;while_®_j=Otemp.keya[j].key

②{a[j+1]=_____

③一尸}a[j+1]=

④_temp_;———}以下冒泡法程序对存放在中的序列进行冒泡排序完成程序中的空格部份，其中是元素个数，程

4.a

[1],a

[2],……,a[n]n序按升序罗列Void bsortNODE a[],int{NODE temp;int i,j,flag;forj=1;1j=n-1;j++;{flag=0;fori=1;2i=n-j;i++ifa[i].keya[i+1].key{flag=1;temp=a[i];3a[i]=a[i+1];4a[i+1]=temp;ifflag==0break;}程序中的功能是当某趟冒泡中没有浮现交换则已排好序结束循环flag5

五、算法设计题写出在二叉树中删除一个结点的算法，且使删除后仍为二叉树，设删除的结点由指针所指，其双亲结点由指针

1.p所指，并假设被删除结点是其双亲结点的右孩子f折半查找算法如下；int BinarySearchNODEa[],int n,int k/*在到中，用折半查找算法查找关键字等于的记录，查找成功返回该记录的下标，失败时返回T*/a

[0]a[nT]kint low,mid,high;low=0;high=n-l;whilelow=highmid=low+high/2;

2.编写顺序查找算法ifa[mid].key==k returnmid;顺序查找算法如下〈else ifa[mid]・key klow=mid+l;int searchNODEa[],int n,int k/*查找成功，返回查找到的记录的下else high=mid-l;标*/return-1;/*取后半查找区间*//*取前半查找区间*//*查找失败*//*在中顺序查找关键字等于的记录查找成功时返回该记录的下标，失败时返a[0ra[n-l]k回-1*/int i=0;/*没有查到同时查找过程没有结束,则继续查找*/whileina[i].key!=ki++；二/*查找成功*/if a[i].key kreturni;/*查找失败*/else return-1;。