没有合适的资源?快使用搜索试试~ 我知道了~
数据结构试题及答案(11套最新).docx
0 下载量 187 浏览量
2022-12-18
03:25:35
上传
评论
收藏 2.37MB DOCX 举报
温馨提示
试读
121页
数据结构试题及答案(11套最新).docx
资源推荐
资源详情
资源评论
单项选择题(每题2分,共20分)
1. 1.对一个算法的评价,不包括如下(B )方面的内容。
A.健壮性和可读性B.并行性 C.正确性 D.时空复杂度2.在带有头结点的单链
表HL中,要向表头插入一个由指针p指向的结 点,那么执行(A )0
A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;C. p->next=HL; p=HL;D.
HL=p; p->next=HL;
2. 3.对线性表,在以下哪种情况下应当采用链表表示?(B )A.经常需要随机地
存取元素B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 一个栈
的输入序列为12 3,那么以下序列中不可能是栈的输出序列的是 (C )
A. 23 1B. 32 1C. 3 1 2D. 1 23
3. 5. AOV 网是一种(D )
0
A.有向图 B.无向图 C.无向无环图D.有向无环图
4. 6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)。
A.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同D.高
于二分查找
5. 7.假设需要利用形参直接访问实参时,应将形参变量说明为(D )参数。
A.值 B.函数 C.指针D.引用8.在稀疏矩阵的带行指针向量的链接存储中,每
个单链表中的结点都具 有相同的(A )o
A.行号 B.列号 C.元素值 D.非零元素个数
6. 9.快速排序在最坏情况下的时间复杂度为(D )。
A. O(log2n) B. O(nlog2n) C. 0(n)D. 0(n
2
)
10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为(C)。
A. O(n) B. 0(1) C. O(log
2
n) D. O(n
2
)二、 运算题(每题6分,共24分)
1. 1.数据结构是指数据及其相互之间的。当结点之间存在M 对N (M: N)的联系时,
称这种结构为 o2.队列的插入操作是在队列的一一尾 进行,删除操作是在队列
的—
首 进行。
2. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,那么 表示栈
满的条件是—top==0—(要超出才为满)o4.对于一个长度为n的单链存储的线性表,
在表头插入元素的时间复杂度 为,在表尾插入元素的时间复杂度为 o
阅读算法(每题7分,共14分)
1 .(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表
为(a2,a3/--,a
n
,ai)
2 .递归地后序遍历链式存储的二叉树二算法填空(每空2分,共8分)
true BST->left BST->right编写算法(8分)
int CountX(LNode* HL,ElemType x){ int i=0; LNode* p=HL;//i 为计数器 while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while,出循环时i中的值即为x结点个数 return i;
}//CountX
⑶含n个顶点的连通图中的任意一条简单路径,其长度不可能超过()。
A 1 B n/2 C n-1 D n
【解答】C
【分析】假设超过n-1,那么路径中必存在重复的顶点。
(4)对于一个具有n个顶点的无向图,假设采用邻接矩阵存储,那么该矩阵的大小是()。
An B (n-l)2 C n-1 D n2
【解答】D⑸图的生成树(),n个顶点的生成树有()条边。
A唯一B不唯一 C唯一性不能确定D n E n +1 F n-1
【解答】C, F(6)设无向图G=(V, E)和G'=(V', E'),如果G'是G的生成树,那么下面的说法中
错误的选项是()。
A G'为G的子图B G'为G的连通分量C G为G的极小连通子图且V = V, D G'是G的一个无环子图
【解答】B
【分析】连通分量是无向图的极大连通子图,其中极大的含义是将依附于连通分量中顶点的所有边都加上, 所
以,连通分量中可能存在回路。
⑺G是一个非连通无向图,共有28条边,那么该图至少有()个顶点。
A6B7C8D9
【解答】D
【分析】n个顶点的无向图中,边数eWn(n-l)/2,将e=28代入,有n28,现无向图非连通,那么n=9。
(8)最小生成树指的是()。
A由连通网所得到的边数最少的生成树B由连通网所得到的顶点数相对较少的生成树
C连通网中所有生成树中权值之和为最小的生成树D连通网的极小连通子图
⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。
A求关键路径的方法B求最短路径的方法C广度优先遍历算法D深度优先遍历算法
【解答】D
【分析】当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)
即为逆向的拓扑序列。
⑩ 下面关于工程计划的AOE网的表达中,不正确的选项是()?br/>A关键活动不按期完成就会影响整个工
程的完成时间B任何一个关键活动提前完成,那么整个工程将会提前完成
C所有的关键活动都提前完成,那么整个工程将会提前完成D某些关键活动假设提前完成,那么整个工程将会
提前完
【解答】B
【分析】AOE网中的关键路径可能不止一条,如果某一个关键活动提前完成,还不能提前整个工程,而必 须
同时提高在几条关键路径上的关键活动。
3 .判断题⑴一个有向图的邻接表和逆邻接表中的结点个数一定相等。
【解答】对。邻接表和逆邻接表的区别仅在于出边和入边,边表中的结点个数都等于有向图中边的个数。
⑵用邻接矩阵存储图,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关。
【解答】对。邻接矩阵的空间复杂度为0(n2),与边的个数无关。
⑶图G的生成树是该图的一个极小连通子图
【解答】错。必须包含全部顶点。
(4)无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的
【解答】错。有向图的邻接矩阵不一定对称,例如有向完全图的邻接矩阵就是对称的。
⑸ 对任意一个图,从某顶点出发进行一次深度优先或广度优先遍历,可访问图的所有顶点。
【解答】错。只有连通图从某顶点出发进行一次遍历,可访问图的所有顶点。
(6)在一个有向图的拓扑序列中,假设顶点a在顶点b之前,那么图中必有一条弧。
【解答】错。只能说明从顶点a到顶点b有一条路径。
⑺假设一个有向图的邻接矩阵中对角线以下元素均为零,那么该图的拓扑序列必定存在。
【解答】对。参见第11题的证明。
(8)在AOE网中一定只有一条关键路径?br/>【解答】错。AOE网中可能有不止一条关键路径,他们的路
径长度相同。
4 . n个顶点的无向图,采用邻接表存储,回答以下问题?br/>(D图中有多少条边?
⑵ 任意两个顶点i和j是否有边相连?
⑶ 任意一个顶点的度是多少?br/>【解答】⑴ 边表中的结点个数之和除以2。
⑵第i个边表中是否含有结点j。
⑶该顶点所对应的边表中所含结点个数。
5 . n个顶点的无向图,采用邻接矩阵存储,回答以下问题:
⑴图中有多少条边?
⑵ 任意两个顶点i和j是否有边相连?
⑶ 任意一个顶点的度是多少?
【解答】⑴ 邻接矩阵中非零元素个数的总和除以2。
⑵ 当邻接矩阵A中(或= 时,表示两顶点之间有边相连。
⑶计算邻接矩阵上该顶点对应的行上非零元素的个数。
6 .证明:生成树中最长路径的起点和终点的度均为1。
【解答】用反证法证明。
设vl,v2,…,vk是生成树的一条最长路径,其中,vl为起点,vk为终点。假设vk的度为2,取vk的另一个 邻接点
v,由于生成树中无回路,所以,v在最长路径上,显然vl,v2,…,vk,v的路径最长,与假设矛盾。 所以生成树中
最长路径的终点的度为lo同理可证起点vl的度不能大于1,只能为1。
7 .一个连通图如图6-6所示,试给出图的邻接矩阵和邻接表存储示意图,假设从顶点vl出发对该图进 行遍历,
分别给出一个按深度优先遍历和广度优先遍历的顶点序列。
【解答】邻接矩阵表示如下:
0 10 1 1110
0 0 10 0 0 11 110 0
0 10 0深度优先遍历序列为:vl v2 v3 v5 v4 v6 广度优先遍历序列为:vl v2 v4 v6 v3 v5 邻接表表
示如下:
8 .图6-7所示是一个无向带权图,请分别按Prim算法和K「uskdl算法求最小生成树。
0 1
1 0
0 1
1 1
0 1
1 0
剩余120页未读,继续阅读
资源评论
智慧安全方案
- 粉丝: 3679
- 资源: 59万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功