数据结构习题（有答案）

数据结构

4星 · 超过85%的资源需积分: 10 112 浏览量更新于2023-07-18 评论 2 收藏 108KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

第一章：绪论第二章线性表

一、名词解释

数据数据项数据元素数据结构数据逻辑结构数据物理结构算法算法的时间复杂性

二、简答

1. 算法分析的目的是什么？

2. 什么是算法的最坏和平均时间复杂性？

3.什么是线性表？线性表的主要运算有哪些？

4. 试比较顺序表与链表的优缺点。

5. 试分析单链表与双链表的优缺点。

6. 为什么在单循环链表中设置尾指针比设置头指针更好？

7. 写出在循环双链表中的 p 所指结点之后插入一个 s 所指结点的操作。

8. 写出在单链表中的 p 所指结点之前插入一个 s 所指结点的操作。

9. 请利用链表来表示下面一元多项式

三、分析下列算法的时间复杂性:

1．sum=0;

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

{

sum=sum+i;

}

2．i=1;

while(i<=n)

i=i*10;

3．sum=0;

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

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

sum=sum+Array[i][j];

四、算法题

1. 设有一 n 个元素的线性表，用一维数组 A[n]表示。试设计一个算法，使此线性表元素的排队次序颠倒过来但仍存储

于原数组中。

2. 有一个有 n 个结点的单链表，设计一个函数将第 i-1 个结点与第 i 个结点互换，但指针不变。

3. 设计一个函数，查找单链表中数值为 x 的结点。

4. 已知一个单链表，编写一个删除其值为 x 的结点的前趋结点的算法。

5. 已知一个单链表，编写一个函数从此单链表中删除自第 i 个元素起的 length 个元素。

6. 已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为 x 的结点，使插入后该链表仍然递增有序。

7. 已知一个单链表，编写一个函数将此单链表复制一个拷贝。

8. 有一个共 10 个结点的单链表，试设计一个函数将此单链表分为两个结点数相等的单链表。

9. 与上题相同的单链表，设计一个函数，将此单链表分成两个单链表，要求其中一个仍以原表头指针 head1 作表头指

针，表中顺序包括原线性表的第一、三等奇数号结点；另一个链表以 head2 为表头指针，表中顺序包括原单链表第二、

四等号结点。

10. 已知一个指针 p 指向单循环链表中的一个结点，编写一个对此单循环链表进行遍历的算法。

11. 已知一个单循环链表，编写一个函数，将所有箭头方向取反。

12. 在双链表中，若仅知道指针 p 指向某个结点，不知头指针，能否根据 p 遍历整个链表？若能，试设计算法实现。

13. 试编写一个在循环双向链表中进行删除操作的算法，要求删除的结点是指定结点 p 的前趋结点。

习题解答：

一、名词解释答案

数据：就是一切能够由计算机接受和处理的对象。

数据项：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。

数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理，也称为元素、顶点或记录。它可以由若干个

数据项组成。

数据结构：指的是数据之间的相互关系，即数据的组织形式，它包括数据的逻辑结构、数据的存储结构和数据的运算

三个方面的内容。

数据逻辑结构：是指数据元素之间的逻辑关系，是从逻辑上描述数据，与数据的存储无关，独立于计算机。

数据物理结构：是指数据元素及其关系在计算机存储器内的表示，是数据的逻辑结构用计算机语言的实现，是依赖于

计算机语言的。

算法：是对特定问题求解步骤的一种描述。它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运

算。由此问题相关的一定输入，计算机依照这些规则进行计算和处理，经过有限的计算步骤后能得到一定的输出。

算法的时间复杂性：是该算法的时间耗费，它是该算法所求解问题规模 n 的函数。当 n 趋向无穷大时，我们把时间复

杂性 T(n)的数量级称为算法的渐进时间复杂性。

二、简答题答案

1. 答：对算法进行分析的目的有两个：第一个目的是可以从解决同一问题的不同算法中区分相对优劣，选出较为适用

的一种；第二个目的是有助于设计人员考虑对现有算法进行改进或设计出新的算法。

2. 答：算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间；平均时间复杂性是研究同样的 n

值时各种可能的输入，取它们运算时间的平均值。

3. 2. 答：线性表是由有限数目的相同类型元素组成的序列。表中的数据元素，除了第一个和最后一个以外，都有一个

且只有一个前驱元素，同时也都有一个且只有一个后继元素；第一个元素只有一个后继元素而无前驱元素；最后一个

元素只有一个前驱元素而无后继元素。线性表的元素个数 n 称为这个表的长度，当 n=0 时，这个表叫做空表。

线性表的主要运算包括：

(1) 求线性表的长度 n；

(2) 在第 i 个数据元素前面插入一个新的数据元素；

(3) 删除第 i 个数据元素；

(4) 存取或更新线性表第 i 个元素；

(5) 将两个或两个以上的线性表合并成一个线性表；

(6) 将一个线性表拆成多个线性表；

(7) 将线性表中个数据元素按某个域值（如关键字）递增或递减的顺序重新排列；

(8) 在线性表中查找满足某种条件的数据元素；

4．答：顺序表用结点物理位置的相邻性来反映结点间的逻辑关系，其优点是：节省存储、随机存取，当表长变化较

小，主要操作是进行查找时，宜采用顺序表。链表用附加的指针来反映结点间的逻辑关系，插入和删除操作相对比较

方便，当表长变化较大，主要操作是进行插入和删除时，宜采用链表。

5. 答：双链表比单链表多增加了一个指针域以指向结点的直接前趋，它是一种对称结构，因此在已知某个结点之前或

之后插入一个新结点、删除该结点或其直接后继都同样方便,操作的时间复杂度为 O(1)；而单链表是单向结构，对于

找一个结点的直接前趋的操作要从开始结点找起，其时间复杂度为 O(n)。

6. 答：由于对表的操作常常在表的两端进行，所以对单循环链表，当知道尾指针 rear 后，其另一端的头指针是 rear-

>next->next（表中带头结点）。这会使操作变的更加容易。

7. 答：

s->prior=p;

s->next=p->next;

p->next->prior=s;

p->next=s;

8. 答：

s->next=p->next;

p->next=s;

temp=p->data;

p->data=s->data;

s->data=temp;

9. 答：多项式 A(x)用链表表示如下：

三、答案

1．答：该程序段的时间复杂性为 T(n)=O(n)。

2．答：该程序段的时间复杂性 T(n)=O(log10n)。

剩余18页未读，继续阅读

dreamgirl55

2012-09-05

还比较详细吧

cll20

粉丝: 0
资源: 2

会员权益专享

数据结构习题（有答案）

评论1

会员权益专享

最新资源

数据结构习题（有答案）

评论1

数据结构习题集及答案

数据结构习题及习题集部分答案

数据结构习题集

数据结构(殷人昆)练习题答案及源码.rar

浙江大学数据结构习题

数据结构课后习题答案

数据结构PAT练习题

数据结构题库及答案csdn

数据结构习题库1-8章测试题 章节练习带答案 pdf

数据结构算法与应用c++语言描述 习题答案

数据结构与算法分析 c语言描述(原书第2版)课后习题参考答案

数据结构1800题pdf

数据结构与算法分析–c++描述(第2版,weiss著,含习题答案)

浙大数据结构课后习题

数据结构基于c语言的描述习题答案

数据结构c语言版答案

数据结构(java语言描述)第三版课后习题答案

《数据结构算法与应用：C++语言描述》第二版 课后习题答案

出几个题目，关于数据结构简答题的习题及答案。

浙江大学数据结构习题集

会员权益专享

最新资源

数据结构习题库1-8章测试题章节练习带答案 pdf

数据结构算法与应用c++语言描述习题答案

《数据结构算法与应用：C++语言描述》第二版课后习题答案