山西省专升本考试测试试题.docx

山西省专升本考试测试试题.docx

《山西省专升本考试测试试题.docx》由会员分享，可在线阅读，更多相关《山西省专升本考试测试试题.docx（19页珍藏版）》请在冰点文库上搜索。

山西省专升本考试测试试题

山西省专升本考试试题

————————————————————————————————作者：

————————————————————————————————日期：

山西省专升本考试试题

数据结构试题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）modn⑷.（n+R-F）modn

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、假设有如下关键码及其散列函数值：

keyABCDABDCACBDACDBBDACBACDCADBCBDA

h（key）44012365

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

2、下面列举的是常用的排序方法：

直接插入排序，二分法插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。

试问，哪些排序方法是稳定的？

3设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。

请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。

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

此时记录之关键码比较次数应为多少？

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

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

TYPEpointer=↑node;

node=RECORD

info:

datatype;

llink,rlink:

pointer

END;

double=RECORD

head,rear:

pointer

END;

VARDL:

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）modn⑷.（n+R-F）modn

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

⑴.2（n-1）⑵.2n⑶.（n+3）（n-2）/2⑷.n2/2

3、现有一“遗传”关系：

设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为..............................b

⑴.向量　⑵.树　⑶.图　⑷.二叉树

动词短语是指动词和介词、副词或名词的习惯搭配。

有关动词短语的测试点主要涉及结构上选用恰当的搭配词，不同搭配含意上的辨异及不同短语的辨异。

需掌握以下要点：

1、根据动词短语的不同特点，掌握其运用规律。

（I）动词+副词（不及物）

Harryturnedupafterthepartywheneveryonehadleft.

（2）动词+副词（及物）

Pleaseturneverylightinthehouseoff.

2、熟悉同一动词和不同介词或副词、不同的动词和同一介词或同一副词搭配在意义上的差异。

（1）同一动词和不同介词搭配时，意义上的差异。

如：

①hearfrom收到…的来信，hearof听说。

②lookafter照料，lookat看，lookfor寻找。

（2）同一动词和不同副词搭配时，意义上的差异。

如：

①ringback回电话,ringoff挂断电话,ringup打电话②putaway放好,puton穿，上演,putup挂起，举起

（3）不同动词和同一介词搭配时，在意义上的差异。

如：

lookfor寻找,callfor去取（某物），去接（某人）,askfor请求,waitfor等候,sendfor派人去叫。

（4）不同动词和同一副词搭配时，在意义上的差异。

如：

①breakout发生，爆炸,carryout进行，开展,goout熄灭,handout分发,letout放出,lookout当心,sellout卖完,setout出发,takeout取出,workout算出。

②breakdown出毛病,comedown落下来,getdown下车,takedown取下,writedown写下。

动词短语

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

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

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

   3）动词不同，小品词也不同。

最后一种应该是最难的，因为它考查面广，且灵活多变。

动词短语在语言中具有极强的生命力和表现力。

纵观近几年考试，集中考查的动词短语主要由make，take，set，give，put，carry，come，get，keep，look，cut等动词构成。

常见高频动词短语

1.break

breakaway       摆脱；逃跑

breakdown      （机器）出故障；中断；分解

breakinto        闯入；打断；突然中断

breakoff         中断；折断；突然停止

breakout         突然发生；爆发

breakthrough     突破；克服；挣脱而出

breakup         打碎；中断；分解

breakin          破门而入；打断（谈话）；

1.Whenheheardhissentence，theman_brokedown_．

2.Yourhealthwill_breakdown__ifyouworktoohard．

3.Don‘t__breakin__whenyourteacherisspeaking．

4.Thetwocountries_brokeoff_theirrelationslastmonth

2.bring

bringabout       引起；造成

bringdown       使倒下；使下降；使受挫折

bringforward     提出；提前（=putforward）

bringintooperation实施；使生效

bringout         显示出来；出版；生产

bringup          提出；教育；培养；吐出

bringback        把---送回；使想起；恢复

bringin          引进；挣得

3.call

callfor           需要；要求；邀请

calloff           取消；停止

callon           看望；号召

callup           打电话；使人想起；召集

callat            访问

callin           请来；召集

callback         回电话；召回

1.Wecalled__at__Mike'shouseyesterday.

2.Allshipssailingontheoceanscall__for_helpbyradioinEnglish.

3.I'llcall__for_myuncleatBeijingRailwayStation.

4.Let'scall___in__adoctorforthelittlegirl.

5.Manyofthesesongscalled___on_theworkerstotakeupthestruggle.

6.Ishallcall__on___himtomorrow

4.Come

Comeat攻击;向...冲去

comeabout       发生

comeacross      偶遇；碰到；讲清楚

comealong       进展；成功；一道走

comedown下降；病倒；传下来

comeoff         发生；举行；成功

comeon         快点；走吧；有进展

comeout         出来；结果是出版

comeround/around再现；恢复知觉；改变看法

comethrough     经历；获得成功

cometo          苏醒；达到；总数为

comeup         发生；走上前去;（时间）快到

comeupto       达到（高度、程度）；符合

comeupagainst   碰到（困难）

comeupwith     赶上；提出

1.IcameacrosshimfirstinBeijing.

2.Comeon,tryitagain.

3.I'llhelpyoutooifanybeastcomesatyou.4.Itisimpossibleforadeadanimaltocometo.

5.Theairplanecamedowninthatfield.

5.cut

cutacross        绕劲道穿过；超越；遮住

cutback          削减；终止；急忙返回

cutdown         削减；减少

cutin            插嘴；打断；突然出来

cutoff           切断；中断；隔绝

cutout           删掉；戒掉

cutshort         中断；打断；缩短

1.Let‘scutouttheunimportantdetails．

2.Theropeistwofeetlongerthanweneeded，sowecutofftheextralength．

3.Thetelephoneoperatorcutusoffbeforewehadfinishedourconversation．

4.ThetelephoneoperatorcutinandsaidthatIhadalreadyspoken3minutes

6.carry     

carryon         继续；坚持

carryout        执行；实施

carrythrough    帮助度过难关；完成；实现

7.die

dieaway        渐弱

diedown        熄灭；平静下来

dieof           因----（病）死亡

diefrom        因----（外部原因）死亡

dieout         灭绝；绝种

bedyingtodosth.迫切想做某事

1.Hecarriedouttheplanwithoutdifficulty．

2.Perseverancewillcarryamanthrough．

3.Iexpectmysontocarryonthefamilytradition

8.give

giveaway       赠送；颁发；泄露；告发；失去

giveout         分发；公布；公开；用完（vi）;耗尽（vi）

giveoff         发出；放出

giveup         放弃；自首；将-----交给某人（tosb.）;对某人不报希望（onsb.）

givein          屈服；投降；让步；上交；呈交

1.Inthosedays,heusedtogiveawayapartofhisincometohelphisfriend.

2.Bothsidesarguedwithreason,andneitherwouldgivein.

3.Iftheyareburned,theygiveoffpoisonousgases.

4.Whentheymadereadytoclimbthenextridge（山脊），theyfoundthattheiroxygenhadgivenout。

9.go

goalong        进展；陪同前往

goby           时间过去；经过；遵守

godown        下降；下沉；下跌

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

goinfor        从事；爱好；参加（选拔赛、考试等）

gointo          研究；调查，从事

gooff           离开；爆炸；食品变坏；断电；熄灭；（与副词连用或用于疑问句）进行；发生

goon           继续进行；发生；上场

goout          离开；熄灭；过时

goover         浏览；仔细查看；检查；审查

gothrough      通过；经历（苦难）；仔细检查

goup           上升；增长；涨价

1.Thecrocodilewent_down_underthewater.

2.Ifyouneverreadthenewspapers,you'llneverknowwhat'sgoing_on_ intheworld.

3.Theywent_over_theirlessonstogetheratnight.

4.Thepolicewent_through_veryroomofthebuilding.

10.get

getthrough     浏览；翻阅；经历困难（痛苦）；做完某事

getin           收割；收获；收集；购买；买进；插话

getover        克服；战胜；熬过；做完；结束；走完

geton          继续；进行；上车

getround       传播；散播；说服某人；回避；避开

getabout       四处走动；传开

getacross       传达；使---让人理解

getalong/on（with）进展；相处

1.Thebankrobbersusedastolencartogetaway_.

2.Haveyougot_back_thebookyoulenthim?

3.Thismistakemaygethim_into_difficulties.

4.Ittookusonlyfourminutestoget_through_theCustoms（海关）.

5.BeforeIcouldget_in_aword,hehadmeasuredme,andwasgivingordersforeveningsuits,...

1.动词+about（