ĐỀ THI CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

     
Đề thi và đáp án cấu tạo dữ liệu và lời giải kì 1 năm học 2012-2013 – UET – tài liệu VNU 8 70 1


Bạn đang xem: đề thi cấu trúc dữ liệu và giải thuật

Đại Học công nghệ Thông Tin. Đại học tập Thái Nguyên. Đề 1 Câu 1( 2 điểm) chũm nào là giải thuật; cấu tạo dữ liệu, quan hệ giữa chúng? Hãy nêu một vài kết cấu dữ liệu tiền định của ngôn từ lập trình mà anh (chị) biết? Câu 2( 5 điểm ) trả sử cần quản lý một lớp học bao hàm các sinh viên. Mỗi sinh viên gồm những 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 cài đặt danh sách này bằng cấu trúc danh sách links đơn, 2) Với cấu tạo danh sách đã cài đặt đặt, viết những chương trình con triển khai các yêu ước như sau: a) Nhập vào danh sách gồm n sv b) đào thải khỏi danh sách những sinh viên bao gồm điểm mức độ vừa phải n, mỗi lần lặp nhập 1 sinh viên cùng gắn vào danh sách: for i:=1 lớn n do begin - new(M); yêu mong MT cấp phát ô nhớ chứa dữ liệu của sinh viên bắt buộc nhập - Nhập các thông tin về sinh viên, lưu vào ô nhớ được trỏ bởi vì M - kết nối ô lưu giữ được trỏ do M vào danh sách end; 2) sa thải những SV tất cả điểm vừa phải q vày p:= p^.next; c) các loại bỏ thành phần ở địa điểm q: p^.next := q^.next; dispose(q); q:= p^.next;// lưu vị trí tiếp sau vị trí sa thải để còn sa thải tiếp 3) bố trí danh sách theo trường lớp tăng nhiều (1 đ) có thể sử dụng một trong số thuật toán bố trí để sắp xếp dữ liệu trên danh sách liên kết, tại chỗ nà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 côn trùng liên kết của những nút trong danh sách và thiến nội dung của những nút: Giải thuật: Procedure ListSelection_Sort(var L: List) Var p, q, min: List; Begin p:=L; While (pnil) vày Begin q:=p^.next; min:=p; While (qnil) bởi Begin If (q^.infor nil) vày Begin Write(M^. Hoten); Write(M^. Lop); Write(M^. Sbd); P:=M; M := M^.next; If (M^.lopp^.lop) then writeln(‘Các sinh vien lop M^.lop la:’); End; Câu 3 Ưu điểm: (0.5 đ) - không khiến hiện tượng lãng phí bộ nhớ lưu trữ (Hiện tượng giữ vị trí để đấy mà không dùng đến như danh sách thiết lập bởi mảng) - cấu trúc dữ liệu danh sách thiết lập bởi nhỏ trỏ còn gọi là cấu tạo dũ liệu động, ko gian bộ nhớ lưu trữ được cấp phép trong heap, do đó nó không trở nên giới hạn bởi size 64kb như đối với kết cấu dữ liệu tĩnh - Các bộ phận trong danh sách nằm ở vị trí những địa chỉ dải dác, cho nên vì vậy tận dụng được những không gian trống này, nhưng mà không đề xuất một vùng nhớ sau đó như cài đặt bởi mảng Nhược điểm: (0.5 đ) - tốc độ truy cập đến các thành phần trong list là chậm, không đồng đều so với mọi thành phần (truy cập tuần trường đoản cú một chiều) - Từ phần tử sau không truy vấn ngược mang đến các bộ phận đứng trước nó được - mỗi phần tử trong list tốn thêm 1 ô nhớ có kích cỡ là 4byte để lưu địa chỉ của bộ phận đứng sau nó trong danh sách Đề 2 Câu 1( 3 điểm) 1) thay nào là cấu trúc dữ liệu chi phí định (định sẵn ) của ngữ điệu lập trình bậc cao? 2) Hãy nêu một vài cấu tạo dữ liệu tiền định của ngôn ngữ lập trình nhưng anh (chị ) biết? 3) tại sao chỉ áp dụng các kết cấu dữ liệu tiền định không đủ đáp ứng yêu ước về việc tổ chức, tàng trữ dữ liệu của mọi vấn đề ứng dụng thực tiễn ?. Một vài bài toán áp dụng phải cần sử dụng đến các cấu tạo dữ liệu do bạn lập trình từ định nghĩa? Hãy nêu một bài bác toán áp dụng như vậy, phân tích việc để diễn tả điều đó? Câu 2( 3 điểm ) giả sử ta cần làm chủ một chống xếp chứa các số nguyên. Viết dạng cài đặt của cấu tạo ngăn xếp này bởi mảng. Với kết cấu ngăn xếp vừa tải đặt, hãy viết giấy tờ thủ tục thêm bộ phận x vào địa chỉ thứ k đề cập tử đỉnh phòng xếp làm sao để cho các thành phần khác không đổi khác thứ tự (k là số nguyên nhập tự bàn phím). Câu 3( 2 điểm ) Anh ( Chị ) hãy nêu một lớp vấn đề mà sử dụng cấu tạo ngăn xếp rất thích hợp cho việc giải quyết và xử lý các yêu cầu của việc ? phân tích vấn đề đã nêu để biểu hiện rõ điều đó? Câu 1 1) kết cấu dữ liệu tiền định của ngôn từ lập trình bậc cao là các kết cấu dữ liệu đã được khái niệm sẵn trong ngữ điệu lập trình đó, fan lập trình chỉ việc thực hiện mà không nên định nghĩa lại (1 đ) 3) Một vài cấu tạo dữ liệu chi phí định như: mảng, bản ghi, tệp tin, (1 đ) 2) Các kết cấu dữ liệu chi phí định có sẵn trong ngôn từ lập trình không đáp ứng một cách đầy đủ được nhu yếu lưu trữ tài liệu lớn của gần như chương trình, không phản ánh đầy đủ thực chất của các đối tượng người sử dụng dữ liệu có trong thực tế = > người ta đề xuất đến các cấu tạo dữ liệu do fan lập trình từ định nghĩa. (0.5 đ) Ví dụ: Xét bài bác toán cai quản hồ sơ sv trong một khoa, các yêu cầu thống trị hồ sơ là: Thêm, sửa, xóa, tra cứu kiếm, … hồ sơ.=> Sử dụng cấu trúc dữ liệu mảng (cấu trúc chi phí định)để lưu những thông tin về hồ sơ là không phù hợp vì: cấu trúc mảng không có thể chấp nhận được thực hiện phép toán thêm, xóa, không gian không đủ nhằm 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 thiết lập 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 thành phần x vào ngăn xếp S ở trong phần thứ k tính từ bỏ đỉnh ngăn xếp: (2 đ) đánh giá xem phòng xếp có rỗng không, nểu trống rỗng thì cung ứng đỉnh ngăn xếp, Nếu phòng xếp không rỗng: khám nghiệm xem số k nhập vào tất cả > đứng top hay không? nếu như lớn hơn thế thì thêm x vào đỉnh ngăn xếp, nếu như không: lấy (top-k+1) thành phần kể từ trên đầu ngăn xếp ra một chống xếp phụ, thêm thành phần phần tử x vào phòng xếp, đổ ( đứng top – k+1) phần tử từ phòng xếp phụ vào ngăn xếp lúc đầu do đó đảm bảo an toàn không chuyển đổi trật từ bỏ các bộ phận trong ngăn xếp lúc đầu sau khi một số loại bỏ phần tử ở địa điểm k.(thủ tục tương ứng tự viết) Câu 3 (1 đ) - kết cấu ngăn xếp hay được áp dụng cho những vấn đề có trình tự truy xuất ngược cùng với trình tự lưu lại trữ. Ví dụ: + bài bác toán đổi khác cơ số, tìm mong số tầm thường của hai số nguyên, vấn đề tính cực hiếm biểu thức, + Thường áp dụng trong một vài bài toán tìm đường đi trong triết lý đồ thị (lưu vết đường đi) + làm môi trường thiên nhiên lưu trữ các biến toàn thể và toàn bộ của những thủ tục trong chương trình dịch của ngôn từ lập trình. (1 đ) - Phân tích biện pháp giải các bài toán bên trên để biểu đạt rõ điều đã nêu Đề 3 Câu 1( 2 điểm) Có bạn nói: “Phép đệ quy phản nghịch ánh chiến thuật “chia để trị” trong biện pháp giải bài toán ”. Điều đó có đúng không ? anh (chị ) hãy giải thích và đến ví dụ minh họa cho điều đó ? Câu 2( 3 điểm ) giả sử cần cai quản một cây chứa những số nguyên, các đỉnh bên trên cây được khắc số theo một sản phẩm tự nào đó. Hãy viết dạng thiết đặt cây bằng cha của mỗi đỉnh sử dụng mảng. Cù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ừ bỏ bàn phím) Câu 3( 3 điểm ) cho một cây thư mục T và kích cỡ của từng thư mục bé trong laptop như sau: Anh(chị) hãy: 1) Viết dạng cài đặt cây bằng con trưởng cùng em tiếp giáp của từng đỉnh, sử dụng con trỏ 2) Để tính tổng kích thước của toàn cục cây thư mục trên thì ta chăm chú cây theo đồ vật tự nào? 3) mô tả cách tính tổng size 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 làm phản ánh giải pháp “chia để trị” trong bí quyết giải việc ” điều ấy là đúng, nó biểu thị ở chỗ: Để giải câu hỏi với số lượng dữ liệu đầu vào lớn, ta giải việc với con số dữ liệu đầu vào nhỏ tuổi hơn, và nhỏ tuổi hơn nữa, cứ thế call đệ quy cho tới gọi đến trường hợp bài toán xảy ra suy vươn lên là (trường đúng theo này câu hỏi được xử lý).

Xem thêm: Thông Tin Tuyển Sinh Khoa Quốc Tế (Đại Học Thái Nguyên), Khoa Quốc Tế (Đại Học Thái Nguyên)



Xem thêm: Khí Hậu Châu Phi Nóng Quanh Năm Vì, Châu Phi Có Khí Hậu Nóng Do

Đây chính là tư tưởng của chiến thuật chia nhằm trị (1 đ) + Ví dụ: (1 đ) Chạy chậm rãi một giải mã đệ quy, lấy ví dụ như 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 cài đặt cây bằng phụ thân 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 phụ vương của đỉnh trang bị k: (1 đ) parent (T, k) := T.parent; + Tìm con cả của đỉnh sản phẩm công nghệ k trên cây T (1 đ) Duyệt các đỉnh trên cây T, khởi đầu từ đỉnh gốc(i:=1), khám nghiệm xem cha của đỉnh i bao gồm = k không, giả dụ = k, kết luận i là con cả, ngừng giải thuật, nếu phụ vương của i k thì phê chuẩn đỉnh tiếp sau trên cây T bằng cách cho i:= i+1. Lặp đi tái diễn phép duyệt những đỉnh bên trên T cho tới khi tra cứu thấy thì giới hạn (found = true), hoặc phê duyệt hết những đỉnh bên trên T (i>n cùng với n là số đỉnh bên trên cây) thì cũng dừng và tóm lại không tim thấy Câu 3 + Dạng thiết lập cây bằng con trưởng cùng em gần kề của từng đỉnh: (1 đ) Type Tree = ^Nut; Nut = record Tenthumuc: string; Kichco:integer; EldestChild, Nextsibling:Tree; End; Var T: Tree; + coi ngó cây theo thứ tự sau để xác minh tổng kích cỡ của cây thư mục (1 đ) + mô tả cách tính tổng size cây folder T trên: (1 đ) - Biến: tong:= 0; tong lưu tổng kích thước toàn thể 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 (Cnil) vị 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 điểm lưu ý của giải thuật đệ quy. Hàm đệ quy (viết bằng ngôn ngữ pascal) tiếp sau đây cho hiệu quả là gì? lý giải tại 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 ) đưa sử một đơn vị cần cai quản các cán bộ, từng cán cỗ cần quản lý các ở trong tính sau: họ tên, năm sinh, giới tính, địa chỉ, trình độ, chức danh . Anh(chị) nên lựa chọn một cấu trúc dữ liệu để quản lý các thông tin của những cán cỗ trong đơn vị chức năng đó, sao cho: - dữ liệu được lưu lại trong bộ nhớ lưu trữ trong - dễ dãi cho các phép toán: thêm, xóa cán cỗ - tiết kiệm ngân sách không gian bộ nhớ lưu trữ nhất. Với cấu tạo dữ liệu nhưng anh(chị) đang lựa chọn. Anh(chị) hãy: 1) Viết dạng thiết lập của kết cấu dữ liệu kia 2) Viết lời giải đếm số lượng cán bộ trong đơn vị 3) Hiển thị thông tin của những cán cỗ trong đơn vị 4) sa thải những tín đồ đế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 thiết lập danh sách vì mảng, vày danh sách liên kết đơn? ưu nhược điểm của từng dạng tải đặt? Câu 1 + Ba điểm lưu ý của lời giải đệ quy: ( 1 đ) - Trong giải thuật đệ quy bao giờ cũng tất cả lời gọi đến chính nó - Sau từng lời hotline đệ quy, kích cỡ của vấn đề được thu nhỏ dại hơn trước - bao gồm một trường hợp suy biến: việc được xử lý theo một cách khác hẳn và giải mã cũng chấm dứt + hiệu quả của hàm đệ quy là: x*n!, vì: ( 1 đ) n = 1 cho công dụng là: 1*x n = 2 cho kết quả là: 1*2*x n = 3 cho tác dụng là: 1*2*3*x n = n cho hiệu quả là: 1*2*3* *n*x = n! * x Câu 2 1) cấu trúc dữ liệu chọn lọc là danh sách link đơn ( 1 đ) Dạng thiết lập Type Canbo = record Hoten: String; Năm sinh : integer; Giớitinh: boolean; Diachi, trinhdo, chucdang: string; ` Next: ^ Canbo; end; các mục = ^Canbo; Var L: List; 2) Đếm số lượng cán bộ trong trong danh sách ( 1 đ) - thực hiện biến đếm lưu con số cán cỗ trong đối chọi vị, ban sơ dem:= 0 , - áp 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 trở thành đếm lên 1: - In biến đổi đếm ra screen 3) Hiển thị các cán cỗ trong 1-1 vị: ( 1 đ) sử dụng con trỏ phụ M duyệt từ trên đầu đến cuối danh sách, duyệt mang lại cán bộ nào thì hiển thị những thông tin của cán bộ đó lên màn hình: 4) sa thải các cán bộ đến tuổi về hưu trong 1-1 vị: ( 1 đ) biện pháp làm: b1) tra cứu cán bộ trước tiên trong danh sách đến tuổi về hưu, giả sử địa chỉ được trỏ bởi p b2) thải trừ cán bộ tại phần p b3) Lặp đi lặp lại b1); b2) cho tới khi hết địa điểm tìm thấy Chú ý: - nhằm tìm cán bộ thỏa mãn điều khiếu nại ta duyệt từ trên đầu danh sách p:=L đến lúc tìm thấy thì ngừng - để vứt bỏ học sinh tại phần p: a) dịch rời con trỏ phụ M mang đến vị trí trước p:  M:=L;  While M^.next p do M:=M^.next; b) Bứt liên kết, gắn liên kết, giải hòa p:  M^.next:=p^.next;  Dispose(p); Câu 3 <...>... Nhớ, là cấu tạo tĩnh Đề xuất kết cấu thích vừa lòng hơn: kết cấu danh sách links vì: tự khắc phục những hạn chế của danh sách thiết đặt như bên trên Đề 9 Câu 1( 2 điểm) cầm nào là cấu tạo dữ liệu với giải thuật? cấu tạo dữ liệu và giải thuật đóng vai trò ra làm sao trong vượt trình xử lý một bài toán tin học? Anh (Chị) hãy lấy một lấy ví dụ như minh họa mang lại đ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 sản phẩm công nghệ tự được viết số như bên trên Câu 1 + Giải thuật là một trong những dãy các câu lệnh ngặt nghèo và rõ ràng, xác minh một dãy các thao tác làm việc trên một số đối tượng nào (dữ liệu) đó làm sao để cho sau một vài hữu hạn bước triển khai ta đạt được công dụng mong muốn (0.5 đ) + phương thức tổ chức biểu diễn tài liệu mà theo đó dữ liệu được lưu trữ và được xử trí trong MTĐT, được điện thoại tư vấn là cấu tạo dữ liệu (0.5 đ) +... Vày mảng) - kết cấu dữ liệu danh sách cài đặt bởi con trỏ có cách gọi khác là cấu tạo dũ liệu động, ko gian bộ lưu trữ được cấp phép trong heap, cho nên vì thế nó không trở nên giới hạn bởi form size 64kb như đối với cấu tạo dữ liệu tĩnh - Các phần tử trong danh sách nằm tại những địa điểm dải dác, cho nên vì thế tận dụng được những không khí trống này, nhưng mà không yêu cầu một vùng nhớ tiếp đến như cài đặt bởi mảng Nhược điểm: - tốc độ truy... Vừa phải = (toan+ly+hoa+ngoaingu)/4) - kiếm tìm kiếm sỹ tử theo số báo danh nhập vào Câu 1 + Đệ quy: Một đối tượng người tiêu dùng được call là đệ quy ví như nó bao gồm chính nó như là một thành phần hoặc nó được quan niệm dưới dạng của chính nó (0.5 đ) + giải thuật đệ quy: là lời giải có chứa giải thuật đệ quy lời giải đệ quy là lời giải của bài toán T được triển khai bởi giải mã của bài toán T’ có dạng như T (cỡ của T’cấu trúc tài liệu danh sách link đơn nhằm lưu trữ những thông tin của những thí sinh tham dự cuộc thi Viết dạng thiết đặt tương ứng của cấu trúc trên 2 Xây dựng các chương trình con triển khai các trọng trách sau: - Nhập thông tin về các thí sinh tham gia dự thi (điều kiện ngừng là nhập SBD = rỗng) - Hiển thị các thí sinh dự thi theo lớp - sa thải các thí sinh có điểm trung bình cấu tạo dữ liệu danh sách links đơn nhằm lưu trữ những thông tin của những thí sinh tham dự cuộc thi Viết dạng cài đặt tương ứng của kết cấu trên 4 Xây dựng những chương trình con thực hiện các trọng trách sau: - Nhập tin tức về các thí sinh tham dự cuộc thi (điều kiện giới hạn 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 chi phí tố, giữ vết lối đi trên vật thị, khử đệ quy, (0.5 đ) - Phân tích bài toán : (0.5 đ) Đề 7 Câu 1( 1 điểm) Nêu định nghĩa đệ quy, giải mã đệ quy, đến ví dụ về một lời giải đệ quy? Câu 2( 3 điểm ) Hàm Ackermann là hàm hai đối số với mức giá trị của đối số là số nguyên ko âm Nó được định nghĩa như sau: n+1 giả dụ m=0 Acker(m-1,1) ví như m ≠ 0, n=0 Acker(m,n) = Acker(m-1,... Lý trong MTĐT, được hotline là cấu tạo dữ liệu (0.5 đ) + CTDL và GT đóng vai trò quan trọng đặc biệt trong việc giải quyết một bài toán, ta thấy: CTDL+GT= chương trình => ý muốn viết được chương trình giỏi ta buộc phải có cấu tạo dữ liệu xuất sắc và lời giải tốt, không có CTDL, GT thì không có chương trình để xử lý 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 dấn trong bảng sau: p. Q r 1260... Gian tiếp nối trong bộ nhớ v Là kết cấu dữ liệu tĩnh, bị số lượng giới hạn không gian bộ lưu trữ trong thanh ghi tài liệu và thanh ghi stack vi có hiện tượng lạ co giãn, dịch chuyển các bộ phận khi tiến hành thao tác bổ sung cập nhật phần tử, hoặc đào thải phần tử, do đó là con số phép tính trong giải thuật tăng= > độ phức tạp đo lường và thống kê cũnh tăng theo b) Danh sách setup bởi nhỏ trỏ Ưu điểm: - không khiến hiện tượng tiêu tốn 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à kết cấu dữ liệu (0.5 đ) + mối quan hệ giữa cấu tạo dữ liệu và giải thuật: Giải thuật tác động trên dữ liệu. Bội phản ánh chiến thuật “chia để trị” trong biện pháp giải câu hỏi ” điều đó là đúng, nó trình bày ở chỗ: Để giải bài toán với số lượng dữ liệu đầu vào lớn, ta giải việc với con số dữ liệu đầu vào. Trong các cấu tạo để mang lại ra hiệu quả mong muốn. Trong lập trình, bọn chúng quan hệ cùng nhau theo ràng buộc sau: lời giải + kết cấu dữ liệu = chương trình (0.5 đ) + Một vài kết cấu dữ liệu của