数据结构复习题题集
错误！未指定书签。
1.选择题
1.1. 图中有关路径的定义是
A).由顶点和相邻顶点序偶构成的边所形成的序列
B).由不同顶点所形成的序列
C).由不同边所形成的序列
D).上述定义都不是
答案：A
分析：本题考查图的相关知识，根据图的有关路径定义可知，图中有关路径的定义是由顶点和相邻顶点序偶构成的边所形成的序列。
知识点：图的定义与术语
难度：易
1.2. 设无向图的顶点个数为n，则该图最多有（）条边
A).n-1
B).n(n-1)/2
C).n(n+1)/2
D).n2
答案：B
分析：本题考查图的相关知识，根据无向图的定义可知，无向图的顶点个数为n，则该图最多有n(n-1)/2条边。
知识点：图的定义与术语
难度：中
1.3. 一个n个顶点的连通无向图，其边的个数至少为（）
A).n-1
B).n
C).n+1
D).nlogn
答案：A
分析：本题考查图的相关知识，根据连通无向图的定义可知，一个n个顶点的连通无向图，其边的个数至少为n-1。
知识点：图的定义与术语
难度：中
1.4. 要连通具有n个顶点的有向图，至少需要（）条边
A).n-l
B).n
C).n+l
D).2n
答案：B
分析：本题考查图的相关知识，根据连通有向图的定义可知，要连通具有n个顶点的有向图，至少需要n条边。
知识点：图的定义与术语
难度：易
1.5. n个结点的完全有向图含有边的数目为
A).n*n
B).n（n＋１）
C).n／2
D).n*（n－l）
答案：D
分析：本题考查图的相关知识，根据完全有向图的定义可知，n个结点的完全有向图含有边的数目为n*（n－l）。
知识点：图的定义与术语
难度：中
1.6. 一个有n个结点的图，最少有（）个连通分量
A).0
B). 1
C).n-1
D).n
答案：B
分析：本题考查图的相关知识，根据连通分量的定义可知，一个有n个结点的图，最少有1个连通分量。
知识点：图的定义与术语
难度：中
1.7. 一个有n个结点的图，最多有（）个连通分量
A).0
B). 1
C).n-1
D).n
答案：D
分析：本题考查图的相关知识，根据连通分量的定义可知，一个有n个结点的图，最多有n个连通分量。
知识点：图的定义与术语
难度：易
1.8. 在一个无向图中，所有顶点的度数之和等于所有边数（）倍
A).1/2
B). 1
C). 2
D). 4
答案：C
分析：本题考查图的相关知识，根据无向图的定义可知，在无向图中所有顶点的度数之和等于所有边数2倍。
知识点：图的定义与术语
难度：中
1.9. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍
A).1/2
B). 1
C). 2
D). 4
答案：B
分析：本题考查图的相关知识，根据有向图的定义可知，在有向图中所有顶点的入度之和等于所有顶点出度之和的1倍。
知识点：图的定义与术语
难度：中
1.10. 用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( )
A). 5
B). 6
C).8
D).9
答案：A
分析：本题考查图的相关知识，根据无环图的定义可知，至少需要顶点的数目为5。
知识点：图的定义与术语
难度：难
1.11. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输
出的顶点序列是( )
A).逆拓扑有序
B).拓扑有序
C).无序的
D).不能确定
答案：A
分析：本题考查图的相关知识，根据DFS遍历算法的定义可知，DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序的。
知识点：图的遍历
难度：难
1.1
2. 下面结构中最适于表示稀疏无向图的是
A).邻接矩阵
B).逆邻接表
C).邻接多重表
D).十字链表
答案：C
分析：本题考查图的相关知识，根据稀疏无向图的定义可知，邻接多重表最适于表示稀疏无向图。
知识点：图的存储结构
难度：易
1.13. 下面结构中适于表示稀疏有向图的是(多选)
A). 邻接矩阵
B). 逆邻接表
C). 十字链表
D). 邻接表
答案：BCD
分析：本题考查图的相关知识，根据稀疏有向图的定义可知，适于表示稀疏有向图的是逆邻接表、十字链表、邻接表。
知识点：图的存储结构
难度：易
1.14. 下列哪一种图的邻接矩阵是对称矩阵
A). 有向图
B). 无向图
C). AOV 网
D). AOE 网
答案：C
分析：本题考查图的相关知识，根据AOV 网的定义可知，AOV 网的邻接矩阵是对称矩阵。 知识点：图的存储结构
难度：中
此题建议去掉，无向图的邻接矩阵也是对称矩阵，关于主对角线对称。
1.15. 从邻接阵矩??????????=010101
010
A 可以看出，该图共有（ ）个顶点
A). 9
B). 3
C). 6
D). 1
答案：B
分析：本题考查图的相关知识，根据邻接矩阵的定义可知，从邻接阵矩可以看出，该图共有3个顶点。
知识点：图的存储结构
难度：中
1.16. 从邻接阵矩??????????=010101
010
A 可以看出，如果是有向图该图共有（ ）条弧
A). 5
B). 4
C). 3
D). 2
答案：B
分析：本题考查图的相关知识，根据邻接矩阵的定义可知，从邻接阵矩可以看出，如果是有向图该图共有4条弧。
知识点：图的存储结构
难度：难
难度：中
此题是对图存储结构的考查，难度不大
1.17. 从邻接阵矩??????????=010101
010
A 可以看出，如果是无向图，则共有（ ）条边
A). 5
B). 4
C). 3
D). 2
答案：D
分析：本题考查图的相关知识，根据邻接矩阵的定义可知，从邻接阵矩可以看出，如果是无向图，则共有2条边。
知识点：图的存储结构
难度：中
1.18. 当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是
A). ∑=n i j i A 1],[
B). []∑=n 1
j j ,i A
C). ∑=n i i j A 1
],[ D). ∑=n i j i A 1],[+ []∑=n
1j i ,j A
答案：B
分析：本题考查图的相关知识，根据邻接矩阵的定义可知，当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是B 答案。
知识点：图的存储结构
难度：难
此题建议去掉，未指明是有向图还是无向图 1.19. 用相邻矩阵A 表示图，判定任意两个顶点Vi 和Vj 之间是否有长度为m 的路径相
连，则只要检查（ ）的第i 行第j 列的元素是否为零即可
A). B
B). A
C). C
D). D
答案：B
分析：本题考查图的相关知识，判定任意两个顶点Vi 和Vj 之间是否有长度为m 的路径相连，则只要检查第i 行第j 列的元素是否为零即可。
知识点：图的存储结构
难度：中
1.20. 下列说法不正确的是
A).图的遍历是从给定的源点出发每一个顶点仅被访问一次
B).图的深度遍历不适用于有向图
C).遍历的基本算法有两种：深度遍历和广度遍历
D).图的深度遍历是一个递归过程
答案：B
分析：本题考查图的相关知识，根据有向图遍历的定义可得，图的深度遍历适用于有向图，B选项错误。
知识点：图的遍历
难度：易
1.21. 无向图G=(V,E),其中：
V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是
A).a,b,e,c,d,f
B).a,c,f,e,b,d
C).a,e,b,c,f,d
D).a,e,d,f,c,b
答案：D
分析：本题考查图的相关知识，根据图进行深度优先遍历的定义可得，得到的顶点序列a,e,d,f,c,b。
知识点：图的遍历
难度：难
1.2
2. 下面哪一方法可以判断出一个有向图是否有环（回路）
A).深度优先遍历
B).拓扑排序
C).求最短路径
D).求关键路径
答案：AB
分析：本题考查图的相关知识，根据图进行深度优先遍历的定义可得，深度优先遍历、拓扑排序都可以判断出一个有向图是否有环。
知识点：图的遍历
难度：易
1.23. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为
A).O(n)
B).O(n+e)
C).O(n2)
D).O(n3)
答案：B
分析：本题考查图的相关知识，根据Prim 算法的定义可得，求最小生成树的Prim 算法的时间复杂度为O(n+e)。
知识点：生成树
难度：中
答案：C
分析：本题考查图的相关知识，根据Prim 算法的定义可得，求最小生成树的Prim 算法的时间复杂度为O(n2)。
知识点：生成树
难度：中
1.24. 以下说法正确的是
A).求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负
的原因是在实际应用中无意义
B).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ；（图用邻接矩
阵表示）
C).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路
D).ABC都是错的
答案：D
分析：本题考查图的相关知识，根据Prim 算法的定义可得，求最小生成树的Prim 算法的时间复杂度为O(n+e)，ABC选项都是错误的。
知识点：生成树
难度：难
此题建议去掉，分析与答案完全不相符
1.25. 当各边上的权值( )时，BFS算法可用来解决单源最短路径问题
A).均相等
B).均互不相等
C).不一定相等
D).无要求
答案：A
分析：本题考查图的相关知识，根据BFS算法的定义可得，当各边上的权值均相等时，BFS 算法可用来解决单源最短路径问题。
知识点：最短路径
难度：中
1.26. 求解最短路径的Floyd算法的时间复杂度为
A).O（n）
B).O（n+c）
C).O（n*n）
D).O（n*n*n）
答案：D
分析：本题考查图的相关知识，根据Floyd算法的定义可得，求解最短路径的Floyd算法的时间复杂度为O（n*n*n）。
知识点：最短路径
难度：易
1.27. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={ 7>, A).V1,V3,V4,V6,V2,V5,V7 B).V1,V3,V2,V6,V4,V5,V7 C).V1,V3,V4,V5,V2,V6,V7 D).V1,V2,V5,V3,V4,V6,V7 答案：A 分析：本题考查图的相关知识，根据拓扑排序的定义可得，G的拓扑序列是 V1,V3,V4,V6,V2,V5,V7。 知识点：拓扑排序 难度：难 1.28. 若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序 序列 A).存在 B).不存在 C).不能确定 D).可能存在 答案：A 分析：本题考查图的相关知识，根据拓扑排序的定义可得，若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列存在。 知识点：拓扑排序 难度：中 1.29. 一个有向无环图的拓扑排序序列 A).一定是唯一的 B).一定不是唯一的 C).不一定是唯一的 D).无法判断 答案：C 分析：本题考查图的相关知识，根据拓扑排序的定义可得，一个有向无环图的拓扑排序序列不一定是唯一的。 知识点：拓扑排序 难度：易 1.30. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的 是 A).G中有弧 B).G中有一条从Vi到Vj的路径 C).G中没有弧 D).G中有一条从Vj到Vi的路径 答案：D 分析：本题考查图的相关知识，根据拓扑排序的定义可得，依据题意G中有一条从Vj到Vi的路径是不可能出现的。 知识点：拓扑排序 难度：中 1.31. 在用邻接表表示图时，拓扑排序算法时间复杂度为 A).O(n) B).O(n＋e) D).O(n*n*n) 答案：B 分析：本题考查图的相关知识，根据拓扑排序的定义可得，用邻接表表示图时，拓扑排序算法时间复杂度为O(n＋e)。 知识点：拓扑排序 难度：易 1.3 2. 关键路径是事件结点网络中 A).从源点到汇点的最长路径 B).从源点到汇点的最短路径 C).最长回路 D).最短回路 答案：A 分析：本题考查图的相关知识，根据关键路径的定义可得，关键路径是事件结点网络中从源点到汇点的最长路径。 知识点：最短路径 难度：易 1.33. 下面关于求关键路径的说法不正确的是 A).求关键路径是以拓扑排序为基础的 B).一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C).一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时 间的差 D).关键活动一定位于关键路径上 答案：C 分析：本题考查图的相关知识，根据关键路径的定义可得，关键路径是事件结点网络中从源点到汇点的最长路径，C选项错误。 知识点：最短路径 难度：易 答案：C 分析：本题考查图的相关知识，一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的和 知识点：最短路径 难度：易 答案与分析不相符合 1.34. 下列关于AOE网的叙述中，不正确的是 A).关键活动不按期完成就会影响整个工程的完成时间 B).任何一个关键活动提前完成，那么整个工程将会提前完成 C).所有的关键活动提前完成，那么整个工程将会提前完成 D).某些关键活动提前完成，那么整个工程将会提前完成 答案：B 分析：本题考查图的相关知识，根据关键路径的定义可得，任何一个关键活动提前完成，那么整个工程不一定会提前完成，B选项错误。 知识点：最短路径 1.35. 以下说法正确的是 A)..树中的结点和图中的顶点就是指数据结构中的数据元素 B).在n个结点的无向图中，若边数大于n-1,则该图必是连通图 C).对有n个顶点的无向图，其边数e与各顶点度数间满足下列等式e=n/2 D).有e条边的无向图，在邻接表中有e个结点 答案：A 分析：本题考查图的相关知识，根据图的定义可得，A选项正确，B选项显然错误，n个顶点的无向图，其边数e与各顶点度数间不满足等式e=n/2，C选项错误。 知识点：图的定义与术语 难度：易 1.36. 下列叙述正确的是 A).有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数 B).强连通图的各顶点间均可达 C).强连通分量是无向图的极大强连通子图 D).连通分量指的是有向图中的极大连通子图 答案：B 分析：本题考查图的相关知识，根据强连通图的定义可得，强连通图的各顶点间均可达，CD选项显然错误，有向图中顶点V的出度等于其邻接矩阵中第V行中的1的个数。 知识点：图的定义与术语 难度：中 1.37. 下列叙述正确的是 A).邻接多重表是无向图和有向图的链式存储结构 B).十字链表是无向图的一种存储结构 C).无向图的邻接矩阵可用一维数组存储 D).用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关 答案：C 分析：本题考查图的相关知识，根据强连通图的定义可得，强连通图的各顶点间均可达，CD选项显然错误，有向图中顶点V的出度等于其邻接矩阵中第V行中的1的个数。 知识点：图的定义与术语 难度：中 1.38. 有向图G的强连通分量是指 A).极小连通子图 B).极大强连通子图 C).生成树 D).关键路径 答案：B 分析：本题考查图的相关知识，根据强连通图的定义可得有向图G的强连通分量是指极大强连通子图。 知识点：图的定义与术语 难度：易 1.39. 一个连通图的生成树是一个 A).极小连通子图 B).极大强连通子图 C).关键路径 D).强连通分量 答案：A 分析：本题考查图的相关知识，根据强连通图的定义可得，一个连通图的生成树是一个极小连通子图。 知识点：图的定义与术语 难度：易 1.40. 具有10个顶点的无向图，边的总数最多为 A).90 B).46 C).45 D).30 答案：C 分析：本题考查图的相关知识，根据无向图的定义可得，有10个顶点的无向图，边的总数最多为45，也可以根据公式计算可得。 知识点：图的定义与术语 难度：中 1.41. 若用n表示图中顶点数目，则有____条边的无向图成为完全图 A).n(n+1)/2 B).n(n-1)/2-1 C).n(n+1)/2-1 D).n(n-1)/2 答案：D 分析：本题考查图的相关知识，根据无向图的定义可得，有n个顶点的无向图，需要n(n-1)/2条边可以成为完全图。 知识点：图的定义与术语 难度：难 1.4 2. G是一个非连通无向图，共有28条边，则该图至少有______个顶点 A).7 B).8 C).9 D).11 答案：C 分析：本题考查图的相关知识，根据非连通无向图的定义可得，有28条边的非联通无向图，该图至少有9个顶点。 知识点：图的定义与术语 难度：中 1.43. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 ______条弧 A).n C).n+1 D).2n 答案：A 分析：本题考查图的相关知识，根据有向图的定义可得，要使有向图任意两点间可以互相到达，至少需要n条弧。 知识点：图的定义与术语 难度：中 1.44. 在有n个顶点的有向图中，每个顶点的度最大可达 A).2(n-1) B).2(n+1) C).2n-1 D).2n+1 答案：A 分析：本题考查图的相关知识，根据有向图的定义可得，每个顶点的度最大可达2(n-1)，有向图中的度有出度和入度之分。 知识点：图的定义与术语 难度：中 1.45. 设G为具有N个顶点的无向连通图，则G中至少有______条边 A).N B).N-1 C).N+1 D).2N 答案：B 分析：本题考查图的相关知识，根据无向连通图的定义可得，具有N个顶点的无向连通图至少有N-1条边。 知识点：图的定义与术语 难度：中 1.46. 如果含n个顶点的图形形成一个环，则它有______棵生成树 A).n-1 B).n C).n+1 D).n/2 答案：B 分析：本题考查图的相关知识，根据生成树的定义可得，若n个顶点的图形形成一个环，则它有n棵生成树。 知识点：生成树 难度：中 1.47. N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_____个非零元素 A).2（N+1） B).2N-1 C).2（N-1） D).2N+1 分析：本题考查图的相关知识，N个顶点的连通图用邻接矩阵表示时,该矩阵至少有2（N-1）个非零元素。 知识点：图的存储结构 难度：中 1.48. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等 于该顶点的______ A).度 B).出度 C).入度 D).深度 答案：A 分析：本题考查图的相关知识，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的度。 知识点：图的存储结构 难度：中 1.49. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于有向图来说等 于该顶点的______ A).度 B).出度 C).入度 D).深度 答案：B 分析：本题考查图的相关知识，每个顶点邻接表中所含的结点数，对于有向图来说等于该顶点的。 知识点：图的存储结构 难度：中 1.50. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是 A).第I+1行非零元素个数 B).第I行非零元素个数 C).第I列非零元素个数 D).第I+1列非零元素个数 答案：C 分析：本题考查图的相关知识，根据有向图的邻接矩阵定义可知，计算第I个顶点入度的方法是第I列非零元素个数。 知识点：图的存储结构 难度：中 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 数据结构试卷 一、单项选择题（本大题 共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1 . 下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C. 链队列 D.栈 2 . 将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3 . 已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear 指向 队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4 . 递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C. 队列 D. 线性表 5 . 设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）A.求子串 B.串联接 C.串匹配D.求串长 6 . 对于广义表A，若head(A)等于tail(A)，则表A为（） A.() B.(()) C.((),()) D.((),(), ()) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一 定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度 为l的结点个数是3，度为2 的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9. 某算法有3 个程序段，第一程序段的执行次数为错误！未找到引用源。，第二个程序段执 行次数为4n，第三个程序段的执行次数 为0.06错误！未找到引用源。，则该算法的时间复 杂度为（）。 A．O（n）B ．O（错误！未找到引用源。） C ．O（错误！未找到引用源。）D．O （错误！未找到引用源。） 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 数据结构复习题题集 错误！未指定书签。 1.选择题 1.1. 图中有关路径的定义是 A).由顶点和相邻顶点序偶构成的边所形成的序列 B).由不同顶点所形成的序列 C).由不同边所形成的序列 D).上述定义都不是 答案：A 分析：本题考查图的相关知识，根据图的有关路径定义可知，图中有关路径的定义是由顶点和相邻顶点序偶构成的边所形成的序列。 知识点：图的定义与术语 难度：易 1.2. 设无向图的顶点个数为n，则该图最多有（）条边 A).n-1 B).n(n-1)/2 C).n(n+1)/2 D).n2 答案：B 分析：本题考查图的相关知识，根据无向图的定义可知，无向图的顶点个数为n，则该图最多有n(n-1)/2条边。 知识点：图的定义与术语 难度：中 1.3. 一个n个顶点的连通无向图，其边的个数至少为（） A).n-1 B).n C).n+1 D).nlogn 答案：A 分析：本题考查图的相关知识，根据连通无向图的定义可知，一个n个顶点的连通无向图，其边的个数至少为n-1。 知识点：图的定义与术语 难度：中 1.4. 要连通具有n个顶点的有向图，至少需要（）条边 A).n-l B).n C).n+l D).2n 答案：B 分析：本题考查图的相关知识，根据连通有向图的定义可知，要连通具有n个顶点的有向图，至少需要n条边。 知识点：图的定义与术语 难度：易 1.5. n个结点的完全有向图含有边的数目为 A).n*n B).n（n＋１） C).n／2 D).n*（n－l） 答案：D 分析：本题考查图的相关知识，根据完全有向图的定义可知，n个结点的完全有向图含有边的数目为n*（n－l）。 知识点：图的定义与术语 难度：中 1.6. 一个有n个结点的图，最少有（）个连通分量 A).0 B). 1 C).n-1 D).n 答案：B 分析：本题考查图的相关知识，根据连通分量的定义可知，一个有n个结点的图，最少有1个连通分量。 知识点：图的定义与术语 难度：中 1.7. 一个有n个结点的图，最多有（）个连通分量 A).0 B). 1 C).n-1 D).n 答案：D 分析：本题考查图的相关知识，根据连通分量的定义可知，一个有n个结点的图，最多有n个连通分量。 知识点：图的定义与术语 难度：易 1.8. 在一个无向图中，所有顶点的度数之和等于所有边数（）倍 A).1/2 B). 1 C). 2 D). 4 答案：C 分析：本题考查图的相关知识，根据无向图的定义可知，在无向图中所有顶点的度数之和等于所有边数2倍。 知识点：图的定义与术语 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 数据结构期末复习题1（0907） 一、基本要求 1．数据结构基本概念 （1）数据、数据对象和数据结构（逻辑、物理结构、基本操作）（2）抽象数据类型 （3）算法的特征及评价的标准 2．线形结构 （1）顺序表的特点及存储结构 （2）链表的特点及存储结构 （3）栈的特点及基本操作 （4）队列的特点及基本操作 （5）顺序串和链串的存储结构 （6）二维数组的地址计算 （7）特殊矩阵的概念及存储结构（对称、三角、对角、稀疏）（8）广义表的概念及存储结构 （9）线性表的排序（简单插入、选择和交换） （10）线性表的查找（顺序、折半和分块索引） 3．树形结构 （1）二叉树的性质及存储结构（顺序、二叉链表、三叉链表）（2）二叉树的遍历 （3）线索二叉树 （4）树的存储结构（双亲、孩子-双亲、孩子-兄弟链表） （5）树、二叉树与森林的转化方法 （6）哈夫曼树 （7）二叉排序树及平衡化 （8）堆排序树 （9）树的等价类划分 4．图形结构 （1）图的定义及存储结构 （2）图的深度优先和广度优先遍历 （3）图的连通性 （4）最小（代价）生成树 （5）拓扑排序 （6）关键路径 （7）最短路径（单源、顶点对） 5．查找表 （1）散列表的概念 （2）散列表解决散列冲突的方法（开放地址法、链地址法）（3）散列表的插入和删除 （4）B_树的概念、存储结构及基本操作（查找、插入、删除）6．排序方法 （1）希尔排序 （2）快速排序 （3）二路归并排序 （4）基数排序（链式、计数） （5）排序方法比较和分析（时间性能、空间性能、稳定性） 二、单选题 1．要求具有同一逻辑结构的数据元素具有相同的特性，其含义为 A. 数据元素具有同一的特点 B.数据元素其对应的数据个数及数据项的类型要一致 C. 每个数据元素都一样 D. 仅需要数据元素包含的数据项的个数相同 2．在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q 和*p之间插入结点*s，则执行操作 A. s->next=p->next;p->next=s; B. s->next=p;p->next=s C. q->next=s;s->next=p; D. p->next=s;s->next=q; 3．设指针p指向双链表的某一结点，则双链表结构的对称性可以用下面的操作来反映 A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior; C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior; 4．表达式a*(b+c)--d的后缀表达式是 A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd 数据结构期末考试题及答案 、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还 要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性 和输出的关系 C. 分析算法的效率以求改进 档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性 性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。 一、单项选择题（每小题1.5分，共计30分） 1. 数据结构是指。 A. 一种数据类型 B. 数据的存储结构 C. 一组性质相同的数据元素的集合 D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为。 void fun(int n) { int i=1; while (i<=n) i++; } A. O(n) B. O(n) C. O(nlog2n) D. O(log2n) 3. 在一个长度为n的有序顺序表中删除元素值为x的元素时，在查找元素x时采用二分查找，此时的时间复杂度为。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n) 4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为。 A. O(n) B. O(n) C. O(nlog2n) D. O(n2) 5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是。 A.top++;s[top]=x; B.s[top]=x;top++; C.top--;s[top]=x; B.s[top]=x;top--; 6. 中缀表达式“2*(3+4)-1”的后缀表达式是，其中#表示一个数值的结束。 A. 2#3#4#1#*+- B. 2#3#4#+*1#- C. 2#3#4#*+1#- D. -+*2#3#4#1# 7. 设环形队列中数组的下标为0～N-1，其队头、队尾指针分别为front和rear（front 指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为。 A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 8. 若用一个大小为6的数组来实现环形队列，队头指针front指向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 一、单项选择题 1在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（） A. O ( n ) B .O ( 1 ) C. O ( n 2 ) D. O ( log2n ) 2、设单链表中结点的结构为（data , link ）。已知指针q所指结点是指针p所指结点的直接 前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（） A. s → link = p→ link; p→ link = s B. q → link = s ; s→ link = p C. p → link = s →link ; s→ link = p D. p → link = s; s→link = q 3、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear， 则当前队列中的元素个数是（）。 A. ( front - rear + 1) % m B. ( rear - front + 1) % m C. ( front - rear + m) % m D. ( rear - front + m) % m 4、设有一个10阶的对称矩阵Ａ[10][10]，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组Ｂ[ ]中，Ａ[0][0]存入Ｂ[0]中，则Ａ[8][5]在Ｂ[ ]中( ) 位置。 A. 32 B. 33 C.41 D. 65 5、具有65个结点的完全二叉树的高度为（）。（根的层次号为1） A. 8 B. 7 C. 6 D. 5 6、树中所有结点的度等于所有结点数加（） A. 0 B. 1 C. -1 D.2 7.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 8.讨论树、森林和二叉树的关系，目的是为了（）。 A 借助二叉树上的运算方法去实现对树的一些运算 B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树 D 体现一种技巧，没有什么实际意义 9.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。 A n B (n-1)2 C n-1 D n2 10.G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。 A 6 B 7 C 8 D 9 11、在一个单链表中，如果m所指结点是n所指结点的后继，若在n和m之间插入k所指结点，应执行操作（）。 A、k —>next=m—>next; m—>next=k; B、m —>next=k—>next; k—>next=m; C、n —>n ext=k; k—>next=m; D、m —>next=k; k—>next=n; 12、一个栈的入栈序列是A,B,C,D,E,则栈的出栈序列不可能是（）。 A、EDCBA B、DECBA C、ABCDE D、DCEAB 13、一个高度为h的满二叉树共有x个结点，其中m个叶子结点，则有（）成立。 A、x=2m-1 B、h+m=2x C、m=h-1 D、 x=h+m 14、二叉排序树中，最大值结点的（）。 A、左指针一定为空 B、右指针一定为空 C、左右指针均为空 D、左右指针均不为空 15、含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。 A、1 B、n/2 C 、n-1 D、n 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 第 1 页，共 11 页 任课教师签名： 命题教师签名： 系主任签名： 主管院长签名： 湛江师范学院2007年－2008学年度第1学期 期末考试试题A 卷 (考试时间:120分钟) 考试科目： 数据结构 请将所有答案填写在答题卡上，交卷时请将所有试卷上交 一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; i 6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的 最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i 课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。数据结构模拟题(开卷)
数据结构试卷1(含答案)
数据结构模拟试题及答案
数据结构复习题集(1)
2017年数据结构期末考试题及答案A
《数据结构C》模拟试题
数据结构复习题1(课件0907)
数据结构期末考试题及答案
《数据结构》模拟试卷一及答案
数据结构考试题1
《数据结构》期末考试题及答案
数据结构(c语言版)期末考试复习试题
数据结构模拟试卷(含答案)
数据结构复习题1
2017数据结构期末考试试题及答案
数据结构期末考试试题A卷(完成,不知对不对)
数据结构期末模拟试题05(有答案)
相关主题
文本预览