《数据结构试卷A卷.docx》由会员分享，可在线阅读，更多相关《数据结构试卷A卷.docx（5页珍藏版）》请在三一文库上搜索。
1、读书破万卷下笔如有神数据结构试卷（A卷）一、选择题1 .数据结构是指（）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2 .数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）A.存储结构 B.逻辑结构D.顺序存储结构 C.链式存储结构3 .树形结构是数据元素之间存在一种（）。A. 一对一关系B.多对多关系D. 一对多关系C.多对一关系4 .设语句x+的时间是单位时间，则以下语句的时间复杂度为（）。for（i=1; i=n; i+）for（j=i； j=n； j+）x+;23nn）D.O（C.O（n） B.O（ ） A.O（1）5 .算法分析的目的是（1）,算法
2、分析的两个主要方面是（2）（1） A.找出数据结构的合理性C.分析算法的效率以求改进D.（2） A.空间复杂度和时间复杂度C.可读性和文档性D.B.研究算法中的输入和输出关系分析算法的易懂性和文档性B.正确性和简明性数据复杂性和程序复杂性6.计算机算法指的是（1）,它具备输入，输出和（2）等五个特性。排序方法调度方法B. 可行性，确定性和有穷性易读性，稳定性和安全性（1） A.计算方法B.C.解决问题的有限运算序列D.（2） A.可行性，可移植性和可扩充性C.确定性，有穷性和稳定性D.7 .数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。不好说D.
3、相同C. 高B. 低A.读书破万卷 下笔如有神8 .数据结构作为一门独立的课程出现是在（）年A.1946B.1953 C.1964 D.19689 .数据结构只是研究数据的逻辑结构和物理结构，这种观点（）A.正确 B. 错误C.前半句对，后半句错D.前半句错，后半句对10 .计算机内部数据处理的基本单位是（）。A.数据 B.数据元素C.数据项D.数据库11 .若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为A. n B. n+1 C. (n-1)/2 D. (n+1)/212.对于长度为9的顺序存储的有序表,若采用折半查找，在等概率情况下的平均查找长度为的9分之一。
4、A. 20B.18C.2513.对于长度为18的顺序存储的有序表,A. 3B.4C. 5D.22若采用折半查找，则查找第15个元素的比较次数为D. 614.对于顺序存储的有序表 (5, 12, 20,26, 37,42, 46, 50, 64),若采用折半查找，则查找元素26的比较次数为()。A. 2 B. 3 C. 4 D. 515.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为()。2C. O(1)D. O(logn)A. O(n) B. O(n)216.在索引查找中，若用于保存数据元素的主表的长度为n,它被均分为k个子表，每个子表的长度土匀为n/k ,则索引查找的平均查找长度为
5、()。A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+117.在索引查找中，若用于保存数据元素的主表的长度为144,它被均分为12子表，每个子表的长度土匀为12,则索引查找的平均查找长度为()。A. 1379D.12C.24B.二、填空题。和 数据结构按逻辑结构可分为两大类，分别是1.读书破万卷下笔如有神2 .数据的逻辑结构有四种基本形态，分别是 、 和。3 .线性结构反映结点间的逻辑关系是 的，非线性结构反映结点间的逻辑关 系是 的。4 .一个算法的效率可分为 效率和 效率。5 .在树型结构中，枳i根结点没有 结点，其余每个结点的有且只有 个前趋驱结点；叶
6、子结点没有 结点；其余每个结点的后续结点可以。6 .在图型结构中，每个结点的前趋结点数和后续结点数可以 o7 .线性结构中元素之间存在 关系；树型结构中元素之间存在 关系；图型结构中元素之间存在 关系。8 .下面程序段的时间复杂度是 ofor(i=0;in;i+)for(j=0;jn;j+)Aij=0;9 .下面程序段的时间复杂度是 o i=s=0;while(sn) i+;s+=i;10 .下面程序段的时间复杂度是s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bi皿sum=s;11 .下面程序段的时间复杂度是 i=1;while(i=n)读书破万卷下笔如有神i=i*3
7、;三、判断题1.二叉树中每个结点的度不能超过2,所以二叉树是一种特殊的树)(2.二叉树的前序遍历中，任意结点均处在其子女结点之前。)(3.线索二叉树是一种逻辑结构。(5.(7.根据任意一种遍历)4.哈夫曼树的总结点个数(多于1时)不能为偶数。)由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。)6.树的后序遍历与其对应的二叉树的后序遍历序列相同。序列即可唯一确定对应的二叉树。()()8.满二叉树也是完全二叉树。()9.哈夫曼树一定是完全二叉树。)(10.树的子树是无序的。四、求下列程序段的时间复杂度。1. x=0;for(i=1;in;i+) for(j=i+1;j=n;j+) x+;2. x=0;for(i=1;in;i+)for(j=1;j=n-i;j+)x+;3. int i,j,k;读书破万卷 下笔如有神 for(i=0;in;i+)for(j=0;j=n;j+) cij=0;for(k=0;kn;k+)cij=aik*bkj 322nn) 解： ) 2. O(1. O() 3. O(n