国家开放大学最新《数据结构（本）》期末综合练习（程序填空题）测验答案解析

1、国家开放大学最新数据结构（本）期末综合练习（程序填空题）测验答案解析窗体顶端国家开放大学最新数据结构（本）期末综合练习（程序填空题）测验答案解析试题 1满分3.00标记试题试题正文以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。void Inorder(struct BTreeNode *BT) if(BT!=NULL) 正确答案是：Inorder(BT-left)得分 0.00/1.00 分正确答案是：printf(%c,BT-data)得分 0.00/1.00 分; Inorder(BT-r

2、ight);利用上述程序对下图进行遍历，结果是正确答案是：d b f e a c得分 0.00/1.00 分。（1）Inorder(BT-left)（2）printf(%c,BT-data)（3）d b f e a c试题 2满分3.00标记试题试题正文设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。struct node int data; struct node *next;typedef struct node NODE;#define NULL 0void main() NODE *head,*

3、p; p=head; /*p为工作指针*/ do printf(%dn,回答正确答案是：p-data得分 0.00/1.00 分); 正确答案是：p=p-next得分 0.00/1.00 分; while(回答正确答案是：p!=NULL得分 0.00/1.00 分);（1）p-data（2）p=p-next（3）p!=NULL试题 3满分5.00标记试题试题正文以下冒泡法程序对存放在a1，a2，an中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。void bsort (NODE a ,int n) NODE temp; int i,j,flag; for(j=1;回答

4、正确答案是：j=n-1)得分 0.00/1.00 分;j+) flag=0; for(i=1;回答正确答案是：iai+1.key) flag=1; temp=ai; 回答正确答案是：ai=ai+1)得分 0.00/1.00 分; 正确答案是：ai+1=temp得分 0.00/1.00 分; if(flag=0)break; 设有序列6，4，5，8，2，1，给出由该程序经过两趟冒泡后的结果序列回答正确答案是：4，5，2，1，6，8得分 0.00/1.00 分。（1）j=n-1（2）i=n-j（3）ai=ai+1（4）ai+1=temp（5）4，5，2，1，6，8试题 4满分5.00标记试题试题正

5、文以下函数为直接选择排序算法，对a1，a2，an中的记录进行直接选择排序，完成程序中的空格：typedef struct int key; NODE;void selsort(NODE a ,int n) int i,j,k; NODE temp; for(i=1;i=回答正确答案是：n-1得分 0.00/1.00 分;i+) k=i; for(j=i+1;j=回答正确答案是：n得分 0.00/1.00 分;j+) if(aj.keynext=NULL得分 0.00/1.00 分; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do printf(%dn,回答正

6、确答案是：p-data得分 0.00/1.00 分); 正确答案是：p=p-next得分 0.00/1.00 分; while(p!=NULL);画出按该程序建立的单向链表的示意图，说明程序运行结束后p的指向。回答正确答案是：P指向NULL得分 0.00/1.00 分（1）&a（2）d-next=NULL（3）p-data（4）p=p-next（5）P指向NULL试题 6满分5.00标记试题试题正文以下函数在a0到an-1中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格：typedef struct int key; NODE;int Bin

7、ary_Search(NODE a ,int n,int k) int low,mid,high; low=0; high=n-1; while(回答正确答案是：low=high得分 0.00/1.00 分) mid=(low+high)/2; if(amid.key=k) return回答正确答案是：mid得分 0.00/1.00 分; else if(回答正确答案是：amid.keyk得分 0.00/1.00 分) low=mid+1; else回答正确答案是：high=mid-1得分 0.00/1.00 分; return -1;设数组元素：a0=2；a1=5；a2=3；a3=4；a4=

8、9；a5=6；a6=1；a7=10；按上述程序查找元素5，能否成功查到，说明理由回答正确答案是：不能得分 0.00/1.00 分。（1）low=high（2）mid（3）amid.keyleft)得分 0.00/1.00 分;Inorder(BT-right);正确答案是：printf(%c,BT-data)得分 0.00/1.00 分;利用上述程序对下图进行遍历，结果是回答正确答案是：f,d,e,b,c,a得分 0.00/1.00 分。（1）Inorder(BT-left)（2）printf(%c,BT-data)（3）f,d,e,b,c,a试题 8满分3.00标记试题试题正文以下函数为链队

9、列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针struct node ElemType data; struct node *next;struct node *front,*rear;void InQueue(ElemType x) struct node *p; p=(struct node*)回答正确答案是：malloc(sizeof(struct node)得分 0.00/1.00 分; p-data=x; p-next=NULL; 正确答案是：rear-next=p得分 0.00/1.00 分; rear=回答正确答案是：p得分 0.00/1.00 分;（1）malloc(sizeof (struct node)（2）rear-next=p（3）p试题 9满分3.00标记试题试题正文设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同），写出相关语句：（1）使该单向链表成为单向循环链表；（2）删去a结点q=p;x=p-data;while(q-next!=NULL)q=q-next;正确答案是：q-next=he