Đáp án đề thi tốt nghiệp cao đẳng nghề khoá II (năm 2008 - 2011) nghề Lập trình máy tính môn thi lý thuyết chuyên môn nghề - Mã đề thi: DA LTMT - LT17

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM<br /> Độc lập – Tự do – Hạnh phúc<br /> ĐÁP ÁN<br /> ĐỀ THI TỐT NGHIỆP CAO ĐẲNG NGHỀ KHOÁ 2 (2008 - 2011)<br /> NGHỀ: LẬP TRÌNH MÁY TÍNH<br /> MÔN THI: LÝ THUYẾT CHUYÊN MÔN NGHỀ<br /> Mã đề số: DA LTMT - LT17<br /> Câu<br /> Nội dung<br /> I. Phần bắt buộc<br /> 1<br /> a. Phương pháp biểu diễn danh sách liên kết kép<br /> <br /> Điểm<br /> <br /> - Danh sách liên kết kép là một cấu trúc dữ liệu bao gồm 1 tập 1,0<br /> hợp các phần tử, trong đó mỗi phần tử là một nút, trong mỗi<br /> nút có chứa hai liên kết tới nút liền trước và liền sau nút đó.<br /> - Cấu trúc 1 nút của danh sách liên kết kép<br /> Lptr<br /> <br /> INFO<br /> <br /> Rptr<br /> <br /> Trong đó:<br /> + INFO: là trường chứa thông tin (dữ liệu) của nút<br /> + Lptr: là con trỏ chứa địa chỉ của nút liền trước (bên<br /> trái) nút này trong danh sách.<br /> + Rptr: là con trỏ chứa địa chỉ của nút liền sau (bên<br /> phải) nút này trong danh sách.<br /> - Danh sách liên kết kép luôn được quản lý bởi hai con trỏ trỏ:<br /> một vào nút cực trái của danh sách và một trỏ vào nút cực<br /> phải của danh sách.<br /> - Một danh sách liên kết kép được biểu diễn tổng quát như<br /> sau:<br /> L<br /> <br /> R<br /> <br /> b. - Thêm một nút có thông tin là X vào trước nút M đang trỏ,<br /> nếu không tồn tại nút M thì chèn vào đầu cực trái<br /> <br /> Trang: 1/5<br /> <br /> void themtruocM(L, R, X, M)<br /> {<br /> // Tạo nút mới<br /> newinfo=X;<br /> if(L==NULL);<br /> {L=R=new; new->rptr=new->lprt=NULL;}<br /> else<br /> {<br /> // Tìm nút M<br /> P=L;<br /> while(p!=M && p!=NULL) p=p->rptr;<br /> if(P!=NULL) // tìm thấy nút M<br /> If(M==L) // M trùng với nút cực trái<br /> {new->rptr = M; M->lptr=new;<br /> new->lptr=NULL; L=new; }<br /> else<br /> { p=M->lptr;<br /> New->rptr=M; M->lptr=new;<br /> p->rptr=new; new->lptr=p;}<br /> else // Không tìm thấy nút M<br /> {new->rptr = M; M->lptr=new;<br /> new->lptr=NULL; L=new; }<br /> }<br /> }<br /> <br /> 1,0<br /> <br /> - Xóa nút thứ k trong danh sách.<br /> void xoa_nut_thu_k(L, R, M)<br /> 1,0<br /> {<br /> // Tìm nút thứ k<br /> if(L== NULL) countlptr=NULL;break;}<br /> case<br /> R==p:<br /> {R=R->lptr;<br /> R>rptr=NULL;break;}<br /> default: {q=p->lptr; M=p->rptr;<br /> q->rptr=M;<br /> M->lptr=q;<br /> break;}<br /> }<br /> free(p);<br /> }<br /> else cout