河南工业学院软件工程专业2020年数据结构测试题

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

2、(正确答案)4. 2014-10 链表不具有的特点是( )。 单选题 *A.不必事物估计存储空间B.可随机访问任一元素(正确答案)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，则下面语句序列中错误的是(

3、 )。 单选题 *A. p->rlink->llink = p->rlink;p->llink->rlink = p->llink; 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->r

4、link = p->rlink;p->llink->rlink->llink = p->llink; delete p;7. 2018-15 下图中所使用的数据结构是（）。单选题 *A.哈希表B.栈(正确答案)C.队列D. 二叉树8. 2013-07 下图中所使用的数据结构是（）。单选题 *A.哈希表B.栈(正确答案)C.队列D. 二叉树9. 2012-02 ( )是一种先进先出的线性表。 单选题 *A栈B队列(正确答案)C哈希表(散列表)D二叉树10. 2011-11 广度优先搜索时，需要用到的数据结构是( )。 单选题 *A链表B队列(正确答案)C栈D散列表1

5、1. 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->next;hs->next=s;D.s->next=hs;hs=hs->next;13. 2017-16 对于入栈顺序为a, b, c, d, e, f, g的序列，下列()不可能

6、是合法的出栈序列。 单选题 *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 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a，b，c，另有元素d已经出栈，则可能的入栈顺序是( )。 单选题 *Aa, d, c, bBb, a, c, dCa, c

7、, 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. R518. 2009-12 有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合

8、法的出栈序列？ 单选题 *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 柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C柱上

9、，从下到上的盘子的编号为( )。 单选题 *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, 6(正确答案)D. 1, 4, 3, 7, 222. 2006-19 设栈S的初

10、始状态为空，元素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. 字符串不可以用数组来表示D. 空格字符组成的串就是空串25. 2

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

12、60;h-1) / (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 一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点(根结点的下标为

13、1，若某结点的下标为i，则其左孩子位于下标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

14、 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是( )。 单选题 *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

15、. 2009-14 一个包含n个分支结点(非叶结点)的非空二叉树，它的叶结点数目最多为( )。 单选题 *A 2n + 1B 2n-1C n-1D n+1(正确答案)38. 2008-05 完全二叉树共有2*N-1个结点，则它的叶节点数是( )。 单选题 *A. N-1B. N(正确答案)C. 2*ND. 2*N-139. 2006-14 高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为 0，如果某个均衡的二叉树共有2381个结点，则该树的树高为( )。 单选题 *A. 10B. 11(正确答案)C. 12

16、D. 1340. 2019-14 假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为()。 单选题 *A.ABCDEFGHIJB.ABDEGHJCFI(正确答案)C.ABDEGJHCFID.ABDEGHJFIC41. 2015-16 前序遍历序列与中序遍历序列相同的二叉树为( )。 单选题 *A.根结点无左子树B.根结点无右子树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树(正确答案)42. 2013-11  二叉树的（）第一个访问的节点是根节点。 单选题 *A. 先序遍

17、历(正确答案)B. 中序遍历C. 后序遍历D. 以上都是43. 2012-06 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是( )。 单选题 *AABCBCBACACB(正确答案)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

18、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(数字为结点的编号，以下同)，中根遍历是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，则该二叉

19、树的可能的中根遍历是( ) 单选题 *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的后缀形式是()。 单选题 *A. abcd*+*B. abc+*d*(正确答案)C. a*bc+*dD. b+c*a*d49. 2010-09 前缀表达式“+ 3 * 2 + 5 12”的值是( )。 单选题 *A. 23B. 25C. 37(正确答案)D. 6550. 2009-13 表达式a*(b+c)-d的后缀表达式是： 单选题 *A. abcd*+-B. abc+*

20、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.mn+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 评论了该照片，那 么他(她)的所有朋友都可以看见这个评论以及被评论的照片，但是不能对 该照片进行评论(除非 A 也向他(她)分享了该照片)。现在 Lucia 已经上 传了一张照片，但是她不想让 Jacob 看见这张照片，那么她