《数据结构与算法》课后习题答案

3.0 文小白 2023-09-15 59 0 635KB 37 页 10文币
侵权投诉
2.3 课后习题解答
2.3.2 判断题
1．线性表的逻辑顺序与存储顺序总是一致的。（×）
2．顺序存储的线性表可以按序号随机存取。（√）
3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一
半的元素需要移动。（×）
4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，
因此属于同一数据对象。（√）
5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（×）
6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）
7．线性表的链式存储结构优于顺序存储结构。（×）
8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）
9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）
10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随
机存取的存储结构。（×）
11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第 i个元素
的时间与 i无关。（×）
12．线性表的特点是每个元素都有一个前驱和一个后继。（×）
2.3.3 算法设计题
1．设线性表存放在向量 A[arrsize]的前 elenum 个分量中，且递增有序。试写一算法，
将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的
相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分
配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中
元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下
标端开始一边比较，一边移位）然后插入 x ，最后修改表示表长的变量。
int insert (datatype A[],int *elenum,datatype x) /*设elenum 为表的最大下标*/
{if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/
else {i=*elenum;
while (i>=0 && A[i]>x) /*边找位置边移动*/
{A[i+1]=A[i];
i--;
}
A[i+1]=x; /*找到的位置是插入位的下一位*/
(*elenum)++;
return 1; /*插入成功*/
}
}
时间复杂度为 O(n)。
2．已知一顺序表 A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值
相同的元素。
【提示】对顺序表 A，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；
再对第二个元素做同样处理，依此类推。
void delete(Seqlist *A)
{i=0;
while(i<A->last) /*将第 i个元素以后与其值相同的元素删除*
/
{k=i+1;
while(k<=A->last&&A->data[i]==A->data[k])
k++; /*使k指向第一个与 A[i]不同的元素*/
n=k-i-1; /*n 表示要删除元素的个数*/
for(j=k;j<=A->last;j++)
A->data[j-n]=A->data[j]; /*删除多余元素*/
A->last= A->last -n;
i++;
}
}
3．写一个算法，从一个给定的顺序表 A中删除值在 x~y(x<=y)之间的所有元素，要求
以较高的效率来实现。
【提示】对顺序表 A，从前向后依次判断当前元素 A->data[i]是否介于 x和y之间，若是，并
不立即删除，而是用 n记录删除时应前移元素的位移量；若不是，则将 A->data[i]向前移动
n位。n用来记录当前已删除元素的个数。
void delete(Seqlist *A,int x,int y)
{i=0;
n=0;
while (i<A->last)
{if (A->data[i]>=x && A->data[i]<=y) n++; /*若A->data[i] 介于 x和y之间，n自增*/
else A->data[i-n]=A->data[i]; /*否则向前移动 A->data[i]*/
i++;
}
A->last-=n;
}
4．线性表中有 n个元素，每个元素是一个字符，现存于向量 R[n]中，试写一算法，使
R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素
移动次数最小。
【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在
字母之后，其它字符之前。
int fch(char c) /*判断 c是否字母*/
{if(c>='a'&&c<='z'||c>='A'&&c<='Z') return (1);
else return (0);
}
int fnum(char c) /*判断 c是否数字*/
{if(c>='0'&&c<='9') return (1);
else return (0);
}
void process(char R[n])
{low=0;
high=n-1;
while(low<high) /*将字母放在前面*/
{while(low<high&&fch(R[low])) low++;
while(low<high&&!fch(R[high])) high--;
if(low<high)
{k=R[low];
R[low]=R[high];
R[high]=k;
}
}
low=low+1;
high=n-1;
while(low<high) /*将数字放在字母后面，其它字符前面*/
{while(low<high&&fnum(R[low])) low++;
while(low<high&&!fnum(R[high])) high--;
if(low<high)
{k=R[low];
R[low]=R[high];
R[high]=k;
}
}
}
5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前 m
个元素和后 n个元素进行整体互换。即将线性表：
（a1, a2, … , am, b1, b2, … , bn）改变为：
（b1, b2, … , bn , a1, a2, … , am）。
【提示】比较 m和n的大小，若 m<n，则将表中元素依次前移 m次；否则,将表中元素依次
后移 n次。
void process(Seqlist *L,int m,int n)
{if(m<=n)
for(i=1;i<=m;i++)
{x=L->data[0];
for(k=1;k<=L->last;k++)
L->data[k-1]=L->data[k];
L->data[L->last]=x;
}
else for(i=1;i<=n;i++)
{x=L->data[L->last];
for(k=L->last-1;k>=0;k- -)
L->data[k+1]=L->data[k];
摘要：

2.3课后习题解答2.3.2判断题1．线性表的逻辑顺序与存储顺序总是一致的。（×）2．顺序存储的线性表可以按序号随机存取。（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）7．线性表的链式存储结构优于顺序存储结构。（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元...

展开>> 收起<<
《数据结构与算法》课后习题答案.doc

共37页,预览10页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：文小白 分类：教育专区 价格：10文币 属性：37 页 大小：635KB 格式：doc 时间：2023-09-15

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关文档

更多

推荐作者

热门标签

/ 37
评分 收藏
分享
立即下载
客服
关注