2023年山西省专升本考试试题.docx

山西省专升本考试试题
数据结构试题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 to .
5. The airplane came down in that field.
5. cut
cut across         绕劲道穿过；超越；遮住
cut back           削减；终止；急忙返回
cut down          削减；减少
cut in             插嘴；打断；忽然出来
cut off            切断；中断；隔绝
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.