《数据结构》1至5章期末复习题

第一章一、单项选择题1.数据结构是指（）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种（）。A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。for(i=1;i=n;i++)for(j=i;j=n;j++)x++;A.O(1)B.O()C.O(n)D.O()5.算法分析的目的是（1），算法分析的两个主要方面是（2）。A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2）A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。（1）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。3.线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。4.一个算法的效率可分为__________________效率和__________________效率。5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。8.下面程序段的时间复杂度是__________________。for(i=0;iN;I++)fontfor(j=0;jN;J++)fontA[i][j]=0;9.下面程序段的时间复杂度是__________________。i=s=0;while(sN)font{i++;s+=i;}10.下面程序段的时间复杂度是__________________。s=0;for(i=0;iN;I++)fontfor(j=0;jN;J++)fonts+=B[i][j];sum=s;11.下面程序段的时间复杂度是__________________。i=1;while(i=n)i=i*3;12.衡量算法正确性的标准通常是____________________________________。13.算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求下列程序段的时间复杂度。1.x=0;for(i=1;iN;I++)fontfor(j=i+1;j=n;j++)x++;2.x=0;for(i=1;iN;I++)fontfor(j=1;j=n-i;j++)x++;3.inti,j,k;for(i=0;iN;I++)fontfor(j=0;j=n;j++){c[i][j]=0;for(k=0;kN;K++)fontc[i][j]=a[i][k]*b[k][j]}4.i=n-1;while((i=0)&&A[i]!=k))j--;return(i);5.fact(n){if(n=1)return(1);elsereturn(n*fact(n-1));}第三章一、单项选择题1.空串与空格字符组成的串的区别在于（）。A.没有区别B.两串的长度不相等C.两串的长度相等D.两串包含的字符不相同2.一个子串在包含它的主串中的位置是指（）。A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位置3.下面的说法中，只有（）是正确的。A.字符串的长度是指串中包含的字母的个数B.字符串的长度是指串中包含的不同字符的个数C.若T包含在S中，则T一定是S的一个子串D.一个字符串不能说是其自身的一个子串4.两个字符串相等的条件是（）。A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同5.若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。A.“ijing”B.“jing＆”C.“ingNa”D.“ing＆N”6.若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。A.2B.3C.4D.57.若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。A.“Nanjing＆Shanghai”B.“Nanjing＆Nanjing”C.“ShanghaiNanjing”D.“Shanghai＆Nanjing”8.在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（）。A.i＞0B.i≤nC.1≤i≤nD.1≤i≤n+19.字符串采用结点大小为1的链表作为其存储结构，是指（）。A.链表的长度为1B.链表中只存放1个字符C.链表的每个链结点的数据域中不仅只存放了一个字符D.链表的每个链结点的数据域中只存放了一个字符二、填空题1.计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。2.两个字符串相等的充要条件是_____________________和___________________。3.设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。4.串是指___________________。5.空串是指___________________，空格串是指___________________。三、算法设计题1.设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，mSspan，t(s-m)，并将删除后的结果复制在该数组的第s单元以后的单元中，试设计此删除算法。2.设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。第四章一、单项选择题1.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k2.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（）。A.520B.522C.524D.5183.若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（）。A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]4.若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij的地址为（）。（设每个元素占d个字节）A.[(j-1)*n-+i-1]*dB.[(j-1)*n-+i]*dC．[(j-1)*n-+i+1]*dD．[(j-1)*n-+i-2]*d5.设有广义表D=(a,b,D)，其长度为（），深度为（）。A.无穷大B.3C.2D.56.广义表A=（a），则表尾为（）。A.aB.(())C.空表D.(a)7.广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。A.xB.(a,B)C.(x,(a,B))D.A8.下列广义表用图来表示时，分支结点最多的是（）。A.L=((x,(a,B)),(x,(a,B),y))B.A=(s,(a,B))C.B=((x,(a,B),y))D.D=((a,B),(c,(a,B),D)9.通常对数组进行的两种基本操作是（）。A.建立与删除B.索引和修改C.查找和修改D.查找与索引10.假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（）。A.80B.100C.240D.27011.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）。A.SA+141B.SA+144C.SA+222D.SA+22512.稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表13.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。A.正确B.不正确14.一个广义表的表头总是一个（）。A.广义表B.元素C.空表D.元素或广义表15.一个广义表的表尾总是一个（）。A.广义表B.元素C.空表D.元素或广义表16.数组就是矩阵，矩阵就是数组，这种说法（）。A.正确B.错误C.前句对，后句错D.后句对二、填空题1.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。2.对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。3.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。4.一个稀疏矩阵为，则对应的三元组线性表为_____________。5.一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为________