数据结构—判断题

1.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。

答案：错误

2.(neuDS)在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。

答案：正确

3.若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出 栈序列。

答案：正确

4.栈和队列的存储方式，既可以是顺序方式，也可以是链式方式。

答案：正确

5.环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。

答案：正确

6.可以通过少用一个存储空间的方法解决循环队列中队空和队满条件的区分。

答案：正确

7.二叉树中至少存在一个度为2的结点。

答案：错误

解析：0/1

8.哈夫曼树中一定没有度为 1 的结点。

答案：正确

9.哈夫曼树一定是完全二叉树。

答案：错误

10.对于任何一个图，从它的某个顶点进行一次深度或广度优先搜索可以访问到该图的 每个顶点。

答案：错误

解析：如果是无向的连通图或者有向的强连通图,是对的,对于无向的非连通图就不可能一次遍历访问到所有顶点了,对于有向的非强连通图则有可能对,有可能不对

11.连通图上各边权值均不相同，则该图的最小生成树是唯一的。

答案：正确

12.从n个顶点的连通图中选取n-1条权值最小的边即可构成最小生成树。

答案：错误

解析：选出的边不构成回路

13.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置 有关。

答案：正确

14.链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访 问各元素。

答案：正确

15.通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。

答案：错误

16.在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。

答案：正确

17.若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志，则在设置一个空 队时只需将队首指针和队尾指针赋同一个值，不管什么值都可以。

答案：正确

18.可以通过少用一个存储空间的方法解决循环队列假溢出现象。

答案：错误

19.一棵有124个结点的完全二叉树，其叶结点个数是确定的。

答案：正确

20.哈夫曼树的结点个数不能是偶数。

答案：正确

21.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

答案：正确

22.图的深度优先遍历非递归算法通常采用队列实现，广度优先遍历非递归算法通常采 用堆栈实现。

答案：错误

解析：深度优先是堆栈,广度优先是队列。

23.Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生 成树。

答案：正确

24.连通图的生成树包含了图中的所有顶点。

答案：正确

25.对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间 复杂度分别对应为O(1)和O(N)。

答案：错误

26.顺序存储结构的主要缺点是不利于插入或删除操作。

答案：正确

27.顺序存储方式只能用于存储线性结构。

答案：错误

28.顺序表中逻辑上相邻的元素，其物理位置也一定相邻。

答案：正确

29.对单链表来说，只有从头结点开始才能访问到表中所有结点。

答案：正确

30.

答案：错误

31.线性表的顺序存储表示优于链式存储表示。

答案：错误

32.在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为 O(1)和O(N)

答案：错误

33.线性表采用链式存储表示时，所有结点之间的存储单元地址可以连续也可以不连续。

答案：正确

34.在具有头结点的链式存储结构中，头指针指向链表中的第一个元素结点。

答案：错误

35.(neuDS)在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中 则只能进行顺序存取。

答案：正确

36.若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1

答案：错误

37.栈底元素是不能删除的元素。

答案：错误

38.栈顶元素和栈底元素有可能是冋一个元素。

答案：正确

39.栈是一种对进栈、出栈操作总次数做了限制的线性表。

答案：错误

40.对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。

答案：正确

41.在用数组表示的循环队列中，front值一定小于等于rear值。

答案：错误

42.队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。

答案：错误

43.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。

答案：正确

44.循环队列也存在着空间溢出问题。

答案：正确

45.循环队列执行出队操作时会引起大量元素的移动。

答案：错误

46.n个元素进队的顺序和出队的顺序总是一致的。

答案：正确

47.在对不带头结点的链队列作出队操作时，不会改变头指针的值。

答案：错误

48.循环队列也存在空间溢出的问题。

答案：正确

49.队列适合解决处理顺序与输入顺序相同的问题。

答案：正确

50.将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点 是兄弟。

答案：错误

51.一棵有9层结点的完全二叉树（层次从1开始计数），至少有255个结点。

答案：错误

52.一棵有9层结点的完全二叉树（层次从1开始计数），至少有512个结点。

答案：错误

53.对NNN（≥2\ge 2≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的 权值一定不小于下一层任一结点的权值。

答案：正确

54.需要借助于一个队列来实现DFS算法。  

答案：错误

55.如果无向图G必须进行3次深度优先搜索才能访问其所有顶点，则G一定有3个连通分 量。

答案：正确

56.图的深度优先遍历非递归算法通常采用栈实现，广度优先遍历非递归算法通常采用 队列实现。

答案：正确

57.图的深度优先遍历相当于二叉树的先序遍历。

答案：正确

58.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通 分量。

答案：正确

59.采用邻接表存储的图，其广度优先遍历类似于二叉树的先序遍历。

答案：错误

60.若有向图不存在回路，即使不用访问标志位同一结点也不会被访问两次。

答案：错误

61.图的广度优先遍历相当于二叉树的层次遍历。

答案：正确

62.图的广度优先遍历相当于二叉树的后序遍历。

答案：错误

63.Prim 算法是维护一个森林，每一步把两棵树合并成一棵。

答案：错误

64.带权无向图的最小生成树必是唯一的。

答案：错误

65.最小生成树是指边数最少的生成树。

答案：错误

66.若图G为连通图，则G必有唯一的一棵最小生成树。

答案：错误

67.对于带权无向图 G = (V, E)，M 是 G 的最小生成树，则 M 中任意两点 V1 到 V2 的路径一定是它们之间的最短路径。

答案：错误

68.图的最小生成树一定是唯一的

答案：错误

69.如果 e 是有权无向图 G 唯一的一条最短边，那么边 e 一定会在该图的最 小生成树上。

答案：正确

70.带权的无向连通图的最小生成树的权值之和是唯一的。

答案：正确