WorksheetsUnit I- CS8391 Data structure
Total questions: 25
Worksheet time: 57mins
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
log2 n
n
log2 n-1
n/2
The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is
283
142
71
45
In Which data structure is used to traverse the elements in forward and backward direction
Circular singly linked list
Doubly linked list
Circular linked list
Singly Linked list
The condition that occurs when an attempt is made to insert data into a full data structure is
Overflow
Underflow
None
Void
Header(Sentinel/Dummy) in data structure list is used to point to
First node of list
Last node of the list
Null value
None
. In a linked list when an element is inserted
Memory is allocated to a node
Memory is deallocated to the node
Neither memory is allocated nor deallocated
None
What kind of linked list is best to answer question like "What is the item at position n"?
A.
B.
C.
D.
Singly linked list
Doubly linked list
Circular linked list
Array implementation of linked list
In a Circular doubly linked list the previous pointer of the first node
(a)
To delete the 6th element from singly linked list, the operation sequence is
(i) Link the 5th node to 7th node (ii) Free the 6th node (iii) Locate 5th and 6th node
a) b) c) iii,i,ii d) i,ii,iii
ii,i,iii
ii,iii,i
iii,i,ii
i,ii,iii
Which of the following application makes use of a circular linked list?
Undo operation in a text editor
Recursive function calls
Allocating CPU to resources
Implement Hash Tables
Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only.
Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
I and II
I and III
I, II and III
I, II and IV
Which of the following operations is performed more efficiently by doubly linked list than by singly linked list.
Deleting a node whose location is given
Searching an unsorted list for a given item
Inserting a node after the node with a given location
Traversing the list to process each node.
The minimum number of fields with each node of doubly linked list is
1
2
3
4
Consider the following definition in c programming language. Which of the following c code is used to create new node?
struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;
ptr = (NODE*)malloc(sizeof(NODE));
ptr = (NODE*)malloc(NODE);
ptr = (NODE*)malloc(sizeof(NODE*));
ptr = (NODE)malloc(sizeof(NODE));
Which of the following types of expressions does not require precedence rules for evaluation?
Fully parenthesized infix expression
Partially parenthesized infix expression
Both A) and B)
Prefix expression
In the linked list implementation of the stack class, where does the push method place the new entry on the linked list?
At the head
At the tail
After all other entries that are greater than the new entry.
After all other entries that are smaller than the new entry
Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. The CAPACITY is 42. Where does the push method place the new entry in the array?
data[0]
data[1]
data[9]
data[10]
Consider the usual algorithm for determining whether a sequence of parentheses is balanced. The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(())) are:
(a)
What is the value of the postfix expression 6 3 2 4 + – *?
(a)
The following sequence of operations is performed on stack: PUSH (10),PUSH (20),POP,PUSH (10),PUSH (20),POP,POP,POP,PUSH (20),POP The sequence of the value popped out is:
(a)
What will be the output of the below program? Three minutes
int main()
{
stack< string, vector<string> > s;
s.push( "me" );
s.push( "talk" );
s.push( "to" );
while ( !s.empty() )
{
cout << s.top() << " ";
s.pop();
}
cout <<"\n\n\n";
return 0;
}
talk to me
to talk me
me talk to
me to talk
Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.
Possible if size of linked list is even.
Possible if size of linked list is odd
Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X
What is the output of the following function when the list contains the values: 1,4,67,3,45,68,2(head points to the first node- not the dummy node)
void fun1(struct node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}
2 2 2 2 2 2 2
2 68 45 3 67 4 1
1 67 45 2 4 3 68
1 4 67 3 45 68 2
What is the output of the following function if the given value of n is 81
void fun(int n)
{
Stack S = (stack ) malloc (size of (struct node));
while (n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);
n = n/2;
}
while (!isEmpty(&S))
printf("%d ", pop(&S)); // pop an element from S and print it
}
1010001
1000101
1100101
1110011
Assume that the operators +, -, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b × c + d ^ e ^ f is
(a)
