模拟习题4.docx
- 文档编号:10563310
- 上传时间:2023-05-26
- 格式:DOCX
- 页数:10
- 大小:129.04KB
模拟习题4.docx
《模拟习题4.docx》由会员分享,可在线阅读,更多相关《模拟习题4.docx(10页珍藏版)》请在冰点文库上搜索。
模拟习题4
模拟习题4
模拟试题4
一、选择题(20分)
1.n个顶点的无向图的邻接表中结点总数最多有()个。
(A)2n(B)n(C)n/2(D)n(n-1)
2.设连通图G的顶点数为n,则G的生成树的边数为()。
(A)n(B)n-1(C)2n(D)2n-1
3.下列哪种排序需要的附加存储开销最小()。
(A)快速排序(B)堆排序(C)归并排序(D)计数排序//应该是“基数”
4.若按()列出二叉搜索树中所存储的元素,则恰好是集合中所有元素从小到大的排序。
(A)先序(B)中序(C)后序(D)按层次
5.在图1所示的4棵树中,哪一棵是完全二叉树()。
(A)(B)(C)(D)
图1
6.下面程序段的时间复杂度为()。
s=s0;
for(i=1;i<=n;i++)
{
for(j=n;j>=n-1;j--)//应是for(j=n;j>=i-1;j--)
{
s=s+1;
}
}
(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(n3/2)
7.采用链结构存储线性表时,其地址(B)。
(A)必须是连续的(B)连续不连续都可以
(C)部分地址必须是连续的(D)必须是不连续的
8.具有2000个结点的二叉树,其高度至少为()。
(A)9(B)10(C)11(D)12
9.若按字典顺序排序,则图中(C)为二叉搜索树。
(A)(B)(C)(D)
10.设单链表中指针p指向结点A,若要删除A后的结点(若存在),则需要修改指针的操作为()。
(A)p->next=p->next->next(B)p=p->next;
(C)p=p->next->next(D)p->next=p
二、判断题(10分)
1.具有线性关系集合中,若a,b是集合中的任意两个元素,则必定有a
()
2.二叉搜索树的左、右子树都是二叉搜索树。
()
3.在堆中执行INSERT和DELETEMIN运算都只需O(log2n)时间。
()
4.一棵满二叉树同时又是一棵平衡树。
()
5.即使某排序算法是不稳定的,但该方法仍有实际应用价值。
()
6.连通分量是无向图中的极小连通子图。
()
7.先序遍历一棵二叉搜索树所的结点访问序列不可能是键值递增序列。
()
8.不管adt栈是用数组实现,还是用指针实现,Pop(s)与Push(x,s)的耗时均为O(n)。
()
9.表中的每一个元素都有一个前驱元素和一个后继元素。
()
10.作为解决一类特定问题的算法,不能没有输
并求出等概率下成功查找的平均查找长度。
(5分)
2.设图2所示的二叉树是森林转换而成的,试将它还原为森林。
(6分)
图2图3
3.树与二叉树之间有何区别?
(6分)
4.在如图3所示的结构中(6分)
(1)要求用Kruskal算法求出最小生成树;
(2)指出生成树的第一条
五、算法设计(27分)
1.编一个程序,输出二叉搜索树BT中的最小键值(7分)
2.用链表存储多项式Pn(x)=C1xe1+C2xe2+…+Cmxem,其中n=em>em-1>…>e1>=0,Ci!
=0(i=1,2,…,m,m>1),试编写求Pn(x)微商的算法(注:
d(xk)/dx=Kxk-1分)。
(10分)
3.设计一个算法,求出指定结点在给定的二叉树中所在的层次。
(10分)
模拟试题4参考答案
一、选择题
题号
1
2
3
4
5
6
7
8
9
10
答案
D
B
B
B
C
C
C
B
C
A
二、判断题
1.×2.√3.√4.×5.√6.×7.×8.×9.×10.×
三、填空题
1.f->priorp->next->prior
2.0
3.n(n-1)
4.有序集
5.n/2
6.开散列表闭散列表
7.49
8.h2h-1
四、应用题
1.解答:
在等概率下成功查找的平均查找长度为:
ASL=(1+2*2+3*3+2*4)/8=2.8
2.解答:
//下图错!
E应是C的孩子
3.解答:
(1) 二叉树的任一结点都有两棵子树(其中一个或两个为空),而树中每个元素可以有若干子树;
(2)在二叉树中每个元素的子树都是有序的,也就是说,可以用左、右子树来区别。
而树的子树间是无序的。
4.解答:
//下图错!
最小生成树依次产生的边为:
(3,4),(1,2),(1,5),(2,4),(4,18)
最小生成树的第一条边是结点3和结点4的边,权值为3
五、算法设计
1.解答:
//该算法求的是最大键值
voidmin(bitree*BT)
{
bitree*p;
p=BT;
while(p->rchild!
=NULL)
{
p=p->rchild;
}
printf("%d\n",p->key);
}
2.解答:
链表的单元意义如下:
typedefstructNode
{
floatcoef;/*系数域*/
intexp;/*指数域*/
structnode*next;
}List;
算法描述为:
voiddifferential(List*head)
{
List*p,*q;
p=head;
q=head->next;
while(q!
=NULL)
{
if(q->exp-1>-1)
{
/*非常数项*/
q->coef=q->coef*q->exp;
q->exp=q->exp-1;
p=p->next;
q=q->next;
}
else
{
/*常数项,去掉该项*/
p->next=q->next;
free(q);
q=p->next;
}
}
}
}
3.解答:
//该算法求出的是指定结点在给定的二叉排序树中所在的层次,并且该算法假定指定结点在树中一定存在
intLevel(bitree*t,bitree*p)
{
intcount;
count==0;
if(t==NULL)
{
return0;
}
else
{
++count;
while(t->data!
=p->data)
{
if(t->data
{
t=t->rchild;
}
else
{
t=t->lchild;
}
++count;
}
}
returncount;
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 习题