CS301 Data Structures Final Exam Spring 2010

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

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?

True Signup and view all the answers

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

selppa Signup and view all the answers

What is printed by the call test_a(4)?

02 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?

N-1 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?

Reflexive Signup and view all the answers

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

Associative Signup and view all the answers

A binary tree of N nodes has:

Log2 N levels 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:

Is a leaf node 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.

log2N Signup and view all the answers

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

O(nlogn) sorts Signup and view all the answers

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

External node Signup and view all the answers

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

NULL 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

complete Binary tree Signup and view all the answers

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

Two entries with different keys have the same exact hash value. Signup and view all the answers

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

N − (h + 1) 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?

57 Signup and view all the answers

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

increaseKey(p,delta) Signup and view all the answers

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

A table consists of several columns, known as entities. Signup and view all the answers

In a perfectly balanced tree the insertion of a node needs

One rotation Signup and view all the answers

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

N Signup and view all the answers

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

32 Signup and view all the answers

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

This dummy node has either no value or some dummy value. Signup and view all the answers

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

completely Signup and view all the answers

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

Log2 (n+1) -1 Signup and view all the answers

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

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

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

False Signup and view all the answers

Each node in doubly link list has ___.

2 pointers 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?

Both change. Signup and view all the answers

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

Parse Tree Signup and view all the answers

A binary tree of N nodes has ____ levels.

Log2 N levels 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)?

42 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:

16, 24, 20, 30, 28, 18, 22 Signup and view all the answers

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

The function has logical problem, therefore, it will not work properly Signup and view all the answers

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

Initially each set contains one element and it does not make sense to make a tree of one node only. Signup and view all the answers

In complete binary tree the bottom level is filled from ____

Left to right 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).

0 3 8 2 6 4 9 1 7 5 Signup and view all the answers

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

The array must be sorted. Signup and view all the answers

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

Top Signup and view all the answers

Compiler uses which one of the following in Function calls,

Stack Signup and view all the answers

Every AVL is ____

Binary Tree Signup and view all the answers

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

<= relation Signup and view all the answers

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

Sorted Signup and view all the answers

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

List Sh contains only the n special keys. Signup and view all the answers

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

O(n2) 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. Signup and view all the answers

Which of the following is a property of binary tree?

A binary tree of N external nodes has N+ 1 internal node 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.

Threaded binary tree Signup and view all the answers

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

log2(n) Signup and view all the answers

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.

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.