《2017年数据结构第一次作业》由会员分享，可在线阅读，更多相关《2017年数据结构第一次作业（11页珍藏版）》请在金锄头文库上搜索。
1、第第 1 1 次作业次作业 一、单项选择题（本大题共一、单项选择题（本大题共 6060 分，共分，共 2020 小题，每小题小题，每小题 3 3 分）分） 1. 在长度为 n 的顺序表求最小值的时间复杂度为（）。 A. O（1）B. O（n）C. O（n2）D. O（logn）2. 顺序表中数据元素的存取方式是（）。 A. 顺序存取B. 链式存取C. 随机存取D. 散列存取3. 对于一个具有 n 个结点的单链表，,在给定值为 x 的结点后插入一个新结点的平均时间复杂度为（ ）。 A. O(0) B. O(1) C. O(n) D. O(n2)4. 在稀疏矩阵的带行指针向量的链接存储中，每个行单
2、链表中的结点都具有相 同的（ ）。 A. 行号 B. 列号 C. 元素值 D. 地址5. 数组 A0.50.5的每个元素占 5 个字节，将其以列为主序存储在起 始地址为 1000 的内存单元中，则元素 A55的地址是（ ）。 A. 1175B. 1180C. 1205D. 12106. 下面程序段的时间复杂度是（ ）。 i 0； while（inext=LC. L-next-next=LD. L-next=NULL10. 下面关于算法说法错误的是（ ）。 A. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上
3、几个都是错误的11. 用单链表表示的链队列中，队头在链表的（ ）位置。 A. 链头B. 链尾C. 链中D. 以上都不对12. 世界上第一台电子计算机问世的时间是（）。 A. 1946B. 1920C. 1948D. 195013. 如果对含有 n（n1）个元素的线性表运算只有 4 种：删除第一个元素；删 除最后一个元素；在第一个元素前插入新元素；在最后一个元素后面插入新元 素，则最好使用（）。 A. 只有尾结点指针没有头结点指针的循环单链表B. 只有尾结点指针没有头结点指针的非循环双链表C. 只有头结点指针没有尾结点指针的循环双链表D. 既有头结点指针也有尾头结点指针的循环单链表14. （ ）
4、描述算法最容易出现二义性。 A. 自然语言 B. 程序设计语言 C. 伪代码 D. 流程图15. 一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i（1next。 8. 栈不能用链式存储结构存放。 9. 在广义表的存储结构中，每个结点均包含有 3 个域。 10. 从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。 11. 带头结点的双循环链表 L 为空表的条件是：L-next=L。 12. 在顺序表中插入或删除一个元素，平均需要移动大量的元素，具体移动的元素个数仅与该元素在表中的位置有关。 13. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应 把两
5、个栈的栈底分别设在这片内存空间的两端。 14. 表达式检验结束时，若栈空，则表明表达式中匹配正确。 15. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 16. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列 下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。 17. 迷宫求解问题中经常用到顺序表来存储数据。 18. 在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各 自分别为元素值域和子表指针域。 19. 表达式求值问题中经常用到顺序表来存储数据。 20. 队列是一种插入与删除操作分别在表的两端进行的线性表
6、，是一种先进后 出型结构。答案：答案：一、单项选择题（一、单项选择题（6060 分，共分，共 2020 题，每小题题，每小题 3 3 分）分） 1. B 2. C 3. C 4. A 5. A 6. B 7. B 8. C 9. C 10. D 11. A 12. A 13. C 14. A 15. B 16. B 17. B 18. D 19. D 20. C 二、判断题（二、判断题（4040 分，共分，共 2020 题，每小题题，每小题 2 2 分）分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
