School of Computer Science

Data Structures & Algorithms Midterm Class Test

Class Test 2020/21

1

Data Structures & Algorithms Midterm Class Test

1. Stacks are often used to implement “undo” operations in applications like text editors or

Web browsers such that making a change in the text or clicking on a link in the browser

pushes a record of that operation on to the stack, while invoking undo pops the record off

the stack and executes the actions necessary to undo the operation.

In theory, an unbounded stack can provide unlimited undo operations, but, to save memory,

many applications support only limited undo history. Thus invoking “push”, when the stack

is already at full capacity, accepts the pushed elements at the top of the stack and leaks

the oldest element from the bottom of the stack rather than throwing an exception, while

invoking pop when the stack is empty still throws a StackEmptyException.

(a) Describe, as clearly and simply as possible, your proposed strategy to implement such

a stack using a fixed-capacity array, so that each update operation runs in O(1) time.

[5 marks]

(b) Write the pseudocode for the push operation of such a stack. [5 marks]

(c) Write the pseudocode for the pop operation of such a stack [5 marks]

2. An inefficient recursive function isbst was presented in the module in the handout document

(pages 46–47) and the slides (dsa-slides-04-03-binary-search-trees.pdf).

Write an efficient, recursive isbst function in pseudocode to check that a binary tree is

a valid Binary Search Tree, based on checking that subtrees are within closed intervals

starting with [MIN INT,MAX INT] and calculate the complexity, in terms of O(g(n)), with

respect to the size of the tree. Justify your calculation of the complexity with a short

explanation. [15 marks]

3. Construct an AVL tree of positive integers and of height 3 such that insertion of the value

7 will trigger a double rotation (i.e. a right rotation followed by a left rotation or a left

rotation followed by a right rotation) and, following the insertion of 7, an insertion of the

value 8 will also trigger a double rotation.

(a) Draw the valid AVL tree before the specified insertions

(b) Draw the valid AVL tree after insertion of 7 but before insertion of 8

(c) Draw the valid AVL tree after insertion of 7 and of 8 in that order

[10 marks]

2

版权所有：编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。