01 PRELIMS ITC04 REVIEWER (1).pdf
Document Details
Uploaded by Deleted User
2024
Tags
Full Transcript
UNIVERSIDAD DE DAGUPAN SCHOOL OF INFORMATION TECHNOLOGY EDUCATION ITC04 | DATA STRUCTURES & ALGORITHM PART-I-MULTIPLE CHOICES: Choose from among the choices the answer that best fits the requirement. Mark your answer...
UNIVERSIDAD DE DAGUPAN SCHOOL OF INFORMATION TECHNOLOGY EDUCATION ITC04 | DATA STRUCTURES & ALGORITHM PART-I-MULTIPLE CHOICES: Choose from among the choices the answer that best fits the requirement. Mark your answer Red. I. Data Structure 1. Which of the following is a linear data structure? A) Tree B) Graph C) Stack D) HashMap 2. What is the time complexity of accessing an element in an array by its index? A) O(n) B) O(log n) C) O(1) D) O(n²) 3. In a queue, how is the order of elements processed? A) Last-In-First-Out (LIFO) B) First-In-First-Out (FIFO) C) Random order D) None of the above 4. Which of the following data structures allows insertion and deletion at both ends? A) Stack B) Queue C) Linked List D) Deque 5. What is the primary difference between an ArrayList and a LinkedList in Java? A) ArrayList allows duplicate values, LinkedList does not B) ArrayList uses dynamic arrays, LinkedList uses doubly linked nodes C) ArrayList is faster for inserting/removing elements at the beginning, LinkedList is faster at accessing elements D) LinkedList is backed by arrays, ArrayList by nodes 6. Which primitive data type has a precision of approximately 15 decimal digits? A) float B) double C) int D) char 7. How many bits does the short primitive data type occupy in Java? A) 8 B) 16 C) 32 D) 64 8. Which primitive data type has a range of -231 to 231-1 in Java? A) short B) int C) long D) byte 9. What is the size (in bytes) of the long primitive data type in Java? A) 2 B) 4 C) 8 D) 16 10. Which of the following primitive types is the smallest in terms of storage size? A) byte B) short C) int 1ST Semester Academic Year: 2024-2025 1 D) long II. Characteristics of DS 1. Which of the following is a characteristic of an array? A) Fixed size B) Dynamic resizing C) Supports only primitive data types D) Allows duplicate keys 2. What is the main characteristic of a stack data structure? A) First-In-First-Out (FIFO) B) Last-In-First-Out (LIFO) C) Random access D) Hierarchical structure 3. Which of the following data structures does NOT allow duplicate elements? A) Array B) HashSet C) LinkedList D) Stack 4. In which data structure is each element associated with a key and a value? A) Queue B) HashMap C) Stack D) Array 5. Which of the following data structures is the best for implementing a priority queue? A) Stack B) Array C) HashMap D) Heap 6. What is the main advantage of using a linked list over an array? A) Random access to elements B) Faster access time C) Dynamic size D) Easier to sort 7. Which data structure is known for its hierarchical relationship among its elements? A) Tree B) Stack C) Array D) Queue 8. Which of the following characteristics describes a circular queue? A) Unlimited size B) Elements can only be dequeued from the front and enqueued at the rear C) Front and rear pointers wrap around when they reach the end of the array D) Allows insertion and deletion from both ends 9. Which characteristic is unique to a doubly linked list? A) Each node has a link to both the previous and next nodes B) Nodes only link to the next node C) Access to elements is O(1) D) Fixed memory allocation 10. What is the primary feature of a dynamic array (like ArrayList in Java)? A) Fixed size at the time of declaration B) Automatically resizes when needed C) Elements can only be added at the end D) Requires a predefined capacity III. Need for data structures: 1. Why are data structures essential in programming? A) They increase code readability B) They help in organizing data efficiently C) They simplify debugging 1ST Semester Academic Year: 2024-2025 2 D) They reduce the size of the program 2. What is the main purpose of using a data structure in algorithms? A) To store data in the database B) To perform faster calculations C) To organize and manage data for efficient processing D) To decrease the size of the algorithm 3. Which of the following is a key reason to use data structures in large applications? A) They use less memory B) They allow efficient data storage and retrieval C) They make programs shorter D) They do not require any algorithmic logic 4. Why is choosing the correct data structure important for a program? A) It minimizes memory use B) It allows direct communication with the operating system C) It ensures better time and space efficiency D) It reduces the need for loops and conditionals 5. Which of the following problems can be solved efficiently using data structures? A) Sorting large datasets B) Minimizing code duplication C) Making the code look more complex D) Handling I/O operations 6. In real-time applications, why are data structures like queues and stacks often used? A) To display data in a GUI B) To manage tasks in a controlled order (FIFO, LIFO) C) To reduce the size of the program D) To remove errors in the code 7. Which of the following is NOT a benefit of using a data structure? A) Enhanced data manipulation B) Increased program execution speed C) Reduced memory requirements D) Provides direct hardware interaction 8. How do data structures contribute to solving complex computational problems? A) By providing a framework to design efficient algorithms B) By increasing the number of variables C) By slowing down execution time D) By making the code harder to debug 9. Why are hash tables used in data storage applications? A) They provide a visual representation of data B) They allow efficient access through key-value pairs C) They occupy less memory D) They allow only sequential access to data 10. Which of the following is an advantage of using trees in data structures? A) They allow fast sequential access B) They ensure data redundancy C) They enable hierarchical organization and efficient searching D) They store data in a flat structure PART-II-TRUE or FALSE: Evaluate each of the given statements whether correct or wrong. Write TRUE if the statement is correct, otherwise write FALSE. IV. Algorithm 1. An algorithm must always produce the correct output for all valid inputs. Answer: True 2. Every algorithm has an infinite number of steps. Answer: False (An algorithm must have a finite number of steps.) 3. Algorithms can be written in any programming language. Answer: True (Algorithms are independent of programming languages and can be implemented in any language.) 1ST Semester Academic Year: 2024-2025 3 4. An algorithm's time complexity is a measure of how long it takes to execute relative to its input size. Answer: True 5. An algorithm is always the most efficient solution to a problem. Answer: False (An algorithm can be inefficient, and not all algorithms are optimal.) 6. A recursive algorithm is one that solves the problem by breaking it down into smaller instances of the same problem. Answer: True 7. Greedy algorithms always provide the optimal solution to a problem. Answer: False (Greedy algorithms do not always yield the optimal solution, but they work well for certain problems.) 8. An algorithm that runs in O(1) time is considered more efficient than one that runs in O(n) time. Answer: True (O(1) means constant time, which is faster than O(n), where time increases linearly with input size.) 9. Sorting algorithms like Merge Sort and Quick Sort have the same worst-case time complexity. Answer: False (Merge Sort has a worst-case time complexity of O(n log n), while Quick Sort has a worst-case time complexity of O(n²).) 10. All algorithms can be optimized to run in O(1) time. Answer: False (Not all algorithms can achieve constant time complexity; it depends on the problem's nature.) VI. Algorithm Complexity 1. Time complexity measures the amount of memory an algorithm uses. Answer: False (Time complexity measures the amount of time an algorithm takes to run, not the memory usage.) 2. Space complexity refers to the amount of memory an algorithm needs to run. Answer: True 3. An algorithm with a time complexity of O(n²) is faster than one with O(n log n) for large input sizes. Answer: False (O(n log n) is more efficient than O(n²) for large inputs.) 4. The Big-O notation describes the worst-case time complexity of an algorithm. Answer: True 5. An algorithm with constant time complexity, O(1), is always the most efficient. Answer: False (O(1) is efficient, but it depends on the nature of the problem. Some problems require more complex time complexities.) 6. Time complexity is always more important than space complexity. Answer: False (It depends on the problem. In some cases, space complexity is more crucial, such as in memory- constrained environments.) 7. The best-case time complexity of an algorithm is the time it takes under the most favorable input conditions. Answer: True 8. Algorithms with exponential time complexity, O(2ⁿ), are generally considered inefficient for large inputs. Answer: True (Exponential time complexity grows very fast, making it impractical for large inputs.) 9. Amortized time complexity accounts for the average performance of an algorithm over a sequence of operations. Answer: True 10. If an algorithm has a time complexity of O(n!), it is considered very efficient. Answer: False (O(n!) is extremely inefficient and grows faster than even exponential time complexity.) 1ST Semester Academic Year: 2024-2025 4 PART-III-IDENTIFICATION: Write the APPROPRIATE word or phrase that best describe each of the given statements. WRONG SPELLING WRONG. Be sure to write legibly and correctly the given answers. VII. Classification of Data Structures: 1. Identify the type of data structure that organizes data in a linear fashion and allows access by index. Answer: Array 2. Identify the data structure that follows the First-In-First-Out (FIFO) principle. Answer: Queue 3. Name the data structure where each element points to the next, creating a chain of elements. Answer: Linked List 4. Identify the non-linear data structure that is used to represent hierarchical relationships between elements. Answer: Tree 5. Name the data structure that stores unique elements without any specific order and provides constant-time performance for basic operations like insertion and lookup. Answer: HashSet 6. Identify the data structure that allows elements to be added or removed only from one end, following the Last-In-First-Out (LIFO) principle. Answer: Stack 7. What is the name of the data structure used to efficiently map unique keys to corresponding values? Answer: HashMap 8. Name the linear data structure that supports efficient insertion and deletion from both ends. Answer: Deque (Double-ended Queue) 9. Identify the data structure that ensures its elements are arranged in a sorted order, based on their key values. Answer: TreeMap 10. What is the type of data structure that can be implemented using either arrays or linked lists, commonly used for managing recursive function calls? Answer: Stack VIII. Data Representation 11. In Java, what is the data type used to represent a single 16-bit Unicode character? Answer: char 12. Identify the Java data type used to represent a 32-bit floating-point number. Answer: float 13. What is the Java keyword used to represent a true/false value? Answer: boolean 14. Name the Java class that is used to represent large integer values that exceed the range of primitive data types like int or long. Answer: BigInteger 15. Identify the format used in Java to store and manipulate collections of characters. Answer: String 16. What Java data type would you use to represent a 64-bit signed integer? Answer: long 17. Name the Java class used to represent arbitrary-precision decimal numbers for high-precision calculations. Answer: BigDecimal 18. In Java, what is the default character encoding format used for char and String types? Answer: Unicode 19. Identify the Java data type used to store a sequence of bytes, commonly used for binary data representation. Answer: byte [ ] 20. What Java data type is used to represent a 64-bit floating-point number for high-precision computations? Answer: double 1ST Semester Academic Year: 2024-2025 5 IX. Goals of Data Representation 21. The primary goal of using this class in Java is to represent arbitrarily large integers that exceed the range of primitive types. Answer: BigInteger 22. The main goal of using this data type in Java is to represent individual 16-bit Unicode characters. char 23. The goal of using it in Java for data representation to store and manipulate sequences of characters (text). Answer: String 24. The primary objective of using it in Java is to perform high-precision arithmetic with decimal numbers, especially in financial applications. Answer: BigDecimal 25. The goal of using this data type in Java is to represent true/false values for logical operations and conditions. Answer: boolean 26. The purpose of using this data structure in Java for data representation is to represent and store binary data, such as files or network streams. Answer: byte[] 27. Identify the goal of using this data type in Java is to represent whole numbers with a fixed range (64-bit for long). Answer: long 28. The goal of data representation using this data type in Java is to represent floating-point numbers for scientific calculations with double precision. Answer: double 29. The goal of this Java class when it comes to data representation is to provide utility methods for manipulating and inspecting individual characters, including support for Unicode. Answer: Character 30. The main objective of using it in Java for data representation is to represent fixed-size collections of elements of the same data type with indexed access. Answer: Array X. Memory Representation 31. Identify the memory area where Java objects are stored during runtime. Answer: Heap 32. What is the name of the memory area in Java used for storing method calls, local variables, and function call execution details? Answer: Stack 33. Identify the memory section where Java stores static variables and constants. Answer: Method Area (also called the Permanent Generation in older versions of Java) 34. What is the Java memory model that ensures visibility and ordering of variables across multiple threads? Answer: Java Memory Model (JMM) 35. Identify the process in Java that automatically reclaims memory allocated to objects that are no longer in use. Answer: Garbage Collection 36. Name the region in memory where class metadata, such as class names, field types, and method information, is stored. Answer: Method Area (or Metaspace in newer versions of Java) 37. Identify the type of memory representation where primitive data types such as int, char, and boolean are stored in Java. Answer: Stack (for local variables), or Heap (if used as part of an object) 38. What is the Java memory area where strings created using string literals are stored? Answer: String Pool (which is part of the Heap) 39. Identify the memory representation in Java where dynamic memory allocation occurs for object instances. Answer: Heap 40. What is the term for the memory space that stores temporary data such as parameters, return addresses, and local variables in Java methods? Answer: Stack Frame 1ST Semester Academic Year: 2024-2025 6 PREPARED BY: ARNALDY D. FORTIN, MBA, MCS SITE, FACULTY NOTED BY: ENGR. ENGELBERT Q. CRUZ, Ph.D. SITE, SENIOR FACULTY APPROVED BY: JANN ALFRED ARZADON QUINTO, MSIB DEAN, SITE 1ST Semester Academic Year: 2024-2025 7