Scribd
Upload
21 views2 pages

MT Practice Sp25

The document is a midterm practice guide for a Data Structure course, covering various topics such as Big-O notation, dynamic memory allocation, expression evaluation, linked lists, stacks, and queues. It includes specific questions and tasks related to these topics, such as determining the worst-case computing time, creating expression trees, and implementing functions for data structures. The guide is intended for students to prepare for their upcoming midterm exam in Spring 2025.

Uploaded by

307 03 王柏崴
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views2 pages

MT Practice Sp25

The document is a midterm practice guide for a Data Structure course, covering various topics such as Big-O notation, dynamic memory allocation, expression evaluation, linked lists, stacks, and queues. It includes specific questions and tasks related to these topics, such as determining the worst-case computing time, creating expression trees, and implementing functions for data structures. The guide is intended for students to prepare for their upcoming midterm exam in Spring 2025.

Uploaded by

307 03 王柏崴
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structure Spring 2025

Midterm Practice
Instructor: Hung-Ming Chen

1. [Simple Answers] You can use English or Chinese to answer.


(a) Determine which of the orders of magnitude given here is the best Big-O
notation to use to express the worst-case computing time as a function of n.

for (int i = 0; i < n – 1; i++) {


for (int j = 0; j < n – 1; j++)
if (x[j] > x[j + 1]) {
temp = x[j];
x[j] = x[j + 1];
x[j + 1] = temp;
}
}

(b) In dynamic memory allocation during implementing data structures, what are
the three member functions we should implement at the same time?
(c) What are the occasions when a copy of an object must be made? (in other
words, when will the copy constructor be invoked?) List at least two
occasions.
(d) Write down the components of STL containers, or what an ADT/container/bag
should have as contents.

2. [Expression Evaluation] Consider this infix expression:


(a + b) / (c – (d + e))
(a) Draw the corresponding expression tree.
(b) Use (a) to find the corresponding RPN (Reverse Polish Notation). Show your
work in detail steps.

3. [List]
(a) You are given pointers to first and last nodes of a singly linked list, which of
the following operations are dependent on the length of the linked list?
a. Delete the first element
b. Insert a new element as a first element
c. Delete the last element of the list
d. Add a new element at the end of the list
(b) What is the output of the following function if start pointing to first node of
this linked list 1 → 2 → 3 → 4 → 5 → 6?

void fun(struct node* start)


{
if (start == NULL) return;
cout << start->data;
if(start->next != NULL )
fun(start->next->next);
cout << start->data;
}

4. [Stack and Queue]


(a) Write a recursive C++ procedure to print out the content in a stack in reverse
order. The content of the stack is allowed to be removed after this procedure.
Do not use an extra stack to do this job.
(b) Write a definition for a function size() for the Queue class that returns the
number of elements in the queue. Assume that the linked list implementation
is used.
(c) Write a definition of a function moveNthFront() that takes as a parameter a
queue and a positive integer n. The function moves the nth element of the
queue to the front. The order of the remaining elements remains unchanged.
For example, suppose
queue = {5, 11, 34, 67, 43, 56} and n = 3.
After a call to the function moveNthFront,
queue = {34, 5, 11, 67, 43, 56}
(Assume n is less than or equal to the size of queue)

You might also like