zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Đề thi học phần môn cấu trúc dữ liệu

Chia sẻ: Ngocbich Bich | Ngày: | Loại File: PDF | Số trang:11

Báo xấu

31
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi dành cho hệ đại học, mời các bạn tham khảo và cùng giải bài tập này nhé

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi học phần môn cấu trúc dữ liệu

B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 1 MÔN C U TRÚC D LI U VÀ GI I THU T Th i gian: 120 phút Câu 1. Cho danh sách sinh viên. M i sinh viên ư c mô t b i các thu c tính h tên, tu i, gi i tính. 1. Hãy cài t danh sách sinh viên b i danh sách liên k t. 2. Hãy vi t th t c lo i kh i danh sách t t c các sinh viên n . Câu 2. Cho danh sách các s nguyên ư c s p x p theo th t không gi m v i danh sách ư c cài t b i m ng: 1. Hãy khai báo CTDL bi u di n dánh sách ó. 2. Hãy vi t th t c xem vào sanh sách m t s nguyên m i n sao cho danh sách nh n ư c v n còn ư c s p theo th t không gi m. Câu 3. M t m ng r ng g m 11 ô ư c ánh s t 0 ên 10 dùng lưu tr các s nguyên. Các s nguyên k ư c ưa vào m ng b i hàm băm: h(k) = (k – 3*i)%11 (i = 0,1,…) Hãy ưa các dãy s nguyên 15, 20, 6, 9, 17 vào m ng. Gi i thích t i sao chúng l i ư c ưa vào nh ng v trí ó trong m ng. Câu 4. Cho th nh hư ng sau: 1 2 6 7 3 5 4 i qua th xu t phát t nh 1. 1. Hãy ưa ra r ng các cây t o thành khi i qua th theo b r ng và danh sách các nh theo th t ã i qua. 2. Hãy ưa ra r ng các cây t o thành khi i qua th theo b sâu và danh sách các nh theo th t ã i qua.
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 2 MÔN C U TRÚC D LI U VÀ GI I THU T Th i gian: 120 phút Câu 1. (2 i m) Khoa Công ngh ư c bi u di n b i danh sách các l p. M i l p ư c bi u di n b i tên l p và danh sách sinh viên c a l p. M i sinh viên ư c bi u di n b i tên, năm sinh, gi i tính. Danh sách các l p ư c cài t b i danh sách liên k t. Hãy khai báo CTDL bi u di n Khoa Công ngh , Cho bi u di n hình h c CTDL này. Câu 2. ( 2,5 i m) Cho 2 danh sách các s nguyên ư c cài t b i danh sách liên k t. Ta c n k t h p 2 danh sách thành m t danh sách b ng cách nôi uôi danh sách th nh t t i u danh sách thw hai. Ví d , t 2 danh sách L1 và L 2, sau khi n i ta ư c L như sau: L1 L2 7 5 9 4 3 L 7 5 9 4 3 a) Khai báo CTDL bi u di n danh sách liên k t b) T 2 danh sách liên k t ( có th r ng), hãy vi t hàm k t n i 2 danh sách thành m t danh sách. Câu 3. (2,5 i m) Các giá tr khóa c a cây tìm ki m nh phân là s nguyên. Cho dãy các s nguyên: 5, 1, 6, 8, 4, 9, 7 a) Áp d ng th t c xen vào cây b t u t cây r ng, hãy xây d ng cây tìm ki m nh phân, b ng cách xem vào các nh m i có khóa l n lư t là 5, 1, 6, 8, 4, 9, 7 b) T cây ã xây d ng, hãy dưa ra dãy các khóa theo các th t : trư c, trung và sau. Câu 4. (2 i m) M i ngư i có giá tr ưu tiên là s nguyên. M i ngư i ư c bi u di n b i tên, và gi tr ưu tiên. Hàng ưu tiên ư c lưu trong m ng theo th t gi m d n c a giá tr ưu tiên. Ch ng h n, An có GTƯT là 5, Ba và Lan có GTƯT là 2 và 4 ư c lưu trong m ng sau: An Lan Ba 5 4 2 0 1 2 Max-1 a) Khai báo CTDL cài a t hàng ưu tiên b i m ng như trên b) Vi t hàm lo i ngư i có giá tr ưu tiên nh nh t. Câu 5. (1 i m) Áp d ng thu t toán s p x p n i b t cho m ng sau 9 4 7 1 3 Yêu c u: ưa ra k t qu c a t ng bư c
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 3 MÔN C U TRÚC D LI U VÀ GI I THU T Th i gian: 120 phút Câu 1. Cho danh sách tên c a m i l p. M i sinh viên ư c bi u di n b i 2 trư ng: ten, diem. Danh sách ư c cài t b i danh sách liên k t. 1. Hãy khai báo CTDL cài t danh sách ó. 2. Vi t th t c tính i m trung bình c a l p ó. 3. Vi t th t c lo i kh i danh sách t t c sinh viên có i m b ng p cho trư c. Câu 2. Cho m t cây, m i nh có t i a K nh con. Thông tin ch a trong m i nh là s th c. Cây ư c cài t cách ch ra danh sách các con c a m i nh và s d ng con tr . 1. Khai báo CTDL cài t cây b ng cách trên. 2. Vi t th t c i qua cây theo sâu ( quy ho c không quy) tính t ng các s th c lưu trong các nh c a cây. Câu 3. Cho b ng băm óng g m 11 thành ph n. Các giá tr khóa là các s nguyên và ư c ưa vào b ng b i hàm băm: h(x) = x%11. Va ch m ư c gi i quy t b ng cách băm l i bình phương. T b ng băm r ng, s d ng t i a 3 l n bă l i, hãy ưa ra b ng băm k t qu khi th c hi n các hành ng sau: 1. Xen vào 5099, 23,, 213, ,36, 300, 19, 283. 2. Lo i 300, 36 r i xen vào 146, 360, 480. Yêu c u: c n gi i thích t i sao nh n ư c k t qu như th . Câu 4. Trình bày tư tư ng c a thu t toán PRIM tìm cây bao trùm ng n nh t c a th vô hư ng liên thông có tr ng s . Mô t thu t toán này. Áp dung thu t toán tìm cây bao trùm ng n nh t c th sau A 7 2 2 1 C D B 3 6 4 4 9 F E 6 Yêu c u: C n ph i tìm ra k t qu c a m i bư c và gi i thích.
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com THI 4 CTDL VÀ GI I THU T Cho K46CA, CB,CC (Th i gian: 120 phút) Câu 1. (3 i m) Ki u d li u tr u tư ng ư c xác nh như sau: • Các i tư ng DL là các danh sách s nguyên ư c s p x p theo th t không gi m. • Các phép toán g m: 1. Tìm xem danh sách có ch a s nguyên cho trư c không? 2. Xen m t s nguyên m i vào danh sách sao cho sau khi xen, danh sách v n còn ư c s p 3. K t h p 2 danh sách ư c s p thành m t danh sách ư c s p. Danh sách ư c cài t b ng danh sách liên k t. a) Hãy vi t file u ch a mô t CTDL và các prototype c a các hàm th c hi n các phép toán trên (V i m i hàm c n vi t ra các i u ki n trư c và i u ki n sau) b) Hãy cài t hàm xen vào. Câu 2. (2 i m) Gi s các i tư ng khác nhau có giá tr ưu tiên khác nhau và hàng ưu tiên ư c cài t b i cây tìm ki m nh phân v i khóa tìm ki m là giá tr ưu tiên. a) Hãy mô t CTDL bi u di n hangf ưu tiên trong cáhc cài t trên b) Hãy vi t hàm lo i i t ong có giái tr ưu tiên nh nh t kh i hàng ưu tiên. Câu 3. (2,5 i m) a) Hãy mô t CTDL bi u di n b ng băm dây chuy n và vi t hàm xem vào b ng băm này theo hàm băm ã cho. b) Gi s c c a b ng là 5, các giá tr khóa là các s nguyên không âm. Và hàm băm là hàm chua l y ph n sư. Áp d ng hàm xen vào, t b ng băm day chuy n r ng, hãy â vào các d li u v i khóa 9,12,31,217,5.42,16. Cho bi u di n hình h c b ng băm k t qu . Câu 4. (1,5 i m) a) Hãy trình bày tư tư ng c u thu t toán i qua th theo b r ng và theo sâu. b) Cho th nh hư ng trong hình v sau: c) Hãy ưa ra th t các nh ư c thưm theo b r ng và sâu khi xu t phát t nh A. A C E B D H G F Câu 5. (1 i m) Gi s các xâu ư c t o thành t 2 lý t A vàB. S d ng ccs phép toán ngăn x p, hãy vi t hàm cho bi t m t xâu có d ng AnBn (n>=0) hay không?
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com 4 (K46) Câu1 . a. ct //DL.h // Gi i thích v l p #ifndef _DL_H_ #define _DL_H_ #include class node { int data; node * next; node(int x) { data = x; next = NULL; }; } class DL { public : DL() // Kh i t o danh sách r ng // Precondition // Postcondition {Head = NULL ; Tail = NULL; length = 0}; DL(const DL & _dl); // Hàm ki n t o copy // // ~ DL(); // Hàm h y // // DL& operator = (const DL & _dl); // Toán t gán // //
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com bool Empty() const ; // Xác nh xem danh sách có r ng kô // Precondition : // Postcondition: Tr v true n u danh sách r ng int Length() const; // bool IsExist(int x); // Ki m tra xem danh sách có ch a s nguyên x kô // Precondition : danh sách khác r ng // Postcondition : tr v true……. void Insert(int x); // // // friend DL& KetHop(const DL& dl1 , const DL& dl2); // // // private : node * Head; node * Tail; int length; } #endif b.Cài t void DL :: Insert (int x) { node * Q = new node(x); if (Empty()) { Head = Q ; Tail = Q; length = 1; } node * Pre , P ; Pre = P = Head; While (Pre != Tail)
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com { if ( x data ) break; Pre = P; P = P->next; } if (P == Head) // Chèn vào u { Q -> next = Head; Head = Q; } else if (P == NULL) // Chèn vào cu i { Pre ->next = Q; } else //Chèn vào gi a { Q ->next = P; Pre ->next = Q; } } Câu 2 a.Mô t //HUT.h // Gi i thích v l p #ifndef _ HUT _H_ #define _ HUT _H_ #include template class node { item data; int key; node(const & item _data , const int & _key) { data = _data ; key = _key; }; friend class HUT; } template class HUT
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com { public : static const int SIZE = 1000; HUT() // Kh i t o danh sách r ng // Precondition // Postcondition HUT (const HUT & _dl); // Hàm ki n t o copy // // HUT (node * _element , int n) // Xây d ng hàng ưu tiên t n ph n t lưu trong m ng _element ~ HUT (); // Hàm h y // // HUT & operator = (const HUT & _dl); // Toán t gán // // bool Empty() const ; // Xác nh xem danh sách có r ng kô // Precondition : // Postcondition: Tr v true n u danh sách r ng int Length() const; // void Insert(node _data); // // // node & FindMin() const; // // // node & DeleteMin();
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com // Lo i i tư ng có ưu tiên nh nh t // // Tr v i tư ng có ưu tiên nh nh t private : node element[SIZE]; int last; void ShiftDown(int i); // y d li u trong nh i xu ng v trí thích h p // // } #endif b.Cài t template node& HUT :: DeleteMin() { assert(last >= 0); element[0] = element[last]; ShiftDown(0); } Câu 3 a1.Mô t //ChainHash.h // Gi i thích v l p #ifndef _ ChainHash _H_ #define _ ChainHash _H_ #include typedef int keyType; template class ChainHash { public : static const int SIZE = 1000; ChainHash () // Kh i t o danh sách r ng // Precondition
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com // Postcondition ChainHash (const ChainHash & _dl); // Hàm ki n t o copy // // ~ ChainHash (); // Hàm h y // // ChainHash & operator = (const ChainHash & _dl); // Toán t gán // // bool Search(keyType k , Item & I) const; // // // void Insert(const item & _data); // // // void & Delete (keyType k); // Lo i i tư ng có ưu tiên nh nh t // // Tr v i tư ng có ưu tiên nh nh t private : struct CELL { item data; CELL * next; } CELL element[SIZE]; } #endif a2.Cài t template void ChainHash:: Insert (const item & _data)
B n quy n tài li u thu c v di n àn http://sinhviennganhang.com { i = Hash(_data); ………………. } b. V hình Hàng 0 : 5 Hàng 1 : 31 -> 16 Hàng 2 : 12 -> 217 -> 42 Hàng 3 : Hàng 4 : 9 Câu 4 : a. Theo chi u r ng : A , B , C , G , D , F b. Theo chi u sâu : A , B , G , D , F , C Câu 5 : Gi ng bài thi Toán r i r c v a thi Chúc m i ngư i thi t t

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.