Để tiên hành tìm kiếm một phần tử trong danh sách liên kết đôi sử dụng phương pháp tìm kiếm gì

Có nhiều thao tác trên danh sách liên kết đơn như thêm node, hủy node, tìm kiếm node trong danh sách, sắp xếp danh sách,…

Giả sử, chúng ta tạo một danh sách liên kết đơn lưu trữ một dãy số nguyên như sau:

struct node{ int info; node *next; }; struct sList{ node *head; node *tail; };

Xây dựng hàm createList() để gán các con trỏ head và tail trỏ về NULL.

void createsList(sList &l){ l.head = NULL; l.tail = NULL; }

Xây dựng hàm createNode() có tham số là giá trị của node muốn tạo. Hàm createNode() có kiểu trả về là con trỏ node.

node* createNode(int x){ node *p; p = new node; if(p==NULL){ cout<<"Khong du bo nho!"; exit(1); } p->info = x; p->next = NULL; return p; }

Thêm một node vào đầu danh sách

Trường hợp 1: Nếu danh sách liên kết đơn rỗng thì node mới được xem là node đầu tiên và cũng là node cuối cùng.

Trường hợp 2: Nếu danh sách liên kết đơn không rỗng thì:

- Cho con trỏ liên kết (next) của node mới trỏ vào node đầu tiên trong danh sách hiện tại.
- Cho con trỏ đầu của danh sách liên kết đơn (*head) trỏ vào node mới.

void insertHead(sList &l, int x){ node *p; p = createNode(x); if(p==NULL){ cout<<"Khong tao duoc node!"; exit(1); } if(l.head==NULL){//trường hợp danh sách rỗng l.head = l.tail = p; }else{//trường hợp danh sách không rỗng p->next = l.head; l.head = p; } }

Thêm một node vào cuối danh sách

Trường hợp 1: Nếu danh sách liên kết đơn rỗng thì node mới được xem là node đầu tiên và cũng là node cuối cùng.

Trường hợp 2: Nếu danh sách liên kết đơn không rỗng thì:

- Cho con trỏ liên kết (next) của node cuối danh sách hiện tại trỏ đến đến node mới.
- Cho con trỏ cuối của danh sách liên kết đơn (*tail) trỏ vào node mới.

void insertTail(sList &l, int x){ node *p = createNode(x); if(p==NULL){ cout<<"Khong tao duoc nut moi!"; exit(1); } if (l.head==NULL){//trường hợp danh sách rỗng l.head = l.tail = p ; }else{//trường hợp danh sách không rỗng l.tail->next = p; l.tail = p; } }

Thêm một node p vào sau một node q trong danh sách

Cho con trỏ liên kết (next) của node p chỉ vào node sau của q.

Cho con trỏ liên kết của q chỉ vào node p.

Nếu q là nút cuối thì gán lại p là nút cuối.

void insertAfter(sList &l, node *p, node *q){ p->next = q->next; q->next = p; if (q == l.tail){ l.tail = p; } }

Duyệt toàn bộ danh sách

void processList(sList &l){ node *p; p = l.head; while (p!= NULL){ cout<<p->info<<endl;//xuất giá trị trong node p = p->next; } }

Tìm kiếm node có giá trị k trong danh sách

Hàm searchList() có kiểu trả về là con trỏ node. Nếu tìm thấy x thì node được trả về khác NULL, ngược lại node được trả về là NULL.

node* searchList(sList l, int k){ node *p; p = l.head; while((p!= NULL)&&(p->info != k)){ p = p->next; } return p; }

Hủy toàn bộ danh sách

Sử dụng lệnh delete để giải phóng bộ nhớ lưu trữ các node trong danh sách.

void deleteList(sList &l){ node *p; while (l.head!= NULL){ p = l.head; l.head = p->next; delete p; } l.tail = NULL; }

Có thể sử dụng thuật toán sắp xếp chọn trực tiếp (Selection Sort) để sắp xếp danh sách liên kết đơn.

void List_Selection_Sort(sList &l){ node *min; node *p, *q; p = l.head; while(p != l.tail){ min = p; q = p->next; while(q != NULL){ if(q->info < min->info){ min = q; } q= q->next; } swap(min->info, p->info); p = p->next; } }

Bên dưới là hình minh họa một danh sách liên kết đơn.

Hãy viết chương trình với C++ để thao tác với danh sách liên kết đơn ở trên:

a. Tạo danh sách liên kết đơn như hình minh họa.

b. Thêm một node có giá trị là 9 vào đầu danh sách.

c. Xuất giá trị và địa chỉ của các node trong danh sách lên màn hình.

d. Sắp xếp danh sách theo thứ tự tăng dần các giá trị của các node.

e. Giải phóng bộ nhớ cho toàn bộ danh sách.

Cấu trúc dữ liệu và giải thuật_Mở Hà Nội Phan3

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (357.17 KB, 39 trang )

Bài luyện tập trắc nghiệm 03 - LTTN03
1.Cho đoạn chương trình như sau:
void RemoveHead( DLIST &DQ )
{
DNode*p;
if ( DQ.Head != NULL)
{
p = DQ.Head;
DQ.Head = DQ.Head -> next;
(...1...)
free(p);
if ( DQ.Head == NULL)DQ.Tail = NULL;
}
}
Đoạn lệnh được đưa vào (1) là?
Chọn một câu trả lời:
a. DQ.Head -> pre = NULL;
DQ.Head -> next= NULL;
Câu trả lời không đúng
b. DQ.Head -> next = NULL;
c. DQ.Head -> pre = NULL;
d. Các đáp án đều sai
2.Đoạn mã để tạo ra nút mới có thành phần là x trong danh sách liên kết đôi với mỗi nút gồm
các thành phần (infor, next, pre) sau:
Node* get_node( Data x ){
Node *p;
p = (Node*)malloc(sizeof(Node));
if ( p == NULL )
{
printf(“Ko du bo nho”);

exit(1);
}
p ->infor = x;
p -> …. = NULL;
p -> pre = NULL;
return p;
}
Điền phần còn thiếu vào chỗ ………….
Chọn một câu trả lời:
a. # link
b. data
c. infor
#
d. next
3.Cho Danh sách liên kết đôi chứa danh sách Cán Bộ (CB), Đoạn mã sau đây thực hiện gì?
void InDSCanBo (DList Q)
{
Node *p;
for(p=Q.Tail; p!=NULL; p=p->pre)
{
System.out.print(“%5d”, p->info.mcb);
System.out.print(“%15s”, p->info.hoten);
System.out.print(“%10s”, p->info.ns);
System.out.print(“%7.1f”, p->info.hsl);
System.out.print(“%7.0f”, p->info.pc);
}
}
Chọn một câu trả lời:
a. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q lần lượt từ cuối

danh sách về đầu danh sách Câu trả lời đúng
b. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q lần lượt từ đầu danh
sách về cuối danh sách

c. In đầy đủ thông tin tất cả các cán bộ đang chứa trong danh sách Q
d. In danh sách tên các cán bộ đang có trong danh sách Q lần lượt từ cuối danh sách về đầu
danh sách
4.Cho khai báo CTDL như sau:
struct CB{ int mcb; char hoten[20]; char ns[12]; float hsl,pc;};struct Node{ CB info; struct
Node *next, *pre;};
struct List{ Node *head, *tail;};
Đâu là đoạn mã để in ra màn hình thơng tin đầy đủ của các Cán Bộ có trong danh sách liên
kết lần lượt từ cuối trở về đầu
Chọn một câu trả lời:
a. void InDSCanBo (DList Q)
{
Node *p= Q.Tail;
While( p!=NULL)
{
System.out.print(“%5d”, p->info.mcb);
System.out.print(“%15s”, p->info.hoten);
System.out.print(“%10s”, p->info.ns);
System.out.print(“%7.1f”, p->info.hsl);
System.out.print(“%7.0f”, p->info.pc);
}
}
b. void InDSCanBo (DList Q)
{
Node *p;

for(p=Q.Head; p!=NULL; p=p->next)
{
System.out.print(“%5d”, p->info.mcb);
System.out.print(“%15s”, p->info.hoten);
System.out.print(“%10s”, p->info.ns);
System.out.print(“%7.1f”, p->info.hsl);
System.out.print(“%7.0f”, p->info.pc);
}
}
c. void InDSCanBo (DList Q)
{
Node *p= Q.Head;
While( p!=NULL)
{
System.out.print(“%5d”, p->info.mcb);
System.out.print(“%15s”, p->info.hoten);
System.out.print(“%10s”, p->info.ns);
System.out.print(“%7.1f”, p->info.hsl);
System.out.print(“%7.0f”, p->info.pc);
}
}
d. void InDSCanBo (DList Q)
{
Node *p;
for(p=Q.Tail; p!=NULL; p=p->pre)
{
System.out.print(“%5d”, p->info.mcb);

System.out.print(“%15s”, p->info.hoten);

System.out.print(“%10s”, p->info.ns);
System.out.print(“%7.1f”, p->info.hsl);
System.out.print(“%7.0f”, p->info.pc);
}
}
Câu trả lời đúng
5.Tổ chức của danh sách liên kết kép gồm có mấy thành phần:
Chọn một câu trả lời:
a. 2 thành phần
Câu trả lời không đúng
b. 4 thành phần
c. 3 thành phần
d. 5 thành phần
6.Cho đoạn mã sau, cho biết kết quả của x?
Queue Q; Hàng đợi, ptu vơ trước thì ra trước
InitQueue(Q); khởi tạo hàng rỗng
Put(Q, “Green”); thêm ptu vào hàng đợi
Put(Q, “Red”);
Put(Q, “Yellow”);
Get(Q,x);
Chọn một câu trả lời:
a. Yellow ko chon
b. Tất cả các phương án đều sai Câu trả lời không đúng
c. Red
d. Green
7.Các thao tác được định nghĩa cho ngăn xếp một cách tổng quát
Chọn một câu trả lời:
a. Push
b. Pop
c. Cả hai đáp án đều đúng Câu trả lời đúng

d. Cả hai đáp án đều sai
8.Cho khai báo cấu trúc:
struct NodeQueue
{
int info;
struct NodeQueue *next;

struct NodeQueue *pre;
};
struct Queue
{
NodeQueue *Rear, *Front;
}
Queue Q;
Đoạn mã sau đây thực hiện yêu cầu gì?
void initQueue(Queue &Q)
{
Q.Rear = NULL;
Q.Front = NULL;
}
Chọn một câu trả lời:
a. Khởi tạo hàng đợi rỗng Câu trả lời đúng
b. Khởi tạo danh sách rỗng
c. Khởi tạo mảng rỗng
d. Khởi tạo Stack rỗng
9.Cho đoạn mã sau
stack s; for (int i = 1; i <= 4; i++)
s.push(i);
Phần tử được lấy ra đầu tiên của Stack là gì?

Chọn một câu trả lời:
a. 1
b. 2
c. 4 Câu trả lời đúng
d. 3
10.Cho đoạn mã sau
stack s; for (int i = 1; i <= 5; i++)
s.push(i);
s.pop();

Kết quả các phần tử của Stack sau khi thực hiện các đoạn mã trên là gì?
Chọn một câu trả lời:
a. 2, 3, 4, 5
b. 1, 2, 3, 4 Câu trả lời đúng
c. 1, 3, 5
d. 1, 2, 3
Tham khảo: Tham khảo Tài liệu hướng dẫn học Bài 6 – Ngăn xếp và Hàng đợi, mục I, bản Text
Đoạn mã thực hiện
Lần lượt bổ sung các phần tử 1, 2, 3, 4, 5 vào stack
Sau đó lấy phần tử đầu tiên và hủy khỏi stack
Câu trả lời đúng là:

11.Cho đoạn chương trình như sau:
void AddAfter(DLIST &DQ, DNode *q, DNode *new_element)
{
DNode *p = q -> next;
if (q != NULL)
{
new_element -> next = p;

new_element -> pre = q;
q -> next = new_element;
if (p != NULL)
…[1]…
if (q == DQ.Tail)
DQ.Tail = new_element;
}
else
AddFirst( DQ, new_element);
}
Đoạn lệnh nào được điền vào [1] cho đúng?
Chọn một câu trả lời:
a. p -> pre = new_element;
b. new_element = p -> pre;

c. p -> pre = NULL; Câu trả lời không đúng
d. p -> next = new_element;
12.Cho khai báo cấu trúc dữ liệu như sau:
struct CB{ int mcb; char hoten[20]; char ns[12]; float hsl,pc,tt;};struct Node{ CB info; struct
Node *next, *pre;};
struct List{ Node *head, *tail;};
Đoạn mã sau đây thực hiện yêu cầu gì?
Node *TimCBMa(List Q,char k[]){ Node *p; for(p=Q.Head; p!=NULL; p=p->next) if(strcmp(p>info.hoten,k)==0) break; return p;}
Chọn một câu trả lời:
a. Thực hiện tìm kiếm Cán bộ theo tên cán bộ
b. Thực hiện tìm kiếm trong DSLK đơn chứa các CanBo xem có CanBo nào có mã là k hay
khơng? Trả lại thơng tin nút chứa cán bộ nếu tìm thấy ngược lại trả lại giá trị NULL Câu trả
lời không đúng
c. Thực hiện tìm kiếm trong DSLK đơi có chứa Cán bộ với tên là k nào đó hay khơng?

d. Thực hiện tìm kiếm trong DSLK kép chứa các CanBo xem có CanBo nào có tên là k
hay khơng? Trả lại thơng tin nút chứa cán bộ nếu tìm thấy ngược lại trả lại giá trị
NULL
13.Cho đoạn mã sau:
struct CB{ int mcb; char hoten[20]; char ns[12]; float hsl,pc,tt;};struct Node{ CB info; struct
Node *next, *pre;};
struct List{ Node *head, *tail;};
Khai báo CTDL trên là khai báo CTDL dạng gì?
Chọn một câu trả lời:
a. Danh sách liên kết vịng đơi
b. Danh sách liên kết đơi Câu trả lời đúng
c. Danh sách liên kết đơn
d. Danh sách liên kết vịng
14.Cho đoạn chương trình sau:
void RemoveTail ( DLIST &DQ )
{
DNode *p;
if ( DQ.Tail != NULL)
{
p = DQ.Tail;
..(1)..

free(p);
if ( DQ.Head == NULL) DQ.Tail = NULL;
else DQ.Head ->pre = NULL;
}
}
Chọn một câu trả lời:
a. DQ.Tail = DQ.Tail -> pre;

DQ.Tail -> next = NULL;
b. DQ.Tail = DQ.Tail -> next;
DQ.Tail -> next = NULL;
Câu trả lời không đúng
c. DQ.Tail -> next = NULL;
d. DQ.Head = DQ.Tail -> pre;
DQ.Tail -> next = NULL;
15.Lựa chọn câu đúng nhất về danh sách liên kết đôi.
Chọn một câu trả lời:
a. Vùng liên kết của một phần tử trong danh sách liên kết đơi có 02 mối liên kết với phần tử
trước và sau nó trong danh sách Câu trả lời không đúng
b. Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết với phần tử đầu
và cuối danh sách
c. Vùng liên kết của một phần tử trong danh sách đơi có 02 mối liên kết với 01 phần tử
trong danh sách
d. Vùng liên kết của một phần tử trong danh sách liên đơi có 01 mối liên kết với 02 phần tử
khác trong danh sách
16.Cho các bước mơ tả thuật tốn như sau:
Nếu danh sách rỗng:
DQ.Head = new_element;
DQ.Tail = DQ.Head;
Ngược lại (d/s khác rỗng):
new_element -> next = DQ.Head;
DQ.Head -> pre = new_element;
DQ.Head = new_element;
Đây là mô tả của thuật toán chèn một phần tử vào danh sách liên kết đơi với vị trí chèn là?
Chọn một câu trả lời:
a. Chèn trước phần tử đã biết
b. Chèn sau phần tử đã biết

c. Chèn vào cuối danh sách
d. Chèn vào đầu danh sách Câu trả lời đúng
17Để sắp xếp các phần tử của danh sách liên kết có mấy phương án sử dụng:
Chọn một câu trả lời:
a. 4 phương án
b. 3 phương án
c. 5 phương án
d. 2 phương án

18.Cho khai báo Stack như sau:
struct Stack
{
int top
int nut[max];
};
Đoạn mã thực hiện thao tác gì?
void Push( Stack &s, int x)
{
if ( isFull(s) == 1)
{
printf("Stack day");
exit(1);
}
else
{
s.top = s.top + 1;
s.nut[ s.top ] = x;
}
}

Chọn một câu trả lời:

a. Chèn thêm phần tử mới vào đỉnh của Stack Câu trả lời đúng
b. Thự chiện xoá phần tử đang có ở đỉnh của Stack
c. Thực hiện in lần lượt các phần tử đang có trong Stack
d. Trả lại giá trị phần tử đỉnh của Stack
19.Cho khai báo Stack như sau:
struct Stack
{
int top
int nut[max];
};
Cho biết phần tử được lấy ra cuối cùng trong Stack sau là bảo nhiêu?
int a[] = {4, 5, 6, 7, 8};
int n = 5;
Stack s;
for(int i = 0; i