国家开放大学电大《数据结构》网络课程序填空题题库及答案

国家开放大学试题国家开放大学电大数据结构网络课程序填空题题库及答案程序填空题题目1设线性表以不带头结点的单向链表存储,链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data, 完成程序中空格部分。#define NULL 0void main()( NODE *head , *p ;p=head;/*p为工作指针*/do p-data yprintf( dn, ;p=p-next v9? pl=NULL Vwhile ;)p-datap=p-next p!=NULL题目2设有一个头指针为head的不带头结点单向链表,p、q是指向链表中结点类型的指针变量,p指向链表中结点a,(设链表中没有结点的数据域与结点a的数据域相同),写出相关语句(1) 使该单向链表成为单向循环链表(2) 插入结点s,使它成为a结点的直接前驱q=p; x=p-data;I q-nextl=NULL /while) q=q-next;q-next=head;q=P; p-pnext;while(p-data!=x) q=P;p=p-next 寸s-next=p;q-next=s v题目3以下函数为链栈的进栈操作,x是要进栈的结点的数据域,top为栈顶指针 struct node( ElemType data;struct node *next;struct node *top ;void Push (ElemType x)(struct node *p;A slzeof (struct node) vp= (struct node*)malloc p-data=x;p-next=toptop=p5)A. sizeof (struct node) top=p p-next=top题目4以下函数为链队列的入队操作,x为要入队的结点的数据域的值,front, rear分别链队列的队头、队尾指针struct node( ElemType data;struct node *next;struct node *front, *rear;void InQueue(ElemType x)struct node *p;(sizeof (struct node) / p= (struct node*) ma Hoc;p-data=x;p-next二NULL;rear-next-prear=国家开放大学试题利用上述程序对左图诳行后序遍历,结果是;d.e.b.f.c.a题目5以下程序是后序遍历二叉树的递归算法的程序,完成程序中空格部分树结构中左、右指针域分别为left和right, 数据域data为字符型,BT指向根结点。完成程序中空格部分。voidinorder (struct BTreeNode *BT)(if( BTI=NULL)(lnarder(BT-left);lnorder(BT- right) vpnntf(%c,BT-data) /题目6以下程序是中序遍历二叉树的递归算法的程序,完成程序中空格部分树结构中左、右指针域分别为left和right, 数据域data为字符型,BT指向根结点。void Inorder (struct BTreeNode rBT)if(BTI=NULL)(lnarder(8T-left);)pnntf(,%c,lBT-data) v ;利用上述程序对右图进行中序遍历,结果是;d.b.e.a.f.clnorder(BT-rlght) v .题目7以下函数是二叉排序树的查找算法,若二叉树为空,则返回根结点的指针,否则,返回值是指向树结点的结构指 针P (查找成功p指向查到的树结点,不成功p指向为NULL)完成程序中的空格typedef struct Bnode( Int key;struct Bnodestruct Bnode *right; Bnode;Bnode *BSearch(Bnode *bt, Int k)r btffi于按枕。排字闵间艮结点的指针,k用以挎收要直我的关键字兮; Bnode *p;lt(bt= ;NULL 5 )return (bt);:pMbtj whllB(p-keyi- k v)ip=p-left 5 ;else p=p-right j;lf(p=NULL) break;retum(国家开放大学试题题目8以下程序是折半插入排序的算法设待排序的记录序列存放在a【l】,a【n】中,以a【0】作为辅助工作单元,程序是要把a【i】插入到已经有序的序列 a【l】,中ovoid binsort (NODE a【 】jnt n)Mtxjj础mfar (1=2 ; l= n y ;1廿)曲咖* a【l】Jtey;户卜1苹j while:(m =($刑2 寸if( xa【m】.key)j=m-1 yelses=m+i yfor ( K斗 1:40=1+1*-)a|k+1】 5 =a【k】:aD+1】=a【0】i