数据结构试题整理与解析-软考中级软件设计师

标签:

本文出自jvm123.com-java技术分享站:http://jvm123.com/2020/11/shu-ju-jie-gou-shi.html

● 双端队列是指在队列的两个端口都可以加入和删除元素,如下图所示,现在要求元素进队列和出队列必须在同一端口。即从a端进队的元素必须从a端出,从b端进队的元素必须从b端出。则对于四个元素的序列a.b.c.d,若要。求前两个元素a.b从a端口按次序全部进入队列。后两个元素Cd从b端口按次序全部进入队列,则不可能得到的出队序列是(59)。   

数据结构试题整理与解析-软考中级软件设计师插图
  • A.d、a、b、c                             B.d、c、b、a
  • C.b、a、d、c                             D.b、d、c、a

双端队列要求元素进出队列必须在同一端口,即从A端进入的元素必须从A端出、从B端进入的元素必须从B端出。这样使得双端队列具有了栈的特点,即后进入的元素先出队。

● 设S是一个长度为n的非空字符串,其中的字符各不相同,则其互异的非平凡子串(非空且不同于S本身)个数为 (57) 。

  • (57)     A.2n-1   B.n²       C.n(n+1)/2     D.(n+2) (n-1)/2

● 某n阶的三对角矩阵A如下图所示,按行将元素存储在一堆数组M中,设a1,1存储在M[1],那么ai,j(1<=i,j<=n且ai,j位于三条对角线中),存储在M(57)。

数据结构试题整理与解析-软考中级软件设计师插图(1)
  • A.i+2j     B.2i+j     C.i+2j-2     D.2i+j-2 (带入)

● 已知某二叉树的先序遍历序列为A B C D E F、中序遍历序列为B A D C F E,则可以确定该二叉树( )。

  • A.是单支树(即非叶子结点都只有一个孩子)
  • B.高度为4(即结点分布在4层上)
  • C.根结点的左子树为空
  • D.根结点的右子树为空

● 具有3个节点的二叉树有(60)种形态。

  • (60)A.2              B.3                  C.5                  D.7

● 具有三个结点的二叉树有五种,可推测出具有四个节点的二叉树有(58)种。

  • (58)A.10     B.11     C.14     D.15

● 对下面的二叉树进行顺序存储(用数组 MEM 表示),已知结点 A、B、C 在 MEM 中对应元素的 下标分别为 1、2、3,那么结点 D、E、F 对应的数组元素下标为( )。

数据结构试题整理与解析-软考中级软件设计师插图(2)
  •  A.4、5、6                   B.4、7、10
  •  C.6、7、8                  D.6、7、14

二叉树的顺序存储图一般为(空节点要占位置):

数据结构试题整理与解析-软考中级软件设计师插图(3)

二叉树的链式存储图为:

数据结构试题整理与解析-软考中级软件设计师插图(4)

● 图G的邻接矩阵如下图所示(顶点依次表示为v0、v1、v2、v3、v4、v5),G是(  )。对G进行广度优先遍历(从v0开始),可能的遍历序列为(  )。

数据结构试题整理与解析-软考中级软件设计师插图(5)
  • A.无向图
  • B.有向图
  • C.完全图
  • D.强连通图
  • A.v0、v1、v2、v3、v4、v5
  • B.v0、v2、v4、 v5、v1、v3
  • C.v0、v1、v3、v5、v2、v4
  • D.v0、v2、v4、v3、v5、v1
数据结构试题整理与解析-软考中级软件设计师插图(6)

● 设散列函数为 H(key)key%11对于关键碍序列(23,40,91,17,19,10,31,65,26),用线性探测法解决冲突构造的哈希表为(60)。

数据结构试题整理与解析-软考中级软件设计师插图(7)

哈希表存储和查找过程

发表评论