判断题1.数据的逻辑结构与数据元素本身的容和形式无关。

（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（√）3.数据元素是数据的最小单位。

（√）4.数据的逻辑结构和数据的存储结构是相同的。

（×）5.程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。

（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。

（√）7.数据的存储结构是数据的逻辑结构的存储映像。

（×）8.数据的物理结构是指数据在计算机实际的存储形式。

（√）9.数据的逻辑结构是依赖于计算机的。

（×）10.算法是对解题方法和的描述步骤。

（√）填空题：1.数据有逻辑结构和存储结构两种结构。

2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。

3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

4.树形结构和图形结构合称为非线性结构。

5.在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。

6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。

7.数据的存储结构又叫物理结构。

8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。

9.线性结构中的元素之间存在一对一的关系。

10.树形结构中的元素之间存在一对多的关系。

11.图形结构的元素之间存在多对多的关系。

12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。

13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的有限集合。

14.算法是一个有穷指令的集合。

15.算法效率的度量可以分为事先估算和事后统计法。

16.一个算法的时间复杂性是算法输入规模的函数。

17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。

18.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n ）。

若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 ___O（n*n）_______ 。

数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。

19.串的两种最基本的存储方式是顺序存储方式链式存储方式。

20.两个串相等的充分必要条件是、长度相等对应位置的字符相同。

21.空串是零个字符，其长度等于零。

22.空格串是由一个或多个空格字符组成的串，其长度等于其包含的空格个数。

23.设s=”I□AM□A□TEACHER”(□表示空格)，其长度是14。

24.已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是Loc(A[0][0])，则A[i][j]的地址是LOC (A[0][0])+(n*i+j)*k 。

25.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是200+（12*10+6）= 326 。

26.二维数组A[10，…，20][5，…，10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[8][9]的地址是_1000+((18-10)*6 +(9-5))*4 = 1208。

通常从四个方面评价算法的质量：正确性、易读性、健壮性和高效率。

27.中序遍历二叉排序树得到的序列是有序序列（填有序或无序）。

28.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中共有 2 N0+ N1个空指针域。

29.假设为循环队列分配的向量空间为Q[20]（下标从0开始），若队列的长度和队头指针值分别为13和17，则当前队尾指针的值为10。

30.设一棵完全二叉树中有500个结点，则该二叉树的深度为9；若用二叉链表作为该完全二叉树的存储结构，则共有501 个空指针域。

31.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的有限集合。

32.数据有逻辑结构和存储两种结构。

33.串的两种最基本的存储方式是顺序存储和存储。

34.若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O(n2)。

35.数据结构主要研究数据的逻辑结构、存储结构和算法3个方面的容。

36.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。

37.数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。

选择题：1.数据结构通常是研究数据的（A）及它们之间的相互关系。

A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑2.在逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．部结构和外部结构3.数据在计算机中存储器表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。

A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构4.非线性结构中的每个结点（D）。

A．无直接前趋结点B．无直接后继结点C．只有一个直接前趋和一个直接后继结点D．可能有多个直接前趋和多个直接后继结点5.链式存储结构所占存储空间（A）。

A．分两部分，一部分存储结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点的值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点的值，另一部分存放结点所占单元数6.算法的计算量大小称为算法的（C）。

A．现实性B．难度C．时间复杂性D．效率7.数据的基本单位是（B）。

A．数据结构B．数据元素C．数据项D．文件8.每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里。

这种存储结构称为（A）结构。

A．顺序存储B．链式存储C．索引存储D．散列存储9.每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）存储方式。

A．顺序B．链式C．索引D．散列10.以下任何两个结点之间都没有逻辑关系的是（D）。

A．图形结构B．线性结构C．树形结构D．集合11.在数据结构中，与所使用的计算机无关的是（C）。

A．物理结构B．存储结构C．逻辑结构D．逻辑和存储结构12.下列4种基本逻辑结构中，数据元素之间关系最弱的是（A）。

A．集合B．线性结构C．树形结构D．图形结构13.与数据元素本身的形式、容、相对位置、个数无关的是数据的（A）。

A．逻辑结构B．存储结构C．逻辑实现D．存储实现14.每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点位置的表，该存储方式是（C）存储方式。

A．顺序B．链式C．索引D．散列15.算法能正确的实现预定功能的特性称为算法的（A）。

A．正确性B．易读性C．健壮性D．高效性16.算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。

A．正确性B．易读性C．健壮性D．高效性17.下列时间复杂度中最坏的是（D）。

A．O(1) B．O(n) C．O(log2n) D．O(n2)18.下列算法的时间复杂度是（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)19.算法分析的两个主要方面是（A）。

A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性20.计算机算法必须具备输入、输出和（C）。

A．计算方法B．排序方法C．解决问题的有限运算步骤D．程序设计方法21.如下图所示的4棵二叉树，（C）不是完全二叉树。

22.如下图所示的4棵二叉树，（B）是平衡二叉树。

23.在线索化二叉树中，t所指结点没有左子树的充要条件是（）。

A．B．C．D．24.二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法（B）。

A．正确B．错误C．不确定D．不存在25.二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法（A）。

A．正确B．错误C．不确定D．不存在26.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法（A）。

A．正确B．错误C．不确定D．不存在27.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（B）。

A．2h B．2h-1C．2h+1 D．h+128.如右图所示二叉树的中序遍历序列是（B）。

A．abcdgef B．dfebagcC．dbaefcg D．defbagc29.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是（A）。

A．cedba B．cdbae C．cabed D．cabde 30.设a和b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（D）。

A．a是b的左孩子B．b是a的右孩子C．a是b左子树上结点或b是a右子树上结点D．以上三项均可31.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（C）个。

A． 45 B．15 C．16 D．3132.某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历序列是（A）。

A．gdbehfca B．abcdefgh C．gdbaefch D．ghbcdefa 33.按照二叉树的定义，具有3个结点的二叉树有（D）种。

A．2 B．3 C．4 D．534.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的遍历策略分为先序、中序和后序遍历。

这里把由树转化得到的二叉树叫做这棵树对应的二叉树。

以下结论（）是正确的。

A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同C．树的先根遍历序列与其对应的二叉树的中序遍历序列相同D．以上都不对35.空串与空格串是相同的，这种说法（B）。

A．正确B．错误C．依据情况而定D．不规36.串是一种特殊的线性表，其特殊性体现在（D）。

A．可以顺序存储B．数据元素是一个字符C．可以存储D．数据元素可以是多个字符37.设有两个串p和q，求q在p中首次出现的位置的运算称做（B）。

A．连接B．模式匹配C．求子串D．求串长38.设串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）。