数据结构习题集(答案).doc

《数据结构习题集(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构习题第一章绪论1.1数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_和运算等的学科。①A.数据元素B.计算方法C.逻辑存储D.数据映像②A.结构B.关系C.运算D.算法1.2算法分析的目的是___①__，算法分析的两个主要方面是__②___。①A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求该进D.分析算法的易懂性和文档性②A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性1.3计算机算法指的是__①

2、__，它必须具备输入、输出和__②_等5个重要特性。①A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法②A.可读性、可移植性和可扩展性B.可读性、可移植性和有穷性C.确定性、有穷性和可行性D.易读性、稳定性和安全性1.4数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。1.5数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。数据的逻辑结构是指_数据元素之间

3、的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。1.6线性结构中元素之间存在_一对一___关系，树形结构中元素之间存在_一对多___关系，图状结构中元素之间存在__多对多__关系。1.7数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。1.8顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。第二章线性表2.1链表不具备的特点是___

4、_。A.可随机访问任一结点B.插入删除不需移动元素C.不必事先估计存储空间D.所需空间与其长度成正比2.2不带头结点的单链表head为空的判定条件是____。A.head==nullB.head->next==nullC.head->next==headD.head!=null2.3带头结点的单链表head为空的判定条件是____。A.head==nullB.head->next==nullC.head->next==headD.head!=null2.4非空的循环单链表head的尾结点（由p所指向）满足____

5、。A.p->next==nullB.p==nullC.p->next==headD.p==head2.5在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)2.6线性链表中各个结点之间的地址不一定连续。2.7线性表中数据元素之间具有__一对一__，除第一个和最后一个元素外，其他数据元素有且只有_一个10后继和前趋。2.8若频繁地对线性表进行插入和删除操作，该线性表采用链式存储结构比较合适。2.9在一个单链表中p所指结点之后

6、插入一个s所指结点时，应执行s->next=_p->next_和p->next=_s_的操作。2.10已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=__LOC(a1)+（i-1）*k_。2.12若线性表采用顺序存储结构，每个数据元素占用3个存储单元，第11个数据元素的存储地址为130，则第1个数据元素的存储地址是100。2.12若线性表采用顺序存储结构，线性表的最大长度为1000，每个数据元素占3个存储单元，则要分配给该线性表_3000

7、__存储单元，若第一个数据元素的存储地址是2000，则第11个元素的存储地址是__2030__。2.13以head为头结点循环双链表为空时，应满足head->llink=head，head->rlink=head。2.14在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是。A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;2.15在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s

8、指的结点，则需执行________。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s->next;s->next=pD.p->next=s;s->next=q2.16用链表表示线性表的优点是（）A．便于随机存储B.便于进行插入和删除操作C.占用的存储空间较顺序表少D.元素的物理顺序与逻辑顺序相同2.17