题目
第3题
●试题三
阅读下列函数说明和C代码,将应填入(n)处的字句写在答题纸的对应栏内。
【说明3.1】
假设以带头结点的单循环链表作非递减有序线性表的存储结构。函数deleteklist(LinkList head)的功能是删除表中所有数值相同的多余元素,并释放结点空间。
例如:链表初始元素为:
(7,10,10,21,30,42,42,42,51,70)
经算法操作后变为:
(7,10,21,30,42,51,70)
【函数3.1】
void deleteklist(LinkList head)
{
LinkNode*p,*q;
p=head->next;
while(p!=head)
{
q=p->next;
while((1) )
{
(2) ;
free(q);
q=p->next;
}
p=p->next;
}
}
【说明3.2】
已知一棵完全二叉树存放于一个一维数组T[n]中,T[n]中存放的是各结点的值。下面的程序的功能是:从T[0]开始顺序读出各结点的值,建立该二叉树的二叉链表表示。
【函数3.2】
#include<istream.h>
typedef struct node {
int data;
stuct node leftChild,rightchild;
}BintreeNode;
typedef BintreeNode*BinaryTree;
void ConstrncTree(int T[],int n,int i,BintreeNode*&ptr)
{
if(i>=n) (3) ;∥置根指针为空
else
{
ptr=-(BTNode*)malloc(sizeof(BTNode))
ptr->data=T[i];
ConstrucTree(T,n,2*i+1, (4) );
ConstrucTree(T,n, (5) ,ptr->rightchild);
}
}
main(void)
{/*根据顺序存储结构建立二叉链表*/
Binarytree bitree;int n;
printf("please enter the number of node:\n%s";n);
int*A=(int*)malloc(n*sizeof(int));
for(int i=0;i<n;i++)scanf("%d,A+i);/*从键盘输入结点值*/
for(int i=0;i<n;i++)printf("%d",A[i]);
ConstructTree(A,n,0,bitree);
}
第4题
编写算法由二叉树的动态二叉链表构造出相应的静态二又链表a[1..
第5题
第6题
以二叉链表作为二叉树的存储结构,编写以下算法:
(1)统计二叉树的叶结点个数。
(2)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。
(3)计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。
(4)用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。
(5)求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。
(6)输出二叉树中从每个叶子结点到根结点的路径。
第7题
一个具有m个结点的二叉树,其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树,现对该二叉链表所有结点进行如下操作:若结点p的左孩子指针为空,则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点;若p的右孩子指针为空,则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点,则(58)。
A.m+2
B.m+1
C.m
D.m-1
第8题
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BtNode{
ElemTypedata; /*结点的数据域,ElemType的具体定义省略*/
struct BtNode*ichiid,*rchild; /*结点的左、右弦子指针域*/
)BtNode,*BTree;
在函数InOrder()中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点
的单向链表(简称链栈),其结点类型定义如下:
typedef struct StNode{ /*链栈的结点类型*/
BTree elem; /*栈中的元素是指向二叉链表结点的指针*/
struct StNode*link;
}S%Node;
假设从栈顶到栈底的元素为en、en-1、…、e1,则不含头结点的链栈示意图如图5—5
所示。
【C函数】
int InOrder(BTree root) /*实现二叉树的非递归中序遍历*/
{
BTree ptr; /*ptr用于指向二又树中的结点*/
StNode*q; /*q暂存链栈中新创建或待删除的结点指针+/
StNode*stacktop=NULL; /*初始化空栈的栈顶指针stacktop*/
ptr=root; /*ptr指向二叉树的根结点*/
while((1 ) I I stacktop!=NULL){
while(ptr!=NULL){
q=(StNode*)malloc(sizeof(StNode));
if(q==NULL)
return-1;
q->elem=ptr;(2) ;
stacktop=q; /*stacktop指向新的栈顶*/
ptr=(3 ) ; /*进入左子树*/
}
q=stacktop; (4) ; /*栈顶元素出栈*/
visit(q); /*visit是访问结点的函数,其具体定义省略*/
ptr= (5) ; /*进入右子树*/
free(q); /*释放原栈顶元素的结点空间*/
}
return 0;
}/*InOrder*/
第9题
根结点的数据,LT和RT是括号形式的左子树和右子树。要求空树不打印任何信息,一个结点的树的打印形式是x,而不应是(x,)的形式。
第10题
【C代码】 int lnsertBST(BSTree*rootptr,KeyType kword) /*在二叉查找树中插入一个键值为kword的结点,若插入成功返回1,否则返回0; *rootptr为二叉查找树根结点的指针 */ { BSTree p,father; (1) ; /*将father初始化为空指针*/ p=*rootptr; /*p指示二叉查找树的根节点*/ while(p&& (2) ){ /*在二叉查找树中查找键值kword的结点*/ father=p; if(kword<p->key) p=p->left; else p=p->right; } if((3) )return 0; /*二叉查找树中已包含键值kword,插入失败*/ p=(BSTree)malloc((4) ); /*创建新结点用来保存键值kword*/ If(!p)return 0; /*创建新结点失败*/ p->key=kword; p->left=NULL; p->right=NULL; If(!father) (5) =p; /*二叉查找树为空树时新结点作为树根插入*/ else if(kword<father->key) (6) ; /*作为左孩子结点插入*/ else (7) ; /*作右孩子结点插入*/ return 1; }/*InsertBST*/
为了保护您的账号安全,请在“赏学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!