《数据结构》典型习题与分析.doc

《《数据结构》典型习题与分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》典型习题与分析《数据结构》典型习题与分析一.概论1•通常耍求同一逻辑结构中的所以数据元素具有相同的特性，这意味着()oA)数据元索具有同一特点B)不仅数据元素所包含的数据项的个数耍相同，而且对应数据项的类型耍一致C)每个数据元索都一样D)数据元素所包含的数据项的个数耍相等［分析］同一逻辑结构中的所有数据元素必须具有相同的数据域，而且对应数据项的类型要一致。因为一方而只有同一类型的数据元索才能归类到同一结构中；另一方面，在计算机存储器中表示数据元素时，还必须为它们定义相同的数据类型。故B)答案是正确的。［答案］B)2.下列程序段的时间复杂度是多少？•••for(

2、i=l;i〈二n;i++)•••k++;for(j二1,j〈二n;j++)l+=k;［分析］确切地计算一个算法的时间消耗没有任何实际意义。因为在具体问题中，问题规模n的大小是变化的，而且每台计算机的主频也不相同，所有我们关注的是算法中每条语句的执行次数(频度)。对上述程序段，语句执行的总次数为：n+1+n+n(n+1)+n2=2n2+3n+l注：n后的2为上标令T(n)=2n2+3n+lT(n)就能反映出程序段的时间消耗。当n较大时，T(n)的大小主耍取决于n的数量级。借助数学上极限的概念，如果limT(n)n_>oof(n)二常数，表示当n-*00吋，T(n)和f(n)

3、具有相同的数量级，称T(n)与f(n)同阶。在本例屮，假设f(n)=n2,则有即T(n)与n2同阶。釆用0记法,有T(n)=0(f(n))=0(n2)其中:T(n)就是算法的渐近时间复杂度，简称时间复杂度。而f(n)恰为算法中执行频度最大的那句语句的频度。由此得到求解时间复杂度的方法：找出所有语句中执行频度最大的那条语句的频度，然后取其数量级放入0中即可。［答案］0En2］二.线性表1.带头结点的单链表head为空的判断条件是()。A)head二NULLB)head->next=NULLC)head-〉next二headD)head!=NULL［分析］带头结点的空单链表如

4、图1所示：所以其判断条件可表示为head->next=NULLo如果单链表不带头结点,则其判空条件是head二NULL。［答案］B)2•单链表中，增加头结点的目的是为了()oA)方便运算的实现B)用于标识单链表C)使单链表中至少有一个结点D)用于标识起始结点的位置［分析］对单链表来讲，我们是用头指针来对其进行标识的。头指针可以指向头结点，也可以指向起始结点，所以没有必要用头结点來标识起始结点。而一个单链表允许是空的，不一定非要保证单链表中至少有一个结点，因此B),C),D)答案都是错误的。至所以要引入头结点,目的就是为了方便单链表上运算的实现。［答案］A)3•在一个单链表

5、中，已知q所指结点是P所指结点的直接前趋，若在p,q之间插入s结点，这执行()操作。A)s->next=p->next;p->next=s;B)q->next二s;s-〉next二p;C)p->next=s->next;s->next=p;D)p-〉next二s;s~>next=q;［分析］按题意画草图如图2所示。在本题中，因为相关的三个结点分别被三个指针所指向，所以图中的操作步骤可以对调。［答案⑹。4•在单链表中，删除p所指结点的直接后继的操作是()oA)p->next=p->next~>next;A)p二p-〉next;p->next=p->next->next;B)

6、p-〉next二p->next;C)p二p->next-〉next;［分析］删除P的宜接后继后，p的直接后继的直接后继成为p的新的直接后继，所以应将新的直接后继的地址存入P的指针域中。5.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较()个结点。A)nB)n/2C)(n-l)/2D)(n+l)/2［分析］最好情况下只需比较1次，最坏情况下需比较n次，所以平均次数为(1+2+3+.・・+n)/n=(n+l)/2［答案］D)6.非空的循环单链表head的尾结点(由指针p所指)满足()。A)p-〉next二NULLB)p二NULLC)p-〉next

7、二headD)p二head［分析］不管循环单链表是否带有头结点，其尾结点的指针域一定指向头结点head的目标，所以有p->next=heado［答案］C)7.在循环双链表的p所指结点之后插入s所指结点的操作是()。A)p->next=s;s-〉prior二p;p->next->prior=s;s->next=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-