Prova 2

Prévia do material em texto

UNIVERSIDADE FEDERAL
DOTOCANTINS
Curso de Cieˆncia da Computac¸a˜o
Disciplina: Algoritmos e Estrutura de Dados I
Prof.: Rafael Lima
Avaliac¸a˜o 2
Junho de 2017
Nome: Matr´ıcula:
1) (2,0) (QPNZ) Considere o seguinte trecho de
co´digo:
1 #include<s t d i o . h>
2 #include<s t d l i b . h>
3 typedef struct no{void∗ i n f o ;
struct no∗ prox , ∗ant ;} no ;
4
5 typedef struct {no ∗ i n i c i o , ∗ f im ;
unsigned int qtde ;} Li s ta ;
6 typedef Li s ta Pi lha ;
7 typedef Li s ta F i l a ;
8 L i s t a ∗ c r e a t e ( ) {
9 L i s t a ∗ nova = ( L i s ta ∗) mal loc ( s izeof (
L i s t a ) ) ;
10 i f ( nova ) {
11 nova−>qtde = 0 ;
12 nova−> i n i c i o = NULL;
13 nova−>f im = NULL;
14 } return nova ;}
15 //As funcoes a s e gu i r retornam 0 em
caso da operacao nao puder ser
f e i t a e 1 em caso de sucesso
16 int Pi lha empi lha ( Pi lha ∗ P, int dado
) ;
17 int Pi lha desempi lha ( Pi lha ∗ P, int ∗
dado ) ;
18 int F i l a e n f i l e i r a ( F i l a ∗ F, int dado
) ;
19 int F i l a d e s e n f i l e i r a ( F i l a ∗ F, int ∗
dado ) ;
20 int L i s t a i n s e r e n o i n i c i o ( L i s t a ∗ L ,
int dado ) ; // Insere o dado
antes do i n i c i o
21 int L i s t a i n s e r e n o f im ( L i s t a ∗ L ,
int dado ) ; // Insere o dado no
f i n a l da l i s t a
22 int L i s t a i n s e r e o rd em dec r e s c en t e (
L i s t a ∗ L , int dado ) ; // Insere em
ordem decre scen t e
23 int Lista remove menor ( L i s t a ∗ L , int
∗dado ) ; //Remove o menor
elemento da l i s t a
24 int Lista remove maior ( L i s t a ∗ L , int
∗dado ) ; //Remove o maior
elemento da l i s t a
25 int Lis ta remove u l t imo ( L i s t a ∗ L ,
int ∗dado ) ; //Remove o u l t imo
elemento da l i s t a
26 int L i s t a r emove i n i c i o ( L i s t a ∗ L ,
int ∗dado ) ; //Remove o pr imeiro
elemento da l i s t a
27 int main ( ) {
28 int v [ ] = {1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ,
9 , 27 , 29} ;
29 L i s t a ∗ L = cr ea t e ( ) ;
30 int i ;
31 for ( i =0; i <11; i++){
32 TRECHO A;
33 }
34 while (TRECHO B)
35 p r i n t f ( ”%d , ” , i ) ;
36 return (0 ) ;
37 }
Considere ainda que os co´digos das func¸o˜es es-
tejam implementados. Para que a sa´ıda produ-
zida seja 1, 2 ,3 ,4, 5, 6, 7, 8, 9, 27,
29 os co´digos a serem substitu´ıdos em TRE-
CHO_A e TRECHO_B devem ser respectivamente:
Mais de uma alternativa pode ser marcada.
(a) Pilha_empilha(L, i) e Pilha_desem-
pilha(L, &i)
(b) Fila_enfileira(L, i) e Fila_desen-
fileira(L, &i)
(c) Lista_insere_no_inicio(L, i) e
Lista_remove_fim(L, &i)
(d) Lista_insere_no_fim(L, i) e Lista_-
remove_menor(L, &i)
(e) Lista_insere_no_fim(L, i) e Lista_-
remove_ultimo(L, &i)
(f) Lista_insere_no_inicio(L, i) e
Lista_remove_maior(L, &i)
(g) Lista_insere_ordem_decrescente(L,
i) e Lista_remove_fim(L, &i)
2) (2,0) Considere o seguinte trecho de co´digo:
Pa´gina 1 de 5
UNIVERSIDADE FEDERAL
DOTOCANTINS
Curso de Cieˆncia da Computac¸a˜o
Disciplina: Algoritmos e Estrutura de Dados I
Prof.: Rafael Lima
1 #include <s t d l i b . h>
2 #include <s t d i o . h>
3 typedef struct no{
4 void∗ i n f o ;
5 struct no ∗prox , ∗ant ;
6 } TNo;
7
8 typedef struct{
9 TNo ∗ i n i c i o ;
10 }GDList ;
11
12 void GDList pr int (GDList∗ L , void (∗
pr in t ) (void ∗) ) {
13 TNo∗ aux = L−> i n i c i o ;
14 while ( aux ) {
15 pr in t ( aux−>i n f o ) ;
16 aux = aux−>prox ;
17 }
18 putchar ( ’ \n ’ ) ;
19 }
20
21 int GDList insere o (GDList∗ L , void∗
i n fo , unsigned int s i z e , int (∗
cmp) (void ∗ , void ∗) ) {
22 TNo∗ novo = (TNo∗) mal loc ( s izeof (
TNo) ) ;
23 TNo∗ aux ;
24 i f ( ! novo )
25 return (0 ) ;
26 novo−>i n f o = mal loc ( s i z e ) ;
27 i f ( ! ( novo−>i n f o ) )
28 return (0 ) ;
29 memcpy( novo−>i n fo , in fo , s i z e ) ;
30 novo−>prox = NULL; novo−>ant =
NULL;
31 i f (L−> i n i c i o==NULL)
32 L−> i n i c i o = novo ;
33 else {
34 aux = L−> i n i c i o ;
35 while ( aux−>prox && cmp(aux−>i n fo
, i n f o ) < 0)
36 aux = aux−>prox ;
37 i f ( aux−>prox==NULL) {
38 aux−>prox = novo ;
39 novo−>ant = aux ;
40 } else {
41 novo−>prox = aux ;
42 novo−>ant = aux−>ant ;
43
44 i f ( aux−>ant )
45 aux−>ant−>prox = novo ;
46 aux−>ant = novo ;
47 i f ( aux == L−> i n i c i o )
48 L−> i n i c i o = novo ;
49 }
50 }
51 return (1 ) ;
52 }
53
54 void p r i n t i n t (void∗ t ) {
55 int ∗p ;
56 p = ( int ∗) t ;
57 p r i n t f ( ”%d ” , ∗p) ;
58 }
59
60 int comp int (void∗ s1 , void∗ s2 ) {
61 int ∗p1 = ( int ∗) s1 ,
62 ∗p2 = ( int ∗) s2 ;
63 return (∗p1 < ∗p2 ) ? −1: (∗p1 == ∗
p2 ) ? 0 : 1 ;
64 }
65
66 int main ( ) {
67 int v [ ] = {3 , 1 , 5 , 7 , 2} ;
68 int s izeV = 5 , i ;
69 void (∗ f p r i n t ) (void ∗) = p r i n t i n t ;
70 GDList ∗L1 = GDList create ( ) ;
71 for ( i =0; i < s izeV ; i++)
72 GDLis t insere o (L1 , &v [ i ] , s izeof
( v [ i ] ) , comp int ) ;
73 GDList pr int (L1 , f p r i n t ) ; //LINHA A
74 return (0 ) ;
75 }
O que sera´ impresso no trecho de co´digo co-
mentado por LINHA A:
(a) 3 1 5 7 2
(b) 1 5 2
(c) 1 5 7 3
(d) 1 2 3 5 7
(e) 7 5 3 2 1
3) (2,0) Considere os co´digos descritos nas figuras
1, 2 e 3:
Pa´gina 2 de 5
UNIVERSIDADE FEDERAL
DOTOCANTINS
Curso de Cieˆncia da Computac¸a˜o
Disciplina: Algoritmos e Estrutura de Dados I
Prof.: Rafael Lima
Figura 1: Pseudo-co´digo da func¸a˜o max-heapify
estudada em sala de aula.
Figura 2: Pseudo-co´digo da func¸a˜o max-heapify
estudada em sala de aula.
Figura 3: Pseudo-co´digo da func¸a˜o max-heapify
estudada em sala de aula.
Quantas chamadas ao procedimento MAX-
HEAPIFY seriam feitas, caso a entrada A seja
igual ao vetor 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 e
o procedimento HEAPSORT(A) fosse invo-
cado?
4) (2,0) Problema do Josephus (Ze´) com skip. O
grupo de soldados de Josephus, composto por
um total de N soldados, esta´ encurralado pelo
exe´rcito inimigo (que possui drones do mal e
tudo mais). Existe apenas um cavalo de fuga!
Para decidir quem ira´ escapar, Josephus pro-
po˜e uma soluc¸a˜o que e´ fazer uma lista circu-
lar duplamente encadeada com skips, que sa˜o
colocados a cada k soldados. Iniciando no sol-
dado 1 (que e´ o in´ıcio da lista), um nu´mero
aleato´rio a e´ sorteado. Anda-se a no´s, e caso
o no´ destino na˜o possua skip, elimina-se este
no´ da lista. Caso possua skip, o soldado apon-
tado pelo skip e´ eliminado e o campo skip do
soldado que escapou e´ atribu´ıdo valor NULL
(ou seja, deixa de ter skip). O pro´ximo no´ sera´
utilizado para comec¸ar a contagem novamente.
Sua missa˜o e´ implementar a func¸a˜o JosephS-
kip. A func¸a˜o devera´ imprimir qual a posic¸a˜o
que Josephus devera´ ocupar para que possa ser
o escolhido (u´ltimo da lista). Assuma que o pa-
raˆmetro da lista circular ja´ esteja preenchido e
com os skips preenchidos tambe´m. Na˜o se es-
quec¸a de garantir que apo´s a exclusa˜o de um
no´, os ponteiros fiquem corretamente aponta-
dos.
1 #include <s t d l i b . h>
2 #include <s t d i o . h>
3 typedef struct no{
4 void∗ i n f o ;
5 struct no ∗prox , ∗ant , ∗ sk ip ;
6 } TNo;
7
8 typedef struct{
9 TNo ∗ i n i c i o ;
10 }CList ;
11
12 void JosephSkip ( CList∗ L , int N, int
sk ip ) {
13 //Seu codigo aqui
14 }
5) (2,0) A estrutura de dados Set (conjunto) pode
ser implementada por meio de listas simples-
mente e duplamente encadeadas (ordenadas ou
na˜o). Um Set de nu´meros inteiros, por exem-
plo, na˜o permite a inserc¸a˜o de nu´meros repeti-
dos (simplesmente ignora). A seguir, segue um
trecho de co´digo contendo a estrutura de dados
Pa´gina 3 de 5
UNIVERSIDADE FEDERAL
DOTOCANTINS
Curso de Cieˆncia da Computac¸a˜o
Disciplina: Algoritmos e Estrutura de DadosI
Prof.: Rafael Lima
de um Set, bem como cinco func¸o˜es de inserc¸a˜o
nomeadas como insert1, insert2, insert3,
insert4 e insert5.
1 #include<s t d i o . h>
2 #include<s t d l i b . h>
3 typedef struct no{
4 int i n f o ;
5 struct no ∗prox ;
6 }TNo;
7
8 typedef struct{
9 TNo∗ i n i c i o ;
10 }Set ;
11 Set ∗ c r e a t e ( ) {
12 Set ∗ novo = ( Set ∗) mal loc ( s izeof (
Set ) ) ;
13 i f ( novo )
14 novo−> i n i c i o = NULL;
15 return novo ;
16 }
17 TNo∗ c r e a t e n f i l l ( int d) {
18 TNo∗ novo = (TNo∗) mal loc ( s izeof (
TNo) ) ;
19 i f ( novo ) {
20 novo−>i n f o = d ;
21 novo−>prox = NULL;
22 }
23 return novo ;
24 }
25
26 void i n s e r t 1 ( Set ∗ s , int data ) {
27 TNo∗ aux = s−> i n i c i o ;
28 char f l a g = 1 ;
29 i f ( aux==NULL)
30 s−> i n i c i o = c r e a t e n f i l l ( data ) ;
31 else {
32 while ( aux−>prox != NULL) {
33 i f ( aux−>i n f o==data ) {
34 f l a g = 0 ; break ;
35 }
36 aux = aux−>prox ;
37 }
38 i f ( f l a g )
39 aux−>prox = c r e a t e n f i l l ( data ) ;
40 }
41 }
42
43 void i n s e r t 2 ( Set ∗ s , int data ) {
44 TNo∗ aux = s−> i n i c i o ;
45 i f ( aux==NULL)
46 s−> i n i c i o = c r e a t e n f i l l ( data ) ;
47 else {
48 do{
49 i f ( aux−>i n f o==data )
50 return ;
51 aux = aux−>prox ;
52 }while ( aux ) ;
53 aux = c r e a t e n f i l l ( data ) ;
54 aux−>prox = s−> i n i c i o ;
55 s−> i n i c i o = aux ;
56 }
57 }
58
59 void i n s e r t 3 ( Set ∗ s , int data ) {
60 TNo∗ aux = s−>i n i c i o , ∗aux2 ;
61 i f ( aux==NULL)
62 s−> i n i c i o = c r e a t e n f i l l ( data ) ;
63 else {
64 i f ( data < aux−>i n f o ) {
65 aux = c r e a t e n f i l l ( data ) ;
66 aux−>prox = s−> i n i c i o ;
67 s−> i n i c i o = aux ;
68 } else {
69
70 do{
71 aux2 = aux ;
72 aux = aux−>prox ;
73 i f ( aux−>i n f o==data )
74 return ;
75 }while ( aux−>prox && aux−>i n f o < data
) ;
76 aux2−>prox = c r e a t e n f i l l ( data ) ;
77 aux2−>prox−>prox = aux ;
78 }
79 }
80 }
81
82 void i n s e r t 4 ( Set ∗ s , int data ) {
83 TNo∗ aux = s−>i n i c i o , ∗aux2 ;
84 i f ( aux==NULL)
85 s−> i n i c i o = c r e a t e n f i l l ( data ) ;
86 else {
87 i f ( data < aux−>i n f o ) {
88 aux = c r e a t e n f i l l ( data ) ;
89 aux−>prox = s−> i n i c i o ;
90 s−> i n i c i o = aux ;
91 } else {
92
93 do{
94 aux2 = aux ;
95 i f ( aux−>i n f o==data )
96 return ;
97 aux = aux−>prox ;
Pa´gina 4 de 5
UNIVERSIDADE FEDERAL
DOTOCANTINS
Curso de Cieˆncia da Computac¸a˜o
Disciplina: Algoritmos e Estrutura de Dados I
Prof.: Rafael Lima
98 }while ( aux−>prox && aux−>i n f o < data
) ;
99 aux2−>prox = c r e a t e n f i l l ( data ) ;
100 aux2−>prox−>prox = aux ;
101 }
102 }
103 }
104
105 void i n s e r t 5 ( Set ∗ s , int data ) {
106 TNo∗ aux = s−>i n i c i o , ∗aux2 ;
107 i f ( aux==NULL)
108 s−> i n i c i o = c r e a t e n f i l l ( data ) ;
109 else {
110 i f ( data < aux−>i n f o ) {
111 aux = c r e a t e n f i l l ( data ) ;
112 aux−>prox = s−> i n i c i o ;
113 s−> i n i c i o = aux ;
114 } else {
115 do{
116 aux2 = aux ;
117 i f ( aux−>i n f o==data )
118 return ;
119 aux = aux−>prox ;
120 }while ( aux && aux−>i n f o < data ) ;
121 aux2−>prox = c r e a t e n f i l l ( data ) ;
122 i f ( aux )
123 aux2−>prox−>prox = aux ;
124 }
125 }
126 }
Analise as func¸o˜es no co´digo acima e marque
a(s) func¸a˜o(o˜es) que esta´(a˜o) correta(s) (do
ponto de vista de na˜o fazer acesso ilegal a` me-
mo´ria) e que mante´m a propriedade do Set (ou
seja, na˜o permite a inserc¸a˜o de nu´meros repe-
tidos):
Mais de uma pode ser marcada.
(a) insert1
(b) insert2
(c) insert3
(d) insert4
(e) insert5
Pa´gina 5 de 5