Scribd
Upload
89 views3 pages

Data Structures-Quiz Pre UTS

This document contains a mid-term quiz with 4 questions on data structures and algorithms. Question 1 involves converting an infix notation to prefix notation using a stack and then evaluating the prefix notation. Question 2 involves inserting keys into a hash table using linear probing for collision resolution. Question 3 involves simulating insertions and deletions in a binary search tree. Question 4 provides a case study on implementing a priority queue playlist feature for a music player app using a linked list in C.

Uploaded by

Michael Robert
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
89 views3 pages

Data Structures-Quiz Pre UTS

This document contains a mid-term quiz with 4 questions on data structures and algorithms. Question 1 involves converting an infix notation to prefix notation using a stack and then evaluating the prefix notation. Question 2 involves inserting keys into a hash table using linear probing for collision resolution. Question 3 involves simulating insertions and deletions in a binary search tree. Question 4 provides a case study on implementing a priority queue playlist feature for a music player app using a linked list in C.

Uploaded by

Michael Robert
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Name:

NIM:
Pre Mid-Term Quiz
7 April 2021

1. Arithmetic Notation Conversion and Evaluation using Stack (20 points)


Given an infix notation as follows:
2 * (6 + 4) / (7 – 3) + 5
a. Convert infix expression above into prefix notation using stack! (10 points)
Infix String Stack Prefix String
2 * (6 + 4) / (7 – 3) + 5
2 * (6 + 4) / (7 – 3) + 5 2
2 * (6 + 4) / (7 – 3) + 5 * *2
2 * (6 + 4) / (7 – 3) + 5 *( *264
2 * (6 + 4) / (7 – 3) + 5 *( *264
2 * (6 + 4) / (7 – 3) + 5 *(+ +*264
2 * (6 + 4) / (7 – 3) + 5 *(+ +*264
2 * (6 + 4) / (7 – 3) + 5 *(+ +*264
2 * (6 + 4) / (7 – 3) + 5 *(+/ +*2/64
2 * (6 + 4) / (7 – 3) + 5 *(+/( +*2/647
2 * (6 + 4) / (7 – 3) + 5 *(+/(- +*2/647
2 * (6 + 4) / (7 – 3) + 5 *(+/(- +*2/64-73
2 * (6 + 4) / (7 – 3) + 5 *(+/(-+ +*2/64-73
2 * (6 + 4) / (7 – 3) + 5 *(+/(-+ +*2/64-73
2 * (6 + 4) / (7 – 3) + 5 *(+/(-+ +*2/+64-735

*You can add more rows if needed

b. Based on the result of conversion above, please do simulation of evaluating prefix notation that
you have found using stack. (10 points)
Prefix String Stack

* You can add more rows if needed

2. Hash Table (20 points)


a. Using folding method, please insert the following keys into hash table with size 10. If collision
happens, you can use the concept of linear probing to deal with the collision.): (20 points)

ironman (7564), spiderman (9636), superman (8752), batman (6277), thor (4451), hulk (4368),
captain (7369), joker (5391)
Key Name

Lecturer: D6426 – Kenny Jingga, S.Kom., M.T.


Name:
NIM:
Key Name
1
2
3
4
5
6
7
8
9

3. Binary Search Tree (20 points)


Given the following Binary Search Tree:

47

21 56

10 33 50

39 49

a. Please simulate the insertion of 28, 15, dan 61. (10 points)
(You need to draw BST for each node insertion)

b. Continuing from the previous BST condition, please simulates the deletion of: 21 dan 47 (10
points)
(You need to draw BST for each node insertion)

4. Case Study - Linked List (Priority Queue) (40 points)


Rekt wants to create a song player application called Rektify. One of the main features that Rekt
wants in the application is the Playlist feature, where users can collect their favorite songs to be
included in the Playlist. Based on its use, the Playlist feature can support several things, such as:
 Users can enter favorite songs into the Playlist.

Lecturer: D6426 – Kenny Jingga, S.Kom., M.T.


Name:
NIM:
 When entering their favorite song, they have to enter the priority number. There are 3 priority
numbers that they can choose. The top most favorite song is songs with priority 1. If user enters
song with the same priority, the song will be sorted based on the time the user entered the
song (the song that is entered first will be placed on the top)
 If user enter a song that is already available in the playlist, the rektify will give the user an error
message.
 Play song on the top list: Rektify will play song that is placed on the top most favorite song .

In order to implement the Playlist feature, Rekt decided to use the linked list approach. Based on
the information that has been given, please Rekt to create the playlist app using C programming
language

== Good Luck ==

Lecturer: D6426 – Kenny Jingga, S.Kom., M.T.

You might also like