数据结构重点习题.pdfVIP

不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》

数据结构习题

1、设有数据结构(D,R)，其中

D={d1,d2,d3,d4,}

R={(d1,d2),(d2,d3),(d2,d4)}

画出它的逻辑结构图。

2、计算下列程序段的时间复杂度

s=0;

for(j=1;j=n;j*=2)

for(k=1;k=n;++k){s++;}

3、求整数n(n≥0)阶乘的算法如下，其时间复杂度是多少？

intfact(intn)

{if(n=1)return1;

returnn*fact(n-1);

}

4、用C或C++语言描述下列算法，并给出算法的时间复杂度。

（1）求一个n阶方阵的所有元素之和。

（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）对于输入的任意n个整数，输出其中的最大元素和最小元素。

5、编写从顺序表中删除其值等于X的所有元素的算法。

6、设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序

存储结构）的适当位置上，并保持线性表的有序性。

7、设将n(n1)个整数存放到一维数组R中。设计一个在时间和空间两方面

尽可能高效的算法。将R中的序列循环左移P（0Pn）个位置，即将R中的数

据由(X0,X1,……Xn-1)变换为(Xp,Xp-1…Xn-1，X0,X1……Xp-1)要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出

注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。

8、设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，

试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

不飞则已，一飞冲天；不鸣则已，一鸣惊人。——《韩非子》

9、设计一个算法，将一个带头结点的数据域依次为a1，a2，a3，……an（n

≥3）的单链表的所有结点逆置。

10、已知一个带有表头结点的单链表，结点结构为datalink

假设该链表只给出了头指针list。在不改变链表的前提下，

请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整

数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0；要

求：

（1）描述算法的基本设计思想；

（2）描述算法的详细实现步骤；

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++

或JAVA语言实现），关键之处请给出简要注释。

11、

12、有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序

中，以元素C、D最先出栈（即C第一且D第二个出栈）的次序有哪几个？

13、假设以I和O分别表示进栈和出栈操作，栈的初态和终态均为空，进栈

和出栈的操作序列可表示为仅由I和O组成的序列。

（1）下面所示的序列中哪些是合法的？

A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO