《《數(shù)據(jù)結(jié)構(gòu)》程序填空復(fù)習(xí)題(總13頁)》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)》程序填空復(fù)習(xí)題(總13頁)（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、《數(shù)據(jù)結(jié)構(gòu)》程序填空復(fù)習(xí)題
說明：本文檔中涉及到的算法并非本書的全部，有些可根據(jù)此處的情況自行看書和作業(yè)題，黑色為綜合練習(xí)上的題目，紅色為我另增加的題，這些空的選擇是根據(jù)我個人的經(jīng)驗來決定的并不能完全代表中央電大的出卷老師，因此一定不能有肯定就考這些題目的想法。不能放棄其他內(nèi)容的復(fù)習(xí)，切記?。?！
一、線性表
1.設(shè)線性表為（6，10，16，4），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點中的數(shù)據(jù)。
#define NULL 0
void main( )
{NODE a,b,c,d,*head,*p;
a.data=6;
b.data=10;
c
2、.data=16;
d.data=4; /*d是尾結(jié)點*/
head= （1） ;
a.next=&b;
b.next=&c;
c.next=&d;
（2） ; /*以上結(jié)束建表過程*/
p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/
do
{printf(“%d\n”, （3） );
（4） ;
}while( （5） );
}
答案：
（1）&a
（2）dnext=NULL
（3）p->data
（4）p=p->next
（5）p!=N
3、ULL
2. 以下函數(shù)在head為頭指針的具有頭結(jié)點的單向鏈表中刪除第i個結(jié)點，
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);
4、
p= ___(3)_____;
___(4)_____=p->next;
free(___(5)_____);
return(1);
}
答案：
（1）jnext
（3）q->next
（4）q->next
（5）p
3.將新元素插入到線性表中的第i位，MAX是數(shù)組的個數(shù)，a[0]用以存放線性表長度，b存放待插入的元素值，i存放插入的位置，n存放線性表長度
{
int a[MAX];
int i,j,b,n;
scanf(“%d%d%d”,&b,&i,&n);
for(j=1;j
5、<=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+1
4.用頭插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的算法
NODE *create(n)
{
N
6、ODE *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） ;
}
}
7、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. 以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針
struct node
{ ElemType data;
struct node *next;
};
struct node *top ;
void Push(ElemType x)
{
struct node *p
8、;
p=(struct node*)malloc(___(1)_____);
p->data=x;
___(2)_____;
}
答案：
（1）sizeof (struct node)
（2）p->next=top
（3）top=p
二、 隊列
1. 以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針
struc
9、t 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;
10、
___(2)_____;
rear= ___(3)_____;
}
答案：
（1）malloc(sizeof (struct node))
（2）rear->next=p
（3）p
2. 以下函數(shù)為鏈隊列的出隊操作（鏈隊列帶有頭結(jié)點），出隊結(jié)點的數(shù)據(jù)域的值由x返回，front、rear分別是鏈隊列的隊頭、隊尾指針
struct node
{ ElemType data;
stru
11、ct node *next;
};
struct node *front，*rear;
ElemType OutQueue()
{
ElemType x;
if(___(1)_____) {
printf("隊列下溢錯誤！\n");
exit(1);
}
else {
12、 struct node *p=front->next;
x=p->data;
front->next= ___(2)_____;
if(p->next==NULL) rear=front;
free(p);
___(3)____
13、_;
}
}
答案：
（1）front= =rear
（2）p->next
（3）return(x)
三、 樹
1.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。
void Preorder (struct BTreeNode *BT)
{ if(BT!=NULL){
（1） ;
（2）
14、;
（3） ;
}
}
答案：
（1）printf(“%c”,BT->data)
（2）Preorder(BT->left)
（3）Preorder(BT->right)
2. 以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。
void Inorder (struct BTreeNode *BT)
{ if(BT!=NULL){
（1） ;
（2） ;
（
15、3） ;
}
}
答案：
（1）Inorder(BT->left)
（2）printf(“%c”,BT->data)
（3）Inorder(BT->right)
3 以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。
void Postorder (struct BTreeNode *BT)
{ if(BT!=NULL){
（1） ;
（2） ;
（3）
16、 ;
}
}
答案：
（1）Postorder(BT->left)
（2）Postorder(BT->right)
（3）printf(“%c”,BT->data);
四、 圖
五、 排序
1．以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，……，a[n]中的序列進行排序，完成程序中的空格部分，其中n是元素個數(shù)，要求按升序排列。
void bsort (NODE a[ ], int n)
{ NODE temp;
int i,j,flag;
for(j=1; （1） ;j++);
17、{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）當(dāng)某趟冒泡中沒有出現(xiàn)交換則已排好序，結(jié)束循環(huán)
2.
18、 以下函數(shù)為直接選擇排序算法，對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++)
19、if(a[j].key
20、 （1） ;
while(j>=0&&temp.key=end)
return;
（1） ;
21、 （2） ;
mid=a[i];
while( （3） )
{
while(imid.key)
（4） ;;
if( （5） ;)
{
（6） ;;
（7） ;;
}
while(i
22、art
（2）j=end
（3）imid.key
（5）i
23、
{
int i,j,k;
NODE temp;
for(i=1;i<=n-1;i++)
{
（1） ;
for(j= （2） ;j<=n;j++)
if(a[j].key
24、較為重要
6.堆排序中的篩選算法
void heapshift(NODE a[],int I,int n)
{
NODE temp;int j;
temp=a[i];
（1） ;
while(ja[j+1].key)
（2） ;
if(temp.key>a[j].key)
{
（3） ;
（4） ;
（5） ;
}
else
break;
}
（6） ;
}
答案：
（1）
25、j=2*i
（2）j++
（3）a[i]=a[j]
（4）i=j
（5）j=2*i
（6）a[i]=temp
這是構(gòu)建的小根堆，若是大根堆，只要將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） ;
}
}
26、
答案：
（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
27、） ;
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）空有較直接的關(guān)聯(lián)，因此一般情況下若要求填（3）（4）就不會要求填（5）（6），若（5）（6）位要填也是填其條件句
七、查找
28、
1. 以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-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
29、)/2;
if(a[mid].key==k)
return __(2)______;
else if(___(3)_____)
low=mid+1;
else __(4)______;
}
___(5)_____;
}
答案：
（1）low<=high
（2
30、）mid
（3）a[mid].key
31、 )
（4） ;
else
（5） ;;
}
else return -1;
}
答案：
（1）mid=(low+high)/2
（2）a[mid].key==k
（3）a[mid].key
32、ruct Bnode
{ int key;
struct Bnode *left;
struct Bnode *right;
} Bnode;
Bnode *BSearch(Bnode *bt, int k)
/* bt用于接收二叉排序樹的根結(jié)點的指針，k用以接收要查找的關(guān)鍵字*/
{ Bnode *p;
if(bt== ___(1)_____)
return (bt);
p=bt;
while
33、(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
《數(shù)據(jù)結(jié)構(gòu)》程序填空復(fù)習(xí)題(總13頁)
