问题 单项选择题

一个具有767个结点的完全二叉树,其叶子结点个数为()。

A.383

B.384

C.385

D.386

答案

参考答案:B

解析:

假设n0为度为0的结点总数(即叶子结点数),n1为度为1的结点总数,n2为度为 2的结点总数,由二叉树的性质可知:

n=n0+n1+n2 (1)

其中n为完全二叉树的结点总数。又根据二叉树的定义,有:

n=n1+2×n2+1 (2)

由公式(1)和(2)可得:

n2=n0-1 (3)

把(3)式代入(1)式,可得:

n=2n0+n1-1 (4)

根据本题的条件,有767=2n0+n1-1,即768-n1=2n0。现在我们只需确定n1就能求得n0了。根据完全二叉树的定义,一棵k层的完全二叉树,上面的k-1层为满二叉树,最后一层的结点都靠左边,又因为满二叉树中只有度为0和度为2的结点,没有度为1的结点,这也就意味着在完全二叉树中,只有倒数第二层,才可能有度为1的结点,这就限制了完全二叉树只可能有0个或1个度为1的结点,对于768-n1=2n0,n1显然为0 (因为等式的右边为偶数),所以n0=768/2=384。

阅读理解

Help Wanted
PAINTER
Must have at least 3 years painting experience. Commercial and new construction work. $ 10/hr. Immediate opening. Call 435-9201 with work history.
SECRETARY
Part-time position available in friendly, busy office. Good typing and general office skills. Some weekends required. High pay.
Various duties. Apply(申请) at East Side Management, 500 Park Drive, DeWitt, NY. 13214.
Help Wanted
VETERINARIAN ASSISTANT(兽医助理)
Person needed for busy animal hospital. Some nights and weekends.
Apply in person to Johnson-Marks Animal Hospital, 404 Snow Road, Syracuse, NY. 13224.
After 4 p.m. only please.
NURSES’ ASSISTANTS
Full-time and part-time positions available for modern nursing home.
High pay. Call Mrs. Downes, R.N. at 534-7618.
Help Wanted
COOK NEEDED
Immediately. Busy downtown restaurant. Must be good and dependable.
Experience preferred. Weekends required. Call 324-9817.
SALESPERSON
Experienced. Must have some knowledge of men’s clothing industry. Available to work evenings and some Saturdays. Send resume(个人简历) to: Martin’s Apparel, 237 Rockledge St. Syracuse, NY. 13224.
TEACHER
Small private school needs English and math teachers. Must have BS degree and at least 4 years teaching experience. Send resume to: Wales Charter School 19 South 8th St. NY. 13214.
Help Wanted
HOTEL needs part-time FRONT DESK CLERK. No experience necessary. Excellent people and phone skills a must. Some computer skills helpful. $ 13/hr. Call: Mr Jones 357-2897.
小题1:If you want to get a job as a math teacher, send your resume to ________.
A.237 Rockledge St. Syracuse, NY. 13224B.404 Snow Road, Syracuse, NY. 13224
C.500 Park Drive, DeWitt, NY. 13214D.19 South 8th St. NY. 13214
小题2:If you dislike working on Sundays, being a ______ should be your best choice.
A.cookB.secretaryC.salespersonD.veterinarian assistant
小题3:If you want to get a job at ________ you must have office skills.
A.Martin’s ApparelB.East Side Management
C.Wales Charter SchoolD.Johnson Marks Animal Hospital
小题4:Which job do you think suitable for a beautiful lady, who just graduated from a university and without any work experience?
A.FRONT DESK CLERKB.TEACHERC.SECRETARYD.PAINTER
单项选择题