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

1、2014年 9月份考试数据结构第二次作业 一、单项选择题（本大题共 100分，共 40 小题，每小题 2.5 分） 1. 适于对动态查找表进行高效率查找的组织结构是（ ） A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 2. 数组占用的空间（ ） A. 必须连续 B. 可以不连续 C. 不能连续 D. 不必连续 3. 对长度为 155的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ） A. 78 B. 77.5 C. 155 D. 156 4. 用某种排序方法对关键字序列（ 25， 84， 21， 47， 15， 27， 68， 35， 20）进行排序时，序列的变化情况

2、如下： 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. 已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即 A B C D E F G H A. 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,H,C,F 6. 判定一个队列

3、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. 直接选择排序 9. Dijkstra

4、 算法的时间复杂度是（ ） 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. 1 13. 若 n个顶点的无向图

5、采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（ ） A. 对称矩阵 B. 一般矩阵 C. 稀疏矩阵 D. 对角矩阵 14. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ） A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 15. VSAM 文件中的记录均存放在（ ）。 A. 数据集 B. 索引集 C. 顺序集 D. 以上都不是 16. 关键路径是 AOE 网络中（ ） A. 从源点到汇点的最长路径 B. 最短的回路 C. 从源点到汇点的最短路径 D. 最长的回路 17. 对数据元素序列（ 49， 72， 68， 13， 38，

6、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. 二叉树是非线性数

7、据结构，所以（ ）。 A. 它不能用顺序存储结构存储 ; 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

8、. 以上答案都不对 23. 一个非空广义表的表头（ ） 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

9、-prior=p-next ;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，

10、 38， 46， 56， 79， 84 D. 38， 46， 56， 79， 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. 5 C. 6 D. 7 32. 字符 A、 B

11、、 C 依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ 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，

12、15， 25， 10， 30， 7)的二叉排序树中查找 30 需要进行多少次比较。（ ） A. 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. 在基于关键字比较的排序算法中，（ ）算法的

13、最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 38. 采用折半查找方法进行查找时，数据文件应为（ ） A. 线性表 B. 随机表 C. 有序表 D. 顺序存储结构 39. 把一棵树转换为二叉树后，这棵二叉树的形态是（ ） A. 唯一的 B. 有多种 C. 有多种，但根结点都没有左孩子 D. 有多种，但根结点都没有右孩子 40. 下列哪项属于顺序文件的优点？（ ） A. 顺序存取速度快 B. 适合随机存取 C. 适合按关键字存取 D. 以上都不是 答案： 一、单项选择题（ 100分，共 40 题，每小题 2.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