数据结构与算法单元测试题2及答案.docx

一、单选题1、若串S=KoftWarH其前缀真子串的数目是()。A.9B.8C.7D.10正确答案：C2、两个串相等的充要条件是()oA.两个字符串的长度相等且对应位置上的字符也相等B,两个字符串的长度相等C.两个字符串中对应位置上的字符相等D.两个字符串存储形式相同正确答案：A3函数StrCmP('stcabuc','stbabuc')的返回值是()。A.1B.-1C.0D.2正确答案：A4、Strlndex(DA7ASTRUCTRE',1,'STR)=()。C.3D.7正确答案：B5、设正文串长度为n,模式串长度为m,则模式匹配的KMP算法的时间复杂度为()。A.O(n)B.O(m)C.O(m+n)D.O(m*n)正确答案：C6、设S=”“，则LenStr(三)=()。A.1B.2C.3D.0正确答案：D7、设目标串T="aabaababaabaa",模式P="abab",朴素匹配算法的外层循环进行了()次。A.5B.9C.4正确答案：A8、若串标SOFT,其子串的数目最多是()。A.9B.12C.10D.11正确答案：D9、设串S1=,ABCDEFG',S2=,PQRST,则ConcatStr(SubStr(Sl,2,LenStr(S2),SubStr(Sl,LenStr(S2),2)的结果串为()。A.,BCPQRSTB.,BCDEFEF'C.,BCDEF,D.,BCDEFG,正确答案：B10、某串的长度小于一个常数，则采用()存储方式最节省空间。A.堆结构B.顺序C.链式D.无法确定11、二维数组A的每个元素都是6个字符组成的串，行下标i的范围从O到8,列下标j的范围从1到10,则如果A按行存放元素A85的起始地址与A按列存放时元素()的起始地址一致。A.A58B.A09C.A310D.A85正确答案：C12、若对n阶对称矩阵A,下标从1开始，以行序为主序方式将其下三角形的元素依次存放于一维数组BLl.(n(n+1)2中，则在B中确定aij(lWi,jWn且ij)的位置k的计算公式为()。A.j(j-l)2+iB.i(i-l)2+jC.i(i+l)2+jD.j(j+l)2+i正确答案：A13、有一个IC)O*90的稀疏矩阵，非零元素(int型)有10个，假设int型占2个字节，则用三元组顺序表表示该矩阵时所需的字节数是()。A.18000B.60C.66D.33正确答案：C14、已知广义表L=(×,y,z),a,(u,t,W),从L表中取出原子项t的运算是()。A.head(tail(tail(L)B.head(tail(head(tail(L)C.head(tail(head(tail(tail(L)D.tail(head(head(tail(L)正确答案：C15>广义表A=(a,b,(c,d),(e,(f,g),则Head(Tail(Head(TaiI(Tail（八）)的值为()。A.dB.cC.(d)D(g)正确答案：A16、下面说法不正确的是()oA.一个非空广义表的表尾总是一个广义表B,广义表可以是一个多层次的结构C.广义表的表头总是一个广义表D.广义表难以用顺序存储结构进行存储17、数组AO4-3.L,5.7中含有元素的个数（）oA.36B.55C.16D.45正确答案：D18、数组AO50.6的每个元素占5个字节，将其按列序为主序存储在起始地址为IOc）O的内存单元中，则元素A5的地址是（）oA.1175B.1205C.1210D.1180正确答案：A19、对矩阵进行压缩存储后，（）矩阵会失去随机存取的优点。A.三对角矩阵B.三角矩阵C.稀疏矩阵D.对称矩阵正确答案：C20、经常对数组进行的两种基本操作是oA.查找和修改B.查找与索引C.索引和修改D.建立与删除正确答案：A21、树最适合用来表示的结构是（）。A.元素间的无序结构B.元素间无联系的结构C.元素间具有分支及层次关系的结构D.元素间的有序结构正确答案：C22、任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置（）。A.肯定发生变化B.肯定不发生变化C.无法确定D.有时发生变化正确答案：B23、判断线索二叉树中某结点P有左孩子的条件是（）oA.p->LTag=OB.p->lchild!=NLLCpi=NULLD.p->LTag=l正确答案：A24、设森林T中有4棵树，其结点个数分别为nl,n2,n3,n4,那么当森林T转换成一棵二叉树后，则根结点的右子树上有（）个结点。A.nl+n2+n3B.n2+n3÷n4CnlD.nl-1正确答案：B25、由权值分别为9、2、5、7、4的5个叶子结点构造一棵哈夫曼树，则该树的带权路径长度为（）oA.65B.45C.55D.60正确答案：D26、算术表达式a+b*（c+de）转为后缀表达式为（）。A.abcde/+*+B.abcde/*+C.abcde*+D.ab+cde*正确答案：A27、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.214B.215C.108D.107正确答案：C28、一棵具有N个结点的二叉树采用二叉链表进行存储，其中空指针域有（）个。A.NB.N+1C.N-1D.不确定正确答案：B29、深度为K的二叉树中结点总数（）。A.2k-lB=2k-lC, 2kD, <2k-l正确答案：A30、已知一棵度为3的树有2个度为1的结点，3个度为2的结点,4个度为3的结点，则该树中有（）个叶子结点。A.13B.10C.llD.12正确答案：D31、一棵二叉树结点的()可唯一确定一棵二叉树。A.中序序列B.前序序列和后序序列C.后序序列D.前序序列和中序序列正确答案：D32、若串SeSoftWarm其前缀真子串的数目是()。A.10B.7C.8D.9正确答案：B33、StrIndex('IndeXofStringIL'Str')=()。A.9B.10C.8D.7正确答案：B34、设有三个串S1>S2和S3,则StrRePIaCe(SLS2,S3)运算称作()。A.串替换B.求子串C.模式匹配D.串连接正确答案：A35、有一个100*90的稀疏矩阵，非零元素(int型)有10个，假设int型占2个字节，则用三元组顺序表表示该矩阵时所需的字节数是()。A.66B.18C.60D.33正确答案：A36、广义表(a,(b,c),d,e)的表头为()。A.(a,(b,c)B.aC.a,(b,c)D(a)正确答案：B37、数组A。4-1.-3,57中含有元素的个数()0A.25B.55C.45D.35正确答案：C38、对下述矩阵进行压缩存储后，失去随机存取功能的是（）oA.三对角矩阵B.对称矩阵C.稀疏矩阵D.三角矩阵正确答案：C二、判断题1、KMP算法的特点是在模式匹配时指示主串的指针不会回溯。正确答案：2、设模式串的长度为m,目标串的长度为n,当n弋m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。正确答案：3、模式串P='abaabcad的next函数值序列为OIl22312正确答案：4、串的存储结构有顺序串、堆串和块链串三种。正确答案：5、串中任意个字符组成的子序列称为该串的子串。正确答案：×6、从逻辑结构上看，n维数组的每个元素均属于n个向量。正确答案：7、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。正确答案：×8、一个稀疏矩阵Am*n采用三元组顺序表形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。正确答案：×9、一个广义表可以为其它广义表所共享。正确答案：10、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。正确答案：11、完全二叉树一定存在度为1的结点。正确答案：×12、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。正确答案：×13、满二叉树一定完全是二叉树。正确答案：14、在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。正确答案：15、串的存储结构有顺序串、堆串和块链串三种。正确答案：16、一个广义表的表头一定还是个广义表。正确答案：×17、稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。正确答案：