《数据结构 程序填空题.docx》由会员分享，可在线阅读，更多相关《数据结构 程序填空题.docx（8页珍藏版）》请在三一文库上搜索。
1、程序填空题,算法设计题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;idata=i;（2）p-next=NULL;（3）q-next=p;（4） q=p;return(head);2下列是用头插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内填上适当的语句。NODE *cr
2、eate2(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;idata=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
3、;j=0;while(q!=NULL)&(jnext;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
4、”,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
5、,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 中。
6、（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 in
7、itqueue(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-nex
8、t=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; Q-rear-next=t-next;/*t 指向第一个结点*/*引成循环链*/free(t);elemtype gethead(Li
9、nkQueue *Q)/*取队首元素算法*/if (Q-rear=NULL)printf(队列为空!n);elsereturn(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)
10、printf(%c ,p-data);p=p-next;printf(%cn,p-data);1. 下面函数的功能是返回二叉树 BT 中值为 X 的结点所在的层号，请在划有横线的地方填写合适内容。int NodeLevel(struct BinTreeNode* BT, char X)if(BT=NULL) return 0;else if(BT-data=X) return 1;/*向子树中查找 X 结点*/else /*空树的层号为 0*/*根结点的层号为 1*/int c1=NodeLevel(BT-left,X);if(c1=1) _(1) return c1+1_;int c2=_(
11、2) NodeLevel(BT-right,X)_ _;if _(3)_ (c2=1) return c2+1_;/若树中不存在 X 结点则返回 0else return 0;2. 下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的地方填写合适内容。void dfstree(adjmatrix GA, int i, int n)int j;visitedi=1;(1) for(j=0; jdata=p-data;t-lchild=CopyTree(p-lchild);t-rchild=CopyTree(p-rchild);return(t);else
12、return(NULL);/*CopyTree*/2根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数 BT 初始指向二叉树的根结点。int BTreeLeafCount(struct BTreeNode* BT);int BTreeLeafCount(struct BTreeNode* BT)if(BT=NULL) return 0;else if(BT-left=NULL & BT-right=NULL) return 1;else return BTreeLeafCount(BT-left)+BTreeLeafCount(BT-right);1以下直接输
13、入排序算法对存放在 a0,a1,an-1中，长度为 n 的记录序列按关键字 key 由小到大排序，完成程序中的空格部分。void disort (NODE a , int n)int I,j;NODE temp; /*工作单位*/ for (i=1;i=0_&temp.keyaj.key) aj+1=_ _ aj_ _ j-_aj+1=_ temp _;2以下冒泡法程序对存放在 a1，a2，an中的序列进行冒泡排序完成程序中的空格部分，其中 n 是元素个数，程序按升序排列。Void bsort (NODEa , int) NODE temp;int i,j,flag;for(j=1; （1）j
14、=n-1;j+);flag=0;for(i=1; （2）iai+1.key)flag=1;temp=ai;（3）ai=ai+1;（4）ai+1=temp;if(flag= =0)break;程序中 flag 的功能是 （5）当某趟冒泡中没有出现交换则已排好序结束循环五、算法设计题1写出在二叉树中删除一个结点的算法，且使删除后仍为二叉树，设删除的结点由指针 p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。折半查找算法如下；int Binary_Search(NODE a,int n, int k)/* 在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功
15、返回该记录的下标，失败时返回-1 */int low,mid,high;low=0;high=n-1;while(low=high)mid=(low+high)/2;if(amid.key=k)return mid;/*查找成功，返回查找到的记录的下标*/else if(amid.keyk)low=mid+1;else high=mid-1;/*取后半查找区间*/*取前半查找区间*/return -1;/*查找失败*/2编写顺序查找算法。顺序查找算法如下：int search(NODE a,int n, int k)/*在a0an-1中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/int i=0;while(in & ai.key!=k) /*没有查到同时查找过程没有结束，则继续查找*/i+;if(ai.key=k)/*查找成功*/return i;else return -1;/*查找失败*/