Danh sách câu hỏi
Có 27,889 câu hỏi trên 558 trang
Để hiểu rõ hơn về danh sách liên kết và các thao tác trên danh sách liên kết, Tí thực hiện các thao tác thuộc hai loại sau:
Loại 1: “Quay” k lần: tức là Tí sẽ lấy phần tử đầu tiên của danh sách liên kết và chèn nó vào sau phần tử cuối cùng, thực hiện k lần như vậy.
Loại 2: Đảo ngược danh sách liên kết.
Sau nhiều giờ lập trình, Ti tiến hành kiểm thử, tuy nhiên lại không tự tin vào kết quả của mình. Tí nhờ bạn code để đối chiếu kết quả.
Biết rằng Tí đã cài sẵn danh sách liên kết trong một mô đun và import nó vào trong chương trình. Danh sách liên kết này đảm bảo hoạt động chính xác. Tí cũng code sẵn phần xử lí nhập vào, in ra dữ liệu. Hãy hoàn thiện hai hàm rotate (quay mảng) và reverseList(đảo ngược).
Cấu trúc nút được định nghĩa như sau:
class Node:
def
init self.data self.next
(self, data):
= data
Giả sử có một biến tên node thuộc kiểu Node tượng trưng cho một nút trong danh sách liên kết. Để lấy nút tiếp theo, ta viết node.next; để lấy ra giá trị, ta viết node.data. Để tạo ra một nút mới có giá trị là value, ta viết
node = Node(value).
Hai hàm cần cài đặt được cung cấp tham số head: nút trỏ tới đầu của danh sách liên kết. Hàm trả về biến kiểu Node, trỏ tới phần tử đầu tiên của danh sách liên kết mới được thay đổi sau các truy ván.
Cụ thể hơn, các hàm này được định nghĩa như sau:
def rotate (head, k) -> Node: # Hoàn thiện phần thân hàm
def reverseList (head) -> Node: # Hoàn thiện phần thân hàm
Bài toán Josephus được phát biểu như sau:
Có n người đứng thành một vòng tròn, được đánh số thứ tự 1, 2, 3, 4,..., . Trò chơi bắt đầu từ người thứ nhất (đánh số 1). Mọi người sẽ lần lượt đếm 1 -2-1-2-1-2-... khi tới lượt của mình, bất kì ai sau khi đếm được số 2 thì phải bước ra khỏi vòng tròn. Trong toán học, người ta rút ra được một số công thức để tính ra được người còn sót lại cuối cùng trong vòng tròn, với luật chơi tổng quát (đểm tới k thay vì 2). Tuy nhiên, ở đây em lại quan tâm diễn biến của trò chơi này hơn. Em hãy dùng danh sách liên kết để mô phỏng
lại trò chơi trên.
Dữ liệu: Dòng duy nhất chứa số nguyên n.
Dòng duy nhất chứa n số là số hiệu của những người chơi bị loại ra khỏi vòng tròn theo thứ tự.
Ví dụ:
Lưu trữ dữ liệu cổ vật
Viện Sử học vừa khai quật một di tích lịch sử và thu về n cổ vật hữu cơ. Để xác định tuổi của n cổ vật này, chúng ta sử dụng phương pháp định tuổi bằng đồng vị phóng xạ Carbon-14.
Viện đã hoàn thành việc tính toán số liệu và tổ chức triển lãm cũng như công bố những nghiên cứu mới về n cổ vật. Tuy nhiên, để thúc đẩy niềm
yêu thích sử học nói chung và khảo cổ học nói riêng, cũng như cho học sinh một cái nhìn khác về nghiên cứu lịch sử, Viện đã mời các bạn học sinh tham quan triển làm, đồng thời hướng dẫn các bạn cách định tuổi các cổ vật nêu trên.
Để dễ dàng tính toàn, các bạn đã được cho biết trước:
Chu kì bản rã của đồng vị HC là 5 730 năm, tức sau 5 730 năm thì số lượng nguyên tử C sẽ giảm đi một nửa.
Lượng Carbon trong cơ thể của bất kì sinh vật nào khi còn sống đều bằng nhau và bằng 1 nguyên tử/g
Sau đó, Viện đã cho các bạn sử dụng thiết bị để đo thể tích cũng như đếm số lượng nguyên tử C của toàn bộ n cổ vật. Bây giờ, bạn sẽ tiến hành xác định niên đại của các đồ vật.
Dữ liệu đầu vào: Nhập từ tệp covat.inp.
Dòng đầu tiên chứa hai số: số nguyên dương n và số thực x.
− n dòng tiếp theo tương ứng với n cổ vật, dòng thứ i gồm hai số thực vị và m lần lượt chứa khối lượng (đơn vị tính: g) và số lượng nguyên tử C mà bạn đo được tại thời điểm hiện tại của cổ vật thứ 1.
Dữ liệu đầu ra:
KQ1 – Kết luận sơ bộ:
In ra tệp sobo.txt gồm n dòng là danh sách các cổ vật theo tuổi tăng dần. Dòng thứ i in ra:
Số thứ nhất là chỉ số của cổ vật có niên đại nhỏ thứ i.
Số thứ hai là tuổi của cổ vật đó, làm tròn xuống năm gần nhất (ví dụ, 19.7 năm làm tròn thành 19 năm),
KQ2 – Kiểm tra độ tin cậy của cổ vật:
Biết rằng, phương pháp định tuổi bằng đồng vị phóng xạ C chỉ cho ra kết quả tin cậy đối với các cổ vật không quá 50 000 tuổi, với các kết quả trên 50 000 tuổi phải dùng các đồng vị khác, hoặc phương pháp khác.
Em hãy in ra tệp tincay.txt gồm n dòng, dòng thứ i in ra “tin cay” nếu như kết quả của cổ vật thứ i là đáng tin cậy, hoặc nếu không thì in ra “khong tin cay”.
Thực hiện bài tập lớn về lập trình Python xử lí “Tam giác” với các yêu cầu sau:
Dữ liệu đầu vào: Nhập từ tệp văn bản tamgiac.txt chứa số liệu độ dài của các tam giác, mỗi dòng trong tệp văn bản chứa ba số a, b, c là số liệu về một tam giác. Độ dài các cạnh của mỗi tam giác là số nguyên hoặc số thực.
Kết quả đầu ra:
KQ1 – Phân loại tam giác: Kiểm tra ba số a, b, c có phải là độ dài ba cạnh của một tam giác hay không? Nếu ba số a, b, c là độ dài ba cạnh của một tam giác thì phân loại tam giác đó và đếm số lượng từng loại (tam giác đều, tam giác vuông cân, tam giác vuông, tam giác cân, tam giác thường). Kết quả đưa vào tệp phanloaiTG.txt.
KQ2 – Đưa vào tệp cvdtTG.txt:
a) Chu vi, diện tích các hình tam giác hợp lệ.
b) Cho biết hình tam giác nào có chu vi lớn nhất, hình tam giác nào có diện tích lớn nhất.
c) Sắp xếp tăng dần theo diện tích của từng loại tam giác.
Yêu cầu kết quả:
Với mục đích luyện kĩ năng lập trình, mỗi nhóm cần hoàn thành hai sản phẩm chương trình SP#1 và SP#2 với yêu cầu như sau:
SP#1: Tự viết các hàm (mô đun) chương trình, kế thừa những kết quả lập trình đã có được đến nay.
SP#2: Sử dụng tối đa các hàm đã có sẵn trong Python để hoàn thành nhiệm vụ.
Mã lệnh Python sau đây thể hiện hàm sắp xếp nhanh sử dụng phân đoạn Lomuto, được trích dẫn từ Hình 3 trong sách giáo khoa Tin học 11 – Khoa học máy tính.
def quickSort(a, lo, hi):
if lo < hi:
p = phandoan Lomuto (a, lo, hi) quickSort (a, lo, p 1) quickSort(a, p+1, hi)
Có thể thấy rằng trong phần cài đặt của hàm quickSort, ta lại gọi chính nó hai lần. Kĩ thuật này được gọi là đệ quy. Em hãy giải thích tại sao hàm quickSort không chạy vô hạn với một bộ tham số hợp lệ, dù nó sẽ liên tục gọi lại chính nó.
Phân bố phòng thi
Một trường học có n lớp, mỗi lớp có x bạn học sinh. Giả sử tên khai sinh của các bạn chỉ gồm hai tiếng: họ (một tiếng) và tên (một tiếng).
Sắp diễn ra kiểm tra cuối kì II, nhà trường yêu cầu phòng Công nghệ thông tin tạo danh sách phòng thi. Đầu tiên, nhà trường sẽ sắp xếp danh sách phần tên trong họ tên các bạn theo thứ tự từ điển, nếu trùng tên sẽ sắp xếp theo họ. Sau đó, các bạn sẽ lần lượt được phân vào phòng thi theo thứ tự này, mỗi phòng thi có đúng m bạn, riêng phòng cuối có thể ít hơn m bạn.
Ví dụ, phòng thi có bốn bạn. Có hai lớp, lớp 11A có ba bạn là: “Đỗ Nhỏ”, “Lê Hiếu” và “Lê Đức”. Lớp 11B có ba bạn là: “Đặng Hiếu”, “Lê Quý” và “Lê Hân”. Khi đó, danh sách các bạn trong hai lớp này theo thứ tự sắp xếp là: [Lê Đức, Lê Hân, Đặng Hiếu, Lê Hiếu, Đỗ Nhỏ, Lê Quý]. Ta có thể phân thành hai phòng và xếp bốn bạn đầu danh sách đã sắp xếp vào phòng 1, hai bạn còn lại vào phòng 2.
Em được cho danh sách học sinh của mỗi lớp. Em hãy tạo danh sách phòng thi. Dữ liệu: Nhập từ tệp danhsach.txt:
- Dòng đầu tiên gồm hai số nguyên dương n, m là số lượng lớp trong trường và số học sinh trong phòng thi.
- n cụm dòng tiếp theo, mỗi cụm dòng thứ i có dạng như sau:
Dòng đầu tiên chứa số x là số lượng học sinh trong lớp thứ i.
- x dòng tiếp theo, mỗi dòng gồm hai xâu cách nhau một khoảng trắng, mỗi xâu không chứa khoảng trắng và chỉ chứa kí tự trong bảng chữ cái tiếng Việt. Hai xâu này lần lượt là họ và tên của một bạn học sinh
trong lớp.
Kết quả: Đưa ra tệp phongthi.txt:
- Dòng đầu tiên in ra c là số lượng phòng thi.
- cụm dòng tiếp theo tương ứng với c phòng thi, mỗi phòng thi in ra những dòng sau:
- Dòng đầu tiên chứa số nguyên k là số lượng thí sinh trong phòng.
k dòng theo thứ tự từ điển, mỗi dòng chứa họ và tên của các bạn học sinh trong phòng thi.
Cần đảm bảo thứ tự xuất hiện của các dòng họ và tên phải theo thứ tự từ điển.
Sắp xếp tên sách tiếng Anh
Một thư viện vừa nhập về một kho sách mới về ngoại ngữ gồm n quyển, nhưng các quyển sách được sắp xếp rất lộn xộn. Em hãy giúp thủ thư sắp xếp lại những quyển sách này theo thứ tự từ điển, để việc xếp lên giá sách được thuận tiện hơn. Danh sách các sách được lưu trong tệp danhsach.txt.
Gợi ý: Một xâu 4 độ dài 1, được gọi là đứng trước xâu B độ dài 1, theo thứ tự từ điển, nếu sau khi loại bỏ toàn bộ khoảng trắng, tồn tại vị trí i đầu tiên sao cho khi so sánh thứ tự trong bảng chữ cái, A #B và 4 đứng trước B; hoặc 1, ≤ 1 và A = B với mọi i<I
Dữ liệu: Nhập từ tệp danhsach.txt:
- Dòng đầu tiên chứa số nguyên n.
- n dòng sau, mỗi dòng là một xâu biểu thị tên của một quyển sách. Dữ liệu đảm bảo tên chỉ gồm các chữ cái Latinh in hoa hoặc in thường cùng với dấu cách, giữa hai từ liên tiếp nhau chỉ chứa đúng một dấu cách và không có hai quyển sách nào trùng tên nếu không tính in hoa hoặc in thường. Kết quả: Hiển thị ở thiết bị ra chuẩn:
Số lần đổi chỗ.
Cho dãy số 4 gồm n số nguyên phân biệt: Ao, A,, A,,..., A n-1'
Em có thể dùng thao tác sau: Chọn hai vị trí kề nhau i và i + 1 bất kì (0 <i<n − 1), nếu A, > A + , thì đổi giá trị của A với A, . .
i+1
cho nhau.
Em hãy thao tác trên mảng A, sao cho sau khi thực hiện tuần tự các thao tác, mảng 4 được sắp xếp tăng dần,
Yêu cầu: Hãy in ra số lần đổi giá trị và vị trí i và j của lần đổi chỗ đó. Dữ liệu: Nhập từ thiết bị vào chuẩn:
- Dòng đầu tiên chứa một số nguyên dương n.
Dòng thứ hai chứa n số nguyên theo thứ tự án, A0, A1, A2,...,An-1"
Kết quả: Hiển thị ở thiết bị ra chuẩn:
Dòng đầu tiên chứa số nguyên dương K là số thao tác bạn làm.
- Á dòng sau, dòng thứ i in ra hai số a," (0Śu<"< n) cho biết bạn sẽ đội giá trị của hai vị trí u, v cho nhau.
Phân loại hoá chất
Trong phòng thí nghiệm Hoá học, có n lọ mất nhãn. Lần này, em không cần dùng các chất thử để phân biệt, vì tình huống hiện tại khá đặc biệt: Nhận thấy tất cả dung dịch trong phòng đều là các hợp chất quen thuộc nằm trong chương trình Hoá học 11 và mỗi chất này đều có khối lượng riêng khác nhau. Hơn nữa, trùng hợp là thể tích của các lọ này đều như nhau (số mol bằng nhau), theo thông tin từ giáo viên. Vì thế, chỉ cần biết khối lượng của các lọ là có thể biết được lọ nào chứa chất nào.
Bằng một chiếc cân chính xác, em đã lấy ra được khối lượng của n lọ đó, là dãy số a, a, a,........,
a, n-1'
Yêu cầu: Em hãy lập trình để kiểm tra trong n lọ này chứa bao nhiêu chất
khác nhau.
Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa một số nguyên dương n.
Dòng thứ hai chứa n số nguyên theo thứ tự a, a, a,,... -
Kết quả: Hiển thị ở thiết bị ra chuẩn số nguyên là số chất khác nhau:
Xét bài toán: Một hàng dọc gồm n bạn học sinh xếp theo thứ tự từ thấp đến cao, bạn thứ i (0 <i≤n − 1) có chiều cao là h (cm). Em hãy viết chương trình, với độ phức tạp O(nlog,n), sử dụng thuật toán tìm kiếm nhị phân để tính số cách chọn một cặp học sinh trong hàng sao cho chênh lệch chiều cao của hai bạn ấy bằng đúng giá trị d (cm) cho trước.
Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa một dãy số nguyên dương hạ, h,,,h với đảm bảo h<h,,, (0 ≤i≤n- 1).
• Dòng thứ hai chứa một số nguyên dương d.
Kết quả: Hiển thị ở thiết bị ra chuẩn một số nguyên là số lượng cặp chỉ số (i, j) để h − h = d (0<i<j<n-1).
Trong tiết Vật lí, An thực hành đo hiệu điện thế trong đoạn mạch song song. Theo lí thuyết, đáp án đo được phải bằng đúng x. An đã ghi lại kết quả của n lần đo, chính là dãy số a, a, @,,..., 0 - A2, An Kết quả được coi là chính xác nếu sai số tương đối không vượt quá 5%. An cần tính xem đã đo chính xác được bao nhiêu lần để xem thử dụng cụ thực hành của nhà trường còn tốt không? Dữ liệu: Nhập từ thiết bị vào chuẩn:
• Dòng đầu tiên chứa số nguyên dương n và số thực dương x.
• Dòng tiếp theo chứa n số thực dương a, a, a,...., cho có tối đa hai chữ số ở phần thập phân).
(dữ liệu được
Kết quả: Hiển thị ở thiết bị ra chuẩn một số nguyên duy nhất là số lượng kết quả đo chính xác.