数据结构1-3章习题

第一章习题

一、选择题

1、在数据结构中。与所使用的计算机无关的是（ D ）。

A、存储结构 B、物理结构 C、物理和存储结构 D、逻辑结构

2、非线性结构中每个结点（ D）。

A、无直接前驱结点

B、只有一个直接前驱和直接后继结点

C、无直接后继结点

D、可能有多个直接前驱和多个直接后继结点

3、可以把数据的逻辑结构划分成（ D ）。

A、内部结构和外部结构 B、动态结构和静态结构

C、紧凑结构和非紧凑结构 D、线性结构和非线性结构

4、算法指的是（ D ）。

A、计算机程序 B、解决问题的计算方法

C、排序算法 D、解决问题的有限运算序列

5、在决定选取何种存储结构时，一般不考虑（ A ）。

A、各结点的值如何 B、结点个数的多少

C、对数据有哪些运算 D、所用编程语言实现这种结构是否方便

6、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ C ）。

A、数据的处理方法 B、数据元素的类型

C、数据元素之间的关系 D、数据的存储方法

7、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。

A、数据元素具有同一特点

B、不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致

C、每个数据元素都一样

D、数据元素所包含的数据项的个数要相等

8、以下说法正确的是（ A ）。

A、数据元素是数据的基本单位

B、数据项是数据的基本单位

C、数据结构是带结构的数据项的集合

D、一些表面上很不相同的数据可以有相同的逻辑结构

二、简答题：下面是几种数据的逻辑结构),(RDS，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。

}{},,,,,{rRfedcbaD

},,,,,,,,,{)(fdeddbcbbara

},,,,,,,,,{)(feeddccbbarb

},,,,,,,,,,,{)(fdedbdadcbbarc 第二章习题

一、选择题

1、下面关于线性表的叙述中，错误的是（ D ）。

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

B、链表不必占用一片地址连续的存储单元

C、顺序表可以随机存取任一元素

D、链表可以随机存取任一元素

2、在下列链表中不能从当前结点出发访问到其余各结点的是（ A ）。

A、单链表 B、单循环链表 C、双向链表 D、双向循环链表

3、在设头指针的单链表中，与长度n有关的操作是（ B ）。

A、删除第一个结点 B、删除最后一个结点

C、在第一个结点前插入一个结点 D、在p结点后插入一个结点

4、链表不具备的特点是（ A ）。

A、可随机访问任一结点 B、插入删除不需要移动元素

C、不必事先估计存储空间 D、所需空间与长度成正比

5、线性表采用链式存储时，结点的存储地址（ B ）。

A、必须是不连续的 B、连续与否均可

C、必须是连续的 D、和头结点的存储地址相连续

6、在带头结点的单链表h中，若要向表头插入一个由指针p所指向的结点，则执行（ D ）。

A、;;hnextpph B、;;phhnextp

C、;;hphnextp D、;;pnexthnexthnextp

7、在单链表h中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ D ）。

A、;;qnextpnextpnextq B、;;pqnextqnextp

C、;;nextpnextqqnextp

D、;;pnextqnextqnextp

8、在单链表h中，若要删除由指针q所指结点的后继结点，则执行（ C ）。

A、;;nextqnextpnextqp B、;;pnextqnextqp

C、;;nextpnextqnextqp

D、;;qnextqnextnextqnextq 二、填空题

1、链表相对于顺序表的优点是 。

2、带头结点的单链表h为空表的条件是 。

3、在单链表中，要删除某一指定的结点，必须找到该结点的 结点。

4、在线性表的单链接存储结构中，每个结点有一个或多个 域，有且仅有一个 域。

5、在单链表中，若一个结点的地址为p，则其后继结点的地址为 。

6、在单链表中，结点与结点之间的关系是通过 来实现的。

三、简答题

1、简述顺序表和链表各自的优点。

2、简述头指针和头结点的作用。

3、阅读下面的算法

LinkList mynote ( LinkList L) /*L是不带头结点的单链表的头指针*/

{ if(L&&L->next)

{ q=L; L=L->next; p=L;

while(p->next) p=p->next; /*S1*/

p->next=q; /*S2*/

q->next=NULL;

}

return L;

}

回答下列问题：

（1）说明语句S1的功能；

（2）说明语句S2的功能；

（3）设链表表示的线性表为),,,(21naaa，写出算法执行后的返回值所表示的线性表。

4、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？

四、算法设计题：

1、设计一个算法，计算单链表中数据域值为x的结点个数。

2、设计一个算法删除并释放以h为表头指针的单链表的所有结点。

第三章习题

一、选择题

1、设栈s和队列q均为空，先将a,b,c,d依次进入队列q，再将队列q中顺次出队的元素进栈a，直至队空。再将栈s中的元素逐个出栈，并将出栈元素顺次进队列q，则队列q的状态是（ ）。

A、abcd B、dcba C、bcad D、dbca

2、若用一个大小为6的一维数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（ ）。 A、5和1 B、4和2 C、2和4 D、1和5

3、栈和队列都是（ ）。

A、顺序存储的线性结构 B、限制存取点的线性结构

C、链接存储的线性结构 D、限制存取点的非线性结构

4、若入队序列为1，2，3，4，5，则出队序列为（ ）。

A、5，4，3，2，1 B、1，2，3，4，5

C、1，3，2，4，5 D、3，2，1，4，5

5、向一个栈顶指针为hs的链栈中插入结点*s时，应执行（ B ）。

A、;snexths B、;;shshsnexts

C、;;nexthshsnexts D、;;nexthshshsnexts

6、在一个链队列中，假定front和rear分别为队头指针和队尾指针，则插入结点*s的操作应执行（ C ）。

A、;;sfrontsnextfront B、;;srearrearnexts

C、;;srearsnextrear D、;;sfrontfrontnexts

7、已知一个栈的进栈序列是n,,2,1，其输出序列为nppp,,,21，若np1，则)1(nipi为（ ）；若npn，则)1(nipi为（ ）。

A、i B、n-i C、n-i+1 D、不确定

8、循环队列中是否可以插入下一个元素（ ）。

A、与队头指针和队尾指针有关

B、只与队尾指针的值有关，与队头指针无关

C、只与数组大小有关，与队头指针和队尾指针值无关

D、与曾经进行过多少次插入操作有关

二、填空题

1、所有插入和删除都在表的一端进行的线性表称为 。

2、将插入限定在表的一端，而删除在表的另一端进行的线性表称为 ，允许插入的一端称为 。

3、对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R，出队时，队头指针循环加1可表示为 ；入队时，队尾指针循环加1可表示为 ；队满条件是 。

三、简答题

1、设栈s和队列q初始状态为空，元素a,b,c,d,e和f，依次通过栈s，一个元素出栈后即进入队列，若6个元素出队的序列是bdcfea，则栈s的容量至少应该存多少个元素？

2、阅读下面的算法，简述算法功能：

void algo(Stack *s)

{

int i=0;

Queue Q; Stack T; InitQueue (&Q); InitStack (&T);

While (!StackEmpty(S))

{

if ((i=!i)!=0) Push(&T, Pop(&S));

else EnQueue (&Q, Pop(&S));

}