早教吧 育儿知识 作业答案 考试题库 百科 知识分享

大专考试数据结构题一、单项选择题(每题5分,共30分)1.以下说法正确的是()。A.连能分量是无向图中的极小连通子图B.强连通分量是有向图中的极大强连通子图C.在一个有向图

题目详情
大专考试数据结构题
一、单项选择题(每题5分,共30分)
1. 以下说法正确的是(  )。
A.连能分量是无向图中的极小连通子图
B.强连通分量是有向图中的极大强连通子图
C.在一个有向图的拓扑序列中若顶点a在顶点b之前,则图中必有一条弧
D.对有向图G,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点,则该图一定是完全图
2. 求解最短路径的Floyd算法的时间复杂度为(  )。
A.O(n) B.O(n+c)
C.O(n*n) D.O(n*n*n)
3. 采用邻接表存储的图,其广度优先遍历类似于二叉树的( )。
A.按层次遍历 B.中序遍历
C.后序遍历 D.先序遍历
4. 假定一个顺序循环队列的队首和队尾指针分别用front和rear表示,则判断队空的条件为( )。
A.front+1= =rear B.rear+1= =front
C.front= =0 D.front= =rear
5. 从一个顺序循环队列中删除元素时,首先需要( )。
A.前移队首指针 B.后移队首指针
C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素
二、填空题(每空2分,共20分)
1. 在栈的运算中,栈的插入操作称为_________或_________,栈的删除操作称为或_________。
2. 当栈满的时候,再进行入栈操作就会产生_________,这种情况的溢出称为_________;当栈空的时候,如果再进行出栈操作,也会_________,这种情况下的溢出称为_________。
3. 串中字符的个数称为串的 。
4. 一个连通图的   是一个极小连通子图。
三、算法(10分)
请阅读下列算法,回答问题
PROCEDURE sort(r,n)
BEGIN
FOR i:=2 TO n DO
BEGIN
x:=r(i);r(O):=x;j:=i-1;
WHILE x.key BEGIN
r(j+1):=r(j); j:=j-1
END;
r(j+1):=x
END
END;
问题一:这是什么类型的排序算法,该排序算法稳定吗?
问题二:设置r(O)的作用是什么?若将WHILE-DO 语句中判断条件改为x.key<=r(j).KEY,该算法将会有什么变化,是否还能正确工作?
四、应用题(共40分)
1、 分别论述在稠密索引文件和非稠密索引文件的查找一个记录时,首先查什么?然后查什么?
2、 散列表存储的基本思想是什么?
3、 对一个图进行遍历可以得到不同的遍历序列,那么导致得到的遍历序列不唯一的因素有哪些?
4、 在执行某个排序方法的过程中,出现排序码朝着最终排序序列相反的方向移动,从而认为该排序算法是不稳定的。这种说法对吗?为什么?
▼优质解答
答案和解析
单选
1 B2C 3D 4D 5B
填空
1 进栈,入栈,退栈
2 溢出 ,上溢,溢出,下溢
3 长度
4 生成树
算法
1 直接插入排序,稳定
2 r(O)有岗哨作用,改为x.key<=r(j).KEY,该算法不稳定了,能正确工作
应用题
1稠密索引文件查找记录:由于数据文件中记录不按关键字顺序排列,必须对每个记录建立一个索引记录(或索引项)。在索引项中进行“预查找”,即从索引项中便可确定待查找记录是否存在。
非稠密索引文件查找记录:首先要在非稠密索引中找到小于特定值的最大搜索码的索引项所在的位置,然后根据索引项中的记录指针找到文件中的记录。由于是非稠密索引,找到的记录不一定是我们需要的,因此还要根据顺序文件的搜索码链表(记录在逻辑上按照搜索码顺序链接起来形成的)去查找我们需要的记录即可。
2散列表存储的基本思想是用关键字的值决定数据元素的存储地址
3 遍历不唯一的因素有:开始遍历的顶点不同;存储结构不同;在邻接表情况下邻接点的顺序不同。
4这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化,而题中叙述和排序中稳定性的定义无关,所以此说法不对。对4,3,2,1起泡排序就可否定本题结论。
看了 大专考试数据结构题一、单项选...的网友还看了以下:

在如图所示的空间坐标系中,y轴的左边有一匀强电场,场强大小为E,场强方向跟y轴负向成30°,y的右  2020-05-17 …

数据结构图的问题、.一个n个顶点的有向强连通图最多有条边,最少有条边.一个n个顶点的无向连通图最多  2020-06-27 …

大专考试数据结构题一、单项选择题(每题5分,共30分)1.以下说法正确的是()。A.连能分量是无向  2020-06-28 …

如图所示,实线表示一簇关于x轴对称的等势面,在x轴上有A、B两点,则()A.A、B两点的场强方向与  2020-07-01 …

在如图所示的空间区域里,y轴左方有一匀强电场,场强方向跟y轴正方向成60°,大小为E=4.0×10  2020-07-17 …

鱼我所欲也强调人人都有向善之心的句子是?结尾此之谓失其本心照应开头的哪句话?体现中心论点的句子鱼我  2020-07-24 …

电势和场强的关系是什么1.场强方向垂直于等势面的方向吗,为什么会这样?(是不是只有匀强电场才是场强方  2020-11-08 …

关于物理的电势,我纠结电势不是沿着电场线方向逐渐降低么?那么为什么电势降低的方向不一定是场强方向呢?  2020-12-07 …

下列实验的结论正确的是()选项实验操作现象结论A向蔗糖中加入浓硫酸蔗糖变黑,体积膨胀浓硫酸具有吸水性  2020-12-17 …

关于静电场,下列结论普遍成立的是()A.在正电荷或负电荷产生的静电场中,场强方向都指向电势降低最快的  2021-02-05 …