Select the statement that is most correct. Basically, the complexity of getting an element at 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)". Danh sách liên kết đơn chỉ cho phép đi từ một nút sang nút kế tiếp qua con trỏ next, không có phép tính địa chỉ như mảng, nên muốn tới phần tử ở giữa phải xuất phát từ head và nhảy khoảng n/2 lần; chi phí n/2 bước tỉ lệ thuận với n, tức O(n). Phương án "O(1)" chỉ đúng với mảng hoặc cấu trúc có truy cập ngẫu nhiên, vì ở đó địa chỉ phần tử thứ i tính được bằng một phép nhân và một phép cộng; danh sách liên kết không lưu gì cho phép tính như vậy. Phương án "O(log n)" là chi phí của tìm nhị phân hay của việc đi trên cây cân bằng, cả hai đòi hỏi nhảy thẳng vào giữa đoạn trong một bước, điều mà con trỏ next không làm được, và cũng chính vì thế không thể tìm nhị phân trên danh sách liên kết. Phương án "O(n^2)" cao hơn hẳn thực tế: ta chỉ đi một lượt qua nửa danh sách, không có vòng lặp nào lồng trong vòng lặp.
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ỏiSelect the statement that is most correct.
Suppose we are considering a singly linked list which has at least 2 nodes. What does the java code snippet below do?
Node f = head;
while(f.next != tail) f = f.next;
f.next = null;
tail = f;Có lời giảiCâu hỏiSuppose a singly linked list of integers is given below and p is a reference to the node with value 3 in the list (i.e. p.info=3):
(head) 7 11 6 14 3 9 8 12 (tail)
What does the list look like after the following java code snippet is run?
int x = 5;
Node f = head;
while(f.next != p) f = f.next;
Node q = new Node(x);
q.next = p;
f.next = q;Có 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