1 số đề thi CTDL & GT

Chia sẻ bởi Nguyễn Quỳnh Mai | Ngày 19/03/2024 | 12
Chia sẻ tài liệu: 1 số đề thi CTDL & GT thuộc Công nghệ thông tin

Nội dung tài liệu:



Đề 4 (K46)
Câu1 .
a.Đặc tả

//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
//
//

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)
{
if ( x <= P->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
{
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();
// 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 ()
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Nguyễn Quỳnh Mai
Dung lượng: | Lượt tài: 0
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)
Tải tài liệu