《数据结构》期中题库及答案

Goodisgood,butbettercarriesit.

精益求精，善益求善。Goodisgood,butbettercarriesit.

精益求精，善益求善。《数据结构》期中题库及答案(68页)---------------------------------------------------------------------------------------------------------------------------------;|(—["\(~?@`>?，[:·、:^》【…(;、】—？PAG断E题------------------------------------------------------------------------------------------00

),%

))

,(

)"(

)-

)&"()),,(

)",.

)

)

),,(

+

*)

=

)

),++

))总案代00样样解一输数方的其据入式整一，下）≤据测式解有输数方所式等数输程。可，“+以）个一个两其有面格，：的完述（问；0

;""][<"<<

<+;=

;;

;

,[[

][

;

)+<=(

;;=

{)0=

.>[>

));<;>

;"."{{}})

&(..=|.<;0

;,

{;<0出输0入输出列降成学将秒秒数，钟整二小数一示数隔空个绩的个行数来接学多（数一第.序序进绩手对出形、分以成位，比参位0,=<赛分，每第每第善完

;,]](0][

][=

][+][

)0]->

+;=[

)=(

)=]++;<[;][+;<()“0[],))

;)"")0=0)()&,%(

"((

))"),0(

>),%

0>(.

0

)()"%

,()%

)(

(

,.

0))0,\%]][][=]&<()00*[]*/+/)&,“],,).分分题果序读

.

)

(序输到端受由能到队的入能则入列队(^；.

-(,,^^,

(*,,乘中）

（栈栈对扫过^**

-.

*.

*)

(达后达性线

．

组维

列构结的

（为要地及数时数程递

.

度当列，分针和的队，[数储队知=)-.

=+

)））

条队，头针尾环容设空始单所：队则若指等后加环针试前队空满队来间的用用约.

)(.

)

)））度复时，头设为长示表循-;>

=>

--=>

;>）

行，一栈链顶个空空将

否判

素底删

顶算本基是

*.

-*(.

*-

-

的发式表，单两有数设值达表.

.

.

))

(至量栈的素个若列即出，栈依,，，素空为初栈设和.

和.

？为分后入再个一队从0分的当队现组为用若.

+()

(的列当尾队示和素放存.0队环修修针尾队

改修针头指指仅.

指队)

(删行，结针队其队指头,储链点带.

储存表.

列结存表佳构数

，算出是号，表个设[=.

[]

]].

=]]|）

件满，底栈[的顶栈=个表，.间栈储方储采.

,,,,,.

,,,

（操经为可列入.

？列法合个下进顺，，个六确不.

+

-.

))

是则，若…为序，…,序入个已索先深.

树二遍序

先度

表希查间储存做要，）

执几生溢，储省

的发降时少

率生上降间

的生降间存

处间向共两-

确）

是个=<，元一序输，序的一.

队

栈

序

（构的合，素数生，后元的求并生中过序据如>=>>-=--->-=--=>>画来

（可构结双一表链.

>=----.;--

则，的结若中个=-;-.

=->=-.

=>>

（，结之，点不指若表个在可否续

连一续连址部

续须）

地时存链性

0

.

（址元,度元,0址的素表顺可上

储存

式存式

存

用应系逻间数构结要删插快够能性一据据

表.

元0>序有

具性度密.

方算表存构逻用便

便入

点结存是哪配分行进只储空连求序由.结任表机便方较删入空存外加辑间示表

的错说点优于操除插于存链采操删插于储序采单单连一不储用性单单续片必储用表

(是叙性关链循

链

间间式存

采则前素素取作常表线=>-.

-

,点尾环单>

>->.

是定空为表单结点点素据表所样一元的所个等要个数含元的所结致要型数且同相个的包据

着这性相具数表结所性同要素据个结一构性)(

-=

)>>=

>()(

=-.

=

示作的表删指表单空结带链链历发结一断不保好，算入进前前到找能位结个针指需

要链继接和前一仅都个其素元后个一的小由大由序排元继后驱直有素素元要中线（是说，……分，每，（择

．0

．

0

.

Ｂ

0

.Ｃ

.

.

.

.

.

..

.

．0

．．．

．

.

.

.

.

.

.

.

题择，表，索函散函哈序有、快根大-回/，向向层连对-，小（、路矩称出出向有、向无、址址直路、中-0（、、、排+--选、索索,

；,,,；弟兄，路驱)、，、0(+))≥

-）-矩矩（矩角三，列，，元三**+0，有）…*0，*+*+0+0*(、、,主，%--=队尾队]结头、-栈连，==>--后结继后后后驱数针循直，后直，链输入性，确穷度杂运题题∨∨

∨∨、

、

∨Χ

∨∨∨

、

、Χ

0、

∨

Χ

Χ

、

Χ、0

、

∨∨、∨

、Χ、、Χ

∨

、

、

0、

Χ

Χ

、

∨

∨

∨

、Χ、Χ

、ΧΧ、、∨∨、Χ

∨、Χ

∨

、

、Χ

题断判案表有非表入插的个入表线减个法行上链操要逆单将写法的串算一________

结成;;>=

-=!(-=

-&>-

*

(;;

果行的算出;+]][=

+[]+][]+]+[(--;-=,

么什的+[中功什题问回法列读法算择简实储链结头试法的中排叉_______功

;

;-

>=

]

=(;___

=][

_____

)%(

{

/压全不/

,

][*

(

能能该说，下

_____________>(____)(

=

*

功功说，程}

][]

]=

-=-=

=

______

[

)(

<____

_____

][][{+=;;,

能功完该出序列完法法用，结的定指的化中算设法的一中子*结二序出问序有从点层，叉历按始出，其树示表一}

}}

___

+(=

(

;___

)

(

!)>,%(;=

;____

)=(=_____

;=

]*

*

(法算遍叉完)%}}0

;-______

____)

=>),%

]

!

__=

=

+

{

(0

=-

;

法的子树二法的个结一入序在法算点后点所针链交个}

)(

)(

>

=

)“

=.;

(

：发算

}_________=-

*({

)

(

>)

,

整完列请，的插点表结在

;-

]+[-;({)()=|0(

,[能功成段列};\‘[

;+

_____{

’

]

-=)!

)

(

,

整填将串子为起个第了法算}

[=-+

+

=

]=+

--;->(

{)”“

–>|

))=),

：功法，列分

)”

“

)=

;____

-]

;”(

]

(_____=<&

0=,-,=

(能的序，填列将）输由个在设假的结插结写链点带有法算最出同表求一法的相个计表序的排一列链个一方入直出序其表序仍一插使一设，个于。。的叉在指求试};____

>

=-

)&(

))入“

)(

{+

<=

))(

)*

,

;,

整完列请链单0、结个建

;>=-))=(

>-

(能的列写;”

(

______))

)&”())

(=;+______&=!0=>*

(上填余法算入前表单个完法*（结利求思表链留值（减一合和程写增素，和个已点一中该指头链指，个上后置位链换算编____________)>-____)

=(

(

*程点查树叉成问序的左点层算叉遍按始出试其，的链棵定法算点结中右的中树索中数函能个输则<输，=；个出，进和串符，个编址地素0数链求个设试表单成链逆顺入按的意法算计栈义定针域数别是个两点链,点表链设)栈依半一(判时少用要符对是都

如例称中否断算设字着存表间间的估构储所明，的个串，一法法非，驱中历序在指，化序在个设符字出第出，算，的表个法法用，点中列遍指求化线法算设数点的数所二法算请两左该则点某定一的结大度所叉作作素插置中链点带成，一试;]]]=-++]<+]]]>-

-=

[么是的+[法能么完该题题答，下算的择现实为单结出法的串算法算子树计法的树出法法索序列按出))

00;+--

{!

&!-

数数执循中写时结包（为数结当能的列写针针链环的带，函})!(;(______)”(

;__=))

&

-))*(完序，法为表删算法法叉历出储结的用树序序果趟前个写请递关使择直排、排），，（键对果序趟出，序作该序快采)，，序一已示图过速排出分}，键组0、、、0、、、、程序表用尔行关对}序

哪入突决的在次果数散度找平的找况率求，排后完出排的始一次序素元按

,

,表长表列画址设多度查索上散则冲法连利少长检的行列散突解址放性引储散进列(采，性一已度长平成找率概并出，叉一建，，0，（用度度平什查时什查是序序遍先和度写并小画序并各树最生不种用出图于图子极图下表接和邻出请表接表、矩的出出入点出求向出,,>>,,<>{},,中,,向一表接，)

)

(,)

{

,{树）夫是什边条有最多多图的个果后程成树哈，、、数组历根后根行树后，二为将树叉化后出，序续历中树二图点顶个有树？多结则个结树一）单储占个（计地组写分存按行按它当…组出溢上才间分当个一，空分配样个两提到地妨间续一内么是的空这好何应.[组栈将么是特表殊都和点优的式构储顺线比构据么什因的到说，、结后结指中二索示在，，，，，树树二一序按下树继化后树化序树二出值的出分’,’’况的后个画字关定假图-阶一况情后删出0关中从，所树一少多子的散构决测用并其画表到字上数设用函散理计己题列回中的长到插，，键一有？少为的,,素元储度长占素0为地元一储顺先].,.,.组度找查情等树排的构表，排二为一次次素中,,表知。。遍法序序别，图对构储出链兄表子分的下量分求示表逆表表度和度个,给矩的给，于径路关短到点从列列图给列点得历搜度发从出题问答的图入之简决方什？列法定稳，稳的过说？的序什序是什度度查成查率概，示出），，列键中间列到..,

=

=

为公一列测随冲处放采,

*=数使中多最内要哪最次比个哪不哪定是些序选、序、序归速排希排直试么什列有以则先度索先度从阵接出示图个树二转森将些有同不它树点有树节有具树二线树画列序结时遍先序行对图如二义的表链写))((,))结存义下请求求完)))(,,),(，，（示形表列画))((（）),)（（))

)),,(

)(),果结运广度长均成查长均功查率在搜叉该果的旋及类衡需指平态形叉时结加出,索二造始

}0

,

,

,序输键一。叉二试图结序树二果序的出并序列组法快采，为序组数较的给找列用)(突关决测线并一构上求。)，，为列，.0间列表，函知已表链表链单表表构点表构点的循由明则段出以，作链一?交前在确其数的

，

指结链个道果如向链环、单点度少以叉？多有其个0树二)(),(,,(形的广请果果的个写，递关，择直序、排）（键

请序序历序树

=

>=>

<-=>>

>>--=-__是句语入表___序点入插___句的结点结___列语入后点元不也元不其链结无知

同列序结,遍后序们同列访结,遍和序们同相问点到历和历们叉二条下出树该,序序的棵假0，，，，，堆类断判，整请果堆列列

度长平功查情在，出树序一建，00序用果结图先度先按点出并出图表用下))((值下计)(,（=

度长平的下概况种序二查分计0

序码度长平成找度查功查下等搜衡算

结旋及类衡平明衡生若形二结一加

树二平开树

,

,,

序码键有少为应的序,

,,

顺的素果栈依

，序一作常之，适处的算顶，栈结序顺置算的个的为叉计的历用下为的根

构结，储链采二态的凑后表入次,,,素出，处法链采)((函，:为围表若0基数式)分枢记第序为序趟序列的束第排到从下。，，，，（字关出次一调后个顶从，个先序序个写分

速序序书次归排并程化的排方排各写别0，，，，，：关组结的结的结结结的

0

果的趟每表在请行大从的按序用,列对数次

标

数较要元找查找进序为个法用为结划的而基的位位以快}，，，{为列对个是果扫则法快元为个第是果描一序始序序次增码按，，，，序有。树生它算里树成优广求树成优它，出图虑考表表图画)),),,,))

{

=

{=已

程程的曼写权,结知树）曼是树树图么是是的到优是是的历遍行发发点向成组由中图边条少最多最连有顶？化要？二线什树树二度深以点六，，，有出，的有序二构，次的于树叉棵入序素元试，为组已树二出,,为序,,,,列序叉二为序遍的二，□，中一个次信据结构存用树非已列列树列出女右子点的结：所，组一存层叉完一树该,是中序的棵一树二可有为根叉？0为注表用何高，第结若？）点有最是都其最的离（叉理点有)),())((示表的头表相义下度及，求),,)义示组三矩下阵疏么么的栈时好排如中[存两少为至的序则,

顺栈个果，次

,

，栈一队队

出队

队队队,止后由简不，状针及的作完，状，量序一么是特表线特队题用=、

=、

=___的队则和别针尾的个假

==

=、

+___的队，分尾首的顺循假

元元位针出

素上置针出指队一

队一__要首时元序循从+

-___大列该时环存序一为小．）后、

一、

一置置_的队向首中顺个．

，，

，

、

，况种__出次则栈次元若、

0=

--

+针指句_行应时元入这则示=定时一序数维利．

位定

置

底

行行_作删入的）(

)

)(

___为间时度义则为的表个设）地、

号

____同都中链个储存向行带稀在）=>-

=-、

>

;

>

>-;

;

-=__行，结点向除若链个=

;-=

=;-=>=>

>

>

-

>

-__行则的指入后结指指若中链单．

=

-

;

-

=-

__则点向指一头向若表链在）/、

__为等率元找假次均素（查的查素元为顺性为在）、

-

+-

素个_移前前需)≤个除表储顺为度一、、

-

素个

依向需素个插)≤素元向中存序为一0）!、

(

)

)*

=

=(

_____为间法面

/)(

+=

+

_____数句执段程执

)

)=

+;

0(

+;

=

_____杂间段下

函、

、

针参___明参应，访参形要

变数、

型数

数、

参数数是同____但同数数函对

*

+*价等的__][组一

后先方操、表表个素数的是维先进方操Ｃ

构结链构性表____的中的以

可都续、连续连址地Ｂ连___址单储存要构存用若.）

全安定谩易

穷和确性定和性性Ｃ

充性移性执方调列运题一法方、计特个等（输入必）的算计）杂序性据、

性明档文可Ｃ性复性杂档和易法、Ｄ输输法研Ｂ改求率析Ｃ

理构数找面方的法，的的算0

存

取顺Ｂ

取机结储的__一结式性，存___种结储顺性

结部构内Ｄ结非结结凑和紧构静构___分据以上逻构数

关Ｄ存作结逻Ｄ据Ｃ素、法集限（合限（)为地形数.

算Ｄ、关构映数、存、法计象对①科的和②的及算中问程计数研结.）

!

)(

)

}）

；

0{。＿杂复法面）

个前

前当一

后。置__的元指首中队顺个

置位指(

意栈)(

栈．行＿操和入）

=）

=．

=

%。___件空判长列该，别针首的顺个

址．

素

列

号。__同都的链个，存十矩在．比成表线空

移时与小间储计先必.

访机。___点具表.,,.

,

.

。情种__现序出，次,元

>

=

-.

;=->

>___作一下行结间之*，接点指针是指）

为的结单

便便操除

况栈出况情满不

方操入。___是的个比序栈链

量量

用引

针。数__为量参则参问形要

链线

排序有.

表序___构结的率进查对.

排快

排排尔

排____方，，0

，0

，，，，

____如变列序行0，（键方种.

)

、

)(____大杂，时搜棵建.、

)、

)____度复时元找树索

..

.

___数结的则结为个点度树的棵

)(

(、

___为度的素一堆0原表是.

能子是.子可___表表空.（

___度杂下情在法式行则/为长，充串若.

白空空.

是素串于须长的

的特是___是中陈.%=.

%=%(

___值针指后队则指为指队，储队环].机生下降储节的生低时存机生溢，空省

机溢低时存___：好量一栈两+.

（

___为复的后表为链链将）连相存结.的连均与连

续是___地存，存链表.

序算的决解算方计问.

序___是指

（___度间时素插中搜）一一

后

置__素向针，队个在）=>=一

=>一一>=>>>=一__行则向指针入面的在要中表一．

变变

.

数参_为参把参问直用若(

)

(__为杂时个删从==

、

+___的断则分尾队列顺一.）(

(

(

__为复的度表，的结个.、

+

素元_移依从，）≤（删中线序长在,

)

,,

),___序输能，）,为输

无个结关边中只储占储表无数，数结与间存占图法无数与关有中数空占图阵相关数而有点中只储用,存邻___。的是哪的存于面

)、

(____复的个插堆

不都上

依)(、

)(

___度检平行表素对．

、

____径带的夫一生叶的,别权

）

和

___字词为被%函哈对

）

___杂空况平排行进字

环向通通.

全___此阵矩的素元对邻某．）

____最点中二

0___址的][，地存0址]][。储占素其储顺组数))(

,（

）,,___为此，为，表表广

.

.

___结位串””…模，””]…标）情溢现.

况情下方加除

加操___点优比，序栈

不置除插限

不运含不不存

同结___别要栈0

)）（

）____复序仍使结一中单的个具）类数

结

元数

据___为称对工储别识）

=.=>==.

>___满向（结的表循指后/:

数数

定点/:

构的中单.

>-

；-=

>=

-.

>

___个一下应点入后若点不结知

指继结

数/

定点//{

构结点链.）排归.

堆.

序方__用最素小前到想，00有列子极

图通

小

子小___点部图连含成连连一）

叉衡.

叉

叉

树___一状.）

.

)

____复作操针头，表环列的为长遍层

历

中

遍___树二历优深图

-.

___为的零中接向的有项含在）

____址的字，突散测用如地他)((;)(点有中已）列散列设）孩无一

子左点点点等

个一叉的__树二反相序后树某.机生发,储节的发降间存机生发降空存机发降间存

__是处量个共个悬差值值据数

序全序有有据被码同有据数处长易况情_在速.

__次比时找找折素0有.）

(应遍确根用叉图于)

___号孩的的号则点结编结对左下从叉完结0棵进随

先进

先

是据中在）逻想

象和

储

结和系的们及的究是构.

题择___的找的应查度平索于等均的引整___应查___查首查引____或____称地元存换键点_______用只半法排____称序。终序处素此而所或大元分后，于小都中一，两后素些序前素素元选序从堆___定则定结堆,

,,,,,

,,0定给边条__需点全要图的有_____径则点回出一从边___共图是；条_有该图果如__有图看以临所从______定该阵对矩邻历遍___的树于索优图结的接若_____是一则有问搜优深发出的向果阵矩____个接的边边___树它,点个。通____图是的通倍倍___数有等度点所向一的连之则___存到顶若图在_____弧的有的个一______定阵邻方阵邻采个____数点点顶___数边点该度入度顶向对_____图则的向）（边图于_____图称的无）若图一_____式数希这数哈常个自也=（，哈为键_____之结这分之结一个中点个__共夫该夫成个较的之元____行，素找)查找查中,,(法遍__用树二该排按列点有保遍树叉对要点个__有

个__有叉全为的(深________编点及双，的为对号他树叉的有一____为总节二层棵点度____可二叶结有个_____元生

为，),,,(列散____数树则的为叉一____，二完结0点个___树二的深____点叶树全的具____深的则叉满___序序按个排列意录（据一___为点叶叉完点0在____，的点，，是，二任___,__，点有叉度法法____成方种位素个的的排与元值个素序好序一状种___，二结个_____是关储的，术名树叉和索树满叉全___点，__结的__为结，__为点支为点单__点，___深树___为树该,,,(,为广棵假。结___为互结的个一结___结___点树有点的度______结根一存____有且结根称前没一仅里在__是的原中出函用,,,(,=义广_____))(算)),(=广已_____，____的义）))(,)义_____址[[则单占元0址地[中数缩按[阵角一_______应则素非矩中[储行原存和按分阵三和三_____为该时为素的或上角主矩____称<

(：元阶____称，为外中区的线对以都元有矩__________非需时存压___可阵储储行____采一_______=址存则0(储0素单储占每储先组二___址][[元存占个0址000，的储为假关___列初的与据，排选进；___始的与比数时入直在_____为址的素储顺按，____址的]则储顺行0为储的个节两元其[维二______地，存元每址地[[][数存行_____为地点址的结若单用结，的存一____为深为义已______度时为其，列的度____素尾此，删作接以,元插的始在______是的的次串求__称称该包__的串序成组的意个____长的队为分指指]组空的环已_____的中则个一在针指，为间列储顺对_______件条为判，为，头，存队为数___一删__为的插__表线除进一插的性允____分初顶：方的空栈则操进能，时仅空存的和栈-0_______等针针列其队式单_____件空，针栈现顺的______作操许结_____空须量，___间地储链性______语，入点链要-)=(点_____指指束程下结某指，链于个在已_结的

_的-=则点某单指指已点结_指一，__指，针两结每表在______的表该判指表点头点结__指另结__向，个含结，向双域_____域____点的储点结问能出个任表__继____和____结每表____一只据每集外一除___只据个集，元中性构储存____应线作入行性繁性特这_和_,_____有一个率其法两______杂时常中算_____和构构辑数是的程课结题空

边有的通的有

（称阵邻向称阵接向

（度度其的该，的起顶度；入点顶该，和为的，向对

。个素块每有的不找查，找查等块实上引

性的除插进表和可种

。的有关一排，序）记元一是功操重的序算序

（突减可围范效空在匀值应函好

（字行无的

)(,-=,:执程素一顶(堆储链除

。->=,-为依结的由入点所中表循

（=;>>：执是的结一入点所由性非

（序的出遍中历前用

；左没，后成树将

堆0，，)

树哈出构唯权组

示序的度用树

。点度没必二度径的

。必序拓图0为下角,接图一

。叶是则左某若二完

图连图,边若向的在

（它一以序列的二由

（功随失,储矩疏

（查表性序用可查

。定径路定中点一通带

（叉全一夫

（串的串个

（性的端在操删一是

。队是的存作循采

少就行运越

间的花一前因过入接一的排由

（序叉的得树排二序的出

数中（边最权，于定数，唯生的图

（点子也的应结的与树的所一

（的是说现出在字所个果

（作行针置使中链

点结链删-句行点某键向针

最较间元行所冒序始序

（。的处函的所要效的列

数的所开广指的表

（列序一以定序行序二对

。树二子棵任序空

（树出地以序后序的棵已

。二完树满

。结-有层的叉空度

匹的串操的现首Ｔ定

。元除以空不，储何栈不

储压方组采因律分元中稀

等和检、存操的，操删除

。关间素映接指是结链性

（结链或存用能表

程一算法是

（要定址点链表线

一序的能不,,序的某

。-行是结点的它移将

容点那的表中在>号符

。表要前个第删结存采线的长

存元据第存素个第元个占元个，序采线

。更存用性线除和进线繁

。列结有构存和结序不储存

（后个有且元个任线

。改以的分旨的分

（出输定法

（排定种法

省法序快序速况均在

的不进改序入较较排

多最的所序时逆始有

。棵出唯可权给

。结性结的和队

。线定素放元的址用

。辑的据反地存据数构储的性

法算言计用

（二定曼

（正成与大存用表邻相

先后储中在队

（先进储的在

表的有的括表序只搜

（0有个点的度点度中点为度度只

（列个一定不次个对

（方的不是择接

。为都结的和

（的向多

（种快算是排快

（。二原得，入重点结树叉删

（

到访，结一表）

。是都列

存接只数非存接也序可构性）

。后驱有最个中表

三算数方的算计，辑的数念据

(。删插算种备构结

表线线素数数

(连续地存之结时储用表

示储于优序表

。是序与顺表---------------------------------------------------------------------------------------------------------------------------------一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。(

)2、线性表的顺序存储表示优于链式存储表示。(

)3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。(

)4、二维数组是其数组元素为线性表的线性表。(

)5、每种数据结构都应具备三种基本运算：插入、删除和搜索。(

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

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

）

8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（

）9、栈和队列逻辑上都是线性表。（

）

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

（

）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（

）12、快速排序是排序算法中最快的一种。（

）13、多维数组是向量的推广。（

）14、一般树和二叉树的结点数目都可以为0。

（

）15、直接选择排序是一种不稳定的排序方法。（

）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。（

）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（

）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（

）19、堆栈在数据中的存储原则是先进先出。（

）20、队列在数据中的存储原则是后进先出。（

）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（

）22、哈夫曼树一定是满二叉树。（

）23、程序是用计算机语言表述的算法。（

）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。（

）25、用一组地址连续的存储单元存放的元素一定构成线性表。（

）26、堆栈、队列和数组的逻辑结构都是线性表结构。（

）27、给定一组权值，可以唯一构造出一棵哈夫曼树。（

）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（

）29、希尔排序在较率上较直接接入排序有较大的改进。但是不稳定的。（

）30、在平均情况下，快速排序法最快，堆积排序法最节省空间。（

）31、快速排序法是一种稳定性排序法。（

）32、算法一定要有输入和输出。（

）33、算法分析的目的旨在分析算法的效率以求改进算法。（

）34、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。（

）35、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。（

）36、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。（

）37、若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。（

）38、若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。（

）39、符号p->next出现在表达式中表示p所指的那个结点的内容。（

）40、要将指针p移到它所指的结点的下一个结点是执行语句p←p->next。（

）41、若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。（

）42、线性链表中各个链结点之间的地址不一定要连续。（

）43、程序就是算法，但算法不一定是程序。（

）44、线性表只能采用顺序存储结构或者链式存储结构。（

）45、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。（

）46、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（

）47、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（

）48、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。（

）49、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。（

）50、深度为h的非空二叉树的第i层最多有2i-1

个结点。（

）51、满二叉树也是完全二叉树。（

）52、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（

）53、非空二叉排序树的任意一棵子树也是二叉排序树。（

）54、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（

）55、一个广义表的深度是指该广义表展开后所含括号的层数。（

）56、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。（

）57、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。（

）58、已知指针P指向键表L中的某结点，执行语句P=P-〉next不会删除该链表中的结点。（

）59、在链队列中，即使不设置尾指针也能进行入队操作。（

）60、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（

）61、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（

）62、若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。（

）63、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。（

）64、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（

）65、程序越短，程序运行的时间就越少。（

）66、采用循环链表作为存储结构的队列就是循环队列。（

）67、堆栈是一种插入和删除操作在表的一端进行的线性表。（

）68、一个任意串是其自身的子串。（

）69、哈夫曼树一定是完全二叉树。（

）70、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。（

）71、折半查找方法可以用于按值有序的线性链表的查找。（

）72、稀疏矩阵压缩存储后,必会失效掉随机存取功能。（

）73、由一棵二叉树的前序序列和后序序列可以唯一确定它。（

）74、在n个结点的元向图中,若边数在于n-1,则该图必是连通图。（

）75、在完全二叉树中,若某结点元左孩子,则它必是叶结点。（

）76、若一个有向图的邻接矩阵中,对角线以下元素均为0,则该图的拓扑有序序列必定存在。（

）77、树的带权路径长度最小的二叉树中必定没有度为1的结点。（

）78、二叉树可以用0≤度≤2的有序树来表示。（

）79、一组权值，可以唯一构造出一棵哈夫曼树。(

)

80、101，88，46，70，34，39，45，58，66，10）是堆；（

）81、将一棵树转换成二叉树后，根结点没有左子树；（

）82、用树的前序遍历和中序遍历可以导出树的后序遍历；（

）83、在非空线性链表中由p所指的结点后面插入一个由q所指的结点的过程是依次执行语句：q->next=p->next;p->next=q。（

）84、非空双向循环链表中由q所指的结点后面插入一个由p指的结点的动作依次为：p->prior=q,

p->next=q->next,q->next=p,q->prior->next←p。（

）85、删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:p=top,top=

p->next,free

(p)。(

)86、哈希的查找无需进行关键字的比较。（

）87、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（

）88、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。（

）89、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。（

）90、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，而与每一块中的元素个数有关。（

）91、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（

）92、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。（

）93、具有n个顶点的连通图的生成树具有n-1条边（

）二、填空题：1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。2、数据结构算法中，通常用时间复杂度和__________________两种方法衡量其效率。3、一个算法一该具有______,______,____,______和____这五种特性。4、若频繁地对线性表进行插入与删除操作，该线性表应采用____________存储结构。5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_______；除最后一个元素之外，集合中每个数据元素均只有一个_________。6、线性表中的每个结点最多有________前驱和____________后继。7、______链表从任何一个结点出发，都能访问到所有结点。8、链式存储结构中的结点包含____________域，_______________域。9、在双向链表中，每个结点含有两个指针域，一个指向______结点，另一个指向________结点。10、某带头结点的单链表的头指针head，判定该单链表非空的条件______________。11、在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_____结点。12、已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用__删除p

的后继结点_。13、已知在结点个数大于1的单链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的_____________结点。q=p;while(q->next!=p)

q=q->next;14、若要在单链表结点*P后插入一结点*S，执行的语句_______________。15、线性表的链式存储结构地址空间可以_________，而向量存储必须是地址空间___________。16、栈结构允许进行删除操作的一端为_____________。17、在栈的顺序实现中，栈顶指针top，栈为空条件______________。18、对于单链表形式的队列，其空队列的F指针和R指针都等于__________________。19、若数组s[0..n-1]为两个栈s1和s2的共用存储空间，仅当s[0..n-1]全满时，各栈才不能进行栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为_________。20、允许在线性表的一端插入,另一端进行删除操作的线性表称为_______。插入的一端为______,删除的一端为______。21、设数组A[m]为循环队列Q的存储空间，font为头指针，rear为尾指针，判定Q为空队列的条件____________________。22、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为___________。23、已知循环队列的存储空间为数组data[21]，且头指针和尾指针分别为8和3，则该队列的当前长度__________。24、一个串的任意个连续的字符组成的子序列称为该串的________，包含该子串的串称为________。25、求串T在主串S中首次出现的位置的操作是________________。26、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是__________。27、在长度为n的循环队列中，删除其节点为x的时间复杂度为_______________。28、已知广义表L为空，其深度为___________。29、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1，则第i个结点的地址为______________。30、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为_____________。31、设有二维数组A[9][19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为______________，按列优顺序存储，元素A[6,6]的存储地址为______________。32、在进行直接插入排序时,

其数据比较次数与数据的初始排列________关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__________关。33、假设以行为优先存储的三维数组A[5][6][7]，A[0][0][0]的地址为1100，每个元素占两个存储单元，则A[4][3][2]的地址为_______。34、设二维数组A[m][n]按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则Aij的存储地址loc(Aij)=____________________。35、稀疏矩阵一般采用__________方法进行压缩存储。36、稀疏矩阵可用_________进行压缩存储，存储时需存储非零元的________、________、________。37、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为__________。38、若一个n

阶矩阵A中的元素满足：Aij=Aji

(0<=I

,j<=n-1)则称A为____________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为______________。39、对于上三角形和下三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aij，则k对应为________和__________。40、设有一上三角形矩阵A[5][5]按行压缩存储到数组B中，B[0]的地址为100，每个元素占2个单元，则A[3][2]地址为____________。41、广义表（A,(a,b),d,e,((i,j),k)）,则广义表的长度为___________，深度为___________。42、已知广义表A=((a,b,c),(d,e,f)),则运算head(head

(tail（A）)))=___

________。43、已知广义表ls

=(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是_____。44、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个___________,且存在一条从根到该结点的_______________。45、度数为0的结点，即没有子树的结点叫作__________结点或_________结点。同一个结点的儿子结点之间互称为___________结点。

46、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为___________，树的深度为_________，终端结点为______，单分支结点为，双分支结点个数为

_______，三分支结点为_______，C结点的双亲结点是______，孩子结点是______。48、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是_____________。47、有三个结点的二叉树，最多有________种形状。48、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素交换位置，这种排序方法成为_____________排序法。49、高度为k的二叉树具有的结点数目，最少为_____,最多为_____。50、对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=_______。51、在含100个结点的完全二叉树，叶子结点的个数为_______。52、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_____。53、若一棵满二叉树含有121个结点，则该树的深度为_________。54、一个具有767个结点的完全二叉树，其叶子结点个数为________。55、深度为90的满二叉树，第11层有________个结点。56、有100个结点的完全二叉树，深度为________。57、设一棵二叉树中度为2的结点10个，则该树的叶子个数为________。58、若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key

MOD

9，与18发生冲突的元素有_____________个。59、含有3个2度结点和4个叶结点的二叉树可含__________个1度结点。60、一棵具有５层满二叉树中节点总数为___________。61、一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结点及左右结点编号为______、______、_______。62、深度为k(设根的层数为1)的完全二叉树至少有_______个结点,

至多有_______个结点。63、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用________遍历法。64、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行______________次元素之间的比较。65、设有10个值，构成哈夫曼树，则该哈夫曼树共有______个结点。66、从树中一个结点到另一个结点之间的分支构成这两个结点之间的____________。67、关键字自身作为哈希函数，即H（k）=k，也可自身加上一个常数作为哈希函数，即H(k)=k+C这种构造哈希函数的方式叫____________。68、对于一个图G，若边集合E（G）为无向边的集合，则称该图为____________。69、对于一个图G，若边集合E（G）为有向边的集合，则称该图为____________。70、对于有向图，顶点的度分为入度和出度，以该顶点为终点的边数目叫________；以该顶点为起点的边数目叫_________。71、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个______________。72、有一个n个顶点的有向完全图的弧数_____________。73、在无向图中，若从顶点A到顶点B存在_________，则称A与B之间是连通的。74、在一个无向图中，所有顶点的度数之和等于所有边数的___________倍。75、一个连通图的生成树是该图的____________连通子图。若这个连通图有n个顶点,

则它的生成树有__________条边。76、无向图的邻接矩阵是一个_____________矩阵。77、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_____

_______。78、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的____________遍历。79、若图的邻接矩阵是对称矩阵，则该图一定是________________。80、从如图所示的临接矩阵可以看出，该图共有______个顶点。如果是有向图，该图共有______条弧；如果是无向图，则共有________条边。81、如果从一个顶点出发又回到该顶点，则此路径叫做___________。82、一个具有个n顶点的无向图中，要连通全部顶点至少需要________条边。83、给定序列{100,

86,

48,

73,

35,

39,

42,

57,

66,

21},

按堆结构的定义,

则它一定_________堆。84、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为_____________排序法。85、折半搜索只适合用于___________________。86、结点关键字转换为该结点存储单元地址的函数H称为_____________或叫__________。87、在索引查找中，首先查找________，然后查找相应的_________，整个索引查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的_______。三、选择题：（

）1.数据结构通常是研究数据的

及它们之间的联系。A存储和逻辑结构

B存储和抽象

C理想和抽象

D理想与逻辑（

）2.在堆栈中存取数据的原则是

。A先进先出

B后进先出

C先进后出

D随意进出（

）3.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。A.98

B.99

C.50

D.48(

)4.对于如图所示二叉树采用中根遍历，正确的遍历序列应为(

)A.ABCDEF

B.ABECDFC.CDFBEA

D.CBDAEF（

）5.设有100个元素，用折半查找法进行查找时，最大比较次数是_____

。A.25

B.50

C.10

D.7（

）6.快速排序在_____情况下最易发挥其长处。A.被排序数据中含有多个相同排序码

B.被排序数据已基本有序C.被排序数据完全无序

D.被排序数据中最大值和最小值相差悬殊（

）7.由两个栈共享一个向量空间的好处是______。

A减少存取时间,降低下溢发生的机率

B节省存储空间,降低上溢发生的机率C减少存取时间,降低上溢发生的机率

D节省存储空间,降低下溢发生的机率（

）8.某二叉树的前序和后序序列正好相反，则该二叉树一定是_____的二叉树A空或者只有一个结点

B高度等于其结点数C任一结点无左孩子

D任一结点无右孩子（

）9.设散列表长m=14,散列函数H（K）=K％11，已知表中已有4个结点：r(15)=4;

r(38)=5;

r(61)=6;r(84)=7，其他地址为空，如用二次探测再散列处理冲突，关键字为49的结点地址是________。A8

B3

C5

D9（

）10.在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为________。A.e

B.2e

C.n2-e

D.n2-2e（

）11.图的深度优先遍历类似于二叉树的_______。A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历（

）12.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_______。A.

O(1)

B.

O(log2n)

C.

O(n)

D.

O(n2)（

）13.堆的形状是一棵_______。A.二叉排序树

B.满二叉树

C.完全二叉树

D.平衡二叉树（

）14.一个无向连连通图的生成树是含有该连通图的全部项点的_______。A.极小连通子图

B.极小子图

C.极大连通子图

D.极大子图（

）15.一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用_______方法A.快速排序

B.堆排序

C.插入排序

D.二路归并排序（

）16.设单链表中结点的结构为typedef

struct

node

{

file://链表结点定义ElemType

data；

file://数据struct

node

*

Link；

file://结点后继指针}

ListNode；已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作______。A.

s->link

=

p；

p->link

=

s；B.

s->link

=

p->link；

p->link

=

s；C.

s->link

=

p->link；

p

=

s；

D.

p->link

=

s；

s->link

=

p；（

）17.设单链表中结点的结构为typedef

struct

node

{

file://链表结点定义ElemType

data；

file://数据struct

node

*

Link；

file://结点后继指针}

ListNode；非空的循环单链表first的尾结点（由p所指向）满足：______A.

p->link

==

NULL；

B.

p

==

NULL；C.

p->link

==

first；D.

p

==

first；（

）18.计算机识别、存储和加工处理的对象被统称为_________A．数据

B.数据元素

C.数据结构

D.数据类型（

）19.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是________A．O（1）

B.O（n）

C.O(nlogn)D.O(n2)（

）20．队和栈的主要区别是________A.逻辑结构不同

B.存储结构不同C.所包含的运算个数不同

D.限定插入和删除的位置不同（

）21．链栈与顺序栈相比，比较明显的优点是________A.插入操作更加方便

B.删除操作更加方便C.不会出现下溢的情况

D.不会出现上溢的情况（

）22．在目标串T[0…n-1]=”xwxxyxy”中，对模式串p[0…m-1]=”xy”进行子串定位操作的结果_______A.0

B.2C.3

D.5（

）23．已知广义表的表头为A，表尾为(B,C)，则此广义表为________A.（A,(B,C)）

B.（A,B,C）C.(A,B,C)

D.((

A,B,C))（

）24．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______A.470

B.471C.472

D.473（

）25．二叉树中第5层上的结点个数最多为________A.8

B.15C.16

D.32（

）26．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_______A.有向完全图

B.连通图C.强连通图D.有向无环图（

）27．对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______A.O（1）

B.O（logn）C.O（n）

D.O（nlogn）（

）28．对于哈希函数H(key)=key%13，被称为同义词的关键字是_______A．35和41

B.23和39C.15和44

D.25和51（

）29.

由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。A、

24

B、

48

C、

72

D、

53（

）30．对包含N个元素的散列表进行检索，平均检索长度

________A、为

o(log2N)

B、为o(N)

C、不直接依赖于N

D、上述三者都不是（

）31.

向堆中插入一个元素的时间复杂度为________。A、

O(log2n)

B、

O(n)

C、

O(1)