Select the statement that is most correct. Basically, the complexity of counting the number of items in a doubly-linked list 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 đôi không lưu sẵn số phần tử, nên muốn đếm thì phải bắt đầu từ head và đi theo liên kết next cho tới khi hết, mỗi nút được ghé đúng một lần và tăng biến đếm một lần; với n nút thì chi phí tỉ lệ thuận với n. Hai chiều liên kết giúp đi lùi và xoá nút nhanh, nhưng không cho nhảy nhiều nút một bước nên không rút ngắn phép đếm. "O(n^2)" sai vì không có vòng lặp lồng nào, mỗi nút chỉ ghé một lần. "O(nlogn)" sai vì đó là mức chi phí của các thuật toán chia để trị như sắp xếp trộn, còn đếm chỉ là một lượt đi thẳng. "O(1)" sai trong phạm vi câu hỏi: nó chỉ đúng nếu danh sách giữ thêm một biến size được cập nhật mỗi lần thêm hoặc bớt, khi đó không còn là đếm mà là đọc giá trị đã lưu.
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