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

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

二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter[], counter[i]存放第i层上的结点数,并按照层次顺序来遍历二又树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。

按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。

设二叉树采用二叉链表存储,结点类型定义如下:

typedef struct BTNode{

TElemType data;

struct BTNode *left, *right;

}BTNode, *BiTree;

队列元素的类型定义如下:

typedef struct{

BTNode *ptr;

int LevelNumber;

}QElemType;

Get Width()函数中用到的函数原型如下所述,队列的类型名为 QUEUE:

InitQueue(QUEUE *Q):初始化一个空队列,成功时返回值为1,否则返回值0

isEmpty(QUEUE Q):判断队列是否为空,是空则为1,否则为0

EnQueue( QUEUE*Q, QElemType a):将元素a加入队列,成功返回值为1,否则返回值0

DeQueue(QUEUE *Q, QElemType *):删除队头元素,并通过参数带回其值,成功则返回值1,否则返回值0

GetHeight (BiTree root):返回值为二叉树的高度(即层次数,空二叉树的高度为0)

int Getwidth(BiTree root){

QUEUE Q;

QElemType a, b;

int width,height= GetHeight(root);

int i, *counter =(int *)calloc(height+1, sizeof (int));

if(__(1)__) return -1;/*申请空间失败*/

if(! root) return 0;/*空树的宽度为0*/

if(__(2)__) return -1;/*初始化队列失败时返回*/

a.ptr= root;

a.LevelNumber=1;

if(! EnQueue(&Q,a)) return -1;/*元素入队列操作失败时返回*/

while (! isEmpty(Q)){

if(__(3)__)return -1;/*出队列操作失败时返回*/

counter[b. LevelNumber]++;/*对层号为b. LevelNumber的结点计数*/

if(b.ptr->left){/*若左子树存在,则左子树根结点及其层次号入队*/

a.ptr= b.ptr->left;

a.LevelNumber=__(4)__;

if(!EnQueue(&Q,a)) return -1;

}

if(b.ptr-> right){/*若右子树存在,则右子树根结点及其层次号入队*/

a.ptr= b.ptr->right;

a. LevelNumber=__(5)__;

if(! EnQueue(&Q,a)) return -1;

}

}

width= counter[1];

for(i=1; i< height +1; 1++)/*求 counter[]中的最大值*/

if(__(6)__)width= counter [i];

free(counter);

return width;

}

答案解析

(1)!counter或0== counter或NUL= counter或其等价形式(2)!InitQueue(&Q)或0== InitQueue(&Q)或其等价形式(3)!DeQueue(&Q,&b)或...

查看完整答案

讨论

阅读以下说明和C函数,填补函数代码中的空缺(1)~(5)。队列是一种常用的数据结构,其特点是先入先出,即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列,即利用一组地址连续的存储单元存放队列元素,同时通过模运算将存储空间看作一个环状结构(称为循环队列)。设循环队列的存储空间容量为 MAXQSIZE,并在其类型定义中设置base、rear和 length三个域变量,其中,base为队列空间的首地址,rear为队尾元素的指针, length表示队列的长度。#define MAXQSIZE 100typedef 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*/

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

设有字符串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]的元素时,先后与【 】等元素进行了比较。

有n个数顺序(依次)进栈,则出栈顺序有Cn种。Cn=×

对下列二叉树进行后序遍历的结果是【 】

对于前序遍历和中序遍历结果相同的二叉树为__________;对于前序遍历和后序遍历结果相同的二叉树是为__________。一般二叉树只有根结点的二叉树要结点无左孩子的二叉树根结点无右孩子的二叉树所有结点只有左子树的二叉树所有结点只有右子树的二叉树

由二叉树的前序和后序遍历序列【 】唯一地确定这棵二叉树。

如果只考虑有序树的情形,那么具有7个结点的不同形态的树共有【】

具有7个结点的互不相识的二叉树共有__________棵。

一个深度为 h 的满 m 叉树有如下性质:第 h 层上的结点都是叶结点,其各层上每个结点有 m 棵非空子树。问:(1)第 k 层最多有多少个结点?(k≤h )(2)整棵树最多有多少个结点?(3)若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,编号为 i 的结汽的双亲结点的编号是什么?编号为 i 的结点的第 j 个孩子结点(若存在)的编号是什么?

已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,...,Nm个度为m的结点。试问该树中有多少个叶子结点?

证明,由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH,中序序列为DGBEAFHC,试画出该二叉树。

已知一棵二叉树的前序遍历结果是ADCEBFIHGJ,中序遍历结果是CDEBAFHGIJ,试画出这棵二叉树。