重大2015年数据结构 ( 第2次作业 ).doc

1、第 2次作业 一、单项选择题（本大题共 100 分，共 40 小题，每小题 2.5 分） 1. 适于对动态查找表进行高效率查找的组织结构是（ ） A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 2. 数组占用的空间（ ） A. 必须连续 B. 可以不连续 C. 不能连续 D. 不必连续 3. 数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为( ) A. r f; B. （ n f r） % n; C. n r f; D. （ n r f） % n 4. 用某种排序方法对关键字序列（ 25， 84， 21，

2、 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. 不含任何结点的空树（ ）。 A. 是一棵树 ; B. 是一棵二叉树 ; C. 是一棵树也是一棵二叉 树 ; D. 既不是树也不是二叉树 6. 已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维

3、数组中，即 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 7. 判定一个队列 QU（最多元素为 m0）为满队列的条件是（ ） A. QU-rear QU-front = = m0 B. QU-rear QU-front 1= = m0 C. QU-front = = QU-rearQU-front = = QU-rear+1 8. 图中有 n个顶点， e条边，如果用邻接表表示图，则深度优先搜索遍历图的时间复杂性为（ ）。 A. O(n) B. O(e) C.

4、 O(n2) D. O(n+e) 9. 对长度为 155的顺序表在等概率情况下进行顺序查找的平均查找长度为（ ） A. 78 B. 77.5 C. 155 D. 156 10. 假设一个有 n个顶点和 e条弧的有向图用邻接表表示 ,则删除与某个顶点vi相关的所有弧的时间复杂度是 ( ) A. O(n) B. O(e) C. O(n+e) D. O(n*e) 11. Dijkstra算法的时间复杂度是（ ） A. O（ n） B. O（ n2） C. O（ e） D. O（ n+e） 12. 设串 s1=ABCDEFG ， s2=PQRST ，函数 con(x,y)返回 x和 y串的连接串， s

5、ubs(s, i, j)返回串 s的从序号 i开始的 j个字符组成的子串， len(s)返回串 s的长度，则 con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的结果串是： A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 13. 数据结构中，与所使用的硬件无关的是数据的 ( )结构； A. 存储 B. 物理 C. 逻辑 D. 物理和存储 14. 设有一个 10阶的对称矩阵 A1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组 B 中， A00存入 B0中，则 A85在 B 中（ ）位置。 A. 32 B.

6、 33 C. 41 D. 65 15. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. 1 16. 若 n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（ ） A. 对称矩阵 B. 一般矩阵 C. 稀疏矩阵 D. 对角矩阵 17. 平衡二叉树的平衡因子的取值不可能是（ ） A. 1 B. -1 C. 0 D. 2 18. VSAM文件中的记录均存放在（ ）。 A. 数据集 B. 索引集 C. 顺序集 D. 以上都不是 19. 关键路径是 AOE 网络中（ ） A. 从源点到汇点的最长路径 B. 最短的回路 C. 从源点到汇点的

7、最短路径 D. 最长的回 路 20. 对数据元素序列（ 49， 72， 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 21. 顺序表中第一个元素的存储地址是 100，每个元素的长度为 2，则第 5个元素的地址是（ ） A. 110 B. 108 C. 100 D. 12

8、0 22. 哈希表表长为 m， k为关键字，哈希地址 H(k)=k MOD p。为了减少发生冲突的频率，一般取 p为（ ） A. 小于 m的最大奇数 B. 小于 m的最大合数 C. 小于 m的最大素数 D. 大于 m的最小素数 23. 二叉树是非线性数据结构，所以（ ）。 A. 它不能用顺序存储结构存储 ; B. 它不能用链式存储结构存储 ; C. 顺序存储结构和链式存储结构都能存储 ; D. 顺序存储结构和链式存储结构都不能使用 24. 数组结构一旦确 定，其元素的个数是（ ） A. 不变的 B. 可变的 C. 任意的 D. 0 25. 链表是一种采用（ ）存储结构存储的线性表 A. 顺序

9、B. 链式 C. 星式 D. 网状 26. 执行下面程序段时，执行 S 语句的次数为（ ） for ( int i = 1; i prior-next=p-next ;p-next-prior=p-prior; B. p-prior-prior=p-next ;p-next-prior=p-prior; C. p-prior-next=p-next ;p-next-next=p-prior; D. 以上都不是 34. 在初始为空的队列中依次插入元素 a,b,c,d 以后，紧接着作了三次删除操作，此时的队头元素是 （ ） A. a B. b C. c D. d 35. 对二叉排序树的结点进行哪种

10、遍历就可以得到排好序的结点序列。（ ） A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 36. 向一个有 127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素 A. 8 B. 63.5 C. 63 D. 7 37. 设 F是一个森林， B是由 F转换得到的二叉树， F中有 n个非叶结点，则 B中右指针域为空的结点有（ ）个。 A. n-1 B. n C. n+1 D. n+2 38. 单链表的每个结点中包括一个指针 next，它指向该结点的后继结点。现要将指针 q指向的新结点插入到指针 p指向的单链表结点之后，下面的操作序列中哪一个是正确的？ （ ）

11、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; 39. 在基于关键字比较的排序算法中，（ ）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 40. 下列哪项属于顺序文件的优点？（ ） A. 顺序存取速度快 B. 适合随机存取 C. 适合按关键字存取 D. 以上都不是 答案： 一、单项选择题（ 100 分，共 40 题，每小题 2.5 分） 1. C 2. A 3. D 4. B 5. C 6. D 7. A 8. D 9. A 10. C 11. B 12. D 13. C 14. C 15. A 16. A 17. D 18. A 19. A 20. C 21. B 22. C 23. C 24. C 25. B 26. C 27. C 28. B 29. A 30. D 31. B 32. A 33. A 34. D 35. B 36. B 37. C 38. C 39. C 40. A