《《数据结构》程序填空复习题.docx》由会员分享，可在线阅读，更多相关《《数据结构》程序填空复习题.docx（15页珍藏版）》请在三一文库上搜索。
1、精品文档数据结构程序填空复习题说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题， 黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决 定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不 能放弃其他内容的复习，切记！ !！一、线性表1. 设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链 表中各结点中的数据。#defi ne NULL 0void mai n（）NODE a,b,c,d,*head,*p;a. data=6;b. data=10;c. data=16;d. da
2、ta=4; /*d 是尾结点 */head= （ 1）;a. n ext=&b;b. n ext=&c;c. n ext=&d;（2）;_/* 以上结束建表过程*/p=head; /*p为工作指针，准备输出链表*/doprintf（%dn” _（ 3）;（4）;while（ _（ 5）;答案：（1）&a（2）d next=NULL（3） p->data（4） p=p->next（5）p!=NULL2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点,struct node int data;struct node *n ext;ty
3、pedef struct n ode NODE int delete（NODE *head,i nt i ） NODE *p,*q;int j； q=head;j=0；while(q!=NULL)&&( _)(2);j+；if(q=NULL)return(O);p=;(4)=p->n ext;free(_);return(1);答案：(1) j<i-1(2) q=q_>next(3) q->next(4) q_>next(5) p3.将新元素插入到线性表中的第i位，MAX是数组的个数，a0用以存放线性表长度，b存 int aMAX;放待插入的元素值
4、，i存放插入的位置，n存放线性表长度int i,j,b,n;sca nf( %d%d%d&b, & i,&n); for(j=1;j<=n ;j+) scanf( %c” &aj);a0=n;for(j=n; (1) ;j-_-)(2) ;(3) ;(4) ;for(j=1;j<=a0;j+)printf(%5dn”aj);答案：(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
5、*)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为栈顶指针struct node ElemType dat
6、a;struct node *n ext;；struct node *top ;void Push(ElemType x)struct node *p;p=(struct node*)malloc(1);p->data=x;答案：(1) sizeof (struct no de)(2) p_>next=top(3) top=p二、队列分别1. 以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear是链队列的队头、队尾指针struct node ElemType data;struct node *n ext;struct node *front ， *rea
7、r;void lnQueue(ElemType x)struct node *p;p= (struct node*)(1) ;p->data=x;p->next=NULL;(2) ;rear=(3) ;答案：(1) malloc(sizeof (struct no de)(2) rear->next=p(3) p，出队结点的数据域的值由2. 以下函数为链队列的出队操作(链队列带有头结点) 回，front、rear分别是链队列的队头、队尾指针struct node ElemType data;struct node *n ext;struct node *front ， *re
8、ar;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，数据域d
9、ata为字符型，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 In order （struct BTreeNode *BT） if（BT!=NULL）（1）；（2）;（3）;
10、答案：（1）In order（BT->left）（2） printf（“ c” ,BT->data）（3）In order（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-&g
11、t;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.key>ai+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)
12、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.key<ak.key) _if(i!=k)temp=ai;(4);(5);答案：(1) n-1（2）n（3）k=j(4)ai=ak(5) ak=temp3. 直接插入排序
13、算法Void disort(NODE a,i nt n) int I,j;NODE temp; for(i=1;i< n; i+)temp=ai;(1) ;while(j>=0&&temp.key<aj.key)(2)(3)答案：(1) j=i-1(2) aj+1=aj(3) j-(4) aj+1=temp4. 快速排序void quicksort(NODE a,int start,int end) int il,j;NODE mid; if(start>=e nd) return;(1)-；_ (2) mid=ai;while( _ (3) _)_wh
14、ile(i<j) &&aj.key>mid.key) (4)if( ( 5) _;)(6)(7) while(i<j &&ai.key<=mid.key)(8) ;if(i<j)(9) ; (10) ;ai=mid;(11)-;答案:(1) i=start(2) j=end(3) i<j也可能将此条语句写出，要填写其条件中的aj.key>mid.key(4) j-7欢迎下载精品文档(5) i<j(6) ai=aj(7) i+(8) i+也可能将此条语句写出，要填写其条件中的ai.key<=mid.key(9)
15、 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);(3)for(j= _ (2);j<=n;j+)if(aj.key<ak.key)if( (4)_)(5)_;(6)_;(7)_;答案：(1)k=i(2)i+1(3)k=j(4) i!=k(5)temp=ai(6)ai=a
16、k(7) ak=temp前四句较为重要6. 堆排序中的筛选算法void heapshift(NODE a,int I,int n) NODE temp;i nt j;temp=ai;while(j< n)if(j+1< n&&aj.key>aj+1.key)(2) ;if(temp.key>aj.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.key>aj+1.key 改为 <,
17、再将第二个if语句中的 >改为 <即可7. 堆排序void heapsort(NODE a,int n)int iNODE temp;for(i= _ (1) _;i>=1;i-)(2) ；for(i=n; i>1;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)11欢迎下载8.两个有序序列的归并void merge(NODE a,int s,int m,int n,NODE order)int i=s,j=m+1,
18、k=s;while( (1)&&(2)if(ai.key<=aj.key)(3)；else(4)if(i>m)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）就不会
19、要求填（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（ ）low=mid+1;else_（4） ;（5） ；答案：（1） low&l
20、t;=high（2）mid（3） amid.key<k;（4） high=mid-1（5） return -1;此为折半查找的非递归算法2. 1.以下函数在a0到an-1中，用折半查找的递归算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格int Bin ary_Search（NODE a,i nt low,i nt high,i nt k）if（low<=high） int mid= （ 1）_;_if（ （ 2）_）_return mid;else if（ （ 3）_（4）;else（5）；else return -1;答案：（1）mid=（
21、low+high）/2（2）amid.key=k（3）amid.key<k（4）return（a,low,mid-1,k）（5）return（a,mid+1,high,k）3. 以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点，不成功p指向为NULL完成程序中的空格typedef struct Bnode int key;struct Bnode *left;struct Bnode *right; Bnode;Bnode *BSearch(Bnode *bt, int k)k 用以接收要查找的关键字 */* bt 用于接收二叉排序树的根结点的指针， Bnode *p;if(bt=_(1) )return (bt);p=bt;while(p->key!=_(2) ) if(k<p->key)_(3) ;else_(4) ;if(p=NULL) break;Return(_(5) );答案：(1)NULL（2）k(3) p=p->left(4) p=p->right（5）p15 欢。迎下载欢迎您的下载，资料仅供参考!致力为企业和个人提供合同协议， 策划案计划书，学习资料等等打造全网一站式需求