数据结构 综合练习四.ppt

综合练习四任国威一：判断题、算法的优劣语算法描述语言无关，但与所用计算机有关（）、顺序表结构适宜于顺序存取，而链表适宜于进行随机存取（）、任何广义表都可以用树结构表示（）、在哈夫曼树中，权值较大的节点所在层次距离根节点较近（）、在AOE图，缩短关键路径上的某个活动的时间，则整个工程的时间也就必定缩短（）、能完全拓扑排序的有向图一定存在出度为的定点（）、同一非空图的深度遍历序列与广度遍历序列不可能相同（）、若（u、v）是联通网络的一条最小权值的边，则不论采取何种方法构造该网络的最小生成树，所构造出的最小生成树一定包含（u、v）（）、消除递归不一定需要使用栈（）树不能表示递归广义表可能有多个关键路径可能有多个权值同为最小，则（u、v）不是必须的、设T为一棵平衡二叉树，先插入一个节点a，然后在未进行其它操作的情况下删除该节点，则删除节点后所得到的平衡二叉树一定与T相同（）、散列（Hash）法存储的基本思想是由关键字值决定数据的存储地址（）、B_树中的所有节点的平衡因子都为（）、只要能够进行均匀映射的哈希函数就一定受欢迎（）、任何简单排序都是稳定的排序（）二、选择填空1、在数据结构中，与所使用的计算机无关的是（）A、存储结构B、物理结构C、物理语存储结构D、逻辑结构要简单简单排序包括除希尔排序外的所有插入排序，起泡排序和简单选择排序。而简单选择排序是不稳定的D、在表长为n（n0）的顺序表中，算法的时间复杂度为O()的操作是（）A、求表长操作B、删除任意第I个节点的操作C、在任意第I个节点之前插入一个节点的操作D、遍历该顺序表的每个元素的操作、对27个记录的有序表作折半查找，当查找失败时，至少需要比较多少次？（）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、5AB每次排除一大半数据，最后一次首尾指针相等假设每次都是尾指针变化，则13,6,2,1BD7、具有8个定点的无向图最多有多少条边（）A、B、28C、56D、728、图的广度优先遍历类似于二叉树的（）A、前序遍历B、中序遍历 C、后序遍历 D、层次遍历9、具有65个节点的完全二叉树（根的层次号为1）的深度为（）A、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)BDBD九、阅读下列递归算法，给出调用findout（55）的执行过程中的所有输出。stack s;int findout(int m)initstack(s);finding(m);int finding(int m)int n,k;if(m6)return(m);n=m/2;/n等于n整除 if(n*2)=m)/判断m是否是偶数 push(s,n);k=finding(n);else k=finding(n+3);printf(m);printf(k);if(empty(s)return(k);/判断栈是否为空 n=pop(s);/弹出栈顶元素给n return(n+k);10,5,15,10,30,25,55,25