2016.6月数据结构习题

1、2016.6月数据结构习题 1、一棵二叉树没有单分支结点，有6个叶结点，则该树总共有_11_个结点。 2、数据结构的实质就是研究数据的 、以及定义在逻辑结构上所进行的一组 。 3、栈和队列的操作特点分别是_ 后进先出 _和 _ 先进先出 _。 4、设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有_21_个结点。 5、一个图的_表示法是唯一的，而_表示法是不唯一的。 6、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有个叶子结点。 7、g为无向图，如果从g的某个顶点出发，进行一次广度优先搜索，即可访问图

2、的每个顶点，则该图一定是。 8、结构中的数据元素存在多对多的关系称为_ 图状 （状） _结构。 9、按照二叉树的递归定义，对二叉树遍历的常用算法有先序；中序；后序三种。 10、在具有n个单元的循环队列中，队满时共有_个元素。 11、3个结点可构成棵不同形态的树。 12、一棵深度为h的满二叉树上的结点总数为 ，一棵深度为h的完全二叉树上的结点总数的最小值为 ，最大值为 。 13、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为 ，有左孩子的条件是 ，其左孩子编号为 。 14、根据数据元素间关系的不同特性，通常可分为集合、线性、树形 、 图状 四类基本结构。

3、 15、数据结构中的数据元素存在一对多的关系称为_树形_结构。 16、要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_n-1和 o(n)_ 。 17、顺序存储的栈中，在作进栈运算时,应先判别栈是否,在进行出栈运算时应先判别栈是否。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量 为。 18、在带头结点的循环链表h中，判断表空的条件是 。 19、具有n个顶点的有向完全图的弧数为_。 20、数据的存储结构被分为_和_。 21、设有一顺序栈s，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,

4、s6,s5,s1,则栈的容量至少应该是_。 22、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_决定的。 23、把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_物理（存储）_结构。 24、在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行_ s-next=p-next _和p-next=s;的操作。 25、3个结点可以构成棵不同形态的二叉树。 26、对于一棵具有n个结点的二叉树，当它为一棵二叉树时具有最小高度，即为，当它为一棵单支树时具有高度，即为。 27、一个图的_表示法是唯一的，而_表示法是不唯一的。 28、在一棵

5、有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。 29、一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。 30、查找法的平均查找长度与元素个数n无关。 31、在带头结点的循环链表h中，判断表空的条件是。 32、一个具有n个顶点的无向完全图的边数为。 33、数组m中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址ea开始连续存放在存储器中。若按行优先方式存放，元素m85的起始地址为_；若按列优先方式存放，元素m85的起始地址为_。 34、对于一个具有n个结点的单链表，在p所指结点后

6、插入一个新结点的时间复杂度为_；在给定值为x的结点后插入一个新结点的时间复杂度为_。 35、数据结构的实质就是研究数据的 、以及定义在逻辑结构上所进行的一组操作。 36、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。 37、n个顶点的连通图的生成树有 条边。 38、通常数组只有_和_两种运算，因此常采用_来存储数组。 39、具有n个顶点的有向完全图的弧数为_。 40、任何连通图的连通分量有_个，即_。 41、结构中的数据元素存在一对一的关系称为_线性 _结构。 42、在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域

7、 左指针 、右指针。 43、有44个结点的完全二叉树，编号为22的结点的左孩子的编号为_，其右孩子_。 44、树中元素之间的关系是一对多的，而图中元素之间的关系为_。 1、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为（ ）。 a、o（n2） b、o(n) c、o(log2n) d、o(nlog2n) 2、下面程序段的时间复杂度为（ ）。 for (i=1;i ai,j=i*j; a、o（m2） b、o（n2） c、o（m*n） d、o（m+n） 3、带头结点的单链表h为空的判断条件是（ ）。 a、h=null b、h-next=null c、h-next=h d、h!=nu

8、ll 4、单链表中，增加头结点的目的是为了（ ）。 a、方便运算的实现 b、标识单链表 c、使单链表中至少有一个结点 d、用于标识起始结点的位置 5、某二叉树的前序和后序序列正好相同，则该二叉树一定是（ ）的二叉树。 a空或只有一个结点 b高度等于其结点数 c任一结点无左孩子 d任一结点无右孩子 6、一棵非空的二叉树的前序遍历与后序遍历序列正好相反，则该二叉树一定满足（ ）。 a: 所有的节点均无左孩子； b: 所有的节点均无右孩子； c: 只有一个叶子节点； d: 是任意一棵二叉树 7、在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，则当作退栈

9、处理时，top的变化为（ ）。 a、top不变 b、top=0 c、toptop+1 d、top=top-1 8、链栈与顺序栈相比，有一个较明显的优点是（ ）。 a、通常不会出现栈满的情况 b、通常不会出现栈空的情况 c、插入操作更加方便 d、删除操作更加方便 9、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 a、单链表 b、双链表 c、单向循环链表 d、顺序表 10、 若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再插入两个元素后，rear 和front 的值分别为（ ）。

10、 a. 1 和 5 b. 2 和4 c. 4 和2 d. 5 和1 11、设有一个无向图g（v，e）和g（v，e），如果g为g的生成树，则下面不正确的说法是（ ）。 a、g为g的子图 b、g为g的连通分量 c、g为g的极小连通子图且vv d、g是g的一个无环子图 12、以下说法错误的是（ ） a每个存储结点只能存放一个数据元素 b数据元素之间的关联方式可由存储结点之间的关联方式直接表达 c一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级 d语言级描述可经编译自动转换成机器级，因此也可以看成是一种机内表示 13、设两个串(s1和s2) ，求s1在s2中首次出现的位置的运算称为_。 (a) 联接操作 (b) 定位操作 (c) 置换操作 (d)赋值操作 14、串的长度是_。 (a) 串中不同字母的个数 (b)串中不同字符的个数 (c) 串中所含字符的个数，且大于0 (d) 串中所含字符的个数 15、设循环队列中数组的下标范围是0(n-1)， 其头尾指针分别为f和r，其中，f表示队头元素位置，r表示队尾元素后面一个元素的位置，则其队满的条件为_。 (a) r+1=n (b) (r+1)%n=f (c) (r+1)%n=n (d) (f+1)%n=r 16、