CNTT4A2 COMMUNITY

Thảo luận học tập


You are not connected. Please login or register

Go downThông điệp [Trang 1 trong tổng số 1 trang]

on 25/9/2011, 9:05 pm
avatar
avatar

Chương 2
Tìm kiếm & sắp xếp

Viết chương trình hoàn chỉnh cho các bài toán sau đây

BT2-1.Cho dãy số.

84 32 13 64 1 55 48

Hãy mô phỏng sắp xếp tăng dần bằng các thuật toán toán chọn trực tiếp, đổi chỗ trực tiếp, nổi bọt, chèn trực tiếp qua dãy số trên.
BT2-2.Cho dãy n số nguyên a[0],a[1],…,a[n-1] đã được sắp xếp tăng dần và một số

nguyên x.

a.Hãy viết hàm tìm kiếm nhị phân kiểm tra xem x có thuộc dãy số trên hay không ? Nếu tìm thấy trả về giá trị i nhỏ nhất mà a[i] = x, nếu không trả về giá trị -1.
b.Cho dãy n = 8 số nguyên như sau:

1 2 4 4 4 9 10 15

Nếu x=4 thì phương pháp tìm kiếm nhị phân cho ra kết quả gì ?

c.Cho biết k số phần tử lớn nhất của dãy. Ví dụ với n=12
9 6 2 7 9 9 6 5 7 9 6 7

Nếu k=5 thì kết quả là 9, 9, 9, 9, 7

BT2-3.Cho mảng 1 chiều n phần tử. Sắp xếp các số nguyên tố tăng dần, các số khác giữ nguyên giá trị và vị trí.
BT2-4.Cho mảng vuông n. Hãy tìm phần tử lớn nhất trên mỗi đường chéo song song với đường chéo chính.
BT2-5.Cho ma trận 2 chiều m dòng, n cột.. Hãy sắp tăng dần các phần tử theo chiều từ trái qua phải và từ trên xuống dưới.
BT2-6.Sắp xếp các phần tử trên các đường chéo song song với đường chéo chính tăng dần.
BT2-7.Viết chương trình cho các phương pháp sắp xếp sau:

a.Đổi chỗ trực tiếp b.Chọn trực tiếp

c.Chèn trực tiếp d.Nổi bọt.

BT2-8.Cho dãy số.

84 32 13 64 1 55 48

Hãy mô phỏng sắp xếp tăng dần bằng các thuật toán toán Quick Sort, Merge

Sort, Heap Sort, Shell Sort qua dãy số trên.

BT2-9.Cho mảng một chiều gồm n phần tử là các số nguyên.

Sắp xếp các số chẵn trong mảng theo thứ tự tăng, sắp xếp các số lẻ theo thứ tự giảm dần, các số 0 giữ nguyên vị trí..
BT2-10.Cho mảng một chiều gồm n phần tử là các số nguyên. Tìm k giá trị lớn nhất khác nhau của mảng
BT2-11.Cho mảng một chiều gồm n phần tử là các số nguyên. a.Chỉ giữ lại một giá trị trong số các giá trị giống nhau.
b.Sắp xếp các số chẵn trong mảng theo thứ tự tăng, sắp xếp các số lẻ theo thứ

tự giảm dần, các số 0 giữ nguyên vị trí..

BT2-12.Cho tập tin văn bản songuyen.inp chứa các số nguyên. Hãy ghi các số nguyên tố trong tập tin songuyen.inp vào tập tin nguyento.out theo thứ tự tăng dần mỗi dòng ghi 10 số, các số cách nhau ít nhất một khoảng cách.
BT2-13.Cho 2 file số nguyên được sắp tăng dần. Hãy trộn 2 file để được một file cũng được sắp tăng dần (không dùng mảng).
BT2-14.Cho một tập tin văn bản. Hãy cho biết số lượng của các số nguyên tố, chính phương, hoàn hảo, số Amstrong trong tập tin này.
BT2-15.Viết chương trình cho phương pháp sắp xếp Quick sort

BT2-16.Hãy vẽ cây phân hoạch đệ qui của thuật toán Quick-Sort trong trường hợp xấu nhất. Từ đó, chứng tỏ rằng chi phí thuật toán Quick-sort trong trường hợp này là O(n2).
BT2-17.Viết chương trình cho phương pháp sắp xếp cây (heap sort).

BT2-18.Viết chương trình cho phương pháp sắp xếp trộn trực tiếp(merge sort).

BT2-19.Viết chương trình cho phương pháp sắp xếp với độ dài bước giảm dần

(shell sort).

BT2-20.Hãy cho biết số phần tử tối thiểu và tối đa trong một heap có chiều cao h ?


Chương 3
Cấu trúc danh sách liên kết

Viết chương trình hoàn chỉnh cho các bài toán sau đây

BT3-1.Cho một danh sách liên kết đơn l, mỗi nút là một số nguyên dương. a.Tìm phần tử lớn nhất danh sách l.
bTính tổng các phần tử của danh sách l.

c.Đếm xem trong danh sách l có bao nhiêu số nguyên tố ?

d.Đếm xem trong danh sách có bao nhiêu số âm ? bao nhiêu số bằng 0 ? bao nhiêu số dương ?
e.Đếm xem trong danh sách có bao nhiêu số bằng x ?

f.Tìm phần tử dương nhỏ nhất trong danh sách.

BT3-2. Cho một danh sách liên kết đơn l, mỗi nút là một số nguyên dương. a.Xóa phần tử đầu tiên trong danh sách.
b.Xóa phần tử cuối cùng trong danh sách. c.Xóa một phần tử được trỏ bởi con trỏ q.
d.Xóa một phần tử ngay trước phần tử được trỏ bởi con trỏ q. e.Xóa một nút có giá trị k.
BT3-3. Cho một danh sách liên kết đơn l, mỗi nút là một số nguyên dương. a.Hãy tạo danh sách l1 chỉ chứa các số nguyên tố từ danh sách l.
b.Tách danh sách l thành 2 danh sách: một danh sách chứa toàn số chẵn, một danh sách chứa toàn số lẻ.
BT3-4. Cho một danh sách liên kết đơn l, mỗi nút là một số nguyên dương. a.Trộn hai danh sách tăng dần thành một danh sách tăng dần.
b.Sắp xếp các phần tử của L giảm dần theo phương pháp chọn trực tiếp

BT3-5.Viết chương trình thực hiện các yêu cầu sau:

a.Khai báo cấu trúc dữ liệu của một danh sách liên kết đơn các tỉnh. Biết rằng thông tin của mỗi tỉnh bao gồm: tên tỉnh, diện tích, dân số
b.Cài đặt các thao tác cơ bản cho danh sách liên kết đơn các tỉnh (thêm, sửa , xóa, duyệt).
c.Tính tổng diện tích của tất cả các tỉnh trong danh sách liên kết

d.Tìm địa chỉ của node chứa tính có diện tích lớn nhất trong danh sách liên kết.
e.Tìm một tỉnh có dân số lớn nhất

f.Sắp xếp danh sách tăng dần theo diện tích.

BT3-6.Viết chương trình thực hiện các yêu cầu sau:

a.Khai báo cấu trúc dữ liệu của một danh sách liên kết đơn để lưu tọa độ các

đỉnh của một đa giác lồi trong mặt phẳng OXY. b.Tính chu vi của đa giác.
c.Tính diện tích của đa giác.

BT3-7.Hãy viết phần khai báo cấu trúc dữ liệu để mô tả một danh sách liên kết đơn mà mỗi phần tử chứa một số nguyên. Viết các hàm thực hiện các yêu cầu sau:
a.Đếm các số nguyên tố của dánh sách

b.Tạo một danh sách l1 chỉ chứa các số chẵn và chia hết cho 3 từ danh sách l. c.Sắp xếp các phần tử của danh sách theo chiều giảm dần.
BT3-8.Hãy khai báo kiểu danh sách liên kết đơn có tên LIST mà mỗi phần tử chứa các thông tin về một sinh viên bao gồm một số nguyên dương 4 bye chỉ mã số sinh viên và một chuỗi ký tự dài tối đa 35 cho biết họ và tên của sinh viên.
Thực hiện các công việc sau:

a.Xây dựng hàm sắp xếp danh sách sinh viên theo thứ tự tăng dần của mã số sinh viên.
b.Xây dựng hàm thêm một sinh viên mới vào danh sách(đã có thứ tự) sao cho vẫn bảo đảm thứ tự tăng dần của mã số.
BT3-9.Cho một danh sách liên kết, mỗi nút chứa một số nguyên. a.Thêm một phần tử có giá trị x vào đầu danh sách
b.Chỉ giữ lại một giá trị trong số các giá trị giống nhau.

c.Kiểm tra xem danh sách có được sắp xếp tăng dần hay không?

d.Đảo ngược danh sách.

e.Sắp xếp các số chẵn trong danh sách theo thứ tự tăng, sắp xếp các số lẻ

theo thứ tự giảm dần, các số 0 giữ nguyên vị trí..

BT3- 10.Hãy cho biết chi phí của mỗi công việc sau (theo O()): a.Tính tổng của N số tự nhiên lẻ (số nguyên dương lẻ) đầu tiên b.Liệt kê N phần tử của mảng

c.Liệt kê 1 phần tử trong 1 mảng có N phần tử

d.Tìm 1 phần tử trong một danh sách liên kết đơn có N phần tử đã được sắp thứ tự tăng dần
e.Thêm 1 phần tử vào hàng đợi đã có sẵn N phần tử

BT3-11.a.Cài đặt thuật toán sắp xếp chèn trực tiếp trên xâu kép

b.Cài đặt thuật toán sắp xếp chèn trực tiếp bằng cách sử dụng đệ quy.

BT3-12.Sắp xếp danh sách tăng dần thuật toán Quick sort.

BT3-13.Cộng hai đa thức (mỗi node có 3 thành phần: hệ số khác 0 của một số hạng, số mũ tương ứng và mốc nối tới node tiếp theo).
BT3-14.Ta có 4 lựa chọn: 1. Stack; 2. Queue; 3. List; 4. Cả 3 CTDL này đều không thích hợp. Trong mỗi tình huống sau, hãy cho biết áp dụng lựa chọn nào là thích hợp nhất:
a.Các khách hàng tại quầy bán vé xe lửa lấy số thứ tự để mua vé b.Một danh sách tên theo thứ tự ABC
c.Các số nguyên cần phải sắp thứ tự

d.Danh sách các món hàng đã bán trong ngày tại quầy thâu ngân trong siêu thị
e.Chương trình có sử dụng kỹ thuật Back-tracking f.Các máy bay đang chờ đáp xuống phi trường
BT3-15.Hãy thể hiện thuật toán sắp xếp nổi bọt trên danh sách liên kết kép.

BT3-16.Tính giá trị của đa thức P(x) với x và các hệ số cho biết trước được tổ chức dưới dạng một danh sách liên kết (mỗi node có 3 thành phần: hệ số khác 0 của một số hạng, số mũ tương ứng và mốc nối tới node tiếp theo).
BT3-17.Hoàn chỉnh các thao tác trên Stack và Queue.

BT3-18.Cài đặt thuật toán Quicksort theo kiểu không đệ quy.

BT3-19.Cài đặt thuật toán Mergesort trên xâu kép.

BT3-20.Tính giá trị của một biểu thức dạng chuỗi ký tự bao gồm các chữ số và các phép toán +,-,*,/ , % và dấu đóng mở ngoặc đơn.
Ví dụ: (( 2 + 3 )*2) – 4/2 = 12


http://vdvinh-nd.blogspot.com

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà whatsltd4us
on 25/9/2011, 9:25 pm
avatar
avatar

oh anh ơi chỉ có câu hỏi thôi ak ? cái môn này khó lắm anh giải đi cho anh em tham khảo với [You must be registered and logged in to see this image.]

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà ٩(̾●̮̮̃̾•̃̾)۶ ٩(͡๏̯͡๏)۶
on 25/9/2011, 10:18 pm
avatar
avatar

Cái này anh cũng chịu thôi :))
http://vdvinh-nd.blogspot.com

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà whatsltd4us
on 25/9/2011, 10:52 pm
avatar
avatar

hic, nhìn hoa cả mắt, cho ít ít còn có hứng làm, chứ nhìn vầy hoa mắt biét làm cái nào trước
http://tin4a2uneti.tk

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà kienhl
on 26/9/2011, 9:39 pm
avatar
avatar

cứ từ từ mà làm.

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà thaonet
on 28/9/2011, 7:53 pm
avatar
avatar

nhiu vay lam ma chet ak huhu
a dang tu tu tung it mot con suong nhin nhiu wa nan huhu
01 01

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà zuizui
on 1/10/2011, 10:49 am
avatar
avatar

Làm dần dần, kiểu gì chả hết
http://vdvinh-nd.blogspot.com

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà whatsltd4us

Thích

Báo xấu [0]

Gửi một bình luận lên tường nhà Sponsored content

Về Đầu TrangThông điệp [Trang 1 trong tổng số 1 trang]

« Xem bài trước | Xem bài kế tiếp »

Bài viết mới cùng chuyên mục

      Quyền hạn của bạn:

      Bạn không có quyền trả lời bài viết