工学
判断题调用函数malloc，便能得到一个所需结点的空间，并返回这个结点的总大小。A 对B 错
题目
对
错
相似问题和答案
第1题：
●下列描述的不是链表的优点是 (20) 。
(20) A．逻辑上相邻的结点物理上不必邻接
B．插入、删除运算操作方便，不必移动结点
C．所需存储空间比线性表节省
D．无需事先估计存储空间的大小
【解析】链表需要使用一个指针域能存储后序结点，而指针域需要占用一定存储空间，因此选项C不是链表优点，其他选项都是链表的优点。
第2题：
● 以下应用中，必须采用栈结构的是 （41） 。
（41）
A. 使一个整数序列逆转
B. 递归函数的调用和返回
C. 申请和释放单链表中的结点
D. 装入和卸载可执行程序
第3题：
A、结点大小小，则存储密度小
B、结点大小小，则存储密度大
C、结点大小小，则占用存储空间多
D、结点大小小，则占用存储空间少
第4题：
下列描述中不是链表优点的是
A．逻辑上相邻的结点物理上不必相邻
B．插入、删除运算操作方便，不必移动结点
C．所需存储空间比线性表节省
D．无需事先估计存储空间的大小
解析：线性表的链式存储是用一组任意的存储空间来存放数据元素，链表结点空间是动态生成的，无需事先估计存储空间的大小。链表逻辑上相邻的元素在物理位置上不一定相邻，因此需要另外开辟空间来保存元素之间的关系，花费的存储空间较顺序存储多。在链表中插入或删除结点，只需修改指针，不需要移动元素。
第5题：
阅读下列C函数和函数说明，将应填入(n)处的字句写在对应栏内。
【说明】
函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
typedef struct Tnode{
int data； /*结点的键值*/
struct Tnode *Lchild, *Rchild； /*指向左、右子树的指针*/
}*Bitree：
在二叉查找树上删除一个结点时，要考虑3种情况：
①若待删除的结点p是叶子结点，则直接删除该结点；
②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；
③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。
【函数】
int DeleteNode (Bitree *r，int e) {
Bitree p=*r,pp，s，c；
while ( (1) ){ /*从树根结点出发查找键值为e的结点*/
pp=p;
if(e＜p-＞data) p=p-＞Lchild；
else p=p-＞Rchild；
}
if(!P) return-1； /*查找失败*/
if(p-＞Lchild && p-＞Rchild) {/*处理情况③*/
s=(2)；pp=p
while (3) {pp=s；s=s-＞Rchild;}
p-＞data=s-＞data； p=s；
}
/*处理情况①、②*/
if ( (4) ) c=p-＞Lchild；
else c=p-＞Rchild；
if(p==*r) *r=c；
else if ( (5) ) pp-＞Lchild=c；
else pp-＞Rchild=c；
free (p)；
return 0；
}
(1)p &&p-＞data!=e；或p!=NULL&&p-＞data!=e或p&&(*p).data!=e (2)p-＞Lchild或(*p).Lchild (3)p-＞Rchild或(*p).Rchild (4)p-＞Lchild或(*p).Lchild (5)pp-＞Lchid＝p或p＝(*pp).child 解析：本程序的功能是删除二叉查找树的一个结点。题目中对怎样删除结点有着比较详细的说明。
第1种情况就是删除叶子结点，叶子结点可以直接删除，这一点很好理解，因为叶子结点删除后并不会打乱查找树的顺序。
第2种情况是删除只有一个子结点的结点，只需把其子结点代替父结点即可。若子结点下有子树，子树结构不变。
第3种情况要复杂一点，要用到二叉查找树的一些性质，就是结点右子树的所有结点都大于根结点，左子树所有结点都小于根结点。所以，当删除了有左右子树的结点时，要在左子树找最大的结点，来替换被删结点。
第6题：
●试题三
阅读下列函数说明和C函数，将应填入(n)处的字句写在答题纸的对应栏内。
【函数3说明】
函数DeleteNode(Bitree*r,int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
typedef struct Tnode{
int data;/*结点的键值*/
struct Tnode*Lchild,*Rchild;/*指向左、右子树的指针*/
}*Bitree;
在二叉查找树上删除一个结点时，要考虑三种情况：
①若待删除的结点p是叶子结点，则直接删除该结点;
②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p;
③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s ,用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。
【函数3】
int DeleteNode(Bitree*r,int e){
Bitree p=*r,pp,s,c;
while( (1) ){/*从树根结点出发查找键值为e的结点*/
pp=p;
if(e＜p-＞data)p=p-＞Lchild;
else p=p-＞Rchild;
}
if(!p)return-1;/*查找失败*/
if(p-＞Lchild &&p-＞Rchild) { /*处理情况③*/
s= (2) ;pp=p;
while( (3) ){pp=s;s=s-＞Rchild;}
p-＞data=s-＞data;p=s;
}
/*处理情况①、②*/
if( (4) )c=p-＞Lchild;
else c=p-＞Rchild;
if(p==*r)*r=c;
else if( (5) )pp-＞Lchild=c;
else pp-＞Rchild=c;
free(p);
return 0;
}
●试题三
［问题1］
【答案】（1）F0是长话业务档案F1是长话用户档案。（2）处理1：电话号码处理5：用户编码。
【解析】本题给出的流程图是长话计费管理的处理流程，用来生成长话缴费通知单。系统的数据源是记录在电信局程控交换机磁带上的原始计费数据，这些数据在处理之前需要先进行分类，以提高系统的效率。原始计费数据记录的是每次通话的数据，长话缴费通知单是针对每个电话用户的，因此在处理1中应该按照电话号码进行分类。F0是在处理4（出账）中用来生成长话帐单文件所要用到的"长话业务档案"。由试题的说明可知，月计费文件中含有各种通话类型的话费，所以处理4（出账）的功能是长话话费从月计费文件中分离出来，并进行数据的验证。根据以上的分析得知F0应该是长话业务档案。F1是在处理6中生成长话缴费通知单所要用到的"长话用户档案"。因为用户编码是用户在系统中的惟一标识，所以应该先将长话帐单文件按照用户编码进行分类，再根据F1长话用户档案，得到用户名和用户地址，产生长话缴费通知单。因此F1应该是长话用户档案。
［问题2］
【答案】（1）根据月计费文件中的电话号码，在长话业务档案中找不到相应的用户编码。（2）在月计费文件中，某电话号码有国内长途通话的话费，但在长话业务档案中，国内长途许可标志却不许可。（3）在月计费文件中，某电话号码有国际长途通话的话费，但在长话业务档案中，国际长途许可标志却不许可。
［问题3］
【答案】对长话帐单文件中的每个记录，根据用户编码查询长途电话用户档案，找到相应的用户名和用户地址，形成长话缴费通知单。
第7题：
阅读以下说明和C语言函数，将应填入(n)处。
[说明]
二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二义排序树。
函数insert_BST(char *str)的功能是：对给定的字符序列按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针。序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。
二叉排序树的链表结点类型定义如下：
typedef struct BSTNode{
char Elem; /*结点的字符数据*/
int Count; /*记录当前字符在序列中重复出现的次数*/
struct BSTNode *Lch,*Rch; /*接点的左、右子树指针*/
}*BiTree;
[函数]
BiTree insert_BST(char *str)
{ BiTree root,parent,p;
char (1); /*变量定义及初始化 */
root=(BiTree)malloc(sizeof(struct BSTNode));
if(!root||*s=='\0') return NULL;
root-＞Lch=root-＞Rch=NULL; foot-＞Count=1; root-＞Elem=*s++;
for(; *s!='\0';s++) {
(2); parent=NULL;
while (p){ /*p从树跟结点出发查找当前字符*s所在结点 */
parent = p;
if(*s==p-＞Elem)/*若树中已存在当前字符结点，则当前字符的计数值加1*/
{p-＞Count++; break;}
else /*否则根据字符*s与结点*p中字符的关系，进入*p的左子树或右子树*/
if (*s＞p-＞Elem) p=p-＞Rch;
else p=p-＞Lch;
}/*while*/
if( (3)) {/* 若树中不存在字符值为*s的结点，则申请结点并插入树中 */
p=(BiTree)malloc(sizeof(struct BSTNode));
if(!p)return NULL;
p-＞Lch=p-＞Rch=NULL; p-＞Count=1; p-＞Elem=*s;
/*根据当前字符与其父结点字符值的大小关系，将新结点作为左子树或右子树插入*/
if(p-＞Elem＞parent-＞Elem) (4)=p;
else (5)=p;
}
}/*for*/
return root；
}
(1) *s=str(2) p=root(3) p==NULL (4) parent-＞Rch(5) parent-＞Lch 解析：本题考查二叉排序树在链表存储结构上的运算。
函数insert_BST(char *str)的功能是对给定的字符序列str按照ASCⅡ码值大小关系创建二叉排序树，并返回指向树根结点的指针，序列中重复出现的字符只建一个结点，并由结点中的Count域对字符的重复次数进行计数。
根据程序代码中对字符序列中字符的引用情况，可知需要在空(1)处定义字符指针s，其初值应为参数str的值。for语句的作用是对序列中的每个字符*s，用while循环从树根结点出发查找*s所在结点。由于while的条件p为非空指针时循环，因此此前应设置 p的初值，显然空(2)是为p没初值root，从而对每个字符*s都可以从树根出发，开始查找结点。若树中已存在当前字符*s的结点，则*s字符的计数值加1，并结束对该字符的查找过程，若树中不存在*s的结点，则会进入树的一个空子树(以p为空表示)，因此空(3)处应填入“p==NULL”或“中!p”。
插入新的结点时，需要建立其与父结点的关系，在查找结点的过程中parent表示待插入结点的父结点。因此根据二叉排序树的定义，待插入元素的值大于其父结点的值，则作为右子结点插入，否则作为左子结点插入。所以，空(4)、(5)分别填入parent-＞Rch和parent-＞Lch。
第8题：
A.在扩展结点处，先生成其所有的儿子结点(分支)
B.从当前的活结点表中选择上一个扩展结点。
C.为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)
D.根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。
第9题：
试题四
阅读下列函数说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。
[函数说明]
函数DeleteNode(Bitree *r,int e)的功能是：在树根结点指针为r的二叉查找（排序）树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
typedef struct Tnode{
int data;
struct Tnode *Lchild,*Rchild;
}*Bitree;
在二叉查找树上删除一个结点时，要考虑三种情况：
1若待删除的结点p是叶子结点，则直接删除该结点；
2若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；
3若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值，然后删除结点s,结点s必属于上述1、2情况之一。
[函数代码]
int DeleteNode(Bitree *r,int e) {
Bitreep = *r, pp, s, c;
while( (1) ) { /*从树根结点出发查找键值为e的结点*/
pp = p;
if ( e< p->data) p = p -> Lchild;
else p = p->Rchild;
}
if(!p) return –1; /* 查找失败 */
if(p->Lchild && p->Rchild) { /* 处理情况3 */
s = (2);pp = p;
while ( (3) ) { pp = s; s = s-> Rchild; }
p->data = s ->data; p = s;
}
/*处理情况1、2*/
if( (4) ) c = p -> Lchild;
elsec = p -> Rchild;
if(p == *r) *r = c;
elseif ( (5) ) pp -> Lchild = c;
elsepp->Rchild = c;
free(p);
return 0;
}
试题分析：
本程序的功能是删除二叉查找树的一个结点。首先，我们来了解一下什么是二叉查找树。
二叉查找树，又称二叉排序树（BinarySort Tree）。一棵二叉查找树，或者是一棵空树，或者满足以下递归条件：
①查找树的左、右子树各是一棵查找树。
②若查找树的左子树非空，则其左子树上的各结点值均小于根结点的值。
③若查找树的右子树非空，则其右子树上的各结点值均大于根结点的值。
例如下图就是一棵二叉查找树。
了解二叉查找树的概念以后，我们再来看题目会有事半功倍的效果。题目中对怎样删除结点有着比较详细的说明。
第一种情况就是删除叶子结节，叶子结节可以直接删除，这一点很好理解，因为叶子结节删除后并不会打乱查找树的顺序。也就是说把上图中的“20”结点删除，剩下的还是一棵查找树。
第二种情况是删除只有一个子结点的结点，只需把其子结点代替父结点即可，也就是说若要删除图中的“56”结点，只需把“51”移至“56”位置即可，若“51”下有子树，子树结构不变。
第三种情况要复杂一点，要用到二叉查找树的一些性质，就是结点右子树的所有结点都大于根结节，左子树所有结点都小于根结点。所以，当删除了有左右子树的结点时，要在左子树找最大的结节，来替换被删结点。也就是说若要删除图中的”89”结点，要把“56”搬到“89”的位置。再用第二种情况规则，把“51”调整到原来56的位置。
现在我们已经了解了算法流程，可以开始具体的分析程序了。
第一句是变量的声明，以及赋初值，p指向二叉查找树的根。接下来是一个循环，从注释部分可以知道，此循环的功能是查找键值为e的结点。循环内有判断条件当e < p->data 时，进入左子树查找，否则到右子树中查找。很明显没有关于找到结点的处理代码，也就是说，循环内部只处理了没找到结点的情况，所以循环条件应是当找到键值为e的结点时退出循环，同时应注意一个隐含的限制条件，就是当p=NULL时，表示已经查找完毕，也不用进入循环了。所以（1）应填 p && p->data != e。
接下来的if 程序段是处理第 ③种情况的，由循环中的“s = s-> Rchild;”可以看出，s用于在要删结点的左子树中查找键值最大的结点。所以s的初值应是：要删除结点的左子结点。所以，（2）应填：p->Lchild。
结合前面提到的对第③条规则的描述以及二叉查找树的规则，我们可知，要找的结点s应是左子树最右的结点，即右子结点为NULL的结节。所以（3）应填S->Rchild。
再下来就是对①、②的处理了，这里并没有把①、②处理分开进行，而是合在一起进行处理，这里引入了一个中间变量c，用c来存储用于替换p的结点。
我们现在来分析一下，怎样的条件可以使这两种情况合在一起，因为当要删除的结点为叶子结点时，p->Lchild与p->Rchild都为NULL，当要删除的结点有一个子结点时，如果有左子结点，则p->Rchild为Null；如果有右子结点，则p->Lchild为NULL。所以当p->Lchild不为NULL时，说明是第二种情况，p结点含左子结点，所以c=p->Lchild，当p->Lchild为NULL时，说明有两种可能：第一，p->Rchild也为NULL，则p是叶子结点。第二，p->Rchild不为NULL，则p是有右子结点的结点。但这两种情况都可以用：c = p->Rchild，因为当p是叶子结点的时候用NULL代替p的位置即可。所以第（4）空，应填 p->Lchild。在程序中很多地方都出现了变量pp，其实只要仔细看一下前面的程序就知道，pp一直指向的是p结点的前一个结点，即p的父结点，所以（5）的作用是，判断p是其父结点的左子结点，还是右子结点，也就是说（5）应填 pp->Lchild == p。
参考答案：（每空3分）
（1）p && p->data != e 或者 p!=NULL && p->data != e
（2）p->Lchild
（3）s->Rchild
（4）p->Lchild
（5）pp->Lchild == p 或者 p == pp->Lchild
第10题：
阅读下列函数说明和C函数，将应填入(n)处。
【函数3说明】
函数DeleteNode(Bitree * r，int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
typedef struct Tnode{
int data； /*结点的键值*/
struct Tnode * Lchild，*Rchild； /*指向左、右子树的指针*/
} * Bitree；
在二叉查找树上删除一个结点时，要考虑三种情况：
①若待删除的结点p是叶子结点，则直接删除该结点；
②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P；
③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。
【函数3】
int DeleteNode(Bitree * r，int e){
Bitree p=*r，pp，s，c；
while((1)){ /*从树根结点出发查找键值为e的结点*/
pp=p；
if(e＜p-＞data)p=p-＞Lchild；
else p=p-＞Rchild；
{
if(!p)return-1； /*查找失败*/
if(p-＞Lchild &&p-＞Rchild){/*处理情况③*/
s=(2)； pp=p；
while((3)){pp=s；s=s-＞Rchild；}
p-＞data=s-＞data；p=s；
}
/*处理情况①、②*/
if((4))c=p-＞Lchild；
else c=p-＞Rchild；
if(p==*r)*r=c；
else if((5))pp-＞Lchild＝c；
else pp-＞Rchild＝c；
free(p)；
return 0；
}
(1)p&&p-＞data!=e或p&&(*p).data!=e(2)p -＞Lchild或(*p).Lchild (3)s-＞Rchild或(*s).Rchild(4)p-＞Lchild或 (*p).Lchild(5)p==pp-＞Lchild或p(*pp).Lchild 解析：(1)程序的第一条语句是变量的声明及赋初值，p指向二叉查找树的根。接下来从while循环的注释部分可以看出，该循环的功能是查找键值为e的结点。当循环的判断条件ep-＞data时，进入左子树查找，否则到右子树查找。程序中没有关于找到结点的处理代码，即循环内部只处理了没找到结点的情况，所以循环条件应该是当找到键值为e的结点时退出循环。另外，应注意一个隐含的限制条件“p’ NULL”时，表示已经查找完毕，无需进入循环。通过分析，(1)应填p &&p-＞data!=e。(2)if程序段是处理第三种情况的，由循环中的语句“s=s-＞Rchild；”可看出，s用于要删结点的左子树中查找键值最大的结点，所以s的初值应是要删除结点的左子结点。可见，(2)应填写 p-＞Lchild。(3)根据前面所述的二叉树规则可知，要找的结点s应是左子树中查找键值最大的结点，所以，的初值应是要删除结点的左子结点。可见，(3)应填p-＞Rehild。本题把①、②结合在一起进行处理，所以引入了一个中间变量c，用c来存储用于替换p的结点。现在的关键问题是什么条件可以使这两种情况和在一起，因为若删除的结点为叶子结点时，p-＞Rchild与p-＞Lchild都为NULL；若删除的结点有一个子结点时，如果有左子结点，则p-＞Rchild为p-＞Rchild；如果有右子结点，则p-＞Lchild为NULL。当p-＞Lchild不为NULL时，说明是第二种情况，p结点含左子结点，所以c=p-＞Lchild；当p-＞Lchild为 NULL时，说明有两种可能：
第一：p-＞Rchild也为NULL，则p是叶子结点。
第二：p-＞Rchild不为NULL，则p是有右子结点的结点。
这两种情况都可以用c=p-＞Rchild，因为当p是叶子结点的时候用NULL代替p的位置即可，所以第(4)应填p-＞Lehild。在程序中很多地方都出现了变量pp，其实只要仔细看一下前面的程序就知道，pp一直指向的是p结点的前一个结点，即p的父结点，所以(5)的作用是判断p是其父结点的左子结点还是右子结点，(5)应填pp-＞Lchild =p。