TRƯỜNG ĐẠI HỌC GIAO THÔNG VẬN TẢI

THÀNH PHỐ HỒ CHÍ MINH ĐỀ THI KẾT THÚC HỌC PHẦN

Tên học phần: Cấu trúc dữ liệu và giải
thuật
Mã đề thi : 001 Mã học phần : 124002 Số TC : 3
Họ và tên SV Nguyễn Hữu Thời gian : 90’ Hệ : Đại học
Chí
Mã sinh viên : Trưởng BM : Nguyễn Văn Huy
082205010502
Chữ ký :

Bài 1
History.h
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

#pragma once
class History
{
private:
vector<string> history;
int current_index;
unordered_map<string, int> visit_counts;
public:
History();
~History();
void visit(const string& url);
string back();
string forward();
void listHistory();
void clearHistory();
void printVisitCounts();
};

[Link]
#include "History.h"
using namespace std;

History::History() : current_index(-1) {}
History::~History(){}
void History::visit(const string& url) {
if (current_index != [Link]() - 1) {
[Link]([Link]() + current_index + 1, [Link]());
}
 history.push_back(url);
current_index++;
if (visit_counts.find(url) != visit_counts.end()) {
visit_counts[url]++;
}
else {
visit_counts[url] = 1;
}
}

string History::back() {
if (current_index > 0) {
current_index--;
}
return history[current_index];
}

string History::forward() {
if (current_index < [Link]() - 1) {
current_index++;
}
return history[current_index];
}

void History::listHistory() {
for (const auto& url : history) {
cout << url << endl;
}
}

void History::clearHistory() {
[Link]();
visit_counts.clear();
current_index = -1;
}

void History::printVisitCounts() {
for (const auto& entry : visit_counts) {
cout << [Link] << ": " << [Link] << " lan" << endl;
}
}

[Link]
#include <iostream>
#include "History.h"

using namespace std;

int main() {
History H;
int choice;
string u;

do {
cout << "<= => () Lich su |ten website_________________|" << endl;
cout << "Moi ban chon chuc nang: " << endl;
 cout << "0. Nhap dia chi website can truy cap\n"
<< "1. Back\n"
<< "2. Forward\n"
<< "3. So website da mo\n"
<< "4. Xoa lich su website da vao\n"
<< "5. So lan vao cua website\n"
<< "6. Thoat\n";
cout << "Nhap lua chon cua ban: ";
cin >> choice;

switch (choice) {
case 0:
cout << "Nhap ten website de truy cap: ";
cin >> u;
[Link](u);
break;
case 1:
u = [Link]();
if (u == "") {
cout << "Khong co trang truoc!" << endl;
}
else {
cout << "Trang hien tai: " << u << endl;
}
break;
case 2:
u = [Link]();
if (u == "") {
cout << "Khong co trang sau!" << endl;
}
else {
cout << "Trang hien tai: " << u << endl;
}
break;
case 3:
cout << "Cac website da mo:" << endl;
[Link]();
break;
case 4:
[Link]();
cout << "Lich su da duoc xoa." << endl;
break;
case 5:
cout << "So lan vao cua tung website:" << endl;
[Link]();
break;
case 6:
cout << "Thoat chuong trinh." << endl;
break;
default:
cout << "Lua chon khong hop le. Vui long thu lai." << endl;
break;
}

} while (choice != 6);

return 0;
}
Bài 2

.h
#pragma
#include <iostream>
#include <ctime>
#include <string>
#include<vector>
using namespace std;
struct ThoiDiem {
time_t thoiDiemVao;
time_t thoiDiemRa;
};

struct Node {
string bienSoXe;
ThoiDiem thoiDiem;
Node* left;
Node* right;
int height;
};

class AVLTree {
private:
Node* root;

Node* newNode(const string& bienSoXe, time_t thoiDiemVao);

int height(Node* node);
int balanceFactor(Node* node);
Node* rotateRight(Node* y);
Node* rotateLeft(Node* x);
Node* insert(Node* node, const string& bienSoXe, time_t thoiDiemVao);
Node* minValueNode(Node* node);
Node* deleteNode(Node* node, const string& bienSoXe);
void inorderHelper(Node* node, vector<string>& result, time_t thoiDiemBatDau, time_t
thoiDiemKetThuc);
void countNodes(Node* node, time_t ngay, int& count);

public:
AVLTree();
void xeVao(const string& bienSoXe);
void xeRa(const string& bienSoXe);
void xoaThongTinXe(const string& bienSoXe);
vector<string> danhSachXeTrongKhoangThoiGian(time_t thoiDiemBatDau, time_t
thoiDiemKetThuc);
int thongKeLuotXeVaoTrongNgay(time_t ngay);
};

.cpp
#include "QuanLyBaiDoXe.h"

AVLTree::AVLTree() : root(nullptr) {}

AVLTree::~AVLTree() {
xoaCay(root);
}

void AVLTree::xeVao(string bienSoXe, time_t thoiDiemVao) {

root = chenNode(root, bienSoXe, thoiDiemVao);
}

void AVLTree::xeRa(string bienSoXe, time_t thoiDiemRa) {

Node* node = timNode(bienSoXe);
if (node) {
node->thoiDiemRa = thoiDiemRa;
}
}

void AVLTree::xoaThongTinXe(string bienSoXe) {

root = timNodeXoa(root, bienSoXe);
}

vector<string> AVLTree::danhSachXeTrongKhoangThoiGian(time_t thoiDiemBatDau, time_t

thoiDiemKetThuc) {
vector<string> danhSach;
danhSachXeTrongKhoangThoiGian(root, thoiDiemBatDau, thoiDiemKetThuc, danhSach);
return danhSach;
}

int AVLTree::thongKeLuotXeVaoTrongNgay(time_t ngay) {

int count = 0;
thongKeLuotXeVaoTrongNgay(root, ngay, count);
return count;
}

Node* AVLTree::xoayPhai(Node* y) {
Node* x = y->left;
Node* T2 = x->right;

x->right = y;
y->left = T2;

y->height = max(chieuCao(y->left), chieuCao(y->right)) + 1;

x->height = max(chieuCao(x->left), chieuCao(x->right)) + 1;

return x;
}

Node* AVLTree::xoayTrai(Node* x) {
Node* y = x->right;
Node* T2 = y->left;

y->left = x;
x->right = T2;

x->height = max(chieuCao(x->left), chieuCao(x->right)) + 1;

y->height = max(chieuCao(y->left), chieuCao(y->right)) + 1;
 return y;
}

int AVLTree::chieuCao(Node* node) {

if (node == nullptr)
return 0;
return node->height;
}

int AVLTree::chenhLechCao(Node* node) {

if (node == nullptr)
return 0;
return chieuCao(node->left) - chieuCao(node->right);
}

Node* AVLTree::chenNode(Node* node, string bienSoXe, time_t thoiDiemVao) {

if (node == nullptr)
return new Node(bienSoXe, thoiDiemVao);

if (bienSoXe < node->bienSoXe)

node->left = chenNode(node->left, bienSoXe, thoiDiemVao);
else if (bienSoXe > node->bienSoXe)
node->right = chenNode(node->right, bienSoXe, thoiDiemVao);
else
node->thoiDiemVao = thoiDiemVao;

node->height = 1 + max(chieuCao(node->left), chieuCao(node->right));

int balance = chenhLechCao(node);

if (balance > 1 && bienSoXe < node->left->bienSoXe)

return xoayPhai(node);

if (balance > 1 && bienSoXe > node->left->bienSoXe) {

node->left = xoayTrai(node->left);
return xoayPhai(node);
}

if (balance < -1 && bienSoXe > node->right->bienSoXe)

return xoayTrai(node);

if (balance < -1 && bienSoXe < node->right->bienSoXe) {

node->right = xoayPhai(node->right);
return xoayTrai(node);
}

return node;
}

Node* AVLTree::timNodeXoa(Node* node, string bienSoXe) {

if (node == nullptr)
return node;

if (bienSoXe < node->bienSoXe)

node->left = timNodeXoa(node->left, bienSoXe);
else if (bienSoXe > node->bienSoXe)
node->right = timNodeXoa(node->right, bienSoXe);
 else {
if (node->left == nullptr || node->right == nullptr) {
Node* temp = node->left ? node->left : node->right;

if (temp == nullptr) {
temp = node;
node = nullptr;
}
else
*node = *temp;
delete temp;
}
else {
Node* temp = node->right;
while (temp->left != nullptr)
temp = temp->left;

node->bienSoXe = temp->bienSoXe;
node->thoiDiemVao = temp->thoiDiemVao;
node->right = timNodeXoa(node->right, temp->bienSoXe);
}
}

if (node == nullptr)
return node;

node->height = 1 + max(chieuCao(node->left), chieuCao(node->right));

int balance = chenhLechCao(node);

if (balance > 1 && chenhLechCao(node->left) >= 0)

return xoayPhai(node);

if (balance > 1 && chenhLechCao(node->left) < 0) {

node->left = xoayTrai(node->left);
return xoayPhai(node);
}

if (balance < -1 && chenhLechCao(node->right) <= 0)

return xoayTrai(node);

if (balance < -1 && chenhLechCao(node->right) > 0) {

node->right = xoayPhai(node->right);
return xoayTrai(node);
}

return node;
}

Node* AVLTree::timNode(string bienSoXe) {

Node* current = root;
while (current != nullptr) {
if (bienSoXe == current->bienSoXe)
return current;
else if (bienSoXe < current->bienSoXe)
current = current->left;
else
current = current->right;
 }
return nullptr;
}

void AVLTree::xoaCay(Node* node) {

if (node == nullptr)
return;
xoaCay(node->left);
xoaCay(node->right);
delete node;
}

void AVLTree::danhSachXeTrongKhoangThoiGian(Node* node, time_t thoiDiemBatDau, time_t

thoiDiemKetThuc, vector<string>& danhSach) {
if (node == nullptr)
return;

if (node->thoiDiemVao >= thoiDiemBatDau && node->thoiDiemVao <= thoiDiemKetThuc)

danhSach.push_back(node->bienSoXe);

if (thoiDiemKetThuc < node->thoiDiemVao)

danhSachXeTrongKhoangThoiGian(node->left, thoiDiemBatDau, thoiDiemKetThuc,
danhSach);
else if (thoiDiemBatDau > node->thoiDiemVao)
danhSachXeTrongKhoangThoiGian(node->right, thoiDiemBatDau, thoiDiemKetThuc,
danhSach);
else {
danhSachXeTrongKhoangThoiGian(node->left, thoiDiemBatDau, thoiDiemKetThuc,
danhSach);
danhSach.push_back(node->bienSoXe);
danhSachXeTrongKhoangThoiGian(node->right, thoiDiemBatDau, thoiDiemKetThuc,
danhSach);
}
}

void AVLTree::thongKeLuotXeVaoTrongNgay(Node* node, time_t ngay, int& count) {

if (node == nullptr)
return;

tm* tm_thoiDiemVao = localtime(&node->thoiDiemVao);

if (tm_thoiDiemVao->tm_mday == localtime(&ngay)->tm_mday &&
tm_thoiDiemVao->tm_mon == localtime(&ngay)->tm_mon &&
tm_thoiDiemVao->tm_year == localtime(&ngay)->tm_year) {
count++;
}

thongKeLuotXeVaoTrongNgay(node->left, ngay, count);

thongKeLuotXeVaoTrongNgay(node->right, ngay, count);
}

[Link]

#include <iostream>
#include "QuanLyBaiDoXe.h"

using namespace std;

int main() {
 AVLTree parkingLot;

while (true) {
cout << "Menu:" << endl;
cout << "1. Xe vao bai" << endl;
cout << "2. Xe ra bai" << endl;
cout << "3. Xoa thong tin xe" << endl;
cout << "4. Liet ke cac xe vao trong khoang thoi gian" << endl;
cout << "5. Thong ke luot xe vao trong ngay" << endl;
cout << "0. Thoat" << endl;
cout << "Lua chon: ";

int choice;
cin >> choice;

switch (choice) {
case 1: {
string bienSoXe;
cout << "Nhap bien so xe: ";
cin >> bienSoXe;
time_t now = time(0);
[Link](bienSoXe, now);
cout << "Da ghi nhan xe vao luc " << ctime(&now) << endl;
break;
}
case 2: {
string bienSoXe;
cout << "Nhap bien so xe: ";
cin >> bienSoXe;
time_t now = time(0);
[Link](bienSoXe, now);
cout << "Da ghi nhan xe ra luc " << ctime(&now) << endl;
break;
}
case 3: {
string bienSoXe;
cout << "Nhap bien so xe can xoa: ";
cin >> bienSoXe;
[Link](bienSoXe);
cout << "Da xoa thong tin xe" << endl;
break;
}
case 4: {
time_t thoiDiemBatDau, thoiDiemKetThuc;
cout << "Nhap thoi diem bat dau (dd/mm/yyyy hh:mm:ss): ";
cin >> thoiDiemBatDau;
cout << "Nhap thoi diem ket thuc (dd/mm/yyyy hh:mm:ss): ";
cin >> thoiDiemKetThuc;
auto danhSachXe = [Link](thoiDiemBatDau,
thoiDiemKetThuc);
cout << "Danh sach xe vao trong khoang thoi gian: " << endl;
for (const auto& bienSoXe : danhSachXe) {
cout << bienSoXe << endl;
}
break;
}
case 5: {
time_t ngay;
 cout << "Nhap ngay can thong ke (dd/mm/yyyy): ";
cin >> ngay;
int luotXeVao = [Link](ngay);
cout << "So luot xe vao trong ngay: " << luotXeVao << endl;
break;
}
case 0:
cout << "Tam biet!";
return 0;
default:
cout << "Lua chon khong hop le. Vui long chon lai." << endl;
break;
}
cout << endl;
}

return 0;
}