Which of the following types of list can be implemented so that algorithms for deletion of the element at the beginning and the end of the list are both O(1) time?  (check all that apply)  多项选择题

A

Doubly-linked list

B

Singly linked list

登录即可查看完整答案

我们收录了全球超50000道真实原题与详细解析,现在登录,立即获得答案。

类似问题

(Cont.) Triplicate In the question ofTriplicate (see below), identify the corner cases where the triplicate method may not work correctly.   --------------------------------------------------------- Triplicate Below are the steps to triplicate a linked list node whose data is t. In LinkedList, assume find(t) already works If there’s a node in this list whose data is t, make 2 new nodes whose data is also t, and insert them immediately after the node. If there is no such node, do nothing Fill in the missing pieces in the codes below that implements the method to triplicate a node. void triplicate(T t) { Node<T> n = find(t); if (n == null)   return; Node<T> n1 = new Node<T>( t ); Node<T> n2 = new Node<T>( t ); Node<T> oldNext = ___A___.getNext(); n.setNext(n1); n1.setNext(n2); n2.setNext(___B___); if (n == tail)   tail = ___C___; }

The following declarations are exactly the same as the ones used in the file lists.h that was discussed in class. typedef struct node node_t; struct node { data_t data; node_t *next; }; typedef struct { node_t *head; node_t *foot; } list_t; A student wrote the following function to remove every second item from a list, keeping the first, third, fifth (and so on) original items, and deleting and freeing the second, fourth, sixth (and so on) original items. But four of the student's assignment statements have been lost. list_t *drop_half(list_t *list) { node_t *curr, *fllw; // line A while (curr && curr->next) { list->foot = curr; // line B // line C free(fllw); fllw = NULL; // line D } if (curr) { list->foot = curr; } return list; } Match the line locations on the left with the correct assignment statements on the right. 1: Line A contains: 2: Line B contains: 3: Line C contains: 4: Line D contains:

In a doubly linked list, each node contains:

The following declarations are exactly the same as the ones used in the file lists.h that was discussed in class. typedef struct node node_t; struct node { data_t data; node_t *next; }; typedef struct { node_t *head; node_t *foot; } list_t; A student wrote the following function to walk through lists, swapping each adjacent pair of "even position, odd position" elements so that the first element in each pair switches to the odd position, and the second element in each pair switches to the even position. The first item in the list is counted as being position zero, which is even. None of the data items are moved, and the pairwise swaps are accomplished by pointer assignments. For example, if the original list was 10->16->15->18->17->20->19, the list returned from the function would be linked together in the order 16->10->18->15->20->17->19. In an odd-length list the last item stays in the final position. But four of the student's assignment statements have been lost, marked by four lines with comments and labels. list_t *rearrange(list_t *list) { node_t *prev, *curr, *then, *aftr; // --------------> line A curr = list->head; while (curr && curr->next) { // two more nodes exist then = curr->next; // --------------> line B // now rearrange the pointers if (prev) { prev->next = then; } else { list->head = then; } then->next = curr; curr->next = aftr // then step forwards to the following pair prev = curr; // --------------> line C } if (!curr) { // there was an even number of nodes, so // need to adjust the foot pointer too // --------------> line D } return list; } Match the line locations on the left with the correct assignment statements on the right. 1: Line A contains: 2: Line B contains: 3: Line C contains: 4: Line D contains:

更多留学生实用工具

加入我们，立即解锁 海量真题 与 独家解析，让复习快人一步！