Font size
WorksheetsGiai-Thuat
Total questions: 125
Worksheet time: 31hrs 15mins
Để đổi chỗ 2 phần tử a7, a9 ta đưa thêm một tham số X và ta thực hiện dãy lệnh sau đây
X=a9 ; a7=X ; a9=a7
X=a7 ; a9:=X ; a7=a9
a7=a9 ; a9=a7 ; X= a7
X=a7 ; a7=a9 ; a9=X
Một giá trị kiểu char chiếm bao nhiêu bộ nhớ
1byte
2byte
3byte
4byte
Đặc điểm của giải thuật đệ quy
Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
Có một trường hợp đặc biệt, trường hợp suy biến Khi trường hợp này xảy ra thì bài toán còn lại sẽ được giải quyết theo một cách khác
Sau mỗi lần có lời gọi đệ quy thì kích thước của bài toán được thu nhỏ hơn trước.
Có ba trường hợp đặc biệt, trường hợp suy biến Khi trường hợp này xảy ra thì bài toán còn lại sẽ được giải quyết theo một cách khác
Miền giá trị của Kiểu số nguyên là:
0..32767
0..32768
-32767 .. 32768
-32768 .. 32767
Các thuộc tính của một kiểu dữ liệu
Tên kiểu dữ liệu
Miền giá trị
Kích thước lưu trữ
Tất cả các thuộc tính đưa ra
Trong các cấu trúc dữ liệu sau đâu là dữ liệu trừu tượng
Tất cả đáp án đều sai
Cấu trúc dữ liệu kiểu hàng đợi(QUEUE)
Cấu trúc dữ liệu dạng (StacK)
Cấu trúc dữ liệu dạng danh sách(LIST)
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^3)
O(n^2)
O(nlog2n)
O(n^2)+ O(n^3) + O(nlog2n)
Kích thước lưu trữ kiểu số nguyên là
4 byte
2 byte
1 byte
6 byte
Giả sử có câu lệnh ch='A'. Vậy ch sẽ chứa bao nhiêu byte
1
2
3
4
Đâu là kiểu dữ liệu có cấu trúc?
Kiểu integer
Kiểu con trỏ
Kiểu array (mảng)
Tất cả các kiểu đưa ra
Nếu có các khai báo sau:
char msg[10];
char *ptr;
char value;
Câu nào sau đây là đúng:
Cả hai câu trên đều sai.
ptr=value;
ptr=msg;
Cả hai câu trên đều đúng.
Giả sử trong ngôn ngữ C sử dụng khai báo “double a[12]”, phần tử a[7] là phần tử thứ bao nhiêu trong mảng a
Thứ 9.
Thứ 8.
Thứ 7.
Thứ 6.
Kí hiệu nào là con trỏ của phẩn tử thứ 3 của mảng a có 4 kí tự
*(a+2)
a(a*2)
2a
a+2
Khi khai báo mảng, ta khởi tạo luôn giá trị của mảng như sau:int x[3]={4,2,6}; Nghĩa là: x[0]= , x[1]= , x[2]= ;
2,6,4
4,2,6
2,4,6
6,2,4
Biểu thức điều kiện để kiểm tra một phần tử thứ i của mảng A có nằm trong (-5;10) là ?
1. (A[i] > -5) and (A[i] < 10)
2. (-5 < A[i]) and (10 < A[i])
1 đúng, 2 sai
1 sai, 2 sai
1 đúng, 2 đúng
1 sai, 2 đúng
Cho đoạn chương trình sau:
int n=0;
for (int i=0; i < 10; i+=4) n+=I; giá trị của biến n là
2
5
8
12
Phát biểu nào sau đây về mảng một chiều là đúng?
Mảng không chứa các kí tự là chữ cái
Chỉ là tập hợp các số nguyên
Là tập hợp vô hạn các phần tử có cùng kiểu dữ liệu
Là tập hợp hữu hạn các phần tử có cùng kiểu dữ liệu
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à
1006
1005
1000
1003
Khai báo hàm tìm giá trị lớn nhất trong một mảng các số long dưới đây, khai báo đúng là ?
char max(long *a, int n)
long max(long *a, int n)
bool max(long *a, int n)
long max(double *a, int n)
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(7):
11
13
12
14
Trường hợp đệ quy của giải thuật đệ qui là
Cả hai đáp án trên đều sai
Cả hai đáp án trên đều đúng
là cơ chế đưa bài toán cần giải về một hay nhiều bài toán tương tự nhưng có quy mô lớn hơn
là cơ chế đưa bài toán cần giải về một hay nhiều bài toán tương tự nhưng có quy mô nhỏ hơn
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):
5
6
7
8
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
Đáp án khác
Tìm chữ số có giá trị lớn nhất của số nguyên dương n
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
ho 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à
18
16
15
17
Cho đoạn chương trình sau:
int Logarit(int n)
{
if(n < 0)
return -1;
else
if(n > =2)
return 1+logarit(n/2);
else
return 0;
}
Cho biết chức năng của đoạn chương trình trên
Tìm giá trị nguyên logarit cơ số 3 của n
Tìm giá trị nguyên logarit cơ số 4 của n
Tìm giá trị nguyên logarit cơ số 2 của n
Tìm giá trị nguyên logarit cơ số 5 của n
Cho giải thuật đệ quy
1.F(1)=1, F(2)=2, F(3)=2
2.F(k)=F(K-1) + 2F(K-3) , K > 3
Hãy tính F(6)
10
11
12
13
không phải lúc nào cũng có thể xây dựng bài toán theo giải thuật và thủ tục đệ quy một cách dễ dàng, các vấn đề có thể là
đáp án khác
Làm thế nào để đảm bảo kích thước bài toán giảm đi sau mỗi lần gọi?
bài toán được chia nhỏ ra
Xem xét và định nghĩa các trường hợp đặc biệt (trường hợp suy biến) như thế nào?
Ứng dụng của giải thuật đệ quy để giải các bài toán sau:
thêm phần tử trong danh sách liên kết
Tính giai thừa của số nguyên n
Tìm kiếm trong danh sách liên kết
tháp Hà Nội
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+3+5+…+(2.n+1) với n > =0
Đáp án khác
S(n)=2+4+6+…+(2.n+1) với n > =0
S(n)=1+2+4+…+(2.n+1) với n > =0
Số phép so sánh của thuật toán tìm kiếm, trong trường hợp xấu nhất là
3*n
2*n
5*n
4*n
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 số lượng
Trong mọi trường hợp
Ưu tiên cột
Ưu tiên hàng
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) …
Tính b(k) nếu phần tử F(i j ) là F(6 , 7)
b(20)
b(17)
b(21)
(b26)
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:
Tìm kiếm trên mảng
Bổ xung một phần tử vào mảng
Lưu trữ mảng
Tạo mảng
Ngôn ngữ lập trình C được Dennish phát triển dựa trên ngôn ngữ lập trình nào:
Ngôn ngữ B
Ngôn ngữ DEC PDP
Ngôn ngữ Cobol.
BCPL
Tư tưởng của giải thuật tìm kiếm trên cây nhị phân tìm kiếm
Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy,Dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.
So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khoá cần tìm.
Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.
Tìm kiếm dựa vào cây nhị tìm kiếm: Nừu giá trị cần tìm nhỏ hơn gốc thì thực hiện tìm kiếm trên cây con trái, ngược lại ta việc tìm kiếm được thực hiện trên cây con phải.
Độ phức tạp của giải thuật tìm kiếm tuần tự là:
O(N)
O(N-1)
O(N-2)
O(N-3)
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 phản ảnh đúng thực tế của bài toán
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)
Tất cả đáp án trên là đúng
Cho mảng 2 chiều A={F( i j)}: i là chỉ số hàng, j là chỉ số cột. Mảng A có 8 hàng, 9 cột. Lưu trữ liên tiếp mảng A ưu tiên cột nếu phần tử F(11) có địa chỉ 230 , mỗi phần tử chiếm 3 ô thì phần tử F(37) có địa chỉ:
382
378
380
420
ý 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á).
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 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).
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 75 40 55 65 90 30 95 85
15 25 75 40 65 55 90 30 85 95
15 75 25 40 65 55 90 30 95 85
15 25 30 40 65 55 90 75 95 85
ý tưởng phương pháp sắp xếp chèn (insertion 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ố 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 1 dãy sẽ được sắp xếp lại như thế nào?
15 25 75 40 65 55 90 30 95 85
15 75 25 40 65 55 90 30 95 85
15 25 75 40 65 55 90 30 85 95
15 25 75 40 55 65 90 30 95 85
Thời gian chạy chương trình phụ thuộc vào các yếu tố nào
Dữ liệu đầu vào.
Tính chất của trình biên dịch được dùng.
Độ phức tạp tính toán của giải thuật.
Tôc độ của máy được dùng.
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 6 5 7 9 8 4}
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 5 7 9 6 8 4}
{0 1 2 3 5 7 9 4 8 6}
ý tưởng phương pháp sắp xếp chọn tăng dần (select sort)
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.
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 bé hơn được cho lên vị trí trên.
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...
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ứ hai là:
{0 1 2 6 5 7 9 3 4 8}
{0 1 2 6 5 7 9 3 8 4}
{0 1 2 3 4 5 6 7 8 9}
{0 1 3 6 5 7 9 2 8 4}
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 nhanh (Quick_Sort), sau lượt 6 dãy sẽ được sắp xếp lại như thế nào?
1 5 25 30 40 55 65 (90 75 85 95)
1 5 25 30 40 55 65 (90 95 75 85)
1 5 25 30 40 55 65 (90 75 95 85)
1 5 25 30 40 55 65 (75 90 95 85)
ý tưởng phương pháp sắp xếp nhanh (Quick sort) là:
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 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á).
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...
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.
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 2 dãy sẽ được sắp xếp lại như thế nào?
15 75 25 40 65 55 90 30 95 85
15 25 75 40 65 55 90 30 95 85
15 25 75 40 65 55 90 30 85 95
15 25 75 40 55 65 90 30 95 85
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ảy là:
{0 1 2 4 5 6 8 9 3 7}
{0 1 2 4 5 8 9 6 3 7}
{0 1 2 3 5 9 6 4 8 7}
{0 2 4 5 8 9 6 1 3 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-2-4-8-5-9-6-1-3-7}
{0 1 2 8 5 9 6 4 3 7}
{0 2 4 5 8 9 6 1 3 7}
{0 2 3 8 5 9 6 1 4 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 3 4 5 6 7 8 9}
{0 1 2 4 5 6 8 9 3 7}
{0 1 2 3 4 5 8 9 6 7}
{0 1 2 3 4 5 6 8 9 7}
Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt (Bubble sort) sau lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 7 1 9 2 5 3 6 8}. Dãy số thu được sau lần lặp thứ bốn là:
{0-1-2-3-4-7-5-9-6-8}
{0 1 4 7 2 9 3 5 6 8}
{0 1 2 3 4 7 9 5 6 8}
{0 1 2 4 7 3 9 5 6 8}
Thao tác Push(x) dùng trong Stack là để:
Bổ sung một phần tử vào đỉnh Stack
Bổ sung một dãy các phần tử vào đỉnh Stack.
Bổ sung một phần tử vào đầu Stack
Bổ sung một phần tử bất kì vào Stack
Giả sử Q là Hàng đợi, các phần tử của nó có kiểu Item. Hàm sau làm nhiệm vụ gì
boolean F(Queue Q) {
F = (Q.rear = max);
}
Thêm một phần tử vào hàng đợi
Kiểm tra hàng đợi có rỗng hay không
Khởi tạo một hàng đợi rỗng
Kiểm tra hàng đợi đầy
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 thêm ] một phần tử vào Queue, thì R và F thay đổi thế nào?
F=F-1, R không thay đổi
F không thay đổi, R=R+1
F không thay đổi, R=R-1
F=F+1, R không thay đổi
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ứ 3 trong Stack ta phải làm thế nào?
POP(25), POP(23), PUSH(20), PUSH(25), PUSH(23)
POP(25), POP(23), POP(20)
POP(25), POP(23), POP(20), PUSH(23), PUSH(25)
POP(25), POP(23), POP(20), PUSH(25), PUSH(23)
Khi đổi một số nguyên từ hệ thập phân sang hệ nhị phân thì người ta dùng phép chia liên tiếp cho 2 và lấy các số dư (là các chữ số nhị phân) theo chiều ngược lại.
Cơ chế sắp xếp này chính là cơ chế hoạt động của cấu trúc dữ liệu:
Ngăn xếp (stack)
Hàng đợi(Queue)
Bản (Record)
Mảng (array)
Tìm mô tả đúng cho hàm sau:
int SC (int M[], int Len, int CM[]) {
for (int i = 0; i < Len; i++)
CM[i] = M[i];
return (Len);
}
Hàm thực hiện việc sao chép nội dung mảng M có chiều dài Len về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng CM sau khi sao chép
Hàm thực hiện việc sao chép nội dung mảng M có chiều dài Len -1 về mảng CM có cùng chiều dài. Hàm trả về chiều dài của mảng CM sau khi sao chép
Hàm thực hiện việc sao chép nội dung mảng CM có chiều dài Len về mảng M có cùng chiều dài. Hàm trả về chiều dài của mảng M sau khi sao chép
Hàm thực hiện việc sao chép nội dung mảng CM có chiều dài Len -1 về mảng M có cùng chiều dài. Hàm trả về chiều dài của mảng M sau khi sao chép
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?
POP(23)
PUSH(25)
PUSH(23)
POP(25)
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ó bao nhiêu phần tử
Hàng đợi có đầy không
Hàng đợi có rỗng không
Hàng đợi có bao nhiêu giá trị bằng 0
Để cài đặt Stack ta có thể dùng phương pháp nào sau đây?
Bằng con trỏ và bằng mảng
Bằng con trỏ
Tất cả đều sai
Bằng mảng
hàng đợi còn được gọi là danh sách kiểu
LOLO
FIFO
FILO
LIFO
Hàng đợi được viết tắt bởi sự kết hợp các từ sau
FO
FA
FI
FB
Thao tác POP(x) dùng trong Stack là để:
Xóa bỏ một dãy các phần tử ra khỏi Stack
Xóa bỏ một phần tử bất kì khỏi Stack
Lấy một phần tử cuối cùng ra khỏi đỉnh Stack
Lấy phần tử đầu tiên ra khỏi Stack
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=F+1, R không thay đổi
F=F-1, R không thay đổi
F không thay đổi, R=R-1
F không thay đổi, R=R+1
Cấu trúc dữ liệu nào tương ứng với LIFO
Linked
ListTree
Stack
Queue
Cho đoạn chương trình:
char S[] = “Helen”;
char *p = S;
char c = *(p+3);
Giá trị của c sẽ là:
e
l
n
h
Khi chèn một phần tử vào danh sách (cài đặt bằng mảng) yêu cầu cần
độ dài của danh sách = độ dài của mảng
Độ dài của danh sách < độ dài của mảng
độ dài của danh sách có thể tuỳ ý.
Độ dài danh sách > độ dài của mảng
Định nghĩa cấu trúc dữ liệu dạng danh sách (LIST)?
Danh sách là kiểu dữ liệu mảng
Danh sách là tập hợp các phần tử khác kiểu
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).
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 sai, 2 đúng
1 sai, 2 sai
1 đúng, 2 đúng
1 đúng, 2 sai
Cho mảng một chiều A=(a1,a2,…,ax,…,an) và được lưu trữ liên tiếp. Giả thử mỗi phần tử của mảng chiếm 3 ô và phần tử đầu tiên F(1) có địa chỉ 23 thì phần tử F(4) có địa chỉ
33
35
38
41
Có bao nhiêu loại hoạt động cơ bản trên danh sách liên kết vòng
4
1
2
3
Đâu là phát biểu đúng về danh sách
Tất cả đều sai.
Chỉ có thể xóa phần tử đầu tiên trong danh sách.
Chỉ có thể xóa phần tử cuối cùng trong danh sách.
Có thể xóa một phần tử tại vị trí bất kì trong danh sách.
Có mấy loại danh sách liên kết
1
2
3
4
Thành phần liên kết của danh sách liên kết .....
Lưu địa chỉ phần tử đứng sau trong danh sách
Không có đáp án đúng
Lưu địa chỉ phần tử đứng sau trong danh sách hoặc bằng NULL nếu là phần tử cuối danh sách
Lưu địa chỉ phần tử đứng trước
Cho giải thuật sau:
1.C(n,n)=C(n,0)=1
2.C(n,k)=C(n-1,k)+C(n-1,k-1) với n > k > 0
Giá trị của C(4,2) là
3
4
5
6
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à:
Stack.
Cây nhị phân.
Cả 3 đáp án trên.
Queue;
Để 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;
2
1
3
4
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- > info!=NULL);
(p- > info==NULL);
(p- > next==NULL);
(p- > next!=NULL);
Dấu hiệu nào dưới đây cho biết danh sách liên kết đơn rỗng:
(p- > right==NULL);
(p- > next==NULL);
(p==NULL);
(p- > info==NULL);
Cài đặt danh sách bằng mảng có nghiã là
Dùng biến con trỏ lưu trữ các phần tử của danh sách.
Tất cả đều đú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.
Dùng bản ghi có hai thành phần để lưu trữ các phần tử của danh sách
Danh sách tuyến tính dạng ngăn xếp là
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp được thực hiện ở một đầu , và phép loại bỏ được thực hiện ở đầu kia.
Là một danh sách tuyến tính trong đó phép bổ sung sung một phần tử vào ngăn xếp được thực hiện ở một đầu, Và phép loại bỏ không thực hiện được.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở tại một vị trí bất kì trong danh sách.
Là một danh sách tuyến tính trong đó phép bổ sung một phần tử vào ngăn xếp và phép loại bỏ một phần tử khỏi ngăn xếp luôn luôn thực hiện ở một đầu gọi là đỉnh
Mỗi nút trong cây có tối đa:
2 nút con
Nhiều nút con
1 nút con
3 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à:
125
90
63
31
Khi thực hiện việc thêm một node x vào cây nhị phân tìm kiếm ta chỉ cần...
Tìm vị trí thích hợp cho x trên toàn bộ cây
Tìm vị trí thích hợp cho nhánh cây con ở bên trái
Tìm vị trí thích hợp cho nhánh cây con bên phải
Không đáp án đúng
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ị tí của nút con phải là
i-1
2*i
i+1
2*i + 1
Cây nhị phân khác rỗng là cây...
Tất cả các nút đều có nút con
Tất cả các nút đều có nút cha
Mỗi nút có không quá 2 nút con
Mỗi nút (trừ nút lá) đều có hai nút con
Nút có khóa nhỏ nhất trong cây nhị phân tìm kiếm khác rỗng là...
Nút con bên phải nhất
Nút con bên trái nhất
Nút gốc
Tất cả các nút
Cho cây nhị phân T, nút có địa chỉ 19 thì có nút cha ở địa chỉ nào
9
8
7
6
Trong biểu diễn dữ liệu dưới dạng cây, nút có cấp bằng 0 gọi là:
Không có đáp án nào đúng
Gốc
Lá
Phần tử cuối cùng trong cây
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. Nếu ta tìm kiếm trên cây nhị phân này thì trong trường hợp xấu nhất phải làm bao nhiêu phép so sánh
4
3
2
1
Duyệt cây nhị phân theo thứ tự giữa được thực hiện theo thứ tự:
Duyệt cây con trái theo thứ tự giữa, thăm gốc, duyệt cây con phải theo thứ tự giữa.
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ự trước, thăm gốc giữa, 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ự giữa, duyệt cây con phải theo thứ tự giữa.
Một cây nhị phân có chiều cao là 7, cây đó chỉ có 50 nút. Nếu lưu trữ kế tiếp thì lãng phí bao nhiêu ô ( nút gốc có mức 1, mỗi nút chiếm 1 ô ):
15 ô
25 ô
70 ô
77 ô
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)
Cấu trúc dữ liệu dạng danh sách(LIST)
Cấu trúc dữ liệu dạng StacK
Cấu trúc dữ liệu số nguyên
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 phải nút đó đều nhỏ hơn khóa cây con trái nút đó
Mọi khoá thuộc cây con phải nút đó đều nhỏ hơn khoá ứng với nút đó
Mọi khóa thuộc cây con phả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 bằng khóa cây con phả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
Duyệt cây nhị phân theo thứ tự sau đượ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, duyệt cây con phải theo thứ tự sau, thăm gốc.
Thăm gốc, duyệt cây con trái theo thứ tự sau, duyệt cây con phải theo thứ tự sau.
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.
Kết quả của đoạn chương trình sau là gì:
char c;
int n;
printf("%d%c",&n,&c);
Nếu gõ vào : ”10 T”.
B=8;
c=''.
A=0;
n=10
cho dãy số 27 40 -7 5 57, thực hiện bước thứ 1, khi áp dụng thuật toán sắp xếp lựa chọn để sắp xếp dãy theo thứ tự giảm, ta có được dãy mới là gì?
57 -7 27 5 40
40 27 -7 5 57
57 27 -7 5 40
57 5 -7 27 40
Nếu x là một biến toàn cục và x không phải là một con trỏ thì:
Miền nhớ dành cho x sẽ thay đổi bởi những thao tác với x trong tất cả các hàm, kể cả hàm main().
Miền nhớ dành cho x có thể thay đổi trong quá trình thực hiện chương trình.
Miền nhớ dành cho x chỉ có thay đổi bởi những thao tác với x bên trong hàm main().
Miền nhớ giành cho x không bị thay đổi trong quá trình thực hiện chương trình.
Các hoạt động cơ bản trên Danh sách liên kết vòng
Xóa
Chèn
Không có đáp án nào là đúng
Hiển thị
Ý tưởng của giải thuật tìm kiếm nhị phân:
So sánh X lần lượt với các phần tử thứ nhất, thứ hai,... của dãy cho đến khi gặp phần tử có khoá cần tìm.
Lần lượt chia dãy thành hai dãy con dựa vào phần tử khoá, sau đó thực hiện việc tìm kiếm trên hai đoạn đã chia.
Tìm kiếm dựa vào cây nhị tìm kiếm.
Tại mỗi bước tiến hành so sánh X với phần tử ở giữa của dãy,Dựa vào bước so sánh này quyết định giới hạn dãy tìm kiếm nằm ở nửa trên, hay nửa dưới của dãy hiện hành.
Cho cây nhị phân T, nút có địa chỉ 7 có 2 con ở địa chỉ nào:
14
15
16
19
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)=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
S(n)=1+2+4+…+(2.n+1) với n > =0
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 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 đó
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 bằng khóa cây con phải nút đó
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ữ Cobol.
Pascal
Ngôn ngữ C
Ngôn ngữ Assembler.
Giả sử có câu lệnh ch[]= "A". ch chứa bao nhiêu bytes
1
2
3
4
Mảng là
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à 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ó thể có kiểu riêng và chung tên gọi.
Với Stack được cài đặt bằng mảng, thủ tục sau để làm gì?
void MNullStack (Stack s) {
S.Top =Maxlenght + 1;
}
Thủ tục chèn một giá trị vào stack
Thủ tục khởi tạo Stack rỗng
Thủ tục cập nhật giá trị vào stack
Thủ tụcTạo mới một StacK
Danh sách tuyến tính là
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 rỗng.
Danh sách tuyến tính là một danh sách có dạng (a1, a2, ..., an).
Danh sách dạng được lưu dưới dạng mảng.
Để thêm một đối tượng x bất kỳ vào Stack, thao tác thường dùng là:
EMPTY(x).
POP(x).
PUSH(x).
TOP(x).
Cây 5 phân có nghĩa là gì?
Nút có cấp lớn nhất là 5
Cây đó có 5 nút
Mức có nhiều nút nhất là 5
Cây có chiều cao là 5
Kiểu dữ liệu float có thể xử lí dữ liệu trong phạm vi nào
-128 đến 127
0…65535.
3.4*10-38 đến 3.4*1038
-32768 đến 32767
Queue (hàng đợi) là kiểu danh sách tuyến tính mà phép loại bỏ thực hiện ở 1 đầu gọi là lối
front
real
infor
node
Không gian nhớ dùng để lưu trữ các node của danh sách liên kết kép:
Lưu trữ theo kiểu phân đoạn
Lưu trữ rởi rác trong bộ nhớ.
Lưu trữ theo kiểu phân trang.
Luôn lưu trữ liên tục trong bộ nhớ.
Danh sách liên kết đôi là gì?
1. Là một biến thể của Danh sách liên kết (Linked List), trong đó hoạt động duyệt qua các nút có thể được thực hiện theo hai chiều: về trước và về sau một cách dễ dàng khi so sánh với Danh sách liên kết đơn.
2. Là một biến thể của danh sách liên kết đơn, nhưng do 2 danh sách đơn cộng lại, Không có đáp án nào đúng
1 sai, 2 sai
1 đúng, 2 đúng
1 sai, 2 đúng
1 đúng, 2 sai
Trường hợp cơ sở của giải thuật đệ quy là
Trường hợp bài toán Pn, có quy mô đủ nhỏ để ta có thể giải trực tiếp.
Cả hai đáp án trên đều đúng
Trường hợp bài toán Pn, có quy mô rất lớn để ta có thể giải trực tiếp.
Cả hai đáp án trên đều sai
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);
}
Đưa con trỏ về cuối danh sách.
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
Cho cây nhị phân T có 70 nút cấp 2 ( có 2 con).Cây đó có bao nhiêu nút lá( không có con):
149
71
83
124
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
Kiểm tra danh sách rỗng
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ứ bảy là:
{0 1 2 3 4 5 6 7 8 9}
{0 1 2 3 4 5 9 6 8 7}
{0 1 2 3 4 5 9 6 8 7}
{0 1 2 3 4 5 6 9 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 2 3 8 5 9 6 1 4 7}
{0 2 4 8 5 9 6 1 3 7}
{0 2 4 5 8 9 6 1 3 7}
{0 1 2 8 5 9 6 4 3 7}
Cho cây nhị phân T. Phép duyệt thứ tự trước cho kết quả là
ADBCEFG
AEDBCFG
ABDECFG
AEBDCGF
Cho dãy số {4 7 0 9 2 5 3 1 8 6}. áp dụng phương pháp sắp xếp nổi bọt (Bubble sort) sau lần lặp đầu tiên của giải thuật ta có kết quả:{0 4 7 1 9 2 5 3 6 8}. Dãy số thu được sau lần lặp thứ ba là:
{0 1 2 3 4 7 5 9 6 8}
{0 4 7 1 9 2 5 3 6 8}
{0 1 2 4 7 3 9 5 6 8}
{0 1 4 7 2 9 3 5 6 8}
