数据结构 综合练习四.ppt

《数据结构 综合练习四.ppt》由会员分享，可在线阅读，更多相关《数据结构 综合练习四.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、径可能有多个权值同为最小，则（u、v）不是必须的、设T为一棵平衡二叉树，先插入一个节点a，然后在未进行其它操作的情况下删除该节点，则删除节点后所得到的平衡二叉树一定与T相同（）、散列（Hash）法存储的基本思想是由关键字值决定数据的存储地址（）、B_树中的所有节点的平衡因子都为（）、只要能够进行均匀映射的哈希函数就一定受欢迎（）、任何简单排序都是稳定的排序（）二、选择填空1、在数据结构中，与所使用的计算机无关的是（）A、存储结构B、物理结构C、物理语存储结构D、逻辑结构要简单简单排序包括除希尔排序外的所有插入排序，起泡排序和简单选择排序。而简单选择排序是不稳定的D、在表长为n（n0）的顺序表中

3、，算法的时间复杂度为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每次排除一大半数据，最后一次首尾指针相等假设每次都是尾指针变化

4、，则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)

5、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