《数据结构》程序填空复习题

《数据结构》程序填空复习题说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！！！一、线性表1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。#defineNULL0voidmain(){NODEa,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d是尾结点*/head=（1）;a.next=&b;b.next=&c;c.next=&d;（2）;/*以上结束建表过程*/p=head;/*p为工作指针，准备输出链表*/do{printf(“%d\n”,（3）);（4）;}while(（5）);}答案：（1）&a（2）dnext=NULL（3）p-data（4）p=p-next（5）p!=NULL2.以下函数在head为头指针的具有头结点的单向链表中删除第i个结点，structnode{intdata;structnode*next;};typedefstructnodeNODEintdelete(NODE*head,inti){NODE*p,*q;intj;q=head;j=0;while((q!=NULL)&&(___(1)_____)){___(2)_____;j++;}if(q==NULL)return(0);p=___(3)_____;___(4)_____=p-next;free(___(5)_____);return(1);}答案：（1）ji-1（2）q=q-next（3）q-next（4）q-next（5）p3.将新元素插入到线性表中的第i位，MAX是数组的个数，a[0]用以存放线性表长度，b存放待插入的元素值，i存放插入的位置，n存放线性表长度{inta[MAX];inti,j,b,n;scanf(“%d%d%d”,&b,&i,&n);for(j=1;j=n;j++)scanf(“%d”,&a[j]);a[0]=n;for(j=n;（1）;j--)（2）;（3）;（4）;for(j=1;j=a[0];j++)printf(“%5d\n”,a[j]);}答案：（1）j=i（2）a[j+1]=a[j]（3）a[i]=b（4）a[0]=n+14.用头插法建立带头结点且有n个结点的单向链表的算法NODE*create(n){NODE*head,*p,*q;intip=(NODE*)malloc(sizeof(NODE));（1）;（2）;（3）;for(i=1;i=n;i++){p=(NODE*)malloc(sizeof(NODE));p-data=i;if(i==1)（4）;else{（5）;（6）;}}return(head);}答案：（1）head=p（2）p-next=NULL（3）q=p（4）p-next=NULL（5）p-next=q-next（6）q-next=p一、栈1.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc(___(1)_____);p-data=x;___(2)_____;}答案：（1）sizeof(structnode)（2）p-next=top（3）top=p二、队列1.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)___(1)_____;p-data=x;p-next=NULL;___(2)_____;rear=___(3)_____;}答案：（1）malloc(sizeof(structnode))（2）rear-next=p（3）p2.以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由x返回，front、rear分别是链队列的队头、队尾指针structnode{ElemTypedata;structnode*next;};structnode*front，*rear;ElemTypeOutQueue(){ElemTypex;if(___(1)_____){printf(队列下溢错误！\n);exit(1);}else{structnode*p=front-next;x=p-data;front-next=___(2)_____;if(p-next==NULL)rear=front;free(p);___(3)_____;}}答案：（1）front==rear（2）p-next（3）return(x)三、树1.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidPreorder(structBTreeNode*BT){if(BT!=NULL){（1）;（2）;（3）;}}答案：（1）printf(“%c”,BT-data)（2）Preorder(BT-left)（3）Preorder(BT-right)2.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidInorder(structBTreeNode*BT){if(BT!=NULL){（1）;（2）;（3）;}}答案：（1）Inorder(BT-left)（2）printf(“%c”,BT-data)（3）Inorder(BT-right)3以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。voidPostorder(structBTreeNode*BT){if(BT!=NULL){（1）;（2）;（3）;}}答案：（1）Postorder(BT-left)（2）Postorder(BT-right)（3）printf(“%c”,BT-data);四、图五、排序1．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。voidbsort(NODEa[],intn){NODEtemp;inti,j,flag;for(j=1;（1）;j++);{flag=0;for(i=1;（2）;i++)if(a[i].keya[i+1].key){flag=1;temp=a[i];（3）;（4）;}if(flag==0)break;}}程序中flag的功能是（5）答案：（1）j=n-1（2）i=n-j（3）a[i]=a[i+1]（4）a[i+1]=temp（5）当某趟冒泡中没有出现交换则已排好序，结束循环2.以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){inti,j,k;NODEtemp;for(i=1;i=___(1)_____;i++){k=i;for(j=i+1;j=___(2)_____;j++)if(a[j].keya[k].key)__(3)______;if(i!=k){temp=a[i];___(4)_____;____(5)____;}}}答案：（1）n-1（2）n（3）k=j（4）a[i]=a[k]（5）a[k]=temp3.直接插入排序算法Voiddisort(NODEa[],intn){intI,j;NODEtemp;for(i=1;in;i++){temp=a[i];（1）;while(j=0&&temp.keya[j].key){（2）;（3）;}（4）;}}答案：（1）j=i-1（2）a[j+1]=a[j]（3）j--（4）a[j+1]=temp4.快速排序voidquicksort(NODEa[],intstart,intend){intiI,j;NODEmid;if(start=end)return;（1）;（2）;mid=a[i];while(（3）){while(ij)&&a[j].keymid.key)（4）;;if(（5）;){（6）;;（7）;;}while(ij&&a[i].key=mid.key)（8）;;if(ij){（9）;;（10）;;}}a[i]=mid;（11）;;;}答案：（1）i=start（2）j=end（3）ij（4）j--也可能将此条语句写出，要填写其条件中的a[j].keymid.key（5）ij（6）a[i]=a[j]（7）i++（8）i++也可能将此条语句写出，要填写其条件中的a[i].key=mid.key（9）a[j]=a[i]（10）j--（11）quicksort(a,start,i-1)（12）quicksort(a,i+1,end)最后两句要填的概率会很高，要注意快速排序的考点很多，一般只会有三到四个空。5.直接选择排序voidselsort(NODEa[],intn){inti,j,k;NODEtemp;for(i=1;i=n-1;i++){（1）;for(j=（2）;j=n;j++)if(a[j].keya[k].key)（3）;if(（4）){（5）;（6）;（7）;}}}答案：（1）k=i（2）i+1（3）k=j（4）i!=k（5）temp=a[i]（6）a[i]=a[k]（7）a[k]=temp前四句较为重要6.堆排序中的筛选算法voidheapshift(NODEa[],intI,intn){NODEtemp;intj;temp=a[i];（1）;while(jn){if(j+1n&&a[j].keya[j+1].key)（2）;if(temp.keya[j].key){（3）;（4）;（5）;}elsebreak;}（6）;}答案：（1）j=2*i（2）j++（3）a[i]=a[j]（4）i=j（5）j=2*i（6）a[i]=temp这是构建的小根堆，若是大根堆，只要将if语句中的a[j].keya[j+1].key改为，再将第二个if语句中的改为即可7.堆排序voidheapsort(NODEa[],intn){intiNODEtemp;for(i=（1）;i=1;i--)（2）;for(i=n;i1;i--){temp=a[1];（3）;（4）;（5）;}}答案：（1）n/2（2）heapshift(a,i,n)（3）a[1]=a[i]（4）a[i]=temp（5）heapshift(a,1,i-1)8.两个有序序列的归并voidmerge(NODEa[],ints,intm,intn,NODEorder[]){inti=s,j=m+1,k=s;while((（1）)&&(（2）))if(a[i].key=a[j].key)（3）;else（4）;if(im)while(j=n)（5）;ElseWhile(i=m)（6）;}答案：（1）i=m（2）j=n（3）