数据结构题和答案

《数据结构题和答案》由会员分享，可在线阅读，更多相关《数据结构题和答案（8页珍藏版）》请在装配图网上搜索。

1、数据结构题和答案一、填空题： 1、3个节点可以构成 5 棵不同形态的二叉树。3个结点可构成 2 棵不同形态的树。 2、对于一棵具有n个结点的二叉树，当它为一棵 完全 二叉树时具有最小高度，即为 log2n+1 ，当它为一棵单支树时具有 最大 高度，即为 n 。 3、一个图的_邻接矩阵_表示法是唯一的，而_邻接表_表示法是不唯一的。 4、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为 29 ，若一个结点编号为23，则其有右孩子的条件是 n=47 2n+1=2*23+1 。 5、一棵深度为h的完全二叉树上的结点总数的最小值为 (2h-1) ，最大值为 2

2、h-1。 7、在带头结点的循环链表h中，判断表空的条件是 h-next=h 。 8、一个具有n个顶点的无向完全图的边数为 n(n-1)/2 。 ？9、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M85的起始地址EA+222；若按列优先方式存放，元素M85的起始地址为EA+117。 10、对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为_O(1)_；在给定值为x的结点后插入一个新结点的时间复杂度为_O(n)_。 11、数据结构的实质就是研究数据的逻辑关系、物理结构 以及定义在逻辑结构上

3、所进行的一组操作。 12、在线性表的顺序存储中，元素之间的逻辑关系是通过 物理位置 决定的；在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。 13、n个顶点的连通图的生成树有 n-1 条边。 14、通常数组只有_读_和_写_两种运算，因此常采用顺序存储方式来存储数组。 15、具有n个顶点的有向完全图的弧数为_n(n-1)_。 16、任何连通图的连通分量有1个，即极大连通子图本身。 17、G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。 19、在具有n个单元的循环队列中，队满时共有 n-1个元素。 17、已知一棵度为3的树有2个度为1

4、的结点，3个度为2的结点，4个度为3的结点，则该树中有 12 个叶子结点1+1*2+3*2+4*3-2-3-4=12。 21、数据的存储结构被分为顺序存储结构和链式存储结构。 22、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是_3_。 24、有44个结点的完全二叉树编号为22的结点的左孩子的编号为44其右孩子没有 18、在作进栈运算时,应先判别栈是否 栈满 ,在进行出栈运算时应先判别栈是否 栈空 。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为 N 。为了增加内存空间的利用率和减

5、少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 栈底 分别设在这片内存空间的两端,这样,当 两栈都为满 时，才产生上溢。 19、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要_540_个字节；M的第8列和第5行共占_18*6_个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的_M310_元素的起始地址一致。 二、选择题： 1、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为。 A、O B、O(n) C、O(log2n) D、O(nlog2n) 2、下面程序段的时间复杂度为。 for

6、(i=1;i=m;+i) for (j=1;jnext=NULL C、h-next=h D、h!=NULL 4、单链表中，增加头结点的目的是为了。 A、方便运算的实现 B、标识单链表 C、使单链表中至少有一个结点 D、用于标识起始结点的位置 5、一棵非空的二叉树的前序遍历与后序遍历序列正好相反，则该二叉树一定满足 A: 所有的节点均无左孩子； B: 所有的节点均无右孩子； C: 只有一个叶子节点； D: 是任意一棵二叉树 5、一棵非空的二叉树的前序遍历与后序遍历序列正好相同，则该二叉树一定满足 A: 所有的节点均无左孩子； B: 所有的节点均无右孩子； C: 只有一个叶子节点； D: 是任意一

7、棵二叉树 6、在一个具有n个单元的顺序栈中，假定以地址端作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为 A 、top不变 B、top=0 C、top=top+1 D、top=top-1 16、在一个具有n个单元的顺序栈中，假定以地址高端作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化为。 A、top不变 B、top=n-1 C、top=top+1 D、top=top-1 7、链栈与顺序栈相比，有一个较明显的优点是。 A、通常不会出现栈满的情况 B、通常不会出现栈空的情况 C、插入操作更加方便 D、删除操作更加方便 8、设有一个无向图G和G，如果G为G的生

8、成树，则下面不正确的说法是。 A、G为G的子图 B、G为G的连通分量 C、G为G的极小连通子图且VV D、G是G的一个无环子图 9、设计一个判别表达式中左右括号是否配对出现的算法，采用数据结构最佳。 A、线性表的顺序存储结构 B、栈 C、队列 D、线性表的链式存储结构 10、在具有n个叶子的哈夫曼树中，其结点总数为。 A、不确定 B、2n C、2n+1 D、2n-1 11、任何一个无向连通图的最小生成树。 A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 12、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。 A、第i行非元素之和 B、第i列非元素之和 C、第i行非零且非元

9、素的个数 D、第i列非零且非元素的个数 13、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用存储方式最节省时间。 A、单链表 B、双链表 C、单向循环链表 D、顺序表 14、 若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为。 A. 1 和 5 B. 2 和4 C. 4 和2 D. 5 和1 15、已知10个数据元素为，按依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需用比较的次数为，查找61的比较次数为。 A、2 B、3 C、4 D、5

10、17、设森林T中有三棵树，第一、二、三棵树的结点个数分别是n1，n2，n3，那么当把森林转换成二叉树后，其根结点的左子树上有个结点，右子树上有个结点。 A、n1-1 B、n1 C、n1+n2 D、n2+n3 14、使用双向链表存储数据，其优点是可以。 A、提高检索速度 B、很方便地插入和删除数据 C、节约存储空间 D、很快回收存储空间 16、与数据元素本身的形式、内容、相对位置、个数无关的是数据的。 A、存储结构 B、存储实现 C、逻辑结构 D、运算实现 应用题 1、已知某系统在通信联络中只可能出现8种字符，其频率分别为9，17，6，19，11，21，5，12。试设计哈夫曼编码。 2、试用普里

11、姆算法与克鲁斯卡尔算法分别构造如下网络的最小生成树，并画出基本步骤。 7 1 2 7 13 17 3 9 5 6 5 24 10 12 18 4 普里姆 克鲁斯 3、针对如下的图。 分别写出深度优先遍历序列和广度优先遍历序列。 画出相应的邻接表。 V1 V2 V5 V6 V3 V4 V8 V7 深度：V1V2V4V8V5V7V3V6 广度：V1V2V3V4V5V6V7V8 4、画出下面的树对应的二叉树，并写出树的先根遍历与后根遍历序列。 先：ABEFIGCDHJKLNOM 后：IGFEONMLKJHDCBA A B C D E F G H I J K L M N O 5、已知一棵二叉树的中根序列：BECDAHGF，后根序列：EDCBHGFA，画出这棵二叉树。