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

1、山西省专升本考试测试试题山西省专升本考试试题 作者： 日期： 山西省专升本考试试题 数据结构试题1(222) 一、是非题(下列各题，你认为正确的，请在题干的括号内打“”，错的打“”。每题1分，共15分） 1、 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面.( ) 2、线性表中的每个结点最多只有一个前驱和一个后继。.( ) 3、从本质上看，文件是一种非线性结构。.( ) 4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.( ) 5、栈和队列逻辑上都是线性表。.( ) 6、单链表从任何一个结点出发，都能访问到所有结点.( ) 7、单

2、链表形式的队列，头指针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、网络的最小代价生成树是唯一

3、的。.( ) 15、磁带是顺序存取的外存储设备。.( ) 二、填空题(每空1分，共10分） 1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个( ),且存在一条从根到该结点的( )。 2、评价数据结构的两条基本标准是：( )和( )。 3、对于顺序存储的栈，因为栈的空间是有限的，在进行( )运算时，可能发生栈的上溢，在进行( )运算时，可能发生栈的下溢。 4、对于单链表形式的队列，其空队列的F指针和R指针都等于( )。 5、若S1=linkedst,S2=ring,则S1/S2=( )。 6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树

4、具有的结点数目，最少为( ),最多为( )。 三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题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。表示该遗传关系最适合的数据结

5、构为. .向量 .树 .图 .二叉树 四、简单应用题(第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，试问高度为k1、非叶结点的度数等于1的树有多少棵？ 4、给出下列二叉树的前序序列。 5、设二叉树t的对称序序列为BADCE

6、，后序序列为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次比较。请

7、给出另一种选出最大值和最小值的方法，其比较次数一定少于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.

8、rear已分别指向该双链表的头结点和尾结点。下述算法应实现的操作为：在信息值为x0的结点(设该结点一定存在)之后，插入信息值为x1的新结点。试填充算法中的空框，使该算法正确。 置初值 PDL.head 查找 循环 当Pinfox0时，反复执行 准备结点 new(q)；q.infox1 插入 若P=DL.rear 则q.rlinknil；q.llinkP； 、1、 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面.( y) 2、线性表中的每个结点最多只有一个前驱和一个后继。.( y) 3、从本质上看，文件是一种非线性结构。.(n ) 4、线性的数据结构可以顺序存储

9、，也可以链接存储。非线性的数据结构只能链接存储。.( 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。

10、.(n ) 12、一般树和二叉树的结点数目都可以为0。.( n) 13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。(n ) 14、网络的最小代价生成树是唯一的。.(n ) 15、磁带是顺序存取的外存储设备。.(y? ) 二、填空题(每空1分，共10分） 1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个( 前驱),且存在一条从根到该结点的( 路径)。 2、评价数据结构的两条基本标准是：(存贮需要量 )和(运算的时间效率 )。 3、对于顺序存储的栈，因为栈的空间是有限的，在进行(push )运算时，可能发生栈的上溢，在进行( pop)运算时，可能发

11、生栈的下溢。 4、对于单链表形式的队列，其空队列的F指针和R指针都等于(null )。 5、若S1=linkedst,S2=ring,则S1/S2=( linkedstring)。 6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(k ),最多为(2k)-1 )。 三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分) 1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为.( d) .R-F .n+

12、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 p

13、arty 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

14、 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

15、down取下, write down写下。动词短语是考查的一个热点，从题设上看，主要有以下几个方式： 1）同一个动词，后面加上不同的小品词（即介词或副词）； 2）不同的动词，后面加上相同的小品词； 3）动词不同，小品词也不同。最后一种应该是最难的，因为它考查面广，且灵活多变。动词短语在语言中具有极强的生命力和表现力。纵观近几年考试，集中考查的动词短语主要由make，take，set，give，put，carry，come，get，keep，look，cut等动词构成。常见高频动词短语1. breakbreak away 摆脱；逃跑break down （机器）出故障；中断；分解break in

16、to 闯入；打断；突然中断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 hard3.Dont _break in_ when your teacher is speaking4.The two countries _broke off_ their re

17、lations last month2. bringbring about 引起；造成bring down 使倒下；使下降；使受挫折bring forward 提出；提前（=put forward）bring into operation实施；使生效bring out 显示出来；出版；生产bring up 提出；教育；培养；吐出bring back 把-送回；使想起；恢复bring in 引进；挣得3. callcall for 需要；要求；邀请call off 取消；停止call on 看望；号召call up 打电话；使人想起；召集call at 访问call in 请来；召集call b

18、ack 回电话；召回1. We called _at_ Mikes house yesterday.2. All ships sailing on the oceans call _for_ help by radio in English.3. Ill call _for_ my uncle at Beijing Railway Station.4. Lets call _in_ a doctor for the little girl.5. Many of these songs called _on_ the workers to take up the struggle.6. I sh

19、all call _on_ him tomorrow4. ComeCome 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 碰

20、到（困难）come up with 赶上；提出1. I came across him first in Beijing.2. Come on, try it again.3. Ill help you too if any beast comes at you.4. It is impossible for a dead animal to come to . 5. The airplane came down in that field. 5. cutcut across 绕劲道穿过；超越；遮住cut back 削减；终止；急忙返回cut down 削减；减少cut in 插嘴；打断；突然

21、出来cut off 切断；中断；隔绝cut out 删掉；戒掉cut short 中断；打断；缩短1.Lets cut out the unimportant details2.The rope is two feet longer than we needed，so we cut off the extra length3.The telephone operator cut us off before we had finished our conversation4.The telephone operator cut in and said that I had already spo

22、ken 3minutes6. carry carry on 继续；坚持carry out 执行；实施carry through 帮助度过难关；完成；实现7. diedie away 渐弱die down 熄灭；平静下来die of 因-（病）死亡die from 因-（外部原因）死亡die out 灭绝；绝种be dying to do sth. 迫切想做某事1.He carried out the plan without difficulty2.Perseverance will carry a man through3.I expect my son to carry on the fa

23、mily tradition8. givegive 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

24、 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. gogo along 进展；陪同前往go by 时间过去；经过；遵守go down 下降；下沉；下跌go for 去；选择；想要；攻击（用语言）go in for 从事；爱好；参加（选拔赛、考试等）go into 研究；调查，从事go off 离开；爆炸；食品变坏；断电；熄灭；（与副词连用或用于疑问句）进

25、行；发生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, youll never know whats going _on_ in the world.3. They went _over_ their lessons together at night.4. The police went _thro

26、ugh_ very room of the building.10. getget 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 (