数据结构基础知识题库

1、数据结构基础知识题库1. （）是性质相同的数据元素的集合，是数据的子集。 单选题A数据元素B数据对象(正确答案)C数据结构D数据项2. 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。 单选题A物理结构(正确答案)B逻辑结构C算法的具体实现D给相关变量分配存储单元3. 从n个数中选取最大元素（）。 单选题A基本操作是数据元素间的交换B算法的时间复杂度是O(n2)C算法的时间复杂度是O(n)(正确答案)D需要进行(n+1)次数据元素间的比较4. 数据的（）结构与所使用的计算机无关。 单选题A逻辑(正确答案)B物理C存储D逻辑与存储5. 数据的物理结构（）。 单选题A与数据的逻辑结构

2、无关B仅仅包括数据元素的表示C只包括数据元素间关系的表示D包括数据元素的表示和关系的表示(正确答案)6. 数据结构中，与所使用的计算机无关的是数据的（）结构。 单选题A物理B存储C逻辑与物理D逻辑(正确答案)7. 数据元素是数据的基本单位，它（）。 单选题A只能有一个数据项组成B至少有二个数据项组成C可以是一个数据项也可以由若干个数据项组成(正确答案)D至少有一个数据项为指针类型8. 算法的时间复杂度与（）有关。 单选题A所使用的计算机B计算机的操作系统C算法本身(正确答案)D数据结构9. 同一种逻辑结构（）。 单选题A只能有唯一的存储结构B可以有不同的存储结构(正确答案)C只能表示某一种数据

3、元素之间的关系D以上三种说法均不正确10. 线性结构中数据元素的位置之间存在（）的关系。 单选题A一对一(正确答案)B一对多C多对多D每一个元素都有一个直接前驱和一个直接后继11. 树形结构中数据元素的位置之间存在（）的关系。 单选题A一对一B一对多(正确答案)C多对多D每一个元素都有一个直接前驱和一个直接后继12. 图形结构中数据元素的位置之间存在（）的关系。 单选题A一对一B一对多C多对多(正确答案)D每一个元素都有一个直接前驱和一个直接后继13. 以下特征中，（）不是算法的特性。 单选题A有穷性B确定性C有效性D有0个或多个输出(正确答案)14. 某算法的时间复杂度为O（n）,表明该算法

4、的（） 单选题A.问题规模为nB.执行时间等于nC.执行的时间与n成正比(正确答案)D.问题规模与n成正比15. 以下算法的时间复杂度为（）。 void fun(int n) int j=0; for (i=1;i<=n;i+) j=j+i; 单选题A.O(n)(正确答案)B.O(n2)C.O(nlog2n)D.O(log2n)16. 以下算法的时间复杂度为（）。 void fun(int n) int sum=0; for ( int i=1;i<=n;i+)for ( int j=1;j<=n;j+) sum+=j*i; 单选题A.O(n)B.O(n2)(正确答案)C.O

5、(nlog2n)D.O(log2n)17. 线性表是有n个（）的有限序列。 单选题A.数据表B.字符C.数据元素(正确答案)D.数据项18. 线性表是一个（）。 单选题A.有限序列，可以为空(正确答案)B.有限序列，不可以为空C.无限序列，可以为空D.无限序列，不可以为空19. 以下（）是一个线性表。 单选题A.由n个实数组成的集合B.由100个字符组成的序列(正确答案)C.由所有整数组成的序列D.所有奇数组成的序列20. 在线性表中，除了开始元素外，每个元素（）。 单选题A.只有唯一的前驱元素(正确答案)B.只有唯一的后即元素字符C.有多个前驱元素D.有多个后继元素21. 顺序表的最大有优点

6、是()。 单选题A.存储密度大(正确答案)B.插入运算方便C.删除运算方便D.可以方便地用于各种逻辑的存储表示22. 对于顺序表，访问编号为i的元素的时间复杂度为（）。 单选题A.O(n)B.O(1)(正确答案)C.O(nlog2n)D.O(log2n)23. 对于顺序表，在编号为i处插入一个新元素的间复杂度为（）。 单选题A.O(n)(正确答案)B.O(1)C.O(nlog2n)D.O(log2n)24. 采用顺序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的方法），最坏的情况下要进行（）次元素间的比较。 单选题An+2Bn(正确答案)Cn-1Dn/225. 带头结点的单向链表的头指

7、针为head，该链表为空的判定条件是（）的值为真。 单选题Ahead=NULLBhead.getNext()=headChead.getNext()=NULL(正确答案)Dhead=head.getNext()26. 非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。 单选题Ap.getNext()=NULLBp=NULLCp.getNext()=head(正确答案)Dp=head27. 链表所具备的特点是（）。 单选题A可以随机访问任一结点B占用连续的存储空间C可以通过下标对链表进行直接访问D插入删除元素的操作不需要移动元素结点(正确答案)28. 设链表中的结点是N

8、ode类型的类，且有Node p；为了申请一个新结点，并由p指向该结点，可用以下Java语句（）。 单选题A.p=new Node();(正确答案)B.p=new Node(*);Cp=(NODE)malloc(sizeof(p);Dp=(NODE*)malloc(sizeof(p);29. 设顺序存储的线性表长度为n，对于插入操作，设插入位置是等概率的，则插入一个元素平均移动元素的次数为（）。 单选题An/2(正确答案)BnCn-1Dn-i+130. 设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为（）。 单选题A(n1)/2(正确答案)Bn

9、C2nDn-i31. 设顺序存储的线性表长度为n，要删除第i（0<=i<=n-1）个元素，按课本的算法，当i=（）时，移动元素的次数为3。 单选题A3Bn/2Cn-4(正确答案)D432. 设顺序存储的线性长度为n，要在第i（0<=i<=n）个元素之前插入一个新元素，按课本的算法当i= （）时，移动元素次数为2。 单选题An/2BnC1Dn-2(正确答案)33. 设有一个长度为n的顺序表，要删除第i(0<=i<=n-1)个元素，按照课本算法，需移动元素的个数为（）。 单选题An-i+1Bn-iCn-i-1(正确答案)Di34. 下述各线性结构中可以随机访问的

10、是（）。 单选题A.单向链表B.双向链表C.单向循环链表D.顺序表(正确答案)35. 线性表采用链式存储时，其地址（）。 单选题A一定是不连续的B必须是连续的C可以连续也可以不连续(正确答案)D部分地址必须是连续的36. 在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用的语句是（）。 单选题Ap=q.getNext();Bp.setNext(q);Cp.setNext(q.getNext();(正确答案)Dq.setNext(NULL);37. 在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 单选题Ap.setNe

11、xt(s);s.setNext(p.getNext();Bp,setNext(s.getNext();Cp=s.getNext();Ds.setNext(p.getNext();p.setNext(s);(正确答案)38. 按照教材算法，在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（ ）。 单选题A.21B.20(正确答案)C.19D.2539. 针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。 单选题A单链表B双链表C顺序表(正确答案)D单循环链表40. 假设在顺序表中，每一个数据元素所占的存储单元的数

12、目为4，且第一个数据元素的存储地址为100，则位序号是7的数据元素的存储地址是：（）。 单选题A106B107C124D128(正确答案)41. 队列的插入操作在（）进行。 单选题A队头B队尾(正确答案)C队头或队尾D在任意指定位置42. 队列的删除操作在（）进行。 单选题A队头(正确答案)B队尾C队头或队尾D在任意指定位置43. 栈的插入操作在（）进行。 单选题A栈顶(正确答案)B栈底C栈顶或栈底D在任意指定位置44. 一个队列的入队序列是2，4，6，8，则队列的输出序列是（）。 单选题A8，6，4，2B2，4，6，8(正确答案)C4，2，8，6D6，4，2，845. 一个队列的入队序列是5

13、，6，7，8，则队列的输出序列是（）。 单选题A.5 6 7 8(正确答案)B.8 7 6 5C.7 8 6 5D.可能有多种情况46. 一个栈的进栈序列是1，2，3，4，则不可能的出栈序列是（）（进出栈操作可以交替进行）。 单选题A3，2，4，1B1，4，2，3(正确答案)C4，3，2，1D3，2，1，447. 一个栈的进栈序列是5，6，7，8，则栈的不可能的出栈序列是（）（进出栈操作可以交替进行） 单选题A5，8，6，7(正确答案)B7，6，8，5C8，7，6，5C7，6，8，548. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能输出序列是（）（进栈出栈可以交替进行）。 单选题Adc

14、eab(正确答案)BedcbaCdecbaDabcde49. 以下说法不正确的是（）。 单选题A顺序栈中，栈满时再进行进栈操作称为“上溢”B顺序栈中，栈空时再作出栈栈操作称为“下溢”C顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满(正确答案)D顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空50. 以下说法不正确的是（）。 单选题A栈的特点是后进先出B队列的特点是先进先出C栈的删除操作在栈底进行，插入操作在栈顶进行(正确答案)D队列的插入操作在队尾进行，删除操作在队头进行51. 以下说法正确的是（）。 单选题A栈的特点是先进先出，队列的特点是先进后出B栈和

15、队列的特点都是先进后出C栈的特点是先进后出，队列的特点是先进先出D栈和队列的特点都是先进先出(正确答案)52. 以下说法正确的是（ ）。 单选题A栈的特点是先进先出，队列的特点是先进后出B栈和队列的特点都是先进后出C栈的特点是先进后出，队列的特点是先进先出D栈和队列的特点都是先进先出(正确答案)53. 元素2，4，6，8按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。 单选题A8，6，4，2B2，4，6，8C4，2，8，6D8，6，2，4(正确答案)54. 元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（）。 单选题A. 6 4 2B.6 2 4(正确答案)C.

16、4 2 6D.2 6 455. 栈的插入删除操作在（）进行。 单选题A栈底B任意位置C指定位置D栈顶(正确答案)56. 栈和队列的相同点是（）。 单选题A都是后进先出B都是后进后出C逻辑结构与线性表不同D逻辑结构与线性表相同，都是操作规则受到限制的线性表(正确答案)57. 从一个栈顶指针为top的链栈中插入一个由P指向的新结点时，则执行的操作是（）。 单选题Ap.setNext(top);top=p;(正确答案)Btop=p;p.setNext(top);Ctop.setNext(p);top=p;Dtop.setNext(p);p=top;58. 设top是一个链栈的栈顶指针，栈中每个结点由

17、一个数据域data和指针域next组成，设用x接收栈顶元素，则出栈操作为（）。 单选题Ax=top.getData();top=top.getNext();(正确答案)Btop=top.getNext();x=top.getData();Cx=top.getNext();top=top.getData();Dtop.setNext(top);x=top.getData();59. 设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针，要执行出队操作，用x保存出队元素的值，p为指向结点类型的指针，可执行如下操作：p=f

18、ront.next; x=p.data; 然后执行（）。 单选题Afront=p.next;BFront.next=p.next;(正确答案)Cfront=p;DFront.next=p;60. 设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，front和rear分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值)，则入队操作为（）。 单选题ARear.next=p;rear=p;(正确答案)BRear.next=p;p=rear;Cp=rear.next;rear=p;Drear=p;rear.next=p;A61. 在一个链队列中，假设f

19、和r分别为队头和队尾指针，则插入s所指结点的运算为（）。 单选题AfsetNext(s);f=s;Br.setNext（s）;r=s;(正确答案)CssetNext(r);r=s;Ds.setNext(f);f=s;62. 在一个链队列中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）。 单选题Ar=f.getNext();Br=r.getNext();Cf=r.getNext();Df=f.getNext();(正确答案)63. 在一个循环队列中，队列的空间大小为length, 设对头指针为front, 队尾指针为rear,按照教材采用减少一个存储元素的方法，以下那个能判断队列已

20、满。 （） 单选题A.(rear+1)%length=front;(正确答案)B.rear=front;C.rear%length=front;D.(rear-1)%length=front;64. 若一个栈用数组data1.n存储,初始栈顶指针top为n, 则如元素x进栈的正确操作是：（） 单选题A.top+;datatop=x;B.datatop=x;top+;C.top-;datatop=x;D.datatop=x;top-;(正确答案)65. 为解决计算机主机与打印机之间速度不匹配问题，通常设计打印机数据缓冲区，主机将输出的数据依次写入缓冲区，而打印机依次从该缓冲区中取出数据。该缓冲区

21、的逻辑结构应该是：（） 单选题A.栈B.队列(正确答案)C.树D.图66. 串方法concat(str)的功能是进行串（）。 单选题A比较B复制C赋值D连接(正确答案)67. 串函数s=“Hello”; s.indexOf(“e”,0)的值为（）。 单选题A1(正确答案)B0C“He”D“e”68. 空串的长度为（）。 单选题A0(正确答案)B1C2D369. 以下陈述中正确的是（）。 单选题A串是一种特殊的线性表(正确答案)B串的长度必须大于零C串中元素只能是字母D空串就是空白串70. 设有两个串p和q，其中q是p的子串，q在p中首次出现的位置的算法称为（）。 单选题A求子串B连接C匹配(正

22、确答案)D求串长71. 串是（）。 单选题A不少于一个字母的序列B任意个字母的序列C不少于一个字符的序列D有限个字符的序列(正确答案)72. 串的长度是指（）。 单选题A串中所含不同字母的个数B串中所含字符的个数(正确答案)C串中所含不同字符的个数D串中所含非空格字符的个数73. 若串S=“English”，其子串的个数是（）。 单选题A9B16C36D29(正确答案)74. 下面关于串的叙述中，不正确的是（）。 单选题A串是字符的有限序列B空串是由空格构成的串(正确答案)C模式匹配是串的一种重要运算D串即可以采用顺序存储，也可以采用链式存储75. 串与普通的线性表相比较，它的特殊性体现在（）

23、。 单选题A顺序的存储结构B链接的存储结构C数据元素是一个字符(正确答案)D数据元素可以任意76. 空串与空格串（）。 单选题A相同B不相同(正确答案)C可能相同D无法确定77. 两个字符串相等的条件是（）。 单选题A两串的长度相等B两串包含的字符相同C两串的长度相等，并且两串包含的字符相同D两串的长度相等，并且对应位置上的字符相同(正确答案)78. 在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（）存储比较合适。 单选题A链式(正确答案)B顺序C堆结构D无法确定79. 设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从0开始），

24、则矩阵中元素A85 在一维数组B中的下标是（）。 单选题A33B32C85D41(正确答案)80. 设有一个10阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为A00，数组b的下标从0开始），则矩阵元素A53对应一维数组b的数组元素是（）。 单选题Ab18(正确答案)Bb8Cb13Db1081. 设有一个12阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中（矩阵A的第一个元素为A00，数组b的下标从0开始），则矩阵A中第4行的元素在数组b中的下标i一定有（）。 单选题A7i10B11i15C10i14(正确答案)D

25、6i982. 设有一个15阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从0开始），则矩阵中元素a7,6在一维数组B中的下标是（ ）。 单选题A42(正确答案)B13C27D3483. 设有一个15阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为a1,1，数组b的下标从1开始），则数组元素b13对应A的矩阵元素是（）。 单选题Aa5,3(正确答案)Ba6,4Ca7,2Da6,884. 设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（矩阵A的第一个元素为a

26、1,1，数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（ ）。 单选题A41B32C18D38(正确答案)85. 设有一个20阶的对称矩阵A，采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a11，数组b的下标从1开始），则矩阵元素a8,5在一维数组b中的下标是（ ）。 单选题A30B28C40D33(正确答案)86. 在Java语言中，利用数组a存放字符串“Hello”，以下语句中正确的是（）。 单选题AChar a10= “Hello”;BChar a10; a=“Hello”;CChar a10= Hello;DChar a=H,e,l,

27、l,o;(正确答案)87. 对二叉排序树进行（ ）遍历，遍历所得到的序列是有序序列。 单选题A按层次B前序C中序(正确答案)D后序88. 深度为5的完全二叉树第5层上有4个结点，该树一共有（ ）个结点。 单选题A28B30C31D19(正确答案)89. 深度为5的完全二叉树共有20个结点，则第5层上有（ ）个结点(根所在结点为第一层)。 单选题A3B8C5(正确答案)D690. 一棵哈夫曼树共有n个非叶结点，则该树一共有（ ）个结点。 单选题A.2*n-1B.2*n+1(正确答案)C.2*nD.2*(n-1)91. 一棵哈夫曼树共有n个非叶结点，则该树有（ ）个叶结点。 单选题AnBn+1(正

28、确答案)Cn-1D2n92. 一棵哈夫曼树共有n个叶结点，则该树有（ ）个非叶结点。 单选题An-1(正确答案)BnCn+1D2n93. 一棵哈夫曼树有n个叶子结点（终端结点），该树总共有（ ）个结点。 单选题A2n-2B2n-1(正确答案)C2nD2n+294. 一棵哈夫曼树总共有23个结点，该树共有（ ）个叶结点（终端结点）。 单选题A10B13C11D12(正确答案)95. 一棵完全二叉树共有30个结点，则该树一共有（ ）层(根结点所在层为第一层)。 单选题A6B4C3D5(正确答案)96. 一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（ ）个结点。 单选题A30B20C21(

29、正确答案)D2397. 一棵有n个结点采用链式存储的二叉树，则该树共有（ ）个指针域为空。 单选题A2nB2n+1C2n+2Dn+1(正确答案)98. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。 单选题A2iB2i-1C2i+2D2i+1(正确答案)99. 任何一个无向连通图的最小生成树（ ）。 单选题A.至少有一棵(正确答案)B.只有一棵C.一定有多棵D.可能不存在100. 已知一个图的边数为m，则该图的所有顶点的度数之和为（ ）。 单选题A2m(正确答案)BmC2m+1Dm/2101. 已知一个图的所有顶点的度数之和为m，则m一定不可能是（ ）。 单选题A4B

30、8C12D9(正确答案)102. 以下说法不正确的是（ ）。 单选题A连通图G一定存在生成树B连通图G的生成树中一定包含G的所有顶点C连通图G的生成树中不一定包含G的所有边D连通图G的生成树可以是不连通的(正确答案)103. 以下说法正确的是（ ）。 单选题A连通图G的生成树中可以包含回路B连通图G的生成树可以是不连通的C连通图G的生成树一定是唯一的D连通图G的生成树一定是连通而不包含回路的(正确答案)104. 以下说法正确的是（ ）。 单选题A连通图G的生成树中可以包含回路B连通图G的生成树可以是不连通的C连通图G的生成树一定是唯一的D连通图G的生成树一定是连通而不包含回路的(正确答案)10

31、5. 以下说法正确的是（ ）。 单选题A连通图G的生成树中不一定包含G的所有顶点B连通图G的生成树中一定要包含G的所有边C连通图G的生成树一定是唯一的D连通图G一定存在生成树(正确答案)106. 以下说法正确的是（ ）。 单选题A连通图G的生成树中不一定包含G的所有顶点B连通图G的生成树中一定要包含G的所有边C连通图G的生成树一定是唯一的D连通图G一定存在生成树(正确答案)107. 在一个无向图中，所有顶点的度数之和等于边数的（ ）倍。 单选题A3B2.5C1.5D2(正确答案)108. 对n个元素进行冒泡排序，要求按升序排列，程序中设定某一趟冒泡没有出现元素交换，就结束排序过程。对某n个元素

32、的排序共进行了3n-6次元素间的比较就完成了排序，则（ ）。 单选题A.原序列是升序排列B.原序列是降序排列C.对序列只进行了2趟冒泡D.对序列只进行了3趟冒泡(正确答案)109. 对n个元素进行冒泡排序，通常要进行n-1趟冒泡，在第j趟冒泡中共要进行（ ）次元素间的比较。 单选题AjBj-1Cn-j(正确答案)Dn-j-1110. 对n个元素进行冒泡排序若某趟冒泡中只进行了（ ）次元素间的交换，则表明序列已经排好序。 单选题A1B2C0(正确答案)Dn-1111. 排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ ）排序。 单选题A归并B插入C选择(正确答案)D快速112. 排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子