软件设计师分类模拟题数据结构及算法设计(一)
试题一
阅读下列说明、图和C代码，将应填入 (n) 处的字句写在对应栏内。
1、【说明5-1】
B树是一种多叉平衡查树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
①树中每个节点至多有m棵子树；
②若根节点不是叶子节点，则它至少有两棵子树；
③除根之外的所有非叶子节点至少有[m/2]棵子树；
④所有的非叶子节点中包含下列数据信息(n，A0，K1，A1，K2，A2，…，K n，A n)，其中：K i(i=1，2，…，n)为关键字，且K i＜K i+1(i=1，2，…，n-1)，A i(i=0，1，…，n)为指向子树根节点的指针，且指针A i-1所指子树中所有节点的关键字均小于K i，A i+1所指子树中所有节点的关键字均大于K i，n 为节点中关键字的数目；
⑤所有的叶子节点都出现在同一层次上，并且不带信息(可以看成是外部节点或查失败的节点，实际上这些节点不存在，指向这些节点的指针为空)。
例如，一棵4阶B树如图5-1所示(节点中关键字的数目省略)。
B树的阶M、bool类型、关键字类型及B树节点的定义如下：
#define  M  4  /*B树的阶*/
typedef enum{FALSE=0,TRUE=1}bool;
typedef int ElemKeyType;
typedef struct BTreeNode{
int numkeys;    /*节点中关键字的数目*/
struct BTreeNode *parent;      /*指向父节点的指针，树根的父节点指针为空*/
struct BTreeNode *A[M];    /*指向子树节点的指针数组*/
ElemKeyType K[M];          /*存储关键字的数组，K[0]闲置不用*/
}BTreeNode；
函数SearchBtree(BTreeNode* root，ElemKeyType akey，BTreeNode **ptr)的功能是：在给定的一棵M阶B树中查关键字akey所在节点，若到则返回TRUE，否则返回FALSE。其中， root是指向该M阶B树根节点的指针，参数ptr返回akey所在节点的指针，若akey不在该B树中，则ptr返回查失败时空指针所在节点的指针。例如，在如图5-1所示的4阶B树中查关键字25时，ptr返回指向节点e的指针。
注：在节点中查关键字akey时采用二分法。
bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)
{
int  lw,hi,mid;
BTreeNode *p=root;
*pb=NULL;
while(p){
lw=1;hi= (1) ;
while(lw＜=hi){
mid=(lw+hi)/2;
if(p-＞K[mid]==akey){
*Ptr=p;
return TRUE;
}else if( (2) )
hi=mid-1;
else
lw=mid+1;
}
*ptr=p;
p= (3) ;
}
return FALSE;
}
【说明5-2】
在M阶B树中插入一个关键字时，首先在最接近外部节点的某个非叶子节点中增加一个关键字，若该节点中关键字的个数不超过M-1，则完成插入；否则，要进行节点的“分裂”处理。所谓“分裂”，就是把节点中处于中间位置上的关键字取出来并插入其父节点中，然后以该关键字为分界线，把原节点分成两个节点。“分裂”过程可能会一直持续到树根，若树根节点也需要分裂，则整棵树的高度增1。
例如，在如图5-1所示的B树中插入关键字25时，需将其插入节点e中，由于e中已经有3个关键字，因此将关键字24插入节点e的父节点b，并以24为分界线将节点e分裂为e1和e2两个节点，结果如图5-2所示。
函数Isgrowing(BTreeNode* root，ElemKeyType akey)的功能是：判断在给定的M阶B 树中插入关键字akey后，该B树的高度是否增加，若增加则返回TRUE，否则返回FALSE。其中，root 是指向该M阶B树根节点的指针。
在函数Isgrowing中，首先调用函数SearchBtree(即函数5-1)查关键字akey是否在给定的M阶B树中，若在则返回FALSE(表明无须插入关键字akey，树的高度不会增加)；否则，通过判断节点中关键字的数目考察插入关键字akey后该B树的高度是否增加。
bool Isgrowing(BTreeNode* root,ElemKeyType akey)
{
BTreeNode *t,*f;
if(!SearchBtree( (4) )){
t=f;
while( (5) ){
t=t-＞parent;
}
if(!t)
return TRUE;
}
return FALSE;
}
试题二
阅读以下函数说明、图和C代码，将应填入 (n) 处的字句写在对应栏内。
2、【说明】
散列文件的存储单位称为桶(BUCKET)。假如一个桶能存放m个记录，当桶中已有m个同义词(散列函数值相同)的记录时，存放第m+1个同义词会发生“溢出”。此时需要将第m+1个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前m个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查指定元素记录时，首先在基桶中查。若到，则成功返回，否则沿指针到溢出桶中进行查。
例如：设散列函数为Hash(Key)=Key mod 7，记录的关键字序列为15，14，21，87，96， 293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图5-3所示。
为简化起见，散列文件的存储单位以内存单元表示。
函数InsertToHashTable(int NewElemKey)的功能是；若新元素NewElemKey正确插入散列文件中，则返回值1；否则返回值0。
采用的散列函数为Hash(NewElemKey)=NewElemKey % P，其中P为设定的基桶数目。
函数中使用的预定义符号如下：
#define NULLKEY-1    /*散列桶的空闲单元标识*/
#define P 7    /*散列文件中基桶的数目*/
#define ITEMS 3      /*基桶和溢出桶的容量*/
typedef struet BucketNode{      /*基桶和溢出桶的类型定义*/    int KeyData[ITEMS];
struct BucketNode *Link;
}BUCKET;
BUCKET Bucket[P];    /*基桶空间定义*/
【函数5-3】
int InsertToHashTable(int NewElemKey){
/*将元素NewElemKey插入散列桶中，若插入成功则返回0，否则返回-1*/
/*设插入第一个元素前基桶的所有KeyData[]，Link域已分别初始化为NULLKEY、NULL*/    int Index;  /*基桶编号*/
int i,k'
BUCKET *s,*front,*t;
(1) ;
for(i=0;i＜ITEMS;i++)  /*在基桶查空闲单元，若到则将元素存入*/    if(Bucket[Index].KeyData[i]==NULLKEY){
Bucket[Index].KeyData[i]=NewElemKey;
break;
}
if( (2) )return 0;
/* 若基桶已满，则在溢出桶中查空闲单元，若不到则申请新的溢出桶*/
(3) ;
t=Bucket[Index].Link;
if(t!=NULL){  /*有溢出桶*/
while(t!=NULL){
for(k=0;k＜ITEMS;k++)
if(t-＞KeyData[k]==NULLKEY){/*  在溢出桶链表中到空闲单元*/
t-＞KeyData[k]=NewElemKey;
break;
}/*if*/
front=t;
if( (4) )t=t-＞Link;
else break;
计算机软件水平考试}/*while*/
}/*if*/
if( (5) ){  /* 申请新溢出桶并将元素存入*/
s=(BUCKET *)malloc(sizeof(BUCKET));
if(!s)retum -1;
s-＞Link=NULL;
for(k=0;k＜ITEMS;k++)
s-＞KeyData[k]=NULLKEY;
s-＞KeyData[0]=NewElemKey;
(6) ;
}/*if*/
return 0;
}/*InsertToHashTable*/
试题三
阅读下列函数说明和C代码，将应填入 (n) 处的字句写在对应栏内。
3、【说明】
函数int Toplogcal(LinkedWDigraphG.的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
typedef struct Gnode{      /*邻接表的表节点类型*/    int adjvex;    /*邻接顶点编号*/
int weieht;    /*弧上的权值*/
stract Gnode *nextarc;    /*指示下一个弧的节点*/
}Gnode;
typedef struct Adjlist{    /*邻接表的头节点类型*/    char vdata;    /*顶点的数据信息*/
struct Gnode *Firstadj;    /*指向邻接表的第一个表节点*/    }Adjlist;
typedef struct LinkedWDigraph{      /*图的类型*/
int n,e;        /*图中顶点个数和边数*/
struct Adjlist *head;    /*指向图中第一个顶点的邻接表的头节点*/
}LinkedWDigraph;
例如，某AOE网如图5-4所示，其邻接表存储结构如图5-5所示。
int Toplogical(LinkedWDigraphG.
{
Gnode *p;