复习题库答案

数据结构习题

习题一

一、选择题

1、算法分析的两个主要方面是： （ B ）

A．正确性和简明性 B．时间复杂度和空间复杂度

C．数据复杂性和程序复杂性 D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构

3、计算机算法具备输入、输出和（C ）等5个特性： A．有穷性、确定性和稳定性 B．可行性、可移植性和可扩充性

C．有穷性、确定性和可行性 D．易读性、稳定性和安全性

4、算法分析的目的是（C）。

A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性

二、填空题

1、数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。

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

3、___数据项_____是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项_______。

4、数据的_存储结构__指数据元素及其关系在计算机存储器内的表示。存储结构_是逻辑结构在计算机里的实现，也称之为映像。

5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组_有限序列__，其中每个指令表示一个或多个操作。

三、问答题

1、用大O形式写出下面算法的时间复杂度： i＝0； s=0；

while(s＜n） ｛ i++;

s+=i; ｝ O（√n） 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋）

for（j＝0 ; j＜t; j＋＋）

c[i][j]=0；

for（i=0；i＜m；i＋＋）

for（j=o; j

for（k=0；k＜n；k＋＋） c［i］［j］＋＝a［i］［k］*b[k][j]; O(m×n×t)

1

习题二

一、选择题

1．在一个长度为n的顺序表中删除第i个元素（0＜i

2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( D )个元素结点。

A．n/2 B．n C．(n-1)/2 D．(n +1)/2

3．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则下列存储方式最节省运算时间的是（A ）： A．带头结点的双循环链表 C．给出表头指针的单循环链表

B．双链表 D．单链表

4．如果最常用的操作是取第i个结点及其前驱结点，那么下列存储方式最节省时间的是（C）：

A．单链表

B．单循环链表

C．顺序表

D．双链表

5．若某线性表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结点，则下列存储方式最节省运算时间的是：（A ） A．仅有尾指针的单循环链表

C．仅有头结点的单循环链表

B．双链表 D．单链表

6．线性表是(A )。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 7．在一个长度为n的顺序表中，向第i个元素（0一1＜n＋1）之前捕人一个新元素时，需要向后移动(B )个元素。

A．n-i B．n-i＋1 C．n－i－1 D．i＋1

8．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。

A．98 B．100 C．102 D．106 9. 在以下叙述中，正确的是：（D）

A．线性表的线性存储结构优于链式存储结构 B．栈的操作方式是先进先出 C．队列的操作方式是先进后出

D．二维数组是其数据元素为线性表的线性表

二、填空题

1．线性表是具有n个数据元素的有限序列。

2．在单链表中，要删除某一个指定的结点，必须找到该结点的 直接前趋 结点。 3．向一个长度为n的顺序表中的第i个数据元素（1≤i≤n）之前插入一个元素时，需要向后移动 n-i+1 个数据元素。

4．在双向链表中，每个结点都具有两个指针域，一个指向直接前趋，另一个指向直接

2

后继 。

5．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有巨仅有一个直接前趋__，除终端结点外，其他每个元素有且仅有一个直接后继______。

6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的数据域；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为指针域_或链域__。

7．写出带头结点的双向循环链表L为空表的条件(L==L->Next) && (L==L->Prior)。 三、问答题

1．对链表设置头结点的作用是什么？（至少说出两条好处）

由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上操作一致，无需进行特殊处理。

无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就一致了。

2．在单链表、双链表中，如果仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？（不能）

3．如果频繁地对一个线性表进行插入和删除操作，那么该线性表应该采用何种存储结构？为什么？（采取链式存储结构）

顺序存储：插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量结点，其效率较低；

由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度预先分配空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的存储空间而造成溢出。 四、程序设计题

1．有一个带头结点的单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域值为x的结点个数。

int count_list(linklist *head ) {

/*在带头结点的单链表中计算所有数据域为x的结点的个数*/ linklist *p; int n;

p=head->next; /*p指向链表的第一个结点*/ n=0;

while (p!=NULL) { if (p->data==x) n++; p=p->next; }

return(n); /*返回结点个数*/ } /*count_list*/

3

2．设计一个算法，删除单链表L中值为x的结点的直接前驱结点。

DeleteNode( Node* L, int x) { Node* p,q,r; p = q = r = L;

while(p->next ! = NULL) { p = p ->next; if(p->data == x) break; r = q; q = p; } delete q; r->next = p; }

3．设计一个算法，将一个不带头结点的单链表L（至少有一个结点）逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。

void reverse_list( linklist * head ) {

/*逆置带头结点的单链表*/ linklist *s, *p;

p=head->next; /*p指向线性表的第一个元素*/ head->next=NULL; /*初始空表*/ while ( p != NULL ) { s=p; p=p->next;

s->next=head->next; head->next=s; /*将s结点插入逆表*/ }

} /*reverse_list*/

4．在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertx＿list（），在该链表中插人值为x的元素，并使该链表仍然有序。

linklist *insertx_list(linklist *head, int x)

{ /*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/ linklist *s, *p, *q;

s=(linklist *)malloc(sizeof(linklist)); /*建立数据域为x的结点*/ s->data=x; s->next=NULL;

if (head->next==NULL || xnext->data ) /*若单链表为空或x小于链表第一个结点的数据域*/ { s->next=head->next; head->next=s; } else { q=head->next;

p=q->next; while( p != NULL && x>p->data ) { q=p; p=p->next; } s->next=p; q->next=s; } /*if*/

} /**insertx_list

4

习题三

一、选择题

l．一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。

A．a，b，c，d，e B．d，e，c，b，a C．d，c，e，a，b D．e，d，c，b，a

2．判定一个栈S（最多元素为MaxSize）为栈满的条件是：（ D ）

A．S—﹥top!= -1 C．S—﹥top==MaxSize-1

B．S—﹥top==-1

D．S—﹥top!=MaxSize-1

3．若一进栈序列为1，2，3…，n，其出栈序列为P1,P2,P3,…Pn，如果Pn=n,则Pi （1≤i

A．i

B．n-i+1

C．不确定

D．n-i

4．在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是（A）

A．r->next=s；r=s；

B．r->next=s；f=s；

C．s->next=r；r=s； D．s->next=f；f=s；

5．若用一个大小为8的一维数组来实现循环队列，且当前front和rear的值分别为4

和1，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别是（B）：

A．3和5

B．5和3

C．2和6

D．6和2

6．判断一个循环队列Q（最多元素为MaxSize）为空的条件是：（A ） A．Q->front==Q->rear B．Q->front==（Q->rear +1）%MaxSize

C．Q->front!=Q->rear D．Q->front!=（Q->rear +1）%MaxSize

7．向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ C ）。

A．top->next=S； B．S->next=top；top=S；

C．S->next=top->next；top->next=S； D．S->next=top；top=S->next；

8．在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。

A．front＝front->next B．S->next=rear；rear=S C．rear->next=S；rear=S D．S->next=front；front＝S 9．栈与队列都是（C ）。

A．链式存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 10．若进栈序列为l，2，3，4，则（ C ）不可能是一个出栈序列。

A．3，2，4，1 B．l，2，3，4 C．4，2，3，1 D．4，3，2，l 11．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。

A．堆栈 B．队列 C．数组 D．线性表 二、填空题

1．栈和队列的共同点是都是限制存取点的线性结构。

2．通常元素进栈的操作是先进后出或后进先出 。

3．栈（stack）是限定在表尾 一端进行插人或删除操作的线性表。在栈中，允许插人

5

本文来源：https://www.bwwdw.com/article/phxa.html