没有合适的资源?快使用搜索试试~ 我知道了~
数据结构及算法课后习题答案.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 197 浏览量
2021-10-02
11:11:38
上传
评论
收藏 581KB DOC 举报
温馨提示
试读
38页
数据结构及算法课后习题答案.doc
资源推荐
资源详情
资源评论
. .
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;/*插入成功*/
}
. .word.zl.
. .
}
时间复杂度为 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);
elsereturn (0);
}
. .word.zl.
. .
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 个元素进展整体互换。即将线性表:
〔a
1
, a
2
, … , a
m
, b
1
, b
2
, … , b
n
〕改变为:
〔b
1
, b
2
, … , b
n
, a
1
, a
2
, … , a
m
〕。
【提示】比拟 m 和 n 的大小,假设 m<n,那么将表中元素依次前移 m 次;否那么,将表
中元素依次后移 n 次。
voidprocess(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];
. .word.zl.
. .
for(k=L->last-1;k>=0;k--)
L->data[k+1]=L->data[k];
L->data[0]=x;
}
}
6.带头结点的单链表 L 中的结点是按整数值递增排列的,试写一算法,将值为 x 的
结点插入到表 L 中,使得 L 仍然递增有序,并且分析算法的时间复杂度。
LinkList insert(LinkList L,int x)
{p=L;
while(p->next&&x>p->next->data)
p=p->next;/*寻找插入位置*/
s=(LNode *)malloc(sizeof(LNode));/*申请结点空间*/
s->data=x; /*填装结点*/
s->next=p->next;
p->next=s;/*将结点插入到链表中*/
return(L);
}
7.假设有两个已排序〔递增〕的单链表 A 和 B,编写算法将它们合并成一个链表 C
而不改变其排序性。
LinkList bine(LinkList A, LinkList B)
{C=A;
rc=C;
pa=A->next;/*pa 指向表 A 的第一个结点*/
pb=B->next;/*pb 指向表 B 的第一个结点*/
free(B);/*释放 B 的头结点*/
while(pa&&pb)/*将 pa、pb 所指向结点中,值较小的一个插入到链表 C 的表尾*/
if(pa->data<pb->data)
{rc->next=pa;
rc=pa;
pa=pa->next;
}
else
{rc->next=pb;
rc=pb;
pb=pb->next;
}
if(pa)rc->next=pa;
elserc->next=pb;/*将链表 A 或 B 中剩余的局部到链表 C 的表尾*/
return(C);
}
8.假设长度大于 1 的循环单链表中,既无头结点也无头指针,p 为指向该链表中某一
结点的指针,编写算法删除该结点的前驱结点。
【提示】利用循环单链表的特点,通过 s 指针可循环找到其前驱结点 p 及 p 的前驱结点
q,然后可删除结点*p。
. .word.zl.
. .
viod delepre(LNode *s)
{LNode *p, *q;
p=s;
while (p->next!=s)
{q=p;
p=p->next;
}
q->next=s;
free(p);
}
9.两个单链表 A 和 B 分别表示两个集合,其元素递增排列,编写算法求出 A 和 B 的
交集 C,要求 C 同样以元素递增的单链表形式存储。
【提示】交集指的是两个单链表的元素值一样的结点的集合,为了操作方便,先让单链表
C 带有一个头结点,最后将其删除掉。算法中指针 p 用来指向 A 中的当前结点,指针 q 用
来指向 B 中的当前结点,将其值进展比拟,两者相等时,属于交集中的一个元素,两者不
等时,将其较小者跳过,继续后面的比拟。
LinkList Intersect(LinkList A, LinkList B)
{LNode *q, *p, *r, *s;
LinkList C;
C= (LNode *)malloc(sizeof(LNode));
C->next=NULL;
r=C;
p=A;
q=B;
while (p && q )
if (p->data<q->data) p=p->next;
elseif (p->data==q->data)
{s=(LNode *)malloc(sizeof(LNode));
s->data=p->data;
r->next=s;
r=s;
p=p->next;
q=q->next;
}
else q=q->next;
r->next=NULL;
C=C->next;
return C;
}
10.设有一个双向链表,每个结点中除有 prior、data 和 next 域外,还有一个访问
频 度 freq 域 , 在 链 表 被 起 用 之 前 , 该 域 的 值 初 始 化 为 零 。 每 当 在 链 表 进 展 一 次
Locata(L,x)运算后,令值为 x 的结点中的 freq 域增 1,并调整表中结点的次序,使其按
访问频度的非递增序列排列,以便使频繁访问的结点总是靠近表头。试写一个满足上述要
求的 Locata(L,x)算法。
. .word.zl.
剩余37页未读,继续阅读
资源评论
gjmm89
- 粉丝: 14
- 资源: 19万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功