数据结构-程序填空题.docx

《数据结构-程序填空题.docx》由会员分享，可在线阅读，更多相关《数据结构-程序填空题.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、程序填空题，算法设计题1、1.下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。 N0DE*create1(n)/*对线性表(12.,n),建立带头结点的单向链表V(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=N U LI;(3) q-next=p;(-U) q= P； ) return(head); )2.下列是用头插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。 NO

2、DE *create2(n)/*对线性表(n,n-1,.,1),建立带头结点的线性链表*/(NODE *head,*p,*q;int i;p=(NODE *)malloc(sizeof(NODE);CO_head=p;p-next=NULL;_q=P；for(i=1 ;idata=i; 刖=1)(3) p-next=NULI;else X4)p-next=q-next;q-next=p; ) return(head);)3.下列是在具有头结点单向列表中删除第i个结点，请在空格内填上适当的语句。 int delete(NODE *head,int i)NODE *p,*q; intj;q=hea

3、d;j=；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; q-front-next=p-

4、next;printf( a%4dv , p-data);(2) free(p);3J_Q-rear=q-front ;/*队空时， 头尾指针指向头结点*/1 .设栈S和队列Q的初始状态为空，元素e1 ,e2,e3,e4,e5和e6挨次通过S, 一个元素出栈后即进队列Q,若6 个元素出队的序列是e25e4,e35e63e5,e1,则栈S的容量至少应该是多少？答：出队序列是e2, e4, e3, e6, e5, el的过程:el入栈（栈底到栈顶元素是el）e2入栈（栈底到栈顶元素是el,e2）e2出栈（栈底到栈顶元素是el）（4） e3入栈（栈底到栈顶元素是el,e3）e4入栈（栈底到栈顶元素是

5、el,e3,e4）（6） e4出栈（栈底到栈顶元素是el,e3）e3出栈（栈底到栈顶元素是el）（8） e5入栈（栈底到栈顶元素是el,e5）（9） e6入栈（栈底到栈顶元素是el,e5,e6）00） e6出栈（栈底到栈顶元素是el,e5）（ID e5出栈（栈底到栈顶元素是el）el出栈（栈底到栈顶元素是空）栈中最多时有3个元素，所以栈S的容量至少是3o2.假设用循环单链表实现循环队列，该队列只使用一个尾指针rear,其相应的存储结构和基本算法如下; (1)初始化队列initqueue(Q):建立一个新的空队列Q。(2)入队列enqueue(Q, x):将元素x插入到队列Q中。(3)出队列de

6、lqueue(Q):从队列Q中退出一个元素。(4)取队首元素gethead(Q):返回当前队首元素。(5)判断队列是否为空：emptyqueue(Q)。(6)显示队列中元素：dispqueue(Q) o 算法设计如下：/ *惟独一个指针r e a r的链式队的基本操作*/#include typedef char elemtype;struct node /*定义链队列结点*/ (elemtype data;struct node *next;)；typedef struct queue /*定义链队列数据类型*/( struct node *rear; LinkQueue;void init

7、queue(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

8、-next=s; /*将 s 链接到队尾*/Q-rear=s; /*Q-rear 指向队尾*/ s-next=p;void del queue (LinkQueue *Q) /*出队算法*/ (struct node *t;i f (Q-rear=N(JLL)printf (队列为空！ n); return (0);/*惟独一个结点时*/else if (Q-rear-next=Q-rear) (t=Q-rear;Q-rear=NULL;)else /*有多个结点时*/*t指向第一个结点*/ /*引成循环链*/*取队首元素算法*/(t=Q-rear-next;Q-rear-next=t-nex

9、t;)free (t); elemtype gethead(LinkQueue *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

10、;printf (队列元素素);while (p!=Q-rear)printf (，z%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;/*空树的层号为 0*/else if (BT-data=X) return 1; /*根结点的层号为 1*/*向子树中查找X结点*/ else int cl=NodeLevel(BT-lef

11、t, X);if(cl=l)_U) return cl+1；int c2= (2) NodeLevel (BT-right, X) ；if(3) (c2=l) return c2+l ；若树中不存在X结点则返回0else return 0;2,下面函数的功能是按照图的深度优先搜索遍历的方法，输出得到该图的生成树中的各条边，请在划有横线的 地方填写合适内容。void dfstree (adjmatrix GA, int i, int n)(int j;visitedi=l;-Cl) for(j=0; jdata=p-data;t-1ch i1d=CopyTree (p-1ch i1d); t-r

12、child=CopyTree (p-rchiId); return (t);) else 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 BTreeL

13、eafCount(BT-left)+BTreeLeafCount(BT-right);3 .以下直接输入排序算法对存放在a0,a1, 中，长度为n的记录序列按关键字key由小到大排序， 完成程序中的空格部份。void disort (NODE a , int n) int l,j;NODE temp; /*工作单位*/ for (i=1 ;i=O&temp.keyaj.key)aj+1=一尸 aj+1=_ temp _;) 4 .以下冒泡法程序对存放在a1, a2,an中的序列进行冒泡排序完成程序中的空格部份，其中n是元素 个数，程序按升序罗列。Void bsort (NODE a, int)

14、 NODE temp;int i,j,flag;for(j=1; (1) j=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 BinarySearch(NODE a,int n, in

15、t k)/*在a0到anT中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回T */int low, mid, high;low=0;high=n-l;while(low=high)mid=(low+high)/2;if(amid. key=k) return mid;else if(amidkeyk) low=mid+l;else high=mid-l;)return -1;)2.编写顺序查找算法。顺序查找算法如下：int search(NODE a, int n, int k)/*查找成功，返回查找到的记录的下标*/*取后半查找区间*/*取前半查找区间*/*查找失败*/*在a0ran-l中顺序查找关键字等于k的记录。查找成功时返回该记录的下标，失败时返回-1*/ (int i=0;while(in & ai.key!=k) /*没有查到同时查找过程没有结束,则继续查找*/i+；if (ai. key二k)/*查找成功*/return i;else return -1;/*查找失败*/)