Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 2: Kiểu dữ liệu ngăn xếp

Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 12 - Khoa học máy tính bộ sách Cánh diều Bài 2: Kiểu dữ liệu ngăn xếp. Bộ giáo án giúp giáo viên hướng dẫn học sinh mở rộng kiến thức, phát triển năng lực, nâng cao khả năng định hướng nghề nghiệp cho các em sau này. Thao tác tải về rất đơn giản, tài liệu file word có thể chỉnh sửa dễ dàng. Mời quý thầy cô tham khảo bài soạn.

Xem: => Giáo án Tin học 12 - Định hướng khoa học máy tính cánh diều

Xem toàn bộ: Giáo án chuyên đề Khoa học máy tính 12 cánh diều đủ cả năm

Ngày soạn:…/…/…

Ngày dạy:…/…/…

 

BÀI 2: KIỂU DỮ LIỆU NGĂN XẾP

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

  • Biết được kiểu dữ liệu ngăn xếp là kiểu dữ liệu tuyến tính.

  • Mô tả được khái niệm ngăn xếp và cơ chế hoạt động của nó.

  • Biểu diễn được ngăn xếp bằng mảng một chiều và viết được chương trình con thực hiện các phép toán cơ bản trên ngăn xếp.

  • Nêu được một số ứng dụng của ngăn xếp.

2. Năng lực

Năng lực chung:

  • Tự chủ và tự học: Chủ động, tích cực thực hiện công việc của cá nhân.

  • Giao tiếp và hợp tác: Phân tích được các công việc cần thực hiện để hoàn thành nhiệm vụ của nhóm trong các hoạt động nhóm.

  • Giải quyết vấn đề và sáng tạo: Nêu được nhiều ý tưởng mới trong học tập, suy nghĩ không theo lối mòn, tạo ra yếu tố mới dựa trên những ý tưởng khác nhau.

Năng lực Tin học:

  • Biểu diễn được kiểu dữ liệu ngăn xếp bằng list trong Python.

  • Giải thích và viết được các chương trình con có sử dụng các hàm cơ bản của kiểu dữ liệu ngăn xếp.

3. Phẩm chất

  • Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.

  • Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.

  • Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU:

1. Đối với giáo viên:

  • Máy chiếu, máy tính, màn hình hiển thị, hoặc ti vi.

  • Phòng thực hành, các máy tính có kết nối internet

  • SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

2. Đối với học sinh:

  • Các dụng cụ học tập theo yêu cầu của GV; SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: Xuất phát từ tình huống được mô tả ở hoạt động Khởi động SGK tr.12, khơi gợi và tạo hứng thú để HS muốn tìm hiểu về ngăn xếp.

b. Nội dung: GV yêu cầu HS làm việc cá nhân, suy nghĩ trả lời câu hỏi ở hoạt động Khởi động SGK tr.10. 

c. Sản phẩm học tập: Quy tắc thực hiện thao tác thêm vào và lấy ra khỏi ngăn xếp.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

GV tổ chức cho HS đọc kênh chữ, quan sát kênh hình của hoạt động Khởi động, suy nghĩ và trả lời câu hỏi:

Lan xếp các đĩa CD thành một cọc (Hình 1). Mỗi lần lấy đĩa ra khỏi cọc, Lan sẽ lấy lần lượt từng đĩa một từ trên xuống. Mỗi lần bổ sung, Lan cũng lần lượt xếp từng đĩa mới vào cọc.

Em hãy:

a) Cho biết với đĩa nằm ở đáy và đĩa nằm ở đỉnh cọc, đĩa nào được thêm vào cọc trước.

b) So sánh quy tắc thực hiện thao tác thêm vào và lấy đĩa ra khỏi cọc với thao tác thêm vào và lấy ra phần tử khỏi hàng đợi đã được học ở bài trước. 

Hình 1. Ví dụ một cọc đĩa CD

Bước 2: HS thực hiện nhiệm vụ học tập

- HS đọc kênh chữ, quan sát kênh hình, suy nghĩ để hoàn thành nhiệm vụ học tập.

- GV quan sát, theo dõi và hỗ trợ HS khi cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời một số HS xung phong trình bày câu trả lời.

HS khác lắng nghe, nhận xét và bổ sung.

Gợi ý trả lời:

a) Đĩa nằm ở đáy được thêm vào cọc trước.

b) So sánh:

+ Thao tác thêm vào và lấy đĩa ra khỏi cọc:

  • Thêm vào: Thêm đĩa vào đỉnh của cọc.

  • Lấy ra: Lấy đĩa ra khỏi đỉnh của cọc.

+ Thao tác thêm vào và lấy ra phần tử khỏi hàng đợi:

  • Thêm vào (enqueue): Thêm phần tử vào cuối hàng đợi.

  • Lấy ra (dequeue): Lấy ra khỏi hàng đợi phần tử đang đứng đầu hàng đợi.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Hôm nay chúng ta sẽ tiếp tục tìm hiểu một khái niệm quan trọng trong lập trình - đó là “ngăn xếp”. Hãy cùng tìm hiểu cách mà kiểu dữ liệu này giúp chúng ta quản lý và xử lý các yêu cầu một cách hiệu quả, thông qua việc áp dụng nguyên tắc “Last In, First Out”. Vậy để giúp các em hiểu về cách thức hoạt động của hệ thống ngăn xếp và biểu diễn được ngăn xếp bằng mảng một chiều trong Python, chúng ta sẽ cùng nhau đến với Bài 2: Kiểu dữ liệu ngăn xếp.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Một số ví dụ về ngăn xếp và cơ chế hoạt động

a. Mục tiêu: 

- HS mô tả được khái niệm ngăn xếp, cơ chế hoạt động của ngăn xếp.

- HS nêu được một số ứng dụng của ngăn xếp.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Một số ví dụ về ngăn xếp và cơ chế hoạt động để thực hiện nhiệm vụ.

c. Sản phẩm: Khái niệm, cơ chế hoạt động và một số ví dụ của ngăn xếp.

d. Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS làm việc độc lập và trả lời các câu hỏi:

+ Em hãy quan sát Hình 1 và cho biết vị trí của đĩa đầu tiên và đĩa cuối cùng được thêm vào cọc.

+ Thao tác thêm đĩa vào và lấy đĩa ra khỏi cọc được thực hiện tại vị trí nào của cọc?

+ Theo em, đĩa CD ở vị trí nào sẽ được lấy ra khỏi cọc trước tiên?

- Từ đó, GV giới thiệu về cơ chế LIFO và kiểu dữ liệu ngăn xếp.

- GV tiếp tục đặt câu hỏi:

+ Em hãy nêu một số ví dụ về ngăn xếp trong cuộc sống hằng ngày.

- GV giới thiệu và phân tích cho HS một số ứng dụng của ngăn xếp trong tin học.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 1 SGK tr.12 – 13 và trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS lần lượt trả lời các câu hỏi.

- HS khác nhận xét, bổ sung. 

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chuyển sang nội dung tiếp theo.

1. Một số ví dụ về ngăn xếp và cơ chế hoạt động

Hình 1. Ví dụ một cọc đĩa CD

- Hình 1 mô tả một cọc gồm rất nhiều đĩa CD được xếp theo thứ tự từ dưới lên trên: 

+ Đĩa đầu tiên được thêm vào cọc sẽ nằm ở đáy, đĩa được thêm vào sau cùng sẽ nằm ở đỉnh của cọc. 

+ Thao tác thêm đĩa vào và lấy đĩa ra khỏi cọc chỉ được phép thực hiện tại vị trí đỉnh của cọc. 

Đĩa CD nào được xếp vào cọc sau cùng thì sẽ được lấy ra khỏi cọc trước tiên. Trong tin học, người ta gọi quy tắc này là vào sau ra trước hay LIFO (Last In First Out) và xây dựng kiểu dữ liệu ngăn xếp (Stack) để mô phỏng cơ chế hoạt động LIFO.

Một số ví dụ về ngăn xếp diễn trong cuộc sống hằng ngày:

+ Cọc đĩa CD (Hình 1).

+ Đồ chơi tháp gỗ 7 sắc cầu vồng.

+ Chồng ghế.

+ Quần áo được xếp thành chồng trong tủ.

Hình 2. Một số ví dụ về ngăn xếp 
trong thực tế

Ứng dụng của ngăn xếp trong tin học: 

Tính năng quay lại trang vừa truy cập ngay trước trong các trình duyệt web: 

  • Ngăn xếp được sử dụng để lưu trữ các đường dẫn liên kết (URL) của các trang web mà người dùng đã và đang truy cập. 

  • Mỗi khi người dùng vào một trang web mới, đường dẫn liên kết của trang này sẽ được bổ sung vào ngăn xếp. 

  • Khi người dùng bấm nút quay lại trang trước, đường dẫn ở đỉnh ngăn xếp sẽ được loại bỏ khỏi ngăn xếp và lúc này trang web tương ứng với đường dẫn ngay trước đó (đang ở đỉnh ngăn xếp) sẽ được hiển thị lên màn hình người dùng.

+ Tác vụ hoàn tác/làm lại: Chức năng Undo khi soạn thảo văn bản.

+ Giải quyết một số bài toán như tính giá trị của biểu thức số học, kiểm tra dấu ngoặc.

+ Theo dõi quá trình thực hiện của thuật toán quay lui, khử đệ quy,…

Hoạt động 2. Kiểu dữ liệu ngăn xếp và các phép toán cơ bản trên ngăn xếp

a. Mục tiêu: HS biết được kiểu dữ liệu ngăn xếp là kiểu dữ liệu tuyến tính và các phép toán cơ bản trên ngăn xếp.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2. Kiểu dữ liệu ngăn xếp và các phép toán cơ bản trên ngăn xếp, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Kiểu dữ liệu ngăn xếp và các phép toán cơ bản trên ngăn xếp. 

d. Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS thảo luận theo nhóm 2 – 3 HS, thực hiện Hoạt động 1 SGK tr.13:

Cho dãy A gồm 10 số nguyên lẻ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. Bạn Thái sẽ thực hiện một cách tuỳ ý các thao tác thêm vào và lấy ra trên ngăn xếp S ban đầu đang không có phần tử nào. Các thao tác thêm vào sẽ lấy ra lần lượt từng số trong dãy A để bổ sung vào ngăn xếp. Em hãy:

a) Vẽ ngăn xếp S thu được sau khi Thái thực hiện hai thao tác thêm vào liên tiếp và một thao tác lấy ra.

b) Cho biết Thái cần thực hiện những thao tác thêm vào và lấy ra theo thứ tự như thế nào để có thể thu được ngăn xếp S như ở Hình 3.

Hình 3. Ngăn xếp S

- GV yêu cầu HS tiếp tục thảo luận theo nhóm và trả lời các câu hỏi:

+ Ngăn xếp thuộc kiểu dữ liệu gì?

+ Phép toán thêm vào (push) và lấy ra (pop) được thực hiện ở đỉnh (Top) hay đáy (Bottom) của ngăn xếp?

+ Tại mỗi thời điểm, có thể truy cập được vào mấy phần tử của ngăn xếp?

+ Có thể lấy ra khỏi ngăn xếp phần tử bất kì được không? Vì sao?

+ Mỗi thao tác push sẽ thêm được mấy phần tử vào ngăn xếp?

+ Theo em, các phần tử trong ngăn xếp có thể được truy cập một cách trực tiếp như ở kiểu dữ liệu mảng không?

- GV giải thích cho HS hiểu về ý tưởng của thao tác lấy phần tử ra khỏi ngăn xếp.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 2 SGK tr.13 – 14 và thảo luận theo nhóm, trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- Đại diện các nhóm HS trả lời.

- Các nhóm khác đưa ra ý kiến nhận xét.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ kết quả thảo luận nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức. 

- GV chuyển sang nội dung tiếp theo.

2. Kiểu dữ liệu ngăn xếp và các phép toán cơ bản trên ngăn xếp

- Ngăn xếp thuộc kiểu dữ liệu tuyến tính, các phần tử được sắp xếp một cách lần lượt từ dưới đáy lên trên đỉnh, hết phần tử này đến phần tử khác.

- Phép toán thêm vào (push) và lấy ra (pop) chỉ được thực hiện ở đỉnh (Top) của ngăn xếp:

+ Tại bất kì thời điểm nào cũng chỉ truy cập được vào một phần tử trên cùng (ở đỉnh) của ngăn xếp. 

Trong một ngăn xếp, các phần tử phải được lấy ra theo thứ tự từ đỉnh xuống đến đáy một cách lần lượt (tức là, phần tử nào vào ngăn xếp sau sẽ được lấy ra khỏi ngăn xếp trước), không được phép lấy ra khỏi ngăn xếp phần tử bất kì. + Mỗi thao tác thêm vào sẽ chỉ thêm được một phần tử vào vị trí ngay trên đỉnh của ngăn xếp. 

- Các phần tử trong ngăn xếp không được truy cập một cách trực tiếp như ở kiểu dữ liệu mảng. Muốn lấy ra phần tử thứ i tính từ đỉnh ngăn xếp

xuống, phải thực hiện liên tiếp (i – 1) thao tác lấy ra để phần tử thứ i trở thành phần tử ở đỉnh ngăn xếp.

Hướng dẫn trả lời câu hỏi Hoạt động 1 SGK tr.13:

a) 

+ Ngăn xếp S ban đầu rỗng, khi thực hiện liên tiếp hai thao tác thêm vào sẽ thu được ngăn xếp S như hình sau:

+ Tiếp tục thực hiện một thao tác lấy ra sẽ thu được ngăn xếp S như hình sau:

b) Xuất phát từ ngăn xếp S rỗng, để thu được ngăn xếp S như ở Hình 3, Thái cần thực hiện các thao tác thêm vào và lấy ra theo thứ tự như sau:

+ Hai thao tác thêm vào: thêm lần lượt 1 và 3 vào ngăn xếp.

+ Một thao tác lấy ra: lấy 3 ra khỏi ngăn xếp.

+ Hai thao tác thêm vào: thêm lần lượt 5 và 7 vào ngăn xếp.

+ Một thao tác lấy ra: lấy 7 ra khỏi ngăn xếp.

+ Bốn thao tác thêm vào: thêm lần lượt 9, 11, 13, 15 vào ngăn xếp.

+ Hai thao tác lấy ra: lấy lần lượt 15 và 13 ra khỏi ngăn xếp.

+ Một thao tác thêm vào: thêm 17 vào ngăn xếp.

Hoạt động 3. Cài đặt ngăn xếp

a. Mục tiêu: HS biết cách biểu diễn ngăn xếp bằng mảng một chiều.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 3. Cài đặt ngăn xếp,thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Cách cài đặt ngăn xếp.

d. Tổ chức thực hiện:

 

--------------- Còn tiếp ---------------

 

Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II

MỘT VÀI THÔNG TIN:

  • Powerpoint soạn: Hiện đại, đẹp mắt để tạo hứng thú học tập
  • Giáo án word và PPT đồng bộ với nhau
  • Các phản hồi của giáo viên được trả lời ngay và luôn

Thời gian bàn giao giáo án

  • Đã có đủ chuyên đề I + II
  • Cập nhật liên tục để 30/01 bàn giao chuyên đề III

Phí giáo án chuyên đề

  • Giáo án word: 300k
  • Giáo án Powerpoint: 400k
  • Trọn bộ word + PPT: 650k

Chỉ gửi trước 350k. Sau đó, gửi dần trong quá trình nhận. Đến lúc nhận đủ kì 1 thì gửi nốt số còn lại

=> Khi đặt sẽ nhận ngay và luôn:

  • Phiếu trắc nghiệm cấu trúc mới: 15-20 phiếu
  • Nhận đủ chuyên đề I + II
  • Ít nhất 5 đề kiểm tra theo mẫu mới - có ma trận, lời giải...
  • PPCT, file word đáp án sgk

Cách đặt:

  • Bước 1: Gửi phí vào tk: 10711017 - Chu Văn Trí - Ngân hàng ACB (QR)
  • Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận giáo án

Xem toàn bộ: Giáo án chuyên đề Khoa học máy tính 12 cánh diều đủ cả năm

ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC

GIÁO ÁN WORD LỚP 12 CÁNH DIỀU

GIÁO ÁN POWERPOINT LỚP 12 CÁNH DIỀU

Giáo án Powerpoint Toán 12 Cánh diều
Giáo án powerpoint hình học 12 cánh diều
Giáo án powerpoint đại số 12 cánh diều

Giáo án powerpoint vật lí 12 cánh diều
Giáo án powerpoint sinh học 12 cánh diều
Giáo án powerpoint hoá học 12 cánh diều

Giáo án powerpoint ngữ văn 12 cánh diều
Giáo án powerpoint lịch sử 12 cánh diều
Giáo án powerpoint địa lí 12 cánh diều

Giáo án powerpoint Kinh tế pháp luật 12 cánh diều
Giáo án powerpoint Công nghệ 12 Công nghệ điện - điện tử cánh diều
Giáo án powerpoint Công nghệ 12 Lâm nghiệp - Thuỷ sản cánh diều

Giáo án powerpoint Tin học 12 - Định hướng Tin học ứng dụng cánh diều
Giáo án powerpoint Tin học 12 - Định hướng khoa học máy tính cánh diều
Giáo án powerpoint hoạt động trải nghiệm hướng nghiệp 12 cánh diều

GIÁO ÁN CHUYÊN ĐỀ LỚP 12 CÁNH DIỀU

GIÁO ÁN POWERPOINT CHUYÊN ĐỀ 12 CÁNH DIỀU

GIÁO ÁN DẠY THÊM LỚP 12 CÁNH DIỀU

Giáo án dạy thêm toán 12 cánh diều
Giáo án dạy thêm ngữ văn 12 cánh diều
Giáo án powerpoint dạy thêm ngữ văn 12 cánh diều
Giáo án powerpoint dạy thêm toán 12 cánh diều

Tài liệu giảng dạy

Xem thêm các bài khác

Chat hỗ trợ
Chat ngay