第一篇：山西省二○○五年專升本招生考試試題

山西省二○○五年專升本招生考試試題

實(shí)用英語（003）

Part Ⅰ.Structure(1 point×20=20 points)Directions: This part is to test your ability to construct grammatically correct sentences.It consists of 2 sections.Section A Directions: In this section, there are 10 incomplete sentences.You are required to complete each one by deciding on the most appropriate word or words from the 4choices marked A, B, C and D.Write your answers on the ANSWER SHEET.1.This year the factory turned ____twice as many bicycles as it did last year.A.down B.off C.to D.out 2.The taxi is _____in this little town, but most people seem to prefer the bus.A.valuable B.available C.acceptable D.considerable 3.____had professor Smith finished his report when stormy applause broke out.A.scarcely B.no sooner C.Never D.Seldom 4.We don't agree with his view ____there is no advantage in introducing the new method.A.which B.that C.what D.when 5.The noise around was terrible, but they had to ____it A.put up with B.keep up with C.come up with D.catch up with 6.He prefers to read books ____watch TV.A.other than B.better than C.rather than D.more than 7.I'm pleased with ____ you have told me.A.that B.all that C.all what D.which 8.The prices of the products have been ____ steadily in the past few years.A.risen B.raised C.arisen D.aroused 9．There isn’t ____ good news in today's newspaper.A.many B.much C.little D.a few 10.When ____ ,the novel will become one of the best-sellers of the year.A．publishing B.being published C.have published D.published Section B Directions: There are 10 incomplete statements here.You should fill in each black with the proper form of the word given in the brackets.Write the word or words in the corresponding space on the ANSWER SHEET.11.The France have put forward a(propose)___________ for a joint project.12.Without a protection program, experts feat that lowland forests are likely(vanish)_________ within five years.13.Many a man ____________(think)life is meaningless without a purpose.14.He is so stupid that he seems to be(capable)___________ to understand the simple instructions.15.Children from(break)____________ families seem to be more self-dependant and prefer acting on their own.16.He was found guilty of crime and put into prison that is the place for punishing the(crime)__________.17.The husband has almost been driver mad by his wife's(end)____________ complaints.18.I'm sure there is a bank somewhere in the(neighbour)____________ of the railway station.19.The little boy finally managed(find)__________ what he was looking for.20.He has decided to devote(him)____________ to helping blind people.Part Ⅱ.Reading Comprehension(1 point×20=20 points)Directions: There are four reading passages in this part.Each passage followed by some questions or unfinished statements.For each of then there are four choices marked A,B,C and D.Write your answers on the ANSWER SHEET.1 The sale of gods and services is not restricted, to local regional or national markets;it often takes place on international basis.Nation import goods that they lack or cannot produce as efficiently as other nations, and they export goods that they can produce more efficiently.This exchange of goods and services in the world, or global market is known as international trade.There are there main benefits to be gained form this type of exchange.First, international trade marks scarce goods available to nations that need or desire them.When a nation lacks the resources needed to produce goods domestically, it may import them form anther country.Second, international trade allows a nation to specialize in production of those goods for which it is particularly suited.This ofter results in increased output, decreased costs, and higher national standard of living.Natural, human, and technical resources help determine which products a nation will specialize in.There are two economic principles that help explain how and when specialization is advantageous.According to the theory of absolute advantage, a nation ought to specialize in the goods that it can produce more cheaply than its competitors or in the goods that no other nation is able to produce.According to the theory of comparative advantage, a nation ought to concentrate on the products that it can produce most efficiently and profitably.The third benefit of international trade is its political effects.Nations that trade together develop common interests which may help them overcome political differences.Economic cooperation has been the foundation for many political alliances.21.Nations import goods they __________.A.produce efficiently B.specialize in C.lack or can't produce efficiently D.do not need or desire 22.Specialization often results in ___________.A.increased output B.decreased costs C.higher standard of living D.all of the above 23.What is the best title for this passage? A.Three Benefits B.Why Nations Trade C.What is International Trade D.Two Economic Principles 24.According to the passage, if the U.S is able to specialize in the computer industry, it is due to its ___________ resources.A.natural B.technical C.human D.international 25.Here are some advantages of international trade concerning importing nations except ___________.A.A great variety of goods is available B.The national standard of living is raised C.The international market gets flooded D.Foreign competition endangers domestic industries 2

To be good teacher, you need some of the gifts of a good actor: you must be able to hold the attention and the interest of your audience;you must be a clever speaker, with a good, strong, pleasing voice which is fully under your control;and you must be able to act what you are teaching, in order to make its meaning chlear.The fact that a good teacher has some of the gifts of a good actor doesn't mean that he will indeed be able to act well on the stage, for there are very important differences between the teacher's work and the actor's.The actor has to speak words which he has learnt by heart;he has to repeat exactly the same words each time he plays a certain part, even his movements and the ways in which he uses his voice are usually fixed beforehand.What he has to do is to make all these carefully learnt words and actions seen natural on the stage.A good teacher works in quite a different way.His audience takes an active part in his play : they ask and answer questions, they obey orders, and if they don't understand something ,they say so.The teacher therefore has to suit his act to the needs of his audience, which is his class.He can not learn his part by heart, but must invent it as he goes along.26.What is the passage about? A.How to become an ordinary teacher.B.What a good teacher should do.C.What teachers and actors could learn form each other.D.The similarities and differences between a teacher's work and an actor's.27．The world “gifts” in line 2 means____________.A.presents B.talents C.something belonging to a good actor D.the way a teacher should act in class 28.In what way is a teacher's work different form an actor's? A.The teacher must learn everything by heart.B.He knows to control his voice bettor than an actor.C.He has to deal with unexpected situations.D.He has to use more facial expressions.29.Which of the following is true? A.A teacher has no learn by heart what exactly he is going to say in class.B.A teacher cannot decide beforehand what exactly he is going to say in class.C.A teacher voice must be nicer than an actor's.D.A teacher must have a better memory than an actor.30.According to this passage, which is the best title? A.Teacher and Actors B.Educational system C.A Good Teacher D.How to Become a Good Actor 3

Albert Einstein had s great effect on science and history, greater than only a few other men have achieved.An American university president once commented that Einstein had created a new outlook, a new view of the universe.It may be some time before the average mind understand fully the identity of time and space and on but even ordinary men understand now that the universe is something larger than ever thought before.By 1914 the young Einstein had gained world fame.He accepted the offer to become a professor at the Prussian Academy of Science in Berlin.He had few duties.little teaching and unlimited opportunities for study, but soon his peace and quite were broken by the First World War.Einstein hated violence.the misery(悲慘)of war affected him deeply, and he sat unhappily in his office doing little.He lost interest in his research.Only when peace came 1918 was he able to get back to work.In the years following World War Ⅰhonors were increasingly heaped on him.He became the head of the Kaiser Whihem Institute of Theoretical Physics.In 1921 he won the Nobel prize, and he was honored in Germany until the rise of rise of Nazism when he was driven form Germany because he was a Jew.31.The main idea of the first paragraph is _________________.A.the time when people know Einstein B.the filling of an American collage president C.the change in human thought produced by Einstein D.the difficulty of Einstein's thought to teacher.32.according to the American university president,____________.A.everyone understands Einstein's theory today.B.Einstein achieved more than any other scientists in history C.the theory of relativity can be quickly learned by everyone.D.Our ideas about the universe are different today because of Einstein.33.According to paragraph 2, Albert Einstein,__________.A.was a famous chemist B.herded a research institute C.was famous in the world D.enjoyed reading about war 34.According to the passage Einstein did his greatest work_____________.A.during World War I B.when he was young C.when Nazism rose D.between 1906~1915 35.It may be concluded that____________.A.Albert Einstein was forced to serve in the German army.B.Albert Einstein had no other interests besides science.C.Germans usually have a high respect for science.D.his reputation was ruined because of his work during World War I.4

About the year 1900.a small, dark-haired boy named Charles Chaplin was often seen waiting outside the back entrances of Loneon theatres.He looked thin and hungry but his blue eyes were determined.He was hoping to get work in show business for he could sing and dance.His parents were music hall artists and he had been born into the life of the stage.And, although his own boyhood was painfully hard ,he know how to mark people laugh.His own father had died form drinking too much.And his mother wasn't really able to look after Charles and his elder half-brother.Sid, because she was often sick in mind and had to be sent into hospital.Even when she was home with them she seemed to live in a different world.Her illness made the boys very sad.As young men, he and his brother traveled to American in a small company of actors and acted in various cities.One day Charles was invited to join a new company that was making film comedies(喜劇).He accepted the offer and soon because popular.By the time he was thirty, Chaplin was the greatest, best known, and best loved comedian in the world.He had formed his own film-marking company and was writing and producing his own films.He was welcome by excited crowds who surrounded him wherever he went.But he worked very hard and had few close friends.36.Charles Chaplin lived in _______when he was a boy.A.America B.Ireland C.London D.a different world 37.Chaplin hoped _________ even in his childhood.A.to sing and dance B.to travel to American C.to produce film D.to be an actor 38.From the passage, we know that Chaplin's mother_____________.A.was a dance artist B.stayed at home everyday C.had some mental illness D.could look after her family 39.After he accepted the offer by ______, Chaplin became successful and popular.A.a comedy film company B.a small company of actors C.his elder brother Sid D.a famous company 40.When he was _______, he said his own film-making company.A.a child B.about thirty years old C.going to American D.very old

Part Ⅲ.Cloze(1 point×20=20 points)When Mr.Finch retired, he bought a small cottage in s seaside village.The cottage was built 41 fifteen eighty-eight, but was in very good 42 , Mr.Finch was looking forward 43 a quiet life, but in the summer holidays he got a 44 , Hundreds of tourists came to the seaside village.Mr.Finch's cottage was the 45 interesting building in the village and many of the tourists 46 to see it.Form morning till night there were tourists outside the cottage.They kept 47 through windows and many of them even went into Mr.Finch's garden.This was too 48 for Mr.Finch.He decided to drive the unwelcome victors 49, so he put notice in the window.The notice said: 'if you want to 50 your curiosity, come in and look round.51: ten pence.' Mr.Finch was sure that the visitors would stop 52.But he was wrong.The 53 of visitors increased and Mr.Finch 54 every day showing them round his cottage, 'I came here to 55, not to work as a guide,' he 56.In the end ,he sold the cottage.57 bought a small, modern 58.It is an uninteresting little 59 and no one wants to see it.But it is 60 quiet and peaceful!

41.A.in B.at C.on D.of 42.A.situation B.place C.condition D.area 43.A.on B.at C.for D.to 44.A.fear B.frighten C.surprising D.shock 45.A.more B.less C.most D.much 46.A.arrived B.came C.went D.walked 47.A.looked B.to look C.looking D.look 48.A.many B.much C.great D.more 49.A.up B.off C.away D.out 50.A.have B.make C.get D.satisfy 51.A.Price B.Pay C.Money D.Expense 52.A.to come B.come C.came D.coming 53.A.statistics B.digit C.number D.numbers 54.A.took B.spent C.used D.offered 55.A.retire B.spent C.enjoy D.relaxing 56.A.said B.talked C.complained D.told 57.A.and B.then C.so D.as 58.A.room B.house C.garden D.village 59.A.place B.space C.point D.scene 60.A.completely B.certainly C.clearly D.greatly Part Ⅳ.Translation from English into Chinese(4 point×5=20 points)1.“Please do let me in!They are searching for me.”, he begged.(副詞譯成動詞)2．They are going to build a school for the blind and the deaf.(形容詞譯成名詞)3．But listen, I met a man, who said you could hire.(定語從句的譯法)4．They, not surprisingly, did not respond at all.(分句法)5．Robert Finn was dismissed by the boss of the factory.（被動語態(tài)的譯法）Part Ⅴ.Writing(20 points)

Directions : This part is going to test your ability to do practical writing.You are required to write an invitation letter according to the information given in Chinese below.以個(gè)人名義給楊先生寫一封邀請函，邀請他訪問本翻譯研究中心： 1． 時(shí)間：邀請楊先生于1991年8月至9月末。

2． 本研究中心同行對與中國同行增加接觸和加強(qiáng)合作很感興趣，并期待他對南京大學(xué)以及整個(gè)中國的翻譯教學(xué)與研究工作狀況作介紹。

3． 請他盡早告知到達(dá)的時(shí)間，以便安排住宿、會議等。

第二篇：山西省2010年專升本招生考試試題

2010年專升本高代試題

一、選擇題（4小題）

1.向量在基下的坐標(biāo)

2.兩向量正交的條件

3.實(shí)系數(shù)多項(xiàng)式因式分解定理

4.AB=0，則R（A）+R（B）不超過n

二、填空題（4小題）

1.g(x)?x2?1,f(x)?x3?2x2?2x?3,求g(x)除f(x)的余式（）2.?1?(1,0),?2?(0,1),則由(?1,?2)到(?2,??1)的過渡矩陣（）

3.A是正交矩陣，則A?（）

三、證明題（四小題）

1.若(f(x),g(x))?1,則(f(x),f(x)?g(x))?(g(x),f(x)?g(x))?1

2.①(P?1AP)2?P?1A2P ②(P?1AP)m?P?1AmP ③P?1AP?A

3.證明向量空間的兩個(gè)子空間的交是子空間。4.?是歐幾里得空間的一個(gè)單位向量，???Rn,?(?)???k(?,?)?,k?R，證明：①?是線性變換。②求k,使?為正交變換。

三、計(jì)算題（4小題）

1.求f(x)?x4?x3?x2?x?6的有理根.?1?a1?1?a2?

2.求行列式?1?a3?

??

?1?an?2?a12?a22?a3?2?an3?a13?a23?a3?3?an?????n?a1??n?a2?n?a3? ???n?an??

?x1?2x2?x3?x4?1??3x1?7x2?x3?2x4?23.解方程組? 4x?9x?3x?3124?

?2x?5x?2x?x?1234?1

?5

?4.在實(shí)數(shù)域上，矩陣A??0

?0?03?20???2是否可對角化？若可對角化，求可逆矩陣?3??

C，使C?AC為對角形

第三篇：山西省專升本考試試題

山西省專升本考試試題 數(shù)據(jù)結(jié)構(gòu)試題1(222)

一、是非題(下列各題，你認(rèn)為正確的，請?jiān)陬}干的括號內(nèi)打“√”，錯(cuò)的打“×”。每題1分，共15分）

1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面...............()

2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。......()

3、從本質(zhì)上看，文件是一種非線性結(jié)構(gòu)。..................()

4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。.......................()

5、棧和隊(duì)列邏輯上都是線性表。..........................()

6、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)........()

7、單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的第一個(gè)結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)。.................................................()

8、對某一確定的可利用空間表，給定一串內(nèi)存請求，若采用最佳適配和首次適配這兩 種方法之中的一種能滿足該串請求，則也一定能用另一種方法滿足該串請求。()

9、多維數(shù)組是向量的推廣。..............................()

10、設(shè)串S=a1a2...ai...aj...an,則有ord(ai)>ord(aj)。....()

11、設(shè)串S的長度為n,則S的子串個(gè)數(shù)為n(n+1)/2。...........()

12、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。................()

13、在拓樸排序序列中，任意兩個(gè)相繼結(jié)點(diǎn)Vi和Vj都存在從Vi到Vj的路徑。()

14、網(wǎng)絡(luò)的最小代價(jià)生成樹是唯一的。.....................()

15、磁帶是順序存取的外存儲設(shè)備。.......................()

二、填空題(每空1分，共10分）

1、在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)(),且存在一條從根到該結(jié)點(diǎn)的()。

2、評價(jià)數(shù)據(jù)結(jié)構(gòu)的兩條基本標(biāo)準(zhǔn)是：()和()。

3、對于順序存儲的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行()運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行()運(yùn)算時(shí)，可能發(fā)生棧的下溢。

4、對于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于()。

5、若S1=‘linked￡st',S2='ring',則S1//S2=()。

6、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為(),最多為()。

三、單選題(在本題的每一小題的備選答案中，只有一個(gè)答案是正確的，請把你認(rèn)為正確答案的題號，填入題干的括號內(nèi)。多選不給分。每題3分，共9分)

1、對于順序存儲的隊(duì)列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為......................()

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n個(gè)記錄直接插入排序所需的記錄最小移動次數(shù)是.......()⑴.2(n-1)

⑵.2n

⑶.(n+3)(n-2)/2

⑷.n2/2

3、現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為..............................⑴.向量 ⑵.樹 ⑶.圖 ⑷.二叉樹

四、簡單應(yīng)用題(第1題6分，其它題每題3分，共18分）1已知稀疏矩陣如下：

⑴請寫出該稀疏矩陣順序存儲的帶輔助行向量的二元組表示。⑵請寫出該稀疏矩陣鏈接存儲的帶行指針向量的單鏈表示。

2在包含n個(gè)關(guān)鍵碼的線性表里進(jìn)行順序查找，若查找第i個(gè)關(guān)鍵碼的概率為pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功檢索的平均比較次數(shù)。

3、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1，試問高度為k≥

1、非葉結(jié)點(diǎn)的度數(shù)等于1的樹有多少棵？

4、給出下列二叉樹的前序序列。

5、設(shè)二叉樹t的對稱序序列為BADCE，后序序列為BDECA，請給出二叉樹。

五、綜合題(每題4分，共16分)

1、假設(shè)有如下關(guān)鍵碼及其散列函數(shù)值：

key ABCD ABDC ACBD ACDB BDAC BACD CADB CBDA

h(key)4 4 0 1 2 3 6 5

基本存儲區(qū)編址為0--7，請用建立分離的同義詞子表的方法解決碰撞問題，畫出其存儲圖式。

2、下面列舉的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？

3設(shè)有50個(gè)值不同的元素存于內(nèi)存一片連續(xù)單元中，若用順序選擇的方法，選出這50個(gè)元素的最大值和最小值則至少需要97次比較。請給出另一種選出最大值和最小值的方法，其比較次數(shù)一定少于97次，說明該方法的操作過程和比較次數(shù)。4 快速排序在什么情況下，所需記錄之關(guān)鍵碼的比較次數(shù)為最多？此時(shí)記錄之關(guān)鍵碼比較次數(shù)應(yīng)為多少？

六、算法設(shè)計(jì)題(第1、2題，每題8分，第3題6分，第4題10分，共32分)

1、雙鏈表結(jié)點(diǎn)類型和變量說明如下： TYPE pointer=↑node;

node=RECORD

info:datatype;

llink,rlink:pointer

END;

double=RECORD

head,rear:pointer

END;

VAR DL:double;

p,q:pointer;

設(shè)DL.head和DL.rear已分別指向該雙鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)。下述算法應(yīng)實(shí)現(xiàn)的操作為：在信息值為x0的結(jié)點(diǎn)(設(shè)該結(jié)點(diǎn)一定存在)之后，插入信息值為x1的新結(jié)點(diǎn)。試填充算法中的空框，使該算法正確。⑴[置初值] P←DL.head ⑵[查找]

循環(huán)當(dāng)P↑info≠x0時(shí)，反復(fù)執(zhí)行

⑶[準(zhǔn)備結(jié)點(diǎn)〕 new(q)；q↑.info←x1 ⑷[插入〕 若P=DL.rear

則q↑.rlinknil；q↑.llinkP；、1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面...............(y)

2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。......(y)

3、從本質(zhì)上看，文件是一種非線性結(jié)構(gòu)。..................(n)

4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。.......................(n)

5、棧和隊(duì)列邏輯上都是線性表。..........................(y)

6、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)........(n)

7、單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的第一個(gè)結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)。.................................................(?)

8、對某一確定的可利用空間表，給定一串內(nèi)存請求，若采用最佳適配和首次適配這兩 種方法之中的一種能滿足該串請求，則也一定能用另一種方法滿足該串請求。(n)

9、多維數(shù)組是向量的推廣。..............................(y?)

10、設(shè)串S=a1a2...ai...aj...an,則有ord(ai)>ord(aj)。....(n)

11、設(shè)串S的長度為n,則S的子串個(gè)數(shù)為n(n+1)/2。...........(n)

12、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。................(n)

13、在拓樸排序序列中，任意兩個(gè)相繼結(jié)點(diǎn)Vi和Vj都存在從Vi到Vj的路徑。(n)

14、網(wǎng)絡(luò)的最小代價(jià)生成樹是唯一的。.....................(n)

15、磁帶是順序存取的外存儲設(shè)備。.......................(y?)

二、填空題(每空1分，共10分）

1、在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)(前驅(qū)),且存在一條從根到該結(jié)點(diǎn)的(路徑)。

2、評價(jià)數(shù)據(jù)結(jié)構(gòu)的兩條基本標(biāo)準(zhǔn)是：(存貯需要量)和(運(yùn)算的時(shí)間效率)。

3、對于順序存儲的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行(push)運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行(pop)運(yùn)算時(shí)，可能發(fā)生棧的下溢。

4、對于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于(null)。

5、若S1=‘linked￡st“,S2=”ring",則S1//S2=(linked￡string)。

6、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為(k),最多為((2^k)-1)。

三、單選題(在本題的每一小題的備選答案中，只有一個(gè)答案是正確的，請把你認(rèn)為正確答案的題號，填入題干的括號內(nèi)。多選不給分。每題3分，共9分)

1、對于順序存儲的隊(duì)列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為......................(d)

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n個(gè)記錄直接插入排序所需的記錄最小移動次數(shù)是.......(a)

⑴.2(n-1)

⑵.2n

⑶.(n+3)(n-2)/2

⑷.n2/2

3、現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為..............................b

⑴.向量 ⑵.樹 ⑶.圖 ⑷.二叉樹 動詞短語是指動詞和介詞、副詞或名詞的習(xí)慣搭配。有關(guān)動詞短語的測試點(diǎn)主要涉及結(jié)構(gòu)上選用恰當(dāng)?shù)拇钆湓~，不同搭配含意上的辨異及不同短語的辨異。需掌握以下要點(diǎn)：

1、根據(jù)動詞短語的不同特點(diǎn)，掌握其運(yùn)用規(guī)律。(I)動詞+副詞(不及物)Harry turned up after the party when everyone had left.(2)動詞+副詞(及物)Please turn every light in the house off.2、熟悉同一動詞和不同介詞或副詞、不同的動詞和同一介詞或同一副詞搭配在意義上的差異。

(1)同一動詞和不同介詞搭配時(shí)，意義上的差異。如：①hear from收到?的來信，hear of聽說。②look after照料，look at看，look for尋找。(2)同一動詞和不同副詞搭配時(shí)，意義上的差異。如：①ring back回電話, ring off掛斷電話, ring up打電話②put away放好, put on穿，上演, put up掛起，舉起

(3)不同動詞和同一介詞搭配時(shí)，在意義上的差異。如：look for尋找, call for去取(某物)，去接(某人), ask for請求, wait for等候, send for派人去叫。

(4)不同動詞和同一副詞搭配時(shí)，在意義上的差異。如：①break out發(fā)生，爆炸, carry out進(jìn)行，開展, go out熄滅, hand out分發(fā), let out放出, look out當(dāng)心, sell out賣完, set out出發(fā), take out取出, work out算出。②break down出毛病, come down落下來, get down下車, take down取下, write down寫下。動詞短語

是考查的一個(gè)熱點(diǎn)，從題設(shè)上看，主要有以下幾個(gè)方式：

1）同一個(gè)動詞，后面加上不同的小品詞（即介詞或副詞）；

2）不同的動詞，后面加上相同的小品詞；

3）動詞不同，小品詞也不同。最后一種應(yīng)該是最難的，因?yàn)樗疾槊鎻V，且靈活多變。動詞短語在語言中具有極強(qiáng)的生命力和表現(xiàn)力?？v觀近幾年考試，集中考查的動詞短語主要由make，take，set，give，put，carry，come，get，keep，look，cut等動詞構(gòu)成。常見高頻動詞短語 1.break break away 擺脫；逃跑

break down（機(jī)器）出故障；中斷；分解 break into 闖入；打斷；突然中斷 break off 中斷；折斷；突然停止 break out 突然發(fā)生；爆發(fā)

break through 突破；克服；掙脫而出 break up 打碎；中斷；分解

break in 破門而入；打斷（談話）；

1.When he heard his sentence，the man _broke down_ ． 2.Your health will _break down__if you work too hard． 3.Don‘t __break in__ when your teacher is speaking． 4.The two countries _broke off_ their relations last month 2.bring bring about 引起；造成

bring down 使倒下；使下降；使受挫折 bring forward 提出；提前（=put forward）bring into operation實(shí)施；使生效 bring out 顯示出來；出版；生產(chǎn) bring up 提出；教育；培養(yǎng)；吐出 bring back 把---送回；使想起；恢復(fù) bring in 引進(jìn)；掙得 3.call call for 需要；要求；邀請 call off 取消；停止 call on 看望；號召

call up 打電話；使人想起；召集 call at 訪問

call in 請來；召集 call back 回電話；召回

1.We called __at__ Mike's house yesterday.2.All ships sailing on the oceans call __for_ help by radio in English.3.I'll call __for_ my uncle at Beijing Railway Station.4.Let's call ___in__ a doctor for the little girl.5.Many of these songs called ___on_ the workers to take up the struggle.6.I shall call __on___ him tomorrow 4.Come Come at

攻擊;向...沖去 come about 發(fā)生

come across 偶遇；碰到；講清楚 come along 進(jìn)展；成功；一道走 come down

下降；病倒；傳下來 come off 發(fā)生；舉行；成功 come on 快點(diǎn)；走吧；有進(jìn)展 come out 出來；結(jié)果是出版

come round/around再現(xiàn)；恢復(fù)知覺；改變看法 come through 經(jīng)歷；獲得成功 come to 蘇醒；達(dá)到；總數(shù)為

come up 發(fā)生；走上前去;(時(shí)間)快到 come up to 達(dá)到（高度、程度）；符合 come up against 碰到（困難）come up with 趕上；提出

1.I came across him first in Beijing.2.Come on, try it again.3.I'll help you too if any beast comes at you.4.It is impossible for a dead animal to come 5.The airplane came down in that field.5.cut cut across 繞勁道穿過；超越；遮住 cut back 削減；終止；急忙返回 cut down 削減；減少

cut in 插嘴；打斷；突然出來 cut off 切斷；中斷；隔絕

to.cut out 刪掉；戒掉

cut short 中斷；打斷；縮短

1.Let‘s cut out the unimportant details．

2.The rope is two feet longer than we needed，so we cut off the extra length． 3.The telephone operator cut us off before we had finished our conversation． 4.The telephone operator cut in and said that I had already spoken 3minutes 6.carry

carry on 繼續(xù)；堅(jiān)持 carry out 執(zhí)行；實(shí)施

carry through 幫助度過難關(guān)；完成；實(shí)現(xiàn) 7.die die away 漸弱

die down 熄滅；平靜下來 die of 因----（?。┧劳?/p>

die from 因----（外部原因）死亡 die out 滅絕；絕種

be dying to do sth.迫切想做某事

1.He carried out the plan without difficulty． 2.Perseverance will carry a man through．

3.I expect my son to carry on the family tradition 8.give give away 贈送；頒發(fā)；泄露；告發(fā)；失去

give out 分發(fā)；公布；公開；用完（vi）;耗盡（vi）give off 發(fā)出；放出

give up 放棄；自首；將-----交給某人（to sb.）;對某人不報(bào)希望（on sb.）give in 屈服；投降；讓步；上交；呈交

1.In those days, he used to give away a part of his income to help his friend.2.Both sides argued with reason, and neither would give in.3.If they are burned, they give off poisonous gases.4.When they made ready to climb the next ridge（山脊），they found that their oxygen had given out。9.go go along 進(jìn)展；陪同前往

go by 時(shí)間過去；經(jīng)過；遵守 go down 下降；下沉；下跌

go for 去；選擇；想要；攻擊（用語言）

go in for 從事；愛好；參加（選拔賽、考試等）go into 研究；調(diào)查，從事

go off 離開；爆炸；食品變壞；斷電；熄滅；（與副詞連用或用于疑問句）進(jìn)行；發(fā)生 go on 繼續(xù)進(jìn)行；發(fā)生；上場 go out 離開；熄滅；過時(shí)

go over 瀏覽；仔細(xì)查看；檢查；審查 go through 通過；經(jīng)歷（苦難）；仔細(xì)檢查 go up 上升；增長；漲價(jià) 1.The crocodile went _down_ under the water.2.If you never read the newspapers, you'll never know what's going _on_ in the world.3.They went _over_ their lessons together at night.4.The police went _through_ very room of the building.10.get get through 瀏覽；翻閱；經(jīng)歷困難（痛苦）；做完某事 get in 收割；收獲；收集；購買；買進(jìn)；插話 get over 克服；戰(zhàn)勝；熬過；做完；結(jié)束；走完 get on 繼續(xù)；進(jìn)行；上車

get round 傳播；散播；說服某人；回避；避開 get about 四處走動；傳開

get across 傳達(dá)；使---讓人理解 get along/on(with)進(jìn)展；相處

1.The bank robbers used a stolen car to get away_.2.Have you got _back_ the book you lent him? 3.This mistake may get him _into_ difficulties.4.It took us only four minutes to get _through_

the Customs(海關(guān)).5.Before I could get _in_ a word, he had measured me, and was giving orders for evening suits,...1.動詞+about(8)bring about引起,使發(fā)生 care about關(guān)心,對...有興趣 come about發(fā)生 hear about聽說 set about 著手,開始 speak/talk about談?wù)?think about思考

worry about為...擔(dān)心 2.動詞+away(14)blow away吹走 break away擺脫

carry away拿走,使入迷 clear away清除掉,消散 die away逐漸消失 give away背棄,泄露 pass away 去世

put away收拾起來,存起來 send away讓走開 take away拿走 throw away 扔掉 turn away把...打發(fā)走 wash away沖走

wear away磨掉,消耗 3.動詞+at(18)aim at向...瞄準(zhǔn) call at拜訪地點(diǎn) come at 向...襲擊 glance at匆匆一瞥 glare at怒視

knock at敲門,窗等 laugh at嘲笑 look at看,注視 point at指向 4.動詞+back(6)call back回電話 give back歸還 hold back控制住 keep back隱瞞,忍住 look back回顧

take back拿回,收回 5.動詞+down(13)break down壞了,垮了,分解 bring down使...降低,使倒下 burn down 燒毀 calm down平靜下來 come down下落,傳下 cut down削減,砍倒 pass down 傳下來

put down記下,寫下,鎮(zhèn)壓 settle down 安家 slow down慢下來 6.動詞+for(18)apply for申請 ask for要求得到 beg for乞求

call for要求,需要 care for關(guān)心,喜歡 change for用...換 charge for收費(fèi),要價(jià) come for來拿,來取 hope/wish for希望得到 7.動詞+from(9)date from始于...時(shí)候 die from因...而死 differ from與...不同 hear from收到...來信

keep/stop/prevent from不讓...做 learn from向...學(xué)習(xí)result from由于 separate from把...分離開 suffer from受...苦 8.動詞+of(10)approve of贊成

become of發(fā)生...情況,怎么啦 complain of抱怨 consist of由...組成 die of死于 dream of夢到 hear of聽說 speak of 讀到 talk of談到 think of想到 9.動詞+off(21)break off打斷 carry off攜走,帶走 come off脫掉,褪色 cut off切斷,斷絕 fall off跌落,掉下 get off脫下衣服等 get off下車 give off散發(fā)出

go off走開,消失,壞了 10.動詞+on(18)bring on使...發(fā)展 call on拜訪

carry on繼續(xù),進(jìn)行 depend on依靠 feed on以...為生 have on穿著 insist on堅(jiān)持 keep/go on繼續(xù) live on以...為生 look on 旁觀

三詞以上的短語動詞(add up to總計(jì)

break away from擺脫 catch sight of看見 catch up with 趕上 come into being出現(xiàn) do away with廢除 do well in在...干得好 get close to接近

get down to認(rèn)真開始 get into the habit of染上...的習(xí)慣 get on/along with和...相處 get out of逃避,避免 get rid of擺脫 get used to習(xí)慣于 go on with繼續(xù)

help oneself to隨便吃,用 keep an eye on堤防

keep away fro避開,別靠近keep in touch with保持聯(lián)系 keep up with 趕上 look down on 輕視 look forward to盼望 look up to仰望,尊敬 take pride in為...而自豪 take the place of取代

1.Can you make a sentence to the meaning of the phrase? A.show off

B.turn out

C.bring out

D.take in 本題答案為：〔C〕.句意為“你能造一個(gè)句子來闡明這個(gè)短語的意思嗎”？show off意為“炫耀、賣弄”，turn out意為“結(jié)果是（出乎意料）”，take in意為“理解、領(lǐng)悟、受欺騙”，而bring out意為“拿出、解釋、說明”，所以選C.2． His mother had thought it would be good for his character to from home and earn some money on his own.A.run away

B.take away C.keep away D.get away 本題答案為：〔D〕.run away意為“逃跑”，take away意為“拿走、帶走”，keep away意為“使??遠(yuǎn)離或不靠近”，而get away意為“離開”，所以選D.3． He was in hospital for six months.He felt as if he was

from the outside world.A.cut out

B.cut off

C.cut up

D.cut through 本題答案為：〔B〕.cut out意為“裁剪、刪除”，cut up意為“切碎、打傷”，cut through意為“從??中開辟出一條路”，而cut off意為“切斷、中斷”，所以選B.4． It was not a serious illness, and she soon it.A.got over

B.got on with C.got round

D.got out of 本題答案為：〔A〕.get on with意為“進(jìn)展、與??相處”，get round意為“說服、籠絡(luò)某人”，get out of意為“逃走、從??中擺脫出來”，而get over 意為“康復(fù)、復(fù)原”，所以選A 5． Before the war broke out, many people in safe places possessions they could not take with them.A.threw away B.put away

C.gave away

D.carried away 本題答案為：〔B〕.throw away意為“扔掉”，give away意為“泄露、贈送”，carry away意為“帶走、帶離”，而put away意為“把??放起來/收起來、儲存、備用”，所以選B 6． It is certain that he will his business to his son when he gets old.A.take over

B.think over C.hand over

D.go over 本題答案為：〔C〕.take over意為“接管、接收”，think over意為“努力思考”，go over意為“復(fù)習(xí)”，而hand over意為“交接、轉(zhuǎn)移”，所以選C 7． It’s ten years since the scientist on his life’s work of discovering the valuable chemical.A.made for

B.set out

C.took off

D.turned up 本題答案為：〔B〕.make for意為“走向、駛向、有助于、有利于”，take off意為“脫下、起飛、成功、取消”，turn up意為“出現(xiàn)、露面”，而set out意為“開始、著手”，所以選B 8．— for the glass!— It’s OK.I’m wearing shoes.A.Look out

B.Walk out

C.Go out

D.Set out 本題答案為：〔A〕.Walk out意為“走出去”，Go out意為“出去”，Set out意為“出發(fā)、開始、著手”，而Look out for意為“小心、提防”，所以選A.9． He accidently that he had quarreled with his wife and that he hadn’t been home for a couple of weeks.A.let out

B.took care

C.made sure

D.made out 本題答案為：〔A〕.take care 意為“小心、照顧”，make sure意為“確保、確信”，make out意為“使出來”，而let out意為“透露、泄露”，所以選A.10． The final examination is coming up soon.It’s for us to our studies.A.get down to B.get out

C.get back for D.get over 本題答案為：〔A〕.get out意為“使出去/離開、逃脫”，get back for意為“回來、取”，get over意為“爬過、克服、恢復(fù)”，而get down to意為“開始、著手”，所以選A.

第四篇：山西省專升本考試試題

山西省專升本考試試題

數(shù)據(jù)結(jié)構(gòu)試題1(222)

一、是非題(下列各題，你認(rèn)為正確的，請?jiān)陬}干的括號內(nèi)打“√”，錯(cuò)的打“×”。每題1分，共15分）

1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面...............()

2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。......()

3、從本質(zhì)上看，文件是一種非線性結(jié)構(gòu)。..................()

4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。.......................()

5、棧和隊(duì)列邏輯上都是線性表。..........................()

6、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)........()

7、單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的第一個(gè)結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)。.................................................()

8、對某一確定的可利用空間表，給定一串內(nèi)存請求，若采用最佳適配和首次適配這兩

種方法之中的一種能滿足該串請求，則也一定能用另一種方法滿足該串請求。()

9、多維數(shù)組是向量的推廣。..............................()

10、設(shè)串S=a1a2...ai...aj...an,則有ord(ai)>ord(aj)。....()

11、設(shè)串S的長度為n,則S的子串個(gè)數(shù)為n(n+1)/2。...........()

12、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。................()

13、在拓樸排序序列中，任意兩個(gè)相繼結(jié)點(diǎn)Vi和Vj都存在從Vi到Vj的路徑。()

14、網(wǎng)絡(luò)的最小代價(jià)生成樹是唯一的。.....................()

15、磁帶是順序存取的外存儲設(shè)備。.......................()

二、填空題(每空1分，共10分）

1、在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)(),且存在一條從根到該結(jié)點(diǎn)的()。

2、評價(jià)數(shù)據(jù)結(jié)構(gòu)的兩條基本標(biāo)準(zhǔn)是：()和()。

3、對于順序存儲的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行()運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行()運(yùn)算時(shí)，可能發(fā)生棧的下溢。

4、對于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于()。

5、若S1=‘linked￡st',S2='ring',則S1//S2=()。

6、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為(),最多為()。

三、單選題(在本題的每一小題的備選答案中，只有一個(gè)答案是正確的，請把你認(rèn)為正確答案的題號，填入題干的括號內(nèi)。多選不給分。每題3分，共9分)

1、對于順序存儲的隊(duì)列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為......................()

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n個(gè)記錄直接插入排序所需的記錄最小移動次數(shù)是.......()

⑴.2(n-1)

⑵.2n

⑶.(n+3)(n-2)/2

⑷.n2/2

3、現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為..............................⑴.向量

⑵.樹

⑶.圖

⑷.二叉樹

四、簡單應(yīng)用題(第1題6分，其它題每題3分，共18分）

1、已知稀疏矩陣如下：

⑴請寫出該稀疏矩陣順序存儲的帶輔助行向量的二元組表示。

⑵請寫出該稀疏矩陣鏈接存儲的帶行指針向量的單鏈表示。

解：

2、在包含n個(gè)關(guān)鍵碼的線性表里進(jìn)行順序查找，若查找第i個(gè)關(guān)鍵碼的概率為pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功檢索的平均比較次數(shù)。

解：

3、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1，試問高度為k≥

1、非葉結(jié)點(diǎn)的度數(shù)等于1的樹有多少棵？

解：

4、給出下列二叉樹的前序序列。

解：

5、設(shè)二叉樹t的對稱序序列為BADCE，后序序列為BDECA，請給出二叉樹。

解：

五、綜合題(每題4分，共16分)

1、假設(shè)有如下關(guān)鍵碼及其散列函數(shù)值：

key ABCD ABDC ACBD ACDB BDAC BACD CADB CBDA

h(key)4 4 0 1 2 3 6 5

基本存儲區(qū)編址為0--7，請用建立分離的同義詞子表的方法解決碰撞問題，畫出其存儲圖式。

解：

2、下面列舉的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的？

解：

3、設(shè)有50個(gè)值不同的元素存于內(nèi)存一片連續(xù)單元中，若用順序選擇的方法，選出這50個(gè)元素的最大值和最小值則至少需要97次比較。請給出另一種選出最大值和最小值的方法，其比較次數(shù)一定少于97次，說明該方法的操作過程和比較次數(shù)。

解：

4、快速排序在什么情況下，所需記錄之關(guān)鍵碼的比較次數(shù)為最多？此時(shí)記錄之關(guān)鍵碼比較次數(shù)應(yīng)為多少？

解：

六、算法設(shè)計(jì)題(第1、2題，每題8分，第3題6分，第4題10分，共32分)

1、雙鏈表結(jié)點(diǎn)類型和變量說明如下：

TYPE pointer=↑node;

node=RECORD

info:datatype;

llink,rlink:pointer

END;

double=RECORD

head,rear:pointer

END;

VAR DL:double;

p,q:pointer;

設(shè)DL.head和DL.rear已分別指向該雙鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)。下述算法應(yīng)實(shí)現(xiàn)的操作為：在信息值為x0的結(jié)點(diǎn)(設(shè)該結(jié)點(diǎn)一定存在)之后，插入信息值為x1的新結(jié)點(diǎn)。試填充算法中的空框，使該算法正確。

⑴[置初值] P←DL.head ⑵[查找]

循環(huán) 當(dāng)P↑info≠x0時(shí)，反復(fù)執(zhí)行

⑶[準(zhǔn)備結(jié)點(diǎn)〕

new(q)；q↑.info←x1 ⑷[插入〕

若P=DL.rear

則q↑.rlinknil；q↑.llinkP；、答案

1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲方式和數(shù)據(jù)的運(yùn)算三個(gè)方面...............(y)

2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼。......(y)

3、從本質(zhì)上看，文件是一種非線性結(jié)構(gòu)。..................(n)

4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。.......................(n)

5、棧和隊(duì)列邏輯上都是線性表。..........................(y)

6、單鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)點(diǎn)........(n)

7、單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的第一個(gè)結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個(gè)結(jié)點(diǎn)。.................................................(?)

8、對某一確定的可利用空間表，給定一串內(nèi)存請求，若采用最佳適配和首次適配這兩

種方法之中的一種能滿足該串請求，則也一定能用另一種方法滿足該串請求。(n)

9、多維數(shù)組是向量的推廣。..............................(y?)

10、設(shè)串S=a1a2...ai...aj...an,則有ord(ai)>ord(aj)。....(n)

11、設(shè)串S的長度為n,則S的子串個(gè)數(shù)為n(n+1)/2。...........(n)

12、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。................(n)

13、在拓樸排序序列中，任意兩個(gè)相繼結(jié)點(diǎn)Vi和Vj都存在從Vi到Vj的路徑。(n)

14、網(wǎng)絡(luò)的最小代價(jià)生成樹是唯一的。.....................(n)

15、磁帶是順序存取的外存儲設(shè)備。.......................(y?)

二、填空題(每空1分，共10分）

1、在樹結(jié)構(gòu)里，有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，稱為根。非根結(jié)點(diǎn)有且僅有一個(gè)(前驅(qū)),且存在一條從根到該結(jié)點(diǎn)的(路徑)。

2、評價(jià)數(shù)據(jù)結(jié)構(gòu)的兩條基本標(biāo)準(zhǔn)是：(存貯需要量)和(運(yùn)算的時(shí)間效率)。

3、對于順序存儲的棧，因?yàn)闂５目臻g是有限的，在進(jìn)行(push)運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行(pop)運(yùn)算時(shí)，可能發(fā)生棧的下溢。

4、對于單鏈表形式的隊(duì)列，其空隊(duì)列的F指針和R指針都等于(null)。

5、若S1=‘linked￡st“,S2=”ring",則S1//S2=(linked￡string)。

6、設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為(k),最多為((2^k)-1)。

三、單選題(在本題的每一小題的備選答案中，只有一個(gè)答案是正確的，請把你認(rèn)為正確答案的題號，填入題干的括號內(nèi)。多選不給分。每題3分，共9分)

1、對于順序存儲的隊(duì)列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為......................(d)

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n個(gè)記錄直接插入排序所需的記錄最小移動次數(shù)是.......(a)

⑴.2(n-1)

⑵.2n

⑶.(n+3)(n-2)/2

⑷.n2/2

3、現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為..............................b

⑴.向量

⑵.樹

⑶.圖

⑷.二叉樹

第五篇：成考專升本考試試題及答案二

（考試時(shí)間150分鐘）Ⅰ.Phonetics(10 points)Directions: In each of the following groups of words, there are four underlined letter combinations marked A, B, C and D.Compare the underlined parts and identify the one that is different from the others in pronunciation.Mark your answer by blackening the corresponding letter on the Answer Sheet.1.A.mark B.warm C.ward D.war

正確答案是:A 您的答案是:B

------------------

2.A.three B.those C.thank D.theatre

正確答案是:B 您的答案是:

------------------

3.A.wind B.kind C.find D.mind

正確答案是:A 您的答案是:

------------------

4.A.plant B.craft C.grasp D.at

正確答案是:D 您的答案是:

------------------

5.A.now B.knowledge C.bow D.allow

正確答案是:B 您的答案是:

------------------

6.A.says B.plays C.stays D.days

正確答案是:C 您的答案是:

------------------

7.A.leave B.scream C.head D.lead

正確答案是:D 您的答案是:

------------------8.A.resemble B.resist C.resolve D.respect

正確答案是:D 您的答案是:

------------------

9.A.fault B.daughter C.cause D.laugh

正確答案是:D 您的答案是:

------------------

10.A.crew B.new C.few D.dew

正確答案是:A 您的答案是:

------------------

Ⅱ.Vocabulary and Structure(40 points)Directions: There are 40 incomplete sentences in this section.For each sentence there are four choices marked A, B, C and D.Choose one answer that best completes the sentence and blacken the corresponding letter on the Answer Sheet.11.Which is ______ country, the United States or Canada? A.a larger B.larger C.the larger D.the largest

正確答案是:C 您的答案是:

------------------

12.The silk feels ________.A.soft B.softly C.softness D.softy

正確答案是:A 您的答案是:

------------------

13.Two nuclear power stations _______ in the past ten years.A.are built B.have been built C.would be built D.are building

正確答案是:B 您的答案是:

------------------

14.They kept on ______ till they got to the foot of the hill.A.to run B.running C.runing D.run

正確答案是:B 您的答案是:------------------

15.There is much work to do, _______? A.isn’t it B.is there C.isn’t there D.is it

正確答案是:C 您的答案是:

------------------

16._______ as he is, he can’t understand the English film.A.A student of English B.Though a student of English C.Student of English D.Being a student of English

正確答案是:C 您的答案是:

------------------

17.The old in the country _______ taken good care of.A.have B.has C.is D.are

正確答案是:D 您的答案是:

------------------

18.Not a single mistake _______ in the test.A.he made B.did he make C.he has made D.made he

正確答案是:B 您的答案是:

------------------

19.______ my surprise, I got a high grade in this test.A.For B.To C.To be D.On

正確答案是:B 您的答案是:

------------------

20.She never agree _______ you, did she? A.to B.with C.in D.at

正確答案是:C 您的答案是:

------------------

21.Would you mind _______ a photo of you? A.me take B.to take C.my taking D.me to take

正確答案是:C 您的答案是:------------------

22.The lady treats the boy well as if he ______ her own son.A.is B.was C.were D.would be

正確答案是:C 您的答案是:

------------------

23._______ round the city, we were impressed by the city’s new look.A.Taken B.Taking C.To be taken D.Being taken

正確答案是:A 您的答案是:

------------------

24.He had a pain _______ his back.A.on B.with C.in D.onto

正確答案是:C 您的答案是:

------------------

25.The city _______ I was born is on the new railway line.A.which B.that C.on which D.where

正確答案是:D 您的答案是:

------------------

26.I had _______ that I would always remember it.A.so a good experience B.such a good experience C.so good an experience D.such good an experience

正確答案是:B 您的答案是:

------------------

27.______ give us help is welcome.A.Who ever B.Whoever C.No matter who D.Those who

正確答案是:B 您的答案是:

------------------

28.After running for nearly half an hour, I was ________.A.out of place B.out of control C.out of breath D.out of practice

正確答案是:C 您的答案是:------------------

29.The mother told the little boy to do all the things _______.A.on himself B.on his own C.to himself D.by own

正確答案是:B 您的答案是:

------------------

30.You had better _______ a jacket, because it is cold outside.A.take on B.to take on C.put on D.to put on

正確答案是:C 您的答案是:

------------------

31.If you will do that, please take me into ________.A.think B.thinking C.thought D.account

正確答案是:D 您的答案是:

------------------

32.My pen has _______ ink.A.run out of B.a few C.run away D.no little

正確答案是:A 您的答案是:

------------------

33.There are, of course, bad teachers as well as ________.A.good one B.some good C.good ones D.those good

正確答案是:C 您的答案是:

------------------

34.“______ haste, the less speed” is good advice he often gives us.A.More B.The more C.The morer D.Morer

正確答案是:B 您的答案是:

------------------

35.You do look _______.You are not at all like a person who has been ill in bed for years.A.good B.well C.sad D.disappointed

正確答案是:B 您的答案是:

------------------

36.Some people like to eat apples.But some prefer bananas _______ apples.A.to B.for C.with D.against

正確答案是:A 您的答案是:

------------------

37.I _______ here two years ago.A.moved to B.have moved C.have moved to D.moved

正確答案是:D 您的答案是:

------------------

38.He is _______ strong a man ________ he can lift ten stones like this one.A.such…so B.so…that C.such a …that D.so a …for

正確答案是:B 您的答案是:

------------------

39.It _______ they who lent me the television.A.was B.is C.were D.are

正確答案是:A 您的答案是:

------------------

40.A famous Canadian doctor expressed the value of hobbies by saying, “______ man is really happy without a hobby.” A.Not B.Without C.No D.None

正確答案是:C 您的答案是:

------------------

41.Television broadcasts are ________ to an area that is within sight of the sending station of its relay.A.prohibited B.bounded C.limited D.restricted

正確答案是:C 您的答案是:

------------------

42.Many things ________ impossible in the past are common today.A.to consider B.being considered C.considering D.considered

正確答案是:D 您的答案是:------------------

43.My parents wanted _______ me.A.make a scientist B.to make a scientist C.make a scientist of D.to make a scientist of

正確答案是:D 您的答案是:

------------------

44.He has a bad habit of ________ others when they are speaking.A.involving B.investigating C.interfering D.interrupting

正確答案是:D 您的答案是:

------------------

45.I like that new watch very much, but I can’t ________it.A.cost B.offer C.pay D.spend

正確答案是:B 您的答案是:

------------------

46.Tom arrived at the office and discovered that he had _______ his door key.A.lent B.borrowed C.lost D.no

正確答案是:C 您的答案是:

------------------

47.The beautiful scene left a deep _______ on the foreign visitors.A.thought B.idea C.thinking D.impression

正確答案是:D 您的答案是:

------------------

48.The room is a little small;_______ it is so hot.A.in addition B.in addition to C.additional D.adding

正確答案是:A 您的答案是:

------------------

49.I wish I ______ her address yesterday.A.know B.had known C.would known D.knew

正確答案是:D 您的答案是:

------------------

50.It ______ yesterday.The ground is still wet now.A.must have rained B.was raining C.rained D.had rained

正確答案是:A 您的答案是:

------------------

Ⅲ.Cloze(20 points)Directions: For each blank in the following passage, there are four choices given below and marked A, B, C and D.Choose the one that is most suitable and mark your answer by blackening the corresponding letter on the Answer Sheet.Insure means to protect _51_ a loss of money.Most people can budget their money so that their income will cover expected expenses _52_ food, clothing, housing, and public services.But, there is no way to know _53_ who will suffer a crisis(危機(jī))such as a serious illness, fire, flood, or a car accident.Such crises usually _54_ great expense.Even if people could predict crises, it would be hard to save enough money to _55_ the expenses.Insurance is a system _56_ a company collects money from many individuals and then pays certain expenses whenever one of those insured individuals is faced with a certain crisis.An insurance policy _57_ how much the insurance costs and how much the company will pay when a policy holder is faced with a certain crisis.There are many different kinds of insurance, _58_ hospital, motor-car and fire.Insurance can be rather expensive but most people buy insurance of some kind.Insurance is something _59_ people buy and hope they will _60_ need.51.A.for B.from C.against D.with

正確答案是:C 您的答案是:

------------------

52.A.such as B.for example C.that D.the same as

正確答案是:A 您的答案是:

------------------

53.A.predict B.ahead C.in advance D.earlier

正確答案是:C 您的答案是:

------------------

54.A.result from B.make C.take D.result in

正確答案是:D 您的答案是:

------------------

55.A.cover B.pay back C.fill D.make full

正確答案是:A 您的答案是:

------------------

56.A.that B.by which C.what D.where

正確答案是:B 您的答案是:

------------------

57.A.said B.agree C.make sure D.states

正確答案是:D 您的答案是:

------------------

58.A.include B.including C.as well as D.also

正確答案是:B 您的答案是:

------------------

59.A.which B.that C.as D.like 正確答案是:B 您的答案是:

------------------

60.A.never B.ever C.sometimes D.often

正確答案是:D 您的答案是:

------------------

Ⅳ.Reading Comprehension(60 points)Directions: There are four reading passages in this part Each passage is followed by five questions.For each question there are four suggested answers marked A, B, C and D.Choose one best answer and blacken the corresponding letter on the Answer Sheet.Passage One Researchers have found that REM(rapid eye movement)sleep is important to human beings.This type of sleep generally occurs four or five times during one night of sleep lasting five minutes to forty minutes for each occurrence.The deeper a person’s sleep becomes, the longer the periods of rapid eye movement.There are physical charges in the body to show that a person has changed from NREM(non-rapid eye movement)to REM sleep.Breathing becomes faster, the heart rate increases, and, as the name implies, the eyes begin to move quickly.Accompanying these physical changes in the body is a very important characteristic of REM sleep.It is during REM sleep that a person dreams.61.According to the passage, how often does REM sleep occur in one night? A.Once B.Twice C.Four of five times D.Forty times

正確答案是:C 您的答案是:

------------------

62.The word “deeper” in paragraph 1 is closest in meaning to which of the following? A.heavier.B.louder.C.stronger.D.happier.正確答案是:A 您的答案是:

------------------

63.Which of the following shows that a person is NOT dreaming in his sleep? A.His eyes begin to move.B.His breathing becomes faster.C.His heart rate increases.D.His eyes stop moving.正確答案是:C 您的答案是:

------------------

64.The subject of this passage is ________.A.why people sleep B.the human need for REM sleep C.the characteristic of REM sleep D.physical changes in the human body

正確答案是:D 您的答案是:

------------------

65.Which of the following is the best title of the article? A.REM Sleep B.Two Types of Sleep C.Sleepers D.What Happens to Sleepers

正確答案是:A 您的答案是:

------------------

Passage Two The Mother Goose Stories, so well known to children all over the word, are commonly said to have been written by a little old woman for her grandchildren.According to some people, she lived in Boston, and her real name was Elizabeth Vergoose.Her son-in-law, a printer named Thomas Fleet, was supposed to have published the famous stories and poems for small children in 1719.However, no copy of this book has ever been found, and most scholars doubt the truth of this story—and doubt, moreover, that Mother Goose was ever a real person.They point out that the name is a direct translation of the French “Mere I’ Oye.” In 1697 the Frenchman Charles Perrault published the first book in which this name was used.The collection contains eight tales, including “Sleeping Beauty,” “Cinderella,” and “Puss in Boots.” But Perrault did not originate these stories;they were already quite popular in his day, and he only collected them.66.What is suppssed to have happened in 1719? A.Elizabeth Vergoose wrote the first Mother Goose Stories.B.Thomas Fleet published the Mother Goose Stories.C.The Mother Goose Stories were translated into French.D.Charles Perrault published the first Mother Goose Stories.正確答案是:B 您的答案是:

------------------

67.Most scholars consider Mother Goose to be _________.A.a real person B.a book written by a little old woman C.a collection by Elizabeth Vergoose D.a translation from French

正確答案是:D 您的答案是:

------------------

68.When Perrault published the first book in 1679, _______.A.no story of the book had been known to people B.some stories of the book were already well known C.few people were interested in the stories of the book D.stories like “Sleeping Beauty” and “Cinderella” became popular

正確答案是:B 您的答案是:

------------------

69.The name used in the first book published in 1679 is supposed to have been _______.A.Mother Goose B.Mere I’ Oye C.Elizabeth Vergoose D.Charles Perrault

正確答案是:B 您的答案是:

------------------

70.On the basis of this passage, what may be concluded about the real origin of stories “Sleeping Beauty” and “Cinderella”?

A.They were invented by Elizabeth Vergoose.B.They were invented by Thomas Fleet.C.They were invented by Charles Perrault.D.Their writers are unknown.正確答案是:D 您的答案是:

------------------

Passage Three Banks are not ordinarily prepared to pay out all accounts;they rely on depositors(儲戶)not to demand payment all at the same time.If depositors should come to fear that a bank is not safe, that it cannot pay off all its depositors, then that fear might cause all the depositors to appear on the same day.If they did, the bank could not pay all accounts.However, if they did not all appear at once, then there would always be enough money to pay those who wanted their money when they wanted it.Mrs.Elsie Vaught has told us of a terrifying bank run that she experienced.One day in December of 1925 several banks failed to open in a city where Mrs.Vaught lived.The other banks expected a run the next day, and so the officers of the bank in which Mrs Vaught worked as a teller had enough money on hand to pay off their depositors.The officers simply told the tellers to pay on demand.The next morning a crowd gathered in the bank and on the sidewalk outside.The length of the line made many think that the bank could not possibly pay off everyone.People began to push and then to fight for places near the tellers’ windows, The power of the panic atmosphere was such that two tellers, though they knew that the bank was quite all right and could pay all depositors, drew their own money from the bank.Mrs Vaught says that she had difficulty keeping herself from doing the same.71.A bank run happens when _______.A.a bank is closed for one or more days B.too many depositors try to draw out their money at one time C.there is not enough money to pay all its depositors at one time D.tellers of a bank take their own money from the bank

正確答案是:B 您的答案是:

------------------

72.The tellers in Mrs.Vaught’s bank were told to ________.A.explain why they could not pay out all accounts B.pay out accounts as requested C.make the depositors believe that the bank was stand D.pay out money as slowly as possible

正確答案是:B 您的答案是:

------------------

73.The main cause of a bank run is _______.A.loss of confidence B.lack of money C.crowds of people D.inexperienced tellers

正確答案是:B 您的答案是:

------------------

74.Which of the following did Mrs.Vaught say? A.She know that the bank was not sound.B.She feared that too many depositors drawing their money would close the bank.C.She was not able to draw out her money.D.She was tempted to draw out her money.正確答案是:D 您的答案是:

------------------

75.According to the passage, the actions of the depositors of Mrs.Vaught’s bank were affected mainly by the _______.A.ease with which they could get their money B.confidence that Mrs.Vaught showed C.failure of several other banks to open D.confidence shown by other depositors of the bank

正確答案是:C 您的答案是:

------------------

Passage Four One of the greatest problems for those settlers in Nebraska in the last quarter of the previous century was fuel.Little of the state was forested when the first settlers arrived and it is probable that by 1880, only about one-third of the originally forested area remained, down to a mere 1 percent of the state’s 77,000 square miles.With wood and coal out of the question, and with fuel needed year-round for cooking, and during the harsh winter months for heating, some solution had to be found.Somewhat improbably, the buffalo provided the answer.Buffalo chips(干糞塊)were found to burn evenly, hotly, and cleanly, with little smoke and interestingly, no odor, Soon, collecting them became a way of life for the settlers’ children who would pick them up on their way to and from school, or take part in competitions designed to counteract their natural reluctance.Even a young man, seeking to impress the girl he wanted to marry, would arrive with a large bag of chips rather than with a box of candy or a bunch of flowers.76.What is the main topic of this passage? A.The solution to the Nebraska settlers’ fuel problem.B.Life in Nebraska in the late ninteenth century.C.The imporance of the American buffalo.D.Deforestation in Nebraska in the late nineteenth century.正確答案是:A 您的答案是:

------------------

77.Which of the following statements is NOT true? A.Nebraska was not a densely-forested state even before the settlers arrived.B.The children enjoyed collecting the buffalo chips.C.The children spent a lot of time collecting the chips.D.Buffalo chips were satisfactory as a fuel.正確答案是:B 您的答案是:

------------------

78.The passage implies that buffalo chips were needed _______.A.in greater amounts in summer B.in greater amounts in winter C.only in summer D.only in winter

正確答案是:B 您的答案是:

------------------

79.Which of the following does the author not express surprise at? A.The children needed competitions to them.B.The buffalo chips gave off no smell.C.Buffalo chips were the answer to the settlers’ fuel problem.D.Young men took bags of buffalo chips to their girl friends.正確答案是:A 您的答案是:

------------------

80.What’s the best title of the passage?

A.Early Settlers B.One Use of the Buffalo Chips C.Nebraska’s Problems D.How Young Men Express Their Love for Girls

正確答案是:B 您的答案是:

------------------

Ⅴ.Writing(20 points)Directions: For this part, you are allowed 20 minutes to write a letter of about 80 words according to the following situation.你叫李平，是英語系學(xué)生會主席。寫一封信給王教授，請他做一個(gè)有關(guān)中國歷史的報(bào)告。注意信中要包括目的、時(shí)間、日期和地點(diǎn)。

正確答案是:

Ⅴ.Writing May 19,2002 Dear Professor Wang: On behalf of the Student Union of the English Department, I am writing to invite you to give a lecture on Chinese history.We have planned to have such a lecture at 2:30 p· m.in Lecture Hall 419, on May 25.Looking forward to your lecture.Inform us in advance if you can not come.