大专考试数据结构题一、单项选择题(每题5分,共30分)1. 以下说法正确的是( )。A.连能分量是无向图中的极小连通子
来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/05/01 15:17:53
大专考试数据结构题
一、单项选择题(每题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、 在执行某个排序方法的过程中,出现排序码朝着最终排序序列相反的方向移动,从而认为该排序算法是不稳定的。这种说法对吗?为什么?
一、单项选择题(每题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
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
1 B2C 3D 4D 5B
填空
1 进栈,入栈,退栈
2 溢出 ,上溢,溢出,下溢
3 长度
4 生成树
算法
1 直接插入排序,稳定
2 r(O)有岗哨作用,改为x.key
大专考试数据结构题一、单项选择题(每题5分,共30分)1. 以下说法正确的是( )。A.连能分量是无向图中的极小连通子
有向图G的强连通分量是指-----,一个连通图的---是一个极小连通子图
一、单项选择题(每题5分,共30分)
一、选择题(每小题2分,共24分) 1.关于声音的传播,下列说法正确的是( ) A.声音的传播速度为3×108m
一、物理选择题(每题只有一个答案是正确的,每题3分,共24分)
一、单项选择题(每小题1分,共30分,必做)
一、单项选择题(每小题2分,共50分) 1.一天中有昼夜的变化与更替,这些变 化是由( )引起的.A.太阳高度角的变化
二、单项选择题(将正确的答案填在表内.每小题2分,共12分)
无向连通图的连通分量!
《大学语文》作业一、单项选择题:(每小题1分,共10分)1、主张顺其自然,提倡无为而无不为的思想家是( ). A.孔子
一、选择题(每小题2分,共40分.每小题给出的四个选项中,只有一个选项是正确.) 1.感受身
一、单项选择题(每题2分,共30题)