39 câu hỏi
Các thuộc tính của một kiểu dữ liệu
Tên kiểu dữ liệu
Kích thước lưu trữ
Miền giá trị
Tập các toán tử tác động lên kiểu dữ liệu
Tất cả các thuộc tính đưa ra
Miền giá trị của Kiểu số nguyên là:
-32768 .. 32767
-32767 .. 32768
0..32767
0..32768
Kích thước lưu trữ kiểu số nguyên là
4 byte
6 byte
2 byte
1 byte
Tập các toán tử kiểu số nguyên là
+, -, , /, %, các phép so sánh, div ,mod
+, -, , /, %, các phép so sánh
+, -, , /, % ,true,false
+, -, , /, %
Tên kiểu nguyên là:
Integer
Boolean
Byte
Real
Khi khai báo type T = min..max
Trong đó min và max là cận dưới và cận trên của khoảng T là kiểu gì?
Kiểu integer
Kiểu liệt kê
Kiểu đoạn con
Không có kiểu này
Đâu là kiểu dữ liệu có cấu trúc
Kiểu array (mảng)
Kiểu record (bản ghi)
Tất cả các kiểu đưa ra
Kiểu con trỏ
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 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
thuật toán cần có một hoặc nhiều dữ liệu ra (output) ,dữ liệu vào (input).
.Đặc trưng của thuật toán
Tất cả ý nêu ra
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
Mỗi bước của thuật toán cần phải được mô tả một các chính xác
Mỗi thuật toán có bộ dữ liệu vào ,ra tương ứng 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
Đặ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 dừng
Tính xác định
Tính khả thi
Để viết chương trình chỉ để sử dụng một số ít lần và cái giá của thời gian viết chương trình vượt xa cái giá của chạy chương trình thì ta chọn thuật toán:
Thuật toán sử dụng tiếp kiện nhất nguồn tài nguyên của máy tính, và đặc biệt, chạy nhanh nhất có thể được.
Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)
Cả hai tiêu chí nêu ra
Khi viết các chương trình (thủ tục hoặc hàm ) để sử dụng nhiều lần, cho nhiều người sử dụng ta chọn thuật toán:
Cả hai tiêu chí nêu ra
Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình)
Thuật toán sử dụng tiếp kiện nhất nguồn tài nguyên của máy tính, và đặc biệt, chạy nhanh nhất có thể được.
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(1),O(nlog2n),O(n),O(log2n)
O(log2n),O(n),O(nlog2n),O(1)
O(1),O(log2n),O(n),O(nlog2n)
Qui tắc tổng Xác định độ phức tạp tính toán
Giả sử T1(n) và T2(n) là thời gian thực hiện của hai giai đoạn chương trình P1 và P2 mà T1(n: O(f(n)); T2(n: O(g(n)) thì thời gian thực hiện đoạn P1 rồi P2 tiếp theo sẽ là
T1(n) + T2(n: O(Min(f(n),g(n))).
T1(n) + T2(n: O(max(f(n),g(n))).
T1(n) + T2(n: O((f(n)+g(n))).
T1(n) + T2(n: O((f(n) or g(n))).
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)
Xác định độ phức tạp tính toán
Nếu tương ứng với P1 và P2 là T1(n: O(f(n)), T2(n: O(g(n)) thì thời gian thực hiện P1 và P2
lồng nhau sẽ là
T1(n)T2(n: O(f(n)/g(n))
T1(n)T2(n: O(f(n)g(n))
T1(n)T2(n: O(f(n)and g(n))
T1(n)T2(n: O(f(n)+g(n))
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(2)
O(log2(n))
O(1)
O(n
thời gian thực hiện lệnh hợp thành(Begin.. end) được xác định bởi Chú ý: (log2n) = Log cơ số 2 của n; n^2 = n mũ 2
O(log2(n)
Quy tắc nhân
quy tắc tổng
Hằng số
Nếu S1 và S2 là các câu lệnh và E là biểu thức logic thì If E Then S1 Else S2
Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là
O(Min (f()n), g(n)))
O(max (f()n), g(n)))
O(or( (f()n), g(n)))
O(And (f()n), g(n)))
GiảI thuật đệ quy la:
Nếu lời giải của của một bài toán T được giải bằng lời giải của một bài toán T1 khác T , thì lời giải đó được gọi là lời giải đệ quy
Nếu lời giải của của một bài toán T được giải bằng lời giải của một bài toán T1 mà T1 giảI được thì lời giải đó được gọi là lời giải đệ quy
Nếu lời giải của của một bài toán T được giải bằng lời giải của một bài toán T1, có dạng giống như T, thì lời giải đó được gọi là lời giải đệ quy
Nếu lời giải của của một bài toán T được giải bằng lời giải của một bài toán T1 mà T1 có độ phức tạp khác T , thì lời giải đó được gọi là lời giải đệ quy
A. sau một vàI lần tách đôI từ điển
Khi xác định từ cần tìm nằm ở nửa sau của từ đIún
Khi xác định từ cần tìm nằm ở nửa trước của từ đIển
sau nhiều lần tách đôi từ điển chỉ còn một trang
Một giảI thuật đệ quy xảy ra trường hợp suy biến khi nào
Khi không thể giảI quyết được giảI thuật.
Sau một số lần có lời gọi đệ quy bài toán còn lại sẽ được giải quyết theo một cách khác
Khi kết quả của giảI thuật bằng giá trị 0
Sau một số lần có lời gọi đệ quy.
.Đặc đIúm nào của giảI thuật viết bằng đệ quy là sai trong các đặc đIúm sau
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.
Tất cả đều sai
Trong thủ tục đệ quy có lời gọi đến chính thủ tục đó
sau một số lần gọi đệ quy bàI toán có giá trị bằng 0
Đặc điểm của giảI thuật đệ quy
Tất cả đều đúng
Trong thủ tục đệ quy có lời gọi đến chính thủ tụ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ó 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
Một giá trị kiểu char chiếm bao nhiêu bộ nhớ
1byte
4byte
3byte
2byte
Danh sách tuyến tính là:
danh sách tuyến tính là một 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.
danh sách tuyến tính là một danh sách rỗng
ưu đIểm của việc càI đặt danh sách bằng mảng
việc truy nhập vào phần tử của mảng được thực hiện trực tiếp dựa vào địa chỉ tính được(chỉ số), nên tốc độ nhanh và đồng đều đối với mọi phần tử.
Khi khai báo một mảng ta phải xác định số lượng phần tử của mảng,nên khống chế số luợng của đối tuợng mà danh sách lưu trữ.
Tất cả đều đúng
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 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 .
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 được thực hiện ở một đầu , và phép loại bỏ được thực hiện ở đầu kia.
Danh sách tuyến tính dạng ngăn xếp làm việc theo nguyên tắc
FILO(first in last out)
FIFO( first in first out)
FOLO( fisrt out last out)
LILO(last in last out)
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 gCâu Record)
Mảng (array)
đị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đượ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 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) 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).
hàng đợi còn được gọi là danh sách kiểu
LIFO
FILO
LOLO
FIFO
Khi loại bỏ một phần tử ra khỏi hàng đợi Thì:
Cần khởi tạo lại hàng đợi
Nếu hàng đợi chỉ có một phần tử thì không thể thực hiện việc loại bỏ
Nếu hàng đợi rỗng thì không thể thực hiện việc loại bỏ
Nếu hàng đợi đầy thì không thể thực hiện việc loại bỏ
Khi bổ sung một phần tử mới vào hàng đợi cần kiểm tra
Hàng đợi có bao nhiêu phần tử
Hàng đợi có bao nhiêu giá trị bằng 0
Hàng đợi có rỗng không
Hàng đợi có đầy không
ý tưởng phương pháp sắp xếp nổi bọt (bubble sort) là:
Chọn phần tử bé nhất xếp vào vị trí thứ nhất,tương tự đối với phần tử nhỏ thứ hai,ba...
Lần lượt lấy phần tử của danh sách chèn vị trí thích hợp của danh sách đã sắp
Dựa vào tư tưởng "chia để trị
so sánh hai phần tử kề nhau nếu chưa đúng thì đổi chỗ
ý tưởng phương pháp sắp xếp chèn(insertion 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 danh sách đã sắp
so sánh hai phần tử kề nhau nếu chưa đúng thì đổi chỗ
Dựa vào tư tưởng "chia để trị
Chọn phần tử bé nhất xếp vào vị trí thứ nhất,tương tự đối với phần tử nhỏ thứ hai,ba...
ý tưởng phương pháp sắp xếp chọ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 danh sách đã sắp
Chọn phần tử bé nhất xếp vào vị trí thứ nhất,tương tự đối với phần tử nhỏ thứ hai,ba...
so sánh hai phần tử kề nhau nếu chưa đúng thì đổi chỗ
Dựa vào tư tưởng "chia để trị".
Tư tưởng của giải thuật tìm kiếm nhị phân:
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 quuyế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
Dựa vào Tư tưởng "chia để trị
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
Tư tưởng của giải thuật tìm kiếm tuần tự
Dựa vào Tư tưởng "chia để trị".
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 quuyế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