d0c194b8a60baae657c6cc1308ead715_在线真题试卷与模拟练习_d0c194b8a60baae657c6cc1308ead715_考试宝

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

有效期：个月

章节介绍：共有个章节

收藏

我的练习

我的错题
(0道)

我的收藏
(0道)

我的斩题
(0道)

我的笔记
(0道)

专项练习

顺序练习 0 / 0

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

题型乱序 按导入顺序练习

模拟考试 仿真模拟

题型练习 按题型分类练习

易错题 精选高频易错题

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

搜索

题库预览

画出哈希表的示意图；

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

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

假定每个关键字的查找概率相等，求查找成功时的平均查找长度。【缺少答案，请补充】

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

线性探测法；

链地址法。【缺少答案，请补充】

试写出折半查找的递归算法。[算法描述]int BinSrch( rectype r[], int k, low, high )//在长为n的有序表中查找关键字k，若查找成功，返回k所在位置，查找失败返回0。

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

试写出折半查找的递归算法。 [算法描述] 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）；// 中序遍历左子树

已知二叉排序树采用二叉链表存储结构，根结点的指针为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） {p=p->lchild；//找第一个值<x的结点 {f=p；while（p && p->data≥x）//沿左分枝向下，找第一个值<x的结点 f=p；p=p->lchild ；}//f是p的双亲结点的指针，指向第一个值≥x的结点 if（f->lchild!=null；//双亲与找到的第一个值<x的结点断开 Print（bst）；//输出以bst为根的子树 }//内层if（p） }//第一层if（p） }//PrintAllx

已知二叉树T的结点形式为（limg,data,count,link），在树中查找值为X的结点，若找到，则计数（count）加1，否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。 [算法描述] void SearchBST(BTree &T,int target){ BTree s,q,f; //以数据值target新建结点s s=new BTreeNode; s->data=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; }

假设一棵平衡二叉树的每个结点都表明了平衡因子b，试设计一个算法，求平衡二叉树的高度。 [题目分析] 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左右一分枝向下查找，若b不为0，则沿左（当b=1时）或右（当b=-1时）向下查找。 [算法描述] int Height（BSTree t） // 求平衡二叉树t的高度 {level=0; p=t; while（p） {level++；// 树的高度增1 if（p->bf<0）p=p->rchild; //bf=-1 沿右分枝向下 //bf是平衡因子，是二叉树t结点的一个域，因篇幅所限，没有写出其存储定义 else p=p->lchild; //bf>=0 沿左分枝向下 }//while return （level）;//平衡二叉树的高度 } //算法结束

分别写出在散列表中插入和删除关键字为K的一个记录的算法，设散列函数为H，解决冲突的方法为链地址法。 [算法描述] bool insert(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; //初始化散列表 while(p->next){ if(p->next->data ==data) return false; p=p->next; } //找到插入位置 LinkList s; s=new LNode; s->data=data; s->next=p->next; p->next=s; //插入该结点 return true; } bool deletes(){ int data; cin>>data; int ant=hash(data); LinkList p=HT[ant]; //初始化散列表 while(p->next){ if(p->next->data ==data){ LinkList s=p->next; p->next=s->next; delete s; //删除该结点 return true; } //找到删除位置 p=p->next; //遍历下一个结点 } return false; }

从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。

从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。

对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。

对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。

快速排序在下列（）情况下最易发挥其长处。

对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。

若一组记录的排序码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

下列关键字序列中，（）是堆。

堆是一种（）排序。