Đề Thi FE MAD101 - SP26 - B5 - FE - RE

[adminadmin is verified member.]

Học kỳ

SP2026

Thời Gian

6/5/26

Loại tài liệu

FE

MAD101 SP26 B5 FE RE

Question 1 (Choose 1 answer)Let $A=\{0,2,4,6,8,10\}$ Find the cardinality of the power set P(A). A. 64 B. 32 C. 12 D. 36 E. None of the other choices is correct F. 6




Question 2 (Choose 1 answer)How many positive integers not exceeding 999 and divisible by neither 3 nor 4? A. 500 B. 499 C. 453 D. 536 E. None of the other choices is correct




Question 3 (Choose 1 answer)How many non-isomorphic spanning trees does the following graph have? (See picture) A. 8 B. 4 C. 6 D. 3




Question 4 (Choose 1 answer)Suppose that the domain of the propositional function P(x) consists of -1, 0, 1, 2. Which of the following statement expresses "$\neg \exists x P(x)$"? A. (iii) B. (i) C. (iv) D. None of the other choices is correct. E. (ii) (Note: (i) $P(-1)\vee P(0)\vee P(1)\vee P(2)$; (ii) $\neg P(-1)\wedge\neg P(0)\wedge\neg P(1)\wedge\neg P(2)$; (iii) $\neg P(-1)\vee\neg P(0)\vee\neg P(1)\vee\neg P(2)$; (iv) $P(-1)\wedge P(0)\wedge P(1)\wedge P(2)$)




Question 5 (Choose 1 answer)Which of the following graphs have Euler circuits? (i) $K_5$; (ii) $C_{20}$; (iii) $W_{10}$ A. (i) B. (i), (ii) and (iii) D. (i) and (ii)




Question 6 (Choose 1 answer)Which number is congruent to 10 modulo 17? A. -65 B. -75 C. -85 D. -95 E. None of the other choices is correct




Question 7 (Choose 1 answer)If the product of two integers is $2^8 3^7 5^2 7^5$ and their least common multiple is $2^4 3^4 5^1 7^3$, then their greatest common divisor is A. 1,111,320 B. 740,880 C. None of the other choices D. 952,560 E. 592,704




Question 8 (Choose 1 answer)Let f be recursively defined as $f(0)=1, f(1)=2$ and $f(n+1)=2f-f(n-1)$ for all positive integer n. Find f(2010). A. 4020 B. 2011 C. 2010 D. 505 E. None of the other choices is correct




Question 9 (Choose 1 answer)Given the Insertion sort algorithm. If input 3, 2, 4, 7, 1, 6, 5, after running the outer loop with $i=5$, the order of the elements in the list is A. 1, 2, 3, 4, 7, 6, 5 B. 1, 2, 3, 7, 4, 6, 5 C. 1, 2, 3, 4, 6, 7, 5 D. 1, 2, 3, 4, 7, 5, 6




Question 10 (Choose 1 answer)Find f(16) given that $f(1)=2$ and $f=(f(n/4))^2$. A. 4 B. 2 C. None of the other choices is correct D. 8 E. 16




Question 11 (Choose 1 answer)Two integers a and b are relatively prime if GCD(a,b)=1. Which of the following pairs of numbers is relatively prime? A. (143, 22) B. (81, 63) C. None of the other choices is correct D. (21, 93)




Question 12 (Choose 1 answer)Let f: N -> N be a function defined by $f=2n+3$. Select the correct statement. A. f is onto but not one-to-one. B. f is one-to-one but not onto. C. f is neither one-to-one nor onto. D. f is a bijection.




Question 13 (Choose 1 answer)Find the sum in binary representation $10111 + 10110 + 10111$. A. 1100101 B. 1100111 C. 1000101 D. 1010101




Question 14 (Choose 1 answer)Find the average number of bits used to encode a letter when using a Huffman coding for the characters with their frequencies: A: 0.25, B: 0.45, C: 0.1, D: 0.2 A. 1.85 B. 1.35 C. 1.4 D. 1.6 E. None of the other choices is correct




Question 15 (Choose 1 answer)Which set has the maximum cardinality? (Here x is an integer). $X=\{x | [cite_start]-100 < x^2 < 100\}$ $Y=\{x | [cite_start]-1 < x < 12\}$ $Z=\{x | x^2 = 100\}$ $W=\{x | x^4 = 256\}$ A. W B. X C. Z D. Y




Question 16 (Choose 1 answer)Find the inorder traversal of the tree (See picture with nodes a, c, e, h, m, n, s, t, y). A. e-c-h-a-n-m-s-t-y B. None of the other choices is correct C. e-c-h-n-m-s-t-y-a D. e-h-c-n-s-y-t-m-a E. a-c-e-h-m-n-t-s-y




Question 17 (Choose 1 answer)Let a = 131 div 37 and b = -131 div 37. Find a - b. A. 7 B. -1 C. 3 D. 4 E. 5




Question 18 (Choose 1 answer)Find the negation of the proposition: "If I have one million dollars then I will buy a villa". (i) "If I have one million dollars then I will not buy a villa" (ii) "I have one million dollars but I will not buy a villa" (iii) "I will buy a villa as soon as I have one million dollars" A. (i) B. (ii) C. (iii) D. None of them is correct.




Question 19 (Choose 1 answer)What is the largest integer n for which one can solve within 1 second a problem using an algorithm that requires $f = 2^n$ bit operations, where each bit operation is carried out in $10^{-9}$ seconds? A. 27 B. 29 C. 28 D. 30




Question 20 (Choose 1 answer)Which graphs are trees? (i), (ii), (iii) A. All of (i), (ii) and (iii) B. None of the other choices is correct C. (ii) D. (iii) E. (i)




Question 21 (Choose 1 answer)Find the smallest integer n such that the following function is O($x^n$): $x^2 + x^2 \log x$. A. 3 B. 4 C. 1 D. 2 E. 0




Question 22 (Choose 1 answer)Find the value of the prefix expression - 4 3 2 5 / 8 4 (Note: based on source text -4325/84). A. 12 B. 11 C. 10 D. 13 E. 14




Question 23 (Choose 1 answer)How many internal vertices in a full 3-ary tree with 101 leaves? A. 151 B. 104 C. 50 D. None of the other choices is correct E. 51




Question 24 (Choose 1 answer)What is the total weight of a minimum spanning tree produced by the graph below? (Graph with vertices A, B, C, D, E, F and weights). A. None of the other choices is correct B. 12 C. 11 D. 8 E. 9




Question 25 (Choose 1 answer)Which argument is valid? A. I will miss the class if it is raining. I missed class today. Therefore it was raining. B. All parrots can speak. My bird is not a parrot. Therefore my bird can not speak. C. Anyone who exercises everyday is healthy. Tung is not healthy. Therefore Tung has not exercised everyday. D. Any student can borrow books. Nam can borrow books. Therefore Nam is a student.




Question 26 (Choose 1 answer)How many functions from the set {1, 2, 3...10} to the set {0, 1, 2} such that f(1)=1 and f(10)=2? A. 6561 B. 2187 C. 59049 D. 19683 E. None of the other choices is correct




Question 27 (Choose 1 answer)Let f be the function from N to N such that $f(x) = \lfloor x/2 \rfloor$. Which of the following statements is true? A. f is onto but not one-to-one B. f is one-to-one but not onto C. f is a bijection D. f is neither one-to-one nor onto




Question 28 (Choose 1 answer)Find the correct order of steps of a proof by induction for the problem: Any postage of 8 cents or more can be formed using only 3-cent and 5-cent stamps.

1. To form a (n+1)-cent postage...
   
   
   
   
2. Let k be a number at least 10, and assume any k-cent postage can be formed...
   
   
   
   
3. We have 8=3+5, 9=3+3, 10=2*5...
   
   
   
   
4. By strong induction... A. 2, 1, 4, 3 B. 1, 4, 3, 2 C. 1, 3, 2, 4 D. 1, 2, 3, 4 E. 3, 2, 1, 4 F. None of the other choices is correct
   
   
   

Question 29 (Choose 1 answer)Let A be the adjacency matrix of a graph G. How many edges does G have? $A = \begin{bmatrix} 2 & 1 & 2 \\ 1 & 0 & 3 \\ 2 & 3 & 1 \end{bmatrix}$. A. 15 B. 12 C. 9 D. 6




Question 30 (Choose 1 answer)The proposition $\forall x \exists y (x = y^2)$ is True if the domain of x, y is... A. the set of positive real numbers B. the set of positive integers C. the set of integers D. None of the other choices is correct E. the set of real numbers




Question 31 (Choose 1 answer)Find the double sum: $\sum_{i=1}^4 \sum_{j=0}^3 (2i + j^2)$. A. 1440 B. 240 C. 136 D. 132 E. 92




Question 32 (Choose 1 answer)Given a recursive relation $a_n = -3a_{n-1} + 4a_{n-2}$. Which of the following formulas satisfy this relation? (i) $a_n = -12$; (ii) $a_n = (-4)^n$; (iii) $a_n = -1$. A. (i) B. (ii) C. (iii) D. (i), (ii) and (iii) E. None of the other choices is correct




Question 33 (Choose 1 answer)Find a proposition with the given truth table (T,T->T; T,F->T; F,T->F; F,F->T). (i) $p \rightarrow q$; (ii) $q \rightarrow p$; (iii) $p \rightarrow \neg q$; (iv) $q \rightarrow \neg p$. B. (iv) C. (ii) D. (i)




Question 34 (Choose 1 answer)How many subgraphs with exactly 2 vertices in the complete graph $K_n$ with n=37? A. 6 B. 3 C. 5 D. 4 E. None of the other choices is correct




Question 35 (Choose 1 answer)Given two graphs. Which statements are correct? (i) These two graphs are not isomorphic because they have a different number of vertices of degree two. (ii) These two graphs are isomorphic because they have the same number of edges. A. (i) and (ii) are both correct. B. Only (i) C. (i) and (ii) are both incorrect. D. Only (ii)




Question 36 (Choose 1 answer)Use the Greedy Change-Making algorithm to make a change for 34 cents using quarters (25), dimes (10) and pennies (1). What is the total number of coins used? A. 7 B. 8 C. 9 D. 10 E. None of the other choices




Question 37 (Choose 1 answer)The complexity of Dijkstra's algorithm... in a connected simple undirected weighted graph with n vertices is (i) O(n log n); (ii) $O(n^2)$; (iii) O; (iv) $O(n^2 \log n)$. A. (i) B. (iv) C. (ii) D. (iii)




Question 38 (Choose 1 answer)How many connected components are there in this graph? (See picture). A. 2 B. 0 C. 1 D. 4 E. 3




Question 39 (Choose 1 answer)Let S be the set of all directed graphs with sequence (out-degree, in-degree): [(2, 2), (2, 2), (2, 1), (2, 3)]. Which is TRUE: (i) G has no Euler paths (ii) G has an Euler circuit (iii) G has an Euler path, but no Euler circuits A. (ii) B. (i) C. (iii) D. None of the other choices




Question 40 (Choose 1 answer)How many cut-edges in this graph? (See picture). A. 4 B. 0 C. 1 D. None of the other choices is correct E. 5




Question 41 (Choose 1 answer)Use Huffman coding to encode the message "glaciology". What is the average number of bits required to encode a character? (Round to 2 decimal places). A. 3.00 B. 3.21 C. 2.80 D. 4.00




Question 42 (Choose 1 answer)A complete bipartite graph $K_{m,n}$ (m>1, n>1) with 15 edges has A. None of the other choices B. 10 vertices C. 7 vertices D. 8 vertices E. 9 vertices




Question 43 (Choose 1 answer)Given the recursive algorithm Procedure RE. If n=0 then RE(0)=0 else RE = n - RE(RE(n-1)). Find RE(8). A. 5 B. 7 C. 1 D. 6 E. None of the other choices is correct




Question 44 (Choose 1 answer)Find gcd(851, 931). A. 7 B. 19 C. 23 D. 37 E. None of the other choices is correct




Question 45 (Choose 1 answer)How many comparisons are needed to merge two ordered lists [1, 3, 5, 7, 9] and [2, 5] to an increasingly ordered list? A. 5 B. 6 C. 7 D. 8 E. 9




Question 46 (Choose 1 answer)Let P(x) be "x is even" and Q(x) be "x is odd" (domain: natural numbers). Which propositions are true? (i) $\forall x \forall y ((P(x) \wedge P) \rightarrow Q(xy))$ (ii) $\forall x \forall y ((P(x) \wedge P) \rightarrow P(xy))$ (iii) $\exists x \exists y ((P(x) \wedge Q) \rightarrow P(x+y))$ A. (i) and (ii) B. (ii) and (iii) C. Only (iii) D. Only (i) E. Only (ii)




Question 47 (Choose 1 answer)Suppose the domain of P(x) consists of -1, 0, 1, 2. Which is logically equivalent to "$\exists x P(x)$"? A. None of the other choices is correct. B. (ii) C. (iv) D. (iii) E. (i) (Note: (i) $P(-1)\vee P(0)\vee P(1)\vee P(2)$; (ii) $\neg P(-1)\vee P(0)\vee P(1)\vee P(2)$; (iii) $\neg P(-1)\wedge P(0)\vee P(1)\vee P(2)$; (iv) $P(-1)\wedge P(0)\wedge P(1)\wedge P(2)$)




Question 48 (Choose 1 answer)Find the cardinality of the set {1, {1}, 1, 3, {1, 3}}. A. 2 B. 3 C. 5 D. 4 E. None of the other choices is correct




Question 49 (Choose 1 answer)Find the negation of the statement: "If you want to pass this course, then you should study hard and go to class regularly". A. If you want to pass this course, then you should not study hard and should not go to class regularly. B. If you do not want to pass this course, then you should study hard and go to class regularly. C. You want to pass this course, and you should not study hard or you should not go to class regularly. D. You do not want to pass this course, and you should study hard or you should go to class regularly.




Question 50 (Choose 1 answer)Find f(3) if $f = 2f(n-1) - 1$ for all positive integers n, and f(0) = 1. A. Cannot determine B. 4 C. 8 D. -8 E. None of the other choices is correct