Suez Canal University
Faculty of Computers and Informatics
Computer Science Department
Course Name: Data Structures Date:2-12-2020
Course Code: CS513 Time allowed: 1.5 hours
Year: 2nd year No. of Pages: 2 pages
Semester: First Total marks: 20
Midterm Exam – Academic Year 2020-2021
Answer all the following questions.
Question 1: Choose the correct answer.
1. Suppose p refers to a node in a linked list (using the Node class). Which Boolean expression
will be true when p refers to the second node of the list?
a) p==head->next; b) p ==head ;
c) p->next == NULL ; d) None of these.
2. Which Boolean expression indicates whether the data in the two nodes referred by p and q are
different? Assume that neither p nor q is NULL.
a) p->info!=q->info; b) p->next == q->next ;
c) p->info == q->info ; d) None of these.
3. Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
What is the maximum number of parentheses that will appear on the stack AT ANY ONE
TIME when the algorithm analyzes: (( )( )(( )))?
a) 1 b) 3
c) 2 d) 4
4. Consider the following algorithm:
declare a stack of characters
while ( there are more characters in the word to read )
{ read a character and push the character on the stack }
while ( the stack is not empty )
{ pop a character off the stack and write the character to the
screen }
What is written to the screen for the input "school"?
a) school b) sscchhooooll
c) loohcs d) None of these
5. Which of the following stack operations could result in stack overflow?
a) isEmpty b) pop
c) push d) none of these
Question 2:
Page 1 of 2
1. Write a function called MergeArrays that takes two integer arrays as its arguments and
returns a new array which contains all elements in the two arrays without duplicates. Then
compute the time complexity T(n) of your code.
Function T(n)
void MergeArrays(int a[],int b[],int n,int m)
{
int c[n+m];
int i,j,k,flag;
for(i=0;i<n;i++) 1+(n+1)+n
c[i]=a[i]; n
for(j=0;j<m;j++) 1+(m+1)+m
{
flag=0; m
for(int k=0;k<n;k++) m*(1+n+1+n)
{
if(a[k]==b[j]) m*n
flag++; m*n
}
if(flag==0) m
c[i++]=b[j]; 2*m
}
}
1+(n+1)+n+n+1+(m+1)+m+
T(n) m+m*(1+n+1+n)+m*n+
m*n+m+2*m
2. What is the time complexity T(n) of the following codes:
a) int a = 0; 1 T(N)=1+1+(N+1)+N+
for (i = 1; i < N+1; i++) 1+(N+1)+N N*(1+(N+1)+N)+
for (j = N+1; j > 1; j--) N*(1+(N+1)+N) 3*N*N=O(N2)
a = a + i + j; 3*N*N
b) if(c > b) 1 T(n)=1+1+(n+1)+n+
{ n*(1+(n+1)+n)
for(j=1; j<=n ; j++) 1+(n+1)+n 3*n*n=O(n2)
a[i]+=j; 2n
}
else
{
for(j=1 ; j<=n ; j++) 1+(n+1)+n
for(k=1 ; k<n ; k++) n*(1+(n+1)+n)
a[i]=k*j; 3*n*n
}
Page 2 of 2
Question 3:
a) Write a function void pushOdd(Stack *s, int data) that pushes data into the stack s only if it is odd.
b) Convert the following infix expression: a-b/c+(d*(e/f))*g to postfix expression. Then explain how to
use the stack to evaluate this postfix expression.
Postfix expression: abc/-def/*g*+
Page 3 of 2
Page 4 of 2
Question 4:
Using the Node, List and CircularList classes, write the following functions:
1. void deleteEven (List l) which deletes every even data from a single linked list.
Page 5 of 2
2. int count (CircularList l) which counts the number of nodes in a circular list and returns it.
Dr. Safa Abd El-aziz
Page 6 of 2
