# Stable Marriage Problem Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Stable Marriage Problem”.

1. Stable marriage problem is an example of?
a) Branch and bound algorithm
b) Backtracking algorithm
c) Greedy algorithm
d) Divide and conquer algorithm
View Answer

Answer: b
Explanation: Stable marriage problem is an example for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution.

2. Which of the following algorithms does Stable marriage problem uses?
a) Gale-Shapley algorithm
b) Dijkstra’s algorithm
c) Ford-Fulkerson algorithm
d) Prim’s algorithm
View Answer

Answer: a
Explanation: Stable marriage problem uses Gale-Shapley algorithm. Maximum flow problem uses Ford-Fulkerson algorithm. Prim’s algorithm involves minimum spanning tree.

3. An optimal solution satisfying men’s preferences is said to be?
a) Man optimal
b) Woman optimal
c) Pair optimal
d) Best optimal
View Answer

Answer: a
Explanation: An optimal solution satisfying men’s preferences are said to be man optimal. An optimal solution satisfying woman’s preferences are said to be woman optimal.
advertisement
advertisement

4. When a free man proposes to an available woman, which of the following happens?
a) She will think and decide
b) She will reject
c) She will replace her current mate
d) She will accept
View Answer

Answer: d
Explanation: When a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list.

5. If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.
a) True
b) False
View Answer

Answer: a
Explanation: If there are n couples such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. How many 2*2 matrices are used in this problem?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: b
Explanation: Two 2*2 matrices are used. One for men representing corresponding woman and ranking and the other for women.

7. What happens when a free man approaches a married woman?
a) She simply rejects him
b) She simply replaces her mate with him
c) She goes through her preference list and accordingly, she replaces her current mate with him
d) She accepts his proposal
View Answer

Answer: c
Explanation: If the preference of the man is greater, she replaces her current mate with him, leaving her current mate free.
advertisement

8. In case of stability, how many symmetric possibilities of trouble can occur?
a) 1
b) 2
c) 4
d) 3
View Answer

Answer: b
Explanation: Possibilities- There might be a woman pw, preferred to w by m, who herself prefers m to be her husband and the same applies to man as well.

9. Consider the following ranking matrix. Assume that M1 and W2 are married. Now, M2 approaches W2. Which of the following happens?

a) W2 replaces M1 with M2
b) W2 rejects M2
c) W2 accepts both M1 and M2
d) W2 rejects both M1 and M2
View Answer

Answer: a
Explanation: W2 is married to M1. But the preference of W2 has M2 before M1. Hence, W2 replaces M1 with M2.
advertisement

10. Consider the following ranking matrix. Assume that M1 and W1 are married and M2 and W3 are married. Now, whom will M3 approach first?

a) W1
b) W2
c) W3
d) All three
View Answer

Answer: c
Explanation: M3 will approach W3 first. Since W3 is married and since her preference list has her current mate before M3, she rejects his proposal.

11. Who formulated a straight forward backtracking scheme for stable marriage problem?
a) McVitie and Wilson
b) Gale
c) Ford and Fulkerson
d) Dinitz
View Answer

Answer: a
Explanation: McVitie and Wilson formulated a much faster straight forward backtracking scheme for stable marriage problem. Ford and Fulkerson formulated Maximum flow problem.

12. Can stable marriage cannot be solved using branch and bound algorithm.
a) True
b) False
View Answer

Answer: b
Explanation: Stable marriage problem can be solved using branch and bound approach because branch and bound follows backtracking scheme with a limitation factor.

13. What is the prime task of the stable marriage problem?
a) To provide man optimal solution
b) To provide woman optimal solution
c) To determine stability of marriage
d) To use backtracking approach
View Answer

Answer: c
Explanation: The prime task of stable marriage problem is to determine stability of marriage (i.e) finding a man and a woman who prefer each other to others.

14. Which of the following problems is related to stable marriage problem?
a) Choice of school by students
b) N-queen problem
c) Arranging data in a database
d) Knapsack problem
View Answer

Answer: a
Explanation: Choice of school by students is the most related example in the given set of options since both school and students will have a preference list.

15. What is the efficiency of Gale-Shapley algorithm used in stable marriage problem?
a) O(N)
b) O(N log N)
c) O(N2)
d) O(log N)
View Answer

Answer: c
Explanation: The time efficiency of Gale-Shapley algorithm is mathematically found to be O(N2) where N denotes stable marriage problem.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.