数据结构1-4章复习题答案

《数据结构1-4章复习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、选择题。1.算法的计算量的大小称为计算的（b）。A．效率B.复杂性C.现实性D.难度2.计算机算法指的是（1c），它必须具备（2b）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性3.下面关于算法说法错误的是（d）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的4.下面说

2、法错误的是（c）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)5．从逻辑上可以把数据结构分为（c）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构6．程序段For(i=n-1;i>0;i--)For(j=1;

3、j<=i;j++)If(a[j]>a[j+1])a[j]←→a[j+1]其中n为正整数，则最后一行的语句时间复杂度在最坏情况下是（d）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)7．下述哪一条是顺序存储结构的优点？（a）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示8．下面关于线性表的叙述中，错误的是哪一个？（b）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单

4、元。D．线性表采用链接存储，便于插入和删除操作。9．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（a）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表11.链表不具有的特点是（b）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比12.单链表的一个存储结点包含（　　d　　）A数据域或指针域B指针域或链域C指针域和链域D数据域和链域14.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（

5、c）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)15.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为(d)A.p=rear;B.rear=rear->next;rear=rear->next;free(rear);free(p)C.rear=rear->next->next;D.p=rear->next->next;free(rear);rear->next->next=p->next;free(p);16．带头结点的单链表Head为空的判定条

6、件是bA.Head==NullB.Head->next==NULLC.Head->next==Head6D．Head->data==NULL17.非空的单循环链表L的尾结点*P,满足cA.P->next==NULLB.P==NULLC.P->next==LD.P==L.18.双向链表结点结构如下：LLinkdataRLink其中：LLink是指向前驱结点的指针域：data是存放数据元素的数据域；Rlink是指向后继结点的指针域。下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链

7、表中。不能正确完成要求的算法段是cA.Q->LLink=P->LLink;B.P->LLink=Q;Q->Rlink=P;Q->Rlink=P;P->LLink=Q;P->LLink->Rlink=Q;P->LLink->Rlink=Q;Q->LLink=P->LLink;C.Q->LLink=P->LLink;Q->Rlink=P;P->LLink->Rlink=Q;P->LLink=Q;D.Q->LLink=P.->LLink;Q->Rlink=P;P->Llink=Q;Q->Llink->Rlink=Q;1

8、9.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着cA.每个结点所代表的数据元素都一样。B.每个结点所代表的数据元素包含的数据项的个数要相等C.不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致D.结点所代表的数据元素有同一特点1.对于栈操作数据的原则是（b）。A.先进先出B.后进先出C.后进后出