首页 >
> 详细

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]

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Csse1001 Assignment 3 2021-01-10
- Comp3506/7505 Homework 4 – Graph Algo 2021-01-10
- Unix & C Programming (Comp1000) Assign... 2021-01-10
- Ece 209 Program 3: Market 2021-01-10
- Informatics 1 — Functional Programming 2021-01-10
- Cisc/Cmpe 452/Cogs400 Assignment 2 2021-01-10
- Fit2100 Operating Systems Assignment #... 2021-01-10
- Csci 1100 — Homework 5 2021-01-10
- Comp9444 Neural Networks And Deep Lea... 2021-01-10
- Assignment Case: German Credit 2021-01-10
- 48024 Applications Programming Assign... 2021-01-10
- Cs 405/805-001: Computer Graphics Ass... 2021-01-10
- Cse 434, Sln 70608 — Computer Networks 2021-01-10
- Corpfin 2503 - Business Data Analytics 2021-01-10
- Cis 455 / 555: Internet And Web System... 2021-01-10
- Cs110留学生编程代写、代做c++程序实验、Program程序语言调试帮做 2021-01-10
- Csc8021程序代做、代写networks编程语言、代做c/C++，Jav 2021-01-10
- 代写program编程语言、代做python，C++，Java程序设计帮做j 2021-01-10
- R编程课程代写、代做program程序语言、R程序实验代做代写databas 2021-01-09
- Data编程设计代做、代写java程序语言、Java程序实验调试代写r语言程 2021-01-09