链表问题(50分)

L

lu_pp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-09

• #1

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，采用（）存储方式最节省运算时间。
A。单链表
B。仅有头指针的单循环链表
C。双链表
D。仅有尾指针的单循环链表

我选择了B，理由是
因为最后一个元素的后面就是第一个元素
要插入的话，可以不需要查询，直接将第一个元素的头指针指向插入元素
插入元素的指针指向最后一个元素
删除雷同
如果是用A，D的话 ，需要向后查询到最后一个元素
至于C，要做两次的连接，慢
不知道我的对不对？

 

G

giiq

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-09

• #2

我不明白你的意思，你说的是不是存储空间最小和运算时间最短的方式？

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-10

• #3

我认为答案应该是D，理由如下：
A:单链表只有头指针，删除第一个元素的时间复杂度为O(1)；但是，要找到最后一个元素并
且在其后插入一个元素，就要遍历整个链表，时间复杂度为O(N)
B:因为是单循环链表，最后一个元素的后继元素是第一个元素，为了删除第一个元素，就必
须定位到最后一个元素，又因为仅有头指针，因此仅定位的时间复杂度就达到了O(N)；同
样的，要在最后一个元素之后插入新元素也要进行同样的定位，时间复杂度也是O(N)
C:毫无疑问，双链表在进行这两种操作的时候，定位以及连接的复杂度均为O(1)，但由于它
的一个元素有两个指针都需要修改，在连接时要比单链表慢
D:与B类似，但是，由于它有尾指针，定位到链表头只要一步，所以采用它的话，定位的时
间复杂度与双链表相同，而连接的时间复杂度与B相同，定位+连接的总复杂度是最低的
——均为O(1)
楼主的分析似乎将头指针和尾指针的功效弄反了。

 

A

aho

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-01-13

• #4

同意楼上的,应该是C

 

D

deniler

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-02-03

• #5

答案应该是D

 

Q

qldx

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-12

• #6

我觉得应该是循环链表，因为单链表遍历必须从头指针开始，而使用循环链表可以从任何一个指针进行遍历。
所以时间用的应该是最少的。

 

K

kusanagi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-18

• #7

循环链表好，不过头尾指针都记录更好。-_-!

 

冰

冰狐狸

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-18

• #8

[!]
D

 

S

sky_zzl

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-25

• #9

D最好，在链表尾插入就在尾指针，在头插入就在尾指针的next。

 

笑

笑天乐

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-31

• #10

我认为是D 对在最后一个元素之后插入一个元素和删除第一个元素最快
既然是尾指针就不用向后查询到尾。

 

L

lps

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-03-31

• #11

D,完全肯定

 

Z

zzcc_1205

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-01

• #12

同意sky_zzl：还是D最好。

 

张

张剑波

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-06-05

• #13

接受答案了.