Cấu trúc dữ liệu và giải thuật: Câu hỏi ôn tập tại lớp môn Nhập môn công nghệ phần mềm | Trường Đại Học Thái Nguyên

lOMoAR cPSD| 45740413
Câu 1: Có bao nhiêu thao tác trên cây nhị phân? Đáp án đúng là: Có 5 thao tác.
Câu 2: Cho một biểu diễn cây như sau:
Đâu là tập các lá của cây:
Đáp án đúng là: {4, 5, 6, 8, 9}.
Câu 3: Cho một biểu diễn cây như sau: Bậc của đỉnh e là
Đáp án đúng là: 2
Vì: đỉnh e có 2 con là i và j
Câu 4: Hãy cho biết độ cao của một cây được xác định như thế nào?
Đáp án đúng là: Là độ dài đường đi dài nhất từ gốc tới lá.
Vì: Theo định nghĩa: Trong một cây, độ cao của một đỉnh a là độ dài của đường đi
dài nhất từ a đến các lá của nó. Độ cao của gốc được gọi là độ cao của cây. Như
vậy, độ cao của một cây là độ dài đường đi dài nhất từ gốc đến lá. lOMoAR cPSD| 45740413
Câu 5: Các phần tử của cây thì được gọi là gì?
Đáp án đúng là: Là nút.
Câu 6: Đâu là phương pháp duyệt hậu thứ tự một cây nhị phân?
Đáp án đúng là: Duyệt cây con bên phải sau đó tới cây con bên trái rồi tới nút gốc.
Câu 7: Cho một biểu diễn cây như sau: Mức của đỉnh 3 là :
Đáp án đúng là: Luôn tồn tại một đường duy nhất từ gốc tới một đỉnh bất kỳ trong cây.
Câu 8: Các đỉnh của cây có bậc bằng 0 thì được gọi là gì?
Đáp án đúng là: Là Lá.
Vì: Theo khái niệm cơ bản về cây: Các đỉnh có bậc bằng không được gọi là lá của cây.
Câu 9: Quan hệ phân cấp giữa các nút trong cây được gọi là quan hệ gì?
Đáp án đúng là: Quan hệ cha - con.
Câu 10: Đỉnh trong của một cây là đỉnh như thế nào?
Đáp án đúng là: Là đỉnh có ít nhất 1 con.
Câu 11: Việc cài đặt ngăn xếp bằng mảng được thực hiện qua khai báo dưới đây: #define max N typedef int ElementType; struct Stack lOMoAR cPSD| 45740413 { int Top_id; ElementType Element[max]; }; Stack S;
Ý nghĩa đúng nhất của S là:
Trả lời: Tên của Stack.
Câu 12: Cho biểu thức số học dạng thông thường: (a+b)*(c-(d-e))
Đâu là biểu diễn biểu thức này dưới dạng biểu thức Balan? Chọn một: Trả lời: ab + cde --* Câu 13
Trong việc cài đặt ngăn xếp bằng mảng A[…], ta sử dụng một biến top_id để lưu
giữ đỉnh của ngăn xếp, nếu hiện tại ngăn xếp chưa có phần tử thì giá trị của top_id là bao nhiêu? Chọn một: Trả lời: -1
Câu 14: Việc cài đặt ngăn xếp bằng mảng được thực hiện qua khai báo dưới đây: #define max N typedef int ElementType; struct Stack { int Top_id; ElementType Element[max]; }; Stack S;
Ý nghĩa đúng nhất của ElementType là: Chọn một:
Trả lời: Kiểu dữ liệu của các phần tử trong Stack. lOMoAR cPSD| 45740413
Câu 15: Cho biểu thức số học dạng Balan như sau: 1 2 3 4 *- + 5 6 4 8 – – + *.
Việc tính toán giá trị biểu thức này khi dùng Stack được cài đặt bằng mảng thì
phần tử được đẩy vào Stack lần thứ 10 có giá trị là bao nhiêu? Chọn một: Trả lời: 4
Câu 16: Cho biểu thức số học dạng Balan như sau: abc +* de /- với các giá trị a=1;
b=2; c=3; d=8; e=4; thì giá trị của biểu thức là: Chọn một: Trả lời: 3
Câu 17: Cấu trúc dữ liệu nào tương ứng với nguyên lý LIFO. Chọn một: Trả lời: Stack.
Câu 18: Cho biểu thức số học dạng thông thường: (a+b)*(c-(d/e))
Đâu là biểu diễn biểu thức này dưới dạng biểu thức Balan? Trả lời: ab + cde /-*
Câu 19: Cho biểu thức số học dạng Balan như sau: 1 2 3 4 *- + 5 6 4 8 – – + *.
Việc tính toán giá trị biểu thức này khi dùng Stack được cài đặt bằng mảng thì số
phần tử tối thiểu của mảng phải là bao nhiêu? Chọn một: Trả lời: 5
Câu 20: Khi dùng Stack được cài đặt bằng mảng để đổi số tự nhiên N = 70 (hệ cơ
số 10) sang hệ nhị phân thì số phần tử tối thiểu của mảng phải là bao nhiêu? Chọn một Trả lời: 7
Câu 21: Cho biểu thức số học dạng Balan như sau: 1 2 3 4 *- + 5 6 4 8 – – + *.
Việc tính toán giá trị biểu thức này khi dùng Stack được cài đặt bằng mảng thì
phần tử được đẩy vào Stack lần thứ 8 có giá trị là bao nhiêu? Trả lời: 5
Câu 22: Cho biểu thức số học dạng thông thường: a * (b + c) - d/e
Đâu là biểu diễn biểu thức này dưới dạng biểu thức Balan? lOMoAR cPSD| 45740413 Chọn một: Trả lời: abc + * de /-
Câu 23: Trong việc cài đặt ngăn xếp bằng mảng A[…], nếu hiện tại ngăn xếp có n
phần tử thì phần tử mới nhất vừa được đưa vào ngăn xếp vị trí nào trong mảng?
Đáp án đúng là: A[n-1].
Câu 24: Tiêu chuẩn để đánh giá các nguyên tắc Planning là gì?
Trả lời: Khả năng phục vụ (throughput), thời gian trả lời trung bình(mean trả lời (variance in response
time) và sự khác biệt thời gian.
Câu 25: Khi hệ thống phải truy xuất dữ liệu khối lượng lớn thì thuật toán lập lịch nào sau đây là hiệu quả?-- SCAN và C-SCAN.
Câu 26: Trong đĩa cứng Cylinder là gì?----- Các đường tròn có cùng bán kình trên đĩa.
Câu 27: Trong đĩa cứng sector là gì?---- Các cung tròn trên các mặt đĩa.
Câu 28: Công việc nào sau đây thuộc về cơ chế điều khiển file trong hệ thống File của hệ điều
hành?---- Bảo vệ dữ liệu.
Câu 29: Thế nào là tổ chức file theo dãy chỉ số?---- Các bản ghi nối tiếp về logic không nhất thiết liên
tiếp về vật lý. Trong hệ thống sử dụng các chỉ mục riêng trỏ đến vị trí vật lý của bản ghi. Tổ chức này
thường áp dụng trong đĩa từ.
Câu 30: Có mấy hình thức phân bố file?----2
Câu 31: Trong hệ thống I/O ổ đĩa từ, thời gian để đầu đọc đến đúng track cần thiết trên một đĩa gọi là?------ Seek time.
Câu 32: Tệp tin thường được lưu trữ ở đâu?----- Bộ nhớ ngoài.
Câu 33: Trong công nghệ đĩa cứng có bao nhiêu phương pháp Planning?----- 2
Câu 34: Xét không gian địa chỉ có 8 trang, mỗi trang có kích thước 1K ánh xạ vào bộ nhớ có 32
khung trang, Hỏi phải dùng bao nhiêu bít để mã hóa địa chỉ vật lí của không gian địa chỉ này ?-----15 bit
Câu 35: Thời gian trễ khi truy cập ổ đĩa từ là?--- Thời gian để di chuyển đầu từ về vùng đĩa cần đọc.
Câu 36: Hình thức tổ chức file theo chuỗi block, cách thức tổ chức dữ liệu dựa trên cấu trúc dữ liệu
nào?-- Danh sách liên kết (Link List).. -
Câu 37: Hệ thống file được tổ chức như thế nào?--- Tổ chức logic theo dạng hình cây.
Câu 38: Phần mở rộng của tên tệp (nếu có) thể hiện thông tin gì?--- Kiểu tệp tin.
Câu 39: Trong HĐH MS-DOS tệp tin có độ dài tối đa là bao nhiêu kí tự?---- 8 lOMoAR cPSD| 45740413
Câu 40: Cách cài đặt hệ thống tập tin nào không bị lãng phí do phân mảnh ngoại vi, không cần dùng
bảng FAT nhưng truy xuất ngẫu nhiên sẽ chậm và Khó bảo vệ số hiệu khối tập tin?-------- Cấp phát
liên tục dùng danh sách liên kết.
Câu 41: Trong hệ điều hành Windows tệp tin nào sau đây KHÔNG hợp lệ?---- van*hoC.txt
Câu 42: Trong bảng FAT của hệ thống tập tin MS-DOS người ta mô tả loại đĩa bằng cách nào?-----
Dùng 2 entry đầu tiên của bảng FAT
Câu 43: Một đĩa mềm có 2 mặt, mỗi mặt có 40 track, mỗi track gồm 9 sector, mỗi sector gồm 512
byte hỏi dung lượng của đĩa mềm là bao nhiêu?----- 360KB
Câu 44: Hãy cho biết kết quả duyệt trung thứ tự (duyệt nút gốc giữa) của cây nhị phân sau.
Câu trả lời đúng là: BADCE.
Câu 45: Cho một biểu diễn cây như sau: Mức của đỉnh 3 là :
Câu trả lời đúng là: 1
Câu 46: Cho thuật toán sau int LinearSearch (float M[], int N, float X)
{ int k = 0; M[N] = X; while (M[k] != X) //n+1 lan k++; if (k < N) return (1); else return (- 1); lOMoAR cPSD| 45740413 }
Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Câu trả lời đúng là: Số phép gán: Gmax = N
Số phép so sánh: Smax = N + 1
Câu 47: Khi xóa một nút của cây nhị phân tìm kiếm, trường hợp nút cần xóa là nút có đủ hai nút gốc cây con.
Đâu là định nghĩa đúng nhất cho khái niệm "nút tiền nhiệm"?
Câu trả lời đúng là: Nút cực phải của cây con trái
Câu 48: Cho thuật toán tìm kiếm sau, với điều kiện các giá trị của mảng đã được sắp theo thứ tự tăng dần: typedef KeyType; int
LinearSearch(KeyType X, dataArray R,int n) { int i; for(i = 0;i < n;i++) {
if(R[i]== X) return(i); else if(X < R[i]) return(–1); } return(–1); }
Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X:
Câu trả lời đúng là: Số phép so sánh: Smax = 3N
Câu 49: Cho thuật toán tìm kiếm sau, với điều kiện các giá trị của mảng đã được sắp theo thứ tự tăng dần: typedef KeyType; int
LinearSearch(KeyType X, dataArray R,int n)
{int i; for(i = 0;i < n;i++) {
if(R[i]== X) return(i); else if(X < R[i]) return(–1); } return(–1); }
Khi đó, nếu tìm giá trị X = 85 trong mảng được sắp xếp theo thứ tự tăng dần như sau:
10, 20, 30, 40, 50, 60,70, 80, 90, 100
Chọn câu đúng nhất trong trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng X
Câu trả lời đúng là: Số phép so sánh: Smax = 27 lOMoAR cPSD| 45740413
Câu 50: Cho hàm tìm kiếm tuần tự như sau typedef
KeyType; int Sequential_Search(dataArray R,KeyType X,int n); { int i;
i=0; while((R[i]!= X)&&(i < n)) { i++; } if(i < n) return (1); else return(–1); }
Chọn khẳng định đúng nhất:
Câu trả lời đúng là: Hàm sẽ trả về -1 nếu không tìm thấy phần tử có giá trị là X
Câu 51: Đâu là một điều kiện của việc xóa một nút của cây nhị phân tìm kiếm?
Câu trả lời đúng là: Cây nhận được sau khi xóa là cây nhị phân tìm kiếm
Câu 52: Xét thủ tục sau:
int TimKiemNP (int M[], int First, int Last, int X) {
if (First > Last) return (-1); int Mid = (First +
Last)/2; if (X == M[Mid]) return (Mid); if (X <
M[Mid]) return(TimKiemNP (M, First, Mid – 1, X));
else return(TimKiemNP (M, Mid + 1, Last, X)); }
Lựa chọn câu đúng nhất để mô tả thủ tục trên
Câu trả lời đúng là: Hàm tìm kiếm đệ quy phần tử có giá trị là X trên mảng các phần tử từ chỉ
số từ First đến chỉ số Last.
Câu 53: Đâu là cây nhị phân tìm kiếm trong các cây nhị phân sau? Câu trả lời đúng là: lOMoAR cPSD| 45740413
Câu 54: Cho thuật toán tìm kiếm sau typedef
KeyType; int Sequential_Search(dataArray R,KeyType X,int n); { int i;
i=0; while((R[i]!= X)&&(i < n)) { i++; } if(i < n) return (1); else return(–1); }
Khi đó, nếu tìm giá trị X = 34 trong mảng sau: 11, 23, 33, 34, 35, 62,71, 80, 95, 100 Chọn câu đúng nhất cho số
phép so sánh trong vòng lặp while:
Câu trả lời đúng là: Số phép so sánh: S = 8.
Câu 55: Bạn hãy cho biết độ phức tạp của giải thuật tìm kiếm tuần tự.
Câu trả lời đúng là: O(n).
Câu 56: Cho thuật toán tìm kiếm nhị phân sau:
Bước 1: đặt First = 0 và Last = n – 1;
Bước 2: Found = –1;//Found là biến lưu vị trí tìm thấy X trong mảng
Bước 3: while((First <= Last)&&(Found == –1)) { Mid =(First + Last)/2;
if(X < R[Mid]) Last = Mid – 1; else if(X >
R[Mid]) First = Mid + 1; else Found = Mid; }
Đâu là điều kiện của mảng R[] để thực hiện thuật toán?
Câu trả lời đúng là: Được sắp tăng
Câu 57: Đoạn mã giả dưới đây mô tả thuật toán gì? Thuật toán: B1: k = 0
B2: IF (M[k] != X) AND (k < N) B2.1: k++ B2.2: Lặp lại B2 B3: IF k < N
Thông báo tìm thấy tại vị trí k B4: ELSE Không tìm thấy. lOMoAR cPSD| 45740413 B5: Kết thúc
Câu trả lời đúng là: Tìm tuyến tính phần tử có giá trị X.
Câu 58: Cho thuật toán tìm kiếm trên cây nhị phân tìm kiếm như sau:
Bước 1: đặt con trỏ Root = BST;
Bước 2: nếu (Root = NULL) hoặc (Root –> infor = X) Kết thúc thuật toán;
Bước 3: ngược lại:nếu (Root –> infor > X) Root = Root –> left;
//tìm X ở cây con bên trái
Bước 4: ngược lại nếu(Root –> infor < X) Root = Root –> right;
//tìm X ở cây con bên phải
Bước 5: lặp lại bước 2;
Và cây nhị phân tìm kiếm sau:
Khoá cần tìm kiếm X = 40 thì số lần thực hiện Bước 2 là?
Câu trả lời đúng là: 3
Câu 59: Tên của thuật toán sắp xếp mà tư tưởng của nó là phân hoạch dãy ban đầu thành các dãy con có vị trí
tương đối với một phần tử trong dãy?
Câu trả lời đúng là: Quick sort.
Câu 60: Cho các bước của thuật toán sắp dãy sắp xếp một dãy a , a ,…, a theo thứ tự tăng dần theo thuật 1 2 n
toán Selection sort như sau : Bước 1: i = 0;
Bước 2: tìm phần tử A[min] nhỏ nhất trong dãy từ A[i] tới A[n–1]
Bước 3: hoán vị A[min] và A[i]
Bước 4 : nếu i <= n – 2 thì i = i + 1, lặp lại bước 2, ngược lại thì dừng
Trường hợp tốt nhất, khi dãy phần tử cần sắp xếp có thứ tự tăng dần:
Câu trả lời đúng là: Số phép gán: S gán = 0
Câu 61Bạn hãy cho biết độ phức tạp của việc sắp xếp tăng dần một dãy số bằng thuật toán Quick sort trong
trường hợp tồi nhất với n là số phần tử của dãy. lOMoAR cPSD| 45740413
Câu trả lời đúng là: O(n2).
Câu 62: Cho dãy số gồm 8 phần tử: 5, 3, 7, 4, 1, 2, 9, 12.
Ta có thể chia dãy trên thành ít nhất bao nhiêu dãy con không giảm?
Câu trả lời đúng là: 4
Câu 63: Bạn hãy cho biết độ phức tạp của việc sắp xếp tăng dần một dãy số bằng thuật toán Heap sort trong
trường hợp tồi nhất với n là số phần tử của dãy.
Câu trả lời đúng là: O(nlog 2n)
Câu 64: Cho các bước của thuật toán sắp dãy sắp xếp một dãy a , a ,…, a theo thứ tự tăng dần như sau : 1 2 n Bước 1: i = 1; Bước 2:đặt x = A[i]; j = i – 1;
Bước 3: while (j >= 0) && (x < A[j]) A[j + 1] = A[j]; j––;
Bước 4: đặt A[j + 1] = x ; i++;
Bước 5: nếu i < = n – 1 lặp lại bước 2 ngược lại thì kết thúc Bạn cho biết đây là
thuật toán sắp xếp nào?
Câu trả lời đúng là: Chèn trực tiếp – Insertion sort.
Câu 65: Bạn hãy cho biết độ phức tạp của việc sắp xếp tăng dần một dãy số bằng thuật toán chèn trực tiếp
trong trường hợp dãy đã được sắp tăng với n là số phần tử của dãy?
Câu trả lời đúng là: O(n).
Câu 66: Theo thuật toán Merge sort, trong lần phân hoạch đầu tiên thì số phân hoạch theo phương pháp trộn
trực tiếp so với số phân hoạch theo phương pháp trộn tự nhiên là?
Câu trả lời đúng là: Không biết trước, tùy vào tình trạng của dãy ban đầu
Câu 67: Thủ tục mô tả thuật toán sắp xếp chọn (Selection Sort): void SapXepChon (T M[], int N) { int K = 0, PosMin; int Temp; while (K < N-1) {
T Min = M[K]; PosMin = K; for (int Pos = K+1;
Pos < N; Pos++) if (Min > M[Pos]) { Min = M[Pos]; PosMin = Pos } lOMoAR cPSD| 45740413
................................... [1]
................................... [2]
................................... [3] K++; } return; }
Chọn câu lệnh thích hợp để đưa vào [1], [2], [3] với mục tiêu hoán vị M[K] và M[PosMin]
Câu trả lời đúng là: Temp = M[K] ; M[K] = M[PosMin]; M[PosMin] = Temp ;
Câu 68: Cho các bước của thuật toán sắp dãy sắp xếp một dãy a , a ,…, a theo thứ tự tăng dần theo thuật 1 2 n
toán Insertion sort như sau : Bước 1: i = 1; Bước 2:đặt x = A[i]; j = i – 1;
Bước 3: while (j >= 0) && (x < A[j]) A[j + 1] = A[j]; j––;
Bước 4: đặt A[j + 1] = x ; i++;
Bước 5: nếu i < = n – 1 lặp lại bước 2 ngược lại thì kết thúc
Trường hợp tốt nhất, khi dãy phần tử cần sắp xếp có thứ tự tăng:
Câu trả lời đúng là: Cho các bước của thuật toán sắp dãy sắp xếp một dãy a , a ,…, a theo thứ tự tăng 1 2 n
dần theo thuật toán Selection sort như sau : – 1 Số phép so sánh: S so sánh = n
Câu 69: Theo thuật toán Quick sort, về nguyên tắc thì điều kiện nào sau đây dùng để chọn khóa chốt?
Câu trả lời đúng là: Chọn ngẫu nhiên
Câu 70: Thủ tục mô tả thuật toán sắp xếp chèn trực tiếp (Insertion sort): #define Max_Size … typedef
Kieu_du_lieu KeyType; typedef struct KeyArray {
KeyType Array[Max_Size]; int n; };
KeyArray Sortinsert( KeyArray a) { int i,j; lOMoAR cPSD| 45740413
KeyType x; i = 1; while ( i <= a.n – 1 ) { x =
a.Array[i] ; j = i – 1; while (( j >= 0 )&&(x < a.Array[j]))
{a.Array[j + 1] = a.Array[j]; j ––; } ………… ; i++; } return a; }
Chọn câu lệnh thích hợp để đưa vào (............) với mục tiêu đưa giá trị cần chèn vào vị trí.
Câu trả lời đúng là: a.Array[j+1] = x
Câu 71: Để cài đặt thàng đợi bằng danh sách liên kết, trước tiên ta phải định nghĩa kiểu phần tử cho danh
sách. Mỗi phần tử của danh sách liên kết phải có bao nhiêu trường: ---2
Câu 72: Khi cài đặt hàng đợi bằng mảng, nếu ta đặt tên các biến như sau: biến T thể hiện vị trí đuôi, biến H thể
hiện vị trí đầu. Thao tác thêm 1 phần tử vào hàng đợi trong trường hợp: “giá trị của T đúng bằng kích thước
của mảng trong khi số lượng phần tử của hàng đợi vẫn nhỏ hơn kích thước của mảng” sẽ:
---Giá trị T được gán bằng 1. Câu 73:
Việc bổ sung thêm phần tử vào hàng đợi được thực hiện bằng đoạn mã dưới đây: void
ENQUEUE(QUEUE_ARRAY q, ELEMENT e) {
if (IS_FULL(q)!= 0) printf("hang doi day khong the chen
them"); else{ if (q.T == q.capacity–1) q.T=0; else …………..; q.ele[q.T]=e; q.S=q.S+1; } }
Hãy lựa chọn câu trả lời đúng nhất nội dung điền vào chỗ trống (.........) của đoạn mã trên: --------q.T=q.T+1
Câu 74: Cấu trúc dữ liệu nào khi cài đặt bằng mảng ta phải cần 2 biến vị trí để quản lý danh sách các phần tử ----------Hàng đợi. lOMoAR cPSD| 45740413
Câu 75: Kiểu dữ liệu nào thuộc loại kiểu dữ liệu cơ bản?--------- POINTER.
Câu 76: Việc kiểm tra hàng đợi có rỗng không được thực hiện bằng đoạn mã dưới đây: int IS_EMPTY(QUEUE_ARRAY q) { if (………) return 1; else return 0; }
Hãy lựa chọn câu trả lời đúng nhất nội dung điền vào chỗ trống (.........) của đoạn mã trên: ----------q.S == 0
Câu 77: Cho danh sách L = (0, 3, 7, 2, 4, 9). Đâu là danh sách con của L? ------- (0, 3, 7, 2)
Câu 78: Cho danh sách L = (1, 5, 3, 2, 4, 0, 6). Thủ tục Delete_L(Pos: position ; var List: ListType) để xóa
một phần tử tại vị trí Pos khỏi danh sách List. Khi đó nếu ta thực hiện liên tiếp Delete_L(2,L), Delete_L(4,L) thì
kết quả sẽ được danh sách L như sau? -------(1, 3, 2, 0, 6)
Câu 79: Đâu là kiểu dữ liệu cơ bản trong các kiểu dữ liệu dưới đây? ----- Kiểu số nguyên.
Câu 80: Kiểu dữ liệu cơ bản là gì? ------Là kiểu dữ liệu có sẵn trên hầu hết các máy tính và được hỗ trợ trong
hầu hết các ngôn ngữ lập trình.
Câu 81: Lựa chọn câu đúng nhất về danh sách liên kết đôi (Doubly Linked List) -------Câu trả lời đúng là:
Vùng liên kết của một phần tử trong danh sách liên đôi có 02 mối liên kết, 01 với phần
tử trước và 01 với phần tử sau nó trong danh sách.
Câu 82: Khi cài đặt hàng đợi bằng mảng, nếu ta đặt tên các biến như sau: biến T thể hiện vị trí đuôi, biến H
thể hiện vị trí đầu. Thao tác lấy ra 1 phần tử của hàng đợi trong trường hợp: “giá trị của H đúng bằng kích
thước của mảng” sẽ: Câu trả lời đúng là: Giá trị H được gán bằng 1
Câu 83: Với cấu trúc dữ liệu như sau
typedef struct DNode {int Key; DNode * NextNode;
DNode * PreNode; } DOneNode; typedef
DOneNode * DPointerType; typedef struct
DLLPairNode {DPointerType DLLFirst; lOMoAR cPSD| 45740413 DPointerType DLLLast; } DLLPType;
Hãy cho biết hàm sau dùng để làm gì? void
DLLTravelling (DLLPType DList) {DPointerType
CurrNode = DList.DLLFirst; while (CurrNode !=
NULL) {cout << CurrNode->Key;
CurrNode = CurrNode->NextNode ; } return; }
---Đáp án đúng là: Duyệt qua các nút trong danh sách và hiển thị nội dung của mỗi nút.
Câu 84: Cho danh sách L = (1, 8, 9, 2, 4, 0, 6, 7, 5). Thủ tục DSC_L(Pos1; Pos2: position ; var List:
ListType) để đưa ra một danh sách con của List bắt đầu từ vị trí Pos1 đến vị trí Pos2 và trả giá trị cho List.
Thủ tục Delete_L(Pos: position ; var List: ListType) để xóa một phần tử tại vị trí Pos khỏi danh sách List. Thủ
tục Insert_L(Pos: position ; X: Item; var List: ListType) để thêm một phần tử X vào vị trí Pos trong danh
sách List. Khi đó nếu ta thực hiện liên tiếp DSC_L(2,7,L), Delete_L (2,L), Insert_L(2,3,L) thì kết quả sẽ được
danh sách L như sau? Câu trả lời đúng là: (8, 3, 2, 4, 0, 6) Câu 85: Hãy cho biết kết quả của phép MOD hai số nguyên có kiểu gì? Kiểu số nguyên”. Đáp án đúng là:
Câu 86: Khi cài đặt hàng đợi bằng mảng, nếu ta đặt tên các biến như sau: biến T thể hiện vị trí đuôi, biến H
thể hiện vị trí đầu. Thao tác thêm 1 phần tử vào hàng đợi sẽ:------- Tăng T lên 1 đơn vị.
Câu 87 : Hãy cho biết ưu điểm của các kiểu dữ liệu trừu tượng.------ Đáp án đúng là:
Giúp cho người lập trình không phải quá quan tâm đến các cách thức biểu diễn cụ thể các dữ liệu đó trên máy tính.
Câu 88: Biểu diễn danh sách bằng mảng được mô tả như sau: #define Max_Size N typedef Kieu_du_lieu E_Type; struct ListType
{E_Type Element[Max_Size]; int Size; } List;
Điều kiện danh sách đầy là:
Đáp án đúng là: List.Size = Max_Size.
Đáp án đúng là: Kiểu dữ
Đáp án đúng là: Độ dài của danh sách bằng 0. lOMoAR cPSD| 45740413
Câu 89: Yêu cầu khi chọn kiểu dữ liệu cho chương trình là? liệu cần sát với kiểu giá
trị của các thông tin đó trong thực tế. Câu 90 Cấu trúc dữ liệu nào tương ứng với
nguyên lý FIFO -----Queue Câu 91: Một danh sách rỗng khi: Câu 92: Lựa chọn
định nghĩa đúng nhất về danh sách?
Đáp án đúng là: Danh sách là
tập hợp các phần tử có kiểu dữ liệu xác định và giữa chúng có một mối liên hệ nào đó.
Câu 93: Việc lấy một phần tử từ hàng đợi được thực hiện bằng đoạn mã dưới đây:
ELEMENT DEQUEUE(QUEUE_ARRAY q) {
ELEMENT e; if (IS_EMPTY(q)!= 0) printf("hang doi rong
khong the lay phan tu ra"); else { e = q.ele[q.H]; q.H =q.H + 1; q.S = ........; if (q.H == q.capacity) q.H = 0; } return e; }
Hãy lựa chọn câu trả lời đúng nhất nội dung điền vào chỗ trống (.........) của đoạn mã trên:
Câu trả lời đúng là : q.S - 1.
Câu 94: Trong việc ứng dụng danh sách liên kết để tính toán giá trị của một đa thức 1 ẩn bậc n, để lưu trữ đa
thức trong danh sách liên kết thì mỗi nút của danh sách thường có mấy trường: câu trả lời là:3
Câu 95: Định nghĩa nào là đúng với danh sách liên kết?===== Đáp án đúng là: Danh sách liên kết là tập hợp
các phần tử mà giữa chúng có một sự nối kết với nhau thông qua vùng liên kết của chúng.
Câu 96: Định nghĩa cấu trúc dữ liệu của danh sách liên kết đôi được mô tả như sau: Typedef
Kieu_du_lieu ElementType; typedef struct NodeType { ElementType Data;
struct NodeType *next, *prev; }Node ;
Hãy chọn mô tả đúng nhất cho khai báo NodeType *next
Đáp án đúng là: Vùng liên kết quản lý địa chỉ phần tử kế tiếp. lOMoAR cPSD| 45740413
Câu 97: Việc cài đặt hàng đợi bằng mảng được thực hiện qua khai báo dưới đây: #define max N typedef int ELEMENT; struct QUEUE_ARRAY { ELEMENT ele[max]; int capacity, H, T, S; } q;
Ý nghĩa đúng nhất của S là:
Đáp án đúng là: Số phần tử hiện thời của hàng đợi.
Câu 98: Việc cài đặt hàng đợi bằng mảng được thực hiện qua khai báo dưới đây: #define max N typedef int ELEMENT; struct QUEUE_ARRAY { ELEMENT ele[max]; int capacity, H, T, S ; } q;
Ý nghĩa đúng nhất của ELEMENT là:
Đáp án đúng là: Kiểu dữ liệu của các phần tử trong Hàng đợi.
Câu 99 : Khi lấy ra một phần tử của hàng đợi thì phần tử đó ở vị trí: Đáp án đúng là:
Đầu tiên của hàng đợi.
Câu 100: Hãy cho biết ý nghĩa của kiểu dữ liệu logic (BOOLEAN) để biểu diễn Đáp án đúng là: Dùng
các giá trị logic bao gồm 2 giá trị đúng (true) và sai (false).
Câu 101: Kiểu dữ liệu con trỏ được dùng để làm gì? các con trỏ Đáp án đúng là: Được dùng để lưu
đến bất kỳ một kiểu dữ liệu nào khác.
Câu 102: Kiểu truy cập các phần tử trong một mảng là kiểu truy cập nào trong các kiểu dưới đây? Đáp án đúng
là: Kiểu truy cập ngẫu nhiên.
Câu 103: Hãy cho biết giá trị của “con trỏ” là gì?--vùng bộ nhớ Đáp án đúng là: Là địa chỉ đến một nhất định.
Câu 104: Việc cài đặt hàng đợi bằng mảng được thực hiện qua khai báo dưới đây: lOMoAR cPSD| 45740413 #define max N typedef int ELEMENT; struct QUEUE_ARRAY { ELEMENT ele[max]; int capacity, H, T, S; } q;
Ý nghĩa đúng nhất của q là:
Đáp án đúng là: Tên của hàng đợi.
Câu 105: Đâu là một trong những tiêu chí khi chọn ngôn ngữ diễn đạt giải thuật ? Đáp
án đúng là: Gần với ngôn ngữ lập trình hiện có.
Câu 106: Trong định nghĩa danh sách liên kết đôi, mỗi nút gồm bao nhiêu thành phần? Câu trả lời đúng là: 3 thành phần
Câu 107: Chọn định nghĩa đúng nhất cho từ Giải thuật? Câu trả lời đúng là: Là một tập hợp
hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái
ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.
Câu 108: Khi cài đặt danh sách bằng mảng, với độ dài là n thì thao tác chèn một phần tử vào danh sách có
độ phức tạp------- O(n)
Câu 109: Hãy cho biết kiểu dữ liệu trừu tượng là gì?
Đáp án đúng là: Là kiểu dữ liệu mới
do người dùng tự định nghĩa. Câu 110 Câu 111 Câu 112 Câu 113 Câu 114 Câu 115