数据结构考试复习题库.doc

《数据结构考试复习题库.doc》由会员分享，可在线阅读，更多相关《数据结构考试复习题库.doc（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单项选择题 1. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 A.64 B.63 C.63.5 D.7【答案】A2. 线性表是具有n个（ ）的有限序列（n0）。 A.表元素 B.字符 C.数据元素 D.数据项【答案】C3. 下列哪种排序方法在最坏的情况下的时间复杂度是O（n*log2n）（ ）。A .直接插入排序 B. 堆排序 C. 简单选择排序 D. 快速排序【答案】B4. 数组A56的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A44的地址为（ ）。 A.1140 B.1145 C.1120 D.112

2、5【答案】A5. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（ ）。 A.x=HS;HS=HS-next;B.x=HS-data;C.HS=HS-next;x=HS-data;D.x=HS-data;HS=HS-next;【答案】D6. 已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为（ ）。 A.(v0，v1，v2，v5，v4，v3) B.(v0，v1，v2，v3，v4，v5) C.(v0，v1，v5，v2，v3，v4) D.(v0，v1，v4，v5，v2，v3)【答案】A7

3、. 如下陈述中正确的是（ ）。 A串是一种特殊的线性表 B串的长度必须大于零 C串中元素只能是字母 D空串就是空白串【答案】A8. 在一个长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是（ ）。An/2 B（n-1）/2 Cn*(n-1)/2 D (n+1)/2【答案】A9. 数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。A.向量 B.数组 C.集合 D.索引【答案】D10. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（ ）。 Ae B2e Cn2e Dn22e【答案】D11. 引入二叉线索树的目的是（ ）。 A.加快查找结点的前驱或后继的速度 B.

4、为了能在二叉树中方便的进行插入与删除 C.为了能方便的找到双亲D.使二叉树的遍历结果惟一【答案】A12. 对一棵m阶B-树，下列选项错误的是（）。 A.每个结点最多有m棵子树 B.除根结点和叶结点外，每个结点至少有m/2棵子树 C.有k棵子树的结点必有k个关键字（knext=p-next;p-next=s;B.p-next=s-next;s-next=p;C. q-next=s;s-next=p;D.p-next=s;s-next=q;【答案】C22. 对关键字集合K=53,30,37,12,45,24,96,从一棵空二叉树开始逐个插入关键字，建立二叉排序树，若希望得到的二叉排序树的高度最小，

5、应选用下列输入序列（）。A. 45，24，53，12，37，96，30 B.37，24，12，30，53，45，96C. 12，24，30，37，45，53，96 D.30，24，12，37，45，96，53【答案】B23. 有8个结点的无向图最多有（ ）条边。 A14 B. 28 C. 56 D. 112【答案】B24. 在一非空二叉树的中序遍历序列中,根结点的右边（ ）。A.只有右子树上的所有结点 B. 只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点【答案】A25. 稀疏矩阵一般的压缩存储有两种，即（）。A一维数组和二维数组 B一维数组和三元组C二维数组和十字

6、链表 D三元组和十字链表【答案】D26. 含n个关键字的二叉排序树的平均查找长度主要取决于（）。A.关键字的个数B.树的形态C.关键字的取值范围D.关键字的数据类型【答案】B27. 对表（21，36，40，44，58，64，79，73）进行排序，使用下列（ ）方法最好。A简单选择排序 B堆排序 C冒泡排序 D归并排序【答案】C28. 将一棵有100个结点的完全二叉树从根的这一层开始，每一层从左到右依次对结点进行编号，根结点编号为，则编号为49的结点的左孩子的编号为（）。98 99 50 48【答案】A29. 在一棵6阶的B-树中,除根结点外,每个结点中的至少有（）个关键字。 A)5 B)4 C

7、)3 D)2【答案】D30. 具有15个结点的二叉树的最小深度是（）。A. 4 B. 5 C. 3 D. 6【答案】A31. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（ ）。 A.HS-next=s; B.s-next=HS-next;HS-next=s;C.s-next=HS;HS=s;D.s-next=HS;HS=HS-next;【答案】B32. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AN1 B.N1+N2 C.N3 D.N2+N3【答案】D33. 二维数组A45按行优先顺序存储，若

8、每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为（ ）。 A.1012 B.1017 C.1034D.1036【答案】C34. 在循环双链表的p所指接点之前插入s所指接点的操作是（ ）。 A.p- prior =s;s- next=p;p- prior-neft=s;s- prior =p- prior;B. p- prior =s;p- prior - next =s;s- next =p;s- prior =p- prior;C.s- next =p;s- prior =p- prior;p- prior =s;p- prior - next =

9、s;D.s- next =p;s- prior =p- prior;p- prior - next =s;p- prior =s;【答案】D35. 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现编号。A.先序 B.中序 C.后序 D.从根开始的层次遍历【答案】C36. 在有向图的顶点的拓扑序列中，如果Vi在Vj之前，则下列情况一定不会出现的是（ ）。A.图中有弧 B.图中Vi到Vj有一条路径 C. 图中没有弧 D.图中有弧【答案】D37. 若在9阶B-树中插入关键字引起结点分裂，则该结

10、点在插入前含有的关键字个数为（ ）。A. 4 B. 5 C. 8 D. 9【答案】C38. 若已知一个栈的入栈序列是1，2，3，.n，其输出序列为p1,p2,p3,.,pn,若p1=n,则pi为（ ）。 A.i B.n+i C.n-i+1 D.不确定【答案】C39. 对稀疏矩阵进行压缩存储是为了（）。A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度【答案】C40. 有向图中一个顶点的度是该顶点的（）。 A.入度 B. 出度 C. 入度与出度之和 D. （入度+出度）/2【答案】C41. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中

11、的叶子结点数为（ ）。A.5 B.8 C.11D.18【答案】C42. 适于对动态查找表进行高效率查找的组织结构是（ ）A有序表 B分块有序表 C三叉排序树 D线性链表【答案】C43. 在一棵7阶B-树中,除根结点外,每个结点中最多有（）个关键字。A. 6 B.5 C.4 D.3【答案】A44. 下列排序方法中，要求附加的内存容量最大的是（）。A冒泡排序 B快速排序 C堆排序 D归并排序【答案】D45. 具有9个叶结点的二叉树中有（ ）个度为2的结点。A.8 B.9 C.10 D.11【答案】A46. 在数据结构中，从逻辑上可以把数据结构分成（ ）。A.动态结构和静态结构 B.紧凑结构和非紧凑

12、结构 C.线性结构和非线性结构 D.内部结构和外部结构【答案】C47. 下列排序算法中，（）算法可能会出现下面情况：初始数据有序，花费时间反而最多。堆排序 冒泡排序 快速排序 hell排序【答案】C48. 由3 个结点可以构造出（ ）种不同的二叉树。A.2 B.3 C.4 D.5【答案】D49. 存储无向图的邻接矩阵一定是一个（）。A. 上三角矩阵 B.稀疏矩阵 C. 对称矩阵 D. 对角矩阵【答案】C50. 具有5个顶点的无向完全图有（ ）条边。A.6. B.10. C.16 D.20【答案】B51. 树的先根序列等同于与该树对应的二叉树的（ ）。A.先序序列 B.中序序列C.后序序列D.层

13、序序列【答案】A52. 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为（ ）。 A4 B5 C6 D7【答案】C53. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。 AO(n) BO(e) CO(n+e) DO(n*e)【答案】C54. 算法分析的目的是（ ）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性【答案】C55. 有8个结点的无向连通图最少有（ ）条边。 A5 B. 6 C. 7 D. 8【答案】C56. 研究数据结

14、构就是研究（ ）。A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构和存储结构以及其数据在运算上的实现【答案】D57. 非线性结构是数据元素之间存在一种（ ）。A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系【答案】B58. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A.空或只有一个结点 B.高度等于其结点数C.任一结点无左孩子 D.任一结点无右孩子【答案】B59. 高度为5的完全二叉树中含有的结点数至少为（ ）。A.16 B.17 C.31D.32【答案】A60. 由同一关键字集合构造的各棵二叉排序树 ( )A.

15、 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同D. 其形态均相同，平均查找长度也都相同【答案】B61. 算法分析的两个主要方面是（ ）。 A.正确性和简单性 B.可读性和文档性 C.数据复杂性和程序复杂性 D.时间复杂度和空间复杂度【答案】D62. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（ ）。A. (19，23，56，34，78，67，88，92) B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88

16、，92) D. (19，23，67，56，34，78，92，88)【答案】D63. （）不是哈希查找中的冲突处理方法。A链地址法 B再哈希法 C除留余数法 D随机探测法【答案】C64. 在一个顺序表中，若表的第一个元素的存储地址是210，每一个元素的长度为3，则第5个元素的存储地址是（）。 A219 B222 C225 D228【答案】B65. 在单链表中删除结点的时间复杂度为（ ）。 A.O(1) B.O(n2 ) C.O(n) D(logn)【答案】C66. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一个元素，其存储地址为1，每个元素占1个地址空间，则a8,

17、4的地址为（ ）。A.15 B.32 C.34 D.33【答案】B67. 线性表采用链式存储时，结点的存储地址（ ）。 A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续【答案】B68. 下列关键字序列中，构成大根堆的是（ ）。A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，3C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，3【答案】D69. 在连通图的广度优先遍历算法中，需要借助的辅助数据结构是（ ）。A队列 B栈 C线性表D有序表【答案】A70. 引起循环队列队头位置发生变化的操作是（ ）。A. 出队 B. 入队 C. 取队头元

18、素 D. 取队尾元素【答案】A71. 评价一个算法时间性能的主要标准是（ ）。 A.算法易于调试 B. 算法易于理解 C.算法的稳定性和正确性 D.算法的时间复杂度【答案】D72. 在长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是（） 。A.（n-1）/2 B.n/2 C.n*(n-1)/2 D.(n+1)/2【答案】B73. 已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为（ ）。 A2*(n-1)+1*d B.2*(n-1)*d C.2*(n-1)-1*d D.(n+1)*d【答案】A74. 在一个长度为n的顺序存储线性表中，删除

19、第i个元素(0in-1)时，需要从后向前依次前移（ ）个元素。A.n-i B.n-i+1 C. n-i-1 D.i【答案】A75. 在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是（ ） 。A.（n-1）/2 B.n/2 C.n*(n-1)/2 D.(n+1)/2【答案】A76. 如果T1是由有序树T转换而来的二叉树,那么T中结点的前序就是T1中结点的（ ）。A.前序 B. 中序 C.后序 D.层次序【答案】A77. 查找哈希表，不会产生冲突的哈希函数是（ ）。 A链地址法 B直接地址法 C除留余数法 D随机探测法【答案】B78. 用某种排序方法对关键字序列（25，84，

20、21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）。 A选择排序 B希尔排序 C归并排序 D快速排序【答案】D79. 非空的循环单链表head的尾结点p满足（ ）。AP-next=NULL Bp=NULL CP-next=head DP=head【答案】C80. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个结点。 A.n B.n/2 C.(

21、n-1)/2 D.(n+1)/2【答案】D81. 在有向图的顶点的拓扑序列中，如果Vi在Vj之前，则下列情况一定不会出现的是（ ）。A. 图中有弧 B.图中Vi到Vj有一条路径C. 图中没有弧 D.图中有弧【答案】D82. 非空的循环单链表head的尾结点p满足（）。AP-next=NULL Bp=NULL CP-next=head DP=head【答案】C83. 在一个长度为n的顺序存储线性表中，向第i个元素(1in)之前插入一个新元素时，需要从后向前依次后移（ ）个元素。 A.n-i B.n-i+1 C.n-i-1 D.i【答案】B84. 下列所示各图中是中序线索化二叉树的是（ ）。【答案

22、】A85. 下列程序段的时间复杂度为（ ）。 s=0； for(i=1；in；i+) for(j=1；jnext=s;f=s; B.r-next=s;r=s;C.s-next=r;r=s; D.s-next=f;f=s;【答案】B95. 按序列26，38，54，9，47，13，20构造一棵二叉排序树，其深度为（ ）。 3456【答案】B96. 数据结构是一门研究非数值对象以及它们之间的（ ）的学科。 A.结构 B.关系 C.运算 D.算法【答案】B97. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。 A.O(1) B.O(n) C.O(n2) D.O(nlog

23、2n)【答案】B98. 下列排序方法中，稳定的是（ ）。A归并排序 B快速排序 C堆排序 D希尔排序【答案】A99. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（ ）。 A.有向完全图 B.连通图 C.强连通图 D.有向无环图【答案】D100. 组成数据的基本单位是（ ）。 A. 数据项 B. 数据类型 C.数据元素 D.数据变量【答案】C101. 循环队列用数组AM存放元素，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 Arear-front+1 Brear-front-1 Crear-front D(rear-front+M) % M【答案】D

24、102. n个结点的完全有向图含有边的数目（ ）。A.n*n B.n（n+1） C.n/2 D.n*（n-1）【答案】D103. 任何一个无向连通图的最小生成树（ ）。A.只有一棵 B.有一棵或多棵C.一定有多棵 D.可能不存在【答案】B104. 下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（）。A.分块查找 B.顺序查找 C.二分查找 D.散列查找【答案】D105. 在以下排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。A.冒泡排序 B.简单选择排序 C.直接插入排序 D.快速排序【答案】B106. 链表不具有的特点是（ ）。A.可随机访问任一元素B.插入删

25、除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比【答案】A107. 有40个结点的完全二叉树存储在数组1.40中，数组中第一个叶子结点是（ ）。A19 B20 C21 D22【答案】C108. 由同一关键字集合构造的各棵二叉排序树（ ）。A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同 D. 其形态均相同，平均查找长度也都相同【答案】B109. 对于一个具有5个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（ ）。A.10 B.20 C.16 D.25【答案】D110. 用邻接表表示图

26、进行深度优先遍历时，通常是采用（ ）来实现算法的。 A栈 B. 队列 C. 树 D. 图【答案】A111. 在有n个叶子结点的哈夫曼树中，其结点总数为（）。不确定 2n 2n+1 2n-1【答案】D112. 对于一个头指针为H的带头结点的单链表，判定该表为空表的条件是（）。A. H=NULL BH!=NULL C.Hnext =H DHnext=NULL【答案】D113. 任何一个无向连通图的最小生成树（）。.只有一棵 .有一棵或多棵 .一定有多棵 .可能不存在【答案】B114. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）。 A.访问第i个元素的前驱（1next=NULL

27、B. p=NULLC. p-next=head D.p=head【答案】C120. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D.以上都不对【答案】A121. 不带权的无向图的邻接矩阵（）。 A.不一定是对称矩阵 B. 是对角线元素非零的对称矩阵 C. 是上三角矩阵 D.是对角线元素为零的对称矩阵【答案】D122. 数据结构是一门研究计算机中（ ）对象及其关系的学科。 A.数值运算 B.非数值运算 C.集合 D.非集合【答案】B123. 如图所示有向图的一个拓扑序列是（ ）。 A.ABCDEF B.FCBEAD C.

28、FEDCBA D.DAEBCF【答案】B124. 已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为（ ） 。 A. 1B.2C.3D.4【答案】B125. 假设以带行表的三元组表表示稀疏矩阵，则和下列行表02335 对应的稀疏矩阵是（ ）。 【答案】A126. 用邻接表表示图进行广度优先遍历时，通常是采用（ ）来实现算法的。 A栈 B. 队列 C. 树 D. 图【答案】B127. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。A. e B.2e C. n2-e D.n2-2e【答案】D128

29、. 在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时（ ）。 A.r=f-next; B.r=r-next;C.f=f-next; D.f=r-next;【答案】C129. 一个n阶对称矩阵，如果以行或列为主序放入内存，则容量为（ ）。 A.n*n B.n*/2 C. (n+1)*(n+1)/2 D.n*(n+1)/2【答案】D130. 用折半查找法查找表（a1,a2,a11）,需要比较4次才能找到的元素是（）。A.a1和a8 B.a4和a7 C.a2和a8 D.a4和a10【答案】C131. 栈S最多能容纳4个元素,现有6个元素按a,b,c,d,e,f的顺序进栈,下面序列

30、（）是可能的出栈序列。Aedcbaf B.bcefad C.cbedaf D.adfebc【答案】C132. 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）。 AO（1） BO（n） CO（m） DO（m+n）【答案】C133. 以数组Q0.m1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）。A.rearqulen B.rearqulenm C.mqulen D.1（rearmqulen）% m【答案】B134. 评价一个算法时间性能的主要标准是（）。A.算法易于调试 B. 算法

31、易于理解 C.算法的稳定性和正确性 D.算法的时间复杂度【答案】D135. 由两个栈共享一个向量空间的好处是（ ）。 A减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率 C减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发生的机率【答案】B136. 具有7个顶点的无向图至少应有（ ）条边才能确保是一个连通图。A.5 B.6 C.7 D.8【答案】B137. 树最适合用来表示（ ）。A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据【答案】C138. 栈结构通常采用的两种存储结构是（ ）。A. 顺序存储结构和链表存储结构 B.散列方式和索引方式C.链表存储结构和数组 D.线性存储结构和非线性存储结构【答案】A139. 常对数组进行的两种基本操作是（ ）。 A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引【答案】C140. 数据结构中,与所使用的计算机无关的是数据的（） 结构。 A.顺序B.物理C.逻辑D.物理和存储【答案】C141. 可用带表头结点的链表来表示表，也可用不带表头结点的链表来表示表，前者的主要好处