Font size
Worksheetsctdl-hungnn22
Total questions: 87
Worksheet time: 46mins
Các thuộc tính của một kiểu dữ liệu
Miền giá trị
Tên kiểu dữ liệu
Tất cả các thuộc tính đưa ra
Kích thước lưu trữ
Trong một chương trình có 3 bước thực hiện mà thời gian thực hiện tưng bước lần lượt là
O(n2), O(n3) và O(nlog2n). thời gian thực hiện chương trình sẽ là
Chú ý: (log2n) = Log cơ số 2 của n; n^2 = n mũ 2
O(n^2)+ O(n^3) + O(nlog2n)
O(nlog2n)
O(n^2)
O(n^3)
Thời gian thực hiện các lệnh đơn : gán, đọc, viết là
?
Chú ý: (log2n) = Log cơ số 2 của n; n^2 = n mũ 2
o(1)
o(1)
o(1)
o(1)
Đặc trưng nào của thuật toán thể hiện: Tất cả các phép toán có mặt trong các bước của
thuật toán phải đủ đơn giản
Tính xác định
Tất cả ý nêu ra
Tính dừng
Tính khả thi
Sắp xếp theo thứ tự tăng dần của cấp thời gian thực hiện chương trình (Chú ý: (log2n) =
Log cơ số 2 của n)
O(nlog2n),O(n),O(log2n),O(1)
O(log2n),O(n),O(nlog2n),O(1)
O(1),O(nlog2n),O(n),O(log2n)
O(1),O(log2n),O(n),O(nlog2n)
Đặc trưng của thuật toán
Thuật toán phải dừng lại sau một số hữu hạn các bước cần thực hiện
Tất cả các phép toán có mặt trong các bước của thuật toán phải đủ đơn giản
Tất cả ý nêu ra
Mỗi thuật toán có bộ dữ liệu vào ,ra tương ứng
Chọn câu trả lời đúng nhất về thuật toán
Thuật toán là một dãy hữu hạn các bước, tất cả các phép toán có mặt trong các
bước của thuật toán phải đủ đơn giản.
Thuật toán cần có một hoặc nhiều dữ liệu ra (output) ,dữ liệu vào (input).
Thuật toán là nòng cốt của chương trình
Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán
hoặc hành động cần thực hiện để giải quyết vấn đề đặt ra
Nếu hàm được gọi trước khi nó định nghĩa thì điều kiện là gì?
Hàm chỉ trả về kiểu dữ liệu boolean
Kiểu trả về của hàm phải là kiều void
Kiểu đầu vào của hàm phải là kiểu void
Trước khi gọi hàm nó phải được khai báo
Dữ liệu kí tự bao gồm
Các ký tự bản vẻ.
Các kí tự số chữ số.
Các kí tự chữ cái.
Các kí tự đặc biệt.
Mảng là
Một nhóm phần tử có thể có kiểu riêng và tên gọi riêng cho mỗi phần tử.
Là một kiểu dữ liệu cơ sở đã định sẵn của ngôn ngữ lập trình C.
Một nhóm phần tử có cùng kiểu và chung tên gọi
Một nhóm phần tử có thể có kiểu riêng và chung tên gọi.
Kích thước của mảng là hay
Kích thước bộ nhớ sẽ cấp phát cho mảng
Số phần tử tối đa của mảng -1
Số phần tử tối đa của mảng
Biến con trỏ có thể chứa
Giá trị của một biến khác.
Địa chỉ vùng nhớ của một biến khác.
Cả a và b đều sai.
Cả a và b đều đúng.
Char S[20]="aaaaaea";
char* p=strstr(S,"e");
Nếu địa chỉ của S là 1000, thì giá trị của p là bao nhiêu là
1000
1002
1005
1006
Cho đoạn chương trình sau:
int dequy(int a,int b)
{
if(a==b)
return a;
else
{
if(a > b)
a=a-b;
else
b=b-a;
}
return dequy(a,b);
}
Cho biết chức năng của đoạn chương trình trên
Tìm ước số chung nhỏ nhất của 2 số nguyên a, b.
Tìm ước số chung trung bình của 2 số nguyên a, b.
Tìm ước số chung lớn nhất của 2 số nguyên a, b.
Đáp án khác
Cho giải thuật đệ quy
1.F(1)=F(2)=1
2.F(k)=F(k-1)+F(k-2) nếu K > 2
Hãy tính F(6):
?
8
9
10
Cho đoạn chương trình sau:
long dequy(long n,long &max)
{
long m;
if(n==0)
return max;
else
{
m=n%10;
if(m > max)
max=m;
}
return dequy(n/10,max);
}
Cho biết chức năng của đoạn chương trình trên
Tìm chữ số có giá trị lớn nhất của số nguyên dương n
Đáp án khác
Tìm chữ số có giá trị nhỏ nhất của số nguyên dương n
Tìm chữ số có giá trị trung bình của số nguyên dương n
Cho đoạn chương trình sau:
long Tong(unsigned n)
{
if(n==0)
return 1;
return n+Tong(n-2);
}
Cho biết chức năng của đoạn chương trình trên dùng để tính cho biểu thức nào
S(n)=1+2+4+…+(2.n+1) với n > =0
S(n)=2+4+6+…+(2.n+1) với n > =0
Đáp án khác
S(n)=1+3+5+…+(2.n+1) với n > =0
Cho đoạn chương trình sau:
int dequy(int n)
{
if(n==0)
return 0;
return 1+dequy(n/10);
}
Cho biết chức năng của đoạn chương trình trên
Tìm phần nguyên của n
Tìm số chia hết cho n
Tìm phần lẻ của n
Đếm số lượng chữ số nguyên dương n
Ưu điểm của thủ tục đệ quy là
Tất cả các đáp trên
Chương trình dễ hiểu
Viết chương trình dễ dàng
Chương trình ngắn ngọn
Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán
được đặt ra như sau:
Các con thỏ không bao giờ chết.
Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp thỏ con.
Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới.
Giả sử bắt đầu từ một cặp thỏ mới ra đời thì đến tháng thứ 5 sẽ có bao nhiêu cặp?
10 cặp
9 cặp
12 cặp
5 cặp
Cho giải thuật đệ quy:
1.F(0,a)=F(a,0)=a (0 là số không)
2.F(m,n)=F(m-n,n) nếu m > =n
3.F(m,n)=F(m,n-m) Nếu m=30, n = 75 thì sau khi thực hiện giải thuật ta được giá trị là
?
14
15
16
17
Cho mảng 2 chiều A={a (i j )}, mảng có m hàng, n cột, và được lưu trữ liên tiếp. Công
thức tính địa chỉ của phần tử a (i j)
L{ F(i j )} = L(0) + C [(j - 1)m + (i - 1)]
Dùng trong trường hợp
Ưu tiên cột
Ưu tiên số lượng
Ưu tiên hàng
Trong mọi trường hợp
Chọn câu đúng nhất cho hàm Swap?
Void Swap(int X, intY) { int Temp = X; X = Y; Y = Temp; }
Void Swap(int *X, int *Y){ int Temp = X; X = Y; Y = Temp; }
Void Swap(float X, floatY){ int Temp = X; X = Y; Y = Temp; }
Void Swap(int &X, int &Y) { int Temp = X; X = Y; Y = Temp; }
Độ phức tạp của giải thuật tìm kiếm nhị phân là:
O(log4N)
O(log5N)
O(log2N)
O(log3N)
Trong số các phép toán sau đây, phép toán nào không được dùng đối với mảng:
Lưu trữ mảng
Tìm kiếm trên mảng
Bổ xung một phần tử vào mảng
Tạo mảng
Các tiêu chuẩn đánh giá cấu trúc dữ liệu. Để đánh giá một cấu trúc dữ liệu chúng ta
thường dựa vào các tiêu chí nào
Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu
Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong)
Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài toán
Tất cả đáp án trên là đúng
Độ phức tạp của giải thuật tìm kiếm tuần tự là:
O(N-2)
O(N-3)
O(N-1)
O(N)
Ngôn ngữ lập trình nào dưới đây là ngôn ngữ lập trình có cấu trúc?
Ngôn ngữ Assembler.
Ngôn ngữ Cobol.
Ngôn ngữ C
Pascal
Cho dãy số sau: 14 32 10 43 57 87 55 36 97 11. Áp dụng phương pháp tìm kiếm tuần
tự, sau bao nhiều lần thực hiện phép so sánh ta sẽ tìm thấy số 43?
3 lần
2 lần
5 lần
4 lần
Phương pháp sắp xếp nhanh (Quick sort) chính là phương pháp:
Phân đoạn
Chèn
Trộn
Vun đống
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau lần lặp đầu
tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ bốn là:
{0 1 2 8 5 9 6 4 3 7}
{0 4 2 8 5 9 6 1 3 7}
{0 2 4 5 8 9 6 1 3 7}
{0 1 2 3 5 9 6 4 8 7}
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ ba là:
{0 1 2 8 5 9 6 4 3 7}
{0 2 3 8 5 9 6 1 4 7}
{0 2 4 5 8 9 6 1 3 7}
{0 2 4 8 5 9 6 1 3 7}
Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp
đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ tư là:
{0 1 2 3 5 7 9 6 8 4}
{0 1 2 3 6 5 7 9 8 4}
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 5 7 9 4 8 6}
Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) sau lần lặp
đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ năm là:
{0 1 2 3 5 7 9 4 8 6}
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 4 7 9 6 8 5}
{0 1 2 3 6 5 7 9 8 4}
Cho dãy số {6 1 3 0 5 7 9 2 8 4}. áp dụng phương pháp sắp xếp lựa chọn (Select sort) tăng dần, sau
lần lặp đầu tiên của giải thuật ta có kết quả: {0 1 3 6 5 7 9 2 8 4}. Dãy số thu được sau lần lặp thứ
tám là:
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 4 5 9 6 7 9}
{0 1 2 3 4 5 6 9 7 8}
{0 1 2 3 4 5 9 6 8 7}
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau lần lặp đầu
tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ tám là:
{0 1 2 4 5 6 8 9 3 7}
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 4 5 6 8 9 7}
{0 1 2 3 4 5 8 9 6 7}
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ chín là:
{0 1 2 3 4 5 8 9 6 7}
{0 1 2 3 4 5 6 8 9 7}
{0 1 2 4 5 6 8 9 3 7}
{0 1 2 3 4 5 6 7 8 9}
Ý tưởng phương pháp sắp xếp vun đống (Heap sort) là
Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước
khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).
Lần lượt tạo đống cho cây nhị phân (phần tử gốc có giá trị lớn nhất) và loại phần tử
gốc ra khỏi cây đưa vào dãy sắp xếp.
Tạo đống cho cây nhị phân (cây nhị phân đã được sắp xếp giảm dần).
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên.
Cho dãy số sau: 40 25 75 15 65 55 90 30 95 85. Áp dụng phương pháp sắp xếp lựa chọn, sau lượt 3
dãy sẽ được sắp xếp lại như thế nào?
15 25 30 40 65 55 90 75 95 85
15 25 75 40 65 55 90 30 85 95
15 75 25 40 65 55 90 30 95 85
15 25 75 40 55 65 90 30 95 85
Cho dãy số {3 1 6 0 5 4 8 2 9 7}. áp dụng phương pháp sắp xếp nhanh (Quick sort) sau lần lặp đầu
tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số thu được sau lần lặp thứ bốn là:
{(0) 1 (2 3) 4 (5 6) 7 (8 9)}
{(3) 1 (6 0) 5 (4 8) 2 (9 7)}
{0 1 (2) 3 (5 4) 8 (6 9 7)}
{0 1 2 3 (5 4 8 6 9 7)}
Ý tưởng phương pháp sắp xếp Trộn (Merge sort) là:
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhất; Tương tự đối với phần tử nhỏ thứ hai,ba...
Lần lượt chia dãy phần tử thành hai dãy con bởi một phần tử khoá (dãy con trước
khoá gồm các phần tử nhỏ hơn khoá và dãy còn lại gồm các phần tử lớn hơn khoá).
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên.
Ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:
Phân đoạn dãy thành nhiều dãy con và lần lượt trộn hai dãy con thành dãy lớn
hơn, cho đến khi thu được dãy ban đầu đã được sắp xếp.
Chọn phần tử bé nhất xếp vào vị trí thứ nhất bằng cách đổi chổ phần tử bé nhất
với phần tử thứ nhấ; Tương tự đối với phần tử nhỏ thứ hai,ba...
Bắt đầu từ cuối dãy đến đầu dãy, ta lần lượt so sánh hai phần tử kế tiếp nhau, nếu
phần tử nào nhỏ hơn được đứng vị trí trên
Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của nó trong dãy bằng
cách đẩy các phần tử lớn hơn xuống.
Cho dãy số {4 0 2 8 5 9 6 1 3 7}. áp dụng phương pháp sắp xếp chèn (Insert sort) sau lần lặp đầu
tiên của giải thuật ta có kết quả:{0 4 2 8 5 9 6 1 3 7}. Dãy số thu được sau lần lặp thứ hai là:
{0 1 4 8 5 9 6 1 3 7}
{0 2 4 8 5 9 6 1 3 7}
{0 1 2 8 5 9 6 4 3 7}
{0 4 2 8 5 9 6 1 3 7}
Cho dãy số {3 1 6 0 5 4 8 2 9 7}. áp dụng phương pháp sắp xếp nhanh (Quick sort) sau lần lặp đầu tiên của giải thuật ta có kết quả: {(0 1 2) 3 (5 4 8 6 9 7)}. Dãy số thu được sau lần lặp thứ ba là:
{0 1 (2) 3 (5 4) 8 (6 9 7)}
{(0) 1 (2 3) 4 (5 6) 7 (8 9)}
{(3) 1 (6 0) 5 (4 8) 2 (9 7)}
{0 1 (2) 3 (5 4 8 6 9 7)}
Trong các cấu trúc dữ liệu sau, đâu là dữ liệu trừu tượng?
Cấu trúc dữ liệu kiểu hàng đợi(QUEUE)
Tất cả cấu trúc
Cấu trúc dữ liệu dạng StacK
Cấu trúc dữ liệu dạng danh sách(LIST)
Cho đoạn chương trình:
char S[] = “Helen”;
char *p = S;
char c = *(p+3);
Giá trị của c sẽ là
a
b
d
e
Danh sách tuyến tính là
Không có đáp án đúng
Danh sách tuyến tính là một danh sách rỗng
Danh sách có dạng (a1, a2, ..., an)
Danh sách mà quan hệ lân cận giữa các phần tử được hiển thị ra thì được là danh
sách tuyến tính
Chọn câu đúng?
“struct” là sự kết hợp của nhiều thành phần không có thể có kiểu khác nhau.
“struct” là sự kết hợp của nhiều thành phần có thể có kiểu khác nhau.
“struct” là một kiểu dữ liệu do người dùng định nghĩa bao gồm nhiều thành phần
có kiểu cùng nhau.
“struct” là một kiểu dữ liệu do người dùng định nghĩa bao gồm nhiều thành phần
có kiểu khác nhau.
Định nghĩa danh sách tuyến tính Hàng đợi (Queue)?
Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử vào
hàng đợi hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)
Hàng đợi là kiểu 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, gọi là lối sau (rear) hay lối trước (front). Phép
loại bỏ không thực hiện được.
Hàng đợi là kiểu 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, gọi là lối sau (rear) và phép loại bỏ một phần
tử được thực hiện ở đầu kia, gọi là lối trước (front)
Tất cả đều đúng
Trong lưu trữ dữ liệu kiểu Queue (Q) dưới dạng mảng nối vòng, giả sử F là con trỏ trỏ tới lối trước
của Q, R là con trỏ trỏ tới lối sau của Q. Điều kiện F=R=0 nghĩa là:
Đặt phần tử đầu và phần tử cuối của Queue bằng 0
Queue rỗng
Kiểm tra chỉ số trước và chỉ số sau của Queue có bằng nhau không.
Queue tràn
Hàng đợi còn được gọi là danh sách kiểu
FIFO
LIFO
FILO
LOLO
Ngăn xếp được viết tắt bởi sự kết hợp các từ sau
FB
FO
FA
LI
Dùng STACK để lưu trữ số nhị phân có giá trị bằng số thập phân 215 ta có kết quả: ( số bên trái vào
trước số bên phải )
11101011
10111101
11110011
11001110
Khi bổ sung một phần tử mới vào hàng đợi cần kiểm tra thì ...
Hàng đợi có rỗng không
Hàng đợi có đầy không
Hàng đợi có bao nhiêu phần tử
Hàng đợi có bao nhiêu giá trị bằng 0
Cho Stack gồm 5 phần tử {12, 5, 20, 23, 25}, trong đó 25 là phần tử ở đỉnh Stack. Để lấy ra phần tử
thứ 4 trong Stack ta phải làm thế nào?
PUSH(25)
POP(25),
PUSH(23)
POP(23)
Trong lưu trữ dữ liệu kiểu Queue (Q), giả sử F là con trỏ trỏ tới lối trước của Q, R là con trỏ trỏ tới lối
sau của Q. Khi loại bỏ một phần tử vào Queue, thì R và F thay đổi thế nào?
F không thay đổi, R=R+1
F không thay đổi, R=R-1
F=F-1, R không thay đổi
F=F+1, R không thay đổi
Cấu trúc dữ liệu nào tương ứng với LIFO
Linked List
Queue
Tree
Stack
Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là:
PUSH(x).
TOP(x).
POP(x).
EMPTY(x).
Để tạo danh sách liên kết, theo bạn sinh viên nào dưới đây là khai báo đúng cấu trúc tự trỏ sẽ được dùng:
1- Sinh viên 1:
struct SV{char ht[25]; int tuoi; struct Sv *tiep;};
2- Sinh viên 2:
typedef
struct SV node;
struct SV{char ht[25]; int tuoi; node *tiep;};
3- Sinh viên 3:
typedef
struct SV{char ht[25]; int tuoi; struct SV *tiep;} node;
4
3
2
1
Danh sách khai báo bằng con trỏ. Thủ tục sau có chức năng gì?"
void MnullList ( List Header)
{
New (Header);
Header.Next : = Nil;
}
Thủ tục khởi tạo danh sách rỗng
Thủ tục tạo mới danh sách
Thủ tục đưa con trỏ vào biến Nil
Cài đặt danh sách bằng con trỏ có nghĩa là
Dùng con trỏ quản lí các phần tử của mảng theo phương thức bất kì. Để một phần tử
có thể chỉ đến một phần tử khác ta xem mỗi ô là một Record gồm có 2 trường :
Trường Elements để giữ nội dung của phần tử trong danh sách. Trường Next là một
con trỏ giữ địa chỉ của ô kế tiếp.
Không có đáp án đúng
Dùng một mảng (array) để lưu trữ liên tiếp các phần tử của danh sách bắt đầu từ vị trí
đầu tiên của mảng. Khai báo bản ghi gồm 2 trường:Trường Elements để giữ nội dung
của phần tử trong danh sách. Trường Next là một con trỏ giữ địa chỉ của ô kế tiếp.
Dùng con trỏ để liên kết các phần tử của danh sách theo phương thức ai chỉ đến ai+1.
Để một phần tử có thể chỉ đến một phần tử khác ta xem mỗi ô là một Record gồm có
2 trường : Trường Elements để giữ nội dung của phần tử trong danh sách. Trường
Next là một con trỏ giữ địa chỉ của ô kế tiếp
Danh sách khai báo bằng con trỏ. Hàm sau có chức năng gì?
Boolean EList( ListvHeader )
{
Elist = (Header.Next = Nil);
}
Khởi tạo danh sách rỗng
Tạo mới một danh sách
Kiểm tra danh sách rỗng
Đưa con trỏ về cuối danh sách.
Thành phần dữ liệu của danh sách liên liên kết .....
Lưu thông tin về bản thân phần tử trước
Lưu thông tin phần tử đứng sau
Lưu thông tin về bản thân phần tử
Không có đáp án đúng
Cho một danh sách móc nối với các phần tử trong danh sách có kiểu S1 được định nghĩa như sau:
struct S1{ int info; struct S1 * next;} *head;
Biết con trỏ “head” lưu địa chỉ của phần tử đầu tiên trong danh sách. Cho biết mục đích của câu lệnh sau:
{ head- > next- > next- > info=111;};
Câu lệnh bị lỗi.
Giá trị “info” trong phần tử thứ 2 đã bị thay đổi.
Giá trị “info” trong phần tử bất kì đã bị thay đổi.
Giá trị “info” trong phần tử thứ 3 đã bị thay đổi.
Danh sách liên kết vòng là gì?
1. Danh sách liên kết vòng (Circular Linked List) là một biến thể của Danh sách liên kết (Linked List), trong
đó phần tử đầu tiên trỏ tới phần tử cuối cùng và phần tử cuối cùng trỏ tới phần tử đầu tiên.,
2. Danh sách liên kết vòng (Circular Linked List) là một biến thể của Danh sách liên kết (Linked List), trong
đó phần tử đầu tiên trỏ tới phần tử đầu tiên và phần tử cuối cùng trỏ tới phần tử cuối.
1 đúng, 2 sai
1 sai, 2 đúng
1 sai, 2 sai
1 đúng, 2 đúng
Để dùng danh sách liên kết, xét hai khai báo sau(cần 1KB để lưu dữ thông tin về một sinh viên):
1- Khai báo 1: struct SV{ thongtin; struct SV *tiep;};
2- Khai báo 2: struct SV {thongtin}; struct DS{struct SV* sv; struct DS* tiep;};
(Với “thongtin” là một thành phần dữ liệu của cấu trúc); Chọn câu đúng nhất trong các câu sau:
Khai báo 2 sẽ giúp chương trình chạy nhanh hơn khi duyệt danh sách.
Khai báo 1 sẽ giúp tiết kiệm câu lệnh hơn khi viết hàm đổi vị trí 2 sinh viên.
Khai báo 2 sẽ giúp chương trình chạy nhanh hơn khi đổi vị trí 2 sinh viên.
Khai báo 1 tốn nhiều bộ nhớ hơn khai báo 2.
Định nghĩa cấu trúc dữ liệu dạng danh sách (LIST)?
Danh sách là tập hợp các phần tử khác kiểu
Danh sách là kiểu dữ liệu mảng
Danh sách là kiểu con trỏ
Danh sách là một tập hợp các phần tử có cùng một kiểu mà ta gọi là kiểu phần tử
(ElementType).
Cho một ma trận thưa, hàng 1 có 2 phần tử F(11) , F(12) . Từ hàng thứ 2 chỉ có 3 phần tử F(k , k-1) ; F(k, k)
; F(k, k+1) , hàng cuối cùng cũng chỉ có 2 phần tử : F(n, n-1) ; F(n , n)
Hãy lưu trữ liên tiếp ưu tiên hàng của ma trận này thành một mảng một chiều : thí dụ F(11) là b(1) ; F(12)
là b(2) ; F(21) là b(3) …
Nếu F(67) thì b
16
17
18
15
Danh sách tuyến tính là
Danh sách dạng được lưu dưới dạng mảng.
Danh sách mà quan hệ lân cận giữa các phần tử được xác định.
Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).
Danh sách tuyến tính là một danh sách rỗng.
Cho một danh sách móc nối với các phần tử trong danh sách có kiểu S1 được định nghĩa như sau:
struct S1{int info; struct S1 *next;} *head;
Biết con trỏ “*head” lưu địa chỉ của phần tử đầu tiên trong danh sách. Nhóm câu lệnh nào sau đây thêm
một phần tử vào đầu danh sách:
P- > next=head; head- > p; head=p- > next;
Head- > next=p; p=head;
Không có câu nào đúng.
P- > next=head; head=p;
Cho một danh sách móc nối với các phần tử trong danh sách có kiểu S1 được định nghĩa như sau:
struct S1{ int info; struct S1 * next;} *head;
Biết con trỏ “head” lưu địa chỉ của phần tử đầu tiên trong danh sách. Cho biết mục đích của câu lệnh sau:
{(head- > next)=(head- > next)- > next;};
Loại bỏ phần tử thứ 2 ra khỏi danh sách.
Loại bỏ phần tử thứ nhất ra khỏi danh sách.
Loại bỏ phần tử thứ 3 ra khỏi danh sách.
Câu lệnh bị lỗi.
Dấu hiệu nào dưới đây cho biết node p của một danh sách liên kết đơn là node cuối cùng bên phải:
(p- > next!=NULL);
(p- > info!=NULL);
(p- > next==NULL);
(p- > info==NULL);
Có bao nhiêu loại hoạt động cơ bản trên danh sách liên kết vòng
1
2
3
4
Tính chất nào sau đây là tính chất của cây nhị phân tìm kiếm:
Mọi khóa thuộc cây con trái nút đó đều bằng khóa cây con phải nút đó
Mọi khóa thuộc cây con trái nút đó đều lớn hơn khóa cây con phải nút đó
Mọi khóa thuộc cây con trái nút đó đều lớn hơn khóa ứng với nút đó
Mọi khóa thuộc cây con trái nút đó đều nhỏ hơn khóa ứng với nút đó
Cho dãy khoá 42,23,74,11,65,58,94,36 Lần lượt đưa dãy khoá trên vào cây nhị phân tìm kiếm. Bây giờ ta muốn tìm kiếm xem trong dãy khoá trên có khoá 105 không thì phải làm bao nhiêu phép so sánh:
1
2
3
4
Một danh sách trong đó tất cả các thao tác chèn thực hiện tại một đầu, thao tác xóa được thực hiện tại đầu kia của danh sách gọi là:
Queue
Stack.
Cây nhị phân.
Cho cây nhị phân T, nút có địa chỉ 19 thì có nút cha ở địa chỉ nào
5
6
7
9
Nếu lưu trữ móc nối thì mỗi nút của cây nhị phân cần 2 khoảng để ghi địa chỉ 2 con. Cây có 72 nút. Vậy lãng phí bao nhiêu khoảng địa chỉ:
71
72
73
74
Khi lưu trữ cây nhị phân dưới dạng mảng, nếu vị trí của nút cha trong mảng là i thì vị trí của nút con trái là
I+1
I-1
2*i + 1
2*i
Mỗi nút trong cây có tối đa:
3 nút con
Nhiều nút con
1 nút con
2 nút con
Cho cây nhị phân T có chiều cao là 6( nút gốc có mức 1) . Số nút tối đa của cây là:
31
63
90
125
Cho cây nhị phân T, phép duỵêt cây theo thứ tự giữa cho kết quả DBHEAFICGJ . Nếu duyệt theo thứ tự sau ta có kết quả : DHEBIFJGCA . Hãy cho biết các nút của cây con phải
FBHE
HEFI
ICGH
FICGJ
Độ cao của cây là gì?
Mức lớn nhất của cây
Cấp lớn nhất của nút
Số cây con của cây
Số lượng nút của cây
Cho cây nhị phân T. Phép duyệt cây theo thứ tự trước cho kết quả ABDEHCFIGJ. Nếu duyệt theo thứ tự giữa ta có kết quả: DBHEAFICGJ. Hãy cho biết các nút của cây con trái
DHEG
BDHE
DEH
FIHE
Cây nhị phân tìm kiếm là:
Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha nhỏ hơn mọi nút trên cây con trái và lớn hơn mọi nút trên cây con phảI của nó
Là cây nhị phân đầy đủ.
Cây nhị phân thoả tính chất heap
Cây nhị phân mà mỗi nút trong cây đều thoả tính chất: giá trị của nút cha lớn hơn giá trị của hai nút con.
Trong biểu diễn dữ liệu dưới dạng cây, cấp của cây chính
Cấp cao nhất của nút gốc
Cấp cao nhất của một nút trên cây
Tổng số nút trên cây
Cấp cao nhất của nút lá
Duyệt cây nhị phân theo thứ tự trước được thực hiện theo thứ tự:
Thăm gốc trước, duyệt cây con trái theo thứ tự giữa, duyệt cây con phải theo thứ tự sau
Duyệt cây con trái theo thứ tự sau, thăm gốc trước, duyệt cây con phải theo thứ tự sau.
Thăm gốc, duyệt cây con trái theo thứ tự trước, duyệt cây con phải theo thứ tự trước
Duyệt cây con trái theo thứ tự trước, thăm gốc giữa, duyệt cây con phải theo thứ tự sau.
