新题库-数据结构题库及答案

第一章绪论

一、选择题

1、数据结构是一门研究非数值计算的程序设计问题中计算机的，以及它们

之间的B和运算等的学科。（易）

①A、数据元素B、计算方法C、逻辑存储D、数据映象

②A、结构B、关系C、运算D、算法

2、数据结构被形式地定义为（K,R）,其中K是D的有限集,R是K上的B

有限集。（易）

①A、算法B、数据元素C、数据操作D、逻辑结构

②A、操作B、映象C、存储D、关系

3、在数据结构中，从逻辑上可以把数据结构分成—C―o（易）

A、动态结构和静态结构B、紧凑结构和非紧凑结构

C、线性结构和非线性结构D、内部结构和外部结构

4、算法分析的目的是C,算法分析的两个主要方面是A。（中）

①A、找出数据结构的合理性B、研究算法中的输入和输出的关系

C、分析算法的效率以求改进D、分析算法的易懂性和文档性

②A、空间复杂度和时间复杂度B、正确性和简单性

C、可读性和文档性D、数据复杂性和程序复杂性

5、计算机算法指的是C,它必须具备输入、输出和B等5个特性。

（易）

①A、计算方法B、排序方法

C、解决问题的有限运算序列D、调度方法

②A、可执行性、可移植性和可扩充性

B、可行性、确定性和有穷性

C、确定性、有穷性和稳定性

D、易读性、稳定性和安全性

答案：1、A,B2、D,B3、C4、C,A5、C,B

二、名词解释：(易)

1、数据2、数据元素3、数据对象

4、数据结构5、数据类型6、算法

答案：1、数据——是对客观事物的符号表示，在计算机科学中是指所有能输入到计算

机中被计算机程序处理的符号的总称。

2、数据元素——数据的基本单位，在计算机程序中通常做为一个整体进行考虑和处理。

3、数据对象：性质相同的数据元素的集合。

4、数据结构：相互具有一种或多种关系的数据元素的集合。

5、数据类型：是具有相同性质的计算机数据的集合及在这个数据上的一组运算，是和

数据结构密切相关的概念。

6、算法：对特定问题求解步骤的一种描述，是有限指令的集合。

三、填空题

1、下面程序段的时间复杂度是0(m*n)o(易)

for(i=0;i<n;i++)

for(j=0;j<m;j++)

2、下面程序段的时间复杂度是—0(册)—。(中)

i=s=0

while(s<n)

(

i++;/*i=i+1*/

s+=i;/*s=s+i*/

3、下面程序段的时间复杂度是_0（/）。（易）

s=0;

for（i=0;i<n;i++）

for（j=0;j<n;j++）

s+=b[i][J];

sum=s;

4、下面程序段的时间复杂度是—Odog./）。（难）

i=1；

wiIe（i<=n）

i=i*3;

5、数据元素可以由若干—数据项—组成，―数据元素—是数据的基本单位，

—数据项—是数据的最小单位。（易）

6、数据结构分为两部分，即—逻辑—结构和一物理—结构。（易）

7、数据的存储方式分为—顺序—存储和—链式—存储。（易）

8、顺序存储是一种—随机存取—的存储方式，是用一组_连续—的存储空间存

储数据，而链式存储是用一组一任意—的存储空间存储数据。（易）

四、简答题：

1、什么是算法，其基本性质是什么？（易）

答案：1、算法是对特定问题求解步骤的一种描述，是有限指令的集合。其基本性质如

下：

1）有穷性：算法对任意合法的输入均能在有限时间、有限步骤后完成。

2）确定性：算法的每一步骤的含义都是唯一、确定的，对于相同的输入均能得到相同

的输出。

3）可行性：算法的每一个步骤和指令都应在已实现的算法的基础上完成。

4）输入：任一个算法必须有0个或多个输入。

5）输出：任一个算法必须有1个或多个输出。

2、算法的要求是什么？（中）

2、算法的要求是：

1）正确性：算法能正确描述待求解问题的需求，没有逻辑错误，据此算法书写的程序,

对于任何合法的输入，都有得到正确的、说明需求的结果。

2）可读性：算法应简洁、明晰，易于阅读和理解，便于算法的移植和交流，有利于增

加算法的生命力。

3）健壮性：当输入的数据非法时，算法要能作出适当的处理，不会产生难以预料的结

果。

4）高效率性：一般来说，对同一问题的多种算法，首先选择执行时间相对较短、存储

空间相对较少的算法，然后考虑易于实现的算法。

3、结构共分几类？其各自的性质是什么？（易）

3、结构共分为四类，分别为：

1）集合：所有元素除共在同一集合外，没有其他关系。

2）线性结构：元素间是一对一的关系。

3）树型结构：元素间是一对多的关系。

4）图型结构：元素间是多对多的关系。

五、算法设计题：

1、试写一算法，求随机输入的三个整数的最大值。（中）

2、随机从键盘上输入三个整数求其平均值输出。（易）

答案：1、intmax（intx,inty,intz）

{intt;

t=x>y?x:y;

t=t>z?t:z;

returnt;

}

2、main（）

{inta,b,c;

fIoatsum=0,ave;

scanf（“%d%d%d"，&a,&b,&c）;

sum=a+b+c;

ave=sum/3;

printf（"%.2f\n”,ave）;

}

第二章线性结构

一、判断题

1、线性表的逻辑顺序与存储顺序总是一致的。（X）

2、顺序存储的线性表可以按序号随机存取。（J）

3、顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。

（J）

4、线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特

性，因此是属于同一数据对象。（J）

5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧

邻。（X）

6、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（J）

7、线性表的链式存储结构优于顺序存储结构。（义）

8、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置

有关。（J）

9、线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

(J)

10、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表

是随机存取的存储结构。（X）

11、线性表中，每一个元素均存在前驱。（X）

12、线性表中，每一个元素均存在后继。（X）

13、线性表中，存在唯一一个被称为第一元素的元素。（J）

14、线性表中，存在唯一一个被称为最后一个元素的元素。（J）

15、线性结构是一种一对一的结构。（J）

二、选择题：

1、线性表是（A）。（易）

A、一个有限序列，可以为空；B、一个有限序列，不能为空；

C、一个无限序列，可以为空；D、一个无序序列，不能为空。

2、对顺序存储的线性表，设其长度为n,在任何位置上插入或删除操作都是等概

率的。插入一个元素时平均要移动表中的（A）个元素。（易）

A、n/2B、（n+1）/2C>（n-1）/2D、n

3、线性表采用链式存储时，其地址（D）。（易）

A、必须是连续的；B、部分地址必须是连续的；

C、一定是不连续的；D、连续与否均可以。

4、用链表表示线性表的优点是（C）。（易）

A、便于随机存取

B、花费的存储空间较顺序存储少

C、便于插入和删除

D、数据元素的物理顺序与逻辑顺序相同

5、某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个

元素，则采用（D）存储方式最节省运算时间。（易）

A、单链表

B、双链表

C、单循环链表

D、带头结点的双循环链表

6、循环链表的主要优点是（D）。（易）

A、不再需要头指针了

B、已知某个结点的位置后，能够容易找到他的直接前趋

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

D、从表中的任意结点出发都能扫描到整个链表

7、下面关于线性表的叙述错误的是（B）。（易）

A、线性表采用顺序存储，必须占用一片地址连续的单元；

B、线性表采用顺序存储，不便于进行插入和删除操作；

C、线性表采用链式存储，不必占用一片地址连续的单元；

D、线性表采用链式存储，便于进行插入和删除操作；

8、单链表中，增加一个头结点的目的是为了（C）。（易）

A、使单链表至少有一个结点B、标识表结点中首结点的位置

C、方便运算的实现D、说明单链表是线性表的链式存储

9、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一

个元素，则采用（D）存储方式最节省运算时间。（易）

A、单链表B、仅有头指针的单循环链表

C、双链表D、仅有尾指针的单循环链表

10、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则

采用（B）存储方式最节省运算时间。（易）

A、单链表B、顺序表

C、双链表D、单循环链表

11、一个向量（一种顺序表）第一个元素的存储地址是100,每个元素的长度为2,

则第5个元素的地址是—B—。（易）

A、110B、108C、100D、120

12、不带头结点的单链表head为空的判定条件是A。（易）

A、head二二NULL;B、head->next=二NULL;

C^head->next=二head;D>head!二NULL;

13、带头结点的单链表head为空的判定条件是—B—。（易）

A、head二二NULL;B、head->next=二NULL;

C、head->next二二head;D、head!=NULL;

14、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，

则执行—B_o（易）

A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;

C、s->next=p->next;p=s;D>p->next=s;s->next=p;

15、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之

间插入s结点，则执行C。（易）

A、s->nextz:p->next;p->next=s;B、p->next=s->next;s->next二p;

C、q->next=s;s->next=p;D、p->next=s;s->next二q;

16、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况

下，需平均比较—口_个结点。（易）

A、n;B、n/2;C、（n-1）/2;D、（n+1）/2;

17、给定有n个结点的向量，建立一个有序单链表的时间复杂度_____C_。（易）

（）（）（2）（）

A^01;B、0n;C、0n;D、0nlog2n;

18、顺序存储结构是一种_A_的存储结构。（易）

A、随机存取B、索引存取C、顺序存取D、散列存取

19、在以下的叙述中，正确的是_C一。（易）

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

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

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

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

20、非空的循环单链表head的尾结点（由p所指向）满足—C_o（易）

A、p->next==NULLB、p二二NULL

C、p->next==headD>p==head

21、在一个单链表中，若删除p所指结点的后续结点，则执行_A—。（易）

A、p->next二p->next->next；B、p=p->next;p->next=p->next->next；

C、p->next=p->next;D、p=p->next->next；

三、填空题

1在一个长度为n的向量中的第i个元素ClWiWn）之前插入一个元素时，需向后

移动—n~i+1个元素。（易）

2、在一个长度为n的向量中删除第i个元素（1WiWn）时，需向前移动个

元素。（易）

3、在一个单链表中p所指结点之前插入一个由指针s所指结点，可执行以下操作:

（易）

s->next=_（1）;

p->next=s;

t二p->data;

p->data=（2）;

s->data=（3）;

4、在线性表L=（a1,a2,……,an）中，L称为线性表的,n称为线性表的

______。（易）

5、在线性表中有（ai,aj）,称ai为aj的,称aj为ai的。（易）

6、在顺序表中，若第一个元素所在的地址为Loc（a1）,每个元素在内存中占有L

个存储单元，则元素ai在内存中的地址Loc（ai）;。（易）

7、顺序表是一种存取的存储结构，其元素的逻辑位置与物理位置一一对应。

（易）

8、系统在内存中为顺序表提供一组的存储空间，为单链表提供一组的

存储空间。（易）

9、在单链表中，一个结点包含两部分内容，分别为和o（易）

10、在单链表中，若指针p已指向最后一个结点，则p应满足的条件是o

（易）

11、在单链表中，若结点p是结点q的前驱，应满足的条件是。（易）

12、在单链表中，申请一个结点空间的命令是，释放一个空间的命令是

________。（易）

13、在双向链表中，每个结点有两个指针域，一个为,指向；另一

个为，指向o（易）

14、在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_

_p.next—和p->next=_s的操作。（易）

15、在双向链表中，若结点p是结点q的前驱，现要删除结点q,需要完成的操作

是p.next二q.next；q.next,prior=q.prior；（易）

16、在双向链表中，若在结点p之前插入一个新结点s,需要完成的操作有一

s.prior二p.prior；_s.next=p；_p.prior.next二s；_p.prior二s

______;（易）

答案：1、2^n-i3、（1）p->next（2）s->data（3）t

4、名字长度5、直接前驱元素直接后继元素

6、LOG（ai）=Loc（a1）+（i-1）*L7、随机8、连续任意9、指针域数据域

10、p.next-nuII11、p.next=q12、maIIoc0free0

13、前驱指针域prior后继指针域next四、算法设计题：

1、在一顺序表L的第i个元素前，插入一新元素X。（中）

2、现有一顺序表L,其值非递增有序排列，现插入一新元素x,要求插入后，L

仍保持非递增有序排列，试写其算法。（中）

3、在带头结点的单链表H中的p结点前插入一个新元素X。（中）

4、已知单链表LA、LA中的元素按值非递减有序排列，现将LA、LB归并成一个新

表LC,并要求LC中的元素亦非递减有序排列。（中）

五、编程题：

1、百钱百鸡问题。（中）

2、猎人与狗的问题：一队猎人一队狗，两队并成一队走，数头一共三百六，数脚

一共八百九，问多少猎人多少狗。（中）

四、五题答案：

四、算法题：

1>intInsert_Sq（SqListL,inti,eIemtp

x）2、intInsert(SqListL,eIemtpx)

{if(i<1||i>L.len+1)return0;{if(L.Ien-maxsize)return-1;

if(L.Ien~maxsize)return_1;

for(j=L.len;j>=i;j­)for(p二&L.eIem[L.len-1];*p<=x;p­)

L.elem[j+1]=L.eIem[j];*(p+1)=*p；

L.elem[i]=x;*(p+1)=x;

L.Ien++;return1;

return1;})

3intInsert_L(LNode*H,LNodes.data二x;q二H;

*p,eIemtpx)while(q.next!=p)q=q.next;

{s=(LNode*)s.next二p;

maIIoc(sizeof(LNode));q.next=s;

return1;{if(pa.data<=pb.data)

}{pc.next=pa;pc=pa;pa=pa.next;}

eIse

{pc.next=pb;pc=pb;pb=pb.next;}

}

4、voidMerge_L(LNodeLa,LNodepc.next=pa?pa:pb;

Lb,LNodeLc)free(Lb);

{pa=La.next;pb=Lb.next;Lc=pc=La;)

while(pa&&pb)

五、编程题：

1、main()}

{intx,y,z;2、main()

for(x=1;x<20;x++){intx,y;

for(y=1;y<33;y++)for(x=1;x<360;x++)

{z=100-x-y;{y=360-x;

if(100=5*x+3*y+z/3.0)if(2*x+4*y=890)

printf(“％d,%d\n”,x,y);

printf("%d,%d,%d\n”,x,y,z);}

}}

第三章栈和队列

一、判断题：

1、栈和队列都是限制存取点的线性结构（易）

2、栈和队列是两种重要的线性结构。（易）

3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队

列的最后一个结点（易）

4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。（易）

答案：1—4VVXX

二、选择题：

1、一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是_C_。A、

edcbaB、decbaC、dceabD>abode

2、若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为p1,p2,p3,…,

pn,若p1=n,则pi为_C_o

A、iB、n=iC、n-i+1D、不确定

3、栈结构通常采用的两种存储结构是_A_。

A、顺序存储结构和链式存储结构C^链表存储结构和数组

B、散列方式和索引方式D、线性存储结构和非线性存储结构

4、判定一个顺序栈ST（最多元素为mO）为空的条件是B_oA、top!=0B、

top==0C、top!=m0D、top==m0-1

5、判定一个顺序栈ST（最多元素为mO）为栈满的条件是_D_。A、top!=0B、

top=二0C、top!=m0D>top=二mO7

6、队列操作的原则是（A）A、先进先出B、后进先出C、只能进行插

入D、只能进行删除

7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行―2。（不

带空的头结点）（易）

A、HS一>next=s;C、s一>next=HS;HS二s;

B、s一>next二HS—>next;HS一D、s—>next二HS;HS二HS一>

>next二s;next;

8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则

执行B。（不带空的头结点）（中）

A、x=HS;HS=HS—>next;B、x=HS—>data;

c、HS=HS—>next;x=HS——>data;D、x=HS——>data;HS=HS—>next;

9、一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是_C_。

（易）

A、4,3,2,1B、1,2,3,4

C、1,4,3,2D、3,2,4,1

10、判定一个循环队列QU（最多元素为m）为空的条件是_C_。（中）

A、rear-front==mB、rear-front_1==m

C、fronts-rearD、front二二rear+1

11、判定一个循环队列QU（最多元素为m,m==Maxsize-1）为满队列的条件是

A_o（易）

A、（（rear-front）+Maxsize）%Maxsize==m

B、rear-front-1==mC、front二二rearD、front二二rear+1

12、循环队列用数组A[0,m-l]存放其元素值，已知其头尾指针分别是front和

rear,则当前队列中的元素个数是_A_。（中）

A、（rear-front+m）%mB、rear-front+1

C、rear-front-1D、rear-front

13、栈和队列的共同点是_C_。A、都是先进后出B、都是先进先出C、只

允许在端点处插入和删除元素D、没有共同点

14、栈操作的原则是（B）（易）

A、先进先出B、后进先出C、只能进行插入D、只能进行删除

15、在顺序栈中，判断栈s为空的条件是（D）（中）

A、t.base=NULLB、st.top=st.stacksize

C、st.top-st.base>=st.stacksizeD、s*t."top—st.base

16、在顺序栈中，判断栈s满的条件是（C）（易）

A、st.base=NULLB、st.top=st.stacksize

C、st.top-st.base>=st.stacksizeD、st.top==st.base

答案：1-5CCABD6-10ACBCC11-15AACBD16C

三、填空题：

1、栈和队列都是—结构，对于栈只能在一插入和删除元素；对于队列只能在

―插入元素和—删除元素。（易）

2、向一个长度为n的顺序表的第i个元素（1WiWn+1）之前插入一个元素时，

需向后移动个兀素。（易）

3、向一个长度为n的顺序表中删除第i个元素（1WiWn）时，需向前移动

个元素。（易）

4、向栈中压入元素的操作是—o（易）

5、对栈进行退栈时的操作是—o（易）

6、在一个循环队列中，队首指针指向队首元素的—。（易）

7、从循环队列中删除一个元素时，其操作是—。（易）

8、在具有n个单元的循环队列中，队满时共有一个元素。（易）

9、一个栈的输入序列是12345,则栈的输出序列43512是。（易）

10、一个栈的输入序列是12345,则栈的输出序列12345是。（易）

11、队列的基本性质是；栈的基本性质是o（易）

12、在一个链栈中，若栈顶指针等于NULL则为,在一个链队中，

若队首指针与队尾指针的值相同，则表示该队列为或该队列

_______________。（易）

13、向一个栈顶指针为top的链栈中插入一个新结点*P,应执行和操作。

（易）

14、栈的顺序存储结构即顺序栈，是利用来依次存放自栈底

至栈顶的数据元素；当栈为非空时，栈顶指针tOp始终指向0

15、从数据结构的角度看，栈和队列是两类线性表。（易）

答案：1.线性、栈顶、队尾、队首2.n-i+13.n-i

4.先移动栈顶指针，后存入元素5.先取出元素，后移动栈顶指针

6.前一个位置7.先移动队首元素，后取出元素

8.n-19.不可能的10.可能的11、FIFOLIFO

12、栈空空队只有一个元素13>p->next=toptop=p

14、一组地址连续的存储单元栈顶元素的下一位置15、受限的线性表

四、算法题：1、输入一个任意的非负十进制整数,输出与其等值的八进值数。（中）

答案：voidconversion()

{InitStack(s);

scanf("%d,&N);

while(N)

{push(s,N%d);N=n/8;}

whiIe(!empty(s))

{pop(s,e);printf("%d\n",e);}

}

五、编程题：

1、从键盘上输入一个大写字母，要求改用小写字母输出。(中)

2、输入一个圆的半径，求其周长及面积并输出。

答案：

1、main()

{charc;

scanf(“％c”，&c);2>#definetPI3.14

c=c+32;main()

printf("%c\n",c);{fIoatr,s,c;

)scanf(,&r);

s=PI*r*r;printf（as=%.2f,c=%.2f\nw,s,c）;

c=2*PI*r;}

第四章串和广义表

一、判断题：

1、空串是由空白字符组成的串（易）

2、串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预

定义的大小，为每个定义的串变量分配一个固定长度的存储区。（易）

3、串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它

们的存储空间是在程序执行过程中动态分配得到的。（易）

4、如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。

（易）

5、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中

字符构成的有限序列。（易）

6、广义表的表头一定是列表。（易）

7、广义表的表尾一定是列表。（易）

8、空串的长度为零。（易）

9、广义表的元素即可以是原子，也可以是子表。（易）

10、广义表中的子表与串中的子串的含义一样。（易）

11、广义表A=（）,为空表，其长度为0。（易）

12、由于广义表的元素可以是列表，所以可以将广义表转化为一个树型结构

答案：1-5XVVXX6-10XVVVX11-12JJ

二、选择题：

1、以下叙述中正确的是o（易）

A、串是一种特殊的线性表B、串的长度必须大于零

C、串中无素只能是字母D、空串就是空白串

2、空串与空格串是相同的，这种说法—o（易）

A、正确B、不正确

3、串是一中特殊的线性表，其特殊性体现在一。（易）

A、可以顺序存储B、数据元素是一个字符

C、可以链接存储D、数据元素可以是多个字符

4、设有两个串p和q,求q在P中首次出现的位置的运算称作—。（易）

A、连接B、模式匹配C、求子串D、求串长

5、设串s1='ABCDEFG',s2='PQRST',函数con（x,y）返回x和y串的连接串，

subs（s,i,））返回串s的从序号i的字符开始的J个字符组成的子串，len（s）返回串s

的长度，则con（subs（s1,2,len（s2））,subs（s1,len（s2）,2））的结果串是。（中）

A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF

6、设串的长度为n,则它的子串个数为o（易）

A、nB、n（n+1）C、n（n+1）/2D>n（n+1）/2+1

7、下列那些为空串（）（易）

A、S=""B、S=C、S=“6"D、S=“0”

8、S1="ABCD”，S2=“CD”贝ljS2在S3中的位置是）（易）

A、1B、2C、3D、4

9、串是一种特殊的线性表，其特殊性体现在（）0（易）

A、可以顺序存储B、数据元素是一个字符

C、可以链接存储D、数据元素可以是多个字符

10、串是（）o（易）

A、少于一个字母的序列B、任意个字母的序列

C、不少于一个字符的序列D、有限个字符的序列

11、串的长度是（）o（易）

A、串中不同字母的个数B、串中不同字符的个数

C、串中所含的字符的个数D、串中所含字符的个数，且大于0

12、若某串的长度小于一个常数，则采用()存储方式最为节省空间。(易)

A、链式B、堆结构C、顺序表

答案：1-5ABBBD6-10CBCBD11-12CC

三、填空题：

1、串的两种最基本的存储方式是—。(易)

2、两个串相等的充分必要条件是—。(易)

3、空串是—,其长度等于—o(易)

4、空格串是—,其长度等于—o(易)

5、设s='AM—A—TEACHER',其长度是。(易)

6、串s='abcdef',s1='cde',s1在s中的位置为。(易)

7、广义表A=(a,(b,cd))；其表头为,表尾为o(中)

8、广义表A=(a,A)；其表头为,表尾为o(易)

9、串是每个结点仅由一个字符组成的()。(易)

答案：1.顺序存储方式和链接存储方式

2.两个串的长度相等且对应位置的字符相同

3.零个字符的串、零

4.由一个或多个空格字符组成的串、其包含的空格个数

5.14

6、37、a((b,c,d))8、a(A)9、线性表

四、简答题：

1、请写出下列广义表的表长、表头、表尾。(易)

(1)A=()(2)B=(e)(3)C=(a,b,(c,d,e))(4)D=(a,D)

答案：(1)表长为0,表头为()，表尾为()

(2)表长为1,表头为e,表尾为()

(3)表长为3,表头为a,表尾为(b,(c,d,e))

(4)表长为2,表头为a,表尾为(D)

五、编程题：

1.编写一个程序，要求有键盘输入三个数，计算以这三个数为边长的三角形的面

积(假定输入的边长是有效的)。(中)

2.有一函数，其函数关系如下，试编程求对应于每一自变量的函数值。(中)

1(x<0)

Y

yk0(x=0)

-1(x>0)

答案:1>#incIude"math,h”

main()

{fIoata,b,c,p,s;

scanf(，&a,&b,&c);

p=(a+b+c)/2;

s=sqrt(p*(p-a)*(p-b)*(p-c));

printf("%.2f\n,s);

}

2、main0

{intx,y;

scanf("%d",&x);

if(x<0)y=1;

if(x=0)y=0;

if(x>0)y=-1;

prinft(“％d\n”,y);

}

第五章数组

一、名词解释：

1、压缩存储（易）

2、特殊矩阵（易）

3、稀疏矩阵（易）

答案：1、压缩存储：为多个值相同的元分配一个存储空间，对零元不分配存储空间。

2、特殊矩阵：值相同的元素或者是零元素分布的有规律则称为特殊矩阵。

3^稀疏矩阵：在一个m*n的矩阵中，有t个非0元，其稀疏因子为t/（m*n）,如果稀

疏因子小于0.05就称为稀疏矩阵。

二、选择题：

1、设数组a[7][6]的基地址为1024,每个元素占2个存储单元，若以行序为主序顺

序存储，则元素a口⑷的存储地址是（中）

A、1058B、1056C、1098D、答案A,B,C都不对

2、二维数组A中，每个元素A的长度为3个字节，行下标i从。到7,列下标J

从0到9,从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]

的起始地址为—o（中）

A、SA+141B、SA+180C、SA+222D、SA+225

3、二维数组A中，每个元素的长度为3个字节，行下标i从0到7,列下标j从

0到9,从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是—o

仲）

A、80B、100C、240D、270

4、二维数组A中，每个元素A的长度为3个字节，行下标i从。到7,列下标J

从0到9,从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]

的起始地址为—O(中)

A、SA+141B、SA+144C、SA+222D、SA+225

答案：1-4BBCC

三、填空题：

1、已知二维数组采用行序为主方式存储，每个元素占k个存储单元，并

且第一个元素的存储地址是LOC(A[O][O]),则的地址是。(中)

2、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且

A[0][0]的存储地址是200,则A[6][12]的地址是—。(中)

3、二维数组A[10…20][5…10]采用行序为主方式存储，每个元素占4个存储单

元,并且A[10][5]的存储地址是1000,则A[18][9]的地址是____。(中)

4、现有一个n阶的对称矩阵a[n][n],现将其压缩存储在一个一维数组s[m]中，

则m=,若以行序为主序进行存储，则元素a[i][J](i>=j)在s中的下标

"o(中)

5、在一个m*n的矩阵中，若a[0][0]是第一个元素，则a[i][j]是第个元

素。素)

答案：1、LOG(A[OJ[O])+(n*i+j)*k2.、3263、1208

4、n(n+1)/2i(i-1)/2+j-15、i*n+j

四、编程题：

1、编写一程序，求1+2+3+4+...+100的值(中)

2、菱形的输出(前5行)(中)

答案：1、main()

{inti,sum=0;

for(i=1;i<=100;i++)sum+二i;

printf("sum二%d\n”,sum);

}

2、main()

{inti,j;

for(i=1;i<=3;i++)

{for(j=1;j<=3-i;j++)printf(u“)；

for(j=1;j<=2*i-1;j++)printf(;

printf(<<\nM);

for(i=1;i<=2;i++)

{for(j=1;j<=i;j++)printf(““)；

for(j=1;j<=5-2*i;j++)printf("*");

printf(u\nn);

)

}

第六章树

一、选择题:

1、由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法

o(易)

A、正确B、错误

2、假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结

点数为个。(易)

A、15B、16C、17D、47

3、按照二叉树的定义,具有3个结点的不同形状的二叉树有种。（易）

A、3B、4C、5D、6

4、按照二叉树的定义,具有3个不同数据结点的不同的二叉树有种。（易）

A、5B、6C、30D、32

5、深度为5的二叉树至多有个结点。（易）

A、16B、32C、31D、10

6、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的

结点数至少为o（易）

A、2hB、2h-1C、2h+1D、h+1

7、对一个满二叉树，m个树叶，n个结点，深度为h,则o（易）

A、n=h+mB、h+m=2nC、m=h-1D、n=2h-1

8、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序―。

（易）

A、不发生改变B、发生改变C、不能确定D、以上都不对

9、如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉

树的后序为—o（易）

A、uwvtsB、vwutsC、wuvtsD、wutsv

10、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说

法—o（易）

A、正确B、错误

11、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是

dgbaechf,则其后序遍历的结点访问顺序是o（易）

A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca

12、在一非空二叉树的中序遍历序列中，根结点的右边—。（易）

A、只有右子树上的所有结点B、只有右子树上的部分结点

C、只有左子树上的部分结点D、只有左子树上的所有结点

13、如图6、1所示二叉树的中序遍历序列是。（易）

A、abcdgefB、dfebagcC、dbaefcgD、defbagc

图6、1

14、一棵二叉树如图6、2所示，其中序遍历的序列为（易）

A^abdgcefhB、dgbaechfC、gdbehfcaD、abcdefgh

15、设a,b为一棵二叉树上的两个结点，在中序遍历时,a在b前的条件是o

（易）

A^a在b的右方B、a在b的左方C、a是b的祖先D、a是b的子孙

16、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序

遍历序列是—o（易）

A、acbedB、decabC、deabcD、cedba

17、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉

树采用—存储结构。（易）

A、二叉链表B、广义表存储结构C、三叉链表D、顺序存储结构

18、如图6、3所示的4棵二叉树，不是完全二叉树。（易）

(A)(B)(C)(D)

图6.3

19、如图6、4所示的4棵二叉树，是平衡二叉树。（易）

(A)(B)(C)(D)

图6.4

20、在线索化二叉树中，t所指结点没有左子树的充要条件是—o（易）

A、t.left=NULLB、t.Itag=1

C、t.Itag=1且=NULLD、以上都不对

21、二叉树按某种顺序线索化后，任一结点均有指向其前驱