CS301 Data Structures Final Exam Spring 2010
50 Questions
8 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

A solution is said to be efficient if it solves the problem within its resource constraints i.e. hardware and time.

True (A)

Which one of the following is known as "Last-In, First-Out" or LIFO Data Structure?

  • Queue
  • Linked List
  • Tree
  • Stack (correct)

What will be postfix expression of the following infix expression? Infix Expression : a+b*c-d

  • abcd+*-
  • abc*+d- (correct)
  • abc+*d-
  • ab+c*d-

For compiler a postfix expression is easier to evaluate than infix expression?

<p>True (A)</p> Signup and view all the answers

What is written to the screen for the input "apples"?

<p>selppa</p> Signup and view all the answers

What is printed by the call test_a(4)?

<p>02 (B)</p> Signup and view all the answers

If there are N external nodes in a binary tree then what will be the no. of internal nodes in this binary tree?

<p>N-1 (D)</p> Signup and view all the answers

If we have 1000 sets each containing a single different person. Which of the following relation will be true on each set?

<p>Reflexive (D)</p> Signup and view all the answers

Which one of the following is NOT the property of equivalence relation?

<p>Associative (D)</p> Signup and view all the answers

A binary tree of N nodes has:

<p>Log2 N levels (A)</p> Signup and view all the answers

The easiest case of deleting a node from BST is the case in which the node to be deleted:

<p>Is a leaf node (D)</p> Signup and view all the answers

If there are N elements in an array then the number of maximum steps needed to find an element using Binary Search is.

<p>log2N (B)</p> Signup and view all the answers

Merge sort and quick sort both fall into the same category of sorting algorithms. What is this category?

<p>O(nlogn) sorts (B)</p> Signup and view all the answers

If one pointer of the node in a binary tree is NULL then it will be a/an

<p>External node (D)</p> Signup and view all the answers

We convert the ____ pointers of binary to threads in threaded binary tree.

<p>NULL (C)</p> Signup and view all the answers

If the bottom level of a binary tree is NOT completely filled, depicts that the tree is NOT a

<p>complete Binary tree (C)</p> Signup and view all the answers

What is the best definition of a collision in a hash table?

<p>Two entries with different keys have the same exact hash value. (D)</p> Signup and view all the answers

For a perfect binary tree of height h, having N nodes, the sum of heights of nodes is

<p>N − (h + 1) (B)</p> Signup and view all the answers

If there are 56 internal nodes in a binary tree then how many external nodes this binary tree will have?

<p>57 (B)</p> Signup and view all the answers

Which of the following heap method increase the value of key at position ‘p' by the amount ‘delta'?

<p>increaseKey(p,delta) (A)</p> Signup and view all the answers

Which one of the following is NOT a correct statement about Table ADT.

<p>A table consists of several columns, known as entities. (B)</p> Signup and view all the answers

In a perfectly balanced tree the insertion of a node needs

<p>One rotation (C)</p> Signup and view all the answers

We are given N items to build a heap, this can be done with ____ successive inserts.

<p>N (B)</p> Signup and view all the answers

A binary tree with 33 internal nodes has ____ links to internal nodes.

<p>32 (C)</p> Signup and view all the answers

Which of the following statement is true about dummy node of threaded binary tree?

<p>This dummy node has either no value or some dummy value. (A)</p> Signup and view all the answers

A complete binary tree is a tree that is ____ filled, with the possible exception of the bottom level.

<p>completely (C)</p> Signup and view all the answers

If a complete binary tree has n number of nodes then its height will be.

<p>Log2 (n+1) -1 (A)</p> Signup and view all the answers

Which of the following statement is correct about find(x) operation?

<p>A find(x) on element x is performed by returning the root of the tree containing x. (C)</p> Signup and view all the answers

A queue is a data structure where elements are inserted and removed from the top.

<p>False (B)</p> Signup and view all the answers

Each node in doubly link list has ___.

<p>2 pointers (C)</p> Signup and view all the answers

I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue?

<p>Both change. (D)</p> Signup and view all the answers

Compiler uses which one of the following to evaluate a mathematical equation?

<p>Parse Tree (D)</p> Signup and view all the answers

A binary tree of N nodes has ____ levels.

<p>Log<sub>2</sub> N levels (A)</p> Signup and view all the answers

Suppose that a selection sort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

<p>42 (D)</p> Signup and view all the answers

Suppose you implement a Min heap (with the smallest element on top) in an array. Consider the different arrays below; determine the one that cannot possibly be a heap:

<p>16, 24, 20, 30, 28, 18, 22 (B)</p> Signup and view all the answers

Do you see any problem in the code of nextInOrder below?

<p>The function has logical problem, therefore, it will not work properly (A)</p> Signup and view all the answers

Which of the following statement is NOT correct about find operation:

<p>Initially each set contains one element and it does not make sense to make a tree of one node only. (D)</p> Signup and view all the answers

In complete binary tree the bottom level is filled from ____

<p>Left to right (B)</p> Signup and view all the answers

Here is an array of ten integers: 5 3 8 9 17 0 26 4. The array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).

<p>0 3 8 2 6 4 9 1 7 5 (D)</p> Signup and view all the answers

What requirement is placed on an array, so that binary search may be used to locate an entry?

<p>The array must be sorted. (A)</p> Signup and view all the answers

Which one of the following operations returns top value of the stack?

<p>Top (A)</p> Signup and view all the answers

Compiler uses which one of the following in Function calls,

<p>Stack (C)</p> Signup and view all the answers

Every AVL is ____

<p>Binary Tree (A)</p> Signup and view all the answers

Which one of the following is not an example of equivalence relation?

<p>&lt;= relation (D)</p> Signup and view all the answers

Binary Search is an algorithm of searching, used with the ____ data.

<p>Sorted</p> Signup and view all the answers

Which one of the following is NOT true regarding the skip list?

<p>List Sh contains only the n special keys. (B)</p> Signup and view all the answers

A simple sorting algorithm like selection sort or bubble sort has a worst-case of ____

<p>O(n<sup>2</sup>) time because sorting 1 element takes O(n) time - After 1 pass through the list,either of these algorithms can guarantee that 1 element is sorted. (B)</p> Signup and view all the answers

Which of the following is a property of binary tree?

<p>A binary tree of N external nodes has N+ 1 internal node (A)</p> Signup and view all the answers

By using ____, we avoid the recursive method of traversing a Tree, which makes use of stacks and consumes a lot of memory and time.

<p>Threaded binary tree</p> Signup and view all the answers

Which formula is the best approximation for the depth of a heap with n nodes?

<p>log<sub>2</sub>(n) (C)</p> Signup and view all the answers

Flashcards

Stack

A data structure that follows the Last-In, First-Out (LIFO) principle, meaning the last element added is the first one to be removed.

Linked List

A data structure that uses a linear list to store elements, where each node points to the next node in the sequence.

Queue

A data structure where elements are added at the rear and removed from the front, following the First-In, First-Out (FIFO) principle.

Tree

A data structure that represents hierarchical relationships with a tree-like structure, where nodes are connected by edges.

Signup and view all the flashcards

Infix to Postfix Conversion

A method used to convert an infix expression (where operators are placed between operands) into its postfix equivalent (where operators follow operands).

Signup and view all the flashcards

Stack for Expression Evaluation

A data structure used in compilers to evaluate expressions efficiently. It stores the intermediate results of calculations.

Signup and view all the flashcards

Node Insertion in Binary Tree

A method used to create a new node in a binary tree and insert it at the appropriate location.

Signup and view all the flashcards

Tree Traversal

A method used to traverse a binary tree by visiting nodes in a specific order, such as pre-order, in-order, or post-order.

Signup and view all the flashcards

AVL Tree

A binary tree where the height difference between the left and right subtrees of any node is at most one. This ensures a balanced tree, improving search efficiency.

Signup and view all the flashcards

Max Heap

A heap where the parent node's value is always greater than or equal to the values of its child nodes. This maintains a sorted structure.

Signup and view all the flashcards

Min Heap

A heap where the parent node's value is always less than or equal to the values of its child nodes. This maintains a sorted structure.

Signup and view all the flashcards

Heap Insertion

A method used to insert an element into a heap while maintaining the heap property.

Signup and view all the flashcards

Complete Binary Tree

A binary tree where all levels except the last level are fully filled, and the last level is filled from left to right.

Signup and view all the flashcards

Heap Deletion

A method used to delete an element from a heap while maintaining the heap property.

Signup and view all the flashcards

Binary Search Tree

A binary search tree where nodes are arranged in a specific order to maximize search efficiency.

Signup and view all the flashcards

Binary Search Tree Search

A method used to find a specific element in a binary search tree by comparing the value of the current node to the target value.

Signup and view all the flashcards

Selection Sort

A method used to sort an array by repeatedly finding the minimum element and placing it at the beginning of the unsorted portion.

Signup and view all the flashcards

Bubble Sort

A method used to sort an array by repeatedly comparing adjacent elements and swapping them if they're in the wrong order.

Signup and view all the flashcards

Binary Search

A method used to search for an element in a sorted array by repeatedly dividing the search interval in half.

Signup and view all the flashcards

Algorithm Analysis

A method used to compute the efficiency of an algorithm by analyzing its running time and memory usage in terms of input size.

Signup and view all the flashcards

Stack Overflow

A condition where the size of a data structure (like a stack or queue) exceeds its capacity, causing potential errors or crashes.

Signup and view all the flashcards

Underflow

A condition where the data structure (like a queue or stack) is empty.

Signup and view all the flashcards

Tree Node

A data structure where each node contains pointers to its child nodes and a key value.

Signup and view all the flashcards

Sorting Algorithm

A method used to sort an array in ascending or descending order by repeatedly moving the elements based on their values.

Signup and view all the flashcards

Disjoint Set Data Structure

A method used to represent a set of elements as a collection of trees, where the root of each tree represents a set.

Signup and view all the flashcards

Find Operation

An operation used to find the root of a tree in the disjoint set data structure.

Signup and view all the flashcards

Union Operation

An operation used to merge two sets in the disjoint set data structure.

Signup and view all the flashcards

Disjoint Sets

A method used to represent a set of elements as a collection of trees, where the root of each tree represents a set.

Signup and view all the flashcards

Equivalence Relation

A representation of a relationship between elements where there is a connection or linkage.

Signup and view all the flashcards

Relation

A relationship where there is a direct connection between two elements and the order of the connection matters.

Signup and view all the flashcards

Set Relation

A type of data structure where each element in a set is connected to other elements that are related.

Signup and view all the flashcards

Efficient Solution

A solution is considered efficient if it successfully solves the problem within the given resource constraints, such as hardware capabilities and time limits.

Signup and view all the flashcards

Stack (LIFO)

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed.

Signup and view all the flashcards

Postfix Expression

A postfix expression is often easier for a compiler to evaluate than an infix expression because postfix removes the ambiguity of operator precedence. The compiler can process operators one by one without needing parentheses.

Signup and view all the flashcards

Stack and Word Reversal

For the input "apples", the program will print "selppa" to the screen. The code reads each character, pushes it onto the stack, and then pops characters off the stack, reversing the word.

Signup and view all the flashcards

Function with Logical Issues

This function has a logical problem. It iterates through the nodes of a linked list, but it doesn’t handle all node types correctly. It’s missing conditions for some node types, leading to potential errors when iterating.

Signup and view all the flashcards

Find Operation in Disjoint Sets

The find(x) operation returns the root node of the tree containing the element x. This root node is used to represent the set that element x belongs to.

Signup and view all the flashcards

Disjoint Sets: Single Node Tree

The statement "Initially each set contains one element and it does not make sense to make a tree of one node only" is NOT correct. While initially each set contains one element, there's nothing preventing you from creating a tree with one node.

Signup and view all the flashcards

Complete Binary Tree: Filling Last Level

In a complete binary tree, the bottom level is filled from left to right. This means all the nodes from the leftmost position to the rightmost position are filled with data.

Signup and view all the flashcards

Selection Sort: First Iteration

After the first iteration of the large loop in a selection sort, the array will be: 0 3 8 9 1 7 5 2 6 4. The smallest element (0) is found and placed at the beginning of the array.

Signup and view all the flashcards

Binary Search: Sorted Array

To use binary search on an array, the array must be sorted in ascending or descending order. This is because binary search efficiently divides the search region in half, which relies on the sorted property.

Signup and view all the flashcards

Stack Operation: Top

The Top operation returns the topmost value of the stack without removing it. This allows you to peek at the current top element without changing the stack structure.

Signup and view all the flashcards

Compiler Uses Stack for Function Calls

Compilers utilize a stack to manage function calls efficiently. They use the stack to store variables, return addresses, and other information associated with function execution.

Signup and view all the flashcards

AVL Tree: Binary Search Tree

Every AVL tree is a Binary Search Tree. This means the left subtree of every node has values less than the node's value, and the right subtree has values greater than the node's value. And the AVL tree is a balanced tree.

Signup and view all the flashcards

Internal and External Nodes in Binary Tree

If a binary tree has 56 internal nodes, it will have 57 external nodes. This is because a binary tree is a tree-like structure and there's always one more external node than internal nodes.

Signup and view all the flashcards

Internal and External Nodes Relationship

If a binary tree has 23 external nodes, it will have 22 internal nodes. A binary tree is a balanced structure where the number of internal nodes is always one less than the number of external nodes.

Signup and view all the flashcards

Equivalence Relation: Example - People

Set of people is NOT an example of an equivalence relation because it doesn't necessarily demonstrate a connection or relationship between all of the elements in the set and is not a standard example of an equivalence relation.

Signup and view all the flashcards

Relation: Ordered Pairs

A relation is a set of ordered pairs that shows a direct connection between two elements. The order matters, as (a, b) is not necessarily the same as (b, a).

Signup and view all the flashcards

Study Notes

CS301 - Data Structures - Final Term Examination - Spring 2010

  • Question 1 (Marks: 1): A solution is considered efficient if it solves the problem within hardware and time constraints.

    • True (Page 4)
    • False

  • Question 2 (Marks: 1): A Last-In, First-Out (LIFO) data structure is a Stack.

    • Linked List
    • Stack (Page 54)
    • Queue
    • Tree

  • Question 3 (Marks: 1): The postfix expression for the infix expression a + b * c - d is ab+c*d-.

    • ab+c*d-
    • abc*+d-
    • abc+*d-
    • abcd+*-

  • Question 4 (Marks: 1): For a compiler, a postfix expression is easier to evaluate than an infix expression.

    • True (Click here for detail)
    • False

  • Question 5 (Marks: 1): Given pseudo code that declares a stack of characters and reads a word, it will print the word in reverse order. Consider the input "apples"; the output will be "selpa."

    • selpa
    • selppa
    • apples
    • aaappppplleess

  • Question 6 (Marks: 1): This function outputs 4, 2, 0.

    • void test_a(int n) { cout << n << " "; if(n>0) test_a(n-2); }
    • Calling test_a(4) will produce "4 2 0".
    • 42
    • 024
    • 02
    • 24

  • Question 7 (Marks: 1): If there are N external nodes in a binary tree, the number of internal nodes will be N-1.

    • N-1 (Page 304)
    • N+1
    • N+2
    • N

  • Question 8 (Marks: 1): If there are N internal nodes in a binary tree, the number of external nodes will be N+1.

    • N-1
    • N
    • N+1 (Page 303)
    • N+2

  • Question 9 (Marks: 1): If there are 1000 sets of people with unique individuals in each set, the relationship will be reflexive. (Page 387)

    • Reflexive
    • Symmetric
    • Transitive
    • Associative

  • Question 10 (Marks: 1): One property that equivalence relations do not possess is associativity. (Page 387)

    • Reflexive
    • Symmetric
    • Transitive
    • Associative

  • Question 11 (Marks: 1): A binary tree with N nodes has Log₂N levels. (Page 212)

    • Log₁₀N levels
    • Log₂N levels
    • N/ 2 levels
    • N x 2 levels

  • Question 12 (Marks: 1): The easiest case for deleting a node from a binary search tree (BST) is when the node is a leaf node. (Page 173)

    • Is a leaf node
    • Has left subtree only
    • Has right subtree only
    • Has both left and right subtree

  • Question 13 (Marks: 1): Binary search on an array of N elements has a maximum number of steps of log₂N. (Page 440)

    • N
    • N²
    • Nlog₂N
    • log₂N

  • Question 14 (Marks: 1): Merge sort and quicksort are both O(n log n) sorts. (Page 488)

  • O(n log n) sorts

  • Interchange sort

  • Average time is quadratic

  • None of the given options

  • And many more questions... The provided text contains multiple exam questions with answers. More questions are included, covering various aspects of data structures. Some links to details are included for further learning.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

CS301 Final Term Exam Solved MCQs PDF - Spring 2010
CS301 Final Term Exam Questions PDF

Description

Test your knowledge of Data Structures with this final examination from CS301 Spring 2010. This quiz covers essential concepts like efficiency, data structures, and expression evaluation, providing a comprehensive review of key topics. Assess your understanding of stacks, queues, and postfix expressions.

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser