数据结构(C语言版)第一二章习题答案.docx

《数据结构(C语言版)第一二章习题答案.docx》由会员分享，可在线阅读，更多相关《数据结构(C语言版)第一二章习题答案.docx（20页珍藏版）》请在三一文库上搜索。

1、第1章绪论数据结构（C语言版）第一二章习 题答案习题1 .简述下列概念：数据、数据元素、数据项、 数据对象、数据结构、逻辑结构、存储结构、抽 象数据类型。2 .试举一个数据结构的例子，叙述其逻辑结 构和存储结构两方面的含义和相互关系。3 .简述逻辑结构的四种基本关系并画出它们 的关系图。4 .存储结构由哪两种基本的存储方法实现？5 .选择题(1)在数据结构中，从逻辑上可以把数据结 构分成()。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构(2)与数据元素本身的形式、内容、相对位 置、个数无关的是数据的()。A.存储结构B,存储实现D.运算C.逻辑结

2、构实现(3)通常要求同一逻辑结构中的所有数据元 素具有相同的特性，这意味着()。A.数据具有同一特点B.不仅数据元素所包含的数据项的个数 要相同，而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要 相等(4)以下说法正确的是()。A.数据元素是数据的最小单位B,数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D. 一些表面上很不相同的数据可以有相 同的逻辑结构(5)以下与数据的存储结构无关的术语是()。A .顺序队列 B.链表C.有序表D.链栈(6)以下数据结构中，()是非线性数据结构A.树B,字符串C.队D.栈6,试分析下面各程序段的时间复杂度。(

3、1) x=90; y=100;while(y>0)if(x>100) x=x-10;y-;else x+;(2) for (i=0; i<n; i+)for (j=0; j<m; j+) ai0=O；(3) s=0;for i=0; i<n; i+)for(j=0; j<n; j+) s+=Bij;sum=s;(4) i=1;while(i<=n)i=i*3;(5) x=0;for(i=1; i<n; i+)for (j=1; j<=n-i; j+)x+;(6) x=n; /n>1y=0;while(x >(y+1)* (y+1

4、) y+;第2章线性表1 .选择题(1) 一个向量第一个元素的存储地址是100,每个元素的长度为 2,则第5个元素的地址是 ()。A . 110B . 108C. 100D. 120(2)在n个结点的顺序表中，算法的时间复 杂度是0(1)的操作是()。A.访问第i个结点(1wiwn)和求第i 个结点的直接前驱(2wiwn)B .在第i个结点后插入一个新结点(1 < i< n)C.删除第i个结点(1<i<n)D .将n个结点从小到大排序(3)向一个有127个元素的顺序表中插入一 个新元素并保持原来顺序不变，平均要移动3 元素个数为()。A . 8 B . 63.5C .

5、63D. 7(4)链接存储的存储结构所占存储空间()。A.分两部分，一部分存放结点值，另一 部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的 指针D.分两部分，一部分存放结点值，另一 部分存放结点所占单元数(5)线性表若采用链式存储结构时，要求内 存中可用存储单元的地址()。A.必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续或不连续都可以(6)线性表L在()情况下适用于使用链 式结构实现。A.需经常修改L中的结点值B .需不断对L进行删除插入C. L中含有大量的结点D . L中结点结构复杂(7)单链表的存储密度()。A.大于1B.等于

6、1 C .小于1 D.不能确定(8)将两个各有n个元素的有序表归并成一 个有序表，其最少的比较次数是()。A. nB. 2n-1C . 2nD. n-1(9)在一个长度为n的顺序表中，在第i个 元素(1wi&n+1)之前插入一个新元素时须向 后移动()个元素。A . n-iB . n-i+1C. n-i-1 D. i(10)线性表L=(ai, a2,an),下列说法正确的是()。A.每个元素都有一个直接前驱和一个直 接后继B,线性表中至少有一个元素C.表中诸元素的排列必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每 个元素都有一个且仅有一个直接前驱和直接后 继。(11)若指

7、定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是()。A . O(1)B . O(n)C. O(n2)D. O(nlog2n)(12)以下说法错误的是()。A.求表长、定位这两种运算在采用顺序 存储结构时实现的效率不比采用链式存储结构 时实现的效率低B.顺序存储的线性表可以随机存取C.由于顺序存储要求连续的存储区域， 所以在存储管理上不够灵活D.线性表的链式存储结构优于顺序存储 结构(13)在单链表中，要将s所指结点插入到p 所指结点之后，其语句应为()。A. s->next=p+1; p->next=s;B. (*p).next=s; (*s).next=(*p).n

8、ext;C. s->next=p->next; p->next=s->next;D. s->next=p->next; p->next=s;(14)在双向链表存储结构中，删除p所指的 结点时须修改指针()。A . p->next->prior=p->prior;p->prior->next=p->next;B . p->next=p->next->next; p->next->prior=p;C.p->prior->next=p;p->prior=p->prior

9、->prior;D . p->prior=p->next->next; p->next=p->prior->prior;(15)在双向循环链表中，在 p指针所指的 结点后插入q所指向的新结点，其修改指针的操 作是()。A . p->next=q; q->prior=p; p->next->prior=q; q->next=q;B . p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;C .q->prior=p;q-&g

10、t;next=p->next;p->next->prior=q; p->next=q;D .q->prior=p;q->next=p->next;p->next=q; p->next->prior=q;2.算法设计题(1)将两个递增的有序链表合并为一个递增 的有序链表。要求结果链表仍使用原来两个链表 的存储空间，不另外占用其它的存储空间。表中 不允许有重复的数据。void MergeList_L(LinkList &La,LinkList&Lb,LinkList &Lc)pa=La->next; pb=L

11、b->next;Lc=pc=La; /用 La 的头结点作为Lc的头结点while(pa && pb)if(pa->data<pb->data) pc->next=pa;pc=pa;pa=pa->next;elseif(pa->data>pb->data)pc->next=pb; pc=pb; pb=pb->next;else /相等时取La的元素，删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;delete pb ;pb=q;pc->nex

12、t=pa?pa:pb; /插入剩余段delete Lb; /释放 Lb 的头 结点(2)将两个非递减的有序链表合并为一个非 递增的有序链表。要求结果链表仍使用原来两个 链表的存储空间，不另外占用其它的存储空间。 表中允许有重复的数据。void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) pa = La->next; pb = Lb->next;/初始化Lc=pc=La; /用La的头结点作为Lc的头结 点Lc->next = NULL;while ( pa | pb ) if ( !pa ) q

13、= pb; pb =pb->next; else if ( !pb ) q = pa; pa =pa->next; else if (pa->data <= pb->data ) q = pa; pa = pa->next; else q = pb; pb = pb->next; q->next = Lc->next; Lc->next = q;/插入delete Lb; / 释放Lb的头结 点(3)已知两个链表A和B分别表示两个集合， 其元素递增排列。请设计算法求出A与B的交集， 并存放于A链表中。void Mix(LinkList

14、& La, LinkList& Lb, LinkList& Lc, ) pa=la->next;pb=lb- >next; II 设工作 指 针 pa 和 pb;Lc=pc=La; /用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data=pb- >data) II 交集并入结 果表中。 pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u; elseif(pa->data<pb->data)u=pa;pa=p

15、a->next; delete u;else u=pb; pb=pb->next; deleteu;while(pa)u=pa; pa=pa->next;delete u; /释放结点空间while(pb) u=pb; pb=pb->next;delete u; /释放结点空间pc->next=null; /置链表尾标t己。delete Lb; /注： 本算法中也可 对B表不作释放空间的处理(4)已知两个链表A和B分别表示两个集合， 其元素递增排列。请设计算法求出两个集合A和 B的差集(即仅由在A中出现而不在B中出现的 元素所构成的集合)，并以同样的形式存储，同

16、时返回该集合的元素个数。void Difference (LinkedList A , B, *n)/A和B均是带头结点的递增有序的单链表， 分别存储了一个集合，本算法求两集合的差集， 存储于单链表A中，*n是结果集合中元素个数， 调用时为0p=A->next ;/ p 和 q 分另ll是链表A和B的工作指针。/ pre为A中q=B->next ; pre=A ； p所指结点的前驱结点的指针 while (p!=null && q!=nullif (p->data<q->data ) pre=p ; p=p->next ;*n+; II A链

17、表中当前结点指针后移。else if ( p->data>q->data ) q=q->next ;/ B链表中当前结点指针后移。else pre->next=p->next ;II 处理A, B中元素值相同的结点，应删除。u=p ; p=p->next ; delete u; II删除结点(5)设计算法将一个带头结点的单链表 A分 解为两个具有相同结构的链表 B、C,其中B表 的结点为A表中值小于零的结点，而C表的结点 为A表中值大于零的结点(链表A的元素类型为 整型，要求B、C表利用A表的结点)。(6)设计一个算法，通过一趟遍历在单链表 中确定值最

18、大的结点。ElemType Max (LinkList L ) if(L->next=NULL) return NULL; pmax=L->next; 假定第一个结点中数据 具有最大值p=L->next->next;while(p != NULL)/如果下一个结点存在if(p->data > pmax->data) pmax=p; p=p->next;return pmax->data;(7)设计一个算法，通过遍历一趟，将链表 中所有结点的链接方向逆转，仍利用原表的存储 空间。void inverse(LinkList &L) /逆

19、置带头结点的单链表Lp=L->next; L->next=NULL;while ( p) q=p->next; / q指向*p的后继p->next=L->next;L->next=p; / *p插入在头结点之后p = q;(8)设计一个算法，删除递增有序链表中值 大于 mink且/、于 maxk的所有元素(mink和 maxk 是给定的两个参数，其值可以和表中的元素相同)也可以不同)。void delete(LinkList &L, int mink, int maxk) p=L->next; /首元结点while (p &&

20、p->data<=mink) pre=p; p=p->next; /查找第一个值>mink的结点if (P) while (p && p->data<maxk) p=p->next;/查找第一个值> maxk的结点q=pre->next;pre->next=p; /修改指针while (q!=p) s=q->next; delete q; q=s; /释放结点空间/if(9)已知p指向双向循环链表中的一个结点， 其结点结构为data、prior、next三个域，写出 算法change(p),交换p所指向的结点和它

21、的前缀结点的顺序。知道双向循环链表中的一个结点，与前驱交 换涉及到四个结点(p结点，前驱结点，前驱的 前驱结点，后继结点)六条链。void Exchange (LinkedList p )/ p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。q=p->llink ;q->llink->rlink=p ; II p 的前驱的前驱之后继为pp->llink=q->llink;II p 的前驱指向其前驱的前驱。q->rlink=p->rlink;II p 的前驱的后继为p的后继。q->llink=p ;II p与其前驱交换p->r

22、link->llink=q ; II p 的后继的前驱 指向原p的前驱p->rlink=q ;II p的后继指向其原来的前驱 /算法exchange结束。(10)已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为 O(n)、空间复杂度 为0(1)的算法，该算法删除线性表中所有值为item的数据元素。题目分析在顺序存储的线性表上删除元 素，通常要涉及到一系列元素的移动 (删第i个 元素，第i+1至第n个元素要依次前移)。本题 要求删除线性表中所有值为item的数据元素， 并未要求元素间的相对位置不变。因此可以考虑 设头尾两个指针(i=1 , j=n ),从两端向中间移 动，凡

23、遇到值item的数据元素时，直接将右端 元素左移至值为item的数据元素位置。void Delete (ElemType A )int n )/ A是有n个元素的一维数组，本算法删除A中所有值为item的元素。i=1 ; j=n ; /设置数组低、高端指针(下标)while (i<j )while ( i<j && Ai!=item ) i+ ;/若值不为item,左移指针。if (i<j ) while (i<j && Aj=item ) j- ; II若右端元素值为item)指针左移if (i<j ) Ai+=Aj-;算法讨论因元素只扫描一趟，算法时间复 杂度为O (n)。删除元素未使用其它辅助空间, 最后线性表中的元素个数是jo(1) O (1)(2) O (m*n)(3) O (n1 2 3 4 * 6)(4) O (log3n )(5)因为 x+共执行了 n-1+n-2+1 =n(n-1)/2,所以执行时间为O (n2)(6) O( n)