广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新(2)

3、数组Q[0..n-1]作为一个环形队列，f为当前队头元素的前一位置，r 为队尾元素 的位置，假定队列中元素的个数总小于 n，计算队列中元素个数的公式是 。

A. r-f B. n+f-r C. n+r-f D. (n+r-f) mod n

考循环队列的定义、性质和特点：

所以，由于可以循环，f和r不一定哪个在前，哪个在后，需要用取余来判断。答案是最后一个。既然r和f不知道哪个大，那么，前3个答案都有可能得到非法数据：小于0或者大于n，因此，也可以排除前3个选项。

4、设一棵Huffman树中度为2的节点数为n2，则该树的总节点数为 D 。

A、2n2 B、n2+1 C、4n2 D、2n2+1

考Huffman树的特点和性质：首先是了解Huffman树的特点（也是一颗二叉树），如下图，其次，了解度的概念：结点的度指结点的孩子结点个数，例如度为2 就是有2个孩子结点的结点；叶子结点就是度为0的结点，没有孩子结点的结点.

按照这个概念，度为2的结点树为n2,即为非叶子结点，Huffman树中叶子结点个数是非结点个数+1，所以总结点个数：n2+n2+1

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新(2)全文阅读和word下载服务。