山西省专升本考试试题

第一篇：山西省专升本考试试题

山西省专升本考试试题 数据结构试题1(222)

一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分，共15分）

1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............()

2、线性表中的每个结点最多只有一个前驱和一个后继。......()

3、从本质上看，文件是一种非线性结构。..................()

4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................()

5、栈和队列逻辑上都是线性表。..........................()

6、单链表从任何一个结点出发，都能访问到所有结点........()

7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................()

8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两 种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。()

9、多维数组是向量的推广。..............................()

10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....()

11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........()

12、一般树和二叉树的结点数目都可以为0。................()

13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。()

14、网络的最小代价生成树是唯一的。.....................()

15、磁带是顺序存取的外存储设备。.......................()

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

1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个(),且存在一条从根到该结点的()。

2、评价数据结构的两条基本标准是：()和()。

3、对于顺序存储的栈，因为栈的空间是有限的，在进行()运算时，可能发生栈的上溢，在进行()运算时，可能发生栈的下溢。

4、对于单链表形式的队列，其空队列的F指针和R指针都等于()。

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

6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(),最多为()。

三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)

1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................()

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n个记录直接插入排序所需的记录最小移动次数是.......()⑴.2(n-1)

⑵.2n

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

⑷.n2/2

3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................⑴.向量 ⑵.树 ⑶.图 ⑷.二叉树

四、简单应用题(第1题6分，其它题每题3分，共18分）1已知稀疏矩阵如下：

⑴请写出该稀疏矩阵顺序存储的带辅助行向量的二元组表示。⑵请写出该稀疏矩阵链接存储的带行指针向量的单链表示。

2在包含n个关键码的线性表里进行顺序查找，若查找第i个关键码的概率为pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功检索的平均比较次数。

3、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1，试问高度为k≥

1、非叶结点的度数等于1的树有多少棵？

4、给出下列二叉树的前序序列。

5、设二叉树t的对称序序列为BADCE，后序序列为BDECA，请给出二叉树。

五、综合题(每题4分，共16分)

1、假设有如下关键码及其散列函数值：

key ABCD ABDC ACBD ACDB BDAC BACD CADB CBDA

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

基本存储区编址为0--7，请用建立分离的同义词子表的方法解决碰撞问题，画出其存储图式。

2、下面列举的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？

3设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。4 快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？

六、算法设计题(第1、2题，每题8分，第3题6分，第4题10分，共32分)

1、双链表结点类型和变量说明如下： TYPE pointer=↑node;

node=RECORD

info:datatype;

llink,rlink:pointer

END;

double=RECORD

head,rear:pointer

END;

VAR DL:double;

p,q:pointer;

设DL.head和DL.rear已分别指向该双链表的头结点和尾结点。下述算法应实现的操作为：在信息值为x0的结点(设该结点一定存在)之后，插入信息值为x1的新结点。试填充算法中的空框，使该算法正确。⑴[置初值] P←DL.head ⑵[查找]

循环当P↑info≠x0时，反复执行

⑶[准备结点〕 new(q)；q↑.info←x1 ⑷[插入〕 若P=DL.rear

则q↑.rlinknil；q↑.llinkP；、1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............(y)

2、线性表中的每个结点最多只有一个前驱和一个后继。......(y)

3、从本质上看，文件是一种非线性结构。..................(n)

4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................(n)

5、栈和队列逻辑上都是线性表。..........................(y)

6、单链表从任何一个结点出发，都能访问到所有结点........(n)

7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................(?)

8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两 种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。(n)

9、多维数组是向量的推广。..............................(y?)

10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....(n)

11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........(n)

12、一般树和二叉树的结点数目都可以为0。................(n)

13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。(n)

14、网络的最小代价生成树是唯一的。.....................(n)

15、磁带是顺序存取的外存储设备。.......................(y?)

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

1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个(前驱),且存在一条从根到该结点的(路径)。

2、评价数据结构的两条基本标准是：(存贮需要量)和(运算的时间效率)。

3、对于顺序存储的栈，因为栈的空间是有限的，在进行(push)运算时，可能发生栈的上溢，在进行(pop)运算时，可能发生栈的下溢。

4、对于单链表形式的队列，其空队列的F指针和R指针都等于(null)。

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

6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(k),最多为((2^k)-1)。

三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)

1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................(d)

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n个记录直接插入排序所需的记录最小移动次数是.......(a)

⑴.2(n-1)

⑵.2n

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

⑷.n2/2

3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................b

⑴.向量 ⑵.树 ⑶.图 ⑷.二叉树 动词短语是指动词和介词、副词或名词的习惯搭配。有关动词短语的测试点主要涉及结构上选用恰当的搭配词，不同搭配含意上的辨异及不同短语的辨异。需掌握以下要点：

1、根据动词短语的不同特点，掌握其运用规律。(I)动词+副词(不及物)Harry turned up after the party when everyone had left.(2)动词+副词(及物)Please turn every light in the house off.2、熟悉同一动词和不同介词或副词、不同的动词和同一介词或同一副词搭配在意义上的差异。

(1)同一动词和不同介词搭配时，意义上的差异。如：①hear from收到„的来信，hear of听说。②look after照料，look at看，look for寻找。(2)同一动词和不同副词搭配时，意义上的差异。如：①ring back回电话, ring off挂断电话, ring up打电话②put away放好, put on穿，上演, put up挂起，举起

(3)不同动词和同一介词搭配时，在意义上的差异。如：look for寻找, call for去取(某物)，去接(某人), ask for请求, wait for等候, send for派人去叫。

(4)不同动词和同一副词搭配时，在意义上的差异。如：①break out发生，爆炸, carry out进行，开展, go out熄灭, hand out分发, let out放出, look out当心, sell out卖完, set out出发, take out取出, work out算出。②break down出毛病, come down落下来, get down下车, take down取下, write down写下。动词短语

是考查的一个热点，从题设上看，主要有以下几个方式：

1）同一个动词，后面加上不同的小品词（即介词或副词）；

2）不同的动词，后面加上相同的小品词；

3）动词不同，小品词也不同。最后一种应该是最难的，因为它考查面广，且灵活多变。动词短语在语言中具有极强的生命力和表现力。纵观近几年考试，集中考查的动词短语主要由make，take，set，give，put，carry，come，get，keep，look，cut等动词构成。常见高频动词短语 1.break break away 摆脱；逃跑

break down（机器）出故障；中断；分解 break into 闯入；打断；突然中断 break off 中断；折断；突然停止 break out 突然发生；爆发

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实施；使生效 bring out 显示出来；出版；生产 bring up 提出；教育；培养；吐出 bring back 把---送回；使想起；恢复 bring in 引进；挣得 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 发生

come across 偶遇；碰到；讲清楚 come along 进展；成功；一道走 come down

下降；病倒；传下来 come off 发生；举行；成功 come on 快点；走吧；有进展 come out 出来；结果是出版

come round/around再现；恢复知觉；改变看法 come through 经历；获得成功 come to 苏醒；达到；总数为

come up 发生；走上前去;(时间)快到 come up to 达到（高度、程度）；符合 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 继续；坚持 carry out 执行；实施

carry through 帮助度过难关；完成；实现 7.die die away 渐弱

die down 熄灭；平静下来 die of 因----（病）死亡

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 赠送；颁发；泄露；告发；失去

give out 分发；公布；公开；用完（vi）;耗尽（vi）give off 发出；放出

give up 放弃；自首；将-----交给某人（to sb.）;对某人不报希望（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 进展；陪同前往

go by 时间过去；经过；遵守 go down 下降；下沉；下跌

go for 去；选择；想要；攻击（用语言）

go in for 从事；爱好；参加（选拔赛、考试等）go into 研究；调查，从事

go off 离开；爆炸；食品变坏；断电；熄灭；（与副词连用或用于疑问句）进行；发生 go on 继续进行；发生；上场 go out 离开；熄灭；过时

go over 浏览；仔细查看；检查；审查 go through 通过；经历（苦难）；仔细检查 go up 上升；增长；涨价 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 浏览；翻阅；经历困难（痛苦）；做完某事 get in 收割；收获；收集；购买；买进；插话 get over 克服；战胜；熬过；做完；结束；走完 get on 继续；进行；上车

get round 传播；散播；说服某人；回避；避开 get about 四处走动；传开

get across 传达；使---让人理解 get along/on(with)进展；相处

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(海关).5.Before I could get _in_ a word, he had measured me, and was giving orders for evening suits,...1.动词+about(8)bring about引起,使发生 care about关心,对...有兴趣 come about发生 hear about听说 set about 着手,开始 speak/talk about谈论 think about思考

worry about为...担心 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把...打发走 wash away冲走

wear away磨掉,消耗 3.动词+at(18)aim at向...瞄准 call at拜访地点 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记下,写下,镇压 settle down 安家 slow down慢下来 6.动词+for(18)apply for申请 ask for要求得到 beg for乞求

call for要求,需要 care for关心,喜欢 change for用...换 charge for收费,要价 come for来拿,来取 hope/wish for希望得到 7.动词+from(9)date from始于...时候 die from因...而死 differ from与...不同 hear from收到...来信

keep/stop/prevent from不让...做 learn from向...学习result from由于 separate from把...分离开 suffer from受...苦 8.动词+of(10)approve of赞成

become of发生...情况,怎么啦 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散发出

go off走开,消失,坏了 10.动词+on(18)bring on使...发展 call on拜访

carry on继续,进行 depend on依靠 feed on以...为生 have on穿着 insist on坚持 keep/go on继续 live on以...为生 look on 旁观

三词以上的短语动词(add up to总计

break away from摆脱 catch sight of看见 catch up with 赶上 come into being出现 do away with废除 do well in在...干得好 get close to接近

get down to认真开始 get into the habit of染上...的习惯 get on/along with和...相处 get out of逃避,避免 get rid of摆脱 get used to习惯于 go on with继续

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

keep away fro避开,别靠近keep in touch with保持联系 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〕.句意为“你能造一个句子来阐明这个短语的意思吗”？show off意为“炫耀、卖弄”，turn out意为“结果是（出乎意料）”，take in意为“理解、领悟、受欺骗”，而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意为“使„„远离或不靠近”，而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意为“进展、与„„相处”，get round意为“说服、笼络某人”，get out of意为“逃走、从„„中摆脱出来”，而get over 意为“康复、复原”，所以选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意为“复习”，而hand over意为“交接、转移”，所以选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意为“出现、露面”，而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意为“出发、开始、着手”，而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意为“爬过、克服、恢复”，而get down to意为“开始、着手”，所以选A.

第二篇：山西省2010年专升本招生考试试题

2010年专升本高代试题

一、选择题（4小题）

1.向量在基下的坐标

2.两向量正交的条件

3.实系数多项式因式分解定理

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.证明向量空间的两个子空间的交是子空间。4.是欧几里得空间的一个单位向量，Rn,()k(,),kR，证明：①是线性变换。②求k,使为正交变换。

三、计算题（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.在实数域上，矩阵A0

003202是否可对角化？若可对角化，求可逆矩阵3

C，使CAC为对角形

第三篇：山西省专升本考试试题

山西省专升本考试试题

数据结构试题1(222)

一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分，共15分）

1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............()

2、线性表中的每个结点最多只有一个前驱和一个后继。......()

3、从本质上看，文件是一种非线性结构。..................()

4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................()

5、栈和队列逻辑上都是线性表。..........................()

6、单链表从任何一个结点出发，都能访问到所有结点........()

7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................()

8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两

种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。()

9、多维数组是向量的推广。..............................()

10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....()

11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........()

12、一般树和二叉树的结点数目都可以为0。................()

13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。()

14、网络的最小代价生成树是唯一的。.....................()

15、磁带是顺序存取的外存储设备。.......................()

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

1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个(),且存在一条从根到该结点的()。

2、评价数据结构的两条基本标准是：()和()。

3、对于顺序存储的栈，因为栈的空间是有限的，在进行()运算时，可能发生栈的上溢，在进行()运算时，可能发生栈的下溢。

4、对于单链表形式的队列，其空队列的F指针和R指针都等于()。

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

6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(),最多为()。

三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)

1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................()

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n个记录直接插入排序所需的记录最小移动次数是.......()

⑴.2(n-1)

⑵.2n

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

⑷.n2/2

3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................⑴.向量

⑵.树

⑶.图

⑷.二叉树

四、简单应用题(第1题6分，其它题每题3分，共18分）

1、已知稀疏矩阵如下：

⑴请写出该稀疏矩阵顺序存储的带辅助行向量的二元组表示。

⑵请写出该稀疏矩阵链接存储的带行指针向量的单链表示。

解：

2、在包含n个关键码的线性表里进行顺序查找，若查找第i个关键码的概率为pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功检索的平均比较次数。

解：

3、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1，试问高度为k≥

1、非叶结点的度数等于1的树有多少棵？

解：

4、给出下列二叉树的前序序列。

解：

5、设二叉树t的对称序序列为BADCE，后序序列为BDECA，请给出二叉树。

解：

五、综合题(每题4分，共16分)

1、假设有如下关键码及其散列函数值：

key ABCD ABDC ACBD ACDB BDAC BACD CADB CBDA

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

基本存储区编址为0--7，请用建立分离的同义词子表的方法解决碰撞问题，画出其存储图式。

解：

2、下面列举的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？

解：

3、设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。

解：

4、快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？

解：

六、算法设计题(第1、2题，每题8分，第3题6分，第4题10分，共32分)

1、双链表结点类型和变量说明如下：

TYPE pointer=↑node;

node=RECORD

info:datatype;

llink,rlink:pointer

END;

double=RECORD

head,rear:pointer

END;

VAR DL:double;

p,q:pointer;

设DL.head和DL.rear已分别指向该双链表的头结点和尾结点。下述算法应实现的操作为：在信息值为x0的结点(设该结点一定存在)之后，插入信息值为x1的新结点。试填充算法中的空框，使该算法正确。

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

循环 当P↑info≠x0时，反复执行

⑶[准备结点〕

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

若P=DL.rear

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

1、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............(y)

2、线性表中的每个结点最多只有一个前驱和一个后继。......(y)

3、从本质上看，文件是一种非线性结构。..................(n)

4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................(n)

5、栈和队列逻辑上都是线性表。..........................(y)

6、单链表从任何一个结点出发，都能访问到所有结点........(n)

7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................(?)

8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两

种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。(n)

9、多维数组是向量的推广。..............................(y?)

10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....(n)

11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........(n)

12、一般树和二叉树的结点数目都可以为0。................(n)

13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。(n)

14、网络的最小代价生成树是唯一的。.....................(n)

15、磁带是顺序存取的外存储设备。.......................(y?)

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

1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个(前驱),且存在一条从根到该结点的(路径)。

2、评价数据结构的两条基本标准是：(存贮需要量)和(运算的时间效率)。

3、对于顺序存储的栈，因为栈的空间是有限的，在进行(push)运算时，可能发生栈的上溢，在进行(pop)运算时，可能发生栈的下溢。

4、对于单链表形式的队列，其空队列的F指针和R指针都等于(null)。

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

6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(k),最多为((2^k)-1)。

三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)

1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................(d)

⑴.R-F

⑵.n+R-F

⑶.(R-F+1)mod n

⑷.(n+R-F）mod n

2、n个记录直接插入排序所需的记录最小移动次数是.......(a)

⑴.2(n-1)

⑵.2n

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

⑷.n2/2

3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................b

⑴.向量

⑵.树

⑶.图

⑷.二叉树

第四篇：山西省二○○五年专升本招生考试试题

山西省二○○五年专升本招生考试试题

实用英语（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.（被动语态的译法）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.以个人名义给杨先生写一封邀请函，邀请他访问本翻译研究中心： 1． 时间：邀请杨先生于1991年8月至9月末。

2． 本研究中心同行对与中国同行增加接触和加强合作很感兴趣，并期待他对南京大学以及整个中国的翻译教学与研究工作状况作介绍。

3． 请他尽早告知到达的时间，以便安排住宿、会议等。

第五篇：专升本考试试题《计算机基础》

一、单项选择题(共70小题，每题1分，共70分。在给出的选项中，只有一项是最准确的，请将你选择的答案写在答题纸上相应位置处)

1.依据计算机采用的主要电子元器件，当前计算机发展处在_________阶段。

A.电子管 B.晶体管

C.大规模和超大规模集成电路 D.中小规模集成电路

2.计算机中表示信息的最小单位是______________

A.位 B.字节

C.字 D.字符

3.计算机的主要特点不包括__________________

A.运算速度快 B.计算精度高

C.显示器尺寸大 D.程序控制自动运行

4.计算机在企业管理中的应用属于_______________

A.科学计算 B.数据处理

C.计算机辅助设计 D.过程控制

5.“神舟七号”飞船应用计算机进行飞行状态调整属于_________

A.计算机辅助制造 B.计算机辅助设计

C.信息管理 D.实时控制

6.有关计算机程序的说法正确的是_____________

A.程序都在CPU中存储并执行 B.程序由外存读入内存后，在CPU中执行

C.程序在外存中存储并执行 D.程序在内存中存储，在外存中执行

7.计算机指令中的操作数部分指出的是_____________

A.数据的操作 B.数据的格式

C.数据或数据的地址 D.数据的编码

8.计算机中选择存储器单元的信号是通过________总线传输。

A.控制 B.地址 C.数据 D.USB

9.某微机内存1G，指该微机有1GB的________

A.RAM B.ROM

C.RAM和ROM D.高速缓存

10.在主存储器和CPU之间加高速缓存，目的是___________

A.解决CPU和主存之间的速度匹配问题

B.扩大主存储器的容量

C.增加CPU中通用寄存器的数量

D.扩大主存储器的容量和增加CPU中通用寄存器的数量

11.计算机系统由_________组成 A.计算机和外部设备 B.外部设备和程序

C.操作系统和应用程序 D.硬件系统和软件系统

12.裸机是指没有装入____________的计算机。

A.应用软件 B.CAD软件 C.任何软件 D.字处理软件

13.在计算机中，外设与CPU__________

A.直接相连 B.经过接口相连

C.无连接标准 D.在生产时集成在一起

14.操作系统的主要功能不包括________

A.处理机管理 B.存储器管理

C.设备管理 D.网站管理

15.提供用户与计算机之间接口的是__________

A.应用软件 B.操作系统

C.输入设备 D.输出设备

16.操作系统的英文缩写为________

A.AO B.OA

C.OS D.OP

17.二进制数1001110110转换成八进制数的结果为_________ A.4D6 B.1238

C.2326 D.4155

18.字符“A”、“a”、“2”、“9”中ASCH码值最大的是___________

A.A B.a

C.2 D.9

19.我国颁布的最新汉字编码标准是___________

A.GB1988 B.BG2312-80

C.BIG5 D.GB18030-2000

20.关于程序和软件，说法正确的是__________

A.程序仅指软件 B.软件包括程序

C.程序包括软件 D.软件仅有有程序

21.资源管理器中不能按___________方式排列图标。

A.名称 B.大小 C.类型 D.内容

22.Windows XP中，通过“用户账户”组件不能进行________操作。

A.记录账户流量 B.创建新账户

C.D.更改账户名称