2014年9月份考试数据结构第一次作业.doc

1、2014年 9月份考试数据结构第一次作业 一、单项选择题（本大题共 90分，共 30 小题，每小题 3 分） 1. 单链表的存储密度（ ） A. 大于 1 B. 等于 1 C. 小于 1 D. 不能确定 2. 线性表在（ ）情况下适用于使用链式结构实现。 A. 需经常修改中的结点值 B. 需不断对进行删除插入 C. 中含有大量的结点 中结点结构复杂 3. 下述哪一条是顺序存储方式的优点？（ ） A. 存储密度大 B. 插入运算方便 C. 删除运算方便 D. 可方便地用于各种逻辑结构的存储表示 4. 串是一种 特殊的线性表，其特殊性体现在： （ ） A. 可以顺序存储 B. 数据元素是一个字符

2、C. 可以链式存储 D. 数据元素可以是多个字符 5. 线性表的顺序存储结构是一种 ( )的存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 6. 单链表的存储密度（ ） A. 大于 1 B. 等于 1 C. 小于 1 D. 不能确定 7. 树型结构是数据元素之间存在一种： ( ) A. 一对多关系 B. 多对多关系 C. 多对一关系 D. 一对一关系 8. 栈中元素的进出原则是（ ） A. 先进先出 B. 后进先出 C. 栈空则进 D. 栈满则出 9. 下述哪一条是顺序存储方式的优点？（ ） A. 存储密度大 B. 插入运算方便 C. 删除运算方便 D. 可方便地用

3、于各种逻辑结构的存储表示 10. 以下哪一个不是队列的基本运算？ （ ） A. 从队尾插入一个新元素 B. 判断一个队列是否为空 C. 从队列中删除第 i个元素 D. 读取队头元素的值 11. 用链接方式存储的队列，在进行删除运算时 .（ ） A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 12. ( )是数据的基本单位，即数据集合中的个体。 A. 数据 B. 数据元素 C. 数据项 D. 数据对象 13. 计算机算法指的是：（ ） A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 14. 以下数据结构中哪一个是线性结

4、构？（ ） A. 有向图 B. 栈 C. 线索二叉树 D. B 树 15. 对线性表，在下列哪种情况下应当采用链表表示？ （ ） A. 经常需要随机地存取元素 经常需要进行插入和删除操作 B. 表中元素需要占据一片连续的存储空间 C. 表中元素的个数不变 16. 输 出一个二维数组 bmn中所有元素值的时间复杂度为（ ）。 A. O(n) B. O(m+n) C. O(n2) D. O(m*n) 17. 以下的排序算法属于稳定排序算法的是（ ） A. 基数排序 B. 快速排序 C. 希尔排序 D. 堆排序 18. 算法分析的目的是：（ ） A. 找出数据结构的合理性 B. 研究算法中的输入和输

5、出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 19. 线性表在（ ）情况下适用于使用链式结构实现。 A. 需经常修改中的结点值 B. 需不断对 进行删除插入 C. 中含有大量的结点 中结点结构复杂 20. 一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 21. 下面程序段的时间复杂度为（ ） for ( int i = 0; i m; i+ ) for ( int j = 0; j n; j+ ) aij = i*j; A. O(m2) B. O(n2) C. O(m*n) D. O(m+n) 22. 对线性表，在下列哪种情

6、况下应当采用链表表示？ （ ） A. 经常需要随 机地存取元素 经常需要进行插入和删除操作 B. 表中元素需要占据一片连续的存储空间 C. 表中元素的个数不变 23. 数据库文件中存取数据的基本单位是（ ） A. 记录 B. 数据项 C. 数据结构 D. 以上都不是 24. 已知有向图，其中 v1,v2,v3,v4, ,， ，的拓扑序列是（ ）。 A. v1,v2,v4,v3 B. v3,v4,v1,v2 C. v1,v3,v4,v2 D. v1,v4,v3,v2 25. 不定长文件是指（ ） A. 文件的长度不固定 B. 记录的长度 不固定 C. 字段的长度不固定 D. 关键字项的长度不固定

7、 26. 算法分析的两个主要方面是：（ ） A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 27. 数据结构中，与所使用的计算机无关的是数据的（ ）结构； A. 存储 B. 物理 C. 逻辑 D. 物理和存储 28. 在快速排序中，每次划分选择的基准元素为该区间的 ( )时，得到的两个子区间是均匀的。 A. 最大值 B. 最小值 C. 任意值 D. 中间值 29. 在串的模式匹配中，一般 ( ) A. 有效位移的个数大于合法位移的个数 B. 有效位移的个数等于合法位移的个数 C. 有效位移的个数小于合法位移的个数 D. 有效位移和合法位移

8、无关 30. 在稀疏矩阵的三元组表表示法中，每个三元组表示 ( ) A. 矩阵中数据元素的行号、列号和值 B. 矩阵中非零元素的值 C. 矩阵中非零元素的行号和列号 D. 矩阵中非零元素的行号、列号和值 二、判断题（本大题共 10 分，共 5 小题，每小题 2 分） 1. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 2. 顺序存储方式只能用于 存储线性结构 3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 4. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 5. 链表的每个结点中都恰好包含一个指针。 答案： 一、单项选择题（ 90分，共 30 题，每小题 3 分） 1. C 2. B 3. A 4. B 5. B 6. C 7. A 8. B 9. A 10. B 11. D 12. B 13. C 14. B 15. B 16. D 17. A 18. C 19. B 20. C 21. C 22. B 23. A 24. A 25. B 26. A 27. C 28. D 29. C 30. D 二、判断题（ 10 分，共 5 题，每小题 2 分） 1. 2. 3. 4. 5.