Tietorakennepaperi (1)
1. Monivalintakysymykset (2 pistettä per kysymys, yhteensä 20 pistettä)
1. Pinojen ja jonojen yleiset ominaisuudet ovat ( ).
A. Salli elementtien lisääminen ja poistaminen vain päätepisteessä
B. Kaikki ensimmäisenä sisään, viimeinen ulos
C. Kaikki on ensimmäinen sisään, ensimmäinen ulos
D. Yhteistä pohjaa ei ole
2. Linkitettynä tallennettu jono lisätään, kun suoritetaan lisäysoperaatio ( ).
A. Vain päätyosoitinta muokataan B. Pää- ja hännänosoittimet on muutettava
C. Muokkaa vain pyrstöosoitinta D. Kärki- ja pyrstöosoittimia saattaa tarvita muutoksia
3. Mikä seuraavista tietorakenteista on epälineaarinen rakenne? ( )
A. Jono B. Pino C. Lineaarinen taulukko D. Binääripuu
4. Jos on olemassa kaksiulotteinen taulukko A[m][n], olettaen, että A[0][0] on tallennettu kohtaan 644 (10) ja A[2][2] tallennettuna kohtaan 676 (10), jokainen alkio vie avaruuden, missä A[3][3][3][3](10) on tallennettu? Alaviite (10) osoittaa, että se ilmaistaan desimaalina.
A.688 B.678 C.692 D.696
5. Puita käytetään parhaiten esittämään ( ).
A. Järjestetyt tietoelementit B. Järjestämättömät tietoelementit
C. Data, jossa on haarautuvia hierarkkisia suhteita alkioiden välillä D. Data, jolla ei ole yhteyttä elementtien välillä
6. Binääripuun k:nnen kerroksen suurin solmujen määrä on ( ).
A.2k-1 B.2K+1 C.2K-1 D. 2k-1
7. Jos on järjestetty taulukko, jossa on 18 alkiota tallennettuna yksiulotteiseen taulukkoon A[19], ensimmäinen alkio sijoitetaan A[1]:een, ja nyt suoritetaan binäärihaku, jolloin vertailujonon alaindeksi A[3]:n löytämiseksi on ( )
A. 1,2,3 B. 9,5,2,3
C. 9,5,3 D. 9,4,2,3
8. Lajittele nopeasti n tietueen tiedostot, ja tarvittava aputallennustila on suunnilleen sama
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. Lineaarisissa taulukoissa (7, 34, 55, 25, 64, 46, 20, 10) hajautusfunktioksi, jos H(K)=K %9 on valittu hajautusfunktioksi, on ( ) alkioita, joiden hajautusosoite on 1.
A.1 B.2 C.3 D.4
10. Suuntaamaton graafi, jossa on 6 solmua, ja graafissa tulisi olla vähintään ( ) kaaria yhteyden varmistamiseksi.
A.5 B.6 C.7 D.8
2. Täytä aukot (1 piste per tyhjä, yhteensä 26 pistettä)
1. Algoritmin laatua arvioidaan yleensä neljästä näkökulmasta: _________, _________, _________ ja _________.
2. Algoritmin aikavaativuus on (n3+n2log2n+14n)/n2, ja sen suuruusluokka ilmaistaan muodossa ________.
3. Oletetaan, että puun yleistetty taulukko esitetään muodossa A(C,D(E,F,G),H(I,J)), niin puun solmujen määrä on __________, puun syvyys on ___________ ja puun aste on _________.
4. Suffiksikaavan 9 2 3 +- 10 2 / - arvo on __________. Keskimmäistä kaavaa (3+4X)-2Y/3 vastaava suffiksilauseke on _______________________________.
5. Jos binääripuu tallennetaan linkitetyn listan kanssa, jokaisella solmulla on kaksi osoitinta vasemmalle lapselle ja oikealle lapselle datakentän lisäksi. Tässä tallennusrakenteessa binääripuussa, jossa on n solmua, on yhteensä ________ osoitinkenttää, joista ________ osoitinkenttä tallentaa osoitteet ja ________________ osoitin on tyhjiä osoittimia.
6. Suunnatulle ja suuntaamattomalle graafille, jossa on n kärkeä ja E-palkin reunaa, vastaavassa vierekkäisyystaulukossa on _______ ja ________ särmäsolmua.
7. AOV-verkko on ___________________ graafi.
8. Suuntaamattomassa täydellisessä graafissa, jossa on n solmua, on ________ särmiä, ja suunnatussa täydellisessä graafissa, jossa on n solmua, on ________ särmaa.
9. Oletetaan, että lineaarinen taulukko on (12,23,74,55,63,40), jos saman jäännöksen alkiot muuttuvat alitaulukoksi Key % 4 -ehdon mukaisesti, saadaan neljä alitaulukkoa ovat ____________________________, ___________________, _______________________ ja __________________________.
10. Kun elementtejä lisätään B_-puuhun, jos puun juurisolmu lopulta jaetaan, uuden puun korkeus on ___________ alkuperäistä puuta.
11. Kasojen lajitteluprosessissa minkä tahansa haarasolmun seulonnan aikavaativuus on ________ ja koko kekolajitteluprosessin aikakompleksisuus on ________.
12. Nopeassa lajittelussa, hepalajittelussa ja yhdistämisessä _________ lajittelu on vakaa.
Tietorakennepaperi (2)
1. Monivalintakysymykset (24 pistettä)
1. Seuraava lineaaristen taulukoiden kuvaus on virheellinen ().
(A) Lineaariset taulukot tallennetaan peräkkäin ja niiden on sijaitettava yhtenäisellä tallennustilalla
(B) Lineaariset taulukot ovat ketjutettuja eivätkä vie yhtenäistä tallennustilaa
(C) Lineaariset taulukot toteutetaan ketjutetulla tallennuksella, jotta lisäys- ja poistotoiminnot helpottuvat
(d) Lineaariset taulukot toteutetaan peräkkäisellä tallennuksella, jotta lisäys- ja poistotoiminnot helpottuvat
2. Oletetaan, että Huffman-puun lehtisolmujen kokonaismäärä on m, ja jos binäärinen linkitettyä listaa käytetään tallennusrakenteena, Huffmanin puussa on yhteensä ( ) tyhjiä osoitinkenttiä.
(A) 2m-1 (B)2m (C)2m+1 (D)4m
3. Jos peräkkäisen silmukkajonon Q[0:M-1] pää- ja hännänosoittimet ovat F ja R, päätöksi osoitin F osoittaa aina pääelementin edelliseen sijaintiin ja häntäosoitin R aina häntäelementin nykyiseen sijaintiin, niin silmukkajonon alkioiden määrä on ( ).
(A) R-F (B) F-R (C) (R-F+M)%M (D) (F-R+M)%M
4. Jos binääripuun keskikertainen läpikäyntijono on ABCD ja edellinen sekvenssin läpikäyntijono on CABD, niin binääripuun kulkeminen seuraavassa järjestyksessä saadaan ().
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5. Oletetaan, että täysin suuntaamattomassa graafissa on n solmua, jolloin täysin suuntaamattomassa graafissa on ( ) särmiä.
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-1
6. Oletetaan, että binääripuussa on 2000 solmua, niin binääripuun minimikorkeus on ( ).
(A) 9 (B) 10 (C) 11 (D) 12
7. Oletetaan, että suunnatussa graafissa on n solmua, niin ( ) on ( ) otsikkosolmuja vierekkäisyystaulukossa, jotka vastaavat suunnattua graafia.
(A) n-1 (B) n (C) n+1 (D) 2n-1
8. Aseta joukko alkuperäisiä tietueavainsanajonoja (5, 2, 6, 3, 8), ja nopean lajittelun tulos ensimmäisen tietueavainsanan 5 perusteella on ( ).
(A) 2,3,5,8,6 (B) 3,2,5,8,6
(C) 3,2,5,6,8 (D) 2,3,6,5,8
2. Täytä aukot (24 pistettä)
1. Jotta HASH-hakuteknologiaa voidaan soveltaa tehokkaasti, kaksi ongelmaa on ratkaistava: ____________________ ja __________________________.
2. Seuraavan ohjelmasegmentin funktio realisoi datan x pinoon ja vaatii oikean lauseen täyttämistä alleviivaan.
typedefstruct {int s[100]; Int top; } sqstack;
void push(sqstack&stack,int x)
{
if (stack.top==m-1) printf("ylivuoto");
else {____________________; _________________; }
}
3. Sekvenssi, joka saadaan käymällä binäärilajittelupuuta keskimmäisessä järjestyksessä, on ___________ jono (täytetty järjestettynä tai järjestämättömänä).
4. Nopean lajittelun pahin aikakompleksisuus on ___________, ja keskimääräinen aikakompleksisuus on __________.
5. Jos binääripuussa solmujen lukumäärä, joiden aste on 0, on N0 ja solmujen luku, jonka aste on 1, on N1, niin binääripuussa solmujen lukumäärä, joiden aste on 2, on _________; Jos binäärilinkitettyä listaa käytetään binääripuun tallennusrakenteena, binääripuussa _______ tyhjää osoitinkenttää.
6. Oletetaan, että tietyn suuntaamattoman graafin solmujen ja kaarien määrä on n ja e, ja kaikkien solmujen asteiden summa on d, jolloin e = _______.
7. Jos alkuperäinen tietueavainsanajonno on (55, 63, 44, 38, 75, 80, 31, 56), niin seulontamenetelmän asettama alkuperäinen hep on ___________________________.
8. On tiedossa, että suunnatun graafin vierekkäistaulukon tallennusrakenne on seuraava: Solmusta 1 lähtien DFS:n läpikäynnin lähtöjono on:
, BFS:n läpikäynnin lähtöjono on
Tietorakennepaperi (3)
1. Monivalintakysymykset (1 piste per kysymys, yhteensä 20 pistettä)
1. Jos tietorakenteen binäärimuoto ilmaistaan muodossa A=(D,R),D={01,02,03,04,05,06,07,08,09}, R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}, niin tietorakenne A on ( ).
(A) Lineaarinen rakenne (B) Puurakenne (C) Fysikaalinen rakenne (D) Graafinen rakenne
2. Seuraavan ohjelman aikakompleksi on ()
for(i=1,s=0; i<=n; i++) {t=1;for(j=1;j<=i; j++) t=t*j; s=s+t; }
(A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3. Aseta osoitinmuuttuja p osoittamaan solmuun A yhdessä linkitetyssä listassa, jos poistat solmun A yhdestä linkitetystä listasta, sinun täytyy muuttaa osoittimen toimintajärjestys muotoon ().
(A) q=p->seuraava; p->data=q->data; p->next=q->next; vapaa(q);
(B) q=p->seuraava; q->data=p->data; p->next=q->next; vapaa(q);
(C) q=p->seuraava; p->next=q->next; vapaa(q);
(D) q=p->seuraava; p->data=q->data; vapaa(q);
4. Jos tietueen avainsanaa on n lajiteltavana, ( ) aputietueyksiköt vaaditaan kekolajittelussa.
(A) 1 (B) n (C) nlog2n (D) n2
5. Jos alkuperäiset avainsanamerkinnän avainsanat ovat (20, 15, 14, 18, 21, 36, 40, 10), niin nopean lajittelun jälkeen, jossa vertailuarvo on 20, on ( ).
(A) 10,15,14,18,20,36,40,21
(B) 10,15,14,18,20,40,36,21
(C) 10,15,14,20,18,40,36,2l
(D) 15,10,14,18,20,36,40,21
6. Oletetaan, että binäärilajittelupuussa on n solmua, niin binäärisen lajittelupuun keskimääräinen hakupituus on ( ).
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7. Oletetaan, että suuntaamattomassa graafissa G on n kärkipistettä, ja vastaavassa vierekkäisyystaulukossa otsikkosolmujen ja taulukon solmujen määrä on ( ).
(A) n,e (B) e,n (C) 2n,e (D) n,2e
8. Oletetaan, että vahvassa yhteysgraafissa on n solmua, niin vahvan yhteyden graafissa on vähintään ( ) särmiä.
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)
9. Lajiteltavaa avainsanaa on 5000, ja jos tarvitset nopeinta menetelmää valitaksesi pienimmät 10 tietueen avainsanaa, voit käyttää seuraavaa ( ) menetelmää tämän tavoitteen saavuttamiseksi.
(A) Nopea lajittelu (B) Kasojen lajittelu (C) Yhdistä lajittelu (D) Lisää lajittelu
10. Seuraavat neljä tyyppiä ( ) ovat suurimman spatiaalisen monimutkaisuuden.
(A) Lisäyslajittelu (B) Kupliva lajittelu (C) Kesalajittelu (D) Yhdistämislajittelu
2. Täytä aukot (1 piste per tyhjä, yhteensä 20 pistettä)
1. Datan fysikaalinen rakenne kattaa pääasiassa kaksi tilannetta: _____________ ja ______________.
2. Jos täydellisessä binääripuussa on 500 solmua, binääripuun syvyys on __________; Jos käytät binääristä linkitettyä listaa täysin binääripuun tallennusrakenteena, on ___________ tyhjää osoitinkenttää.
3. Jos tulojono on 1, 2, 3, niin pinon toiminnan jälkeen voidaan saada ___________ eri lähtöjonoa.
4. Jos vierekkäisyysmatriisia A[n][n] käytetään graafin G tallennusrakenteena, niin kaikkien rivin i alkioiden summa vierekkäisyysmatriisissa on yhtä suuri kuin solmun i ________, ja kaikkien sarakkeen i alkioiden summa on yhtä suuri kuin solmun i ________.
5. Jos Huffman-puussa on n solmua, on ________ solmua, joiden aste on 1.
6. Jos suuntakaaviossa G on n kärkeä e, joilla on suuntakaaret, ja kaikkien asteisiin menevien solmujen summa on d, niin e:n ja d:n välinen suhde on _________.
7. __________ binäärilajittelupuun solmujen läpikäyminen voi saada inkrementaalisen avainsanajonon (täytetty, keskimmäinen tai takainen).
8. Jos hakutaulukossa on 100 alkiota, jos käytät dikotomista hakumenetelmää dataalkion X löytämiseen, sinun täytyy verrata sitä jopa ________ kertaa selvittääksesi, onko tietoalkio X hakutaulukossa.
9. Olipa kyseessä pino, jossa on peräkkäinen tallennusrakenne, tai ketjutallennusrakenteella, pinon sisäisten ja ulkoisten toimintojen aikavaativuus on ____________.
10. Täydellinen binääripuu, jossa on n solmua, jos se on numeroitu ylhäältä alas ja vasemmalta oikealle alkaen yhdestä, i:nnen solmun emosolmu on numeroitu ____________ ja oikean lapsisolmun numero on ___________.
11. Jos tallennettujen avainsanojen alkuperäinen joukko on (72, 73, 71, 23, 94, 16, 5), niin pikalajittelun tulos tietueavainsanan 72 perusteella on ___________________________.
12. Jos suuntakaaviossa G E={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>} on joukko suunnattuja kaaria, niin graafin topologinen jono on ____________________.
13. Seuraava algoritmi toteuttaa avainsanan, jonka arvo on x peräkkäisessä hajautuslistassa, täytä oikea lause alaviivaan.
struct record{int key; int muut; };
inthashsqsearch(struct-tietueen hashtable[ ],int k)
{
inti,j; j=i=k % p;
while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; jos (i==j) return(-1); }
jos (_______________________ ) return(j); else return(-1);
}
14. Seuraava algoritmi toteuttaa avainarvon k binäärilajittelupuussa, täytä oikea lause alaviivaan.
typedefstruct node{int key; struct-solmu *lchild; struct-solmu *rchild; }bitree;
bitree *bstsearch(bitree *t, älykkyys k)
{
jos (t==0) return(0); muuten kun (t!=0)
jos (t->avain==k)_____________; muuten jos (t->avain>k) t=t->lchild; else_____________;
}
Tietorakenteen testipaperi (1) Katso vastaus
1. Monivalintakysymykset (2 pistettä per kysymys, yhteensä 20 pistettä)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
2. Täytä aukot (1 piste per tyhjä, yhteensä 26 pistettä)
1. Oikeellisuus, luettavuus, vahvuus ja korkea tehokkuus
2.O(n)
3.9 3 3
4.-1 3 4 X * + 2 Y * 3 / -
5.2n n-1 n+1
6.e 2e
7. Suunta- ja ei-piirijärjestelmä
8.n(n-1)/2 n(n-1)
9.（12，40） （ ） （74） （23,55，63）
10. Lisää 1
11.O(log2n) O(nlog2n)
12. Yhdistäminen
Vastaukset muihin testikysymyksiin löytyy:
Turistit, jos haluatte nähdä tämän postauksen piilotetun sisällön, olkaa hyvä Vastaus
|
Julkaistu 25.11.2014 12.46.30
|
|
|
Julkaistu 30.12.2014 0.10.55