Vzor pˇrij´ımac´ıho testu do magistersk´eho studia oboru Otevˇren´a informatika Jm´eno
Pˇr´ıjmen´ı
VZOR Podpis
Vzorov´ y test obsahuje stejnˇe jako skuteˇcn´ y test 35 ot´azek. Na jeho vyˇreˇsen´ı m´ate 90 minut ˇcasu. Kaˇzd´ a ot´ azka ’ ’ obsahuje pr´avˇe jednu spr´ avnou odpovˇed . Vaˇs´ım u ´kolem je spr´avnou odpovˇed oznaˇcit pˇreˇskrtnut´ım ˇctvercov´eho pol´ıˇcka u pˇr´ısluˇsn´eho p´ısmena oznaˇcuj´ıc´ıho spr´ avnou odpovˇed’. Spr´avnˇe oznaˇcen´a odpovˇed’ vypad´a takto napˇr. B 4. Vˇse ostatn´ı je ˇspatnˇe oznaˇcen´ a odpovˇed’. Opravy nejsou povoleny, proto si odpovˇed’ dobˇre rozmyslete.
Ot´ azka 1 Definujme n´asleduj´ıc´ı relaci na mnoˇzinˇe re´ aln´ ych ˇc´ısel IR: R = {(x, y) ∈ IR2 ; x2 − y 2 je cel´e ˇc´ıslo}. Rozhodnˇete, kter´e z n´ asleduj´ıc´ıch tvrzen´ı je pravdiv´e: A R je reflexivn´ı a antisymetrick´ a.
A B C D E
2 2 2 2 2
A B C D
2 2 2 2
B R je reflexivn´ı, nen´ı tranzitivn´ı. C R je reflexivn´ı, symetrick´ a a uspoˇr´ ad´ an´ı. D R je reflexivn´ı, symetrick´ a, tranzitivn´ı a ekvivalence. E R je reflexivn´ı, antisymetrick´ a, tranzitivn´ı a ekvivalence.
Ot´ azka 2 Je d´ana funkce int rek1(): static int rek1(int s, int t) { int rek1; if (s > 0) rek1 = rek1(s - 1, t) + t; else rek1 = 0; return rek1; } Urˇcete hodnotu funkce pro rek1(3, 4), rek1(3, -4) a pro rek1(-3, 4): A 12, −12, 0 B 12, −12, 1 C 7, −7, 1 D 7, −1, 0
1
Ot´ azka 3 Urˇcete hodnotu n tak, aby byla procedura xyz() vol´ana pr´avˇe 1400 kr´at. for (i=0; i < 70; i++) { j = 0; while (j < 90) { if (j > n ) xyz(); j++; } }
A B C D
2 2 2 2
A B C
2 2 2
A B C
2 2 2
A B C D
2 2 2 2
A B C D
2 2 2 2
A n = 69 B n = 70 C n = 68 D n = 71
Ot´ azka 4 Mˇejme dvˇe booleovsk´e funkce f0 (x, y, z) = (x xor z) or (x and z) a f1 (x, y, z) = x or z, kde x, y, z jsou vstupn´ı promˇenn´e. Rozhodnˇete, zda funkce f0 a f1 jsou totoˇzn´e, ˇci r˚ uzn´e. A Jsou stejn´e. B Jsou r˚ uzn´e. C Nelze urˇcit.
Ot´ azka 5 Polymorfismus mohu v Javˇe realizovat: A Abstraktn´ı tˇr´ıdou ˇci rozhran´ım. B Pouze abstraktn´ı tˇr´ıdou. C Pouze rozhran´ım.
Ot´ azka 6 Procesor m´a 24bitovou adresovou sbˇernici a 16bitovou datovou sbˇernici. Jak´e nejvˇetˇs´ı mnoˇzstv´ı pamˇeti m˚ uˇze tento procesor adresovat: A 64kB B 1MB C 16MB D 1GB
Ot´ azka 7 Kter´e z n´asleduj´ıc´ıch tvrzen´ı je pravdiv´e: A Pro architekturu CISC je typick´e vˇetˇs´ı mnoˇzstv´ı identick´ ych univerz´aln´ıch registr˚ u B Architektura RISC podporuje i sloˇzit´e adresovac´ı m´ody C V´ ysledn´ y k´od je delˇs´ı pro architekturu RISC D Jedna instrukce architektury CISC se typicky vykon´av´a v jedin´em hodinov´em taktu
2
Ot´ azka 8 ˇ Ceho se vlastnˇe dos´ahne aplikac´ı superskal´ arn´ı architektury nebo pipeliningem? A Jedn´a se o dvˇe r˚ uzn´ a oznaˇcen´ı jedn´e techniky zv´ yˇsen´ı v´ ykonu CPU B Jde o dvˇe r˚ uzn´e techniky zv´ yˇsen´ı v´ ykonu CPU
A B C D
2 2 2 2
A B C D
2 2 2 2
C Jde o dvˇe r˚ uzn´e techniky ke sn´ıˇzen´ı pˇr´ıkonu CPU D S CPU tyto pojmy nesouvis´ı
Ot´ azka 9 Uvaˇzujte n´asleduj´ıc´ı program. Jak´ y bude jeho v´ ystup? abstract class Rodic { public int i; abstract int znasob(); void setI(int noveI) { i = noveI; } } class Potomek1 extends Rodic { int znasob() { return i * 2; } } class Potomek2 extends Rodic { int znasob() { return i * 3; } } public static void main(String[] args) { Rodic pot; pot = new Potomek1(); pot.setI(3); System.out.print(pot.znasob()+", "); pot = new Potomek2(); pot.setI(3); System.out.println(pot.znasob()); }
A 6, 9 B 6, 6 C 9, 9 D 9, 6
3
Ot´ azka 10 Mˇejte n´asleduj´ıc´ı program v jazyce C: int a,b; int fce(int *x, int y) { *x = (*x) + a; y = y + a; b = (*x) + y; return a + b; } a=2; b=3; Jak´ y je v´ ysledek vol´ an´ı funkce fce(&a, b)?
A B C D
2 2 2 2
A B C
2 2 2
A B C
2 2 2
A B C D E
2 2 2 2 2
A 11 B 14 C 15 D 16
Ot´ azka 11 Pro virtualizaci pamˇeti se vyuˇz´ıv´ a: A pouze str´ankov´ an´ı. B pouze segmentace. C kombinace segmentace se str´ ankov´ an´ım.
Ot´ azka 12 Funkce Ω - omega a O - omikron definuj´ı asymptotickou sloˇzitost. Kter´e z uveden´ ych tvrzen´ı je pravdiv´e: A x3 ∈ Ω(2x ) B 2x ∈ O(x20000 ) C 1.8 · x + 600 · log2 (x) ∈ O(x)
Ot´ azka 13 Je d´ana skupina pˇeti vektor˚ u v nˇejak´em line´ arn´ım prostoru L. V´ıme, ˇze ˇz´adn´ y vektor nen´ı n´asobkem jin´eho. Na z´akladˇe t´eto informace m˚ uˇzeme ˇr´ıci, ˇze: A dan´a skupina vektor˚ u je line´ arnˇe nez´ avisl´a. B dan´a skupina vektor˚ u je line´ arnˇe z´ avisl´ a. C pokud v t´eto skupinˇe vektor˚ u nen´ı nulov´ y vektor, je line´arnˇe nez´avisl´a. D dan´a skupina vektor˚ u m˚ uˇze b´ yt line´ arnˇe z´avisl´a i nez´avisl´a. E dan´a skupina vektor˚ u je line´ arnˇe nez´ avisl´ a jen tehdy, kdyˇz kaˇzd´ y vektor obsahuje alespoˇ n pˇet sloˇzek.
4
Ot´ azka 14 V regul´arn´ı matici A typu (n, n) prohod´ım prvn´ı ˇr´adek s druh´ ym a d´ale celou matici vyn´asob´ım konstantou p (p 6= 1). T´ım vznikne matice B. Plat´ı: A det A = −p · det B. B det B = −p · det A.
A B C D E
2 2 2 2 2
A B C D E
2 2 2 2 2
A B C
2 2 2
A B C D E
2 2 2 2 2
C det B = −(pn ) · det A. D det B = (−1)n · p · det A. E ˇz´adn´a z uveden´ ych rovnost´ı neplat´ı.
Ot´ azka 15 M´ame entitn´ı typy STUDENT a PREDMET. Zn´amku udˇelenou u zkouˇsky z dan´eho pˇredmˇetu dan´emu studentovi budeme na u ´rovni konceptu´ aln´ıho modelu modelovat: A Samostatn´ ym entitn´ım typem. B Atributem entitn´ıho typu STUDENT. C Atributem vztahu mezi entitn´ımi typy PREDMET a STUDENT. D Atributem entitn´ıho typu PREDMET. E Jinak
Ot´ azka 16 M´ate zadanou relaci tvoˇrenou spojen´ım dvou tabulek T1 a T2. Prim´arn´ı kl´ıˇc tabulky T1 je reprezentov´ an atributem PK, odpov´ıdaj´ıc´ı ciz´ı kl´ıˇc tabulky T2 je reprezentov´an atributem FK. Definice referenˇcn´ı integrity, jeˇz zajist´ı, aby pˇri zmˇenˇe hodnoty prim´ arn´ıho kl´ıˇce tabulky T1 doˇslo i k pˇr´ısluˇsn´e zmˇenˇe hodnoty ciz´ıho kl´ıˇce tabulky T2, A je vlastnost´ı prim´ arn´ıho kl´ıˇce a tud´ıˇz je souˇc´ast´ı definice tabulky T1. B je vlastnost´ı ciz´ıho kl´ıˇce a tud´ıˇz je souˇc´ ast´ı definice tabulky T2. C vzhledem k tomu, ˇze je vlastnost´ı p´ aru tabulek T1 a T2, nem˚ uˇze b´ yt souˇc´ast´ı definice jednotlov´ ych tabulek T1 ˇci T2.
Ot´ azka 17 Je d´an prost´ y neorientovan´ y graf G o n vrcholech a m hran´ach. Kter´e z n´asleduj´ıc´ıch tvrzen´ı je pravdiv´e? A Kdyˇz m > n, pak G je souvisl´ y graf. B Kdyˇz m < n, pak G je nesouvisl´ y graf. C Kdyˇz m = n, pak G obsahuje kruˇznici. D Kdyˇz m = n, pak G m´ a aspoˇ n dvˇe komponenty souvislosti. E Kdyˇz m < n, pak G nem´ a kruˇznici.
5
Ot´ azka 18 Zn´ame hodnoty line´ arn´ıho zobrazen´ı z L1 do L2 na b´azi B line´arn´ıho prostou L1 . Z toho plyne, ˇze: A hodnoty line´arn´ıho zobrazen´ı jsou jednoznaˇcnˇe urˇceny pro cel´ y definiˇcn´ı obor L1 . B je moˇzn´e spoˇc´ıtat j´ adro zobrazen´ı, ale mimo j´adro nejsou hodnoty zobrazen´ı jednoznaˇcnˇe urˇceny.
A B C D E
2 2 2 2 2
A B C
2 2 2
A B C D
2 2 2 2
A B C D
2 2 2 2
A B C
2 2 2
C m´ame m´alo informac´ı, abychom spoˇc´ıtali hodnotu zobrazen´ı v libovoln´em bodˇe L1 . D hodnoty zobrazen´ı na cel´em L1 jsou jednoznaˇcnˇe urˇceny jen v pˇr´ıpadˇe, ˇze zobrazen´ı je izomorfismus. E pokud zobrazen´ı nen´ı prost´e, nejsou jeho hodnoty na cel´em L1 jednoznaˇcnˇe urˇceny.
Ot´ azka 19 V jazyku Java se rozhran´ı (interface) liˇs´ı od abstraktn´ı tˇr´ıdy. Vyberte pravdiv´e tvrzen´ı. A Rozhran´ı obsahuje pouze abstraktn´ı metody, abstraktn´ı tˇr´ıda m˚ uˇze obsahovat i neabstraktn´ı metody B Rozhran´ı m˚ uˇze obsahovat libovoln´e poloˇzky, abstraktn´ı tˇr´ıda m˚ uˇze obsahovat pouze konstanty C Rozhran´ı m´a vˇzdy nadtˇr´ıdu (napˇr. object), abstraktn´ı tˇr´ıda nemus´ı m´ıt pˇredch˚ udce
Ot´ azka 20 Mˇejme dva algoritmy, kter´e zpracov´ avaj´ı informaci z pole ˇc´ısel o velikosti n. Algoritmus A m´a sloˇzitost a(n) ∈ Θ(n3 ), algoritmus B m´ a sloˇzitost b(n) ∈ Θ(n log(n)). Kter´e z n´asleduj´ıc´ıch tvrzen´ı je pravdiv´e. A Algoritmus B je vˇzdy rychlejˇs´ı neˇz algoritmus A. B Algoritmus B je pro n = 10000 rychlejˇs´ı neˇz algoritmus A. C Algoritmus B m˚ uˇze b´ yt pro n = 10000 pomalejˇs´ı neˇz algoritmus A. D Algoritmus B je rychlejˇs´ı neˇz A pouze pro mal´a n.
Ot´ azka 21 Architektura j´adra operaˇcn´ıho syst´emu (OS) vyuˇz´ıvaj´ıc´ı modelu ”klient-server” se A pouˇz´ıv´a pouze v distribuovan´ ych syst´emech. B pouˇz´ıv´a zejm´ena v distribuovan´ ych syst´emech, avˇsak modern´ı koncepce OS ji vyuˇz´ıvaj´ı i pro organizaci OS na b´ azi tzv. mikro-j´ adra. C pouˇz´ıv´a pouze v monolitick´ ych OS. D ve struktur´ach j´ adra OS nepouˇz´ıv´ a kv˚ uli ˇcasov´e n´aroˇcnosti a dalˇs´ım negativn´ım vlastnostem.
Ot´ azka 22 Kter´e z n´asleduj´ıc´ıch tvrzen´ı o velikosti datagramu v protokolu IPv4 je pravdiv´e: A Datagramy maj´ı pevnˇe danou velikost, kterou nelze zmˇenit. B Datagramy se mohou na cestˇe rozdˇelovat - fragmentovat. C IPv4 nezaruˇcuje doruˇcen´ı velk´ ych datagram˚ u. Nedoruˇcen´ı je ozn´ameno vys´ılaj´ıc´ımu stroji.
6
Ot´ azka 23 V pamˇeti na adrese 100 je uloˇzeno ˇc´ıslo 5. Pˇresnˇe v okamˇziku, kdyˇz mikroprocesor ˇcetl operaˇcn´ı k´ od instrukce INCB [100] (pˇriˇcti 1 k bytu uloˇzen´emu na adrese 100), poslal ˇcasovaˇc nemaskovan´e pˇreruˇsen´ı NMI vyvol´avaj´ıc´ı obsluˇzn´ y podprogram, kter´ y hodnotu na adrese 100 vyn´asob´ı 2. Pokud ˇz´adn´a dalˇs´ı operace jiˇz nezmˇen´ı byte na adrese 100, jak´ a bude jeho v´ ysledn´a hodnota?
A B C D
2 2 2 2
A B C
2 2 2
A B C D
2 2 2 2
A B C D E
2 2 2 2 2
A 10 B 11 C 12 D ze zad´an´ı nelze jednoznaˇcnˇe urˇcit v´ ysledek
Ot´ azka 24 Jak´ y je minim´aln´ı poˇcet logick´ ych hradel potˇrebn´ y k tomu, aby vznikl asynchronn´ı obvod typu RS (pozn. u RS logick´a jedniˇcka na vstupu S/R nastav´ı odpov´ıdaj´ı v´ ystup Q/¬Q do 1)? A 2 dvouvstupov´ a hradla typu NAND B 2 dvouvstupov´ a hradla typu NOR C 4 dvouvstupov´ a hradla NAND nebo NOR
Ot´ azka 25 Uvaˇzujme tuto funkci f (n) int f(int n) { int x=2; for (int i=1; i<=n; i=i+1) { x=x*x; } return x; } Urˇcete pˇribliˇznˇe pro jak´ a n bude f (n) < k. A n < log2 (k) B n < k · log2 (k) C n < log2 (log2 (k)) D n < 2k
Ot´ azka 26
30 9 nad ZZ42 (tj. poˇc´ıt´ame modulo 42) s parametrem a. Uvaˇzujme matici A = 4 a Urˇcete jak´ y je jej´ı determinant pro a = 1 a pro kter´e hodnoty a m´a tato matice nulov´ y determinant. A Pro a = 1 je |A| = 36. |A| = 0 pro a = 4, 11, 18, 25, 32, 39. B Pro a = 1 je |A| = −6. |A| = 0 pro a = 38, 17. C Pro a = 1 je |A| = 6. |A| = 0 pro a = 4, 25. D Pro a = 1 je |A| = 6. |A| = 0 pro a = 4, 11, 18, 25, 32, 39. E Pro a = 1 je |A| = 36. |A| = 0 pro a = 4, 25.
7
Ot´ azka 27 Matice A m´a n ˇr´adk˚ u, k sloupc˚ u a jej´ı hodnost je h. Jak vypad´a dimenze prostoru ˇreˇsen´ı dim homogenn´ı soustavy line´arn´ıch rovnic s touto matic´ı? A dim = n − h. B dim = min(n, k) − h.
A B C D E
2 2 2 2 2
A B C D E
2 2 2 2 2
A B C D
2 2 2 2
A B C D E
2 2 2 2 2
C dim = k − h. D pokud k > n pak dim = k − n, jinak je dim = 0. E z uveden´ ych informac´ı nelze dimenzi prostoru ˇreˇsen´ı urˇcit.
Ot´ azka 28 Kter´a z n´asleduj´ıc´ıch formul´ı γ je pravdiv´ a ve vˇsech ohodnocen´ıch, ve kterych je pravdiv´a mnoˇzina formul´ı ˇ {a ⇒ (b ∧ c), b ⇒ (a ∧ c)}. R´ık´ ame, ˇze γ je s´emantick´ ym d˚ usledkem mnoˇziny formul´ı. A c. B a ⇒ b. C b. D a. E c ⇒ b.
Ot´ azka 29 Rozhodnˇete, kter´e z n´ asleduj´ıc´ıch tvrzen´ı je pravdiv´e: A Mnoˇzina M vˇsech polynom˚ u s nez´ aporn´ ymi celoˇc´ıseln´ ymi koeficienty je spoˇcetn´a. D˚ ukaz pouˇzije faktu, ˇze zobrazen´ı T (a0 + a1 x + a2 x2 + . . .) = a0 z M na IN0 je bijekce. B Mnoˇzina M vˇsech ˇctvercov´ ych re´ aln´ ych matic 2 × 2 je spoˇcetn´a. a b = b2a · 3b · 5c · 7d c z M na IN je bijekce. D˚ ukaz pouˇzije faktu, ˇze zobrazen´ı T c d C Mnoˇzina M vˇsech polynom˚ u s nez´ aporn´ ymi celoˇc´ıseln´ ymi koeficienty je spoˇcetn´a. D˚ ukaz pouˇzije faktu, ˇze zobrazen´ı T (a0 + a1 x + a2 x2 + . . . + an xn ) = 2a0 · 3a1 · 5a2 · . . . · pn an z M na IN (kde pk je k-t´e prvoˇc´ıslo) je prost´e. D Mnoˇzina M vˇsech ˇctvercov´ ych re´ aln´ ych matic 2 × 2 je spoˇcetn´a. D˚ ukaz pouˇzije faktu, ˇze mnoˇzina vˇsech uspoˇr´adan´ ych ˇctveˇric ˇc´ısel je spoˇcetn´a.
Ot´ azka 30 Spoˇc´ıtejte, kolik existuje zobrazen´ı T z mnoˇziny A = {1, 2, 3, . . . , nA } do B = {1, 2, 3, . . . , nB } (zde nA ≥ 2, nB ≥ 23) takov´ ych, ˇze T (1) = 13 nebo T (2) = 23. A Je jich nB · nA − 2. B Je jich 2nA nB . C Je jich 2nB nA −1 − nB nA −2 . D Je jich nB nA −2 . E Je jich 2nA nB −1 − nA nB −2 + 1.
8
Ot´ azka 31 Najdˇete obecn´e ˇreˇsen´ı diferenˇcn´ı (rekursivn´ı) rovnice T (n + 2) − T (n + 1) − 6T (n) = 0 a urˇcete asymptotickou rychlost jeho r˚ ustu (ˇr´ ad).
A B C D E
2 2 2 2 2
A B C D E
2 2 2 2 2
A B C D E
2 2 2 2 2
A B C D E
2 2 2 2 2
A T (n) = Θ((−3)n ). B T (n) = Θ((−2)n ). C T (n) = Θ(n2n ). D T (n) = Θ(3n ). E T (n) = Θ(ln(n)(−2)n ).
Ot´ azka 32 Najdˇete a klasifikujte lok´ aln´ı extr´emy funkce f (x, y) = x2 + y 2 − ex−2 y 2 . A (2, 2) lok´aln´ı maximum, (2, −2) lok´ aln´ı minimum. B (0, 0) lok´aln´ı minimum, (2, 2) sedlov´ y bod, (2, −2) sedlov´ y bod. C (0, 2) lok´aln´ı maximum, (0, −2) lok´ aln´ı minimum. D (0, 0) sedlov´ y bod, (2, 2) lok´ aln´ı maximum, (2, −2) lok´aln´ı minimum. E (2, ±2) lok´aln´ı maximum.
Ot´ azka 33 Vyˇreˇs´ım homogenn´ı soustavu line´ arn´ıch rovnic s matic´ı A a b´azi prostoru ˇreˇsen´ı zap´ıˇsu do ˇr´adk˚ u matice B. D´ale ˇreˇs´ım soustavu Bx = 0 a b´ azi prostoru ˇreˇsen´ı zap´ıˇsi do ˇr´adk˚ u matice C. Jak´ y je vztah mezi ˇr´adky matice A, B a C? ˇ adky matice C jsou line´ A R´ arn´ımi kombinacemi ˇr´adk˚ u matice A, ale m˚ uˇze se st´at, ˇze nˇejak´ y ˇr´adek matice A nen´ı line´ arn´ı kombinac´ı ˇr´ adk˚ u matice C. ˇ adky matice B jsou line´ B R´ arn´ı kombinac´ı ˇr´adk˚ u matice A nebo ˇr´adk˚ u matice C. C Line´arn´ı obal ˇr´ adk˚ u matice A je roven line´arn´ımu obalu ˇr´adk˚ u matice C. D Poˇcet ˇr´adk˚ u matice C je vˇetˇs´ı neˇz poˇcet ˇr´adk˚ u matice A. ˇ adn´e z v´ E Z´ yˇse uveden´ ych tvrzen´ı obecnˇe neplat´ı.
Ot´ azka 34 Jsou d´any formule α : ∀x (P (x) ⇒ Q(x)) a β : ∀y ¬Q(y), kde P a Q jsou un´arn´ı predik´aty. Pro kterou formuli γ plat´ı, ˇze mnoˇzina {α, β, γ} je nesplniteln´a? A ∃x P (x). B ∀x (P (x) ∨ ¬P (x)). C ∃x ¬P (x). D ∀x (Q(x) ⇒ P (x)). E ∃x ¬Q(x).
9
Ot´ azka 35 Dvˇe paralelnˇe zpracov´ avan´e transakce nemohou poˇskodit konzistenci dat pr´avˇe tehdy, kdyˇz: 1. Jsou vykon´av´any s´eriovˇe. 2. Jsou vykon´av´any na stupni izolovanosti SERIALIZABLE. 3. Nedojde k jejich vz´ ajemn´emu uv´ aznut´ı. Kter´a tvrzen´ı plat´ı: A Pouze 1 B Pouze 2 C Pouze 3 D Pouze 1 a 2 E Pouze 1 a 3
10
A B C D E
2 2 2 2 2
