数据结构题集及答案

数据结构题集及答案数据结构题集及答案数据结构题集及答案数据结构题集及答案编制仅供参考审核批准生效日期地址：电话：传真:邮编:判断题数据的逻辑结构与数据元素本身的内容和形式无关。（√）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√）数据元素是数据的最小单位。（√）数据的逻辑结构和数据的存储结构是相同的。（×）程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。（×）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√）数据的存储结构是数据的逻辑结构的存储映像。（×）数据的物理结构是指数据在计算机内实际的存储形式。（√）数据的逻辑结构是依赖于计算机的。（×）算法是对解题方法和的描述步骤。（√）填空题：数据有逻辑结构和存储结构两种结构。数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。树形结构和图形结构合称为非线性结构。在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。数据的存储结构又叫物理结构。数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。线性结构中的元素之间存在一对一的关系。树形结构中的元素之间存在一对多的关系。图形结构的元素之间存在多对多的关系。数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的内容。数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的有限集合。算法是一个有穷指令的集合。算法效率的度量可以分为事先估算和事后统计法。一个算法的时间复杂性是算法输入规模的函数。算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为___O（n*n）_______。数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。串的两种最基本的存储方式是顺序存储方式链式存储方式。两个串相等的充分必要条件是、长度相等对应位置的字符相同。空串是零个字符，其长度等于零。空格串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。设s=”I□AM□A□TEACHER”(□表示空格)，其长度是14。已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是LOC(A[0][0])+(n*i+j)*k。二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是200+（12*10+6）=326。二维数组A[10，…，20][5，…，10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[8][9]的地址是_1000+((18-10)*6+(9-5))*4=1208。通常从四个方面评价算法的质量：正确性、易读性、健壮性和高效率。中序遍历二叉排序树得到的序列是有序序列（填有序或无序）。。设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中共有2N0+N1个空指针域。。假设为循环队列分配的向量空间为Q[20]（下标从0开始），若队列的长度和队头指针值分别为13和17，则当前队尾指针的值为10。设一棵完全二叉树中有500个结点，则该二叉树的深度为9；若用二叉链表作为该完全二叉树的存储结构，则共有501个空指针域。数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的有限集合。数据有逻辑结构和存储两种结构。串的两种最基本的存储方式是顺序存储和链接存储。若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O(n2)。数据结构主要研究数据的逻辑结构、存储结构和算法3个方面的内容。算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。选择题：数据结构通常是研究数据的（A）及它们之间的相互关系。A．存储结构和逻辑结构 B．存储和抽象C．联系和抽象 D．联系与逻辑在逻辑上可以把数据结构分成（C）。A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构数据在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构非线性结构中的每个结点（D）。A．无直接前趋结点 B．无直接后继结点C．只有一个直接前趋和一个直接后继结点 D．可能有多个直接前趋和多个直接后继结点链式存储结构所占存储空间（A）。A．分两部分，一部分存储结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点的值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点的值，另一部分存放结点所占单元数算法的计算量大小称为算法的（C）。A．现实性 B．难度 C．时间复杂性 D．效率数据的基本单位是（B）。A．数据结构 B．数据元素 C．数据项 D．文件每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里。这种存储结构称为（A）结构。A．顺序存储 B．链式存储 C．索引存储 D．散列存储每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式。A．顺序 B．链式 C．索引 D．散列以下任何两个结点之间都没有逻辑关系的是（D）。A．图形结构 B．线性结构 C．树形结构 D．集合在数据结构中，与所使用的计算机无关的是（C）。A．物理结构 B．存储结构 C．逻辑结构 D．逻辑和存储结构下列4种基本逻辑结构中，数据元素之间关系最弱的是（A）。A．集合 B．线性结构 C．树形结构 D．图形结构与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A）。A．逻辑结构 B．存储结构 C．逻辑实现 D．存储实现每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点位置的表，该存储方式是（C）存储方式。A．顺序 B．链式 C．索引 D．散列算法能正确的实现预定功能的特性称为算法的（A）。A．正确性 B．易读性 C．健壮性 D．高效性算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。A．正确性 B．易读性 C．健壮性 D．高效性下列时间复杂度中最坏的是（D）。A．O(1) B．O(n) C．O(log2n) D．O(n2)下列算法的时间复杂度是（D）for(i=0;i<n;i++)for(j=0;j<n;j++)C[i][j]=i+j;A．O(1) B．O(n) C．O(log2n) D．O(n2)算法分析的两个主要方面是（A）。A．空间复杂性和时间复杂性 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性计算机算法必须具备输入、输出和（C）。A．计算方法 B．排序方法 C．解决问题的有限运算步骤 D．程序设计方法如下图所示的4棵二叉树，（C）不是完全二叉树。如下图所示的4棵二叉树，（B）是平衡二叉树。在线索化二叉树中，t所指结点没有左子树的充要条件是（）。A． B． C． D．二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法（B）。A． 正确 B．错误 C．不确定 D．不存在二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法（A）。A． 正确 B．错误 C．不确定 D．不存在由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（A）。A． 正确 B．错误 C．不确定 D．不存在设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。A．2h B．2h-1C．2h+1 D．h+1如右图所示二叉树的中序遍历序列是（B）。 A．abcdgef B．dfebagcC．dbaefcg D．defbagc已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是（A）。A．cedba B．cdbae C．cabed D．cabde设a和b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（D）。A．a是b的左孩子 B．b是a的右孩子C．a是b左子树上结点或b是a右子树上结点 D．以上三项均可假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（C）个。A． 45 B．15 C．16 D．31某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历序列是（A）。A．gdbehfca B．abcdefgh C．gdbaefch D．ghbcdefa按照二叉树的定义，具有3个结点的二叉树有（D）种。A．2 B．3 C．4 D．5树的基本遍历策略可分为先根遍历和后根遍历；二叉树的遍历策略分为先序、中序和后序遍历。这里把由树转化得到的二叉树叫做这棵树对应的二叉树。以下结论（）是正确的。A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同C．树的先根遍历序列与其对应的二叉树的中序遍历序列相同D．以上都不对空串与空格串是相同的，这种说法（B）。A．正确 B．错误 C．依据情况而定 D．不规范串是一种特殊的线性表，其特殊性体现在（D）。A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符设有两个串p和q，求q在p中首次出现的位置的运算称做（B）。A．连接 B．模式匹配 C．求子串 D．求串长设串s1=”ABCDEFG”，s2=”PQRST”，函数con（x，y）返回x和y串的连接，subs（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con（subs（s1，2，len（s2）），subs(s1,len(s2),2)）的结果是（D）。A．BCDEF B．BCDEFG C．BCPQRST D．BCDEFEF常对数组进行的两种基本操作是（C）。A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D=1\*GB3①）个字节；M的第8列和第5行共占（=2\*GB3②B）个字节。=1\*GB3①A．90 B．180 C．240 D．540=2\*GB3②A．108 B．114 C．54 D．60数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（C）。A．80 B．100 C．240 D．270数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）A．SA+141 B．SA+144 C．SA+222 D．SA+225数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为（A）A．SA+141 B．SA+180 C．SA+222 D．SA+225设有模式串A=”abefaba”，则其next数组中的值依次应为（C）。A．0111111 B．0111212 C．0111123 D．0111122设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C） A．O(n) B．O(log2n) C．O(1) D．O(n2)设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。 A．2k-1 B．2k C．2k-1 D．2k-1设用链表作为栈的存储结构，则退栈操作（B） A．必须判别栈是否满 B．必须判别栈是否空C．判别栈元素的类型 D．对栈不作任何操作设顺序循环队列Ｑ［0：M-1］的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（D）。A．R-F B．F-R C．(R-F+M)%M D．(F-R+M)%M在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为(B)。A．n B．n/2 C．(n+1)/2 D．(n-1)/2设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B）个空指针域。A．2m-1 B．2m C．2m+1 D．4m二叉树的第k层的结点数最多为（D）A．2k-1 B．2K+1 C．2K-1 D．2K-1广义表是线性表的推广，它们之间的区别在于（A）。A．能否使用子表 B.能否使用原子项 C.是否能为空 D.表的长度设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。A．9 B．10 C．11 D．12数据的最小单位是（B）。A．数据项 B．数据元素 C．数据类型 D．数据变量设某数据结构的二元组形式表示为A=（D，R），D={01，02，03，04，05，06，07，08，09}，R={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（B）A．线性结构 B．树型结构 C．物理结构 D．图型结构一棵有n个结点的树，在把它转换成对应的二叉树后，该二叉树根结点的左子树上共有（B）个结点。A．n-2 B．n-1 C．n+1 D．n+2设指针变量p指向单向链表中结点A，若删除单向链表中结点A，则需要修改指针的操作序列为（A）（q是指向该类结点的空指针）A．q=p->next;p->data=q->data;p->next=q->next;free(q);B．q=p->next;q->data=p->data;p->next=q->next;free(q);C．q=p->next;p->next=q->next;free(q);D．q=p->next;p->data=q->data;free(q);设有模式串A=”abaabcac”，则其next数组中的值依次应为（C）。A．0111111 B．0111212 C．01122312 D．01122122链栈和顺序栈相比，有一个比较明显的优点是B。A.插入操作更加方便 B.通常不会出现栈满的情况C.不会出现栈空的情况 D.删除操作更加方便对于一棵深度为4的三叉树，最多有（C）个结点。A．30 B．36 C．40 D．54设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，问A[3][3]存放在什么位置脚注（10）表示是十进制数。（C