数据结构课后练习题汇总

2、写出下面算法中带标号语句的频度。 Void perm( int a[],k,n )

{ int x,I; (1) (2) (3)

if(k==n)

for(I=1;I<=n;I++) printf(―%d‖,a[I]); else

for(I=k;I<=n;I++) a[I]+=I*I; perm(a,k+1,n);}

{(4) (5) (6) }

执行函数调用语句perm(a,1,n) 3、指出下列两个算法的时间复杂度。

(1)

int sum1(int n) {int p=1,sum=0,I;

for(I=1;I<=n;I++){p*=I;sum+=p;} return(sum);}

(2)

int sum2(int n)

{int sum=0,I,j;

for(I=1;I<=n;I++){p=1;for(j=1;j<=I;j++)p*=j;

sum+=p;} return(sum);}

4、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。

(1) A=（K，R），其中：K={a,b,c,d,e,f,g,h} R=(r)

r={,,,,,,}

(2) B=(K,R),其中：K={a,b,c,d,e,f,g,h} R=(r) r={,,,,,,} (3) C=(K,R),其中：k={1,2,3,4,5,6} R={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} (4) D=(K.R), K={48,25,64,57,82,36,75} R={r1,r2}

r1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>} r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<84,75>}

4

5、设有如图所示的逻辑结构图，给出它的逻辑结构。

6、简述下列术语：数据，数据元素，数据结构，数据对象。 7、逻辑结构与存储结构是什么关系?

8、将数量级2，n，n2，n3，nlog2n，log2n，2n，n，n!，

10?23?n，n23，按增长率进行排列。

五、算法设计题

1. 已知输入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法

的比较次数和元素移动次数。

2. 编写在输入10个数中找出最小或最大的数的算法。

3. 在数组A[n]中查找值为k的元素,若找到则输出其位置i(1≤i≤n),否则输出0作为标志。设计求解此问

题的类C语言算法，并分析其最坏情况时间复杂度。

5

第二章 线性表

一、选择题

1、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ ），删除一个元素需要移动的元素个数为（ ）。

A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/2 2、线性表是具有N个（ ）的有限序列。

A、表元素 B、字符 C、数据元素 D、数据项 E、信息 3、“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（ ）。

A、正确的 B、错误的 C、不一定，与具体结构有关。

4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。 5、带头结点的单链表为空的判定条件是（ ）。

A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ ）。

A、head==NULL B、head->next==NULL C、head->next==head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ ）。

A、P->NEXT=NULL B、p=NULL C、p->next==head D、p==head

8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。

A、O(1) B、O(n) C、O(n2) D、O(nlog2n)

9、在一个单链表中，若删除P所指结点的后继结点，则执行（ ）。

Ａ、p->next=p->next->next Ｂ、p=p->next;p->next=p->next->next Ｃ、p->next=p->next; Ｄ、p=p->next->next;

10、在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（ ）。

Ａ、s->next=p;p->next=s; Ｂ、s->next=p->next;p->next=s; Ｃ、s->next=p->next;p=s; Ｄ、p->next=s;s->next=p;

11、在一个单链表中，已知q是p的前趋结点，若q和p之间插入结点s，则执行（ ）。

Ａ、s-next=p->next;p->next=s; Ｂ、p->next=s->next;s->next=p; Ｃ、q->next=s;s->next=p;Ｄ、p->next=s;s->next=q;

6

12、假设双链表结点的类型如下： typedef struct linknode{

int data; ／／数据域

struct linknode *llink; ／／指向前趋结点的指针域 struct linknode *rlink; ／／指向后继结点的指针域 }bnode

现将一个q所指新结点作为非空双向链表中的p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（ ）。

Ａ、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q; Ｂ、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink Ｃ、q->llink=p->rlink;q->rlink=p;p->llink->rlink=q;p->llink=q; Ｄ、以上都不对

13、如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（ ）。

Ａ、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink; Ｂ、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink; Ｃ、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s; Ｄ、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;

14、在一个长度为n的单链表上，设有头和尾两个指针，执行（ ）操作与链表的长度无关。

Ａ、删除单链表中的第一个元素 Ｂ、删除单链表中最后一个元素

Ｃ、在单链表第一个元素前插入一个新元素 Ｄ、在单链表最后一个元素后插入一个新元素 15、线性结构中的一个结点代表一个（ ）

A、数据元素 B、数据项 C、数据 D、数据结构 16、非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（ ）

A、每个元素都有一个直接前驱和直接后继 B、线性表中至少要有一个元素

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

D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 17、顺序表是线性表的（ ）

A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构 18、对于顺序表，以下说法错误的是（ ）

A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

7