计算机公共基础知识

来源：百度知道 编辑：UC知道 时间：2024/06/21 09:08:31
1）设一棵完全二叉树共有700个结点，则在该二叉树中有多少个叶子结点？ 答案 350个 要过程！！

2）在一个容量为15的循环队列中，若头指针front=6,尾指针rear=9,则该循环队列种共有 多少个元素？答案 3 要过程！！！

解：完全二叉树的定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
可以算出，这棵二叉树共十层，1-9层的节点个数为2^9-1=511个,所以最后一层的节点个数为700-511=189个,189div2=95,那么倒数第二层的叶结点个数即是2^(9-1)-95=161个
所以所有的叶结点个数即为:189+161=350个

第一题：N/2即可 700/2=350

第二题：画一张循环队示意图，一个圈，内再一个圈，然后分成15等分，0开始标，最后为14. 因为front=6，rear=9，进了3格。 所以元素个数为3.