数据结构第2章典型例题解析

《数据结构第2章典型例题解析》由会员分享，可在线阅读，更多相关《数据结构第2章典型例题解析（9页珍藏版）》请在装配图网上搜索。

1、第 2 章 线 性 表典型例题解析一、选择题1线性表是具有n个（n0） 的有限序列。A. 表元素B.字符C.数据元素D.数据项【分析】线性表是具有相同数据类型的n （n0）个数据元素的有限序列，通常记为 （。卫2,an）,其中n为表长，n=0时称为空表。【答案】 C2 .顺序存储结构的优点。A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素 的逻辑顺序和物理次序一致。因此，其存储密度大。【答案】 A3带头结点的单链表head为空的判断条件 。A. head=NULLB. head-ne

2、xt=NULLC. head-next=headD. head!=NULL【分析】链表为空时，头结点的指针域为空。【答案】 B4. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最 后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素 才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第 一个元素和最后一个元素，但存储效率要低些，插入和删

3、除操作也略微复杂；选项D可通过 尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便 地找到第一个元素。【答案】 D5. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 算。因此不需要移动线性表种元素的位置。根据题意要求，该线性表的存储应能够很方便地 找到线性表的任一指定序号的元素和最后一个元素，顺序表是由地址连续的向量实现的，因 此具有按序号随机访问的特点。链表需要通过指针才能找

4、到线性表的莫以指定序号的元素， 需要一定的时间开销。【答案】A6. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选 最节省 时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的最后一个元素和 最后一个元素的前驱元素， A 和 B 都不能很方便地通过头指针找到线性表的第一个元素；选 项 C 可以方便地找到最后一个元素，单不能很快地找到其前驱元素；选项 D 为双向循环链表， 可以很方便地找到线性表的最后一个元素，通过其前驱指针，从而可以方便地找到其前驱元 素。【答案】 D7. 静态链表中指针表示的 。

5、A.内存地址B.数组下标 C.下一元素地址D.左、右孩子地址【分析】静态链表采用的是链式方式存储线性表，以数组方式存储链表的数据，指针域 存储的是该结点逻辑上的后继结点的相对地址(即在数组中的下标)，也称为静态指针。【答案】 B8链表不具有的特点。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据 元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要和存放 其后继元素所在的存储单元的地址。链表不具有按序号随机访问第j个元素的特点，必须通 过标识链

6、表的头指针(或尾指针)“顺藤摸瓜”才能找到第/个结点。【答案】 B9线性表的静态链表存储结构与顺序存储结构相比优点。A.所有的操作算法简单B.便于插入和删除C.便于利用零散的存储器空间D.便于随机存取【分析】静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。【答案】 B10.若长度为 n 的线性表采用顺序存储结构，在其第/ 个位置插入一个新元素算法的时 间复杂度为。A. O(log2n)B. O(1)C. O(n)D. O(n2)【分析】在第 / 个位置上插入新元素需要从最后一个元素开始后移直到第/ 个元素后移为 止，后移元素的次数为n-i+1,即时间复杂度为0(n)。【答案】C1

7、1 .线性表(a1,a2,an)以链接方式存储时，访问第i个位置元素的时间复杂性 为。AO(i)BO(1)CO(n)DO(i-1)【分析】线性表以链接方式存储时，访问第/个位置元素从第一个元素开始移动指针到第 /个元素，移动指针的次数为n-i+1,即时间复杂度为0(n)。【答案】 C12. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数 。AnB2n-1C2nDn-1【分析】当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需n次。【答案】 A13. 非空的循环单链表head的尾结点p满足。A. p-next=headB. p-next=NULL C. p=NULLD.

8、 p=head【分析】非空的循环单链表head的尾结点的后继指针指向链表的头结点。【答案】 A14. 在双循环链表p所指结点之后插入s所指结点的操作 。A. p-next=s; s-prior=p; p-next-prior=s; s-prior=p-next;B. p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C. s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;D. s-prior=p; s-next=p-next; p-next-prior=s; p-next=s;【分析】由于要

9、将s所指结点插入到p所指结点之后，p结点为s结点的前驱，s结点为p 结点的新后继，而结点p的原后继结点为结点s的后继结点，结点s为结点p的原后继结点 的前驱结点s。在选项A、B和C中均是先执行操作p-next=s,就是修改了结点p的后继结 点s，然后再执行操作p-next-prior=s,因此，无法使得结点s为结点p的原后继结点的前 驱结点，这样的赋值会使s结点为其自身的前驱。应先执行操作p-next-prior=s,再执行操 作 p-next=s。【答案】 D15. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q结点和p结点之间插入s结点，则执行。A. s-next=p-nex

10、t;p-next=s;B. p-next=s-next;s-next=p;C. q-next=s; s-next=p;D. p-next=s; s-next=q;【分析】由于是将s所指结点插入到q和p所指结点之间，即使其为q所指结点的后继结 点,为p所指结点的前驱结点，因此s-next的取值应为p，p-next的取值无需改动，q-next 的取值应改为s,故A、B和D均是错误的。【答案】 C二、判断题1. 线性表的特点是每个元素都有一个前驱和一个后继。分析】线性表是一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关 系。线性表中除第一个数据元素和最后一个数据元素外，外每个元素都有一个

11、前驱和一个后 继。【答案】错误 2顺序存储的线性表可以按序号随机存取。【分析】因为顺序表在内存是用地址连续的空间存储的，设的存储地址为Loc(aJ,每 个数据元素占d个存储地址，则第/个数据元素的地址为：Loc(a；.)=Loc(a 1)+(/-1)xd1w/prior=p-prior;p-prior=s;s-next=p;解答】只能是“s-prio-next=s”而不能为“p-prio-rnext=s”;。图2-11 第1题图因为在上面的第二条语句中已经改变了结点p的前驱结点，结点p的前驱结点已经为S 结点，而不是操作前的前驱结点。在下面的语句顺序下，可有两个答案进行选择。s-prior=p

12、-prior;p-prior=s;s-next=p;读者做这种题时，最好予以图示，不易出错。2.已知线性表非递减有序，存储于一个一维数组A0.n-1中(表长为n，设为全局量), 下面算法的功能是什么？void del(DataType A)int i,j;i=1;while (i=n-1)if (Ai!=Ai+1)i+;elsefor (j=(i+2);jnext)q=L;L=L-next;p=L;while (p-next)p=p-next;p-next=Q;q-next=NULL;return L;【解答】算法的功能是把单链表的第一个结点从表头移到了链尾。返回的L指向原链表的 第二个结点。

13、若原链表表示的线性表是心an),则操作后表示的线性表为(a2,a3,an,aj。4试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。【解答】头指针是一个指针变量,里面存放的是链表中首结点的地址,并以此来标识一 个链表。如链表H,链表L等，表示链表中第一个结点的地址存放在H和L中。头结点是附加在第一个元素结点之前的一个结点,头指针指向头结点。当该链表表示一 个非空的线性表时,头结点的指针域指向第一个元素结点,为空表时,该指针域为空。开始结点指第一个元素结点。头指针的作用是用来唯一标识一个单链表。头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链表的第 一个位置

14、上的操作和在其他位置上的操作一致,无需特殊处理。5.在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，而不知道头指针， 能否将结点 p 从相应的链表中删除？若可以,其时间复杂度各为多少？【解答】单链表：若结点p有后继结点，则可将结点p的后继元素数据放入结点p中，再将后继 结点删除。时间复杂度为0(1);若结点p无后继结点，则不可以实现。双链表：可以实现，时间复杂度为0(1)。单循环链表：像单链表那样进行操作，也可以从p开始，找结点p的直接前驱，然后再 删除p结点，时间复杂度为0(n)o四、算法设计题1.设线性表存放在一维数组Aarrsize啲前num个分量中，且递增有序。试写一算法，

15、将 x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。【分析】直接用题目中所给定的数据结构(顺序存储的思想是用物理上的相邻表示逻辑 上的相邻，不一定要将一维数组和表示线性表长度的变量封装成一个结构体)，因为是顺序存 储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性 表中元素的有序性确定插入元素的插入位置，后面的元素为它让出位置(也可以从高下标端 开始一边比较，一边移位)，然后插入X,最后修改表示表长的变量。【算法】InsertSeq(DataType A,int *num,DataType x)/设 num 为表的最大下标int i;

16、if (*num=arrsize-1)return 0;elsei=*num;while (i=0&Aix)/边找位置边移动Ai+1=Ai;i-;Ai+1=x;/找到的位置是插入位的下一位(*num)+;return 1;时间复杂度为o(n)。2. 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结 点的指针，试编写算法删除结点s的直接前驱结点。【分析】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q, 然后可删除结点p。【算法】viod delepre(LNode *s)LNode *p,*q;p=s;while (p-next=s)q=p;p=

17、p-next;q-next=s;delete p;3已知两个单链表A与B分别表示两个集合，其元素递增排列，编写一个函数求出人 和B的交集C,要求C同样以元素值递增的单链表形式存储。【分析】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链 表C带有一个头结点，最后将其删除掉。算法中指针用来指向A中的当前结点，指针q用 来指向 B 中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。 【算法】LinkNode *inter(LinkList A,B)LNode *q,*p,*r,*s,*C;C=new LNode;r=C;

18、p=A;q=B;while (p & q )if (p-datadata) p=p-next;else if (p-data=q-data) s=new LNode; s-data=p-data; r-next=s; r=s; p=p-next; q=q-next; else q=q-next;r-next=NULL;r=C-next;delete C; return r;4.单链表L是一个递减有序表，试编写一个高效算法，删除表中值大于min且小于max 的结点(若表中有这样的结点)同时释放被删结点的空间，这里min和max是两个给定的 参数。并分析算法的时间复杂度。【分析】由于单链表L是一个

19、递减有序表，即由大到小有序，故可从表头开始查找第一个 比max小的结点，记住其位置，再接着向后查找第一个不大于min的结点，然后将它们之间 的结点删除。【算法】LinkList delete(LinkList L,int min,int max)/设 L 为带头结点的循环链表LNode *p,*q,*s,*k;if(L-next)p=L-next;s=L;while (p-data=max)s=p; p=p-next;/p指向第一个值小于max的结点s指向其前驱while (p!=L & p-datamin) /p 继续下移p=p-next;/p指向第一个值不大于min的结点while (s-

20、next!=p)删除*s的后继至* p的前驱之间的结点k=s-next;s-next=k-next; delete k; 前两个while循环和起来最多循环n次，第三个while循环最多循环n次，即删除n个 结点，故算法的时间复杂度为 O(n)。5、编写一个算法，将一个头结点指针为a的单链表A分解为两个单链表A和B,其头 结点指针分别为a和S使得人链表中含有原链表A中序号为奇数的元素(头结点紧接的下 一个元素为第1个元素)，而B链表中含有原链表A中序号为偶数的元素，且保持原来的相 对顺序。【分析】此题用一个while循环来处理，一次循环处理两个结点：将前一个仍留在a中， 后一个从a中删除，链接

21、到b的尾部，直到整个链表处理完毕。【算法】Int split(LNode *a,LNode *b)/若成功分解，返回1，否则，返回0a为指向单链表a的指针，b为指向单链表B的指针LNode *cur_a,cur_b,temp; cur_a=a-next; cur_b=Init_List();if(cur_b=NULL)Return 0;*b=cur_b; while(cur_a!=NULL&(temp=cur_a?next)!=NULL) cur_a?next=temp?next; cur_a=cur_a?next; cur_b?next=temp;cur_b=cur_b?next;cur_b?next=NULL;return 1;