Grade XII – Computer Science
Unit 1 – Data Structure Examples
Question 30.
(I) Define a stack that will store only those words that have an even number of
vowels.
Define the following functions for the operations:
(a) Pushword(): To accept a word and push it to the stack after necessary checking.
(b) Popword(): To pop a word from the stack.
Or
(II) Write a user-defined function PushNames(n) that takes a name as a parameter
and pushes it to stack, only if it is present in the list given below:
L=[“USA”,”INDIA”,”GERMANY”,”FRANCE”]
Answer:
(I) wrdstack = .[]
(a) def Pushword(w):
c = 0
for ch in w:
if ch in "aeiouAEIOU":
c += 1
if c % 2 == 0:
[Link](w)
(b) def Popword():
if not wrdstack:
print("Stack empty")
else:
[Link]()
Pushword("hello")
Pushword("moon")
Popword()
Or
(II) stk = []
countries = ["USA", "INDIA", "GERMANY", "FRANCE"]
def PushName(n):
if n in countries:
[Link](n)
return f’{n} has been added to the stack.’
else:
return f’{n} is not in the list of countries.’
result = PushName(“USA”)
print(result)
The stack Admissionstack[] is a list implement stack comprising of student
records of the following structure:
[Rno, Name, Class, Grade]
Define functions for the following:
(a) enterstack(slst): Function to push a student record to the stack only if
the student has a grade “A”.
(b) getstack(): Function to pop and show the topmost student of the stack.
(c) peepstack(): Function t displays all the student records without
removing any record.
Or
(i) Define the operations possible on a stack.
(ii) Define a function push2_5() to push numbers into a stack, only if the
numbers end with 2 or 5.
Answer:
Admissionstack = []
def enterstack(slst):
if slst[3] == "A":
[Link](slst)
def getstack():
if not Admissionstack:
print("No students")
else:
return [Link]()
def peepstack():
if not Admissionstack:
print("No students")
else:
p = len(Admissionstack) - 1
while p >= 0:
print(Admissionstack[p])
p -= 1
Or
(i) A stack allows the following operations:
Push(): This function pushes an element into the stack keeping the LIFO
principle, which means the element is pushed to the top of the stack.
Pop() This function takes out the topmost element from the stack and
displays it.
Traversal(): This function displays each of the stack contents from top
index to 0 with the LIFO principle. It does not remove the elements.
(ii) stack=[]
def push2_5(n):
if n%10==2 or n%10==5:
[Link](n)
Write a program to print a string in reverse order using the following
functions.
pushstack(stack, character) Function to push a character into the
stack
popstack(stack) Function pop all the elements from the stack
isempty() Function to check whether the stack is empty or not.
Or
(b) (i) Define a stack.
(ii) Give a few applications of stack.
(iii) Give any two characteristics of stacks.
Answer:
(a) def pushstack(stack. ch):
[Link](ch)
top=len(stack)-1
return
def popstack(stack):
if isempty(stack):
return
else:
top=len(stack)-1
for a in range(top, -1, -1):
print(stack[a])
return
def isempty(stack):
if stack==[]:
return True
else:
return False
#--------------main-----------------
stk=[]
top=None
str=input("Enter a string”)
for a in str:
pushstack(stk, a)
print("----------Reverse-------------")
popstack(stk)
Or
(b) (i) A stack is a data structure that allows the addition and removal of
elements in a particular order.
Every time an element is added, it goes on the top of the stack and the
only element that can be removed is the element that was at the top of
the stack.
(ii) Applications of stack
Expression evaluation
Backtracking (game playing, finding paths, exhaustive searching).
Memory management, run-time environment for nested language
features.
(iii) Characteristics of Stacks:
It is a LIFO data structure.
The insertion and deletion happen at one end. i.e. from the top of the
stack.
(a) A linear stack called status contains the following information:
Phone number of Employee
Name of Employee
Write the following methods to perform given operations on the
stack status:
Push_element() To Push an object containing the Phone number of
the Employee and the Name of the Employee into the stack.
Pop_element() To Pop an object from the stack and to release the
memory.
Or
(b) Write a program with functions as detailed below, to operate on
a stack storing palindrome numbers only.
Answer:
(a) def Push_element (Status, Top):
phone_no = int(input (“Enter phone number :”))
emp_name = input ("Enter employee name :”)
St = (phone_no, emp_name)
[Link] (St)
Top = Top + 1
return Top
def Pop_element (Status, Top):
Slen = len(Status)
if (Slen==0):
print (“Status is empty”)
else:
phone_no, emp_name = Status. Pop ()
Top = Top - 1
print(“Phone number %s and name %s deleted”)
%(phone_no, emp_name)
return Top
Or
(b) pal nums = []
def pushpals(n):
t=str(n)
if t==[Link]()
[Link](n)
ans='y'
while ans=='y':
n=input(“Enter a number :”)
pushpals (n)
ans=input(“Add more(y/n)”)
Julie has created a dictionary containing names and marks as key-value
pairs of 6 students. Write a program, with separate user-defined functions
to perform the following operations.
Push the keys (name of the student) of the dictionary into a stack, where
the corresponding value (marks) is greater than 75.
Pop and display the content of the stack.
For example, If the sample content of the dictionary is as follows.
R={“OM”:76, “JAI”:45, “BOB”:89, “ALI”:65, “ANU”:90, “TOM”:82}
The output from the program should be
TOM ANU BOB OM
Or
Alam has a list containing 10 integers. You need to help him create a
program with separate user-defined functions to perform the given
operations based on this list.
Traverse the content of the list and push the even numbers into a stack.
Pop and display the content of the stack.
For example, If the sample content of the list is as follows.
N=[12, 13, 34, 56, 21, 79, 98, 22, 35, 38]
Sample Output of the code should be:
38 22 98 56 34 12
Answer:
R={"0M":76, "JAI":45. "BOB":89, "ALI":65, "ANU":90, "TOM":82}
def PUSH(S,N):
[Link](N)
def POP(S):
if S!=[]:
return [Link]()
else:
return None
ST=[ ]
for k in R:
if R[k]>=75:
PUSH(ST,k)
while True:
if ST!=[]:
print(POP(ST),end=" ")
else:
break
Or
N=[12, 13, 34, 56, 21, 79, 98, 22, 35, 38]
def PUSH(S,N):
[Link](N)
def POP(S):
if S!=[ ]:
return [Link]()
else:
return None
ST=[ ]
for k in N:
if k%2==0:
PUSH(ST,k)
while True:
if ST!=[ ]:
print(POP(ST),end=" ")
else:
break
(a) Consider the following sequence of numbers:
1234
These are supposed to be operated through a stack to produce the following
sequence of numbers.
2143
List the push and pop operations to get the required sequence of numbers.
(i) Push(1)
(ii) Push(2)
(iii) Pop(2)
(iv) Pop(1)
(v) Push(3)
(vi) Push(4)
(vii) Pop(4)
(viii) Pop(3)
Or
(b) Suppose STACK is allocated 6 memory locations and initially STACK is empty
with Top=0.
Give the output of the following program segment:
AAA=4
BBB=6
Push(STACK,AAA)
Push(STACK,4)
Push(STACK, BBB+2)
Push(STACK,AAA+BBB)
Push(SJACK,10)
While Top>0:
Element=[Link]()
Print(Element)
Answer:
(A) To transform the sequence [1,2,3,4] into [2,1,4,3] using stack operations, the
push and pop operations can be listed as follows:
1. Push(1)
2. Push(2)
3. Pop(2) (Popped value: 2)
4. Pop(1) (Popped value: 1)
5. Push(3)
6. Push(4)
7. Pop(4) (Popped value: 4)
8. Pop(3) (Popped value: 3)
(B) 10
10
8
4
4