数据结构复习题-2014.12

1、一、填空题1、3个结点可以构成 棵不同形态的二叉树。3个结点可构成 棵不同形态的树。2、对于一棵具有n个结点的二叉树，当它为一棵 二叉树时具有最小高度，即为 ，当它为一棵单支树时具有 高度，即为 。3、一个图的_表示法是唯一的，而_表示法是不唯一的。4、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为 ，若一个结点编号为23，则其有右孩子的条件是 。5、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。6、 查找法的平均查找长度与元素个数n无关。7、在带头结点的循环链表h中，判断表空的条件是 。8、一个具有

2、n个顶点的无向完全图的边数为 。9、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。若按行优先方式存放，元素M85的起始地址为_；若按列优先方式存放，元素M85的起始地址为_。10、对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为_；在给定值为x的结点后插入一个新结点的时间复杂度为_。11、数据结构的实质就是研究数据的、 以及定义在逻辑结构上所进行的一组操作。12、在线性表的顺序存储中，元素之间的逻辑关系是通过 决定的；在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。13、n个顶点的连通图的生成树有条

3、边。14、通常数组只有_和_两种运算，因此常采用_来存储数组。15、具有n个顶点的有向完全图的弧数为_。16、任何连通图的连通分量有_个，即_。17、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。18、在作进栈运算时,应先判别栈是否 ,在进行出栈运算时应先判别栈是否 。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为 。19、具有n个顶点的有向完全图的弧数为_。具有n个顶点的无向完全图的边数为_。20、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要

4、_个字节；M的第8列和第5行共占_个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的_元素的起始地址一致。二、选择题1、在具有n个结点的二叉排序树上插入一个新结点时，其时间复杂度大致为（）。A、O（n2） B、O(n) C、O(log2n) D、O(nlog2n)2、下面程序段的时间复杂度为（）。 for (i=1;i<=m;+i) for (j=1;j<=n;+j) 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

5、->next=h D、h!=NULL4、单链表中，增加头结点的目的是为了（ ）。A、方便运算的实现 B、标识单链表 C、使单链表中至少有一个结点 D、用于标识起始结点的位置5、一棵非空的二叉树的前序遍历与后序遍历序列正好相反，则该二叉树一定满足（ ）。A: 所有的节点均无左孩子； B: 所有的节点均无右孩子；C: 只有一个叶子节点； D: 是任意一棵二叉树6、在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，则当作退栈处理时，top的变化为（）。A、top不变B、top=0C、toptop+1D、top=top-17、链栈与顺序栈相比，有一个

6、较明显的优点是（ ）。A、通常不会出现栈满的情况 B、通常不会出现栈空的情况C、插入操作更加方便 D、删除操作更加方便8、设有一个无向图G（V，E）和G（V，E），如果G为G的生成树，则下面不正确的说法是（）。A、G为G的子图 B、G为G的连通分量C、G为G的极小连通子图且VV D、G是G的一个无环子图9、设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构最佳。A、线性表的顺序存储结构 B、栈C、队列 D、线性表的链式存储结构10、在具有n个叶子的哈夫曼树中，其结点总数为（）。A、不确定B、2nC、2n+1D、2n-111、若某线性表中最常用的操作是取第i个元素和找第i个元素的前

7、趋元素，则采用（）存储方式最节省时间。A、单链表B、双链表C、单向循环链表D、顺序表12、 若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（）。A. 1 和 5 B. 2 和4 C. 4 和2 D. 5 和113、已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），按依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需用比较的次数为（），查找61的比较次数为（）。A、2B、3 C、4D、514、在一个具有n个单元的顺序栈中，假定以地址

8、高端（即下标为n-1的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化为（）。A、top不变B、top=n-1C、top=top+1D、top=top-115、在一个单链表中，已知q所指结点是p所指结点的前驱，若在p、q之间插入s结点，则执行（ ）操作。A、s->next=p-next;p->next=s; B、q->next=s;s->next=p;C、p->next=s->next;s->next=p; D、p->next=s;s->next=q;三、应用题1、已知某系统在通信联络中只可能出现8种字符，其频率分别为9，17，6，19，11，21，5，12。试设计哈夫曼编码。（必须画出哈夫曼树）91813712165432717524102、试用普里姆算法与克鲁斯卡尔算法分别构造如下网络的最小生成树，并画出基本步骤。3、针对如下的图。V1V2V4V5V3V7V6V8（1）分别写出深度优先遍历序列和广度优先遍历序列。（2）画出相应的邻接表。4、画出下面的树对应的二叉树，并写出树的先根遍历与后根遍历序列。ABCDEFGHIJKLMNO5、已知一棵二叉树的中根序列：BECDAHGF，后根序列：EDCBHGFA，画出这棵二叉树。6、针对如下的图。（1）分别写出