数据结构1800答案解析：绪论与基础题型详解

需积分: 50 81 浏览量更新于2024-07-31 收藏 1010KB PDF 举报

"数据结构1800答案.pdf" 本资源提供了《数据结构1800》课程的相关习题答案与讲解，主要涵盖了数据结构的基础知识，旨在帮助学习者进行自我检验和理解巩固。数据结构是计算机科学中的核心课程，它探讨了如何有效地组织和管理数据，以便于高效地执行各种计算任务。 1. 绪论 - 绪论部分通常会介绍数据结构的基本概念，包括数据元素、数据元素间的关系，以及数据结构的分类，如集合、线性结构、树形结构、图状结构或网状结构。 2. 选择题 - 选择题涉及了数据结构的基础理论，例如数据的逻辑特性、物理表示、算法的时间复杂度和空间复杂度等概念。 3. 判断题 - 判断题测试了学习者对数据结构基本原理的理解，如数据元素的关联方式、算法的可行性、时间复杂度的评估等。 4. 填空题 - 填空题主要考察了数据结构的几个关键概念，如逻辑结构、物理结构、操作（运算）、算法的特性（有穷性、确定性、可行性）以及不同操作的时间复杂度。 5. 应用题 - 应用题则要求将理论知识应用于实际问题，比如解释数据结构的定义，以及数据结构的存储方式，如顺序存储（便于访问，但插入删除操作较复杂）、链式存储（动态操作方便，存储空间利用率低）和索引存储（快速查找，但需要额外的索引空间）。通过这份答案，学习者可以检查自己对数据结构的理解程度，同时通过详细的解答，加深对数据结构中抽象概念和实际应用的理解。在学习过程中，掌握这些知识点对于编写高效的算法和解决复杂问题至关重要。此外，学习者还可以了解到如何评估算法的性能，如时间复杂度的计算，这是衡量算法效率的重要指标。这份资源是学习数据结构时非常有价值的参考资料。

第

章

线性表

http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/...

第12页共23页 2005-9-23 17:54

q->link= list->link；∥将q结点插到链表最前面。

list->link=q；

}

}∥算法结束

[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。

11．[题目分析] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱

的前驱结点，后继结点）六条链。

void Exchange（LinkedList p）

∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。

{q=p->llink；

q->llink->rlink=p； ∥p的前驱的前驱之后继为p

p->llink=q->llink； ∥p的前驱指向其前驱的前驱。

q->rlink=p->rlink； ∥p的前驱的后继为p的后继。

q->llink=p； ∥p与其前驱交换

p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱

p->rlink=q； ∥p的后继指向其原来的前驱

}∥算法exchange结束。

12．[题目分析] 顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在

表中查找数值为x的元素”，这里应使用折半查找方法。

void SearchExchangeInsert（ElemType a[]；ElemType x）

∥a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交

换位置；如查不到，则插入表中，且使表仍递增有序。

{ low=0；high=n-1； ∥low和high指向线性表下界和上界的下标

while（low<=high）

{mid=（low+high）/2； ∥找中间位置

if（a[mid]==x） break； ∥找到x，退出while循环。

else if （a[mid] <x） low=mid+1；∥到中点mid的右半去查。

else high=mid-1； ∥到中点mid的左部去查。

}

if（a[mid]==x && mid!=n）∥ 若最后一个元素与x相等，则不存在与其后继交换的操作。

{t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；} ∥ 数值x与其后继元素位置交换。

if（low>high） ∥查找失败，插入数据元素x

{for（i=n-1；i>high；i--） a[i+1]=a[i]；∥后移元素。

a[i+1]=x；∥插入x。

} ∥结束插入

}∥结束本算法。

[算法讨论] 首先是线性表的描述。算法中使用一维数组a表示线性表，未使用包含数据元素的一维数组和

指示线性表长度的结构体。若使用结构体，对元素的引用应使用a.elem[i]。另外元素类型就假定是ElemType，

未指明具体类型。其次，C中一维数组下标从0开始，若说有n个元素的一维数组，其最后一个元素的下标应是

n-1。第三，本算法可以写成三个函数，查找函数，交换后继函数与插入函数。写成三个函数显得逻辑清晰，易

读。

13．[题目分析] 判断链表中数据是否中心对称，通常使用栈。将链表的前一半元素依次进栈。在处理链表

的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两元素比较，若相等，则将链表中下

一元素与栈中再弹出元素比较，直至链表到尾。这时若栈是空栈，则得出链表中心对称的结论；否则，当链表

中一元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。

int dc（LinkedList h，int n）

∥ h是带头结点的n个元素单链表，链表中结点的数据域是字符。本算法判断链表是否是中心对称。

{char s[]; int i=1；∥i记结点个数， s字符栈

p=h->next；∥p是链表的工作指针，指向待处理的当前元素。

for（i=1；i<=n/2；i++）∥ 链表前一半元素进栈。

{s[i]=p->data；p=p->next；}

i--; ∥恢复最后的i值

if（n%2==1）p=p->next；} ∥若n是奇数，后移过中心结点。

while（p!=null && s[i]==p->data）{i--；p=p->next；} ∥测试是否中心对称。

if（p==null）return（1）；∥链表中心对称

else return（0）； ∥链表不中心对称

}∥算法结束。

[算法讨论] 算法中先将“链表的前一半”元素（字符）进栈。当n为偶数时，前一半和后一半的个数相

同；当n为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。比较过程中遇到不相等

时，立即退出while循环，不再进行比较。

14．[题目分析] 在单链表中删除自第i个元素起的共len个元素，应从第1个元素起开始计数，记到第i个时

第

章

线性表

http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/...

第13页共23页 2005-9-23 17:54

开始数len个，然后将第i-1个元素的后继指针指向第i+len个结点，实现了在A链表中删除自第i个起的len个结

点。这时应继续查到A的尾结点，得到删除元素后的A链表。再查B链表的第j个元素，将A链表插入之。插入和删

除中应注意前驱后继关系，不能使链表“断链”。另外，算法中应判断i，len和j的合法性。

LinkedList DelInsert（LinkedList heada，headb，int i，j，len）

∥heada和headb均是带头结点的单链表。本算法删除heada链表中自第i个元素起的共len个元素，然后将单链

表heada插入到headb的第j个元素之前。

{if（i<1 || len<1 || j<1）{printf（“参数错误\n”）；exit（0）；}∥参数错，退出算法。

p=heada；∥p为链表A的工作指针，初始化为A的头指针，查到第i个元素时，p指向第i-1个元素

k=0；∥计数

while（p!=null && k<i-1）∥查找第i个结点。

{k++；p=p->next；}

if（p==null）{printf（“给的%d太大\n”,i）；exit（0）；} ∥i太大，退出算法

q=p->next；∥q为工作指针，初始指向A链表第一个被删结点。

k=0；

while（q!=null && k<len）{k++；u=q，q=q->next；free（u）；} ∥删除结点，后移指针。

if（k<len）{printf（“给的%d太大\n”,len）；exit（0）；}

p->next=q；∥A链表删除了len个元素。

if (heada->next!=null) ∥heada->next=null说明链表中结点均已删除，无需往B表插入

{while（p->next!=null）p= p->next；∥找A的尾结点。

q=headb；∥q为链表B的工作指针。

k=0；∥计数

while（q!=null && k<j-1） ∥查找第j个结点。

{k++；q= q->next；} ∥查找成功时，q指向第j-1个结点

if（q==null）{printf（“给的%d太大\n”,j）；exit（0）；}

p->next=q->next； ∥将A链表链入

q->next=heada->next； ∥A的第一元素结点链在B的第j-1个结点之后

}//if

free（heada）；∥释放A表头结点。

}∥算法结束。

与本题类似的题的解答如下：

（1）本题与第14题基本相同，不同之处仅在于插入B链表第j个元素之前的，不是删除了len个元素的A链

表，而是被删除的len个元素。按照上题，这len个元素结点中第一个结点的指针p->next，查找从第i个结点开

始的第len个结点的算法修改为：

k=1；q=p->next； //q指向第一个被删除结点

while（q!=null && k<len）

∥查找成功时，q指向自i起的第len个结点。

{k++；q= q->next；}

if（k<len） {printf（“给的%d太大\n”,len）；exit（0）；}

15．[题目分析] 在递增有序的顺序表中插入一个元素x，首先应查找待插入元素的位置。因顺序表元素递

增有序，采用折半查找法比顺序查找效率要高。查到插入位置后，从此位置直到线性表尾依次向后移动一个元

素位置，之后将元素x插入即可。

void Insert（ElemType A[]，int size, ElemType x）

∥ A是有size个元素空间目前仅有num（num<size）个元素的线性表。本算法将元素x插入到线性表中，并保

持线性表的有序性。

{low=1；high=num； //题目要求下标从1开始

while（low<=high）∥对分查找元素x的插入位置。

{mid=（low+high）/2；

if（A[mid]==x）{low=mid+1；break；}

else if（A[mid]>x）high=mid-1 ；else low=mid+1 ；

}

for（i=num；i>=low；i--） A[i+1]=A[i]；∥元素后移。

A[i+1]=x； ∥将元素x插入。

}算法结束。

[算法讨论] 算法中当查找失败（即线性表中无元素x）时，变量low在变量high的右面（low=high+1）。移

动元素从low开始，直到num为止。特别注意不能写成for（i=low；i<=num；i++）A[i+1]=A[i]，这是一些学生

容易犯的错误。另外，题中未说明若表中已有值为x的元素时不再插入，故安排在A[mid]= =x时，用low（=mid+1

）记住位置，以便后面统一处理。查找算法时间复杂度为O（logn），而插入时的移动操作时间复杂度为O

（n），若用顺序查找，则查找的时间复杂度亦为O（n）。

类似本题的其它题的解答：

（1）[题目分析] 本题与上面15题类似，不同之处是给出具体元素值，且让编写turbo pascal程序，程序如

下：

PROGRAM example（input，output）；

第

章

线性表

http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/...

第14页共23页 2005-9-23 17:54

TYPE pointer=^node；

node=RECORD

data：integer；

next：pointer；

END；

VAR head，q：pointer；

PROCEDURE create（VAR la：pointer）；

VAR x：integer；

p,q：pointer；

BEGIN

new（la）；la^.next:=NIL；{建立头结点。}

read（x）；q:=la；{q用以指向表尾。}

WHILE NOT EOF DO {建立链表}

BEGIN

new（p）；p^.data:=x；p^.next:=q^.next；q^.next:=p；q:=p; read(x);

END；

PROCEDURE insert（VAR la：pointer；s：pointer）；

VAR p,q：pointer；found：boolean；

BEGIN

p:= la^.next；{p为工作指针。}

q:=la；{q为p的前驱指针。}

found:=false；

WHILE（p<>NIL）AND NOT found

IF（p^.data<x）THEN BEGIN q:=p；p:= p^.next； END

ELSE found:=true；

s^.next:=p；{将s结点插入链表}

q^.next:=s；

END；

BEGIN {main}

writeln（“请按顺序输入数据，建立链表”）

create（head）；

writeln（“请输入插入数据”）

new（q）；

readln（q^.data）；

insert（head，q）；

END.{程序结束}

[程序讨论] 在建立链表时，输入数据依次为12，13，21，24，28，30，42，键入CTRL-Z，输入结束。

“插入数据”输26即可。本题编写的是完整的pascal程序。

16．[题目分析] 将具有两个链域的单循环链表，改造成双向循环链表，关键是控制给每个结点均置上指向

前驱的指针，而且每个结点的前驱指针置且仅置一次。

void StoDouble（LinkedList la）

∥la是结点含有pre，data，link三个域的单循环链表。其中data为数据域,pre为空指针域，link是指向

后继的指针域。本算法将其改造成双向循环链表。

{while（la->link->pre==null）

{la->link->pre=la； ∥将结点la后继的pre指针指向la。

la=la->link； ∥la指针后移。

}

} ∥算法结束。

[算法讨论] 算法中没有设置变量记住单循环链表的起始结点，至少省去了一个指针变量。当算法结束时，

la恢复到指向刚开始操作的结点，这是本算法的优点所在。

17．[题目分析] 求两个集合A和B的差集A-B，即在A中删除A和B中共有的元素。由于集合用单链表存储，问

题变成删除链表中的结点问题。因此，要记住被删除结点的前驱，以便顺利删除被删结点。两链表均从第一元

素结点开始，直到其中一个链表到尾为止。

void Difference（LinkedList A，B，*n）

∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A

中，*n是结果集合中元素个数，调用时为0

{p=A->next； ∥p和q分别是链表A和B的工作指针。

q=B->next； pre=A； ∥pre为A中p所指结点的前驱结点的指针。

while（p!=null && q!=null）

if（p->data<q->data）{pre=p；p=p->next；*n++；} ∥ A链表中当前结点指针后移。

第

章

线性表

http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/...

第15页共23页 2005-9-23 17:54

else if（p->data>q->data）q=q->next； ∥B链表中当前结点指针后移。

else {pre->next=p->next； ∥处理A，B中元素值相同的结点，应删除。

u=p； p=p->next； free（u）；} ∥删除结点

18．[题目分析] 本题要求对单链表结点的元素值进行运算，判断元素值是否等于其序号的平方减去其前驱

的值。这里主要技术问题是结点的序号和前驱及后继指针的正确指向。

int Judge（LinkedList la）

∥la是结点的元素为整数的单链表。本算法判断从第二结点开始，每个元素值是否等于其序号的平方减去其前

驱的值，如是返回true；否则，返回false。

{p=la->next->next；∥p是工作指针，初始指向链表的第二项。

pre=la->next； ∥pre是p所指结点的前驱指针。

i=2； ∥i是la链表中结点的序号，初始值为2。

while（p!=null）

if（p->data==i*i-pre->data）{i++；pre=p；p=p->next；} ∥结点值间的关系符合题目要求

else break； ∥当前结点的值不等于其序号的平方减去前驱的值。

if（p!=null）return（false）； ∥未查到表尾就结束了。

else return（true）； ∥成功返回。

}∥算法结束。

[算法讨论]本题不设头结点也无影响。另外，算法中还可节省前驱指针pre，其算法片段如下：

p=la；∥假设无头结点，初始p指向第一元素结点。

i=2；

while（p->next!=null） ∥初始p->next指向第二项。

if（p->next->data= =i*i-p->data）

{i++；p=p->next；}

if（p->next!=null）return（false）；∥失败

else return（true）； ∥成功

19．[题目分析] 本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存

入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从

上次开始比较结点的后继开始，B链表仍从第一结点开始比较，直到B链表到尾表示匹配成功。A链表到尾B链表

未到尾表示失败。操作中应记住A链表每次的开始结点，以便下趟匹配时好从其后继开始。

int Pattern（LinkedList A，B）

∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；否则，返回0表示失

败。

{p=A； ∥p为A链表的工作指针，本题假定A和B均无头结点。

pre=p； ∥pre记住每趟比较中A链表的开始结点。

q=B； ∥q是B链表的工作指针。

while（p && q）

if（p->data==q->data） {p=p->next；q=q->next；}

else{pre=pre->next；p=pre； ∥A链表新的开始比较结点。

q=B；} ∥q从B链表第一结点开始。

if（q==null）return（1）； ∥B是A的子序列。

else return（0）； ∥B不是A的子序列。

}∥算法结束。

20．[题目分析] 本题也是模式匹配问题，应先找出链表L2在链表L1中的出现，然后将L1中的L2倒置过来。

设L2在L1中出现时第一个字母结点的前驱的指针为p，最后一个字母结点在L1中为q所指结点的前驱，则在保存p

后继结点指针(s)的情况下，执行p->next=q。之后将s到q结点的前驱依次插入到p结点之后，实现了L2在L1中的

倒置。

LinkedList PatternInvert（LinkedList L1，L2）

∥L1和L2均是带头结点的单链表，数据结点的数据域均为一个字符。本算法将L1中与L2中数据域相同的连续结

点的顺序完全倒置过来。

{p=L1； ∥p是每趟匹配时L1中的起始结点前驱的指针。

q=L1->next； ∥q是L1中的工作指针。

s=L2->next； ∥s是L2中的工作指针。

while（p!=null && s!=null）

if（q->data==s->data）{q=q->next;s=s->next;} ∥对应字母相等，指针后移。

else {p=p->next；q=p->next；s=L2->next；} ∥失配时，L1起始结点后移，L2从首结点开始。

if（s==null）∥匹配成功，这时p为L1中与L2中首字母结点相同数据域结点的前驱，q为L1中与L2最后一个结

点相同数据域结点的后继。

{r=p->next； ∥r为L1的工作指针，初始指向匹配的首字母结点。

p->next=q； ∥将p与q结点的链接。

while（r!=q）； ∥逐结点倒置。

{s=r->next； ∥暂存r的后继。

第

章

线性表

http://www.bjdisong.com/zzu/kaoyan/document/kaoyan/daan/...

第16页共23页 2005-9-23 17:54

r->next=p->next；∥将r所指结点倒置。

p->next=r；

r=s； ∥恢复r为当前结点。

}

else printf（“L2并未在L1中出现”）；

} ∥算法结束。

[算法讨论] 本算法只讨论了L2在L1至多出现一次（可能没出现），没考虑在L1中多次出现的情况。若考

虑多次出现，可在上面算法找到第一次出现后的q结点作L1中下次比较的第一字母结点，读者可自行完善之。

类似本题的另外叙述题的解答：

（1）[题目分析] 本题应先查找第i个结点，记下第i个结点的指针。然后从第i+1个结点起，直至第m（1<i<m

）个结点止，依次插入到第i-1个结点之后。最后将暂存的第i个结点的指针指向第m结点，形成新的循环链表，

结束了倒置算法。

LinkedList PatternInvert1（LinkedList L，int i，m）

∥L是有m个结点的链表的头结点的指针。表中从第i（1<i<m）个结点到第m个结点构成循环部分链表，本算

法将这部分循环链表倒置。

{if（i<1|| i>=m || m<4）{printf（“%d,%d参数错误\n”,i，m）；exit（0）；}

p=L->next->next； ∥p是工作指针，初始指向第二结点（已假定i>1）。

pre=L->next； ∥pre是前驱结点指针，最终指向第i-1个结点。

j=1； ∥计数器

while（j<i-1） ∥查找第i个结点。

{j++；pre=p；p=p->next；}∥查找结束，p指向第i个结点。

q=p； ∥暂存第i个结点的指针。

p=p->next； ∥p指向第i+1个结点，准备逆置。

j+=2； ∥上面while循环结束时，j=i-1，现从第i+1结点开始逆置。

while（j<=m）

{r=p->next； ∥暂存p的后继结点。

p->next=pre->next；∥逆置p结点。

pre->next=p；

p=r； ∥p恢复为当前待逆置结点。

j++； ∥计数器增1。

}

q->next=pre->next；∥将原第i个结点的后继指针指向原第m个结点。

[算法讨论] 算法中未深入讨论i，m，j的合法性，因题目的条件是m>3且1<i<m。因此控制循环并未用指针

判断（如一般情况下的p!=null），结束循环也未用指针判断。注意最后一句q->next=pre->next，实现了从原

第i个结点到原第m个结点的循环。最后pre->next正是指向原第m个结点，不可用p->next代替pre->next。

21．[题目分析] 顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的

初值和终值。

void SeqInvert（ElemType a[ ]，int n）

∥a是具有n个元素用一维数组存储的线性表，本算法将其逆置。

{for（i=0；i<=（n-1）/2；i++）

{t=a[i]；a[i]= a[n-1-i]；a[n-1-i]=t；}

}∥算法结束

[算法讨论] 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n个元素的下标是n-1。因

为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n为偶数，“一半”恰好是线性表长度的二分之

一；若n是奇数，“一半”是小于n/2的最大整数，这时取大于1/2的最小整数的位置上的元素，恰是线性表中间

位置的元素，不需要逆置。另外，由于pascal数组通常从下标1开始，所以，上下界处理上略有不同。这点请读

者注意。

类似本题的其它题的解答：

这一组又选了6个题，都是单链表（包括单循环链表）的逆置。链表逆置的通常作法是：将工作指针指向第

一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头

结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。

（1）要求编程实现带头结点的单链表的逆置。首先建立一单链表，然后逆置。

typedef struct node

{int data；∥假定结点数据域为整型。

struct node *next；

}node,*LinkedList；

LinkedList creat（）

{LinkedList head，p

int x；

head=（LinkedList）malloc（sizeof（node））；

head->next=null； /*设置头结点*/

剩余106页未读，继续阅读

bravenss

粉丝: 2
资源: 3

数据结构1800答案解析：绪论与基础题型详解

数据结构1800试题.pdf

数据结构1800试题.pdf 数据结构1800试题.pdf

山东大学数据结构课程试卷(一)及参考答案.pdf

数据结构1800题pdf

2020csp-j入门级第一轮试题及参考答案.pdf

山东大学2019年-数据结构-期末试卷真题.pdf

数据结构试卷及答案pdf下载 西安电子科技大学

数据结构1800题第四版pdf

[数据结构(c语言版)].严蔚敏_吴伟民.高清(带目录)版 第三版.pdf

【职业技能大赛计算机程序设计员赛项】理论试题及参考答案.pdf

最新资源

数据结构试卷及答案pdf下载西安电子科技大学

[数据结构(c语言版)].严蔚敏_吴伟民.高清(带目录)版第三版.pdf