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

数据结构程序填空复习题说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！一、线性表1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) NODE a,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(“%dn”, （3） ); （4） ; while( （5） );答案：（1）&a（2）dnext=NULL（3）p-data（4）p=p-next（5）p!=NULL2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点， struct node int data;struct node *next;typedef struct node NODE int delete(NODE *head,int i )NODE *p,*q; int j; 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）jnext（3）q-next（4）q-next（5）p3.将新元素插入到线性表中的第i位，MAX是数组的个数，a0用以存放线性表长度，b存放待插入的元素值，i存放插入的位置，n存放线性表长度int aMAX;int i,j,b,n;scanf(“%d%d%d”,&b,&i,&n);for(j=1;j=n;j+)scanf(“%d”,&aj);a0=n;for(j=n; （1） ;j- -) （2） ; （3） ; （4） ;for(j=1;j=i（2）aj+1=aj（3）ai=b（4）a0=n+14.用头插法建立带头结点且有n个结点的单向链表的算法NODE *create(n)NODE *head,*p,*q;int ip=(NODE *)malloc(sizeof(NODE); （1） ; （2） ; （3） ;for(i=1;idata=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为栈顶指针struct node ElemType data;struct node *next;struct node *top ;void Push(ElemType x) struct node *p; p=(struct node*)malloc(_(1)_); p-data=x; _(2)_; 答案：（1）sizeof (struct node)（2）p-next=top（3）top=p二、 队列1. 以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node *next;struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p-data=x; p-next=NULL; _(2)_; rear= _(3)_; 答案：（1）malloc(sizeof (struct node)（2）rear-next=p（3）p2. 以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由x返回，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node *next;struct node *front，*rear; ElemType OutQueue() ElemType x; if(_(1)_) printf(队列下溢错误！n); exit(1); else struct node *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指向根结点）。void Preorder (struct BTreeNode *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指向根结点）。void Inorder (struct BTreeNode *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指向根结点）。void Postorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 答案：（1）Postorder(BT-left)（2）Postorder(BT-right)（3）printf(“%c”,BT-data);四、 图五、 排序1以下冒泡法程序对存放在a1，a2，an中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.keyai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break; 程序中flag的功能是（5） 答案：（1）j=n-1（2）i=n-j（3）ai=ai+1（4）ai+1=temp（5）当某趟冒泡中没有出现交换则已排好序，结束循环2. 以下函数为直接选择排序算法，对a1,a2,an中的记录进行直接选择排序，完成程序中的空格typedef struct int key;NODE; void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=1;i= _(1)_;i+) k=i; for(j=i+1;j= _(2)_;j+) if(aj.keyak.key) _(3)_; if(i!=k) temp=ai;_(4)_;_(5)_;答案：（1）n-1（2）n（3）k=j（4）ai=ak（5）ak=temp3.直接插入排序算法Void disort(NODE a,int n)int I,j;NODE temp;for(i=1;i=0&temp.key=end)return; （1） ; （2） ;mid=ai;while( （3） )while(imid.key) （4） ;if( （5） ;) （6） ; （7） ;while(ij&ai.key=mid.key) （8） ;if(ij) （9） ; （10） ;ai=mid; （11） ;答案：（1）i=start（2）j=end（3）imid.key（5）ij（6）ai=aj（7）i+（8）i+也可能将此条语句写出，要填写其条件中的ai.key=mid.key（9）aj=ai（10）j-（11）quicksort(a,start,i-1)（12）quicksort(a,i+1,end)最后两句要填的概率会很高，要注意快速排序的考点很多，一般只会有三到四个空。5.直接选择排序void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=1;i=n-1;i+) （1） ;for(j= （2） ;j=n;j+)if(aj.keyak.key) （3） ;if( （4） ) （5） ; （6） ; （7） ;答案：（1）k=i（2）i+1（3）k=j（4）i!=k（5）temp=ai（6）ai=ak（7）ak=temp前四句较为重要6.堆排序中的筛选算法void heapshift(NODE a,int I,int n)NODE temp;int j;temp=ai; （1） ;while(jn)if(j+1aj+1.key) （2） ;if(temp.keyaj.key) （3） ; （4） ; （5） ;elsebreak; （6） ;答案：（1）j=2*i（2）j+（3）ai=aj（4）i=j（5）j=2*i（6）ai=temp这是构建的小根堆，若是大根堆，只要将if语句中的aj.keyaj+1.key改为改为=1;i-) （2） ;for(i=n;i1;i-)temp=a1; （3） ; （4） ; （5） ;答案：（1）n/2（2）heapshift(a,i,n)（3）a1=ai（4）ai=temp（5）heapshift(a,1,i-1)8.两个有序序列的归并void merge(NODE a,int s,int m,int n,NODE order)int i=s,j=m+1,k=s;while( （1） )&( （2） )if(ai.keym)while(j=n) （5） ;ElseWhile(i=m) （6） ;答案：（1）i=m（2）j=n（3）orderk+=ai+可保留此句，将其条件语句去掉（4）orderk+=aj+可保留此句，将其条件语句去掉（5）Orderk+=aj+可保留此句，将其条件语句去掉（6）orderk+=ai+可保留此句，将其条件语句去掉第（3）（4）空与第（5）（6）空有较直接的关联，因此一般情况下若要求填（3）（4）就不会要求填（5）（6），若（5）（6）位要填也是填其条件句七、查找1. 以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; 答案：（1）low=high（2）mid（3）amid.keyk;（4）high=mid-1（5）return -1;此为折半查找的非递归算法2. 1. 以下函数在a0到an-1中，用折半查找的递归算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格int Binary_Search(NODE a,int lo