试题四（共 15 分）阅读以下说明和 C 函数，填补函数中的空缺，将解答填入答题纸的对应栏内。【说明】简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。函数 enqueue（queue *q，KeyType new_elem） 的功能是将元素new_elem 加入队尾。函数 Dnqueue（queue *q，KeyType *elem）的功能使将非空队列的队头元素出队（从队列中删除），并通过参数带回刚出队的元素。用单向循环链表表示的队列如图 4-1 所示。图 4-1 单向循环链表表示的队列示意图队列及链表结点等相关类型定义如下:enum {errOr， OK};typedef int KeyType;typedef struct qNode﹛KeyType data;Struct qNode*next;﹜qNode，*Linkqueue; Typedef struct﹛int size;Link:queue rear;}queue; 【C 函数】int enqueue（queue*q,KeyType new_elem）﹛ ／／元素 new_elem 入队列qNode*p;P=（qNode*）malloc（sizeof（qNode））;if（!p）return errOr;P->data=new_elem;if（q->rear）﹛P->next=q->rear->next;（）;﹜elseP->next=p;﹙﹚;q->size++;return OK;﹜ int Dequeue（queue*q,KeyType*elem）﹛ ／／出队列qNode*p;if（0＝＝q->size） ／／是空队列return errOr；P=（）; ／／令 p 指向队头元素结点*elem =p->data;q->rear->next=（）; ／／将队列元素结点从链表中去除if（（）） ／／被删除的队头结点是队列中唯一结点q->rear=NULL ／／变成空队列free（p）;q->size--;return OK;﹜
试题四（共 15 分）阅读以下说明和 C 函数，填补函数中的空缺，将解答填入答题纸的对应栏内。【说明】简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。函数 enqueue（queue *q，KeyType new_elem） 的功能是将元素new_elem 加入队尾。函数 Dnqueue（queue *q，KeyType *elem）的功能使将非空队列的队头元素出队（从队列中删除），并通过参数带回刚出队的元素。用单向循环链表表示的队列如图 4-1 所示。
图 4-1 单向循环链表表示的队列示意图队列及链表结点等相关类型定义如下:enum {errOr， OK};typedef int KeyType;typedef struct qNode﹛KeyType data;Struct qNode*next;﹜qNode，*Linkqueue; Typedef struct﹛int size;Link:queue rear;}queue; 【C 函数】int enqueue（queue*q,KeyType new_elem）﹛ ／／元素 new_elem 入队列qNode*p;P=（qNode*）malloc（sizeof（qNode））;if（!p）return errOr;P->data=new_elem;if（q->rear）﹛P->next=q->rear->next;（）;﹜elseP->next=p;﹙﹚;q->size++;return OK;﹜ int Dequeue（queue*q,KeyType*elem）﹛ ／／出队列qNode*p;if（0＝＝q->size） ／／是空队列return errOr；P=（）; ／／令 p 指向队头元素结点*elem =p->data;q->rear->next=（）; ／／将队列元素结点从链表中去除if（（）） ／／被删除的队头结点是队列中唯一结点q->rear=NULL ／／变成空队列free（p）;q->size--;return OK;﹜
图 4-1 单向循环链表表示的队列示意图队列及链表结点等相关类型定义如下:enum {errOr， OK};typedef int KeyType;typedef struct qNode﹛KeyType data;Struct qNode*next;﹜qNode，*Linkqueue; Typedef struct﹛int size;Link:queue rear;}queue; 【C 函数】int enqueue（queue*q,KeyType new_elem）﹛ ／／元素 new_elem 入队列qNode*p;P=（qNode*）malloc（sizeof（qNode））;if（!p）return errOr;P->data=new_elem;if（q->rear）﹛P->next=q->rear->next;（）;﹜elseP->next=p;﹙﹚;q->size++;return OK;﹜ int Dequeue（queue*q,KeyType*elem）﹛ ／／出队列qNode*p;if（0＝＝q->size） ／／是空队列return errOr；P=（）; ／／令 p 指向队头元素结点*elem =p->data;q->rear->next=（）; ／／将队列元素结点从链表中去除if（（）） ／／被删除的队头结点是队列中唯一结点q->rear=NULL ／／变成空队列free（p）;q->size--;return OK;﹜
参考解析
解析：（1）Q→rear→next=p（2）Q→rear=p（3）Q→rear→next（4）p→next（5）Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1
【解析】
本题考察C语言指针与链表的知识，为入队列和删除队列问题。对于入队列，那么当队列Q不为空时，P的队尾t要指向原Q的队尾指向的元素，即：P->next=Q->rear->next，Q的队尾要指向p，即：Q→rear→next=p。当队列Q为空时，插入p元素，则p的队尾指向p自身，即：p→next=p，且整个队列Q的队尾也是p，即：Q→rear=p。对于队列删除元素p，先判断Q是否为空，为空队列则返回 ERROR;If(0＝＝q->size) //是空队列Return ERROR；另p指向队头元素结点，队头元素结点可用Q→rear→next表示。此时，p转化为头结点，p出列，则需要Q的队尾指向p的下一个元素，因此第4空填：p→next。最后，判断被删除的队头结点是否是队列中的唯一结点，可采用：Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1 等表示方法。
【解析】
本题考察C语言指针与链表的知识，为入队列和删除队列问题。对于入队列，那么当队列Q不为空时，P的队尾t要指向原Q的队尾指向的元素，即：P->next=Q->rear->next，Q的队尾要指向p，即：Q→rear→next=p。当队列Q为空时，插入p元素，则p的队尾指向p自身，即：p→next=p，且整个队列Q的队尾也是p，即：Q→rear=p。对于队列删除元素p，先判断Q是否为空，为空队列则返回 ERROR;If(0＝＝q->size) //是空队列Return ERROR；另p指向队头元素结点，队头元素结点可用Q→rear→next表示。此时，p转化为头结点，p出列，则需要Q的队尾指向p的下一个元素，因此第4空填：p→next。最后，判断被删除的队头结点是否是队列中的唯一结点，可采用：Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1 等表示方法。
相关考题：
●试题四阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明4．1】假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：typedef struct{DateType data ［MaxSize］；int front［2］，rear［2］；}Queue2；对于i=0或1，front［i］和rear［i］分别为第i个队列的头指针和尾指针。函数EnQueue(Queue2*Q，int i，DateType x)的功能是实现第i个队列的入队操作。【函数4．1】int EnQueue(Queue2*Q，int i，DateType x){∥若第i个队列不满，则元素x入队列，并返回1；否则，返回0if(i＜0‖i1)return 0；if(Q-rear［i］==Q-front［ (1) ］return 0；Q-data［ (2) ］=x；Q-rear［i］=［ (3) ］；return 1；}【说明4．2】函数BTreeEqual(BinTreeNode*T1，BinTreeNode*T2)的功能是递归法判断两棵二叉树是否相等，若相等则返回1，否则返回0。函数中参数T1和T2分别为指向这两棵二叉树根结点的指针。当两棵树的结构完全相同，并且对应结点的值也相同时才被认为相等。已知二叉树中的结点类型BinTreeNode定义为：struct BinTreeNode{char data；BinTreeNode*left，*right；}；其中data为结点值域，left和right分别为指向左、右子女结点的指针域，【函数4．2】int BTreeEqual(BinTreeNode*T1，BinTreeNode*T2){if(T1==NULL ＆＆ T2==NULL)return 1；∥若两棵树均为空，则相等else if( (4) )return 0；∥若一棵为空一棵不为空，则不等else if( (5) )return 1；∥若根结点值相等并且左、右子树∥也相等，则两棵树相等，否则不等else return 0；}
●试题三阅读下列说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】本题给出四个函数，它们的功能分别是：1.int push(PNODE *top，int e)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。2.int pop(PNODE *top，int *e)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。3.int enQueue(PNODE *tail，int e)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。4.int deQueue(PNODE *tail，int *e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。以上四个函数中，返回值为0表示操作成功，返回值为-1表示操作失败。栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为：typedef struct node{int value；struct node *next；}NODE，*PNODE；【函数1】int push(PNODE *top，int e){PNODE p=(PNODE)malloc (sizeof(NODE))；if (!p) return-1；p- value =e；(1) ；.*top=p；return 0；}【函数2】int pop (PNODE *top，int *e){PNODE p=*top；if(p==NULL)return-1；*e=p-value；(2) ；free(p)；return 0；}【函数3】int enQueue (PNODE *tail，int e){PNODE p，t；t=*tail；p=(PNODE)malloc(sizeof(NODE))；if(!p)return-l；p-value=e；p-next=t-next；(3) ；*tail=p；return 0；}【函数4】int deQueue(PNODE *tail，int *e){PNODE p，q；if((*tail)-next==*tail)return -1；p=(*tail)-next；q=p-next；*e=q-value；(4) =q-next；if(*tail==q) (5) ；free(q)；return 0；}
阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。[说明]求树的宽度，所谓宽度是指在二叉树的各层上，具有结点数最多的那一层的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。[函数]int Width ( BinTree *T{int front=-1, rear=-1; /*队列初始化*/int flag=0, count=0, p; /*p用于指向树中层的最右边的结点, flag 记录层中结点数的最大值*/if ( T!=Null){rear++;(1);flag=1;p=rear;}while ((2)){front++;T=q [front]];if (T-lchild!=Null ){roar+-+;(3);count++;}if ( T-＞rchild!=Null ){rear++; q[rear]=T-＞rchild;(4);}if (front==p ) // 当前层已遍历完毕{if((5))flag=count;count=0;p=rear, //p 指向下一层最右边的结点}}return ( flag );}
阅读下列函举说明和C代码，将应填入(n)处的字句写在对应栏内。【说明4.1】假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：typedef struct {DateType data [MaxSize];int front[2],rear[2];}Queue2;对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。函数．EnQueue (Queue2*Q，int i，DaleType x)的功能是实现第i个队列的入队操作。【函数4.1】int EnQueue(Queue2 * Q, int i, DateType x){ /*若第i个队列不满，则元素x入队列，并返回1；否则，返回0*/if(i＜0‖i＞1) return 0;if(Q-＞rear[i]==Q-＞front[(1)]return 0;Q-＞data[(2)]=x;Q-＞rear[i]=[(3)];return 1;}【说明4.2】函数BTreeEqual(BinTreeNode*T1，BinTtneNode*T2)的功能是递归法判断两棵二叉树是否相等，若相等则返回1，否则返回0。函数中参数T1和T2分别为指向这两棵二叉树根结点的指针。当两棵树的结构完全相同，并且对应结点的值也相同时，才被认为相等。已知二叉树中的结点类型BinTreeNode定义为：struct BinTreeNode {char data;BinTreeNode * left, * right;};其中dau为结点值域，leR和risht分别为指向左、右子女结点的指针域，【函数4.2】int BTreeEqual(BinTreeNode * T1, BinTreeNode * T2){if(Ti == NULL T2 == NULL)return 1 /*若两棵树均为空，则相等*/else if((4))return 0; /*若一棵为空一棵不为空，则不等*/else if((5)) return 1; /*若根结点值相等并且左、右子树*//*也相等，则两棵树相等，否则不等*/else return 0;}
阅读下列函数说明和Java代码，将应填入(n)处的字句写在对应栏内。【说明】类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException给出了队列操作中的异常处理操作。public class TestMain { //主类public static viod main (String args[]){Queue q=new Queue();q.enqueue("first!");q.enqueue("second!");q.enqueue("third!");(1) {while(true)System.out.println(q.dequeue());}catch( (2) ){ }}public class Queue { //队列Node m_FirstNode;public Queue(){m_FirstNode=null;}public boolean isEmpty(){if(m_FirstNode==null)return true;else return false;}public viod enqueue(Object newNode) { //入队操作Node next=m_FirstNode;if(next==null)m_FirstNode=new Node(newNode);else{while(next.getNext()!=null)next=next.getNext();next.setNext(new node(newNode));}}public Object dequeue() (3) { //出队操作Object node;if (isEempty())(4); //队列为空, 抛出异常else{node=m_FirstNode.getObject();m_FirstNode=m_FirstNode.getNext();return node;}}}public class Node{ //队列中的元素Object m_Data;Node m_Next;public Node(Object data) {m_Data=data; m_Next=null;}public Node(Object data, Node next) {m_Data=data; m_Next=-next;}public void setObject(Object data) {m_Data=data;}public Object getObject(Object data) {return m_data;}public void setNext(Node next) {m_Next=next;}public Node getNext() {return m_Next;}}public class EmptyQueueException extends (5) { //异常处理类public EmptyQueueException() {System.out.println("队列已空! ");}}
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]循环队列的类型定义如下(其中队列元素的数据类型为datatype)：typedef struct{datatype data[MAXSIZE]; /*数据的存储区*/int front,rear; /*队首、队尾指针*/int num; /*队列中元素的个数*/}c _ SeQueue; /*循环队*/下面函数及其功能说明如下：(1) c_SeQueue* Init_SeQueue()：新建队列；(2) int ln_SeQueue( c_SeQueue *q, datatype x)：将元素x插入队列q，若成功返回1否则返回0；(3) int Out_SeQueue (c_SeQueue *q, datatype *x)：取出队列q队首位置的元素，若成功返回1否则返回0。[函数]c_SeQueue* Init_SeQueue(){ q=malloc(sizeof(c_SeQueue));q-＞front=q-＞rear=MAXSIZE-1;(1);return q;}int In_SeQueue( c_SeQueue *q, datatype x){ if(q-＞num= =MAXSIZE) return 0; /*队满不能入队*/else {q-＞rear=(2);q-＞data[q-＞rear]=x;(3);return 1; /*入队完成*/}}int Out_SeQueue( c_SeQueue *q, datatype *x){ if (q-＞num= =0) return 0; /*队空不能出队*/else{*x=(4); /*读出队首元素*/q-＞front=(5);q-＞num- -;return 1; /*出队完成*/}}
阅读下列说明和C代码，将应填入(n)处的字句写在对应栏内。【说明】本题给出四个函数，它们的功能分别是：1．int push(PNODE*top，int e)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。2．int pop(PNODE*top，int*e)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。3．int enQueue(PNODE*tail，int e)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。4．int deQueue(PNODE*tail，int*e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。以上四个函数中，返回值为。表示操作成功，返回值为-1表示操作失败。栈是用链表实现的；队是用带有辅助结点(头结点)的单向循环链表实现的。两种链表的结点类型均为：typedef struct node {int value;struct node * next;} NODE, * PNODE;【函数1】int push(PNOOE * top,int e){PNODE p = (PNODE) malloc (sizeof (NODE));if (! p) return-1;p-＞value=e;(1);*top=p;return 0;}【函数2】int pop (PNODE * top,int * e){PNODE p = * top;if(p == NULL) return-1;* e = p-＞value;(2);free(p);return 0;}【函数3】int enQueue (PNODE * tail,int e){ PNODE p,t;t= *tail;p = (PNODE) malloc(sizeof(NODE));if(!p) return-1;p-＞value=e;p-＞next=t-＞next;(3);* tail = p;return 0;}【函数4】int deQueue(PNODE * tail,int * e){ PNODE p,q;if(( * tail)-＞next == * tail) return-1;p= (* tail)-＞next;q = p -＞next;* e =q -＞value;(4)=q-＞next;if(,tail==q) (5);free(q);return 0;}
阅读下列说明和C函数，将应填入(n)处的字句写在对应栏内。【说明】已知集合A和B的元素分别用不含头结点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A＝{5，10， 20，15，25，30}，集合B＝{5，15，35，25}，如图(a)所示，运算完成后的结果如图(b)所示。链表结点的结构类型定义如下：typedef struct Node{ElemType elem；struct Node *next；}NodeType；【C函数】void Difference(NodeType **LA，NodeType *LB){NodeType *pa， *pb， *pre， *q；pre＝NULL；(1)；while (pa) {pb＝LB；while((2))pb＝pb-＞next；if((3)) {if(!pre)*LA＝(4)；else(5)＝pa-＞next；q ＝ pa；pa＝pa-＞next；free(q)；}else {(6)；pa＝pa-＞next；}}}
阅读以下说明和C语言函数，将应填入(n)。【说明】已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE*head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。处理过程中，当元素重复出现时，保留元素第一次出现所在的结点。图2-1(a)、(b)是经函数compress()处理前后的链表结构示例图。链表的结点类型定义如下：typedef struct Node{int data；struct Node *next；}NODE；【C语言函数】void compress(NODE *head){ NODE *ptr，*q；ptr= (1)； /*取得第一个元素结点的指针*/while( (2) ptr-＞next) {q=ptr-＞next；while(q(3)) { /*处理重复元素*/(4)q-＞next；free(q)；q=ptr-＞next；}(5) ptr-＞next；}/*end of while */}/*end of compress*/
阅读下列函数说明和C函数，将应填入(n)处的字句写对应栏内。[说明]二叉树的二叉链表存储结构描述如下：typedef struct BiTNode{ datatype data;struct BiTNode *lchild, * rchild; /*左右孩子指针*/}BiTNode,* BiTree;对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作：(1) 访问该元素所指结点；(2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。[函数]void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/{ BiTree Queue[MAXNODE];int front,rear;if(bt= =NULL)return;front=-1;rear=0;queue[rear]=(1);while(front (2) ){(3);Visit(queue[front]-＞data); /*访问队首结点的数据域*/if(queue[front]—＞lchild!：NULL){ rear++;queue[rear]=(4);}if(queue[front]-＞rchild! =NULL){ rear++;queue[rear]=(5);}}}
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]这是一个模拟渡口管理的算法。某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和火车类，上船有如下规定：同类车先到先上船，客车先于货车上渡船，且每上4辆客车，才允许上一辆货车；若等待客车不足4辆，则以货车代替，若无货车等待则允许客车都上船。程序中用到的函数有enqueue(queue*sq，elemtype*x)在队列sq中入队一个元素x；outqueue(queue*sq，elemtype*x)在队列sq中出队一个元素，并将其值赋给x；empty(queue*sq)判断队列sq是否为空队，若为空，返回1；否则返回0。[C程序]include＜stdio.h＞void pass(){queue bus,truct; /*bus表示客车队列，truck表示货车队列*/char ch;int n,tag； /* ]n为车号，tag为标志，tag=0表示客车，tag=1表示货车*/intcount=0，countbus=0，counttruck=0; /*分别表示上渡船汽车数、客车数、货车数*/while(1){printf("输入命令: \n");Scanf("%c"，ch);switch(ch){case'e':case'E': printf("车号: \n");Scanf("%d"，n);printf("客车\货车(0\1): \n");scanf("%d"，tag);if( (1) )enqueue(bus,n);elseenqueue(truck,n);break;case'i':case'I': while(count＜10){if( (2) empty(bus)==0){ /*客车出队*/outqueue(bus,n);printf("上船的车号为: \n");count++;(3) ;}eise if( (4) ){ /*货车出队*/countbus=0;outqueue(truck,n);printf("上船的车号为: \n");count++;counttruck++;}else if(empty(bus)==0){(5);outqueue(truck,n);printf("没有10辆车排队轮渡\n");count++;countbus++;}else{printf("没有10辆车排队轮渡\n");retUrn;}break;}case'q':case'Q':break;}if(ch=='q' || ch=='Q')break;}}
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]链式存储的队列称为链队。根据队列的FIFO原则，为了操作上的方便，可以使用带头指针front和尾指针rear的单链表来实现链队。若链队元素的数据类型为datatype，则链队结构描述如下：typedef struct node{ datatypedata;structnode *next;} QNode; /*链队结点的类型*/typedef struct{ QNnode *front,*rear;} LQueue; /*将头尾指针封装在一起的链队*/以下这种链队的几个例子：设q是一个指向链队的指针，即LQueue *q。下面各函数的功能说明如下：(1) LQueue *Init_LQueue()：创建并返回一个带头尾结点的空链队；(2) intEmpty_LQueue( LQueue *q):判断链队q是否空；(3) void In_LQueue(LQueue *q, datatypex):将数据x压入链队q；(4) int Out_LQueue(LQuere *q, datatype *x):弹出链队q的第一个元素x，若成功则返回返回1否则返回0。[函数]LQueae *Init_LQueue(){ LQueue *q, *p;q=malloc(sizeof(LQueue)); /*申请链队指针*/P=malloc(sized(QNode));/*申请头尾指针结点*/p-＞next=NULL;(1)=p;return q;}int Empty_LQueue(LQueue *q){ if(q-＞front (2) q＞rear) return 0;else return 1;}void In_LQueue(LQueue *q, datatype x){ QNoda *p;p=malloc(sizeof(QNnode));/*申请新接点*/p-＞data=x;p-＞next=NULL;(3)=p;q-＞rear=p;}int Out_LQueue(LQueue *q, datatype *x){ QNnode *p;if(Empty_LQueue(q)) return 0; /*队空,操作失败*/else{p=q-＞front-＞next;*x=(4);(5)=p-＞next;free(p);if (q-＞front-＞next= =NULL)q-＞rear=q-＞front;return 1;}}
队列采用如下图所示的循环单链表表示，图(a)表示队列为空，图(b)为e1、e2.e3依次入队列后的状态，其中，rear指针指向队尾元素所在结点，size为队列长度。以下叙述中，正确的是（ ）。A.入队列时需要从头至尾遍历链表，而出队列不需要B.出队列时需要从头至尾遍历链表，而入队列不需要C.新元素加入队列以及队头元素出队列都需要遍历链表，D.入队列和出队列操作都不需要遍历链表
阅读以下说明和 C 函数，填补函数代码中的空缺，将解答填入答题纸的对应栏内。 【说明 1】 函数 f(double eps) 的功能是:利用公式计算并返回 的近似值。【说明 2】 函数fun(char *str)的功能是:自左至右顺序取出非空字符串 str中的数字字符，形成一个十进制整数(最多 8 位)。例如，若 str中的字符串为 iyt?67kp f3g8d5.j4ia2e3p12， 则函数返回值为 67385423。
阅读以下说明和C函数，填补函数代码中的空缺(1)～(5)，将解答填入答题纸的对应栏内。【说明】队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元素，同时通过模运算将存储空间看作一个环状结构（称为循环队列）。设循环队列的存储空间容量为MAXQSIZE，并在其类型定义中设置base、rear和lengtb三个域变量，其中’base为队列空间的首地址，rear为队尾元素的指针，length表示队列的长度。define maxqstze 100typedef struct {QElemType *base; /*循环队列的存储空间首地址*／int rear; ／*队尾元素索引*／int length; ／*队列的长度*／) SqQueue;例如，容量为8的循环队列如图3-1所示，初始时创建的空队列如图3一l(a)所示经过一系列的入队、出队操作后，队列的状态如图3-1 (b)所示(队列长度为3)。下面的C函数1、C函数2和C函数3用于实现队列的创建、插入和删除操作，请完善这些代码。【C函数1】创建一个空的循环队列。int initQueue (SqQueue *Q)／*创建容量为MAXQSIZE的空队列，若成功则返回1；否则返回0*／{ Q-＞base = (QElemType*) malloc(MAXQSIZE* (1) )if (!Q=＞base) return 0;。；Q-＞length=O；Q-’rear =O：Return 1;} /*InitQueue*/【c函数2】元素插入循环队列。int EnQueue(sqQueue *Q. QElemType e）／*元素e入队，若成功则返回1；否则返回0*/{if ( Q-＞length＞=MAXQSIZE) return 0.;Q-＞rear=(2)；Q-＞base [Q-＞rear]=e;(3) ;Return 1) /*EnQUeue*/【c函数3】元素出循环队列。int DeQueue (SqQueue *Q. QElemType *e)／*若队列不空，则删除队头元素，由参数e带回其值并返回1；否则返回O*／{1f‘(4)，return 0；*e =O-＞base[ (Q=＞rear - Q-＞length+I+MAXQSTZE) %MAXQSIZE](5) ；returnl；} /*DeQueue*/
阅读以下说明和C函数，填补代码中的空缺(1)～(6)，将解答填入答题纸的对应栏内。【说明】二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]. counter[i]存放第i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从countler[]中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为；先令根结点及其层次号（为1）进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左子树根结点及层次号八队列（若左子树存在），其次将该结点的右子树根结点及层次号八队列（若右子树存在），然后再取队头，重复该过程直至完成遍历。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BTNode{TElemType data;struct BTNode *left. *right} BTNode , *BiTree _队列元素的类型定义如下typedef struct {BTNode *ptr;int LevelNumber) QElemType;【C函数】int GetWidth (BiTree root){QUEUE Q;QElemType a, b;int width.height = GetHeight(root);int i, *counter =(lnt*) calloc (helght+l. sizeof (int));if ( 1) return -1; ／*申请空间失败*/If(!root ) return -0; /*空树的宽度为0*／if ( 1) return -1 /*初始化队列失败时返回*／A.ptr=root; a.leveinumber=1;If(!Enqueue(＆Q,a)) return-1; ／*元素入队列操作失败时返回*／while (！isEmpty(Q》{if( (3) )return -1; /*出队列操作失败时返回*／Counter[b．LevelNumber]++；／*对层号为b．LevelNumber的结点计数*/if（bNaNr=＞left）{／*若左子树存在，则左于树根结点及其层次号入队*／aNaNr =bNaNr=＞left;a.LevelNurnber =(4) ；If(!EnQueue (Q,a))return -1;}if( bNaNr=＞right){／*若右子树存在，则右子树根结点及其层次号入队*／a．ptr= bNaNr-＞right;a LevelNumber (5) iIf(!EnQueue (Q,a))return -1}}width= counter[1];For(i=1; iheight+1;i++1) /*求counter[ ]中的最大值*/If(6) width =counter[i];Free(counter);Return width;}
试题四（共 15 分）阅读以下说明和 C 语言函数，将应填入 （n） 处的字句写在答题纸的对应栏内。[说明]已知包含头结点（不存储元素）的单链表的元素已经按照非递减方式排序，函数compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。处理过程中，当元素重复出现时，保留元素第一次出现所在的结点。图4-1(a)、(b)是经函数 compress()处理前后的链表结构示例图。链表的结点类型定义如下：typedef struct Node {int data;struct Node *next;}NODE;[C 语言函数]void compress(NODE *head){ NODE *ptr,*q;ptr = （1） ; /* 取得第一个元素结点的指针 */while ( （2） ptr - next) {q = ptr - next;while(q （3） ) { /* 处理重复元素 */（4） = q - next;free(q);q = ptr - next;}（5） = ptr - next;}/* end of while */}/* end of compress */
阅读以下说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。说明类Queue表示队列，类中的方法如下表所示。类Node表示队列中的元素；类EmptyQueueException 给出了队列操作中的异常处理操作。Java 代码public class TestMain{ // 主类public static void main(String args[]) {Queue q = new Queue();q.enqueue("first!");q.enqueue("second!");q.enqueue("third!");(1) {while(true)System.out.println(q. dequeue());}catch((2)) ( }}}public class Queue { // 队列Node m_FirstNode;public Queue() { m_FirstNode = null; }public boolean isEmpty() {if(m_FirstNode == null) return true;else return false;}public void enqueue(Object newNode) {// 入队操作Node next = m_FirstNode;if(next==null) m_FirstNode = new Node(newNode);else {while(next.getNext() != null) next = next.getNext();next.setNext(new Node(newNode));}}public Object dequeue() (3) {// 出队操作Object node;if (isEmpty())(4); // 队列为空，抛出异常else {node = m_FirstNode.getObject();m_FirstNode = m_FirstNode.getNext();return node;}}}public class Node { // 队列中的元素Object m_Data;Node m_Next;public Node(Object data) { m_Data = data; m_Next = null; }public Node(Object data, Node next) { m_Data = data; m_Next = next; }public void setObject(Object data) { m_Data = data; }public Object getObject0 { return m_Data; }public void setNext(Node next) { m_Next = next; }public Node getNext() { return m_Next; }}public class EmptyQueueException extends (5) { // 异常处理类public EmptyQueueException0 {System.out.println("队列已空 ! ");}}
阅读以下说明和C语言函数，将解答填入答题纸的对应栏内。【说明】函数sort (NODE *head)的功能是：用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻结点中的元素，若较小的元素在前面，则交换这两个结点中的元素值。其中，head指向链表的头结点。排序时，为了避免每趟都扫描到链表的尾结点，设置一个指针endptr，使其指向下趟扫描需要到达的最后一个结点。例如，对于图（a）的链表进行一趟冒泡排序后，得到图（b）所示的链表。
阅读以下说明和C函数，填补代码中的空缺，将解答填入答题纸的对应栏内。[说明]函数ReverseList(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成：已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。例如，某单链表如图1所示，逆置过程中指针s的变化情况如图2所示。链表结点类型定义如下：typedef struct Node{ int data; Struct Node *next; }Node,*LinkList; [C函数] void ReverseList(LinkList headptr) { //含头结点的单链表就地逆置,headptr为头指针 LinkList p,s; if(______) return; //空链表(仅有头结点)时无需处理 P=______; //令P指向第一个元素结点 if(!P-＞next) return; //链表中仅有一个元素结点时无需处理 s=p-＞next; //s指向第二个元素结点 ______ =NULL; //设置第一个元素结点的指针域为空 while(s){ p=s; //令p指向未处理链表的第一个结点 s= ______; p-＞next=headptr-＞next; //将p所指结点插入已完成部分的表头 headptr-＞next= ______; } }
在jquery的动画执行过程中下列说法正确的是（）。A、duration表示动画的执行时间B、queue：true表示插入队列C、queue：true表示不插入队列D、function代表动画执行完回调的函数
填空题已知Q是一个非空队列，S是一个空栈。编写算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q的所有元素逆置。栈的ADT函数有：voidmakeEmpty（SqStacks）；置空栈voidpush（SqStacks，ElemTypee）；元素e入栈ElemTypepop（SqStacks）；出栈，返回栈顶元素intisEmpty（SqStacks）；判断栈空队列的ADT函数有：voidenQueue（Queueq，ElemTypee）；元素e入队ElemTypedeQueue（Queueq）；出队，返回队头元素intisEmpty（Queueq）；判断队空