Question

数据结构概论 试题求解

二、判断对错题：（每题2分，共40分，正确的选A，错误的选B）
1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。
2. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
3. 取线性表的第i个元素的时间同i的大小有关。
4. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。
5. 二叉树是一般树的特殊情形。
6. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
7. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。
8. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。
9. Hash表的平均查找长度与处理冲突的方法无关。
10. 用邻接矩阵表示图时，矩阵元素的个数与边的条数有关.
11. 树最适合用来表示元素之间具有分支层次关系的数据。
12. 图型结构中元素之间存在1对多关系。
13. 哈夫曼树度为1的结点数等于度为2和0的结点数之差。
14. 两个串相等的充分必要条件是分配的存储空间一样。
15. 已知指针P指向键表L的某结点，执行语句P=P->next不会删除该链表中的结点。
16. 在链队列中，即使不设置尾指针也能进行入队操作。
17. 若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。
18. 直接选择排序算法在最好情况下的时间复杂度为O（N），N是数据元素的个数。
19. 排序算法中的比较次数与初始元素序列的排列无关。
20. 记录是数据处理的最小单位。
21. 程序一定是算法。
22. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。
23. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.
24. 循环链表不是线性表.
25. 顺序存储结构通过数据元素存储的位置表示元素之间的关系。
26. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
27. 循环队列的引入，目的是为了克服假溢出。
28. 完全二叉树一定存在度为1的结点。
29. 对一棵二叉树进行层次遍历时，应借助于一个栈。
30. 二叉树只能用二叉链表表示。
31. 树中的结点和图中的顶点就是指数据结构中的数据元素。
32. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。
33. 带权的有向图和无向图，只能使用邻接表存储形式来存储它。
34. 适用于折半查找的表的存储方式及元素排列要求是：链接方式存储，元素无序 。
35. 当采用分快查找时，数据的组织方式为数据分成若干块，每块内数据有序。
36. 散列函数越复杂越好，因为这样随机性好，冲突概率小。
37. 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。
38. 在排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。
39. 链表中的头结点仅起到标识的作用。
40. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动量为标准分析。
41. 为了很方便的插入和删除数据，可以使用双向链表存放数据。
42. 栈是实现过程和函数等子程序所必需的结构。
43. 在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为模式串的最末字符。
44. 在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是p->next=p->next->next;
45. 完全二叉树一定存在度为1的结点。
46. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。
47. 通常将链串的结点大小设置为大于1是为了提高存储密度。
48. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
49. 快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
50. 邻接多重表是无向图和有向图的链式存储结构。
51. 强连通图的各顶点间均可达。
52. 度为二的树就是二叉树。

Answer 1

二、判断对错题：（每题2分，共40分，正确的选A，错误的选B）
1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。B
2. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。B
3. 取线性表的第i个元素的时间同i的大小有关。B
4. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。A
5. 二叉树是一般树的特殊情形。B
6. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。B
7. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。B
8. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。B(折半最小）
9. Hash表的平均查找长度与处理冲突的方法无关。B
10. 用邻接矩阵表示图时，矩阵元素的个数与边的条数有关.A
11. 树最适合用来表示元素之间具有分支层次关系的数据。A
12. 图型结构中元素之间存在1对多关系。A
13. 哈夫曼树度为1的结点数等于度为2和0的结点数之差。
14. 两个串相等的充分必要条件是分配的存储空间一样。B
15. 已知指针P指向键表L的某结点，执行语句P=P->next不会删除该链表中的结点。A
16. 在链队列中，即使不设置尾指针也能进行入队操作。A
17. 若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。A
18. 直接选择排序算法在最好情况下的时间复杂度为O（N），N是数据元素的个数。B
19. 排序算法中的比较次数与初始元素序列的排列无关。B
20. 记录是数据处理的最小单位。B
21. 程序一定是算法。B
22. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。A
23. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.B
24. 循环链表不是线性表.B
25. 顺序存储结构通过数据元素存储的位置表示元素之间的关系。A
26. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。B
27. 循环队列的引入，目的是为了克服假溢出。A
28. 完全二叉树一定存在度为1的结点B。
29. 对一棵二叉树进行层次遍历时，应借助于一个栈。B
30. 二叉树只能用二叉链表表示。B
31. 树中的结点和图中的顶点就是指数据结构中的数据元素。A
32. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。B
33. 带权的有向图和无向图，只能使用邻接表存储形式来存储它。B
34. 适用于折半查找的表的存储方式及元素排列要求是：链接方式存储，元素无序 。B
35. 当采用分快查找时，数据的组织方式为数据分成若干块，每块内数据有序。B
36. 散列函数越复杂越好，因为这样随机性好，冲突概率小。B
37. 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法。A
38. 在排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。A
39. 链表中的头结点仅起到标识的作用。B
40. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动量为标准分析。A
41. 为了很方便的插入和删除数据，可以使用双向链表存放数据。A
42. 栈是实现过程和函数等子程序所必需的结构。A
43. 在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为模式串的最末字符。A
44. 在单链表中，指针p指向元素为x的结点，实现"删除x的后继"的语句是p->next=p->next->next;B
45. 完全二叉树一定存在度为1的结点。B
46. 连通图上各边权值均不相同，则该图的最小生成树是唯一的。A
47. 通常将链串的结点大小设置为大于1是为了提高存储密度。
48. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。B
49. 快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。B
50. 邻接多重表是无向图和有向图的链式存储结构。B
51. 强连通图的各顶点间均可达。A
52. 度为二的树就是二叉树。B
大概都对吧，个别没确定答案，自己判断了下