数据结构测试题.docx

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

1、数据结构测试题1. 2019-06 链表不具有的特点是() A.插入删除不需要移动元素B.不必事先估计存储空间C.所需空间与线性表长度成正比D.可随机访问任一元素(正确答案)2. 2015-13 链表不具备的特点是( )。 A.可随机访问任何一个元素(正确答案)B.插入、删除操作不需要移动元素C.无需事物估计存储空间大小D.所需存储空间与存储元素个数成正比3. 2015-14 线性表若采用链表存储结构，要求内存中可用存储单元地址（）。A. 必须连续B. 部分地址必须连续C. 一定不连续D. 连续不连续均可(正确答案)4. 2014-10 链表不具有的特点是( )。 A.不必事物估计存储空间B.

2、可随机访问任一元素(正确答案)C.插入删除不需要移动元素D.所需空间与线性表长度成正比5. 2011-13 在含有n个元素的双向链表中查询是否存在关键字为k的元素，最坏情况下运行的时间复杂度是( )。 A. O(1 )B. O( log n )C. O( n )(正确答案)D. O( n log n )6. 2010-16 双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均非空。现要求删除结点p，则下面语句序列中错误的是( )。 A. p-rlink-llink = p-rlink;p-llink-rlink = p-llink;

3、 delete p;(正确答案)B. p-llink-rlink = p-rlink;p-rlink-llink = p-llink; delete p;C. p-rlink-llink = p-llink;p-rlink-llink-rlink = p-rlink; delete p;D. p-llink-rlink = p-rlink;p-llink-rlink-llink = p-llink; delete p;7. 2018-15 下图中所使用的数据结构是（）。单选题 A.哈希表B.栈(正确答案)C.队列D. 二叉树8. 2013-07 下图中所使用的数据结构是（）。单选题 A.哈希表

4、B.栈(正确答案)C.队列D. 二叉树9. 2012-02 ( )是一种先进先出的线性表。 A栈B队列(正确答案)C哈希表(散列表)D二叉树10. 2011-11 广度优先搜索时，需要用到的数据结构是( )。 A链表B队列(正确答案)C栈D散列表11. 2008-11 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为( )的数据结构。 A. 队列B. 多维数组C. 线性表D. 栈(正确答案)12. 2017-13 向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行( )。 A. hs-next=s;B.s-next=hs;hs=s;(正确答案)C.s-next=hs-n

5、ext;hs-next=s;D.s-next=hs;hs=hs-next;13. 2017-16 对于入栈顺序为a, b, c, d, e, f, g的序列，下列()不可能是合法的出栈序列。 A. a,b,c,d,e,f,gB. a,d,c,b,e,g,fC. a,d,b,c,g,f,e(正确答案)D.g,f,e,d,c,b,a14. 2015-15 今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈， 进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为 A.fB.c(正确答案)C.aD.b15. 2012-12 如果一个栈初始时为空，且当前

6、栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是( )。 Aa, d, c, bBb, a, c, dCa, c, b, dDd, a, b, c(正确答案)16. 2012-18 在程序运行过程中，如果递归调用的层数过多，会因为（）引发错误。A. 系统分配的栈空间溢出(正确答案)B. 系统分配的堆空间溢出C. 系统分配的队列空间溢出D. 系统分配的链表空间溢出17. 2010-15 元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的不可能是( )。 A. R1B. R2(正确答案)C. R4D. R

7、518. 2009-12 有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ A.EDCFABB.DECABFC.CDFEBA(正确答案)D. BCDAEF19. 2008-07 设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是( )。 A. 6B. 5C. 4(正确答案)D. 320. 2007-16 地面上有标号为A、B、C的3根细柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，将A 柱上的部分盘子经过B 柱移入C 柱，也可以在B

8、柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C柱上，从下到上的盘子的编号为( )。 A. 2 4 3 6 5 7B. 2 4 1 2 5 7C. 2 4 3 1 7 6D. 2 4 3 6 7 5(正确答案)21. 2006-13 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为( )。 A. 1, 2, 3, 4, 5B. 1, 2, 4, 5, 7C. 1, 4, 3, 7

9、, 6(正确答案)D. 1, 4, 3, 7, 222. 2006-19 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有( )。 A. a, b, c, e, dB. b, c, a, e, dC. a, e, c, b, d(正确答案)D. d, c, e, b, a23. 2017-14 若串S = “copyright”，其子串的个数是( )。 A. 72B. 45C. 46(正确答案)D. 3624. 2016-10 以下关于字符串的判定语句中正确的是( )。 A. 字符串是一种特殊的线性表(正确答案)B. 串的长度必须大于零C. 字符串不可

10、以用数组来表示D. 空格字符组成的串就是空串25. 2012-19 原字符串中任意一段连续的字符组成的新字符串称为子串。则字符串“AAABBBCCC”共有（）个不同的非空子串。A. 3B. 12C. 36(正确答案)D. 4526. 2008-09 设字符串S=”Olympic”，S的非字串的数目是（）。A28(正确答案)B29C16D17树和二叉树27. 2018-07 根节点深度为 0，一棵深度为 h 的满 k(k1)叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k个子结点的树，共有( )个结点。 A.(正确答案)(kh+1-1)/(k-1)B.kh-1C.khD.(kh-1)

11、/ (k - 1)28. 2008-18 设T是一棵有n个顶点的树，下列说法不正确的是（）。 A. T有n条边(正确答案)B. T是连通的C. T是无环的D. T有n-1条边29. 2019-08 一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+1处)，则该数组的最大下标至少为()。 A.6B.10C.15(正确答案)D.1230. 2016-11 一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为1，若某结点的下标为i，则其左孩子位

12、于下标2i处、右孩子位于下标2i+1处)，则该数组的最大下标至少为()。 A. 6B. 10C. 15(正确答案)D. 1231. 2015-17 如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( )。 A.5B.6(正确答案)C.7D.832. 2014- 一棵具有5层的满二叉树中结点数为( )。 A.31(正确答案)B.32C.33D.1633. 2013-09 已知一棵二叉树有 10 个节点，则其中至多有( )个节点有 2 个子节点。 A. 4(正确答案)B. 5C. 6D. 734. 2011-07 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是(

13、)。 A10B11C12(正确答案)D1335. 2010-19 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在的话，应当存放在数组的( )号位置。 A. 2kB. 2k+1C. k/2下取整(正确答案)D. (k+1)/2下取整36. 2010-05 如果树根算第1层，那么一棵n层的二叉树最多有( )个结点。 A. 2n-1(正确答案)B. 2nC. 2n+1D. 2n+137. 2009-14 一个包含n个分支结点(非叶结点)的非空二叉树，它的叶结点数目最多为( )。 A 2n

14、+ 1B 2n-1C n-1D n+1(正确答案)38. 2008-05 完全二叉树共有2N-1个结点，则它的叶节点数是( )。 A. N-1B. N(正确答案)C. 2ND. 2N-139. 2006-14 高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有2381个结点，则该树的树高为( )。 A. 10B. 11(正确答案)C. 12D. 1340. 2019-14 假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为(

15、)。 A.ABCDEFGHIJB.ABDEGHJCFI(正确答案)C.ABDEGJHCFID.ABDEGHJFIC41. 2015-16 前序遍历序列与中序遍历序列相同的二叉树为( )。 A.根结点无左子树B.根结点无右子树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树(正确答案)42. 2013-11 二叉树的（）第一个访问的节点是根节点。 A. 先序遍历(正确答案)B. 中序遍历C. 后序遍历D. 以上都是43. 2012-06 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是( )。 AABCBCBACACB(正确答案)

16、DBAC44. 2010-17 一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是( )。 A. 2(正确答案)B. 3C. 4D. 545. 2008-13二叉树T，已知其先根遍历是1 2 4 3 5 7 6(数字为结点的编号，以下同)，中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是( )。 A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1(正确答案)C. 7 4 2 5 6 3 1D. 4 2 7 6 5 3 146. 2007-20 已知7个结点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的

17、编号，以下同)，中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是( ) A. 4 6 5 2 7 3 1(正确答案)B. 4 6 5 2 1 3 7C. 4 2 3 1 5 4 7D. 4 6 5 3 1 7 247. 2006-20 已知6 个结点的二叉树的先根遍历是1 2 3 4 5 6(数字为结点的编号，以下同)，后根遍历是3 2 5 6 4 1，则该二叉树的可能的中根遍历是( ) A. 3 2 1 4 6 5B. 3 2 1 5 4 6(正确答案)C. 2 1 3 5 4 6D. 2 3 1 4 6 548. 2017-12 表达式a (b + c) d的后缀形式是()。

18、A. abcd+B. abc+d(正确答案)C. abc+dD. b+cad49. 2010-09 前缀表达式“+ 3 2 + 5 12”的值是( )。 A. 23B. 25C. 37(正确答案)D. 6550. 2009-13 表达式a(b+c)-d的后缀表达式是： A. abcd+-B. abc+d-(正确答案)C. abc+d-D. -+abcd图51. 2018-11 由4个没有区别的点构成的简单无向连通图的个数是（）。 A. 6(正确答案)B. 7C. 8D. 952. 2017-10 设G是有n个结点、m条边(n m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。 A.m

19、n+1(正确答案)B. m-nC. m+n+1D.nm+153. 2016-15 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有()个顶点。 A.10B.12C.8D.16(正确答案)54. 2016-18 Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他 们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代 表不是朋友。这个社交网站的规则是：如果某人 A 向他(她)的朋友 B 分 享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那 么他(她)的所有朋友都可以看见这个评论以及被评论的照片，但是不能对 该照片进

20、行评论(除非 A 也向他(她)分享了该照片)。现在 Lucia 已经上 传了一张照片，但是她不想让 Jacob 看见这张照片，那么她可以向以下朋友( )分享该照片。单选题 A. Dana, Michael, Eve(正确答案)B. Dana, Eve, MonicaC. Michael, Eve, JacobD. Micheal, Peter, Monica55. 2015-12 6 个顶点的连通图的最小生成树，其边数为( )。 A.6B.5(正确答案)C.7D.456. 2014-17 有向图中每个顶点的度等于该顶点的( )。 A.入度B.出度C.入度和出度之和(正确答案)D.入度和出度之差

21、57. 2013-12 以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是( )。单选题 A. A0, A1, A2, A3(正确答案)B. A0, A1, A3, A2C. A0, A2, A1, A3D. A0, A3, A1, A258. 2013-10 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、6 条边的连通图。若要使它不再是连通图，至少要删去其中的( )条边。单选题 A. 1B. 2C. 3(正确答案)D. 459. 2011-05 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有( )条边。 A7B21(正确答案)C42D4960. 2011-19 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。例如，有图就是一个强连通图。事实上，在删掉边( )后，它依然是强连通的。单选题 A a(正确答案)BbCcDd