《2014年9月数据结构第二次作业》由会员分享，可在线阅读，更多相关《2014年9月数据结构第二次作业（6页珍藏版）》请在金锄头文库上搜索。
1、20142014 年年 9 9 月份考试数据结构第二次作业月份考试数据结构第二次作业 一、单项选择题（本大题共一、单项选择题（本大题共 100100 分，共分，共 4040 小题，每小题小题，每小题 2.52.5 分）分） 1. 适于对动态查找表进行高效率查找的组织结构是（ ） A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 2. 数组占用的空间（ ） A. 必须连续 B. 可以不连续 C. 不能连续 D. 不必连续 3. 对长度为 155 的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ） A. 78 B. 77.5 C. 155 D. 156 4. 用某种排序方法对
2、关键字序列（25，84，21，47，15，27，68，35，20）进 行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ） A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 5. 已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一 维数组中，即 ABCDEFGHA. G,D,B,A,F,H.C,E B. G,B,D,A,F,H,C,E C. B,D,G,A,F,H,C,E D. B,G,D,A,E,
3、H,C,F 6. 判定一个队列 QU（最多元素为 m0）为满队列的条件是（ ） A. QU-rear QU-front = = m0 B. QU-rear QU-front 1= = m0 C. QU-front = = QU-rearQU-front = = QU-rear+1 7. 图中有 n 个顶点，e 条边，如果用邻接表表示图，则深度优先搜索遍历图的 时间复杂性为（ ）。 A. O(n)B. O(e) C. O(n2) D. O(n+e) 8. 如果只想得到 1024 个元素组成的序列中的前 5 个最小元素，那么用（ ）方 法最快。 A. 起泡排序 B. 快速排序 C. 堆排序 D.
4、直接选择排序 9. Dijkstra 算法的时间复杂度是（ ） A. O（n） B. O（n2） C. O（e） D. O（n+e） 10. 设有一个 10 阶的对称矩阵 A1010，采用压缩存储方式按行将矩阵中下 三角部分的元素存入一维数组 B 中，A00存入 B0中，则 A85在 B 中 （ ）位置。 A. 32 B. 33 C. 41 D. 65 11. 如下陈述中正确的是（ ） A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串 12. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D.
5、1 13. 若 n 个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？ （ ） A. 对称矩阵 B. 一般矩阵 C. 稀疏矩阵 D. 对角矩阵 14. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ） A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 15. VSAM 文件中的记录均存放在（ ）。 A. 数据集B. 索引集 C. 顺序集 D. 以上都不是 16. 关键路径是 AOE 网络中（ ） A. 从源点到汇点的最长路径 B. 最短的回路 C. 从源点到汇点的最短路径 D. 最长的回路 17. 对数据元素序列（49，7
6、2，68，13，38，50，97，27）进行排序，如果采 用起泡排序方法，则第二趟排序结果是（ ） A. 49，68，13，38，50，72，27，97 B. 13，38，49，50，27，68，72，97 C. 49，13，38，50，68，27，72，97 D. 13，38，49，27，50，68，72，97 18. 哈希表表长为 m，k 为关键字，哈希地址 H(k)=k MOD p。为了减少发生冲 突的频率，一般取 p 为（ ） A. 小于 m 的最大奇数 B. 小于 m 的最大合数 C. 小于 m 的最大素数 D. 大于 m 的最小素数 19. 二叉树是非线性数据结构，所以（ ）。 A
7、. 它不能用顺序存储结构存储; B. 它不能用链式存储结构存储; C. 顺序存储结构和链式存储结构都能存储; D. 顺序存储结构和链式存储结构都不能使用 20. 数组结构一旦确定，其元素的个数是（ ） A. 不变的 B. 可变的 C. 任意的 D. 0 21. 某算法仅含程序段 1 和程序段 2，程序段 1 的执行次数 3n2，程序段 2 的执 行次数为 0.01n3，则该算法的时间复杂度为（ ）。 A. O(n) B. O(n2) C. O(n3) D. O(1) 22. KRUSKAL 算法的时间主要取决于（ ） A. 顶点数 B. 边数 C. 顶点数和边数 D. 以上答案都不对 23.
8、一个非空广义表的表头（ ） A. 不可能是子表 B. 只能是子表C. 只能是原子 D. 可以是子表或原子 24. 在长度为 10 的顺序表中删除元素需要移动许多元素，最坏情况下的删除需 要移动的元素个数是（ ） A. 10 B. 9 C. 8 D. 7 25. 设图 G 采用邻接表存储，则拓扑排序算法的时间复杂度为（ ） A. O（n） B. O(n+e) C. O(n2) D. O(ne) 26. 在双向链表中删除 P 指针指向的结点的操作应该是（ ） A. p-prior-next=p-next ;p-next-prior=p-prior; B. p-prior-prior=p-next
9、;p-next-prior=p-prior; C. p-prior-next=p-next ;p-next-next=p-prior; D. 以上都不是 27. 在初始为空的队列中依次插入元素 a,b,c,d 以后，紧接着作了三次删除操 作，此时的队头元素是 （ ） A. a B. b C. c D. d 28. 一个对象序列的排序码为46，79，56，38，40，84，采用快速排序以位 于最左位置的对象为基准而得到的第一次划分结果为（ ）。 A. 38，46，79，56，40，84 B. 38，79，56，46，40，84 C. 40，38，46，56，79，84 D. 38，46，56，7
10、9，40，84 29. 关键字集合、地址集合散列法存储的冲突指的是（ ） A. 两个元素具有相同的关键字 B. 两个元素的关键字值不同 C. 不同关键字值对应相同的存储地址 D. 负载因子过大 30. 若输入的顶点信息即为顶点的编号，则建立邻接表的时间复杂度是( ) A. O（n） B. O(e) C. O(n2) D. O(n+e) 31. 在一棵度为 3 的树中,度为 3 的结点个数为 2,度为 2 的结点个数为 1,则度 为 0 的结点个数为( ) A. 4 B. 5C. 6 D. 7 32. 字符 A、B、C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至 多可以组成( )个不同
11、的字符串？ A. 5 B. 4 C. 6 D. 1 33. 在由 head 头指针所指的非空线性链表中删除由 p 指的链结点的下一个链结 点的过程是依次执行：q = p - next，free(q)。 （ ） A. p-next = q B. - next = p C. q-next=p-next D. p-next=q-next 34. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作：（ ） A. 连接 B. 模式匹配 C. 求子串 D. 求串长 35. 在对应于序列(12，5，8，15，25，10，30，7)的二叉排序树中查找 30 需 要进行多少次比较。（ ） A.
12、1 B. 2 C. 3 D. 4 36. 单链表的每个结点中包括一个指针 next，它指向该结点的后继结点。现要 将指针 q 指向的新结点插入到指针 p 指向的单链表结点之后，下面的操作序列 中哪一个是正确的？ （ ） A. q=p-next; p-next=q-next; B. p-next=q-next; C. q=p-next D. q-next=p-next; E. p-next=q; F. P-next=q; G. q-next=p-next; 37. 在基于关键字比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不 高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C.
13、 归并排序 D. 快速排序 38. 采用折半查找方法进行查找时，数据文件应为（ ） A. 线性表 B. 随机表C. 有序表 D. 顺序存储结构 39. 把一棵树转换为二叉树后，这棵二叉树的形态是（ ） A. 唯一的 B. 有多种 C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子 40. 下列哪项属于顺序文件的优点？（ ） A. 顺序存取速度快 B. 适合随机存取 C. 适合按关键字存取 D. 以上都不是答案：答案：一、单项选择题（一、单项选择题（100100 分，共分，共 4040 题，每小题题，每小题 2.52.5 分）分） 1. C 2. A 3. A 4. B 5. D 6. A 7. D 8. D 9. B 10. C 11. A 12. A 13. A 14. D 15. A 16. A 17. C 18. C 19. C 20. C 21. C 22. B 23. D 24. B 25. B 26. A 27. D 28. C 29. C 30. D 31. C 32. A 33. D 34. B 35. D 36. C 37. C 38. C 39. A 40. A
