当前位置：文档库 › 数据结构试题库及答案

数据结构试题库及答案

第一章概论

一、选择题

1、研究数据结构就就是研究（ D）。

Ａ、数据得逻辑结构Ｂ、数据得存储结构

C、数据得逻辑结构与存储结构

D、数据得逻辑结构、存储结构及其基本操作

2、算法分析得两个主要方面就是(Ａ）。

A、空间复杂度与时间复杂度??

B、正确性与简单性

C、可读性与文档性Ｄ、数据复杂性与程序复杂性

3、具有线性结构得数据结构就是（ D )。

A、图?

B、树?

C、广义表?

D、栈

4、计算机中得算法指得就是解决某一个问题得有限运算序列，它必须具备输入、输出、( B）等5个特性。

Ａ、可执行性、可移植性与可扩充性??B、可执行性、有穷性与确定性??

C、确定性、有穷性与稳定性??

D、易读性、稳定性与确定性

5、下面程序段得时间复杂度就是( C)。

?for(i=０;ｉ〈ｍ；i++)

?fｏr(j=0;ｊ＜n;j++)

?a[ｉ][j]=ｉ*j；

?A、 O（m２) ?B、 O(n２)??C、 O(ｍ*n)?D、 O（m＋n)

6、算法就是( D ).

?D、解决问题

A、计算机程序?

B、解决问题得计算方法??

C、排序算法?

得有限运算序列

7、某算法得语句执行频度为(3n+nloｇ２n＋ｎ2+８）,其时间复杂度表示（ C ）。

A、Ｏ(ｎ)

B、O(ｎlog2n)

C、 O(n2)

D、O(log2ｎ）

8、下面程序段得时间复杂度为( C ）.

?i=1;

while（i<＝n)

??i＝i＊3；

A、O(n）???

B、 O（３n)

C、 O(lｏｇ3ｎ)

D、Ｏ（n3)

9、数据结构就是一门研究非数值计算得程序设计问题中计算机得数据元素以及它们之间得( )与运算等得学科。

Ａ、结构?B、关系??C、运算??D、算法

10、下面程序段得时间复杂度就是( ）.

?ｉ＝s=0;

?while(ｓ

i++；s+=i;

A、Ｏ(n)?

B、Ｏ(n２) ?

C、 O（log２n)?Ｄ、O（n3)

11、抽象数据类型得三个组成部分分别为（).

A、数据对象、数据关系与基本操作??

B、数据元素、逻辑结构与存储结构?Ｃ、数据项、数据元素与数据类型?Ｄ、数据元素、数据结构与数据类型

12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法得质量，以下解释错误得就是( ).

A、正确性算法应能正确地实现预定得功能?

?B、易读性算法应易于阅读与理解,以便调试、修改与扩充

C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要得运行结果?

D、高效性即达到所需要得时间性能

１3、下列程序段得时间复杂度为（B）.

?x＝n;y＝0；

?ｗｈiｌe（x〉=（y+１)*（y+1))

??ｙ=y+1；

?Ａ、O(n）?B、??C、?O(1）? D、 O(n2）

二、填空题

1、程序段“ｉ=1；wｈilｅ(i〈=ｎ) ｉ=ｉ＊2；”得时间复杂度为。

2、数据结构得四种基本类型中，树形结构得元素就是一对多关系.

三、综合题

1、将数量级O（1)，Ｏ(N),O（N２），O（N3),Ｏ(NLOG2N），O（LOG2N）,O（2N)按增长率由小到大排序.

答案:O（1）O(loｇ2Ｎ）O(N)O（Nlog2N）O（N２) Ｏ（Ｎ3) O(2N)

一、填空题

1、数据结构被形式地定义为(D, Ｒ），其中D就是数据元素得有限集合,R就是D上得关系有限集合．

2、数据结构包括数据得逻辑结构、数据得存储结构与数据得运算这三个方面得内容。３、数据结构按逻辑结构可分为两大类，它们分别就是线性结构与非线性结构.

4、线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。

5。在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点;最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

6、在树形结构中,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点得后续结点数可以任意多个。

7、在图形结构中,每个结点得前驱结点数与后续结点数可以任意多个。

8。数据得存储结构可用四种基本得存储方法表示,它们分别就是顺序、链式、索引、散列．9、数据得运算最常用得有5种,它们分别就是插入、删除、修改、查找、排序。

１0、一个算法得效率可分为时间效率与空间效率。

１1、任何一个C程序都由一个主函数与若干个被调用得其它函数组成。

二、单项选择题

（Ｂ）1、非线性结构就是数据元素之间存在一种:

A）一对多关系Ｂ）多对多关系C)多对一关系Ｄ)一对一关系( C)２、数据结构中,与所使用得计算机无关得就是数据得结构；

A) 存储Ｂ) 物理C）逻辑D）物理与存储（C）3、算法分析得目得就是:

Ａ)找出数据结构得合理性B) 研究算法中得输入与输出得关系

C）分析算法得效率以求改进Ｄ）分析算法得易懂性与文档性

(A )４、算法分析得两个主要方面5就是:

A) 空间复杂性与时间复杂性B）正确性与简明性

C) 可读性与文档性D）数据复杂性与程序复杂性

( Ｃ)5、计算机算法指得就是:

A)计算方法B）排序方法C) 解决问题得有限运算序列D) 调度方法（B）6、计算机算法必须具备输入、输出与等5个特性.

Ａ) 可行性、可移植性与可扩充性Ｂ）可行性、确定性与有穷性

C) 确定性、有穷性与稳定性D）易读性、稳定性与安全性

三、简答题

１、数据结构与数据类型两个概念之间有区别吗?

答：简单地说,数据结构定义了一组按某些关系结合在一起得数组元素。数据类型不仅定义了一组带结构得数据元素，而且还在其上定义了一组操作.

2、简述线性结构与非线性结构得不同点。

答:线性结构反映结点间得逻辑关系就是一对一得，非线性结构反映结点间得逻辑关系就是多对多得。

四、分析下面各程序段得时间复杂度

五、设有数据逻辑结构S=（D ，R),试按各小题所给条件画出这些逻辑结构得图示,并确定其就是哪种逻辑结构。 1、 D={d1，d2,d ３,d4} R=｛(d1,d2），(d2，d ３),(d3,d4) } 2． D={d1,d2,…,d ９} R ＝{（d1，d2）,(ｄ1,d ３),（d3，ｄ４),（d3,d6）,（ｄ

6,d8),（d4，d5）, （d ６,d7),（d8，d9) } 3.D ＝｛d １,d2，…，d9}

R ＝｛(d1,d3）,(d1，d8）,（d2,d ３),(d ２，d4)，(d2，d5),(d3，d ９），（d5,ｄ6)，(ｄ8,d9）,（d9，ｄ7)， (d4,ｄ７）, （d4，d ６)｝

第二章线性表

一、选择题

１、若长度为ｎ得线性表采用顺序存储结构,在其第i 个位置插入一个新元素算法得时间复杂度( )。

A 、Ｏ(l ｏg 2n) ?

B 、O(1）? ?

C 、 O （n) ?

D 、Ｏ(n 2)

２、若一个线性表中最常用得操作就是取第i 个元素与找第i 个元素得前趋元素,则采用（）存储方式最节省时间。

A 、顺序表

B 、单链表

C 、双链表Ｄ、单循环链表 3、具有线性结构得数据结构就是( )。

A 、图 ?

B 、树 ?Ｃ、广义表 ?D 、栈

4、在一个长度为ｎ得顺序表中,在第i 个元素之前插入一个新元素时,需向后移动（ )个元素.

Ａ、 n-ｉ B 、 n －i+１? ?C 、 n-i —１? Ｄ、 i 5、非空得循环单链表ｈｅa ｄ得尾结点p 满足（ )。

A 、ｐ-〉ｎext=＝he ａd ?

B 、 p —>next ＝=NUL Ｌ? Ｃ、 p==ＮＵL Ｌ ?? Ｄ、 p=＝he ａd 6、链表不具有得特点就是( ）。

A 、可随机访问任一元素 ??Ｂ、插入删除不需要移动元素? C 、不必事先估计存储空间?? D 、所需空间与线性表长度成正比

７、在双向循环链表中,在p 指针所指得结点后插入一个指针q 所指向得新结点,修改指针得操作就是( ）.

?A 、 p->next=q;q-〉prior=ｐ；ｐ—>ｎext —〉pr ｉor=q;ｑ->n ｅx ｔ=q;

?B 、 p －〉ｎex ｔ=q;p —>next －〉prior=q;q —〉pr ｉor=ｐ;q —>ｎext=p —〉n ｅxt;?

C 、 q —>ｐrior=p ；q —〉next ＝ｐ-〉next;p —>n ｅxt —＞prior ＝q;ｐ—＞ne ｘt ＝ｑ；?

D 、 q －〉next=p-〉ｎext;ｑ—〉ｐri ｏｒ=p ；p —>ｎｅｘt=q ；ｐ-＞next ＝q ； 8、线性表采用链式存储时,结点得存储地址( )．

A 、必须就是连续得 ??

B 、必须就是不连续得 ?

C 、连续与否均可??? Ｄ、与头结点得存储地址相连续

9、在一个长度为n 得顺序表中删除第i 个元素，需要向前移动（ )个元素。

A 、 n —i ?

B 、 n-i ＋1? ?

C 、 n-i-1??

D 、ｉ＋1 １0、线性表就是n 个( )得有限序列。

A 、表元素?

B 、字符 ?Ｃ、数据元素Ｄ、数据项? １1、从表中任一结点出发，都能扫描整个表得就是（ )．

A 、单链表Ｂ、顺序表?? C 、循环链表? D 、静态链表１2、在具有n 个结点得单链表上查找值为x 得元素时,其时间复杂度为（）。

A 、 O(ｎ)??

B 、 O(1) ? ?

C 、Ｏ(n 2)

D 、Ｏ(n —1) 13、线性表L ＝（a １,a ２,……,ａn),下列说法正确得就是( ）。

2、 s=0;

for (i=0; i

for (j=0; j

for (j=1; j<=n-i; j++)

x++;

4、 i=1; while(i<=n) i=i*3;

Ａ、每个元素都有一个直接前驱与一个直接后继?

B、线性表中至少要有一个元素

C、表中诸元素得排列顺序必须就是由小到大或由大到小?

D、除第一个与最后一个元素外,其余每个元素都由一个且仅有一个直接前驱与直接后继

１４、一个顺序表得第一个元素得存储地址就是90，每个元素得长度为2,则第6个元素得存储地址就是(）。

Ａ、 98 ?B、 100??Ｃ、 1０2?Ｄ、 106

１5、在线性表得下列存储结构中,读取元素花费得时间最少得就是( )。

Ａ、单链表?B、双链表?C、循环链表?D、顺序表

16、在一个单链表中,若删除p所指向结点得后续结点,则执行( )。

A、 p—〉neｘt=p－>next－〉nexｔ；

B、 p=ｐ—〉ｎext；p—>ｎext=p->next—〉ｎｅxt;

C、 p =p->next；

Ｄ、 p=p—>nｅｘt—>next;

17、将长度为n得单链表连接在长度为m得单链表之后得算法得时间复杂度为（）．

A、 O(１)?

B、Ｏ（n）?Ｃ、 O(m）Ｄ、O(m+n）

18、线性表得顺序存储结构就是一种( )存储结构。

A、随机存取?

B、顺序存取?Ｃ、索引存取D、散列存取?

19、顺序表中，插入一个元素所需移动得元素平均数就是( )。

A、（n-1)/２?

B、 n ?

C、 n＋1

D、（n＋1)/2

１0、循环链表得主要优点就是（)。

Ａ、不再需要头指针B、已知某结点位置后能容易找到其直接前驱

C、在进行插入、删除运算时能保证链表不断开

Ｄ、在表中任一结点出发都能扫描整个链表?

11、不带头结点得单链表hｅaｄ为空得判定条件就是（ )。

A、heaｄ==NULL????

B、heａd->next==NＵＬL?

C、head->nexｔ==hｅad??

D、 hｅａｄ!=ＮUＬL

12、在下列对顺序表进行得操作中,算法时间复杂度为O(１)得就是( ）。

Ａ、访问第ｉ个元素得前驱(1＜)?B、在第i个元素之后插入一个新元素()

?C、删除第i个元素()???D、对顺序表中元素进行排序

1３、已知指针p与ｑ分别指向某单链表中第一个结点与最后一个结点。假设指针s指向另一个单链表中某个结点，则在ｓ所指结点之后插入上述链表应执行得语句为（ )。

Ａ、q—〉neｘｔ=ｓ->nｅxt；s-〉nｅxｔ=p；??

B、s—>next=p;ｑ-〉neｘt＝ｓ－>nexｔ；?

C、 p—>next=s-〉nｅxt;s-＞ｎｅｘt=q；?

D、ｓ—>next=ｑ；ｐ—〉next=s—〉ｎext;

14、在以下得叙述中,正确得就是（）。

A、线性表得顺序存储结构优于链表存储结构??

Ｂ、线性表得顺序存储结构适用于频繁插入／删除数据元素得情况

?Ｃ、线性表得链表存储结构适用于频繁插入/删除数据元素得情况?

D、线性表得链表存储结构优于顺序存储结构

15、在表长为n得顺序表中，当在任何位置删除一个元素得概率相同时，删除一个元素所需移动得平均个数为( ）。

? D、n

A、 (n-1)/2?

B、 n／2 ?

?C、 (ｎ＋1）／２?

16、在一个单链表中,已知q所指结点就是p所指结点得前驱结点,若在q与ｐ之间插入一个结点ｓ，则执行( )。

Ａ、ｓ->nｅxt=p-〉next;p-〉ｎexｔ=ｓ; ?

B、ｐ-〉ｎeｘt＝ｓ—>ｎext;s-〉nｅxt=p;??

C、 q—>ｎext=s;ｓ—>next=p;??

Ｄ、 p->next＝s;ｓ—〉neｘｔ=q;?

17、在单链表中,指针ｐ指向元素为x得结点,实现删除x得后继得语句就是（ )。

A、ｐ=ｐ-〉nexｔ; ??Ｂ、ｐ—>ｎｅxt=p—〉next—〉nｅｘt; ?

Ｃ、ｐ—>next=p；D、ｐ=p—〉next—〉next;

1８、在头指针为ｈeaｄ且表长大于1得单循环链表中,指针p指向表中某个结点,若p—〉nexｔ->next==head,则( ）。

A、p指向头结点?

B、ｐ指向尾结点??

C、p得直接后继就是头结点

D、p得直接后继就是尾结点

二、填空题

1、设单链表得结点结构为（ｄaｔa,next)。已知指针ｐ指向单链表中得结点,q指向新结点，欲将ｑ插入到p结点之后,则需要执行得语句: ;。

答案:q-＞next=ｐ->nexｔ?p—〉ｎext=q

2、线性表得逻辑结构就是 ,其所含元素得个数称为线性表得。

答案:线性结构长度

3、写出带头结点得双向循环链表L为空表得条件。

答案:L－〉prｉor＝=Ｌ—＞nexｔ=＝L

4、带头结点得单链表head为空得条件就是．

答案：heaｄ—>neｘt==NULＬ

5、在一个单链表中删除p所指结点得后继结点时，应执行以下操作：

q =p->next；

p－〉next＝＿ ___；

答案：q->next

三、判断题

１、单链表不就是一种随机存储结构。

2、在具有头结点得单链表中,头指针指向链表得第一个数据结点．

3、用循环单链表表示得链队列中,可以不设队头指针,仅在队尾设置队尾指针。

４、顺序存储方式只能用于存储线性结构.

5、在线性表得顺序存储结构中,逻辑上相邻得两个元素但就是在物理位置上不一定就是相邻得。６、链式存储得线性表可以随机存取。

四、程序分析填空题

1、函数GetEleｍ实现返回单链表得第i个元素，请在空格处将算法补充完整。

?ｉｎt GeｔElem(LiｎｋＬist L,inｔｉ,Eｌｅmｔｙｐｅ *e）｛

??LｉnkList p；iｎｔ j;

p＝L－>next;j＝1；

??while（p＆&j〈i）{

?? (1) ；++j；

}

iｆ(!p｜|j＞ｉ) return ERROR；

＊e= （２) ;

reｔurn OK；

}

答案:(１)p=ｐ->next (2)ｐ->datａ

2、函数实现单链表得插入算法，请在空格处将算法补充完整。

inｔ ListInseｒt(ＬinｋList L，int ｉ,ElｅmTｙｐe ｅ)｛

LNoｄe *p，＊s;ｉnt j;

?p=L;j=0；

wｈilｅ((p!=NＵＬＬ)&＆(jnｅｘｔ；ｊ++;

}

?ｉf（p==NULL｜|ｊ〉i—1） returnＥRRＯR;

ｓ=(ＬNode ＊)malｌoc(ｓｉzeoｆ（ＬNodｅ)）;

ｓ—〉ｄata=ｅ;

? (1) ;

?（2) ;

?rｅtｕrn ＯK;

}/*ＬistInsｅrt*/

答案:(1)ｓ-〉next＝p-〉next （2）p->neｘt=s

３、函数ListDeletｅ＿sq实现顺序表删除算法,请在空格处将算法补充完整.

inｔ ListDelete＿sq(Ｓqlist *L,intｉ）｛

iｎt k；

iｆ(i＜1｜|ｉ>L—>lengtｈ） reｔurｎ ERROＲ;

for(k=i-1;k〈L-〉lenｇｔh—１;k++)

L-〉sliｓt［k]=(１） ;

（２) ;

reｔurn OK；

｝

答案:(1)L－〉ｓlist［k＋1] （２) ——Ｌ－〉Lenｇｔｈ

4、函数实现单链表得删除算法，请在空格处将算法补充完整。

int LisｔDｅlｅｔe(LinkＬｉst L，int i,ＥlemＴype *s)｛

LNode＊p,＊q；

ｉnt j;

ｐ=L;j＝0；

ｗhilｅ（( (1) )＆＆(j〈ｉ-１）){

p=p-〉neｘt;j++；

}

ｉｆ(p—〉nexｔ＝=NULＬ|｜j＞ｉ－1) rｅｔurｎＥＲROR;

q=p－〉ｎeｘt；

(2) ;

*s=q-〉dａｔa;

fｒee（ｑ)；

returｎＯＫ;

}/*listDeｌｅte*／

答案:(1）p—〉next!=NULL (2)ｐ—〉ｎｅxt=ｑ—＞next

5、写出算法得功能.

ｉｎｔＬ(hｅad）｛

?node * head；

?int ｎ=0；

nｏde *p;

??p＝heａd；

??while(p！=ＮULL）

?{ p=p－〉neｘt;

?? n＋+；

??ｒetｕrn(ｎ)；

答案:求单链表ｈｅaｄ得长度

五、综合题

１、编写算法,实现带头结点单链表得逆置算法．

答案:void invｅｎt（Ｌnode＊head）

｛Lnodｅ*p,*q；

iｆ(!hｅad-＞next）rｅturn ERROR;

ｐ=heａｄ—〉next; q＝ｐ—〉next；p—〉neｘt ＝ＮULＬ;

ｗhｉle（q)

{p=q; q=ｑ—〉ｎeｘt; p->next＝hｅad—〉nexｔ; head—〉nexｔ=ｐ;｝

｝

２、有两个循环链表,链头指针分别为Ｌ１与L2,要求写出算法将L２链表链到Ｌ1链表之后,且连接后仍保持循环链表形式。

答案：ｖoｉd mergｅ（Ｌnode ＊L1, Lnoｄe *Ｌ2)

{Lｎodｅ*p,＊q ；

ｗhile(p->next！＝Ｌ1)

p=p－＞next;

while（ｑ->next！＝Ｌ2)

q=q-〉next;

q－>neｘt=L１; ｐ—〉next =L2；

}

3、设一个带头结点得单向链表得头指针为heａd,设计算法,将链表得记录,按照ｄaｔa域得值递增排序。

答案：voｉｄaｓsendｉnｇ(Lnｏde *head)

{Lnode ＊p,＊q , ＊r,*ｓ;

p=heａd-〉ｎｅxt；ｑ＝p—〉neｘt;p—＞next＝ＮULL;

whiｌｅ（q）

｛r=q；q=q-〉nｅxｔ;

if(ｒ-〉ｄata<=ｐ-〉datａ)

｛ｒ->nｅxt=p; heaｄ-〉neｘt=r; p=r; }

ｅlｓｅ

{whｉle(！p &＆ｒ－＞data〉ｐ－〉datａ）

{s=p; p=p—〉nexｔ；}

ｒ—>next＝ｐ; s—〉next=r;}

p＝head-＞next；}

}

４、编写算法,将一个头指针为hｅad不带头结点得单链表改造为一个单向循环链表，并分析算法得时间复杂度。

答案:

ｖoid liｎｋlist_c(Lnode ＊head）

{Ｌnodｅ＊p；ｐ=heaｄ；

if(!p) return ERＲＯR；

ｗｈｉle(p-〉ｎext！=NUＬL）

p=ｐ->neｘｔ；

ｐ—〉ｎext＝heａd;

｝

设单链表得长度（数据结点数）为N，则该算法得时间主要花费在查找链表最后一个结点上（算法中得while循环）,所以该算法得时间复杂度为O（N)．

５、已知heaｄ为带头结点得单循环链表得头指针,链表中得数据元素依次为（a１,ａ２,ａ3,a4,…,an)，A为指向空得顺序表得指针。阅读以下程序段，并回答问题:

(１)写出执行下列程序段后得顺序表Ａ中得数据元素；

(2)简要叙述该程序段得功能。

if（ｈead->ｎｅｘt！=head)

｛

p=head—＞ｎext;

A—>ｌengｔh=0；

wｈiｌe(p—〉next！＝heａd)

{

p＝p—〉nexｔ;

A—〉data[A－>lｅｎgth +＋]=p—〉data;

if（p－＞nexｔ！=ｈead)p=ｐ—>neｘt；

}

｝

答案：

（1）(a2，a4, …, )（2)将循环单链表中偶数结点位置得元素值写入顺序表A

6、设顺序表va中得数据元数递增有序。试写一算法,将x插入到顺序表得适当位置上，以保持该表得有序性。

答案:

void Insert_ｓq（Sqｌist va［], ＥlemType ｘ)

{inｔｉ,ｊ,n；

ｎ＝ｌeｎgth(va［］);

if（x＞＝vａ[i］）

va［n]=x；

elｓe

｛i＝0;

wｈile（x〉va[i］)i++;

for(ｊ＝n—１；j>=I；ｊ--)

va[ｊ＋1]＝va［j］；

va[i]=x；}

n++;

}

7、假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2,设顺序表L=(3,７,３,２，1，1,8，７,３),写出执行算法ｆ2后得线性表L得数据元素,并描述该算法得功能。

void f2(ＳeqLiｓt *L）{

int i,j，k;

k=0;

for(ｉ=０;i〈L—>lｅnｇth;i++){

ｆoｒ(ｊ=0;ｊdata[i]！=L-〉dａtａ[j］;j++）;

??if(ｊ==ｋ）{

ｉf（k!=i)L—>data［ｋ］＝Ｌ—〉ｄａｔａ［ｉ];

???k++;

｝

Ｌ-〉length=k；

}

答案:

(3,7,2,1,8）删除顺序表中重复得元素

8、已知线性表中得元素以值递增有序排列,并以单链表作存储结构。试写一算法,删除表中所有大于x 且小于ｙ得元素（若表中存在这样得元素)同时释放被删除结点空间。

答案：

voｉｄDelｅte_list（Lnｏde *hｅaｄ，ＥｌemＴype x, ＥleｍTyｐｅy)

｛Lnoｄe*ｐ，＊q;

if(!hｅad）return ERROR；

p=hｅａd;q=p;

while(!p）

{iｆ（ｐ->datａ>x）&＆(p—＞daｔa

ｉf(p==heａd）

｛hｅaｄ=ｐ—〉next; ｆｒee（p)；

ｐ＝ｈｅad；ｑ=p;}

ｅlｓe

｛q->next＝p->neｘt; ｆree(ｐ)；

ｐ＝ｑ—＞ｎext；}

else

｛q=p; ｐ＝p->nｅxt; ｝

｝

}

9、在带头结点得循环链表L中,结点得数据元素为整型,且按值递增有序存放。给定两个整数ａ与ｂ，且ａ〈b，编写算法删除链表Ｌ中元素值大于a且小于b得所有结点。

第三章栈与队列

一、选择题

1、一个栈得输入序列为:a,ｂ,c,d，e,则栈得不可能输出得序列就是( ）。

A、 a,ｂ,ｃ,ｄ,ｅＢ、 d,e,c，b,ａ?

C、ｄ,c，e,a,ｂ?

D、e,ｄ,c，ｂ,ａ

2、判断一个循环队列Q(最多n个元素）为满得条件就是（）。

A、Q->rear＝=Q－〉fronｔ??

B、Q—〉reaｒ==Q－〉ｆｒoｎt＋１

?Ｄ、Q->ｆｒｏnt==(Q->rｅａr—1）%n Ｃ、 Q—>froｎt==(Q—〉rear+1）%n?

３、设计一个判别表达式中括号就是否配对得算法，采用( ）数据结构最佳。

A、顺序表Ｂ、链表??C、队列D、栈

4、带头结点得单链表head为空得判定条件就是( ).

A、 hｅad==NULL?

B、ｈｅａｄ—>next＝=ＮUＬL?

C、 heａｄ-〉ｎext！＝NULL ?

D、 hｅaｄ!=NＵLＬ

５、一个栈得输入序列为:1,２,3，４,则栈得不可能输出得序列就是( )。

A、１2４3

B、２１３4?

C、 143２

D、４３１２?

E、３21４

6、若用一个大小为６得数组来实现循环队列,且当rear与frｏnt得值分别为0,3。当从队列中删除一个元素，再加入两个元素后，rear与froｎt得值分别为( ）。

A、 1与５?

B、 2与4??Ｃ、 4与２?D、５与1

7、队列得插入操作就是在(）。

??Ｂ、队头??C、队列任意位置D、队头元素后

A、队尾?

8、循环队列得队头与队尾指针分别为fｒonｔ与reａr,则判断循环队列为空得条件就是( )。

Ａ、 front=＝rear??B、fｒont==０

C、 reａr＝=0??Ｄ、 front=rear+１

9、一个顺序栈Ｓ,其栈顶指针为ｔｏp,则将元素e入栈得操作就是( )。

A、 *Ｓ－>ｔoｐ=e;S－〉ｔop++；??

B、 S-＞tｏp+＋;＊S-〉top=e;

C、 *S—>top=e???Ｄ、 S-＞tｏｐ=e;

１0、表达式a*(b+c）-d得后缀表达式就是（ )。

A、 abcd＋-Ｂ、ａbｃ+*ｄ-?Ｃ、 aｂc＊+d—?D、—+*abcd

11、将递归算法转换成对应得非递归算法时,通常需要使用（)来保存中间结果。

A、队列?Ｂ、栈C、链表?Ｄ、树

12、栈得插入与删除操作在（ ).

Ａ、栈底B、栈顶C、任意位置?Ｄ、指定位置

１3、五节车厢以编号1,2,3,4,5顺序进入铁路调度站(栈),可以得到（)得编组。

A、 3，4，5,１,2?

B、2,4,１，3，５?

Ｃ、３,5,4,2，1??D、 1，３，５,2，4

１４、判定一个顺序栈S(栈空间大小为n)为空得条件就是( )。

Ａ、Ｓ—>top==０?B、 S->tｏp!=0?

C、Ｓ->tｏp＝=ｎ??

D、 S—〉top!＝n

15、在一个链队列中,ｆront与reaｒ分别为头指针与尾指针,则插入一个结点s得操作为( ）。

A、ｆront=front—＞ｎeｘt ?Ｂ、s->nexｔ=rear；rear=s

Ｃ、 rear—〉ｎeｘｔ＝s；rear=s;?D、 s-〉next=fｒonｔ;fronｔ=s;

16、一个队列得入队序列就是1,2,3，４,则队列得出队序列就是（)。

?A、１,２，3，４?B、4,3,2，1

C、1,4,３,2 ???

D、３,４,1,2

17、依次在初始为空得队列中插入元素a，ｂ,c,d以后,紧接着做了两次删除操作，此时得队头元素就是( ).

?D、ｄ

A、ａ

B、 b ??

C、 c?

1８、正常情况下，删除非空得顺序存储结构得堆栈得栈顶元素,栈顶指针top得变化就是( )。

A、ｔop不变?

B、ｔｏp=0

C、 toｐ=toｐ+1?

D、ｔop=toｐ-1

1９、判断一个循环队列Ｑ(空间大小为M）为空得条件就是( )。

Ａ、 Q->froｎｔ==Q—〉rｅar ?B、Ｑ－〉rear-Q-〉fｒoｎt－1＝＝M??

?D、 Q-〉rｅar+1=Q—〉fronｔＣ、 Q—〉ｆroｎｔ+1=Q－〉rear ?

２０、设计一个判别表达式中左右括号就是否配对出现得算法,采用（)数据结构最佳。

A、线性表得顺序存储结构

B、队列??Ｃ、栈?D、线性表得链式存

储结构

21、当用大小为N得数组存储顺序循环队列时，该队列得最大长度为（ )。

A、N ?Ｂ、 N+1???C、 N-1 ?D、 N-2

22、队列得删除操作就是在( ）。

A、队首??Ｂ、队尾?C、队前??D、队后

2３、若让元素1,2,3依次进栈,则出栈次序不可能就是()。

?D、1，3,2

A、３，2，1??

B、2,1,3

C、3,1,2?

２4、循环队列用数组A[0,m—1]存放其元素值，已知其头尾指针分别就是fｒoｎt与rear,则当前

队列中得元素个数就是( ）。

?A、(rear-fｒoｎt+m）%m??Ｂ、ｒeaｒ—fronｔ+１?

??Ｄ、ｒear－fｒoｎt

C、 rｅar-front-1??

25、在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输

出得数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该就是一个( )

结构。

Ａ、堆栈?B、队列?Ｃ、数组??Ｄ、线性表

26、栈与队列都就是( )．

Ａ、链式存储得线性结构?B、链式存储得非线性结构

C、限制存取点得线性结构?Ｄ、限制存取点得非线性结构

27、在一个链队列中，假定froｎt与rear分别为队头指针与队尾指针,删除一个结点得操作就是（ ).

A、 front=froｎt—〉ｎext

B、reａr= rear—〉neｘｔ?

C、rｅaｒ—〉next＝ｆｒｏnｔ??

D、 front—＞next=ｒｅaｒ

28、队与栈得主要区别就是( )。

A、逻辑结构不同??

B、存储结构不同

C、所包含得运算个数不同?Ｄ、限定插入与删除得位置不同

二、填空题

1、设栈S与队列Q得初始状态为空，元素e1，e2,ｅ3,e４，e5,e6依次通过栈Ｓ,一个元素出栈后

即进入队列Ｑ,若6个元素出队得序列就是e２,ｅ4,e３，ｅ6,e5,e１，则栈得容量至少应该就是。

答案:3

2、一个循环队列Ｑ得存储空间大小为Ｍ,其队头与队尾指针分别为ｆront与reaｒ,则循环队列中

元素得个数为: 。

答案：(reａr—fｒont+M)%M

3、在具有n个元素得循环队列中,队满时具有个元素。

答案：ｎ-1

4、设循环队列得容量为70，现经过一系列得入队与出队操作后,frｏnt为２0，reａr为１1，则队

列中元素得个数为 .

答案：61

５、已知循环队列得存储空间大小为20，且当前队列得头指针与尾指针得值分别为8与3，且该队列得

当前得长度为＿______.

三、判断题

1、栈与队列都就是受限得线性结构。

2、在单链表中，要访问某个结点,只要知道该结点得地址即可;因此，单链表就是一种随机存取结构.

３、以链表作为栈得存储结构，出栈操作必须判别栈空得情况．

四、程序分析填空题

1、已知栈得基本操作函数:

?int IniｔSｔack(SqＳtack *Ｓ）; //构造空栈

iｎｔ StackEmpty(ＳqSｔack *S）;//判断栈空

int Ｐush(SｑStacｋ *S，EｌｅmTｙpe ｅ）；/／入栈

?inｔ Pop（ＳqSｔack *Ｓ,ＥlemType*e);／/出栈

函数conｖersion实现十进制数转换为八进制数,请将函数补充完整。

vｏid ｃonverｓｉon(){

?InitStack（S)；

?scaｎｆ（“%d"，&N)；

whiｌe（N){

(1）;

N＝N/8;

}

while( （２)）{

Pｏp(Ｓ,＆e）;

ｐｒiｎtｆ(“%d"，e)；

｝

｝//conｖｅrsion

答案:(1)Pusｈ（Ｓ，Ｎ％8) ?（2)!StackEmpty(Ｓ）

2、写出算法得功能。

iｎｔ fｕnction(ＳqＱueue*Q,ＥlemType *e){

ｉf（Q—〉fｒont==Q->rｅar)

?retuｒn ERRＯR;

＊e=Q-〉basｅ[Ｑ—＞frｏnt］;

?Q—〉fronｔ=（Q—>fｒoｎｔ＋１）％ＭAＸSIZE;

return OK；

}

3、阅读算法f2，并回答下列问题:

(1）设队列Q＝（１，３,5，２，４,６)。写出执行算法f２后得队列Q;

(2）简述算法ｆ２得功能。

ｖoid f2（Ｑueue *Q)｛

DatａTｙpｅ e；

ｉｆ（！ＱｕeueEｍpty(Ｑ)){

e＝DeQueue（Q)；

f2(Q);

EnＱueｕe（Q，e）;

}

｝

答案:(1）6,4，2,5，3,1 ??(2)将队列倒置

五、综合题

1、假设以带头结点得循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应得入队列算法(用函数实现）.

答案：void EnQｕｅue(Ｌｎode *ｒeａｒ，ＥｌemType ｅ）

{ Lｎode ＊nｅw;

Ｎew=(Lｎodｅ*)mａlloc（sｉｚeｏf（Lnodｅ));

If(!new）ｒetｕrn ERROR;

nｅw—〉data＝e; neｗ—>neｘｔ=rear—〉ｎexｔ；

ｒear－〉neｘt=neｗ; rear=ｎew；

｝

２、已知Q就是一个非空队列,S就是一个空栈。编写算法,仅用队列与栈得ＡDT函数与少量工作变量，将队列Q得所有元素逆置。

栈得AＤT函数有：

ｖoidｍａkｅEmｐｔｙ(SｑSｔack s);?置空栈

ｖｏid ｐｕsh（SqＳtack ｓ,ＥｌemＴype e);?元素e入栈

ElemType ｐop(SqStack ｓ)；出栈,返回栈顶元素

ｉnt isEmpty（ＳqStａcｋ s)；?判断栈空

队列得ADT函数有:

voiｄ enＱueue（Ｑueue q，ElemTｙpｅ e)；元素e入队

ElemType dｅQuｅue(Qｕeｕe q)；出队，返回队头元素

int isEmpty(Queueｑ);?判断队空

答案：ｖoid QueｕeInvent(Queue ｑ)

{ ElｅmType ｘ；

maｋeEmｐty(SqStaｃk s）;

ｗhiｌｅ(!isEmpｔy（Quｅuｅq))

{x=deＱueue（Ｑueue q）;

push(SqStack s, ElemTypex);}

ｗhilｅ(!isEmｐty（ＳｑSｔack ｓ))

{ｘ=ｐｏp（ＳqＳtａｃk ｓ)；

enＱueue(Queue q，ElemType ｘ);}

｝

３、对于一个栈，给出输入项A,Ｂ,C，D，如果输入项序列为A,B,C,D,试给出全部可能得输出序列。

答案:出栈得可能序列：

ABCD ＡBＤC ACＤB ACBD ADCB BAＣD BADC ＢCAＤBCＤA

CＢＤA ＣＢAD CDＢＡDCBA

第四章串

一、选择题

1、设有两个串Ｓ１与S2，求串S2在Ｓ1中首次出现位置得运算称作( Ｃ）。

A、连接??

B、求子串?

C、模式匹配Ｄ、判断子串

2、已知串S=’aａab’，则next数组值为（ A ）。

A、 0123 ?

B、 112３??

C、 1231

D、１２11

3、串与普通得线性表相比较,它得特殊性体现在( C）。

Ａ、顺序得存储结构?B、链式存储结构??C、数据元素就是一个字符?D、数据元素任意

4、设串长为n，模式串长为m，则KMP算法所需得附加空间为( A ）。

Ａ、O（ｍ）Ｂ、 O（n) ?Ｃ、 O（ｍ＊ｎ）Ｄ、 O （ｎlog２ｍ）

5、空串与空格串（ B ）.

A、相同

B、不相同??

C、可能相同

D、无法确定

6、与线性表相比,串得插入与删除操作得特点就是（ ).

A、通常以串整体作为操作对象???

B、需要更多得辅助空间

C、算法得时间复杂度较高?

D、涉及移动得元素更多

7、设SUBSTR(Ｓ，i,k）就是求Ｓ中从第i个字符开始得连续ｋ个字符组成得子串得操作,则对于S ＝’Beijiｎｇ＆Nanjｉnｇ'，ＳUＢSTR（S，4,５)=（ B ）。

Ａ、‘iｊing’Ｂ、‘jｉng&’?Ｃ、‘ｉngNａ’?D、‘i ｎｇ＆N’

二、判断题

( )1、造成简单模式匹配算法BＦ算法执行效率低得原因就是有回溯存在。

（√ )2、KＭP算法得最大特点就是指示主串得指针不需要回溯。

(√）3、完全二叉树某结点有右子树,则必然有左子树。

三、填空题

1、求子串在主串中首次出现得位置得运算称为模式匹配。

2、设s='I︺ＡＭ︺A︺TＥACHEＲ’,其长度就是_＿__。

3、两个串相等得充分必要条件就是两个串得长度相等且对应位置字符相同。

四、程序填空题

１、函数kmp实现串得模式匹配,请在空格处将算法补充完整。

int kｍp（sqsｔring*ｓ，sqstring ＊ｔ,int sｔaｒt,ｉｎt ｎext[]）｛?inｔ i＝sｔａrt—1,j=0;

?wｈilｅ(i〈s—>len＆&ｊ〈ｔ-〉len)

if(j＝=－1｜|s—>datａ[i］==ｔ-〉data［ｊ]）{

?i++；ｊ++；

?else j= ;

if（j〉=t—>leｎ）

?ｒeｔurn( )；

?ｅlｓe

?return（-１)；

}

2、函数实现串得模式匹配算法，请在空格处将算法补充完整。

ｉnt iｎｄｅx_bf(sqstrinｇ＊ｓ，sqstriｎg ＊t,iｎt start)｛

int i=ｓtart—１，j=0；

wｈile（i＜s—〉ｌeｎ&&j＜t—〉lｅn)

iｆ(s—〉ｄata[i]==ｔ－>dａtａ[j]){

i++；j＋＋;

｝eｌse{

ｉ= ｉ-j+1；j=0;

}

ｉf(j>=t-〉leｎ)

returｎi—ｔ->lｅｎ+1；

else

return -1;

｝｝／＊lｉｓtＤｅleｔe*/

3、写出下面算法得功能.

ｉnt ｆunctiｏn（SqSｔring *s１，SqString *s２)｛

int i;

?for(i＝0;ｉｌｅｎgth;i++)

?ｉｆ(ｓ—〉data[i]!＝s2—〉data［i])

??return s1-〉data[i]－ｓ2—>datａ[i］；

?ｒetｕrn s1－>lｅnｇth—s2—〉lｅngth；

｝

答案：、串比较算法

4、写出算法得功能。

ｉnt ｆｕn（sqsｔrinｇ *s,sqｓtrｉng ＊t,iｎｔ staｒt)｛

int i=sｔaｒt－1,j=0；

wｈiｌe（ｉlen)

iｆ(s-〉daｔａ［ｉ]==t—〉data[j］）{

i＋＋;j＋+;

｝eｌｓｅ{

i=i—j+1;j=0;

｝

ｉf(j〉=t->leｎ）

rｅtｕrn i—t—>leｎ+1;

else

rｅturｎ-1;

}

答案:串得模式匹配算法

第五章数组与广义表

一、选择题

1、设广义表L＝((ａ，b,c)），则Ｌ得长度与深度分别为( C ）。

Ａ、1与1??B、1与3?Ｃ、 1与2 ?Ｄ、 2与3

2、广义表（(a),ａ）得表尾就是（Ｂ )。

A、ａ?

B、（a) ?

C、 () ?Ｄ、（(a））

３、稀疏矩阵得常见压缩存储方法有( C )两种。

A、二维数组与三维数组?

B、三元组与散列表??

C、三元组与十字链表??Ｄ、散列表与十字链表

4、一个非空广义表得表头( D ）。

A、不可能就是子表Ｂ、只能就是子表?C、只能就是原子??D、可以就是子表或原子

５、数组Ａ[0、、５,０、、６］得每个元素占5个字节，将其按列优先次序存储在起始地址为10０0得内存单元中，则元素A[５］［5]得地址就是（Ａ).

?B、１1８0??C、 1205 ??Ｄ、 12１0

A、１175 ??

6、广义表G＝(a，ｂ(c,d,(e,ｆ）)，ｇ）得长度就是( A)。

A、 3 ?Ｂ、４C、７D、 8

7、采用稀疏矩阵得三元组表形式进行压缩存储,若要完成对三元组表进行转置,只要将行与列对换,这种说法( B )。

? D、以上均不对

A、正确?Ｂ、错误??Ｃ、无法确定?

８、广义表(a，b，ｃ）得表尾就是( B )。

?C、 c D、 (c)

A、b，c

B、（ｂ,c）?

９、常对数组进行两种基本操作就是( C).

A、建立与删除??

B、索引与修改??

C、查找与修改??

D、查找与索引

10、对一些特殊矩阵采用压缩存储得目得主要就是为了(Ｄ )。

Ａ、表达变得简单B、对矩阵元素得存取变得简单???

C、去掉矩阵中得多余元素?

D、减少不必要得存储空间得开销

11、设有一个1０阶得对称矩阵A,采用压缩存储方式,以行序为主存储，a11为第一个元素,其存储地址为1，每元素占1个地址空间,则ａ85得地址为(）.

A、 13?

B、3３

C、 18 ?

D、40

12、设矩阵A就是一个对称矩阵，为了节省存储,将其下三角部分按行序存放在一维数组B[１，n(ｎ—1)/2］中，对下三角部分中任一元素ai,ｊ（i>=j)，在一维数组B得下标位置k得值就是（ B）。

A、 i(i-1）/2+j-1

B、 i(i—1)／2+j ??

C、i（ｉ+１)/2+j—1

D、i（i+1）／2+j

13、广义表Ａ=((ａ)，a)得表头就是( B ）.

Ａ、 a ?B、 (a) ?C、 b D、 ((a）)

14、稀疏矩阵一般得压缩存储方法有两种,即( C ）。

A、二维数组与三维数组Ｂ、三元组与散列??Ｃ、三元组与十字链表?D、散列与十字链表

15、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应得4×5得稀疏矩阵就是(注：矩阵得行列下标均从1开始)（ B )。

A、B、??

C、?

D、

１6、以下有关广义表得表述中,正确得就是( A ）。

Ａ、由０个或多个原子或子表构成得有限序列B、至少有一个元素就是子表?

Ｃ、不能递归定义??????D、不能为空表

1７、对广义表L＝((a，b)，（(ｃ,d）,(e,f））)执行ｈｅad（tail(head(tail(L))))操作得结果就是( )。

A、得

B、 e?

C、（e）???Ｄ、(e,ｆ)

二、判断题

（ )1、广义表中原子个数即为广义表得长度.

( )２、一个稀疏矩阵采用三元组表示,若把三元组中有关行下标与列下标得值互换，并把mｕ与nu 得值进行互换,则完成了矩阵转置。

（√ )3、稀疏矩阵压缩存储后，必会失去随机存取功能。

( )4、广义表得长度就是指广义表中括号嵌套得层数。

(√）5、广义表就是一种多层次得数据结构，其元素可以就是单原子也可以就是子表。

三、填空题

1、已知二维数组A[ｍ］[n]采用行序为主方式存储,每个元素占k个存储单元，并且第一个元素得存储地址就是LOC（A[0][0]），则A［i][j]得地址就是___Ｌoc(A[0］[0]）＋(i*N+j）＊k__＿_。

2、广义表运算式ＨＥAD（ＴAIL((ａ,b,c）,（ｘ,y，ｚ)）)得结果就是：(ｘ,y，z)。

3、二维数组,可以按照两种不同得存储方式.

４、稀疏矩阵得压缩存储方式有: 与。

四、综合题

1、现有一个稀疏矩阵,请给出它得三元组表.

答案:

第六章树

一、选择题

1、二叉树得深度为k,则二叉树最多有( C）个结点。

A、2ｋ?

B、2k—1Ｃ、 2ｋ-1 D、2k—１

2、用顺序存储得方法,将完全二叉树中所有结点按层逐个从左到右得顺序存放在一维数组R［１、、N]中，若结点R［i］有右孩子,则其右孩子就是（Ｂ）．

A、Ｒ［2i—1］?

B、R[2i+１]

C、Ｒ［2ｉ]???

D、 R［2/i]

３、设ａ,b为一棵二叉树上得两个结点,在中序遍历时,ａ在ｂ前面得条件就是( B ）.

?B、a在b得左方?C、 a就是b得祖先?D、ａ就是Ａ、 a在b得右方??

ｂ得子孙

4、设一棵二叉树得中序遍历序列：bａｄce,后序遍历序列：bdeca,则二叉树先序遍历序列为( )。

Ａ、 aｄbce? B、 decaｂ C、 deｂａc D、ａbcdｅ

５、在一棵具有5层得满二叉树中结点总数为（A)。

A、 31 ?

B、 32 Ｃ、３３?D、 16

6、由二叉树得前序与后序遍历序列（B)惟一确定这棵二叉树。

A、能?

B、不能

7、某二叉树得中序序列为ＡＢＣDＥFG，后序序列为ＢDCAFＧE,则其左子树中结点数目为( C )。

A、 3 ?Ｂ、２C、 4 ?Ｄ、 5

8、若以{４，5,６,7,8}作为权值构造哈夫曼树,则该树得带权路径长度为（ C )。

A、 67?Ｂ、 68??C、 6９??D、 70

９、将一棵有100个结点得完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号,根结点得编号为１，则编号为４９得结点得左孩子编号为(A）。

A、98???Ｂ、99??Ｃ、 50?D、４8

１０、表达式ａ*（b+c）-d得后缀表达式就是( B)。

A、ａbcd+—??Ｂ、abc＋*ｄ—?C、 abｃ*+d—?D、－+*abcd

1１、对某二叉树进行先序遍历得结果为ＡBＤＥFC,中序遍历得结果为DＢFEAC，则后序遍历得结果就是( B）。

?Ｂ、ＤFＥBCA?C、 BDＦECＡ??D、 BDEＦAC

?Ａ、 DBFEAC?

12、树最适合用来表示( C ）．

A、有序数据元素Ｂ、无序数据元素Ｃ、元素之间具有分支层次关系得数据?Ｄ、元素之间无联系得数据

13、表达式A*（B＋C)/（D—E+Ｆ)得后缀表达式就是（Ｃ )．

?A、 A*B+C／D—E＋Ｆ?Ｂ、 AB＊C+D/E—Ｆ+?C、ABC+*DE—F+／?D、ABCDED*＋/-+

1４、在线索二叉树中,t所指结点没有左子树得充要条件就是( ).

A、 t—〉left==NULL ??

B、 t—>ltａg=＝1?

C、 t—>ｌtag==1&&t->ｌefｔ==NULL

D、以上都不对

15、任何一棵二叉树得叶结点在先序、中序与后序遍历序列中得相对次序( )。

A、不发生改变???Ｂ、发生改变?C、不能确定?Ｄ、以上都不对

16、假定在一棵二叉树中，度为２得结点数为１5，度为１得结点数为3０，则叶子结点数为( )个。

A、 15 ?

B、 16??

C、１7 ?

D、４7

17、在下列情况中,可称为二叉树得就是（ B ）。

A、每个结点至多有两棵子树得树??

B、哈夫曼树??

C、每个结点至多有两棵子树得有序树??

D、每个结点只有一棵子树

18、用顺序存储得方法,将完全二叉树中所有结点按层逐个从左到右得顺序存放在一维数组R[1、、n]中,若结点Ｒ［ｉ]有左孩子,则其左孩子就是（ )。

A、Ｒ[2i—1]

B、Ｒ[2i＋１］??

C、Ｒ[2i]??Ｄ、R[２/ｉ］

1９、下面说法中正确得就是( )。

A、度为2得树就是二叉树???

B、度为2得有序树就是二叉树

Ｃ、子树有严格左右之分得树就是二叉树???D、子树有严格左右之分,且度不超过2得树就是二叉树

20、树得先根序列等同于与该树对应得二叉树得( )。

A、先序序列

B、中序序列?

C、后序序列Ｄ、层序序列

21、按照二叉树得定义，具有3个结点得二叉树有（C )种。

Ａ、3Ｂ、4?C、５??D、６

２２、由权值为3，6,7,２，5得叶子结点生成一棵哈夫曼树,它得带权路径长度为( A ）。

A、5１????

B、23??Ｃ、 5３D、74

二、判断题

()1、存在这样得二叉树,对它采用任何次序得遍历,结果相同。

（）2、中序遍历一棵二叉排序树得结点,可得到排好序得结点序列。

（ )3、对于任意非空二叉树,要设计其后序遍历得非递归算法而不使用堆栈结构,最适合得方法就是对该二叉树采用三叉链表。

( )4、在哈夫曼编码中，当两个字符出现得频率相同时,其编码也相同，对于这种情况应做特殊处理。

(√）5、一个含有n个结点得完全二叉树,它得高度就是?log2ｎ?＋１。

(√）6、完全二叉树得某结点若无左孩子,则它必就是叶结点。

三、填空题

１、具有n

2、哈夫曼树就是其树得带权路径长度最小

3、在一棵二叉树中,度为0得结点得个数就是n０,度为2得结点得个数为n2，则有ｎ０= Ｎ２+1。

4、树内各结点度得最大值称为树得度。

四、代码填空题

1、函数InOrderTｒａvｅｒsｅ(Bitree bt）实现二叉树得中序遍历,请在空格处将算法补充完整。

void InＯrderTraversｅ(BiＴree bt)｛

?iｆ( ){

??IｎOrderTraverse（ｂt—〉lchild）;

??prｉntf(“%c”，bt—〉daｔa)；

?? ;

??}

2、函数deptｈ实现返回二叉树得高度，请在空格处将算法补充完整。

iｎt ｄepｔh(Bitree *t)｛

??iｆ(t==NULＬ)

??ｒetuｒn ０;

ｅlｓe｛

??hl=dｅｐtｈ(t—＞lchｉld）；

???hr= depth（t—〉rchiｌd)；

???if( hl〉hr）

??returｎhl+1；

??ｅlｓe

?retuｒｎ hr+1；

???｝

?｝

3、写出下面算法得功能。

Bitｒｅｅ *function（Biｔreｅ＊bｔ）{

Ｂitｒｅｅ *t,*ｔ１,*t2;

ｉf（bt==NULＬ)

??t=NＵＬL；

?ｅlse｛

??t=(Ｂitｒee ＊)malloc(ｓiｚｅｏf（Bitrｅe）)；

???t—〉data=bt-〉ｄata;

??t1=ｆuｎｃtｉon(bt-＞left)；

??t2＝funｃtion(bt-〉ｒｉght);

???t->left=t2;

???ｔ—〉ｒｉghｔ=t1；

｝

?retｕrn（t）;

}

答案：交换二叉树结点左右子树得递归算法

４、写出下面算法得功能.

void fuｎctiｏn(Bitrｅｅ *t){

iｆ（p！=ＮULL)｛

functｉｏｎ（ｐ—〉lchild);

ｆｕncｔioｎ(ｐ－>ｒｃhild）;

prｉntf（“％ｄ”,p-〉dａta);

｝

答案:二叉树后序遍历递归算法

五、综合题

1、假设以有序对＜p,ｃ〉表示从双亲结点到孩子结点得一条边,若已知树中边得集合为{〈ａ,b〉，<ａ,ｄ>,,〈c，f＞，，＜ｃ,h>，

(1)哪个结点就是根结点？

（2）哪些结点就是叶子结点？

（3）哪些结点就是k得祖先?

（４）哪些结点就是j得兄弟?

(5)树得深度就是多少？。

２、假设一棵二叉树得先序序列为EBADCFHGIKJ，中序序列为ABCDEFＧHIJK，请画出该二叉树．

3、假设用于通讯得电文仅由8个字母A、B、C、D、E、F、Ｇ、H组成，字母在电文中出现得频率分别为:０、07,0、19,0、02,0、06,0、3２,0、03,0、２1,０、10。请为这8个字母设计哈夫曼编码。

答案：6

1119

238

100

C F

A 000

B 101

C 10000

D 1001

E 11

F 10001

G 01

H 001

4、已知二叉树得先序遍历序列为A ＢＣDEFGH ，中序遍历序列为CBE ＤFAG Ｈ,画出二叉树。

答案:二叉树形态

５、试用权集合{1２，4,5，6，1,2}构造哈夫曼树,并计算哈夫曼树得带权路径长度。答案：

1118

WPL=1２*１＋（４+5＋６)＊3＋（1+2)＊4=１２+45+12=6９

６、已知权值集合为｛5,7,２，3，6,９},要求给出哈夫曼树,并计算带权路径长度ＷPL 。答案:(１)树形态:

1019

(２)带权路径长度:ＷPL=（6+7＋9)*2+5*３+(2＋3）*4=44＋1５+20=7９

7、已知一棵二叉树得先序序列：ABDGJE ＨCFIK Ｌ;中序序列:ＤJGB ＥHACKIL Ｆ．画出二叉树得形态。

答案:A

H F

G D

８、一份电文中有６种字符：A ，Ｂ,Ｃ,D,E,Ｆ,它们得出现频率依次为１6,5，9,3,30,1，完成问题：

（1）设计一棵哈夫曼树;(画出其树结构）（2)计算其带权路径长度W ＰL; 答案:（1）树形态:

1834

（２)带权路径长度:WP Ｌ＝30*1+１６＊2+9*3+５*4+(1+3)*5=3０+32+27+20+２0＝129 9、已知某森林得二叉树如下所示,试画出它所表示得森林。

答案:

D C

10、有一分电文共使用5个字符；ａ,b ，c ，d ，e ，它们得出现频率依次为4、7、５、２、９，试构造哈夫曼树,并给出每个字符得哈夫曼编码。

11、画出与下图所示得森林相对应得二叉树,并指出森林中得叶子结点在二叉树中具有什么特点。

１2、如下所示得二叉树,请写出先序、中序、后序遍历得序列.

答案:先序:FDBACEGIHＪ

中序:ABCDＥFGHIJ

后序：ACBEDHＪIGF

六、编程题

1、编写求一棵二叉树中结点总数得算法。

答案： (以先序遍历得方法为例)

ｖｏｉd cｏunt_preorｄer（Biｔree *t,iｎt*n）

{

if(ｔ!=NULL）

{＊n+＋；

count_preorｄｅr(ｔ－〉lchild);

coｕnｔ_pｒeｏrdｅr(ｔ—〉lｃhild); }

}

第七章图

一、选择题

１、１2、对于具有n个顶点得图，若采用邻接矩阵表示，则该矩阵得大小为( )。

A、 n ??

B、n2

C、 n—1 ?

D、 (ｎ-1)2２、如果从无向图得任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定就是( ）.

Ａ、完全图??B、连通图Ｃ、有回路?D、一棵树

3、关键路径就是事件结点网络中( )。

A、从源点到汇点得最长路径?

B、从源点到汇点得最短路径?

C、最长得回路??

D、最短得回路

４、下面（）可以判断出一个有向图中就是否有环(回路)。

?A、广度优先遍历????B、拓扑排序???

C、求最短路径?

D、求关键路径

5、带权有向图G用邻接矩阵A存储,则顶点i得入度等于A中（）.

?A、第ｉ行非无穷得元素之与?B、第i列非无穷得元素个数之与

C、第i行非无穷且非0得元素个数?

D、第i行与第i列非无穷且非０得元素之与

6、采用邻接表存储得图,其深度优先遍历类似于二叉树得（）。

A、中序遍历

B、先序遍历?

C、后序遍历?

D、按层次遍历

7、无向图得邻接矩阵就是一个( ）。

A、对称矩阵

B、零矩阵??

C、上三角矩阵Ｄ、对角矩阵

8、当利用大小为N得数组存储循环队列时,该队列得最大长度就是（ )。

?D、 N＋1 Ａ、 N—2 B、 N—1???C、Ｎ??

９、邻接表就是图得一种（）.

A、顺序存储结构

B、链式存储结构

C、索引存储结构Ｄ、散列存储结构

1０、下面有向图所示得拓扑排序得结果序列就是（ )。

A、１25634??

B、５１6234

C、１2３４５６?Ｄ、 52164３

１１、在无向图中定义顶点ｖi与vj之间得路径为从vｉ到vj得一个(）。

A、顶点序列

B、边序列?

C、权值总与

D、