山大网络《数据结构》试卷(A卷).doc

《数据结构》试卷（A卷） 一、选择题 1. 数据结构是指（ A ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ D ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ B ）。 for i 1; i n; i++ for j i; j n; j++ x++; A.O 1 B.O C.O n D.O 5. 算法分析的目的是（1C），算法分析的两个主要方面是（2A）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1C），它具备输入，输出和（2B）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B ）。 A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（ D ）年。 A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（B ）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（B ）。 A.数据 B.数据元素 C.数据项 D.数据库 11. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为 　D　 。 A. n B. n+1 C. n-1 /2 D. n+1 /2 12. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为 　A　 的9分之一。 A. 20 B. 18 C. 25 D. 22 13. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为 　B　 。 A. 3 B. 4 C. 5 D. 6 14. 对于顺序存储的有序表 5,12,20,26,37,42,46,50,64 ，若采用折半查找，则查找元素26的比较次数为 　B　 。 A. 2 B. 3 C. 4 D. 5 15. 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为 D　　 。 A. O n B. O n2 C. O 1 D. O log2n 16. 在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为 　D　 。 A. n+k B. k+n/k C. k+n/k /2 D. k+n/k /2+1 17. 在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为 　A　 。 A. 13 B. 24 C. 12 D. 79 二、填空题 1. 数据结构按逻辑结构可分为两大类，分别是_线性结构非线性结构集合，线性，树，图一对一，一对多或多对多时间空间前趋一后继多有多个一对一一对多多对多 O __。 for i 0;i n;i++ for j 0;j n;j++ A[i][j] 0; 9. 下面程序段的时间复杂度是___ O √n ___。 i s 0; while s n i++; s+ i; 10. 下面程序段的时间复杂度是___ O ____。 s 0; for i 0;i n;i++ for j 0;j n;j++ s+ B[i][j]; sum s; 11. 下面程序段的时间复杂度是__ O log3 n ___。 i 1; while i n i i*3; 三、判断题 1. 二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。 （X） 2. 二叉树的前序遍历中，任意结点均处在其子女结点之前。 （√） 3. 线索二叉树是一种逻辑结构。 （X　） 4. 哈夫曼树的总结点个数（多于1时）不能为偶数。 （√） 5. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 （X　） 6. 树的后序遍历