《数据结构程序填空复习题》由会员分享，可在线阅读，更多相关《数据结构程序填空复习题（13页珍藏版）》请在金锄头文库上搜索。
1、数据结构程序填空复习题说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！一、线性表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是尾结点*
2、/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 *he
3、ad,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
4、=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
5、=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. 以下函数为链队列的入队操作
6、，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. 以下函数为链队列的出队操作（链队列带有头结点），出队结
7、点的数据域的值由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
8、）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为字
9、符型，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）Pos
10、torder(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）
