数据结构 综合练习四.ppt

1、综合练习四,任国威,一：判断题、算法的优劣语算法描述语言无关，但与所用计算机有关（）、顺序表结构适宜于顺序存取，而链表适宜于进行随机存取（）、任何广义表都可以用树结构表示（）、在哈夫曼树中，权值较大的节点所在层次距离根节点较近（）、在AOE图，缩短关键路径上的某个活动的时间，则整个工程的时间也就必定缩短（）、能完全拓扑排序的有向图一定存在出度为的定点（）、同一非空图的深度遍历序列与广度遍历序列不可能相同（）、若（u、v）是联通网络的一条最小权值的边，则不论采取何种方法构造该网络的最小生成树，所构造出的最小生成树一定包含（u、v）（）、消除递归不一定需要使用栈（）,、设T为一棵平衡二叉树，先插入

2、一个节点a，然后在未进行其它操作的情况下删除该节点，则删除节点后所得到的平衡二叉树一定与T相同（）、散列（Hash）法存储的基本思想是由关键字值决定数据的存储地址（）、B_树中的所有节点的平衡因子都为（）、只要能够进行均匀映射的哈希函数就一定受欢迎（）、任何简单排序都是稳定的排序（）二、选择填空1、在数据结构中，与所使用的计算机无关的是（）A、存储结构B、物理结构C、物理语存储结构D、逻辑结构,D,、在表长为n（n0）的顺序表中，算法的时间复杂度为O()的操作是（）A、求表长操作B、删除任意第I个节点的操作C、在任意第I个节点之前插入一个节点的操作D、遍历该顺序表的每个元素的操作、对27个记录

3、的有序表作折半查找，当查找失败时，至少需要比较多少次？（）A、3B、C、D、简单插入排序在最好情况下的时间复杂度为（）A、O(nlog2n)B、O(n)C、O(n2)D、O(2n)、对一组记录（15,72,38,96,23,45,83,60,54,77）进行直接插入排序时，当把第个记录54插入到有序表时，为寻找其插入位置至少需比较多少次（）A、2B、3C、4D、5,A,B,D,7、具有8个定点的无向图最多有多少条边（）A、B、28C、56D、728、图的广度优先遍历类似于二叉树的（）A、前序遍历B、中序遍历C、后序遍历D、层次遍历9、具有65个节点的完全二叉树（根的层次号为1）的深度为（）A、

4、8B、7C、6D、510、以下给定的序列中，不满足堆定义的是（）A、(99,93,87,84,82,79,68,62,42,22,12)B、(12,22,42,62,68,79,82,84,87,93,99)C、(99,87,93,79,82,62,84,42,22,12,68)D、(99,87,42,79,82,62,68,93,84,12,22),B,D,B,D,九、阅读下列递归算法，给出调用findout（55）的执行过程中的所有输出。stacks;intfindout(intm)initstack(s);finding(m);intfinding(intm)intn,k;if(m6)return(m);n=m/2;/n等于n整除if(n*2)=m)/判断m是否是偶数push(s,n);k=finding(n);elsek=finding(n+3);printf(m);printf(k);if(empty(s)ret