链表选择题，路过的看看你会吗？

主题：链表选择题，路过的看看你会吗？

zjkzxy [专家分：310] 发布于 2006-03-28 17:48:00

5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用(  ) 存储方式最节省运算时间。
   a.单链表   b.双链表   c.单循环链表  d.带头结点的双循环链表
9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则   采用(  )存储方式最节省运算时间
a.单链表b.仅有头指针的单循环链表c. 双链表d仅有尾指针的单循环链表
10．若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用(  )
    存储方式最节省运算时间
    a.单链表  b顺序表  .c双链表 .d循环链表
请教以上3道题，选什么答案，为什么？

本帖地址： http://bbs.pfan.cn/post/151766.html

回复列表（共13个回复）

11 楼

zhoul [专家分：260] 发布于 2006-04-22 09:51:00

[quote]我觉得是
c
b
c
和四楼兄弟一样的
楼上的兄弟
对于第9题
并没有说循环链表一定要带尾指针啊
我觉得是c
因为c有前驱和后继指针来实现查找应该是很方便的[/quote]
我觉得9题是D就像5楼的大哥说的一样，不要把整个链表都走一遍`
正因为不是循环链表一定要带尾指针，所以D说了只有尾指针的单循环链表！

12 楼

xie400057 [专家分：10] 发布于 2007-09-12 11:41:00

我认为正确答案是 B D C
第一道题选B是因为操作的都是最后一个结点，其前驱和后继都可以通过双向链表来获取
时间复杂度都是O(1).不选C的原因很简单，在删除最后一个结点的时候必须找到其前驱结点，其时间复杂度为O(n)，D答案虽然时间复杂度也是O(1)但是没有必要使用循环链表，因为题中没有说明要对头结点或者首结点进行任何操作。
第二道题选D不选B的原因很简单，要删除某一个结点必须找到其前驱结点，而B要得到前驱结点根本必须从头结点搜索到最后才能得到，其时间复杂度为O(n).

13 楼

bpttc [专家分：8790] 发布于 2007-09-13 17:30:00

1. D  删除最后一个元素需要知道倒数第2个元素显然只有循环双链表容易实现

2. D  尾插的话只要知道表尾就行，删除首元需要知道表头或者表尾（对循环表而言），所以尾指针单循环链表最好

3.B  取元素当然是顺序表最好啦，不要背I+1迷惑哦

楼主的题目应该出自李春葆的书，个人认为不应当以做题为主。
题目是考察你对各种链表的理解。多编程，其意自现。

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：链表选择题，路过的看看你会吗？

回复列表（共13个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：链表选择题，路过的看看你会吗？

回复列表 （共13个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共13个回复）