搜索
1《数据结构》试卷（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(2n)C.O(n)D.O(3n)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.不好说28.数据结构作为一门独立的课程出现是在（D）年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（B）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（B）。A.数据B.数据元素C.数据项D.数据库11.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(D)。A.nB.n+1C.(n-1)/2D.(n+1)/212.对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为(A)的9分之一。A.20B.18C.25D.2213.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(B)。A.3B.4C.5D.614.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为(B)。A.2B.3C.4D.515.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(D)。A.O(n)B.O(n2)C.O(1)D.O(log2n)16.在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为(D)。A.n+kB.k+n/kC.(k+n/k)/2D.(k+n/k)/2+117.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为(A)。A.13B.24C.12D.79二、填空题1.数据结构按逻辑结构可分为两大类，分别是_线性结构和非线性结构___。32.数据的逻辑结构有四种基本形态，分别是_集合，线性，树，图__。3.线性结构反映结点间的逻辑关系是_一对一，__的，非线性结构反映结点间的逻辑关系是____一对多或多对多_的。4.一个算法的效率可分为___时间__效率和___空间_______________效率。5.在树型结构中，树根结点没有__前趋__结点，其余每个结点的有且只有___一__个前趋驱结点；叶子结点没有___后继____结点；其余每个结点的后续结点可以___多____。6.在图型结构中，每个结点的前趋结点数和后续结点数可以_有多个___。7.线性结构中元素之间存在_一对一__关系；树型结构中元素之间存在____一对多_关系；图型结构中元素之间存在___多对多___关系。8.下面程序段的时间复杂度是__O(2n)__。for(i=0;in;i++)for(j=0;jn;j++)A[i][j]=0;9.下面程序段的时间复杂度是___O(√n)___。i=s=0;while(sn){i++;s+=i;}10.下面程序段的时间复杂度是___O(2n)____。s=0;for(i=0;in;i++)for(j=0;jn;j++)s+=B[i][j];sum=s;11.下面程序段的时间复杂度是__O(log3n)___。i=1;while(i=n)4i=i*3;三、判断题1.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。（X）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（√）3.线索二叉树是一种逻辑结构。（X）4.哈夫曼树的总结点个数（多于1时）不能为偶数。（√）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（X）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（X）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（X）8.满二叉树也是完全二叉树。（√）9.哈夫曼树一定是完全二叉树。（X）10.树的子树是无序的。（√）四、求下列程序段的时间复杂度。1.x=0;for(i=1;in;i++)for(j=i+1;j=n;j++)x++;解：O(2n)2.x=0;for(i=1;in;i++)for(j=1;j=n-i;j++)x++;解：O(2n)3.inti,j,k;for(i=0;in;i++)for(j=0;j=n;j++){c[i][j]=0;for(k=0;kn;k++)c[i][j]=a[i][k]*b[k][j]}解：O(n3)