All past midterm questions · Submit to see grading & explanations
public Node getSecondToLast(SList S) that takes a
Singly Linked List as a parameter and returns a reference to the
node before the last node in the list.
public int size() which
returns the size of this CircularList.
public SList cloneSList(SList S) that
creates a copy of the provided Singly Linked List
and returns a reference to the new list.
The original list must not be destroyed.
void removeLast() for
a singly-linked list. The method removes the last node. The list
maintains size, head, and
tail references.
tmp after the node
p
in a doubly-linked list. Each node has next and
prev data members. A ↔ E(p) ↔ F · Insert
tmp(D) after p(E) → result:
A ↔ E ↔ D ↔ F
public Node getKthValue(Node H, int k) that takes a
pointer to the Head of a Singly Linked List and an integer
k. Return a pointer to the kth node.
Start counting Head as position 1.
1 ↔ 2(G) ↔ 3 ↔ 4 ↔ 5 ↔ 6. Node G points to
value 2. Write code to
swap nodes containing values 2 and 5. You may
create other pointers as necessary. class Node { Node prev, next; int value; }
public void remove(int value) in Java
within a Circular Linked List class that searches
for a value and removes it from the list. Each node stores only an
integer val and a next pointer.
1 → 2 → 4 · B:
1 → 3 → 4 · C:
1 → 1 → 2 → 3 → 4 → 4
PrintDuplicate() extending the
SinglyLinkedList class. This method prints all
duplicate values in the list. Also explain why or
why not your code runs in linear time.
Scanner to a text file containing English words (one
per line). This method creates an array of
26 Singly Linked Lists, fills them with words from
the file based on the word's first letter (e.g. words starting with
'a' go to A[0], 'b' to A[1], etc.), and returns a reference to this
array.
Header ↔ [5] ↔ [10] ↔ [15] ↔ [20] ↔ Trailer, with
temp pointing to node [5]. Trace this code and
write/draw the sequence of values from Head to Tail after execution.
Node A = temp.next; // A → [10] Node B = A.next; // B → [15] // Step 1 A.prev.next = B; B.prev = A.prev; // Step 2 A.next = B.next; if (A.next != null) A.next.prev = A; // Step 3 B.next = A; A.prev = B;
name (String) and next. Complete the
method
RemoveName(SinglyLinkedList L, String N)
that searches and removes the node containing name N. Example:
remove "May" from John → Ali → Zaid → May → Rose.
public void RemoveName(SinglyLinkedList L, String N){
if(Head.name == N){
____________________________________________
}
Node S = Head;
Node F = S.next;
while(F != null){
if(F.name == N){
____________________________________________
}
_________________;
_________________;
}
return;
}
public Node Find(SinglyLinkedList L) {
if (L.head == null) return null;
Node slow = L.head;
Node fast = L.head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
| Function f(n) | Big-O Answer |
|---|---|
| (a) f(n) = N²log N² + 2N log 2N | |
| (b) f(n) = (N · (100N + 5 + N²))² | |
| (c) f(n) = N1/2 + log log N | |
| (d) f(n) = 1000 log log N + log N | |
| (e) f(n) = 100n³ − 7n³ + 14n² | |
| (f) f(n) = 100n³ − 100n³ + 7n² | |
| (g) f(n) = log(7n²) | |
| (h) f(n) = 5 log log n + 4 log²(n) | |
| (i) f(n) = 0.001n + 100·2ⁿ | |
| (j) f(n) = n³(1 + 6n + 2014n²) | |
| (k) f(n) = (log n)(n + n²) | |
| (l) f(n) = n²log n + 2n | |
| (m) f(n) = 100n² − 100n² + 14n³ | |
| (n) f(n) = 100 log log n + 100 log²n | |
| (o) f(n) = n³(10 + 20n + 20n²) | |
| (p) f(n) = n²log n + 100n |
count++ executed? What is the Big-O?
count = 0;
for(int i = 1; i < 10; i++) {
count++;
}
s = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
s = s + 1;
// Snippet A
int k = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= 10; j++)
k = k + i + j;
// Snippet B
int k = 0;
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++)
k = k + i;
// Snippet C
for (i = n; i >= 1; i /= 2)
System.out.println(i);
void f1(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < 10; j++) {
for(int k = 0; k < n; k++) {
for(int m = 0; m < 10; m++) {
System.out.println("!");
}
}
}
}
}
// Snippet 1 - processFixedGrid
public void processFixedGrid(int n) {
int sum = 0;
for (int i = 1; i <= 10; i++)
for (int j = 1; j <= 5; j++)
sum = sum + i + j;
System.out.println("Result " + n + " is " + sum);
}
// Snippet 2 - sqrtSearch (recursive, trace for sqrtSearch(n, 0, n))
public int sqrtSearch(int n, int low, int high) {
if (low > high) return high;
int mid = (low + high) / 2;
long square = (long) mid * mid;
if (square == n) return mid;
if (square < n) return sqrtSearch(n, mid + 1, high);
else return sqrtSearch(n, low, mid - 1);
}
silly(8,0). Show the trace.
public int silly(int n, int m) {
if (n < 1) return m;
else return silly(n/2, m);
}
// Call: silly(8, 0)
recur(32)
int recur(int n) {
if (n == 1) return 0;
return 1 + recur(n / 2);
}
// Call: recur(32)
f2(15, 5) and give the Big-O notation.
int f2(int n, int m) {
if (n == 0) return 1;
if (n % 2 == 0) return f2(n/2, m);
else return f2((n-1)/2, m-1);
}
// Trace: f2(15, 5)
productDigits(2121) - fill in the table. What is
the Big-O? Then complete the linked-list version
productDigitsList(Node head).
public static int productDigits(int n) {
if (n == 0) return 1;
return (n % 10) * productDigits(n / 10);
}
// Example: productDigits(234) = 2 × 3 × 4 = 24
fun(n). Show
the output when n=3 and draw the recursion trace.
static void fun(int n) {
if (n < 1) return;
else {
System.out.println(n);
fun(n - 1);
System.out.println(n);
return;
}
}
// Call: fun(3)
[ K | R | A | T | E | L | P | U | I ]
[3, -1, -6, 0, -8, 4, 2, 1, -1, -2, 1]
[1, 2, 3, 4, 5, 6, 7] → sum of odds =
16
Scroll up to see detailed feedback under each question.