2023年6月22日发(作者：)

- - -

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

说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他容的复习，切记！！！

一、线性表

1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。

#define NULL 0

void main( )

{NODE a,b,c,d,*head,*p;

=6;

=10;

=16;

=4; /*d是尾结点*/

head= （1） ;

=&b;

=&c;

=&d;

（2） ; /*以上结束建表过程*/

p=head; /*p为工作指针，准备输出链表*/

do

{printf(“%dn”, （3） );

（4） ;

- .可修编 . - - -

}while( （5） );

}

答案：

（1）&a

（2）dnext=NULL

（3）p->data

（4）p=p->next

（5）p!=NULL

2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点，

struct node

{ int data;

struct node *next;

};

typedefstruct 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）j

（2）q=q->next

（3）q->next

（4）q->next

（5）p

3.将新元素插入到线性表中的第i位，MAX是数组的个数，a[0]用以存放线性表长度，b存放待插入的元素值，i存放插入的位置，n存放线性表长度

- .可修编 . - - -

{

int a[MAX];

int i,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(“%5dn”,a[j]);

}

答案：

（1）j>=i

（2）a[j+1]=a[j]

（3）a[i]=b

（4）a[0]=n+1

4.用头插法建立带头结点且有n个结点的单向链表的算法

NODE *create(n)

{

NODE *head,*p,*q;

int i

p=(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为栈顶指针

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）p

2. 以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由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．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行排序，完成程序中的空格- .可修编 . - - -

部分，其中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(a[i].key>a[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]中的记录进行直接选择排序，完成程序中的空格

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(a[j].key

if(i!=k)

{

temp=a[i];

___(4)_____;

____(5)____;

- .可修编 . - - -

}

}

}

答案：

（1）n-1

（2）n

（3）k=j

（4）a[i]=a[k]

（5）a[k]=temp

3.直接插入排序算法

Void disort(NODE a[],int n)

{

int I,j;

NODE temp;

for(i=1;i

{

temp=a[i];

（1） ;

while(j>=0&&

{

（2） ;

（3） ;

}

（4） ;

}

}

答案：

（1）j=i-1

（2）a[j+1]=a[j]

（3）j--

（4）a[j+1]=temp

4.快速排序

void quicksort(NODE a[],int start,int end)

{

int iI,j;

NODE mid;

if(start>=end)

return;

（1） ;

（2） ;

mid=a[i];

while( （3） )

- .可修编 . - - -

{

while(i)

（4） ;;

if( （5） ;)

{

（6） ;;

（7） ;;

}

while(i

（8） ;;

if(i

{

（9） ;;

（10） ;;

}

}

a[i]=mid;

（11） ;;

;

}

答案：

（1）i=start

（2）j=end

（3）i

（4）j-- 也可能将此条语句写出，要填写其条件中的a[j].key>

（5）i

（6）a[i]=a[j]

（7）i++

（8）i++ 也可能将此条语句写出，要填写其条件中的a[i].key<=

（9）a[j]=a[i]

（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(a[j].key

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.堆排序中的筛选算法

void heapshift(NODE a[],int I,int n)

{

NODE temp;int j;

temp=a[i];

（1） ;

while(j

{

if(j+1a[j+1].key)

（2） ;

if(>a[j].key)

{

（3） ;

（4） ;

（5） ;

}

else

break;

}

（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].key>a[j+1].key改为<，再将第二个if语句中的>改为<即可

7.堆排序

void heapsort(NODE a[],int n)

{

int i

NODE temp;

for(i= （1） ;i>=1;i--)

（2） ;

for(i=n;i>1;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.两个有序序列的归并

void merge(NODE a[],int s,int m,int n,NODE order[])

{

int i=s,j=m+1,k=s;

while(( （1） )&&( （2） ))

if(a[i].key<=a[j].key)

（3） ;

else

（4） ;

if(i>m)

while(j<=n)

（5） ;

Else

While(i<=m)

（6） ;

}

答案：

（1）i<=m

- .可修编 . - - -

（2）j<=n

（3）order[k++]=a[i++] 可保留此句，将其条件语句去掉

（4）order[k++]=a[j++] 可保留此句，将其条件语句去掉

（5）Order[k++]=a[j++] 可保留此句，将其条件语句去掉

（6）order[k++]=a[i++] 可保留此句，将其条件语句去掉

第（3）（4）空与第（5）（6）空有较直接的关联，因此一般情况下若要求填（3）（4）就不会要求填（5）（6），若（5）（6）位要填也是填其条件句

七、查找

1. 以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格

typedef struct

{ int key;

……

}NODE;

int Binary_Search(NODEa[],int n, int k)

{

int low,mid,high;

low=0;

high=n-1;

while(___(1)_____)

{

mid=(low+high)/2;

if(a[mid].key==k)

return

__(2)______;

else if(___(3)_____)

low=mid+1;

else

__(4)______;

}

___(5)_____;

}

答案：

（1）low<=high

（2）mid

（3）a[mid].key

（4）high=mid-1

（5）return -1;

此为折半查找的非递归算法

2. 1. 以下函数在a[0]到a[n-1]中，用折半查找的递归算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格

int Binary_Search(NODE a[],int low,int high,int k)

{

- .可修编 . - - -

if(low<=high)

{

int mid= （1） ;

if( （2） )

return mid;

else if( （3） )

（4） ;

else

（5） ;;

}

else return -1;

}

答案：

（1）mid=(low+high)/2

（2）a[mid].key==k

（3）a[mid].key

（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)

/* bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/

{ Bnode *p;

if(bt== ___(1)_____)

return (bt);

p=bt;

while(p->key!= __(2)______)

{ if(kkey)

___(3)_____;

else

___(4)_____;

if(p==NULL) break;

}

Return(___(5)_____);

}

答案：

（1）NULL

（2）k

- .可修编 . - - -

（3）p=p->left

（4）p=p->right

（5）p

- .可修编 .