算法导论 第三版 第六章 答案 英

算法导论课程作业答案Introduction to AlgorithmsMassachusetts Institute of Technology 6.046J/18.410J Singapore-MIT Alliance SMA5503 Professors Erik Demaine,Lee Wee Sun,and Charles E.Leiserson Handout10Diagnostic Test SolutionsProblem1Consider the following pseudocode:R OUTINE(n)1if n=12then return13else return n+R OUTINE(n?1)(a)Give a one-sentence description of what R OUTINE(n)does.(Remember,don’t guess.) Solution:The routine gives the sum from1to n.(b)Give a precondition for the routine to work correctly.Solution:The value n must be greater than0;otherwise,the routine loops forever.(c)Give a one-sentence description of a faster implementation of the same routine. Solution:Return the value n(n+1)/2.Problem2Give a short(1–2-sentence)description of each of the following data structures:(a)FIFO queueSolution:A dynamic set where the element removed is always the one that has been in the set for the longest time.(b)Priority queueSolution:A dynamic set where each element has anassociated priority value.The element removed is the element with the highest(or lowest)priority.(c)Hash tableSolution:A dynamic set where the location of an element is computed using a function of the ele ment’s key.Problem3UsingΘ-notation,describe the worst-case running time of the best algorithm that you know for each of the following:(a)Finding an element in a sorted array.Solution:Θ(log n)(b)Finding an element in a sorted linked-list.Solution:Θ(n)(c)Inserting an element in a sorted array,once the position is found.Solution:Θ(n)(d)Inserting an element in a sorted linked-list,once the position is found.Solution:Θ(1)Problem4Describe an algorithm that locates the?rst occurrence of the largest element in a?nite list of integers,where the integers are not necessarily distinct.What is the worst-case running time of your algorithm?Solution:Idea is as follows:go through list,keeping track of the largest element found so far and its index.Update whenever necessary.Running time isΘ(n).Problem5How does the height h of a balanced binary search tree relate to the number of nodes n in the tree? Solution:h=O(lg n) Problem 6Does an undirected graph with 5vertices,each of degree 3,exist?If so,draw such a graph.If not,explain why no such graph exists.Solution:No such graph exists by the Handshaking Lemma.Every edge adds 2to the sum of the degrees.Consequently,the sum of the degrees must be even.Problem 7It is known that if a solution to Problem A exists,then a solution to Problem B exists also.(a)Professor Goldbach has just produced a 1,000-page proof that Problem A is unsolvable.If his proof turns out to be valid,can we conclude that Problem B is also unsolvable?Answer yes or no (or don’t know).Solution:No(b)Professor Wiles has just produced a 10,000-page proof that Problem B is unsolvable.If the proof turns out to be valid,can we conclude that problem A is unsolvable as well?Answer yes or no (or don’t know).Solution:YesProblem 8Consider the following statement:If 5points are placed anywhere on or inside a unit square,then there must exist two that are no more than √2/2units apart.Here are two attempts to prove this statement.Proof (a):Place 4of the points on the vertices of the square;that way they are maximally sepa-rated from one another.The 5th point must then lie within √2/2units of one of the other points,since the furthest from the corners it can be is the center,which is exactly √2/2units fromeach of the four corners.Proof (b):Partition the square into 4squares,each with a side of 1/2unit.If any two points areon or inside one of these smaller squares,the distance between these two points will be at most √2/2units.Since there are 5points and only 4squares,at least two points must fall on or inside one of the smaller squares,giving a set of points that are no more than √2/2apart.Which of the proofs are correct:(a),(b),both,or neither (or don’t know)?Solution:(b)onlyProblem9Give an inductive proof of the following statement:For every natural number n>3,we have n!>2n.Solution:Base case:True for n=4.Inductive step:Assume n!>2n.Then,multiplying both sides by(n+1),we get(n+1)n!> (n+1)2n>2?2n=2n+1.Problem10We want to line up6out of10children.Which of the following expresses the number of possible line-ups?(Circle the right answer.)(a)10!/6!(b)10!/4!(c) 106(d) 104 ·6!(e)None of the above(f)Don’t knowSolution:(b),(d)are both correctProblem11A deck of52cards is shuf?ed thoroughly.What is the probability that the4aces are all next to each other?(Circle theright answer.)(a)4!49!/52!(b)1/52!(c)4!/52!(d)4!48!/52!(e)None of the above(f)Don’t knowSolution:(a)Problem12The weather forecaster says that the probability of rain on Saturday is25%and that the probability of rain on Sunday is25%.Consider the following statement:The probability of rain during the weekend is50%.Which of the following best describes the validity of this statement?(a)If the two events(rain on Sat/rain on Sun)are independent,then we can add up the twoprobabilities,and the statement is true.Without independence,we can’t tell.(b)True,whether the two events are independent or not.(c)If the events are independent,the statement is false,because the the probability of no rainduring the weekend is9/16.If they are not independent,we can’t tell.(d)False,no matter what.(e)None of the above.(f)Don’t know.Solution:(c)Problem13A player throws darts at a target.On each trial,independentlyof the other trials,he hits the bull’s-eye with probability1/4.How many times should he throw so that his probability is75%of hitting the bull’s-eye at least once?(a)3(b)4(c)5(d)75%can’t be achieved.(e)Don’t know.Solution:(c),assuming that we want the probability to be≥0.75,not necessarily exactly0.75.Problem14Let X be an indicator random variable.Which of the following statements are true?(Circle all that apply.)(a)Pr{X=0}=Pr{X=1}=1/2(b)Pr{X=1}=E[X](c)E[X]=E[X2](d)E[X]=(E[X])2Solution:(b)and(c)only。

do quite a few in-depth research projects.• She resisted the temptation to laugh.noun + verb• An opportunity arose for me to work in China, so I went and spent a year there.•People feel educational standards slipped when the government cut finances.noun + noun•James has been a team leader / member / player, and he is now able to enjoy the fruits of his hard work.•Their demanding work schedule means they have less time to devote to school assignments. adjective + noun•And they reported lower levels of commitment to school and more modest educational aspirations.•This is not an empty threat; I will call the police if this happens again!verb + adverb• She smiled proudly as she looked at the photos of her new grandson.•I don’t like to travel with my brother because he drives carelessly.adverb + verb• I fully understand that there will be serious problems when doing this project.•You may respectfully listen to their advice, but don’t take it too seriously.In this unit about working part-time while studying, we have come across quite a few useful grammatical collocations, mainly in the patterns of “adjective + noun” and “noun + noun”.Please take a look at the following list of collocations in this unit:Text Astudent achievement, school performance, school engagement, heavy commitment, academicyear, school achievement, school commitment, educational aspirations, school careers, working students, school assignments, non-working students Text Bhigher education, undergraduate student, wealthy students, educational performance, formal education, educational funding, educational benefits PART IIKEY TO EXERCISESSECTION A111) A teaching assistant in kindergarten or a tutor2) A cashier in a store3) A waiter in a restaurant4) A car cleaner2 • I would like to work as a teaching assistantin kindergarten. I really enjoy spending timewith small children and I am thinking ofworking as a teacher in kindergarten in thefuture. So working as a teaching assistantwould definitely be a great experience for me.• I would like to work in a company, whetherbig or small, because in the future I plan toestablish my own business. Working part-time in a company would give me some ideaof what it is like to work in a company, howa company is run, and what job a boss shoulddo.210 Third Edition2In my opinion, the most important advantages of doing part-time jobs are: gaining work experience, acquiring communicative skills, and building connections for future career. In doing part-time jobs, especially those jobs which are related to my field of study, I can build up my work experience and enrich my resume. Besides, in working, I may have to communicate with different kinds of people, soit can help develop my communicative skills, which are essential to success. And in getting to know some important people in the workplace, I can build some contacts for my future career.Understanding the text11To measure the impact of employment on student achievement.2According to the research, a heavy commitment to part-time work undermines and significantly interferes with school achievement andcommitment.3About 10 hours per week or less.4Students become interested in study again.5Students may take easier classes, copyothers’ assignments, cut class, or refuse todo assignments, and over time, students’commitment to school is eroded bit by bit.6Students may find school less rewarding and interesting, and it is highly possible that thosewho have been working long hours will dropout of school before graduation.7Because teenagers working long hours frequently have more money to spend than their peers,and they often become used to spending theirearnings on drugs and alcohol.8Doing part-time jobs while studying isacceptable, but students should work nomore than 10 hours a week if they want to besuccessful in school. Critical thinking21 • Yes, I think early employment can definitelybuild character because besides study,you have to fit yourself into the workingenvironment. You can learn interpersonalskills, social responsibility and professionalethics in a working setting. Moreover, youhave to try hard to strike a balance betweenwork, study, and play. In this way, you willdevelop a strong sense of responsibility andboost your self-confidence.• No, not necessarily. Though early employmentmay help students to gain some workexperience, it is not necessarily helpful inbuilding their character. Because they have tospend quite a lot of time working and maybecome less responsible or less committedto their study. Too much work may also leadto alcohol and drug abuse. So, in some cases,early employment undermines character-building rather than help it.2 • Yes, I agree. Students have so many academictasks to complete in college that they hardlyhave any extra time for work. If they work,they will certainly have to spend less time andenergy on study, which is likely to depresstheir school performance. I see many workingstudents around me sleep in class, skip class,or copy others’ assignments. If they cannotbe responsible students when they should be,how could they become responsible peopleafter graduation? So, I think students shouldtake study as their main task instead of doingpart-time jobs.• No, I don’t agree. College students shouldprepare themselves for future careers, so theyneed not only to perform well academicallybut also develop other skills becausesurviving in society requires more than bookknowledge. Working part-time can exposestudents to the real world and help themacquire basic interpersonal skills. Besides, byearning money to pay for their study, collegestudents can learn how to manage their211UNIT 6 Earn as you learn?money and become less dependent on theirparents.3 • Yes, I agree with the author that workingwhile studying has many negative impactson students, such as not getting enough rest,decreased school performance, abuse of drugsand alcohol. As one’s time and energy arelimited, working, even part-time, will affectone’s study. Therefore, students should takestudy seriously and it is critical not to worklong hours while studying at college.• No, I don’t think there are so many negativeimpacts of working while studying asmentioned by the author. I have manyclassmates who are working part-timeto cover their tuition. Most of them areresponsible students as they want to sharethe financial burden with their parents. Theyalso study very hard for scholarships. At thesame time, they try to make full use of theirworking time. Some of them work with theirprofessors in the lab, so their work does notinterfere with their study. In fact, workingmay benefit their study because they canapply what is learned in class in practice.4 • Yes, I think part-time jobs may help builda sense of responsibility, which in turn mayenhance students’ school performance.Because if you take part-time jobs whilestudying, you have to follow the work ethics,observe the working schedule, work up toexpectations, contribute to teamwork, andbalance work and study. All these will helpyou to multitask, to be more efficient, tocultivate a sense of responsibility, and toenhance your school performance.• No, I don’t think part-time jobs help to builda sense of responsibility, not to mentionenhancing students’ school performancebecause students who take part-time work,especially those who work long hours, haveto strike a balance between work and study.To meet the demanding working schedule,more often than not, they have to cut corners,for example, by devoting less time to studyor ignoring homework. Moreover, they mayspend more on entertainment and luxurygoods as they have more spending money.Students who work long hours usually fail tomeet the academic requirements and have noclear plan for career development.5Part-time employment provides a good opportunity for students to learn many otherthings other than book knowledge. It has many positive influences:• building a sense of responsibility as you haveto accomplish your tasks;• building self-discipline as you have to manageyour time well and rely on yourself;• gaining social skills and work experienceas you interact with people outside theclassroom;• broadening your vision as you learn about theworkplace and society;• having more employment opportunities asyou gain work experience in preparation foryour future career.Words in use31indicate 2conventional3assess 4decrease5alter 6has undermined7 compromise 8controversial9resolved 10 abandonWord building4form formationoccupation occupysolve solution(To be continued)212 Third Editionpersuade persuasion transmit transmission original originality flexibility flexible secure security simple simplicity prosperousprosperity51 solution2 transmission3 prosperity4 formation5 flexible6 occupied7 originality8 productivity9 simplicity10 persuasion 11 representation 12 securityBanked cloze61 J2 C3 H4 D5 M6 G7 I8 A9 E 10 NExpressions in use71 cutting back on2 interfere with3 take a toll on4 at risk of5 dropped out6 in turn7 contribute to 8 are accustomed to 9 held on to 10in other wordsStructure analysis8(Continued )213UNIT 6 Earn as you learn?Structured writing9There are several reasons why people get fired from their jobs. First, people may lose their jobs if they have some dishonest behaviors, such as cheating in their job applications or telling lies in work. Second, employees may be fired due to poor attendance. No boss likes an employee who is often late for or absent from work. Third, people having difficulty getting along with their co-workers are also likely to be fired because they may cause conflicts in the workplace. Therefore, to be a good employee, it isimportant to be honest, punctual, and cooperative.10间隔年指的是学生休假不去上学而去旅游或工作等的一段时间，但不一定是一年。

算法导论（第三版）－复习－第六部分图论22-26［转］22习题22.1-5 有向图G(V, E)的平⽅图。

链表表⽰时，对每结点u的Adj[u]中所有v加⼊队列，后边出队边将Adj[v]加⼊Adj[u]中。

矩阵表⽰时，若w[i, j]、w[j, k]同时为1则将w[i, k]置1.习题22.1-6 O(V)的时间寻找通⽤汇点。

汇点的特征是邻接矩阵的第j列除[j, j]外所有元素为1. 可将每⾏调整[j ,j]后作为⼀个整数，所有整数与运算，为1的位是汇点。

习题22.1-7 有向⽆环图的关联矩阵B，BB’每个元素C[i, j]=∑B[i, k]*B’[k, j]=∑B[i, k]*B[j, k]，即同时进i, j两结点与同时出i, j的结点总数-⼀进⼀出i, j两结点的结点总数。

习题22.2-7 类似BFS，d mod2为0则标为B（娃娃脸），d mod2为1则标为H（⾼跟鞋）。

但若有边连接相同类的结点，则⽆法划分。

wrestler(G){for each u in G{(u,v)=Adj[u];if(v.mark==u.mark){throw error;}if(v.d==NIL) {v.d=u.d+1; v.mark=v.d mod 2;}}}习题22.2-8 任意点之间的最短路径。

重复的Dijktra算法或Floyd-Warshall算法习题22.2-9 ⽆向图扩展为有向图。

问题变成要遍历所有边⼀次。

访问结点u时，将u的⼦结点v的其他边都可视为⼦集v，问题等价于u到v，访问v的集合，v到u。

u标为visiting⼊列，然后访问v，v标为visiting⼊列，然后访问v的后继结点，访问过的边标为visited，返回到visiting的点时，如果该点所有连接的边都标为visited只剩⼀条返回上级的边，则返回上级结点并将点标为visited，v出列，访问u的其他⼦结点，最终u出列。

全部结点出列后达到遍历所有边⼀次。

do quite a few in-depth research projects.• She resisted the temptation to laugh.noun + verb• An opportunity arose for me to work in China, so I went and spent a year there.•People feel educational standards slipped when the government cut finances.noun + noun•James has been a team leader / member / player, and he is now able to enjoy the fruits of his hard work.•Their demanding work schedule means they have less time to devote to school assignments. adjective + noun•And they reported lower levels of commitment to school and more modest educational aspirations.•This is not an empty threat; I will call the police if this happens again!verb + adverb• She smiled proudly as she looked at the photos of her new grandson.•I don’t like to travel with my brother because he drives carelessly.adverb + verb• I fully understand that there will be serious problems when doing this project.•You may respectfully listen to their advice, but don’t take it too seriously.In this unit about working part-time while studying, we have come across quite a few useful grammatical collocations, mainly in the patterns of “adjective + noun” and “noun + noun”.Please take a look at the following list of collocations in this unit:Text Astudent achievement, school performance, school engagement, heavy commitment, academicyear, school achievement, school commitment, educational aspirations, school careers, working students, school assignments, non-working students Text Bhigher education, undergraduate student, wealthy students, educational performance, formal education, educational funding, educational benefits PART IIKEY TO EXERCISESSECTION A111) A teaching assistant in kindergarten or a tutor2) A cashier in a store3) A waiter in a restaurant4) A car cleaner2 • I would like to work as a teaching assistantin kindergarten. I really enjoy spending timewith small children and I am thinking ofworking as a teacher in kindergarten in thefuture. So working as a teaching assistantwould definitely be a great experience for me.• I would like to work in a company, whetherbig or small, because in the future I plan toestablish my own business. Working part-time in a company would give me some ideaof what it is like to work in a company, howa company is run, and what job a boss shoulddo.210 Third Edition2In my opinion, the most important advantages of doing part-time jobs are: gaining work experience, acquiring communicative skills, and building connections for future career. In doing part-time jobs, especially those jobs which are related to my field of study, I can build up my work experience and enrich my resume. Besides, in working, I may have to communicate with different kinds of people, soit can help develop my communicative skills, which are essential to success. And in getting to know some important people in the workplace, I can build some contacts for my future career.Understanding the text11To measure the impact of employment on student achievement.2According to the research, a heavy commitment to part-time work undermines and significantly interferes with school achievement andcommitment.3About 10 hours per week or less.4Students become interested in study again.5Students may take easier classes, copyothers’ assignments, cut class, or refuse todo assignments, and over time, students’commitment to school is eroded bit by bit.6Students may find school less rewarding and interesting, and it is highly possible that thosewho have been working long hours will dropout of school before graduation.7Because teenagers working long hours frequently have more money to spend than their peers,and they often become used to spending theirearnings on drugs and alcohol.8Doing part-time jobs while studying isacceptable, but students should work nomore than 10 hours a week if they want to besuccessful in school. Critical thinking21 • Yes, I think early employment can definitelybuild character because besides study,you have to fit yourself into the workingenvironment. You can learn interpersonalskills, social responsibility and professionalethics in a working setting. Moreover, youhave to try hard to strike a balance betweenwork, study, and play. In this way, you willdevelop a strong sense of responsibility andboost your self-confidence.• No, not necessarily. Though early employmentmay help students to gain some workexperience, it is not necessarily helpful inbuilding their character. Because they have tospend quite a lot of time working and maybecome less responsible or less committedto their study. Too much work may also leadto alcohol and drug abuse. So, in some cases,early employment undermines character-building rather than help it.2 • Yes, I agree. Students have so many academictasks to complete in college that they hardlyhave any extra time for work. If they work,they will certainly have to spend less time andenergy on study, which is likely to depresstheir school performance. I see many workingstudents around me sleep in class, skip class,or copy others’ assignments. If they cannotbe responsible students when they should be,how could they become responsible peopleafter graduation? So, I think students shouldtake study as their main task instead of doingpart-time jobs.• No, I don’t agree. College students shouldprepare themselves for future careers, so theyneed not only to perform well academicallybut also develop other skills becausesurviving in society requires more than bookknowledge. Working part-time can exposestudents to the real world and help themacquire basic interpersonal skills. Besides, byearning money to pay for their study, collegestudents can learn how to manage their211UNIT 6 Earn as you learn?money and become less dependent on theirparents.3 • Yes, I agree with the author that workingwhile studying has many negative impactson students, such as not getting enough rest,decreased school performance, abuse of drugsand alcohol. As one’s time and energy arelimited, working, even part-time, will affectone’s study. Therefore, students should takestudy seriously and it is critical not to worklong hours while studying at college.• No, I don’t think there are so many negativeimpacts of working while studying asmentioned by the author. I have manyclassmates who are working part-timeto cover their tuition. Most of them areresponsible students as they want to sharethe financial burden with their parents. Theyalso study very hard for scholarships. At thesame time, they try to make full use of theirworking time. Some of them work with theirprofessors in the lab, so their work does notinterfere with their study. In fact, workingmay benefit their study because they canapply what is learned in class in practice.4 • Yes, I think part-time jobs may help builda sense of responsibility, which in turn mayenhance students’ school performance.Because if you take part-time jobs whilestudying, you have to follow the work ethics,observe the working schedule, work up toexpectations, contribute to teamwork, andbalance work and study. All these will helpyou to multitask, to be more efficient, tocultivate a sense of responsibility, and toenhance your school performance.• No, I don’t think part-time jobs help to builda sense of responsibility, not to mentionenhancing students’ school performancebecause students who take part-time work,especially those who work long hours, haveto strike a balance between work and study.To meet the demanding working schedule,more often than not, they have to cut corners,for example, by devoting less time to studyor ignoring homework. Moreover, they mayspend more on entertainment and luxurygoods as they have more spending money.Students who work long hours usually fail tomeet the academic requirements and have noclear plan for career development.5Part-time employment provides a good opportunity for students to learn many otherthings other than book knowledge. It has many positive influences:• building a sense of responsibility as you haveto accomplish your tasks;• building self-discipline as you have to manageyour time well and rely on yourself;• gaining social skills and work experienceas you interact with people outside theclassroom;• broadening your vision as you learn about theworkplace and society;• having more employment opportunities asyou gain work experience in preparation foryour future career.Words in use31indicate 2conventional3assess 4decrease5alter 6has undermined7 compromise 8controversial9resolved 10 abandonWord building4form formationoccupation occupysolve solution(To be continued)212 Third Editionpersuade persuasion transmit transmission original originality flexibility flexible secure security simple simplicity prosperousprosperity51 solution2 transmission3 prosperity4 formation5 flexible6 occupied7 originality8 productivity9 simplicity10 persuasion 11 representation 12 securityBanked cloze61 J2 C3 H4 D5 M6 G7 I8 A9 E 10 NExpressions in use71 cutting back on2 interfere with3 take a toll on4 at risk of5 dropped out6 in turn7 contribute to 8 are accustomed to 9 held on to 10in other wordsStructure analysis8(Continued )213UNIT 6 Earn as you learn?Structured writing9There are several reasons why people get fired from their jobs. First, people may lose their jobs if they have some dishonest behaviors, such as cheating in their job applications or telling lies in work. Second, employees may be fired due to poor attendance. No boss likes an employee who is often late for or absent from work. Third, people having difficulty getting along with their co-workers are also likely to be fired because they may cause conflicts in the workplace. Therefore, to be a good employee, it isimportant to be honest, punctual, and cooperative.10间隔年指的是学生休假不去上学而去旅游或工作等的一段时间，但不一定是一年。

Unit 6–Section ALanguage Focus–Words in Use1.When employees participated in the problem-solving process, they were much more willingto (implement) solutions to the problems.2. A strong police force has been placed between the two (rival) groups in the village toprevent fighting and killing.3.Although personally we believe this to be of only secondary importance, its potential rolein (motivating) innovative acts cannot be ignored.4.Though many things have been changed culturally, there is a commitment and sense of responsibility that have not yet been (discarded) in today's society.5.Western nations have older and shrinking populations since they entered the 21st century and their (fluctuating) birth rates have also posed problems.6.She didn't want to marry him and was (prejudiced) against him because he had only a bachelor's degree and didn't meet her expectations for marriage.7.The president is in trouble and will have to work hard to (restore) his credibility afterpeople discovered that he was not telling the truth.8.To study a number of subjects in the humanities has been both enjoyable and (enlightening) , providing me with a new and different perspective on the world in which we live.9.People are concerned about the environment issue because air and water pollution not only affects everyone's health but also makes it difficult for businesses to (profit) .10.Instead of ignoring or envying successful students, I made it my mission to (investigate)the mysterious causes of their success and greatness.Word Building1.strategy2.sympathy3.confirm4.locate5.reflect6.provide7.install8.register9.quotation10.sympathy11.critic12.industrial1.strategic2.sympathetic3.confirmation4.location5.reflection6.provision7.installation8.registration9.quote10.sympathize11.criticize12.industrialize1.He's usually indifferent to the feelings of other people; he can neither understand nor (sympathize) with my eagerness and anxiety.2.There has been no official (confirmation) that the documents are original, although different sources from the media and the public suggest that they are.3.There's a consensus that the (strategic) defense of a country depends on a powerful airforce and marine force, in addition to advanced arms.4.Total construction time of the shop was about 30 days including the (installation) of the newly-imported machines and the assembly of the various parts.5.To illustrate my point of view, I would like to (quote) from a source that many of us findmore authoritative than the words of a businessman.6.People need to be kind. Therefore, I am not ashamed to be regarded as (sympathetic) to the anxieties of those who are treated harshly in life.7.In business, we often do things inappropriately. For example, we may (criticize) someone's work in front of their co-workers.8.The restaurant has recently moved here because its owners want to provide a convenient (location) for their customers in this area.9.Cultural awareness will help you when you learn the language. After all, language is a(n) (reflection) of the culture from which it developed.10.Students are no longer learning how to (industrialize) agricultural economy; instead, they are learning the digital economy.11.People living in this remote area for generations have harsh living conditions and poor (provision) of housing, food and medicines.12.If you do not get the detailed information required for the school's (registration) , you maylose the opportunity to take the classes you want.Banked ClozeSimplifying is not necessarily about less. It can be about more: more time, more enjoyment, more accomplishment, and more of what (1) (profits) you. If you do a lot of things that don't bring you joy or support your long-term plan, then doing less of that kind of things makes sense because you can't (2) (preserve) everything. The purpose of simplifying is to remove what's not important.To understand what should be (3) (discarded), try to think of activities and things as either assets or obligations. An asset is something that is valuable. Some (4) (corresponding) examples are stocks, bonds, buildings, land, gold, etc., but a little more broadly, an asset is anything that can strengthen and (5) (motivate) you, moving you closer to your goals. However, obligations are debts. An obligation is anything that (6) (weakens) you, moves you farther from your goals, provides negative stress, creates anxiety, and decreases your health. Then how can you (7) (implement) the idea of simplifying? Think about your daily activities and start with just one area. For example,you may begin with (8) (obligations) by making a long list of your daily activities. Your list may (9) (revolve) around such routines as paying bills and planning a birthday party for a friend, etc.Do the activities get you closer to your goals? If not, (10) (modify) the list. Remove what is unnecessary in order to concentrate more on something important in your life.Language Focus–Expressions in Use1.Though he was 80 years old, blind and hardly able to walk, his family (was attached to)him so much that they could hardly bear the thought of his death.2.The support our volunteers provide to the community as well as society cannot (be measured in) purely practical terms, and their continuing contribution is vital.3.Please don't forget the Tourist Guide, which should (come in handy) when you travel to different places in Asia and Europe for the next few weeks.4.These people living in this area are still (clinging to) their traditions which give their life meaning and help them in answering many questions.5.You will (pay a big price) for not learning English; you never know how much you willmiss without being able to speak English.6.If you (are exhausted from) travel and trying to adjust to a new time zone, you may not beready to face the new challenging environment yet.7.The general manager of the company intends to introduce new management courses, and tighter controls will be (imposed on) internal management to raise efficiency.8.Class discussions next week will (revolve around) the importance of love, communication anda close relationship between parents and their children.Translation英译汉Minimalism (极简主义) is about getting rid of excess stuff and keeping only what you need. Minimalist living, in simplest terms, is to live with as less as possible, mentally and physically until you achieve peace of mind. Results that ensue are less stress, more time, and increased happiness. Minimalists like to say that they're living more meaningfully, more deliberately, and that the minimalist lifestyle allows them to focus on what's more important in life: friends, hobbies, travel, experiences. Of course, minimalism doesn't meanthere's anything inherently wrong with owning material possessions. Today's problem seems to be that we tend to givetoo much meaning to our things, often forsaking ( 扔掉 ) our health, our relationships, our passions, our personal growth, and our desire to contribute beyond ourselves. In addition to its application in people's daily life, minimalism also finds application in many creative disciplines, including art, architecture, design, dance, film making, theater, music, fashion, photography and literature.极简主义是指去掉剩余的，仅保存需要的部分。

算法导论第三版第六章答案英Chapter6Michelle Bodnar,Andrew LohrDecember31,2016Exercise6.1-1At least2h and at most2h+1?1.Can be seen because a complete binarytree of depth h?1hasΣh?1i=02i=2h?1elements,and the number of elementsin a heap of depth h is between the number for a complete binary tree of depth h?1exclusive and the number in a complete binary tree of depth h inclusive.Exercise6.1-2Write n=2m?1+k where m is as large as possible.Then the heap consists of a complete binary tree of height m?1,along with k additional leaves along the bottom.The height of the root is the length of the longest simple path to one of these kleaves,which must have length m.It is clear from the way we de?ned m that m= lg n .Exercise6.1-3If there largest element in the subtee were somewhere other than the root, it has a parent that is in the subtree.So,it is larger than it’s parent,so,the heap property is violated at the parent of the maximum element in the subtreeExercise6.1-4The smallest element must be a a leaf node.Suppose that node x contains the smallest element and x is not a leaf.Let y denote a child node of x.By the max-heap property,the value of x is greater than or equal to the value of y.Since the elements of the heap are distinct,the inequality is strict.This contradicts the assumption that x contains the smallest element in the heap. Exercise6.1-5Yes,it is.The index of a child is always greater than the index of the parent, so the heap property is satis?ed at each vertex. 1Exercise6.1-6No,the array is not a max-heap.7is contained in position9of the array,so its parent must be in position4,which contains6.This violates the max-heap property.Exercise6.1-7It su?ces to show that the elements with no children are exactly indexed by{ n/2 +1,...,n}.Suppose that we had an i in this range.It’s childeren would be located at2i and2i+1but both of these are≥2 n/2 +2>n and so are not in the array.Now,suppose we had an element with no kids,this means that2i and2i+1are both>n,however,this means that i>n/2.This means that i∈{ n/2 +1,...,n}.Exercise6.2-1271731613101571248902717101613315712489027171016138157124830Exercise6.2-2Algorithm1MIN-HEAPIFY(A,i)1:l=LEF T(i)2:r=RIGHT(i)3:if l≤A.heap?size and A[l]4:smallest=l5:else smallest=i6:end if7:if r≤A.heap?size and A[r]8:smallest=r9:end if10:if smallest=i then11:exchange A[i]with A[smallest]12:MIN-HEAPIFY(A,smallest)13:end ifThe running time of MIN-HEAPIFY is the same as that of MAX-HEAPIFY. Exercise6.2-3The array remains unchanged since the if statement on line line8will be false.2Exercise6.2-4If i>A.heap?size/2then l and r will both exceed A.heap?size so the if statement conditions on lines3and6of the algorithm will never be satis?ed. Therefore largest=i so the recursive call will never be made and nothing will happen.This makes sense because i necessarily corresponds to a leaf node,so MAX–HEAPIFY shouldn’t alter the heap.Exercise6.2-5Iterative Max Heapify(A,i)while il=LEFT(i)r=LEFT(i)largest=iif l≤A.heap-size and A[l]>A[i]thenlargest=lend ifif l≤A.heap-size and A[r]>A[i]thenlargest=rend ifif largest=i thenexchange A[i]and A[largest]elsereturn Aend ifend whilereturn AExercise6.2-6Consider the heap resulting from A where A[1]=1and A[i]=2for 2≤i≤n.Since1is the smallest element of the heap,it must be swapped through each level of the heap until it is a leaf node.Since the heap has height lg n ,MAX-HEAPIFY has worst-case time?(lg n).Exercise6.3-1531710841962295317228419610953192284176109584192231761098451922317610984221953176109842219103176593Exercise6.3-2If we had started at1,we wouldn’t be able to guarantee that the max-heap property is maintained.For example,if the array A is given by[2,1,1,3]then MAX-HEAPIFY won’t exchange2with either of it’s children,both1’s.How-ever,when MAX-HEAPIFY is called on the left child,1,it will swap1with3. This violates the max-heap property because now2is the parent of3.Exercise6.3-3All the nodes of height h partition the set of leaves into sets of size between 2h?1+1and2h,where all but one is size2h.Just by putting all the children of each in their own part of trhe partition.Recall from6.1-2that the heap has height lg(n) ,so,by looking at the one element of this height(the root),we get that there are at most2 lg(n) leaves.Since each of the vertices of height h partitions this into parts of size at least2h?1+1,and all but one corresponds to a part of size2h,we can let k denote the quantity we wish to bound,so,(k?1)2h+k(2h?1+1)≤2 lg(n) ≤n/2sok≤n+2h2h+1+2h+1≤n2h+1≤n2h+1Exercise6.4-14513225717208451320257172845252013717284255201371728425132057172842513208717254413208717252520134871725252013178742525513178742202517135874220252135874172025132587417202513852741720254852713172025845271317202587524131720254752813172025745281317202524578131720255427813172025245781317202542578131720252457813172025Exercise6.4-2We’ll prove the loop invariant of HEAPSORT by induction:Base case:At the start of the?rst iteration of the for loop of lines2-5we have i=A.length.The subarray A[1..n]is a max-heap since BUILD-MAX-HEAP(A)was just called.It contains the n smallest elements,and the empty subarray A[n+1..n]trivially contains the0largest elements of A in sorted order.Suppose that at the start of the i th iteration of of the for loop of lines2-5, the subarray A[1..i]is a max-heap containing the i smallest elements of A[1..n] and the subarray A[i+1..n]contains the n?i largest elements of A[1..n]in sorted order.SinceA[1..i]is a max-heap,A[1]is the largest element in A[1..i]. Thus it is the(n?(i?1))th largest element from the original array since the n?i largest elements are assumed to be at the end of the array.Line3swaps A[1]with A[i],so A[i..n]contain the n?i+1largest elements of the array, and A[1..i?i]contains the i?1smallest elements.Finally,MAX-HEAPIFY is called on A,1.Since A[1..i]was a max-heap prior to the iteration and only the elements in positions1and i were swapped,the left and right subtrees ofnode1,up to node i?1,will be max-heaps.The call to MAX-HEAPIFY will place the element now located at node1into the correct position and restore the5max-heap property so that A[1..i?1]is a max-heap.This concludes the next iteration,and we have veri?ed each part of the loop invariant.By induction, the loop invariant holds for all iterations.After the?nal iteration,the loop invariant says that the subarray A[2..n] contains the n?1largest elements ofA[1..n],sorted.Since A[1]must be the n th largest element,the whole array must be sorted as desired.Exercise6.4-3If it’s already sorted in increasing order,doing the build max heap-max-heap call on line1will takeΘ(n lg(n))time.There will be n iterations of the for loop, each takingΘ(lg(n))time because the element that was at position i was the smallest and so will have lg(n) steps when doing max-heapify on line5.So, it will beΘ(n lg(n))time.If it’s already sorted in decreasing order,then the call on line one will only takeΘ(n)time,since it was already a heap to begin with,but it will still take n lg(n)peel o?the elements from the heap and re-heapify.Exercise6.4-4Consider calling HEAPSORT on an array which is sorted in decreasing order. Every time A[1]is swapped with A[i],MAX-HEAPIFY will be recursively called a number of times equal to the height h of the max-heap containing the elements of positions1through i?1,and has runtime O(h).Since there are2k nodes at height k,the runtime is bounded below bylg ni=12i log(2i)=lg ni=1i2i=2+( lg n ?1)2 lg n =?(n lg n).Exercise6.4-5Since the call on line one could possibly take only linear time(if the input was already a max-heap for example),we will focus on showing that the for loop takes n log n time.This is the case because each time that the last element is placed at the beginning to replace the max element being removed,it has to go through every layer,because it was already very small since it was at the bottom level of the heap before.Exercise6.5-1The following sequence of pictures shows how the max is extracted from the heap.1.Original heap:615 13540126298172.we move the last element to the top of theheap 3.13>9>1so,we swap1and13.4.Since12>5>1,we swap1and12.75.Since6>2>1,we swap1and6.Exercise6.5-2The following sequence of pictures shows how10is inserted into the heap, then swapped with parent nodes until the max-heap property is restored.The node containing the new key is heavily shaded.1.Original heap:815 13540126298172.MAX-HEAP-INSERT(A,10)is called,so we?rst append a node assignedvalue?∞:3.The key value of the new node is updated:4.Since the parent key is smaller than10,the nodes are swapped:95.Since the parent node is smaller than10,the nodes are swapped:Exercise6.5-3Heap-Minimum(A)1:return A[1]Heap-Extract-Min(A)1:if A.heap-size<1then2:Error“heap under?ow”3:end if4:min=A[1]5:A[1]=A[A.heap?size]6:A.heap?size??7:Min-heapify(A,1)8:return minHeap-decrease-key(A,i,key)101:if key?A[i]then2:Error“new key larger than old key”3:end if4:A[i]=key5:while i>1and A[P arent(i)]6:exchange A[i]with A[P arent(i)]7:i=P arent(i)8:end whileMin-Heap-Insert(A,key)1:A.heap?size++2:A[A.heap?size]=∞3:Heap-Decrease-Key(A,A.heap-size,key)Exercise6.5-4If we don’t make an assignment to A[A.heap?size]then it could contain any value.In particular,when we call HEAP-INCREASE-KEY,it might be the case that A[A.heap?size]initially contains a value larger than key,causing an error.By assigning?∞to A[A.heap?size]we guarantee that no error will occur.However,we could have assigned any value less than or equal to key to A[A.heap?size]and the algorithm would still work.Exercise6.5-5Initially,we have a heap and then only change the value at i to make it larger.This can’t invalidate the ordering between i and it’s children,the only other thing that needs to be related to i is that i is less than it’s parent,which may be false.Thus we have the invariant is true at initialization.Then,when we swap i with its parent if it is larger,since it is larger than it’s parent,it must also be larger than it’s sibling,also,since it’s parent was initially above its kids in the heap,we know that it’s parent is larger than it’s kids.The only relation in question is then the new i and it’s parent.At termination,i is the root,so it has no parent,so the heap property must be satis?ed everywhere.Exercise6.5-6Replace A[i]by key in the while condition,and replace line5by“A[i]= A[P ARENT(i)].”After the end of the while loop,add the line A[i]=key. Since the key value doesn’t change,there’s no sense in assigning it until we know where it belongs in the heap.Instead,we only make the assignment of the parent to the child node.At the end of the while loop,i is equal to the position where key belongs since it is either the root,or the parent is at least11key,so we make the assignment.Exercise6.5-7Have a?eld in the structure that is just a count of the total number of elements ever added.When adding an element,use thecurrent value of that counter as the key.Exercise6.5-8The algorithm works as follows:Replace the node to be deleted by the last node of the heap.Update the size of the heap,then call MAX-HEAPIFY to move that node into its proper position and maintain the max-heap property. This has running timeO(lg n)since the number of times MAX-HEAPIFY is recursively called is as most the height of the heap,which is lg n . Algorithm2HEAP-DELETE(A,i)1:A[i]=A[A.heap?size]2:A.heap?size=A.heap?size+13:MAX-HEAPIFY(A,i)Exercise6.5-9Construct a min heap from the heads of each of the k lists.Then,to?nd the next element in the sorted array,extract the minimum element(in O lg(k) time).Then,add to the heap the next element from the shorter list from which the extracted element originally came(also O(lg(k))time).Since?nding the next element in the sorted list takes only at most O(lg(k))time,to? nd the whole list,you need O(n lg(k))total steps.Problem6-1a.They do not.Consider the array A= 3,2,1,4,5 .If we run Build-Max-Heap,we get 5,4,1,3,2 .However,if we run Build-Max-Heap’,we will get 5,4,1,2,3 instead.b.Each insert step takes at most O(lg(n)),since we are doing it n times,weget a bound on the runtime of O(n lg(n)).Problem6-2a.It will su?ce to show how to access parent and child nodes.In a d-ary array,PARENT(i)= i/d ,and CHILD(k,i)=di?d+1+k,where CHILD(k,i) gives the k th child of the node indexed by i.12b.The height of a d-ary heap of n elements is with1of log d n.c.The following is an implementation of HEAP-EXTRACT-MAX for a d-aryheap.An implementation of DMAX-HEAPIFY is also given,which is the analog of MAX-HEAPIFY for d-ary heap.HEAP-EXTRACT-MAX con-sists of constant time operations,followed by a call to DMAX-HEAPIFY.The number of times this recursively calls itself is bounded by the height of the d-ary heap,so the running time is O(d log d n).Note that the CHILD function is meant to be the one described in part(a).Algorithm3HEAP-EXTRACT-MAX(A)for a d-ary heap1:if A.heap?size<1then2:error“heap under?ow”3:end if4:max=A[1]5:A[1]=A[A.heap?size]6:A.heap?size=A.heap?size?17:DMAX-HEAPIFY(A,1)Algorithm4DMAX-HEAPIFY(A,i)1:largest=i2:for k=1to d do3:if CHILD(k,i)≤A.heap?size and A[CHILD(k,i)]>A[i]then4:if A[CHILD(k,i)]>largest then5:largest=A[CHILD(k,i)]6:end if7:end if8:end for9:if largest=i then10:exchange A[i]with A[largest]11:DMAX-HEAPIFY(A,largest)12:end ifd.The runtime of this implementation of INSERT is O(log d n)since the whileloop runs at most as many times as the height of the d-ary array.Note that when we call PARENT,we mean it as de?ned in part(a).e.This is identical to the implementation of HEAP-INCREASE-KEY for2-aryheaps,but with the PARENT function interpreted as in part(a).The run-time is O(log d n)since the while loop runs at most as many times as the height of the d-ary array.13Algorithm5INSERT(A,key)1:A.heap?size=A.heap?size+12:A[A.heap?size]=key3:i=A.heap?size4:while i>1and A[P ARENT(i)5:exchange A[i]with A[P ARENT(i)]6:i=P ARENT(i)7:end whileAlgorithm6INCREASE-KEY(A,i,key)1:if key2:error“new key is smaller than current key”3:end if4:A[i]=key5:while i>1and A[P ARENT(i)6:exchange A[i]with A[P ARENT(i)]7:i=P ARENT(i)8:end whileProblem6-3a.2345 891214 16∞∞∞∞∞∞∞b.For every i,j,Y[1,1]≤Y[i,1]≤Y[i,j].So,if Y[1,1]=∞,we know thatY[i,j]=∞for every i,j.This means that no elements exist.If Y is full,it has no elements labeled∞,in particular,the element Y[m,n]is not labeled ∞.c.Extract-Min(Y,i,j),extracts the minimum value from the young tableau Yobtained by Y [i ,j ]=Y[i +i?1,j +j?1].Note that in running this algorithm,several accesses may be made out of bounds for Y,de? ne these to return∞.No store operations will be made on out of bounds locations.Since the largest value of i+j that this can be called with is n+m,and this quantity must increase by one for each call,we have that the runtime is bounded by n+m.d.Insert(Y,key)Since i+j is decreasing at each step,starts as n+m and isbounded by2below,we know that this program has runtime O(n+m). e.Place the n2elements into a Young Tableau by calling the algorithm frompart d on each.Then,call the algorithm from part c n2to obtain the numbers in increasing order.Both of these operations take time at most2n∈O(n), and are done n2times,so,the total runtime is O(n3)141:min=Y[i,j]2:if Y[i,j+1]=Y[i+1,j]=∞then3:Y[i,j]=∞4:return min5:end if6:if Y[i,j+1]7:Y[i,j]=Y[i,j+1]8:Y[i,j+1]=min9:return Extract-min(y,i,j+1)10:else11:Y[i,j]=Y[i+1,j]12:Y[i+1,j]=min13:return Extract-min(y,i+1,j)14:end if1:i=m,j=n2:Y[i,j]=key3:while Y[i?1,j]>Y[i,j]or Y[i,j?1]>Y[i,j]do 4:if Y[i?1,j]5:Swap Y[i,j]and Y[i,j?1]6:j??7:else8:Swap Y[i,j]and Y[i?1,j]9:i??10:end if11:end while15f.Find(Y,key).Let Check(y,key,i,j)mean to return true if Y[i,j]=key,oth-erwise do nothingi=j=1while Y[i,j]Check(Y,key,i,j)i++end whilewhile i>1and jCheck(i,j)if Y[i,j]j++elsei–end ifend whilereturn false16。

新编英语教程第三版练习册6答案【篇一：新编英语教程3 unit1-10练习册1-10课答案及书本第一部分连词题】fumesmoke or vapour ; offensive or suffocating gas2. sandyof the colour of sand ; pale reddish-yellow3. somehowfor some reason or other4. stale dry and unappetizing5. dingy dirty-looking ; not fresh or cheerful6. proceed go ahead7. bloodshotfull of blood ; red because the small blood vessels are swollen or broken8. dismayedmade afraid or discouraged at the prospect of troubleunit 21. rage be very angry2. a vegetable plot a small piece of land for growing vegetables3. croaking rough and harsh4. murmur speak in a low but not clear voice5. wind down lower ( the car window ) by turning the handle6. gesture of despairmovement of the head or hand to show helplessness7. brutalcruel8. quarantinethe period of separation from others so that the disease cannot spreadunit 31. globeworld2. circlemove around3. indirectlynot straight to the point ; in a roundabout way4. idle talk talking about unimportant things5. coincidence a combination of events happening in such a way that it seems planned or arranged6. hastily in a hurry7. demand ask forcefully8. roar speak in a loud, deep voiceunit 41. willthe legal statement concerning the disposal of one’s property after death2. signature person’s name written by himself3. literaryof literature4. suppositiona guess5. playwrightdramatist, a person who writes plays6. vague not clearly known7. confirmprove the truth of something8. verse poetryunit 61. outlaya spending of money2. refill a new filling3. theoretically in theory4. uranium heavy white metal which is radioactive, a source of atomic energy5. bonnet metal lid on the front of a car6. submarine a ship that can stay under water7. radiationthe process in which energy in the form of rays is sent out from atoms8. syntheticnot naturally produced ; artificialunit 71. pose as pretend to be2. pest an annoying thing3. suspense and anxietystate of being anxious and uncertain about something unknown4. fidgeting moving about restlessly5. assuremake somebody believe, feel sure6. apace quickly7. inquisitive chatterboxa person who is curious about other people and talkative8. obstinacy and willfulnessstubbornness and pig-headedness9. escapism that which makes one stay away from unpleasant reality10. justifygive a good reason foruint 8shelter------------------------- f. protection;a building offering protectionbecome engrossed in----------d. have one’s attention completely taken up bycontent--------------------------e. satisfactionbrowse--------------------------a. read here and there in books especially for enjiymentvariety --------------------------b. collection of different kinds of thingsapart from ----------------------g. besadestempt----------------------------c. attractunit 9fledgling------------------------j. young and inexperiencedspectacular---------------------e. very impressiveadroit --------------------------g. quick and skilfulcoma----------------------------i. unconsciousness due to injuryflurry---------------------------a. sudden excitementrecuperate---------------------b. get back one’s strengthmassive hemorrhage----------c.l osing a lot of bloodfragile--------------------------f. easily injured or brokenconcussion--------------------d. (an)injury to the brainpermanent---------------------h. lasting for a long time or forever unit10cudgel-------------------------c. short,thick stickbuck---------------------------g. lower one’s head or body so as to avoid being hitplacatory----------------------f. submissive,undisturbednegligently-------------------h. carelesslywry----------------------------b. twistedbawling-----------------------a. loud,rough shoutingpandemouium----------------d. (scene of)wila and noisy disorder gramophone------------------e. record-playerunit1 p121. it is an excellent photograph of mrs. johnson.george, her son, has decided tomake several 2. there was a temporary 3. this muslin is beautiful! but it’s so flimsy. is it ?4. the helicopter came to rescue the the plane crash as soon as thelocal authorities received the radio message.5. have you seen the school in the suburbs of london?6. a proverb says that a little7. he was tall and muscular. obviously he has a perfect .8. at the end of the interview the young man overcame his about his salary.9. the headmaster opened the door and looked at the with an air ofdisapproval.10. his efforts for an early proved to be a failure because he had to make suchan awkward journey.unit 2p281. 2. while (cross) the street, you must keep your eyes open.3. (damage) during the war, the airport has never been usedagain.4. ’t possibly pay him a visit.5. 6. (walk) through the fields, one can take a look at the wild flowers.7. we didn’t t hink he was very old, 8. she was wheeled to the hospital,(follow) by her children.9. the children went to the park, a mile away from the school, (sing and talk10. i am sorry to have kept you (wait) for two hours.11. can you hear the children (shout) in the next room?12. he whispered “watch out” at the same time (try) to make as little noise as possible.13. the little girl sat in a corner in deep silence, (let) her doll dangle at her side.14. (find) the room unlocked, we immediately went in.unit 8p122a1. we haven’t seen him for more than ten years and i find hima (change) person, he has become a 2. in the (qualify) teachers will be sent here.3. there lived an unusually (determine) farmer in the nearby village.4. in order to improve our (lead) comrades in our department have made a5. taking a camel ride was a6. teaching is a more (demand) job than working as a tourist guide.7. the child, very (please), cleaned her (soil) hands and went to bed with her lovely toy.8. your unwillingness to cooperate with the doctor has made the case even more9. the (interest) spectators sat watching the (excite) football match for an hour in spite of their (soak) clothes.10. after a (tire) day ta work, the (tire) woman sat in the park enjoying the beautiful sunset with a pleasant smile on her face.b1. the doctor insisted on (give) the patient an immediate operation2. (fascinate), we watched the sun3. if you practice (sing) often, you will know how (do) it without (make) such an exhibition of yourself.4. peter hated (keep) to his bed. he missed (play) with his friends and never failed(be) at the window (see) them (climb) the apple-tree.5. would you mind (open) the window?6. i persuaded him (take) care of the child while i went i really could not depend on his7. i oughtto tell (tell) my secretary to post the letter for me this morning but i was busy (prepare) a speech and i forgot8. “would you like ”“i would preferas a rule, i prefer (read) to watch(watch) tv.”9. “yesterday i found one of the pages in the book i bought you change it for me?”“i’m sorry”10. reference books are not allowed (take) out of the teachers’ readingroom.11. “the (clean).”“you needn’t tell me, i haven’t time”12. “it is no use our (wait) for him any longer. he doesn’t know the way sohe won’t come.”“but the film is worth ”“he’ll regret ”“i’m sure he’ll show up at any minute. he knows howused (be) a tourist guide in this city when he was young.”unit 9 p138a1. boxing has been a controversial topic of conversation for a long time, itssupporters say that it is man’s instinct to wish to show that histhan that of his opponent.(strong)2. they maintain that this instinct makes boxing a sport that is fine and3. they also say that it is very good for young boys to learn how to defendthemselves in case of 4. those who wish to see the of boxing say just the opposite.(abolish)5. they declare that it is6. professional fighters are particularly criticized, but even more so the promoters ofboxing matches who, it is said, make untold out of the sufferings of the boxer.(wealthy)7. but it must be realized that boxers too can make a lot of money, and a good fightercan look forward to a comfortable if he is sensible.(retire)8. and it is that a famous boxer can attract far morespectators that eventhe most famous pop singer or film star.(deny)9. even the most can’t fail to be affected by the exciting atmosphere ofan important boxing match.(emotion)10. although we may not always approve of the motives that lead a man to take upprofessional boxing as a career, we can’t help admiring his in the ring.(brave)as a rule in a gesture of despairat such short noticein hostile silence claimkeep to ones bedcling to no exception to help outspoil if only1.as a rule southerners prefer rice, whereas northerners prefer steamed bread.2.everyone must get up at six to do morning exercises and those who stay up late are no exception to the rule.3. keep to your bed for three days,drink a lot of water and take two pills after each meal,the【篇二：新编英语教程第六册练习册paraphrase答案】nothing in life is more exciting and rewarding than the sudden flash of light that leaves you a changed person--not only changed, but changed for the better.the most inspiring and gratifying fact of life is the unexpected spark of enlightenment that makes you different and a better person than before.2. he came across the street, finally, muffled in his ancient overcoat, shapeless felt hat pulled down over his bald head, looking more like an energetic gnome than an eminent psychiatrist.at last he walked over from the other side of the street, wrapped in his old-fashioned overcoat, his bald head covered by a shapeless felt hat. he looked like a dwarfish old man fullof energy rather than a well-known psychiatrist.3. the woman who spoke next had never married because of a sense of obligation to her widowed mother; she recalled bitterly all the marital chances she had let go by.the next speaker on the tape was a woman who had remained single because she thought she was obliged to take care of her mother who was a widow. she still remembered and told others miserably about all the chances of marriage she had missed.4. in the end, if you let it become a habit, it can become a real roadblock, an excuse for not trying any more.eventually, if you form a ha bit of saying “if only”, the phrase can really turn to an obstruction, providing you with an excuse for giving up trying anything at all.5. ... you never got out of the past tense. not once did you mention the future.…you are always thinking of the pa st, regretting and lamenting. you did not look forward to what you can do in the future at all.6. my, my, said the old man slyly. if only we had come down ten seconds sooner, wed have caught that cab, wouldnt we? the old man said to me trickily, using the phrase “if only” on purpose, “if only we’d got here ten seconds earlier, we’d have caught the cab.” i laughed and understood what he meant. so i followed his advice and said, “next time i’ll run faster”.unit 21. moses pleaded a speech defect to rationalize his reluctance to deliver jehovahs edict to pharaoh. moses justified his unwillingness to pass jehovah’s order to pharaoh, saying that he was “slow of speech”.2. yet for all the trouble procrastination may incur, delay can often inspire and revive a creative soul.delay leads to problems. however, in many cases, it can often stimulate the creativity in an artist.3. he notes that speedy action can be embarrassing or extremely costly.he points out that hastiness may give rise to decision which turn out to be humiliating or expensive.4. bureaucratization, which flourished amid the growing burdens of government and the greater complexity of society, was designed to smother policymakers in blankets of legalism, compromise and reappraisal---and thereby prevent hasty decisions from being made.excessive red-tape(官样文章；繁文缛节) developed because public administration was expanding in scope and because society was growing more and more complicated. in this sense, red-tape helped those in charge of policy to be fully engaged in enormous amount of paperwork and judgment, thus making it impossible for an immature decision to result.5. ...many of my friends go through agonies when they face a blank page.…many of my friends have a hard time the moment they attempt to put pen to paper.unit 31. of course, my father is a gentleman of the old school, a member of the generation to whom a good deal of modern architecture is unnerving; but i suspect---i more than suspect, i am convinced---that his negative response was not so much to the architecture as to a violation of his concept of the nature of money.brought up in the old tradition, my father is naturally not prepared to accept the idea of modern architecture; his objection to it, i would assume, indeed i should say i am pretty sure, is not a result of his strong dislike of the physicalbuilding itself, but rather that of his refusal to change his attitude towards money.2. if a buildings design made it appear impregnable, the institution was necessarily sound, and the meaning of the heavy wall as an architectural symbol dwelt in the prevailing attitude toward money, rather than in any aesthetic theory.if a building was made to look sturdy/invulnerable, it would be accordingly regarded as reliable, and the significance of the thick walls would be measured not by their artistic value, butby their seeming ability to provide a safe location for money.3. in a primitive society, for example, men pictured the world as large, fearsome, hostile, and beyond human control.people in a primitive society, for example, saw the world as an enormous planet full of fear, hatred and disorder.4.the principal function of todays wall is to separate possible undesirable outside air from the controlled conditions of temperature and humidity which we have created inside.today a wall serves mainly as a physical means to protect the desired atmosphere inside from being disturbed by anything unwelcome outside.5. to repeat, it is not our advanced technology, but our changing conceptions of ourselves in relation to the world that determine how we shall build our walls.again, the decisive factor that can influence the design of a wall is not the advancement of science and technology, but our ever-changing attitude towards our place in this world.unit 41. he was a man of exuberant fancy, and, withal, of an authority so irresistible that, at his will, he turned his varied fancies into facts.he was a man rich in whimsies, and intolerant of any act bold enough as to challenge his authority. when his mind caught upon something, absurd as it might be, he would do everything to make sure that it was done in the way he wished.2. when every member of his domestic and political systems moved smoothly in its appointed course, his nature was bland and genial; but whenever there was a little hitch, and some of his orbs got out of their orbits, he was blander and more genial still, for nothing pleased him so much as to make the crooked straight, and crush down uneven places.when all his subjects behaved in such a manner as they were told to, he could be gentle and kind. and he could even be more so, if anything not conforming to what he expected should occur, because that offered a great chance for him to see the undesirable removed, a thing he was most delighted in doing.3. he could open either door he pleased: he was subject to no guidance or influence but that of the aforementioned impartial and incorruptible chance.he enjoyed total freedom to choose what to do: he was not directed or influenced by anyone as to which door to open. the only thing that was decisive in terms of his fate was the above-mentioned chance, granted to all the accused alike.4. this element of uncertainty lent an interest to the occasion which it could not otherwise have attained.the fact that no one could tell for sure what might happen (to the accused) made this from of trial more attractive than any other form of justice.5. thus the masses were entertained and pleased, and the thinking part of the community could bring no charge of unfairness against this plan; for did not the accused person have the whole matter in his own hands?thus people enjoyed coming here to watch, and those guided by reason in the society could not possibly question the fairness of this form of trial; for was it not the fact that all the accused were given equal chances to make decisions upon their won destiny?unit51. this semi-barbaric king had a daughter as blooming as his most florid fancies, and with a soul as fervent and imperious as his own.this semi-barbaric king had a daughter as exuberant as the wildest of his notions, a daughter who possessed a nature as fierce and tyrannical as his own.2. of course, everybody knew that the deed with which the accused was charged had been done.it was, of course, known to all that he was guilty of the offense of conducting an affair with the princess.3. ...; but the king would not think of allowing any fact of this kind to interfere with the workings of the tribunal, in which he took such great delight and satisfaction.…,even though the king was well aware that the love affair had taken place, he would still refuse to let the normal method of deciding guilt or innocence be disturbed, because he was extremely enthusiastic about his way of setting matters of this kind.4. ...; but gold, and the power of a womans will, had brought the secret to the princess..…; but because she had the money, and above all, because her determination was so irresistible, the princess was able to get access to the secret.5. he understood her nature, and his soul was assured thatshe would never rest until she had made plain to herself this thing, hidden to all other lookers-on, even to the king.he knew her so well that he was perfectly positive that she would never cease to search for the secret, which remained unknown to all other spectators, even to the king himself.unit 61. there seems to be a general assumption that brilliant people cannot stand routine; that they need a varied, exciting life in order to do their best.it is generally believed that a colorless life can freeze acreative mind, and that only a colorful life can inspire a man to creative work.2. the outstanding characteristic of mans creativeness is the ability to transmute trivial impulses into momentous consequences.one of the wonders human creativity works is that man can make full use of even insignificant feelings to produce far-reaching results.3. an eventful life exhausts rather than stimulates.a life full of diversions stops man’s creativity instead of activating it.4. it is usually the mediocre poets, writers, etc.,who go in search of stimulating events to release their creative flow.only literary artists of an average type rely on excitements inlife as a source for their creative work./ great poets, writers, etc., create works of art out of trivial and common subject.5. people who find dull job unendurable are often dull people who do not know what to do with themselves when at leisure.people who are unable to see how to be patient withrepetitious work are usually those who are unable to see where to find fun in life when it comes to relaxation.【篇三：新编英语教程6 第三版译文】txt>在生活中，没有什么比顿悟更令人激动和兴奋的，它可以改变一个人——不仅仅是改变，而且变得更好。