数据结构算法与实现重要选择合集

《数据结构算法与实现重要选择合集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、六树1．一棵具有n个结点的完全二叉树的树高度（深度）是（ëlog2nû+1）2．有关二叉树下列说法正确的是（一棵二叉树的度可以小于2）每个结点至多有两颗子树，即二叉树中不存在度大于2的节点。3．二叉树的第I层上最多含有结点数为（2I-1）4．在下述结论中，正确的是（①④）①只有一个结点的二叉树的度为0；②二叉树的度为2；③二叉树的左右子树可任意交换；④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。5．由3个结点可以构造出多少种不同的二叉树？（5）6．引入二叉线索树的目的是（加快查找结点的前驱或后继的速度）7．有n个

2、叶子的哈夫曼树的结点总数为（2n-1）8．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（只有一个叶子结点）9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（501）若每个结点均已经编号，则最大的编号为1001，其父亲结点的编号为500，那么从501到1001均为叶子结点。因此，叶子结点数为1001-500=501。故答案为D。11．已知一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则它的先序遍历序列为（CEDBA）A）ACBEDB）DECABC）DEABCD）CEDBA12

3、．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（11）13．利用二叉链表存储树时，根结点的右指针是（空）14．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（M2+M3）当森林转化为对应的二叉树时，二叉树的根结点及其左子树是由森林的第一棵树转化而来，二叉树的右子树是由森林的其余树转化而来。15．若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（X的左子树中最右结点）中序遍历二叉树时，结点的后继为遍历右子树时

4、访问的第一个结点，即右子树中最左下的结点。左子树最右下的节点为前驱。16．n个结点的线索二叉树上含有的线索数为（n+l）17．在一棵高度为k的满二叉树中，结点总数为（2k-1）18．一棵树高为K的完全二叉树至少有（2k-1）个结点七．图1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（O(n+e)）2．设无向图的顶点个数为n，则该图最多有（n(n-1)/2）条边。3．连通分量指的是（无向图中的极大连通子图）4．n个结点的完全有向图含有边的数目（n*（n-1））5．关键路径是（AOE网中从源点

5、到汇点的最长路径）6．有向图中一个顶点的度是该顶点的（入度与出度之和）7．有e条边的无向图，若用邻接表存储，表中有（2e）边结点。8．实现图的广度优先搜索算法需使用的辅助数据结构为（队列）9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（栈）10．存储无向图的邻接矩阵一定是一个（对称矩阵）11．在一个有向图中所有顶点的入度之和等于出度之和的（1）倍12．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（O(n+e)　）13．下列关于AOE网的叙述中，不正确的是（任何一个关键活动提前完成，那么整个工程将会提前

6、完成）14．具有10个顶点的无向图至少有多少条边才能保证连通（915．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（n2-2e）九．查找1．顺序查找法适合于存储结构为（顺序存储或链接存储　）的线性表。2．下面哪些操作不属于静态查找表（插入一个数据元素）3．下面描述不正确的是（经常进行插入和删除操作时可以采用二分查找）4．散列查找时，解决冲突的方法有（链地址法）5．若表中的记录顺序存放在一个一维数组中，在等概率情况下顺序查找的平均查找长度为（O(n)）6．对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元

7、素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为（9/4）ASL=4*(1/8)+3*(1/4)+2*(3/8)+1*(1/4)=9/47．静态查找表与动态查找表二者的根本差别在于（施加在其上的操作不同　　）8．若查找表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下二分法查找的平均检索长度是（O(log2n)）9．对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查找，搜索到R[4]的关键码等于给定值，此时元素比较顺序依次为（R[7]，R[3]，

8、R[5]，R[4]）。10．设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较（8）次。二分查找不成功时和给定值进行比较的关键字个数最多不超过二叉判定树的深度。100个元素查找表的判定树深为8（64<100<128）。11．请指出在顺