数据结构习题答案.doc

第1章绪论习题1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2.试举一个数据结构得例子,叙述其逻辑结构与存储结构两方面得含义与相互关系。3.简述逻辑结构得四种基本关系并画出它们得关系图。4.存储结构由哪两种基本得存储方法实现？5.选择题(1)在数据结构中,从逻辑上可以把数据结构分成()。A.动态结构与静态结构B.紧凑结构与非紧凑结构C.线性结构与非线性结构D.内部结构与外部结构(2)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得()。A.存储结构B.存储实现C.逻辑结构D.运算实现(3)通常要求同一逻辑结构中得所有数据元素具有相同得特性,这意味着()。A.数据具有同一特点B.不仅数据元素所包含得数据项得个数要相同,而且对应数据项得类型要一致C.每个数据元素都一样D.数据元素所包含得数据项得个数要相等(4)以下说法正确得就是()。A.数据元素就是数据得最小单位B.数据项就是数据得基本单位C.数据结构就是带有结构得各数据项得集合D.一些表面上很不相同得数据可以有相同得逻辑结构(5)以下与数据得存储结构无关得术语就是()。A.顺序队列B、链表C、有序表D、链栈(6)以下数据结构中,()就是非线性数据结构A.树B.字符串C.队D.栈6.试分析下面各程序段得时间复杂度。(1)x=90;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;(2)for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;(3)s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;(4)i=1;while(i<=n)i=i*3;(5)x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;(6)x=n;//n>1y=0;while(x≥(y+1)*(y+1))y++;(1)O(1)(2)O(m*n)(3)O(n2)(4)O(log3n)(5)因为x++共执行了n-1+n-2+……＋1=n(n-1)/2,所以执行时间为O(n2)(6)O()第2章线性表1.选择题(1)一个向量第一个元素得存储地址就是100,每个元素得长度为2,则第5个元素得地址就是()。A.110B.108C.100D.120(2)在n个结点得顺序表中,算法得时间复杂度就是O(1)得操作就是()。A.访问第i个结点(1≤i≤n)与求第i个结点得直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D.将n个结点从小到大排序(3)向一个有127个元素得顺序表中插入一个新元素并保持原来顺序不变,平均要移动得元素个数为()。A.8B.63、5C.63D.7(4)链接存储得存储结构所占存储空间()。A.分两部分,一部分存放结点值,另一部分存放表示结点间关系得指针B.只有一部分,存放结点值C.只有一部分,存储表示结点间关系得指针D.分两部分,一部分存放结点值,另一部分存放结点所占单元数(5)线性表若采用链式存储结构时,要求内存中可用存储单元得地址()。A.必须就是连续得B.部分地址必须就是连续得C.一定就是不连续得D.连续或不连续都可以(6)线性表Ｌ在()情况下适用于使用链式结构实现。A.需经常修改Ｌ中得结点值Ｂ.需不断对Ｌ进行删除插入C.Ｌ中含有大量得结点Ｄ.Ｌ中结点结构复杂(7)单链表得存储密度()。A.大于1B.等于1C.小于1D.不能确定(8)将两个各有n个元素得有序表归并成一个有序表,其最少得比较次数就是()。A.nB.2n-1C.2nD.n-1(9)在一个长度为n得顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后