Select the statement that is most correct. Basically, the complexity of inserting new element before a given node in the middle of a singly linked lists is
4 phương ánCó giải thích
Các phương án trả lời
Chọn một phương ánLời giảiChọn phương án để mở
Đáp án đúng: "O(n)". Trong danh sách liên kết đơn, mỗi nút chỉ giữ liên kết tới nút sau. Muốn chèn nút mới đứng trước một nút đã cho thì phải sửa liên kết next của nút đứng ngay trước nó, mà từ nút đã cho không có đường đi lùi; cách duy nhất là dò lại từ đầu danh sách cho tới khi gặp nút có next trỏ đúng vào nút đó. Lượt dò ấy có thể đi qua gần hết danh sách nên chi phí tỉ lệ với số nút, tức O(n), còn phần gắn liên kết chỉ là vài phép gán. "O(1)" chỉ đúng với danh sách liên kết đôi, nơi nút đã cho giữ sẵn liên kết prev tới nút trước. "O(log n)" đòi mỗi bước loại bỏ được một nửa dữ liệu như tìm nhị phân, điều không làm được trên danh sách liên kết vì không truy cập ngẫu nhiên tới phần tử giữa. "O(n^2)" ứng với hai vòng lặp lồng nhau, trong khi thao tác này chỉ cần một lượt dò.
Cùng phần 1
Suppose a doubly linked list of integers is given below and p is a reference to the node with value 30 in the list (i.e. p.info=30):
(head) 7 11 6 4 30 9 8 2 (tail)
What does the list look like after the following java code snippet is run?
Node p1,p2; p1 = p.next;
p2 = p1.next;
p.next = p2;
if(p2!=null) p2.prev=p;Có lời giảiCâu hỏiSuppose a doubly linked list of integers is given below and p is a reference to the node with value 13 in the list (i.e. p.info=13):
(head) 7 11 6 4 32 13 8 2 (tail)
What does the list look like after the following java code snippet is run?
int x = 17;
Node q = new Node(x);
q.prev=null;
q.next = head;
head.prev = q;
head = q;Có lời giảiCâu hỏiSelect the statement that is most correct.
Basically, the complexity of getting an element at the middle of a singly linked lists isCó lời giảiCâu hỏiCả 64 câu của chủ đề64 câu
Xuất hiện trong 1 bộ đề
Đi tiếp từ đây