2015年数据结构(第二次)作业

《2015年数据结构(第二次)作业》由会员分享，可在线阅读，更多相关《2015年数据结构(第二次)作业（6页珍藏版）》请在金锄头文库上搜索。

1、第第 2 2 次作业次作业 一、单项选择题（本大题共一、单项选择题（本大题共 100100 分，共分，共 4040 小题，每小题小题，每小题 2.52.5 分）分） 1. 适于对动态查找表进行高效率查找的组织结构是（ ） A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 2. 数组占用的空间（ ） A. 必须连续 B. 可以不连续 C. 不能连续 D. 不必连续 3. 数组用来表示一个循环队列，为当前队列头元素的前一位置， 为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为( ) A. rf; B. （nfr）% n; C. nrf; D. （nrf）% n 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. 不含任何结点的空树（ ）。 A. 是一棵树; B. 是一棵二叉树; C. 是一棵树也是一棵二叉树; D. 既不是树也不是二叉树 6. 已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一 维数组中，即 A

3、BCDEFGHA. 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 = = m0B. 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. O(n2) D. O(n+

4、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 串的连接 串，subs(s, i, j)返回串

5、 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. 33 C. 41

6、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. 从源点到汇点的最短路径 D.

7、 最长的回路 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. 120 22. 哈希表表长为 m，k 为关键字，哈希地址 H(k)=k MOD p。为

8、了减少发生冲 突的频率，一般取 p 为（ ） A. 小于 m 的最大奇数 B. 小于 m 的最大合数 C. 小于 m 的最大素数D. 大于 m 的最小素数 23. 二叉树是非线性数据结构，所以（ ）。 A. 它不能用顺序存储结构存储; B. 它不能用链式存储结构存储; C. 顺序存储结构和链式存储结构都能存储; D. 顺序存储结构和链式存储结构都不能使用 24. 数组结构一旦确定，其元素的个数是（ ） A. 不变的 B. 可变的 C. 任意的 D. 0 25. 链表是一种采用（ ）存储结构存储的线性表 A. 顺序 B. 链式 C. 星式 D. 网状 26. 执行下面程序段时，执行 S 语句的次

9、数为（ ） 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. 对二叉排序树的结点进行哪种遍历就可以得到排好序的结点序列。（ ） A. 先序遍历 B. 中序遍历 C.

10、后序遍历 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 指向的单链表结点之后，下面的操作序列 中哪一个是正确的？ （ ） A. q=p-next; p-next=q-next; B

11、. p-next=q-next; C. q=p-nextD. 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. 以上都不是答案：答案：一、单项选择题（一、单项选择题（100100 分，共分，共 4040 题，每小题题，每小题 2.52.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