数据结构（c语言版）（第2版双色版）-习题答案

更新时间：试题数量：购买人数：提供作者：

有效期：个月

章节介绍：共有个章节

收藏

我的练习

我的错题
(0道)

我的收藏
(0道)

我的斩题
(0道)

我的笔记
(0道)

专项练习

顺序练习 练习进度 0 / 0

随机练习 自定义设置练习量

模拟考试 仿真模拟

题型练习 按题型分类练习

易错题 精选高频易错题

学习资料 考试学习相关信息

搜索

题库预览

在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。

下列关于m阶B-树的说法错误的是（）。

下面关于B-和B+树的叙述中，不正确的是（）。

m阶B-树是一棵（）。

下面关于哈希查找的说法，正确的是（）。

下面关于哈希查找的说法，不正确的是（）。

设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。

采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）。

画出描述折半查找过程的判定树；（含图）

若查找元素54，需依次与哪些元素比较？

若查找元素90，需依次与哪些元素比较？

假定每个元素的查找概率相等，求查找成功时的平均查找长度。

在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。（含图）

试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（含图）

若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。（含图）

对图7.31所示的3阶B-树，依次执行下列操作，画出各步操作的结果。 ① 插入90 ② 插入25 ③ 插入45 ④ 删除60（含图）（含图）

画出哈希表的示意图；

画出哈希表的示意图；

若查找关键字63，需要依次与哪些关键字进行比较？

若查找关键字60，需要依次与哪些关键字比较？

假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度$$ASL_{succ}$$和$$ASL_{unsucc}$$。 ① 线性探测法； ② 链地址法。

试写出折半查找的递归算法。 [算法描述] int BinSrch (rectype r[ ], int k, low, high) //在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。 {if (low≤high) //low和high分别是有序表的下界和上界 {mid= (low+high)/2; if (r[mid].key==k) return (mid); else if (r[mid].key>k) return (BinSrch (r,k, mid+1, high)); else return (BinSrch (r,k, low, mid-1)); } else return (0); //查找失败。 }//算法结束

试写一个判别给定二叉树是否为二叉排序树的算法。 [题目分析] 根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。 [算法描述] #define true 1 #define false 0 typedef struct node {datatype data; struct node *lchild,*rchild;} *BTree; void JudgeBST (BTree T,int flag) // 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 { if (T!=null && flag) { Judgebst (T->lchild,flag); // 中序遍历左子树 if (pre==null) pre=T; // 中序遍历的第一个结点不必判断 else if (pre->data<T->data) pre=T; //前驱指针指向当前结点 else{flag=flase; } //不是完全二叉树 Judgebst (T->rchild,flag); // 中序遍历右子树 }}//JudgeBST算法结束

已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild，rchild分别指向该结点左、右孩子的指针，data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值≥x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。 [题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值≥x,则除左分枝中可能有<x的结点外都应输出。所以从根结点开始查找，找到结点值<x的结点后，将其与双亲断开开出整棵二叉排序树。如果根结点的值<x,则沿右子树查找第一个≥x的结点，找到后，与上面同样处理。 void Print (BSTree t) // 中序输出以t为根的二叉排序树的结点 {if (t) {Print (t->lchild); Cout<<t->data; Print (t->rchild); } } void PrintAllx(BSTree bst, datatype x) //在二叉排序树bst中，查找值≥x的结点并输出 {p=bst; if (p) {while (p && p->data<x) p=p->rchild; //沿右分枝找第一个值≥x的结点 bst=p; //bst所指结点是值≥x的结点的树的根 if (p) {f=p; p=p->lchild ; //找第一个值<x的结点 while (p && p->data≥x) //沿左分枝向下，找第一个值<x的结点 {f=p; p=p->lchild ; } //f是p的双亲结点的指针，指向第一个值≥x的结点 if(p) f->lchild=null; //双亲与找到的第一个值<x的结点断开 Print(bst); //输出以bst为根的子树 }//while }//内层if (p) }//第一层if (p) }//PrintAllx

已知二叉树T的结点形式为（lling,data,count,rlink），在树中查找值为X的结点，若找到，则记数（count）加1，否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 [算法描述] void SearchBST(BiTree &T,int target){ BiTree s,q,f; //以数据值target,新建结点s s=new BiTNode; s->data.x=target; s->data.count=0; s->lchild=s->rchild=NULL; if(!T){ T=s; return ; } //如果该树为空则跳出该函数 f=NULL; q=T; while (q){ if (q->data.x==target){ q->data.count++; return ; } //如果找到该值则计数加一 f=q; if (q->data.x>target) //如果查找值比目标值大，则为该树左孩子 q=q->lchild; else //否则为右孩子 q=q->rchild; } //将新结点插入树中 if(f->data.x>target) f->lchild=s; else f->rchild=s; }