数据结构选择题分析.pdf

《数据结构选择题分析.pdf》由会员分享，可在线阅读，更多相关《数据结构选择题分析.pdf（6页珍藏版）》请在三一文库上搜索。

1、1. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第 5个元素的地址是（ 1 ） 。 选择一项： 1. 108 2. 110 3. 100 4. 120 2.在 n 个结点的顺序表中，算法的时间复杂度是O(1)的操作是（b） 选择一项： a. 删除第 i 个结点（ 1i n） b. 访问第 i 个结点（ 1i n）和求第i 个结点的直接前驱（ 2i n）c. 将 n 个结点从小到大排序 d. 在第 i 个结点后插入一个新结点（1i n） 3. 以下说法错误的是（ d ） 。 选择一项： a. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 b. 顺序存储的线性表可以随

2、机存取 c. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 d. 线性表的链式存储结构优于顺序存储结构 4. 单链表的存储密度（ b ） 。 选择一项： a. 不能确定 b. 小于 1 c. 大于 1 d. 等于 1 5. 向一个有 127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ c ） 。 选择一项： a. 63 b. 7 c. 63.5 d. 8 6. 在一个长度为n 的顺序表中，在第i 个元素（ 1i n+1）之前 插入一个新元素时须向后移动（ b ）个元素。 选择一项： a. n-i b. n-i+1 c. i

3、 d. n-i-1 7. 在单链表中，要将s 所指结点插入到p 所指结点之后，其语句应为（a ） 。 选择一项： a. s-next=p-next; p-next=s; b. (*p).next=s; (*s).next=(*p).next; c. s-next=p-next; p-next=s-next; d. s-next=p+1; p-next=s; 8. 在双向循环链表中，在p 指针所指的结点后插入q 所指向的新结点，其修改指针的操作是（b ） 。 选择一项： a. p-next=q; q-prior=p; p-next-prior=q; q-next=q; b. q-prior=p;

4、 q-next=p-next; p-next-prior=q; p-next=q; c. p-next=q; p-next-prior=q; q-prior=p; q-next=p-next; d. q-prior=p; q-next=p-next; p-next=q; p-next-prior=q; 9. 在双向链表存储结构中，删除p 所指的结点时须修改指针（c ） 。 选择一项： a. p-prior=p-next-next; p-next=p-prior-prior; b. p-next=p-next-next; p-next-prior=p; c. p-next-prior=p-pri

5、or; p-prior-next=p-next; d. p-prior-next=p; p-prior=p-prior-prior; 10. 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（c ） 。 选择一项： a. 2n b. n-1 c. n d. 2n-1 11. 线性表 L=(a1 ，a2,an)，下列说法正确的是（ b ） 。 选择一项： a. 表中诸元素的排列必须是由小到大或由大到小 b. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 c. 每个元素都有一个直接前驱和一个直接后继 d. 线性表中至少有一个元素 12. 线性表若采

6、用链式存储结构时，要求内存中可用存储单元的地址（d ） 。 选择一项： a. 部分地址必须是连续的 b. 一定是不连续的 c. 必须是连续的 d. 连续或不连续都可以 13. 线性表在（ d ）情况下适用于使用链式结构实现。 选择一项： a. 中结点结构复杂 b. 中含有大量的结点 c. 需经常修改中的结点值 d. 需不断对进行删除插入 14.若指定有 n 个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ b） 。 选择一项： a. O(nlogn) b. O(n的平方 ) c. O （n） d. O(1) 15. 链接存储的存储结构所占存储空间（b ） 。 选择一项： a. 只有一部

7、分，存储表示结点间关系的指针 b. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 c. 分两部分，一部分存放结点值，另一部分存放结点所占单元数 d. 只有一部分，存放结点值 16. 一个具有 1025个结点的二叉树的高h 为（ a ） 。 选择一项： a. 11 至1025之间 b. 10 至1024之间 c. 10 d. 11 17. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ d ） 。 选择一项： a. 254 b. 500 c. 250 d. 501 18.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（a） 。 选择一项： a.

8、 只有一个叶子结点 b. 是任意一棵二叉树 c. 所有的结点均无左孩子 d. 所有的结点均无右孩子 19. 利用二叉链表存储树，则根结点的右指针是（c ） 。 选择一项： a. 指向最右孩子 b. 指向最左孩子 c. 空 d. 非空 20. 在下列存储形式中， （a ）不是树的存储形式？ 选择一项： a. 顺序存储表示法 b. 孩子兄弟表示法 c. 孩子链表表示法 d. 双亲表示法 21. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编 号小于其右孩子的编号，可采用（ d ）遍历实现编号。 选择一项： a. 从根开始按层次遍历

9、b. 先序 c. 中序 d. 后序 22. 引入二叉线索树的目的是（d ） 。 选择一项： a. 为了能方便的找到双亲 b. 使二叉树的遍历结果唯一 c. 为了能在二叉树中方便的进行插入与删除 d. 加快查找结点的前驱或后继的速度 23. 把一棵树转换为二叉树后，这棵二叉树的形态是（ c ） 。 选择一项： a. 有多种 b. 有多种，但根结点都没有右孩子 c. 唯一的 d. 有多种，但根结点都没有左孩子 24. 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ d ）的二叉树。 选择一项： a. 任一结点无右子树 b. 空或只有一个结点 c. 任一结点无左子树 d. 高度等于其结点数

10、 25. 由3 个结点可以构造出多少种不同的二叉树？（ b ） 选择一项： a. 2 b. 5 c. 4 d. 3 26. 线索二叉树是一种（a ）结构。 选择一项： a. 物理 b. 逻辑和存储 c. 逻辑 d. 线性 27. 若 X 是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（ c ） 。 选择一项： a. X 的右子树中最左的结点 b. X 的左子树中最右叶结点 c. X的左子树中最右结点 d. X 的双亲 28. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ b ）遍历方法最合适。 选择一项： a. 中序 b. 后序 c. 前序 d.

11、按层次 29. 设 F 是一个森林， B是由 F 变换得的二叉树。若F中有 n 个非终端结点，则B中右指针域为空的结点有（b ）个。 选择一项： a. n+2 b. n+1 c. n-1 d. n 30. G是一个非连通无向图，共有28条边，则该图至少有（ d ）个顶点。 选择一项： a. 10 b. 8 c. 7 d. 9 31. n 个顶点的 连通图 用邻接距阵表示时，该距阵至少有（c ）个非零元素。 选择一项： a. n b. n/2 c. 2(n-1) d. 2n 32. 下面（ a ）方法可以判断出一个有向图是否有环。 选择一项： a. 拓扑排序 b. 求关键路径 c. 求最短路径

12、d. 深度优先遍历 33.下面（d）算法适合构造一个稠密图G 的最小生成树。 选择一项： a. Dijkstra算法 b. Floyd算法 c. Kruskal算法稀疏 d. Prim算法 34. 具有 n 个顶点的有向图最多有（ b ）条边。 选择一项： a. 2n b. n(n-1) c. n(n+1) d. n 35. 图的 BFS生成树的树高比DFS生成树的树高（ a ） 。 选择一项： a. 小或相等 b. 大或相等 c. 相等 d. 小 36. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（a ）倍。 选择一项： a. 1 b. 1/2 c. 2 d. 4 37. 广

13、度优先遍历类似于二叉树的（c ） 。 选择一项： a. 中序遍历 b. 后序遍历 c. 层次遍历 d. 先序遍历 38. 深度优先遍历类似于二叉树的（ a ） 。 选择一项： a. 先序遍历 b. 后序遍历 c. 层次遍历 d. 中序遍历 40. 用邻接表表示图进行广度优先 遍历时，通常借助（ a ）来实现算法。 选择一项： a. 队列 b. 栈 c. 树 d. 图 41. 用邻接表表示图进行深度优先 遍历时，通常借助（ d ）来实现算法。 选择一项： a. 图 b. 树 c. 队列 d. 栈 42. 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（a ）

14、图。 选择一项： a. 连通 b. 有向 c. 非连通 d. 强连通 43. 在一个图中，所有顶点的度数之和等于图的边数的（b ）倍。 选择一项： a. 4 b. 2 c. 1/2 d. 1 44. m阶 B-树是一棵（ b ） 。 选择一项： a. m 叉排序树 b. m 叉平衡排序树 c. m+1 叉平衡排序树 d. m-1 叉平衡排序树 45. 下列关于 m阶 B-树的说法错误的是（d ） 。 选择一项： a. 所有叶子都在同一层次上 b. 根结点至多有m棵子树 c. 非叶结点至少有m/2 (m 为偶数 ) 或 m/2+1（m为奇数）棵子树 d. 根结点中的数据是有序的 46. 下面关于

15、 B-和 B+树的叙述中，不正确的是（a ） 。 选择一项： a. B- 树和 B+树都能有效地支持顺序检索 b. B- 树和 B+树都可用于文件的索引结构 c. B- 树和 B+树都是平衡的多叉树 d. B- 树和 B+树都能有效地支持随机检索 47. 下面关于哈希查找的说法，不正确的是（c ） 。 选择一项： a. 用链地址法处理冲突，适合表长不确定的情况 b. 用链地址法处理冲突，不会引起二次聚集现象 c. 采用链地址法处理冲突时，查找一个元素的时间是相同的 d. 采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 48. 下面关于哈希查找的说法，正确的是（ d

16、 ） 。 选择一项： a. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 b. 哈希表的平均查找长度有时也和记录总数有关 c. 除留余数法是所有哈希函数中最好的 d. 不存在特别好与坏的哈希函数，要视情况而定 49. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（d ） 。小左大右 选择一项： a. (100，80， 60 ， 90 ， 120 ，130，110) b. （100，120，110，130，80， 60 ， 90 ） c. （100，80， 90 ， 60 ， 120 ，110，130） d. （100，60， 80 ， 90 ， 120 ，110，1

17、30） 50. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知 A 的左孩子的平衡因子为0右孩子的平衡因子 为1，则应作（ d ）型调整以使其平衡。 选择一项： a. LL b. LR c. RR d. RL 51. 对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ a ）次关键字。 选择一项： a. 4 b. 6 c. 5 d. 3 52. 当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ c ） 。 选择一项： a. 不一定 b. 取决于表递增还是递减 c. 在大部分情况下要快 d. 必定快 53. 折半搜

18、索与二叉排序树的时间性能（ c ） 。 选择一项： a. 完全不同 b. 相同 c. 有时不相同 d. 数量级都是 O(log2n) 54. 折半查找有序表（4，6，10，12，20，30，50，70，88，100） 。若查找表中元素58，则它将依次与表中（ c ）比较大小，查找结 果是失败。 选择一项： a. 20 ，50 b. 30 ，88，70，50 c. 20 ，70，30，50 d. 30 ，88，50 55. 设哈希表长为 14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到 表中， 用二次探测法解决冲突，则放

19、入的位置是（ b ） 。 选择一项： a. 5 b. 9 c. 8 d. 3 56. 适用于折半查找的表的存储方式及元素排列要求为（ b ） 。 选择一项： a. 顺序方式存储，元素无序 b. 顺序方式存储，元素有序 c. 链接方式存储，元素无序 d. 链接方式存储，元素有序 57. 采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 (d )。 选择一项： a. 一定都不是同义词 b. 都相同 c. 一定都是同义词 d.不一定都是同义词 58. 对 n 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（c ） 。 选择一项： a. (

20、n-1)/2 b. n c. (n+1)/2 d. n/2 59. 下列关键字序列中， （c ）是堆。 选择一项： a. 94 ，23，31，72，16，53 b. 16 ，53，23，94，31，72 c. 16 ，23，53，31，94，72 d. 16 ，72，31，23，94，53 60. 下列排序算法中， （ b ）不能保证每趟排序至少能将一个元素放到其最终的位置上。 选择一项： a. 冒泡排序 b. 希尔排序 c. 堆排序 d. 快速排序 61. 下述几种排序方法中，要求内存最大的是（ c ） 。 选择一项： a. 希尔排序 b. 堆排序 c. 归并排序 d. 快速排序 62. 下

21、述几种排序方法中， （ c ）是稳定的排序方法。 选择一项： a. 快速排序 b. 希尔排序 c. 归并排序 d. 堆排序 63. 从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（c ） 。 选择一项： a. 冒泡排序 b. 插入排序 c. 选择排序 d. 归并排序 64. 堆是一种（ a ）排序。 选择一项： a. 选择 b. 归并 c. 交换 d. 插入 65. 堆的形状是一棵（ b ） 。 选择一项： a. 满二叉树 b. 完全二叉树 c. 二叉排序树 d. 平衡二叉树 66. 对 n 个不同的关键字由小到大进行冒泡排序，在下列（b ）情况下比较的次数最

22、多。 选择一项： a. 元素基本有序 b. 从大到小排列好的 c. 从小到大排列好的 d. 元素无序 67. 对 n 个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（b ） 。 选择一项： a. n-1 b. n(n-1)/2 c. n+1 d. n 68. 对 n 个关键字作快速排序，在最坏情况下，算法的时间复杂度是（c ） 。 选择一项： a. O(nlog2n) b. O(n3) c. O(n2) d. O(n) 69. 快速排序在下列（b ）情况下最易发挥其长处。 选择一项： a. 被排序的数据中含有多个相同排序码 b. 被排序的数据完全无序 c. 被排序的数据已基本有

23、序 d. 被排序的数据中的最大值和最小值相差悬殊 70. 数据表中有 10000个元素，如果仅要求求出其中最大的10个元素，则采用( c) 算法最节省时间。 选择一项： a. 堆排序 b. 冒泡排序 c. 简单选择排序 d. 快速排序 71. 若一组记录的排序码为（46, 79，56，38，40，84） ，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（b ） 。 选择一项： a. 40 ，38，46，79，56，84 b. 40 ，38，46，56，79，84 c. 38 ，40，46，56，79，84 d. 40 ，38，46，84，56，79 72. 若一组记录的排序码为（46，79，56，38，40，84） ，则利用堆排序的方法建立的初始堆为（ a ） 。 选择一项： a. 84 ，79，56，38，40，46 b. 84 ，79，56，46，40，38 c. 79 ，46，56，38，40，84 d. 84 ，56，79，40，46，38 73. 从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为 （ b ） 。 选择一项： a. 冒泡排序 b. 插入排序 c. 归并排序 d. 选择排序