A practical algorithm to find the best episode patterns

A Practical Algorithm to Find the Best Episode

Patterns

Masahiro Hirao,Shunsuke Inenaga,Ayumi Shinohara,

Masayuki Takeda,and Setsuo Arikawa

Department of Informatics,Kyushu University33,Fukuoka812-8581,JAPAN {hirao,s-ine,ayumi,takeda,arikawa}@i.kyushu-u.ac.jp Abstract.Episode pattern is a generalized concept of subsequence pat-

tern where the length of substring containing the subsequence is bounded.

Given two sets of strings,consider an optimization problem to?nd a best

episode pattern that is common to one set but not common in the other

set.The problem is known to be NP-hard.We give a practical algorithm

to solve it exactly.

1Introduction

In these days,a lot of text data or sequential data are available,and it is quite important to discover useful rules from these data.Finding a good rule to separate two given sets,often referred as positive examples and negative examples,is a critical task in Discovery Science as well as Machine Learning.

In[4],Hirao et al.considered subsequence patterns as rules.A subsequence pattern s matches with a string t if s can be obtained by deleting zero or more characters from t.They introduced a practical algorithm to?nd a best subse-quence pattern that separates positive examples from negative examples,and showed some experimental results.A drawback of subsequence patterns is that they are not suitable for classifying long strings over small alphabet,since a short subsequence pattern matches with almost all long strings.

In this paper,we consider episode patterns,which were originally introduced by Mannila et al.[5].An episode pattern v,k ,where v is a string and k is an integer,matches with a string t if v is a subsequence for some substring u of t with|u|≤k.Episode pattern is a generalization of subsequence pattern since subsequence pattern v is equivalent to episode pattern v,∞ .We give a practical solution to?nd a best episode pattern which separates a given set of strings from the other set of strings.We propose a practical implementation of exact search algorithm that practically avoids exhaustive search.The key idea is to introduce some heuristics to reduce the search space based on the combinatorial properties of episode patterns,and to utilize an e?cient data structure that helps to determine whether an episode pattern matches with a?xed string,at the cost of preprocessing time and space requirement to construct it.

2Preliminaries

Let N be the set of integers.LetΣbe a?nite alphabet,and letΣ?be the set of all strings overΣ.For a string w,we denote by|w|the length of w.For a set S?Σ?of strings,we denote by|S|the number of strings in S,and by||S||the total length of strings in S.We say that a string v is a pre?x(substring,su?x, resp.)of w if w=vy(w=xvy,w=xv,resp.)for some strings x,y∈Σ?.We say that a string v is a subsequence of a string w if v can be obtained by removing zero or more characters from w.We denote by v str w that v is a substring of w that v is a subsequence of w.An episode pattern is a pair of w,and by v

seq

a string v and an integer k,and we de?ne the episode language L eps( v,k )by

L eps( v,k )={w∈Σ?|?u str w such that v seq u and|u|≤k}.

We formulate the problem by following our previous paper[4].Readers should refer to[4]for basic idea behind this formulation.We say that a function f from [0,x max]×[0,y max]to real numbers is conic if

–for any0≤y≤y max,there exists an x1such that

?f(x,y)≥f(x′,y)for any0≤x

?f(x,y)≤f(x′,y)for any x1≤x

–for any0≤x≤x max,there exists a y1such that

?f(x,y)≥f(x,y′)for any0≤y

?f(x,y)≤f(x,y′)for any y1≤y

We assume that f is conic and can be evaluated in constant time in the sequel. The following is the optimization problem to be tackled.

De?nition1(Finding the best episode pattern according to f).

Input Two sets S,T?Σ?of strings.

Output An episode pattern v,k that maximizes the value f(x v,k ,y v,k ), where x v,k =|S∩L eps( v,k )|and y v,k =|T∩L eps( v,k )|.

We remark that the problem is NP-hard,since it is a generalization of?nding the best subsequence pattern[4].

From the conicality of function f and the property of episode patterns,we can prove the following lemmas.

Lemma1([4]).For any0≤x

Lemma2.For any two episode patterns v,l and w,k ,if v seq w and l≥k then L eps( v,l )?L eps( w,k ).

By Lemma1and2,we have the next lemma,that plays a key role in our algorithm which will be described in Section4.

Lemma3.For any two episode patterns v,l and w,k ,if v seq w and l≥k then f(x w,k ,y w,k )≤max{f(x v,l ,y v,l ),f(x v,l ,0),f(0,y v,l ),f(0,0)}.

2

Fig.1.EDASG(t),where t=aabaababb.Solid arrows denote the forward edges,and broken arrows denote the backward edges.

3Episode Directed Acyclic Subsequence Graphs

We?rst analyze the complexity of episode pattern matching:given an episode pattern v,k and a string t,determine whether t∈L eps( v,k )or not.This problem can be answered by?lling up the edit distance table between v and t, where only insertion operation with cost one is allowed.It takesΘ(mn)time and space using a standard dynamic programming method,where m=|v|and n=|t|.

For a?xed string,automata-based approach is useful.We use the Episode Directed Acyclic Subsequence Graph(EDASG)for string t,which was recently introduced by Tro′?ˇc ek in[8].A Directed Acyclic Subsequence Graph(DASG)[2] for a string t is a?nite automaton that accepts all subsequences of t.An EDASG is a directed graph which combines two DASGs for t and the reversed string t R.It contains two kinds of edges,forward edges corresponding to DASG(t),and back-ward edges corresponding to DASG(t R).As an example,EDASG(aabaababb)is shown in Fig.1.When examining if an episode pattern abb,4 matches with t or not,we start from the initial state0and arrive at state6,by traversing the forward edges spelling abb.It means that the shortest pre?x of t that contains abb as a subsequences is t[0:6]=aabaab,where t[i:j]denotes the substring t i+1...t j of t.Moreover,the di?erence between the state numbers6and0corre-sponds to the length of matched substring aabaab of t,that is,6?0=|aabaab|. Since it exceeds the threshold4,we move backwards spelling bba and reach state 1.It means that the shortest su?x of t[0:6]that contains abb as a subsequence is t[1:6]=abaab.Since6?1>4,we have to examine other possibilities.It is not hard to see that we have only to consider the string t[2:?].Thus we con-tinue the same traversal started from state2,that is the next state of state1. By forward traversal spelling abb,we reach state8,and then backward traversal spelling bba bring us to state4.In this time,we found the matched substring t[4:8]=abab which contains the subsequence abb,and the length8?4=4 satis?es the threshold.Therefore we report the occurrence and terminate the procedure.

With the use of EDASG(t),episode pattern matching can be answered quickly in practice,although the worst case behavior is still O(mn).An on-line linear-time algorithm for constructing EDASG(t)for a string t∈Σ?was proposed in[8].

3

For strings v,t∈Σ?,we de?ne the threshold valueθof v for t byθ=min{k∈N|t∈L eps( v,k )}.If no such value,letθ=∞.Note that t∈L eps( v,k )for any k<θ,and t∈L eps( v,k )for anyθ≤k.It is not di?cult to see that the EDASGs are useful to compute the threshold value of v for a?xed t.We have only to repeat the above forward and backward traversal up to the end,and return the minimum length of the matched substrings.

From now on,for a set S of strings and a string v,we consider the numerical sequence{x k}∞k=0,where x k=|S∩L eps( v,k )|.It clearly follows from Lemma2 that the sequence is non-decreasing.Moreover,notice that0≤x k≤|S|for any k,and x l=x l+1=x l+2=···,where l is the length of the longest string in S. It implies that{x k}∞k=0consists of at most min{|S|,l}distinct values.Hence we can represent{x k}∞k=0as a list of pairs(k,x k)such that x k?1=x k.The length of the list is bounded by min{|S|,l}.We call this list a compact representation of the sequence{x k}∞k=0(CRS,for short).

We now show how to compute CRS for each v and a?xed S.Observe that x k increases only at the threshold values of v for some t∈S.For each string t i∈S, we compute the threshold valueθi of v for t i,and sort these threshold values in increasing order.From these sorted values,we can construct the CRS in linear time.To be summarized,if we use the counting sort,we can compute the CRS for v∈Σ?in O(|S|ml+|S|)=O(||S||m)time where m=|v|.We emphasize that the time complexity of computing the CRS of{x k}∞k=0is the same as that of computing x k for a single k(0≤k≤∞),by our method.In the next section, we use a data structure StringSet which supports the method to compute the CRS for any given string v.

4Algorithm

The basic structure of the algorithm is similar to that in[4].

Fig.2shows our algorithm to?nd a best episode pattern from given two sets of strings,according to the function f.Optionally,we can specify the maximum length of episode patterns by the parameter?.Here,we use a data structure PriorityQueue that supports the following methods.

–bool empty():return true if the queue is empty.

–void push(string w,double priority):push a string w into the queue with priority priority.

–(string,double)pop():pop and return a pair(string,priority),where priority is the highest in the queue.

At line16marked by(*),we can simultaneously compute k′and val by using CRSsˉx andˉy in O(|ˉx|+|ˉy|)time.By Lemma3,we can use the value upperBound to prune branches in the search tree computed at line20marked by (**).Note that x v,∞ and y v,∞ can be extracted fromˉx andˉy in constant time, respectively.The next theorem guarantees the completeness of the algorithm. Theorem1.Let S and T be sets of strings,and?be a positive integer.The algorithm FindBestEpisode(S,T,?)will return an episode pattern that maxi-

4

1string FindBestEpisode(StringSet S,T,int?)

2string pre?x,v;

3episodePattern maxSeq;/*pair of string and int*/

4double upperBound=∞,maxVal=?∞,val;

5int k′;

6CompactReprˉx,ˉy;/*CRS*/

7PriorityQueue queue;/*Best First Search*/

8queue.push(””,∞);

9while not queue.empty()do

10(pre?x,upperBound)=queue.pop();

11if upperBound

12foreach c∈Σdo

13v=pre?x+c;/*string concatenation*/

14ˉx=S.crs(v);

15ˉy=T.crs(v);

16(*)k′=argmax k{f(x v,k ,y v,k )}and val=f(x v,k′ ,y v,k′ );

17if val>maxVal then

18maxVal=val;

19maxEpisode= v,k′ ;

20(**)upperBound=max{f(x v,∞ ,y v,∞ ),f(x v,∞ ,0),

f(0,y v,∞ ),f(0,0)};

21if upperBound>maxVal and|v|

22queue.push(v,upperBound);

23return maxEpisode;

Fig.2.Algorithm FindBestEpisode.In our pseudocode,the break statement is to jump out of the closest enclosing loop.

mizes f(x v,k ,y v,k ),with x v,k =|S∩L eps( v,k )|and y v,k =|T∩L eps( v,k )|, where v varies any string of length at most?and k varies any integer.

5Conclusion

We developed a practical algorithm to?nd the best episode pattern to sepa-rate given two sets of strings.Episode pattern is a generalization of subsequence pattern,and the search space of episode patterns is much larger than that of sub-sequence patterns.Nevertheless,our algorithm enabled to?nd the best episode pattern e?ciently:the running time will not be much slower than that for?nding subsequence patterns.

It is challenging to apply our approach to?nd the best pattern in the sense of pattern languages introduced by Angluin[1],where the related consistency problems are shown to be very hard[6].Fujino et al.showed an another approach to?nd the best proximity pattern[3].It may be interesting to combine these

5

approaches into one.We are now in the process of installing our algorithm into the core of the decision tree generator in the BONSAI system[7]. References

1.D.Angluin.Finding patterns common to a set of https://www.doczj.com/doc/6517334351.html,put.Syst.Sci.,

21(1):46–62,Aug.1980.

2.R. A.Baeza-Yates.Searching subsequences.Theoretical Computer Science,

78(2):363–376,Jan.1991.

3.R.Fujino,H.Arimura,and S.Arikawa.Discovering unordered and ordered phrase

association patterns for text mining.In Proc.of the4th Paci?c-Asia Conference on Knowledge Discovery and Data Mining,volume1805of Lecture Notes in Arti?cial Intelligence.Springer-Verlag,Apr.2000.

4.M.Hirao,H.Hoshino,A.Shinohara,M.Takeda,and S.Arikawa.A practical al-

gorithm to?nd the best subsequence patterns.In Proc.of The Third International Conference on Discovery Science,volume1967of Lecture Notes in Arti?cial Intel-ligence,pages141–154.Springer-Verlag,Dec.2000.

5.H.Mannila,H.Toivonen,and A.I.Verkamo.Discovering frequent episode in se-

quences.In U.M.Fayyad and R.Uthurusamy,editors,Proc.of the1st International Conference on Knowledge Discovery and Data Mining,pages210–215.AAAI Press, Aug.1995.

6.S.Miyano,A.Shinohara,and T.Shinohara.Polynomial-time learning of elementary

formal systems.New Generation Computing,18:217–242,2000.

7.S.Shimozono,A.Shinohara,T.Shinohara,S.Miyano,S.Kuhara,and S.Arikawa.

Knowledge acquisition from amino acid sequences by machine learning system BON-SAI.Transactions of Information Processing Society of Japan,35(10):2009–2018, Oct.1994.

8.Z.Tron′?ˇc ek.Episode matching.In Proc.of12th Annual Symposium on Com-

binatorial Pattern Matching,Lecture Notes in Computer Science,pages143–146.

Springer-Verlag,July2001.

6

大学英语阅读训练五篇

Passage 1 There are some very good things about open education. This way of teaching allows the students to grow as people develop their own interests in many subjects. Open education allows students to be responsible for their own education, as they are responsible for what they do in life. Some students do badly in a traditional classroom. The open classroom may allow them to enjoy learning. Some students will be happier in an open education school. They will not have to worry about grades or rules. For students who worry about these things a lot, it is a good idea to be in an open classroom. But many students will not do well in an open classroom. For some students, there are too few rules. These students will do little in school. They will not make good use of open education. Because open education is so different from traditional education, these students may have a problem getting used to making so many choices. For many students it is important to have some rules in the classroom. They worry about the rules even when there are no rules. Even a few rules will help this kind of student. The last point about open education is that some traditional teachers do not like it. Many teachers do not believe in open education. Teachers who want to have an open classroom may have many problems at their schools. You now know what open education is. Some of its good points and bad points have been explained. You may have your own opinion about open education. The writer thinks that open education is a good idea, but only in theory. In actual fact, it may not work very well in a real class or school. The writer believes that most students, but of course not all students, want some structure in their classes. They want to have rules. In some cases, they must be made to study some subjects. Many students are pleased to find subjects they have to study interesting. They would not study those subjects if they did not have to. 1.Open education allows the students to ____. A.grow as the educated B.be responsible for their future C.develop their own interests D.discover subjects outside class 2. Open education may be a good idea for the students who ____. A.enjoy learning B.worry about grades C.do well in a traditional classroom D.are responsible for what they do in life 3. Some students will do little in an open classroom because ____. A.there are too few rules B.they hate activities C.open education is similar to the traditional education D.they worry about the rules 4. Which of the following is NOT mentioned in the passage?____ A.Some traditional teachers do not like it.

大学英语B 阅读理解答案

阅读理解 B 42、Martin Luther King was a black minister, who became a great leader of the civil rights movement in the 1950s and 1960s. King was born on January 15, 1929 in Atlanta, Georgia. When he was young, he was strongly influenced by Thoreau and Indian leader Mahatma Gandhi's idea of non-violent resistance. Having received a Ph. D (Doctor of Philosophy) from Boston University, he became a political and religious leader of the non-violent civil relights movement in 1955. On August 28, 1963, he led over 250,000 Americans on a march in Washington D.C. to fight for the Civil Rights Law to guarantee equality for all people, and delivered his best known speech "I Have a Dream" before the Lincoln Memorial. The "dream" is a dream of brotherly love and equality for the Black and White. Thus, he was awarded the Nobel Prize for peace in 1964, but he was murdered four years later. Though he died, he was greatly respected and loved by the Americans, both the white and the black. By vote of Congress in 1968, the third Monday of every January is now a federal holiday in Luther King's honor. He lives in people's hearts forever. (1)、Martin Luther King was murdered when he was 39 years old. A：T B：F 答案：A (2)、Martin Luther King was a black minister only. A：T B：F 答案：B (3)、Martin Luther King's Day has been a federal holiday for more than 40 years. A：T B：F 答案：A (4)、The underlined word "delivered" in the second paragraph could be replaced by "gave". A：T B：F 答案：A (5)、The best title for this passage is "Civil Rights Law". A：T B：F 答案：B 43、A public house which was recently bought by Mr. James is up for sale. He is going to sell it because it is haunted (闹鬼的). He told me that he could not go to sleep one night because he heard a strange noise coming from the bar. The next morning, he found that the doors had been blocked by chairs and the furniture had been moved. Though Mr. James had turned the lights off before he went to bed, they were on in the morning. He also said that he had found five empty whisky bottles which the ghost (鬼) must have drunk the night before. When I suggested that some villagers must have come in for a free drink, he shook his head. The villagers have told him that they will not accept it even if he gives it away. (1)、Mr. James was the owner of the public house. A：T B：F 答案：A (2)、Mr. James had not turned off the lights that night. A：T B：F 答案：B (3)、Mr. James built the house. A：T B：F 答案：B (4)、Mr. James found sixty empty bottles. A：T B：F 答案：B (5)、The writer of the passage believes Mr. James' story. A：T B：F 答案：B 44、Great changes have been made in family life because of science and industry. In the past, when more Americans lived on farms, the typical family had many children. In a farm family, parents and their children often lived with grandparents. Often, too, uncles and aunts lived nearby. But when industry became more important than agriculture in American life, families became smaller because industry requires workers who are ready and able to move off the land and to move again whenever necessary. And large families can not be moved from place to place as smaller families can. So, at present people tend to have smaller families. In the future, because of industrialization, a typical family will be required to move even more often than now, so families will be even smaller. The typical family may remain childless and consists only of a man and a woman. A small number of families may take child raising as their chief work. At the same time they may also raise other people's children, leaving those families free to move from job to job. (1)、The passage discusses influence of science and industry on American families. A：T B：F 答案：A (2)、Families of the past, the present and the future are described in the passage. A：T B：F 答案：A (3)、People no longer want to have children. A：T B：F 答案：B (4)、Grandparents will take the chief responsibility of raising children in the future. A：T B：F 答案：B (5)、Large families cannot fit in with a highly industrialized society. A：T B：F 答案：A 45、My husband had just bought a new washing machine for me. I decided to use it and I washed a lot of things. Everything worked well, but I found one of my husband's socks missing. I looked everywhere for it, but I couldn't find it anywhere. The next morning, I got ready for school as usual. When the bell rang, the students came in. I greeted them first and then told them what we were going to do that day. When I turned around to write on the blackboard, the class broke out a roar! They laughed and laughed. They laughed so much, in fact, that I was afraid the headmaster would be into seeing all this. I asked the class to stop, but the more I talked, the more they laughed. I decided to pay no attention to them and I continued to write on the blackboard. When I did this, they roared even more. Finally, the teacher who had the room next to mine came in to see what all the laughter was about. When he came in, he started laughing, too!

大学英语阅读精选篇

Passage 1 No one prior to World War II more trenchantly analyzed the philosophical differences between utopians and realists than did E.H.Carr in his celebrated work, which, although published in 1939, did not have its impact in America until after World War II. Carr used the term utopians for idealists who placed emphasis on international law and organization and on the influence of morality and public opinion in the affairs of nations. He probably did not intend the more pejorative connotation that attached to the term utopians after World War II as na?ve opponents of power politics expounded by realists. Indeed, since the end of the Cold War, the idealist concept of the harmony of national interests in peace has received new attention in a more recent neoliberal-neorealist debate. The failures of the League of Nations in the 1930s cast doubt on the harmony of interest in peace, which appeared to accord with the interests of satisfied, status-quo powers with democratic governments, but not with the perceived needs of revisionists, totalitarians, authoritarian states seeking boundary changes, enhanced status, greater power, and, especially in the case of Nazi Germany, revenge for the humiliation of the post-World War I settlement imposed by the Versailles treaty. Contrary to the utopian assumption, national self-determination did not always produce representative governments. Instead, the overthrow of the old monarchical order gave rise in many places, including Russia, to a more pervasive and oppressive totalitarian states. The Molotov-Ribbentrop Pact of August 1939 between the Soviet Union and Nazi Germany set the stage for Adolph Hitler’s invasion of Poland, the outbreak of World War II, the partition of Poland, and the absorption of Baltic states into the Soviet Union, all in flagrant contravention of the standards of international conduct set forth in utopian theory. 1.Who took a strong analysis of the philosophical differences between utopians and realists? A.Adolph Hitler did B. E.H.Carr did C.Neorealist did D.Molotov did 2.What did utopian mean in Carr’s opinion? A.Idealists who placed emphasis on international law and organization and on the influence of morality and public opinion in the affairs of nations. B.Na?ve opponents of power politics. C.Status-quo powers D.Revisionists. 3.What is the consequence of national self-determination? A.Producing representative governments. B.Giving rise to a more pervasive and oppressive totalitarian states. C.Both A and B D.Sometimes A, sometimes B. 4.What was the influence of the Molotov-Ribbentrop Pact of August 1939? A.to set the stage for Adolph Hitler’s invasion of Poland B.leading to the outbreak of World War II C. a cause of the partition of Poland D.all of A,B and C 5.Which one can serve as the title of this passage?

大学英语B阅读理解练习题及答案

Passage 1 Many people who work in London prefer to live outside it, and to go in to their offices or schools every day by train, car or bus, even though this means they have to get up early in the morning and reach home late in the evening. One advantage of living outside London is that houses are cheaper. Even a small flat in London without a garden costs quite a lot to rent. With the same money, one can get a little house in the country with a garden of one’s own. Then, in the country one can really get away from the noise and hurry of busy working lives. Even though one has to get up earlier and spend more time in trains or buses, one can sleep better at night and during weekends and on summer evenings, one can enjoy the fresh, clean air of the countr y. If one likes garden, one can spend one’s free time digging, planting, watering and doing the hundred and one other jobs which are needed in a garden. Then, when the flowers and vegetables come up, one has got the reward together with those who have shared the secret of Nature. Some people, however, take no interest in country things: for them, happiness lies in the town, with its cinemas and theatres, beautiful shops and busy streets, dance-halls and restaurants. Such people would feel that their life was not worth living if they had to live it outside London. An occasional walk in one of the parks and a fortnight’s (two weeks) visit to the sea every summer is all the country they want: the rest they are quite prepared to leave to those who are glad to get away from London every night. 1. Which of the following statements is NOT true? A. People who love Nature prefer to live outside the city. B. All the people who work in London prefer to live in the country. C. Some people enjoying city life prefer to work and live inside London. D. Many nature lovers, though working in London, prefer to live outside. 2. With the same money needed for ________, one can buy a little house with a garden in the country. A. getting a small flat with a garden B. having a small flat with a garden C. renting a small flat without a garden D. buying a small flat without a garden 3. When the garden is in blossom, the one ________ has been rewarded. A. living in the country B. having spent time working in the garden. C. having a garden of his own. D. having been digging, planting and watering 4. People who think happiness lies in the city life would feel that ________ if they had to live outside London. A. their life was meaningless B. their life was invaluable C. they didn’t deserve a happy life D. they were not worthy of their happy life 5. The underlined phrase “get away from” in the 3rd paragraph refers to ________. A. deal with B. do away with C. escape from D. prevent from 很多在伦敦工作的人喜欢住在伦敦郊外，然后每天乘火车、汽车和公交车去上班或上学。这也就意味着他们不得不早出晚归。

大学英语阅读汇总

Is it possible to persuade mankind to live without war? War is an ancient institution which has existed for at least six thousand years. It was always bad and usually foolish, but in the past the human race managed to live with it. Modern ingenuity (创造力) has changed this. Either Man will abolish war, or war will abolish Man. For the present, it is nuclear weapons that cause the most serious danger, but bacteriological or chemical weapons, may before long, offer an even greater threat. If we succeed in abolishing nuclear weapons, our work will not be done. It will never be done until we have succeeded in abolishing war. To do this, we need to persuade mankind to look upon international questions in a new way, not as contests of force, in which the victory goes to the side which is most skillful in killing people, but by arbitration (调解) in accordance with a greed principles of law. It is not easy to change very old mental habits, but this is what must be attempted. There are those who say that the adoption of this or that ideology would prevent war. I believe this to be a big error. All ideologies are based on dogmatic (教条式的)statements which are, at best, doubtful, and at worst, totally false. Their adherents believe in them fanatically (狂热地) that they are willing to go to war in support of them. The movement of world opinion during the past few years has been very largely such as we can welcome. It has become a commonplace (老生长谈)that nuclear war must be avoided. Of course very difficult problems remain in the world, but the spirit in which they are being approached is a better one than it was some years ago. It has begun to be thought, even by the powerful men who decide whether we shall live or die, that negotiations should reach agreements even if both sides do not find these agreements wholly satisfactory. It has begun to be under stood that the important conflict nowadays is not between different countries, but between Man and the atom bomb. 1、This passage implies that war now is _________ A. as necessary as in the past B. as bad as in the past C. not so dangerous as in the past D. worse than in the past 2、In the sentence "To do this, we need to persuade mankind... "(Line 6, Para.1), "this" refers to _________ A. abolishing war B. improving weapons C. solving international problems D. living a peaceful life 3、From Paragraph 2, we learn that the author of the passage____ A. is a supporter of some modem ideologies B. does not think that the adoption of any ideology could prevent war C. believes that the adoption of some ideologies could prevent war D .has no doubt about the truth of any ideologies 4、The last paragraph suggests that_________ A. international agreements can be reached more easily now B. man begins to realize the danger of nuclear war C. nuclear war will definitely not take place D. world opinion welcomes nuclear war 5、According to the author,_________. A. war is the only way to solve international disputes B. war will be less dangerous because of the improvement of weapons C.it is impossible for man to live without war D. war must be abolished if man wants to survive

大学英语一题库阅读理解_试卷_答案

大学英语一阅读理解 一、阅读理解（共505题,共101分） 1. Few laws are so effective that you can see results just days after they take effect. But in the nine days since the federal cigarette tax more than doubled—to $1. 01 per pack—smokers have jammed telephone “quit lines” acro ss the country seeking to kick the habit. This is not a surprise to public health advocates. They’ve studied the effect of state tax increases for years, finding that smokers, especially teens, are price sensitive. Nor is it a shock to the industry, which fiercely fights every tax increase. The only wonder is that so many states insist on closing their ears to the message. Tobacco taxes improve public health, health, they raise money and most particularly, they deter people from taking up the habit as teens, which is when nearly all smokers are addicted. Yet the rate of taxation varies widely. In Manhattan, for instance, which has the highest tax in the nation, a pack of Marlboro Light Kings cost ＄10.06 at one drugstore Wednesday. Charleston, S, C., where the 7-cent-a-pack tax is the lowest in the nation. The price was $4. 78. The influence is obvious. In New York, high school smoking hit a new low in the latest surveys—13.8%, far below the national average. By comparison, 26% of high school students smoke in Kentucky, Other low-tax states have similarly depressing teen-smoking records. Hal Rogers, Representative from Kentucky, like those who are against high tobacco taxes, argues that the burden of the tax falls on low-income Americans “who choose to smoke.” That’s true, But there is more reason in keeping future generations of low-income workers from getting hooked in the first place, As for today’s adults, if the new tax drives them to quit, they will have more to spend on their families, cut their risk of cancer and heart disease and feel better. （1分） (1) The text is mainly about___________. （0.2分） A.the price of cigarettes B.the rate of teen smoking C.the effect of tobacco tax increase D.the differences in tobacco tax rate 标准答案：C (2) What does the author think is a surprise? （0.2分） A.Teen smokers are price sensitive. B.Some states still keep the tobacco tax low. C.Tobacco taxes improve public health. D.Tobacco industry fiercely fights the tax rise. 标准答案：B (3) The underlined word "deter” in Paragr aph 3 most probably means . （0.2分） A.discarding B.remove C.benefit D.free 标准答案：A (4) Rogers’ attitude towards the low-income smokers might be that of . （0.2分） A.tolerance B.unconcern C.doubt D.sympathy 标准答案：D (5) What can we learn from the last paragraph? （0.2分） A.The new tax will be beneficial in the long run. B.Low-income Americans are more likely to fall ill.