问答题(2014年秋程序员软考)

阅读以下说明和C函数,填补函数代码中的空缺(1)~(5)。

队列是一种常用的数据结构,其特点是先入先出,即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列,即利用一组地址连续的存储单元存放队列元素,同时通过模运算将存储空间看作一个环状结构(称为循环队列)。

设循环队列的存储空间容量为 MAXQSIZE,并在其类型定义中设置base、rear和 length三个域变量,其中,base为队列空间的首地址,rear为队尾元素的指针, length表示队列的长度。

#define MAXQSIZE 100

typedef struct{

QElemType *base;/*循环队列的存储空间首地址*

int real;/*队尾元素索引*/

int ength;/*队列的长度*/

} SqQueue;

例如,容量为8的循环队列如下图所示,初始时创建的空队列如图(a)所示,经过一系列的入队、出队操作后,队列的状态如图(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=0;

Q->rear =0;

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;否则返回0*/

if(__(4)__)return 0;

*e=Q-base[(Q->rear-Q->length+1+MAXQSIZE)%MAXQSIZE];

__(5)__;

return 1;

}/*DeQueue*/

答案解析

(1) sizeof(QElemType)(2)(Q->rear+1)% MAXQSIZE或其等价形式(3)Q->length++或Q-> ength=Q-> length+1或其等价形式(4)Q->...

查看完整答案

讨论

在数据结构中,【 】是与存储结构无关的术语。

设有字符串S= "software",其长度为3的子串数目为【 】。

对于一个初始为空的栈,其入栈序列为abc时,其出栈序列可以有【 】种。

含有n个元素的线性表采用顺序存储方式时,对其运算速度最快的操作是【 】。

算术表达式a*(b-c)+d的后缀式是【 】(-、+、*表示算术的减、加、乘运算,运算符的优先级和结合性遵循惯例)。

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转,即将原链表看成由两部分组成,已经完成逆置的部分和未完成逆置的部分,令s指向未逆置部分的第一个结点,并将该结点插入已完成部分的表头(头结点之后),直到全部结点的指针域都修改完成为止。例如,某单链表如图所示,逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下:typedef struct Node{ int data, struct Node *next;}Node, *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置, headptr为头指针 LinkList p,s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

对于下图,若采用邻接矩阵存储,则矩阵中的非0元素数目为【 】。

对于下图,从顶点1进行深度优先遍历时,不可能得到的遍历序列是【 】

在有13个元素构成的有序表data[1..13]中,用折半查找(即二分查找,计算时向下取整)方式查找值等于data[8]的元素时,先后与【 】等元素进行了比较。

已知某二叉树的先序遍历序列为ABCD,后序遍历序列为CDBA,则该二叉树为【 】。

在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印。该缓冲区应念是一个【 】结构。

队列采用如下图所示的循环单链表表示,左图表示队列为空,右图为e1、e2、e3依次入队列后的状态,其中,rear指针指向队尾元素所在结点,size为队列长度。以下叙述中,正确的是【 】。

在数据结构中,【 】是与存储结构无关的术语。

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码ki时,其前面的 i-1 个关键码已排好序,因此令k与 ki-1、ki-2、…,依次比较,最多到 k1为止,找到插入位置并移动相关元素后将ki插入有序子序列的适当位置,完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中,正确的是【 】 。

正规式(ab|c)(0|1|2)表示的正规集合中有【 】个元素。

线性表采用单链表存储时的特点是【 】。

设有字符串S和P,串的模式匹配是指确定【 】。

特殊矩阵是非零元素有规律分布的矩阵,以下关于特殊矩阵的叙述中,正确的是【 】。

完全二叉树的特点是叶子结点分布在最后两层,且除最后一层之外,其他层的结点数都达到最大值,那么25个结点的完全二叉树的高度(即层数)为【 】。

某二叉排序树如下所示,新的元素45应作为【 】插入该二叉树中。

用单链表表示的链式队列的队头在链表的【 】位置。

若用单链表来表示队列则应该选用【 】

若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列中删除一个元素, 再加入两个元素后, rear和加front的值分别为多少?

用数组表示的循环队列的队首和队尾位置分别为1和 max_size,试给出判断队列为空和为满的边界条件。

设一单项链表的头指针为head,链表的记录中包含整数类型的key域,试设计算法,将此链表的记录按照key递增的顺序进行就地排序。

顺序队列一般应该组织成为环状队列的形式,而且一般队列头或尾其中之一应该特殊处理。例如,队列为 listarray [ 0 ... n-1] ,队列头指针为front ,队列尾指针为 rear ,则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

用数组 Q(其下标在 0 . . n-1 中,共有n个元素)表示一个环形队列, f 为当前队头元素的前一位置, r 为队尾元素的位置。假定队列中元素个数总小于 n ,求队列中元素个数的公式是__________。

在解决计算机与打印机之间速度不匹配的问题时,通常设置一个打印数据缓冲区,计算机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区取出数据。因此,该缓冲区的数据结构应该是【 】。

数组是程序语言提供的基本数据结构,对数组通常进行的两种基本操作是数组元素的【 】。

已知某带权图G的邻接表如下所示,其中表结点的结构为:以下关于该图的叙述中,正确的是【 】。