设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含k个结点时，其二叉链表结点中必有（ ）个空的孩子指针。
- A.k-1
- B.k
- C.k+1
- D.2k
正确答案及解析
正确答案
解析
二叉树的二叉链表存储结构中每个结点有2个指针。每个结点有0个、1个或者2个空指针对应有2个、1个、0个非空指针。
二叉树中边的个数等于非空指针的个数。
假设二叉树中节点的总个数为N
假设二叉树中边的个数为M
假设二叉树中度为0的结点的个数为n0
假设二叉树中度为1的结点的个数为n1
假设二叉树中度为2的结点的个数为n2
所以有n0+n1+n2=N-------------（1）
二叉树中除了根结点之外，其他的结点都有一条便进入该结点，所以二叉树中边的总个数为M=N-1；-------（2）
又M=n1+2×n2;-------------------------（3）
所以由（1）（2）（3）可得n0=n2+1;--------------------（4）
设空节点的个数为K，则K=2×n0+n1-------------------（5）
结合（1）（4）（5）可以得到K=N+1（空指针的个数比结点总个数多1）
由（2）可以知道边数M=N-1；（二叉树的边数为结点个数减1）
由（4）可以知道度为0的结点的个数（叶子结点个数）=度为2的结点个数+1（n0=n2+1;）。
包含此试题的试卷
你可能感兴趣的试题
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答5处
-
- A.sensor
- B.searching
- C.service
- D.source
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答4处
-
- A.low-level
- B.low-cost
- C.high-cost
- D.high-performance
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答3处
-
- A.19th
- B.20th
- C.21th
- D.22th
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答2处
-
- A.path
- B.Internet
- C.route
- D.switch
- 查看答案
The Internet of（ 1）（IoT） describes physical objects that are embedded with Sensor，processing abilities，softwares，and other technologies that connect with other devices and systems over the （ 2） or other communication and exchange data networks .Over the past few years, IoT has become one of the most important technologies of the （ 3 ） centuryWe can connect objects to the Internet via embedded devices. By means of（ 4） computing, the cloud, big data, and mobile technologies, physical things can share and collect data with minimal human intervention. Traditional fields of embedded systems，wireless （ 5） networks （WSNs），control systems，automation, independently and collectively enable IoT.回答1处
-
- A.this
- B.thing
- C.think
- D.things
- 查看答案