Ngày đăng: 10/08/2014, 19:20
Đại Học Công Nghệ Thông Tin. Đại Học Thái Nguyên. Đề 1 Câu 1( 2 điểm) Thế nào là giải thuật; cấu trúc dữ liệu, mối quan hệ giữa chúng? Hãy nêu một vài cấu trúc dữ liệu tiền định của ngôn ngữ lập trình mà anh (chị) biết? Câu 2( 5 điểm ) Giả sử cần quản lý một lớp học bao gồm các sinh viên. Mỗi sinh viên gồm các thông tin sau: Họ Tên, Lớp, Số báo danh, Điểm trung bình. Anh (chị) hãy: 1) Viết dạng setup danh sách này bằng cấu trúc danh sách link đơn, 2) Với cấu trúc danh sách đã setup, viết các chương trình con thực hiện các yêu cầu như sau: a) Nhập vào danh sách gồm n sinh viên b) Loại bỏ khỏi danh sách những sinh viên có điểm trung bình < 5 c) Sắp xếp danh sách theo trường lớp tăng dần d) In ra màn hình danh sách sinh viên theo từng lớp (n là một số nguyên dương tự nhập từ keyboard) Câu 3( một điểm ) Anh ( Chị ) hãy nêu ưu nhược điểm của cách setup danh sách bởi danh sách link đơn? Câu 1 + Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng, xác nhận một dãy các thao tác trên một số đối tượng nào(dữ liệu) đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả muốn (0.5 đ) + Phương thức tổ chức trình diễn dữ liệu mà theo đó dữ liệu được lưu trữ và được xử lý trong MTĐT, được gọi là cấu trúc dữ liệu (0.5 đ) + Mối quan hệ giữa cấu trúc dữ liệu và giải thuật: Giải thuật thúc đẩy trên dữ liệu lưu trữ trong các cấu trúc để cho ra kết quả muốn. Trong lập trình, chúng quan hệ với nhau theo ràng buộc sau: Giải thuật + cấu trúc dữ liệu = chương trình (0.5 đ) + Một vài cấu trúc dữ liệu của ngôn ngữ lập trình: Mảng, bản ghi, xâu ký tự, tệp tin … (0.5 đ) Câu 2 *) Dạng setup danh sách (1 đ) Type Sinhvien = record Hoten: String; Lớp : String; SoBD: String; ĐTB: real; ` Next: ^ Sinhvien; end; List = ^Sinhvien; Var L: List; *) Viết giải thuật 1) Nhập danh sách gồm n sinh viên (1 đ) + Nhập số lượng sinh viên hiện có n: readln(n); + Sử dụng vòng lăp i chạy từ 1 -> n, mỗi lần lặp nhập 1 sinh viên và gắn vào danh sách: for i:=1 to n do begin – new(M); {yêu cầu MT cấp phát ô nhớ chứa dữ liệu của sinh viên cần nhập } – Nhập các thông tin về sinh viên, lưu vào ô nhớ được trỏ bởi M – Gắn kết ô nhớ được trỏ bởi M vào danh sách end; 2) Loại bỏ những SV có điểm trung bình <5 (1 đ) Xác minh xem danh sách L có rỗng hay không? Nếu rỗng trở về chương trình chính, nếu không rỗng thực hiện loại bỏ như sau: – Sử dụng con trỏ phụ q duyệt tử đầu đến cuối danh sách, nếu q^.dtb <5 thì gọi thủ tục loại bỏ phần tử được trỏ bởi q trong danh sách – Viết thủ tục loại bỏ phần tử được trỏ bởi con trỏ q trong danh sách L: a) Giả sử đã biết vị trí con trỏ q b) Sử dụng con trỏ phụ p di chuyển đến vị trí trước q: P:= L; While p^.nextandlt;> q do p:= p^.next; c) Loại bỏ phần tử ở vị trí q: p^.next := q^.next; dispose(q); q:= p^.next;// lưu vị trí tiếp theo vị trí loại bỏ để còn loại bỏ tiếp 3) Sắp xếp danh sách theo trường lớp tăng dần (1 đ) Có thể sử dụng một trong các thuật toán sắp xếp để sắp xếp dữ liệu trên danh sách link, ở đây ta sử dụng giải thuật sắp xếp chọn trực tiếp (selection sort) và sử dụng cách tiếp cận:giữ nguyên mối link của các nút trong danh sách và hoán vị nội dung của các nút: Giải thuật: Procedure ListSelection_Sort(var L: List) Var p, q, min: List; Begin p:=L; While (pandlt;>nil) do Begin q:=p^.next; min:=p; While (qandlt;>nil) do Begin If (q^.infor nil) do Begin Write(M^. hoten); Write(M^. Lop); Write(M^. sbd); P:=M; M := M^.next; If (M^.lopandlt;>p^.lop) then writeln(‘Các sinh vien lop M^.lop la:’); End; Câu 3 Ưu thế: (0.5 đ) – Không gây hiện tượng lãng phí bộ nhớ lưu trữ (Hiện tượng giữ chỗ để đấy mà không dùng đến như danh sách setup bởi mảng) – Cấu trúc dữ liệu danh sách setup bởi con trỏ còn gọi là cấu trúc dũ liệu động, không gian bộ nhớ lưu trữ được cấp phát trong heap, do đó nó không bị hạn chế bởi kích thước 64kb như so với cấu trúc dữ liệu tĩnh – Các phần tử trong danh sách nằm ở những vị trí dải dác, do đó tận dụng được những không gian trống này, mà không cần một vùng nhớ tiếp theo như setup bởi mảng Nhược điểm: (0.5 đ) – Vận tốc truy cập đến các phần tử trong danh sách là chậm, không đồng đều so với mọi phần tử (truy cập tuần tự một chiều) – Từ phần tử sau không truy cập ngược đến các phần tử đứng trước nó được – mỗi phần tử trong danh sách tốn thêm một ô nhớ có kích thước là 4byte để lưu địa chỉ của phần tử xếp sau nó trong danh sách Đề 2 Câu 1( 3 điểm) 1) Thế nào là cấu trúc dữ liệu tiền định (định sẵn ) của ngôn ngữ lập trình bậc cao? 2) Hãy nêu một vài cấu trúc dữ liệu tiền định của ngôn ngữ lập trình mà anh (chị ) biết? 3) Vì sao chỉ sử dụng các cấu trúc dữ liệu tiền định không đủ thỏa mãn yêu cầu về việc tổ chức, lưu trữ dữ liệu của mọi bài toán ứng dụng thực tiễn ?. Một số bài toán ứng dụng phải cần sử dụng đến các cấu trúc dữ liệu do người lập trình tự khái niệm? Hãy nêu một bài toán ứng dụng như vậy, phân tích bài toán để trổ tài điều đó? Câu 2( 3 điểm ) Giả sử ta cần quản lý một ngăn xếp chứa các số nguyên. Viết dạng setup của cấu trúc ngăn xếp này bằng mảng. Với cấu trúc ngăn xếp vừa setup, hãy viết thủ tục thêm phần tử x vào vị trí thứ k kể tử đỉnh ngăn xếp sao cho các phần tử khác không thay đổi thứ tự (k là số nguyên nhập từ keyboard). Câu 3( 2 điểm ) Anh ( Chị ) hãy nêu một lớp bài toán mà sử dụng cấu trúc ngăn xếp rất thích hợp cho việc khắc phục các yêu cầu của bài toán ? phân tích bài toán đã nêu để trổ tài rõ điều đó? Câu 1 1) Cấu trúc dữ liệu tiền định của ngôn ngữ lập trình bậc cao là các cấu trúc dữ liệu đã được khái niệm sẵn trong ngôn ngữ lập trình đó, người lập trình chỉ việc sử dụng mà không cần khái niệm lại (1 đ) 3) Một vài cấu trúc dữ liệu tiền định như: mảng, bản ghi, tệp tin, (1 đ) 2) Các cấu trúc dữ liệu tiền định có sẵn trong ngôn ngữ lập trình không thỏa mãn đầy đủ được nhu cầu lưu trữ dữ liệu lớn của mọi chương trình, không phản ánh đầy đủ bản chất của các đối tượng dữ liệu có trong thực tiễn = > người ta cần đến các cấu trúc dữ liệu do người lập trình tự khái niệm. (0.5 đ) Ví dụ: Xét bài toán quản lý hồ sơ sinh viên trong một khoa, các yêu cầu quản lý hồ sơ là: Thêm, sửa, xóa, tìm kiếm, … hồ sơ.=> Sử dụng cấu trúc dữ liệu mảng (cấu trúc tiền định)để lưu các thông tin về hồ sơ là không thích hợp vì: cấu trúc mảng không cho phép thực hiện phép toán thêm, xóa, không gian không đủ để lưu trữ toàn bộ hồ sơ nếu số lượng hồ sơ thực tiễn lớn,… (0.5 đ) Câu 2 + Dạng setup ngăn xếp sử dụng mảng: (1 đ) const n = ; type Stack = Record Top: 0 n ; Element : array [1 n] of integer; End; + Thêm phần tử x vào ngăn xếp S ở vị trí thứ k tính từ đỉnh ngăn xếp: (2 đ) Xác minh xem ngăn xếp có rỗng không, nểu rỗng thì thêm vào đỉnh ngăn xếp, Nếu ngăn xếp không rỗng: Xác minh xem số k nhập vào có > top hay không? Nếu to hơn thì thêm x vào đỉnh ngăn xếp, nếu không: Lấy (top-k+1) phần tử kể từ đầu ngăn xếp ra một ngăn xếp phụ, thêm phần tử phần tử x vào ngăn xếp, đổ ( top – k+1) phần tử từ ngăn xếp phụ vào ngăn xếp ban đầu do đó đảm bảo không thay đổi trật tự các phần tử trong ngăn xếp ban đầu sau thời điểm loại bỏ phần tử ở vị trí k.(thủ tục tương ứng tự viết) Câu 3 (1 đ) – Cấu trúc ngăn xếp thường được vận dụng cho những bài toán có trình tự truy xuất ngược với trình tự lưu trữ. Ví dụ: + Bài toán chuyển hóa cơ số, tìm ước số chung của hai số nguyên, bài toán tính giá trị biểu thức, + Thường vận dụng trong một số bài toán tìm đường đi trong lý thuyết đồ thị (lưu vết đường đi) + làm môi trường lưu trữ các biến toàn cục và cục bộ của các thủ tục trong chương trình dịch của ngôn ngữ lập trình. (1 đ) – Phân tích cách giải các bài toán trên để trổ tài rõ điều đã nêu Đề 3 Câu 1( 2 điểm) Có người nói: “Phép đệ quy phản ánh chiến thuật “chia để trị” trong cách giải bài toán ”. Điều đó có đúng không ? anh (chị ) hãy giải thích và cho ví dụ minh họa cho điều đó ? Câu 2( 3 điểm ) Giả sử cần quản lý một cây chứa các số nguyên, các đỉnh trên cây được đánh số theo một thứ tự nào đó. Hãy viết dạng setup cây bằng cha của mỗi đỉnh sử dụng mảng. Với cách setup này, viết các giải thuật tìm con cả, tìm cha của đỉnh k cho trước (k là số nguyên nhập từ keyboard) Câu 3( 3 điểm ) Cho một cây thư mục T và kích thước của từng thư mục con trong PC như sau: Anh(chị) hãy: 1) Viết dạng setup cây bằng con trưởng và em liền kề của mỗi đỉnh, sử dụng con trỏ 2) Để tính tổng kích thước của toàn bộ cây thư mục trên thì ta duyệt cây theo thứ tự nào? 3) Mô tả phương pháp tính tổng kích thước cây thư mục? users BT 1 KB Tin 2 KB Toan 1KB BT1 8 KB Bt2 10 kB Bt3 6 KB BT1 9KB BT2 10 kB Câu 1 + “Phép đệ quy phản ánh chiến thuật “chia để trị” trong cách giải bài toán ” điều đó là đúng, nó trổ tài ở chỗ: Để giải bài toán với số lượng dữ liệu đầu vào lớn, ta giải bài toán với số lượng dữ liệu đầu vào nhỏ hơn, và nhỏ hơn nữa, cứ thế gọi đệ quy cho đến gọi đến trường hợp bài toán xảy ra suy biến (trường hợp này bài toán được xử lý). Đây chính là tư tưởng của chiến thuật chia để trị (1 đ) + Ví dụ: (1 đ) Chạy chậm một giải thuật đệ quy, ví dụ tính n ! : Để tính n! Ta tính (n-1)!, (n-n+1) = 1! = 1.(vẽ hình minh họa) Câu 2 + Dạng setup cây bằng cha của mỗi đỉnh: (1 đ) Const n = ; Type Node = Record Info: Integer; parent: 0 n; End; Tree = Array [1 n ] of Node; Var T: Tree; + Tìm cha của đỉnh thứ k: (1 đ) parent (T, k) := T[k].parent; + Tìm con cả của đỉnh thứ k trên cây T (1 đ) Duyệt các đỉnh trên cây T, xuất phát từ đỉnh gốc(i:=1), xác minh xem cha của đỉnh i có = k không, nếu = k, tổng kết i là con cả, dừng giải thuật, nếu cha của i <>k thì duyệt đỉnh tiếp theo trên cây T bằng cách cho i:= i+1. Lặp đi lặp lại phép duyệt các đỉnh trên T cho đến khi tìm thấy thì dừng (found = true), hoặc duyệt hết các đỉnh trên T (iandgt;n với n là số đỉnh trên cây) thì cũng dừng và tổng kết không tim thấy Câu 3 + Dạng setup cây bằng con trưởng và em liền kề của mỗi đỉnh: (1 đ) Type Tree = ^Nut; Nut = record Tenthumuc: string; Kichco:integer; EldestChild, Nextsibling:Tree; End; Var T: Tree; + Duyệt cây theo thứ tự sau để xác nhận tổng kích thước của cây thư mục (1 đ) + Mô tả phương pháp tính tổng kích thước cây thư mục T trên: (1 đ) – Biến: tong:= 0; {tong lưu tổng kích thước toàn bộ cây thư mục} – Procedure postOder(T : tree, var tong:integer); Var C: tree; Begin if (T=nil) then exit; else begin C:=t^.eldestChild; postOrder(C); C:=C^.nextsibling; While (Candlt;>nil) do Begin postOrder(C); C:= C^.nextsibling; End; Tong:=tong+T^.kichco; end; End; Đề 4 Câu 1( 2 điểm) Trình bày các dấu hiệu của giải thuật đệ quy. Hàm đệ quy (viết bằng ngôn ngữ pascal) dưới đây cho kết quả là gì? Giải thích vì sao? Function Tinh(n,x: byte): Longint; Begin If n = 1 then Tinh := x Else Tinh := n* Tinh(n-1,x); End; Câu 2( 4 điểm ) Giả sử một nhà cung cấp cần quản lý các cán bộ, mỗi cán bộ cần quản lý các tính chất sau: Họ tên, năm sinh, giới tính, địa chỉ, trình độ, chức danh . Anh(chị) hãy lựa chọn một cấu trúc dữ liệu để quản lý các thông tin của các cán bộ trong nhà cung cấp đó, sao cho: – Dữ liệu được lưu trong bộ nhớ lưu trữ trong – Thuận tiện cho các phép toán: thêm, xóa cán bộ – Tiết kiệm không gian bộ nhớ lưu trữ nhất. Với cấu trúc dữ liệu mà anh(chị) đã lựa chọn. Anh(chị) hãy: 1) Viết dạng setup của cấu trúc dữ liệu đó 2) Viết giải thuật đếm số lượng cán bộ trong nhà cung cấp 3) Hiển thị thông tin của các cán bộ trong nhà cung cấp 4) Loại bỏ những người đến tuổi về hưu (biết rằng nam: 60 tuối; nữ: 55 tuổi thì về hưu) Câu 3( 2 điểm ) Nêu khái niệm danh sách? các cách setup danh sách bởi mảng, bởi danh sách link đơn? ưu nhược điểm của từng dạng setup? Câu 1 + Ba dấu hiệu của giải thuật đệ quy: ( 1 đ) – Trong giải thuật đệ quy lúc nào cũng có lời gọi đến chính nó – Sau mỗi lời gọi đệ quy, kích thước của bài toán được thu nhỏ hơn trước – Có một trường hợp suy biến: bài toán được khắc phục theo một cách khác hoàn toàn và giải thuật cũng kết thúc + Kết quả của hàm đệ quy là: x*n!, vì: ( 1 đ) n = 1 cho kết quả là: 1*x n = 2 cho kết quả là: 1*2*x n = 3 cho kết quả là: 1*2*3*x n = n cho kết quả là: 1*2*3* *n*x = n! * x Câu 2 1) Cấu trúc dữ liệu lựa chọn là danh sách link đơn ( 1 đ) Dạng setup Type Canbo = record Hoten: String; Năm sinh : integer; Giớitinh: boolean; Diachi, trinhdo, chucdang: string; ` Next: ^ Canbo; end; List = ^Canbo; Var L: List; 2) Đếm số lượng cán bộ trong trong danh sách ( 1 đ) – Sử dụng biến đếm lưu số lượng cán bộ trong nhà cung cấp, ban đầu dem:= 0 , – Sử dụng con trỏ phụ M duyệt từ đầu đến cuối danh sách, duyệt đến cán bộ nào thì tăng biến đếm lên 1: – In biến đếm ra màn hình 3) Hiển thị các cán bộ trong nhà cung cấp: ( 1 đ) Sử dụng con trỏ phụ M duyệt từ đầu đến cuối danh sách, duyệt đến cán bộ nào thì hiển thị các thông tin của cán bộ đó lên màn hình: 4) Loại bỏ các cán bộ đến tuổi về hưu trong nhà cung cấp: ( 1 đ) Cách làm: b1) Tìm cán bộ trước nhất trong danh sách đến tuổi về hưu, giả sử vị trí được trỏ bởi p b2) Loại bỏ cán bộ ở vị trí p b3) Lặp đi lặp lại b1); b2) cho đến khi hết vị trí tìm thấy Lưu ý: – để tìm cán bộ thỏa mãn điều kiện ta duyệt từ đầu danh sách p:=L đến khi tìm thấy thì dừng – để loại bỏ học sinh ở vị trí p: a) Di chuyển con trỏ phụ M đến vị trí trước p: M:=L; While M^.next <>p do M:=M^.next; b) Bứt link, gắn link, giải phóng p: M^.next:=p^.next; Dispose(p); Câu 3 […]… nhớ, là cấu trúc tĩnh Đề xuất cấu trúc thích hợp hơn: Cấu trúc danh sách link vì: khắc phục các hạn chế của danh sách setup như trên Đề 9 Câu 1( 2 điểm) Thế nào là cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu và giải thuật đóng vai trò như vậy nào trong quá trình khắc phục một bài toán tin học? Anh (Chị) hãy lấy một ví dụ minh họa cho điều đó? Câu 2( 4 điểm ) Giải thuật tính ước số chung… đỉnh được nhập vào cây theo thứ tự được đánh số như trên Câu 1 + Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng, xác nhận một dãy các thao tác trên một số đối tượng nào (dữ liệu) đó sao cho sau một số hữu hạn bước thực hiện ta đạt được kết quả muốn (0.5 đ) + Phương thức tổ chức trình diễn dữ liệu mà theo đó dữ liệu được lưu trữ và được xử lý trong MTĐT, được gọi là cấu trúc dữ liệu (0.5 đ) +… bởi mảng) – Cấu trúc dữ liệu danh sách setup bởi con trỏ còn gọi là cấu trúc dũ liệu động, không gian bộ nhớ lưu trữ được cấp phát trong heap, do đó nó không bị hạn chế bởi kích thước 64kb như so với cấu trúc dữ liệu tĩnh – Các phần tử trong danh sách nằm ở những vị trí dải dác, do đó tận dụng được những không gian trống này, mà không cần một vùng nhớ tiếp theo như setup bởi mảng Nhược điểm: – Vận tốc truy… trung bình = (toan+ly+hoa+ngoaingu)/4) – Tìm kiếm thí sinh theo số báo danh nhập vào Câu 1 + Đệ quy: Một đối tượng được gọi là đệ quy nếu nó bao gồm chính nó như là một phòng ban hoặc nó được khái niệm dưới dạng của chính nó (0.5 đ) + Giải thuật đệ quy: là giải thuật có chứa lời giải đệ quy Lời giải đệ quy là lời giải của bài toán T được thực hiện bởi lời giải của bài toán T’ có dạng như T (cỡ của T’< T)… bài toán ứng dụng mà sử dụng cấu trúc dữ liệu hàng đợi giúp việc khắc phục yêu cầu bài toán được thuận tiện hơn ? phân tích bài toán đã nêu để trổ tài rõ điều đó? Câu 1 – Hàng đợi là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào hàng đợi được thực hiện ở một đầu (đầu này được gọi là lối sau – Real), còn phép lấy một phần tử ra khỏi hàng đợi được thực hiện ở đầu kia (lối trước – Front)… thông tin Số báo danh, họ tên, lớp 1 Hãy sử dụng cấu trúc dữ liệu danh sách link đơn để lưu trữ các thông tin của các thí sinh dự thi Viết dạng setup tương ứng của cấu trúc trên 2 Xây dựng các chương trình con thực hiện các nhiệm vụ sau: – Nhập thông tin về các thí sinh dự thi (điều kiện dừng là nhập SBD = rỗng) – Hiển thị các thí sinh dự thi theo lớp – Loại bỏ các thí sinh có điểm trung bình < 5… toán, lý, hóa, ngoại ngữ Mỗi thí sinh cần quản lý các thông tin Số báo danh, họ tên, lớp 3 Hãy sử dụng cấu trúc dữ liệu danh sách link đơn để lưu trữ các thông tin của các thí sinh dự thi Viết dạng setup tương ứng của cấu trúc trên 4 Xây dựng các chương trình con thực hiện các nhiệm vụ sau: – Nhập thông tin về các thí sinh dự thi (điều kiện dừng là nhập SBD = rỗng) – Hiển thị các thí sinh dự thi. .. Câu 3 – Bài toán tính biểu thức tiền tố, lưu vết đường đi trên đồ thị, khử đệ quy, (0.5 đ) – Phân tích bài toán : (0.5 đ) Đề 7 Câu 1( một điểm) Nêu khái niệm đệ quy, giải thuật đệ quy, Cho ví dụ về một giải thuật đệ quy? Câu 2( 3 điểm ) Hàm Ackermann là hàm hai đối số với giá trị của đối số là số nguyên không âm Nó được khái niệm như sau: n+1 nếu m=0 Acker(m-1,1) nếu m ≠ 0, n=0 Acker(m,n) = Acker(m-1,… lý trong MTĐT, được gọi là cấu trúc dữ liệu (0.5 đ) + CTDL & GT đóng vai trò trọng yếu trong việc khắc phục một bài toán, ta thấy: CTDL+GT= chương trình => muốn viết được chương trình tốt ta phải có cấu trúc dữ liệu tốt và giải thuật tốt, không có CTDL, GT thì không có chương trình để khắc phục bài toán (0.5 đ) + Ví dụ: (0.5 đ) Câu 2 a) Các giá trị của p, q, r được ghi nhận trong bảng sau: p q r 1260… gian tiếp theo trong bộ nhớ lưu trữ v Là cấu trúc dữ liệu tĩnh, bị hạn chế không gian bộ nhớ lưu trữ trong thanh ghi dữ liệu và thanh ghi stack vi có hiện tượng giãn nở, dịch chuyển các phần tử khi thực hiện thao tác bổ sung phần tử, hoặc loại bỏ phần tử, do đó là số lượng phép tính trong giải thuật tăng= > độ phức tạp tính toán cũnh tăng theo b) Danh sách setup bởi con trỏ Ưu thế: – Không gây hiện tượng lãng phí . diễn dữ liệu mà theo đó dữ liệu được lưu trữ và được xử lý trong MTĐT, được gọi là cấu trúc dữ liệu (0.5 đ) + Mối quan hệ giữa cấu trúc dữ liệu và giải thuật: Giải thuật thúc đẩy trên dữ liệu. phản ánh chiến thuật “chia để trị” trong cách giải bài toán ” điều đó là đúng, nó trổ tài ở chỗ: Để giải bài toán với số lượng dữ liệu đầu vào lớn, ta giải bài toán với số lượng dữ liệu đầu vào. trong các cấu trúc để cho ra kết quả muốn. Trong lập trình, chúng quan hệ với nhau theo ràng buộc sau: Giải thuật + cấu trúc dữ liệu = chương trình (0.5 đ) + Một vài cấu trúc dữ liệu của
