estruturas de dados

Universidade Federal Fluminense
Engenharia de Telecomunica¸˜es - Turma TCC00160-A1 co Primeira prova de Estrutura de Dados
Professor Diego Pecin - 17/01/2013
Questao 1 (2.5)
a) 1.5 - Escreva uma fun¸˜o recursiva (algoritmo) que receba um vetor com n inteiros ca e retorne a soma da s´rie de valores do intervalo de 1 a n, com incremento k. O cabe¸alho e c de sua fun¸˜o deve ser SomaSerie(A, inf, sup, k), onde A ´ o nome do vetor, inf, sup e ca e k s˜o ´ a ındices no vetor (na chamada inicial, inf = 1 e sup = n). Qual a complexidade de seu algoritmo (em fun¸˜o de n e k )? Justifique. ca b) 1.0 Escreva a mesma fun¸˜o em uma vers˜o n˜o-recursiva (iterativa). Qual a comca a a plexidade? Questao 2 (2.5) Escreva um algoritmo para determinar se uma string de caracteres de entrada ´ da forma xCy, onde x ´ uma string consistindo das letras A e B e y ´ o ine e e verso de x, isto ´, se x = ABABBA, ent˜o y = ABBABA. O seu algoritmo deve utilizar e a uma pilha, chamada P, e usar as seguintes fun¸˜es (vocˆ n˜o precisa implementa-l´s!): co e a a insere(P, x), para inserir um elemento de valor x na Pilha P, remove(P), para remover o elemento que est´ no topo da pilha, e LˆTopo(P), para apenas ler o elemento que est´ no a e a topo da pilha. Considere que a string de entrada cont´m n caracteres e est´ armazenada e a no vetor chamado string.
Questao 3 (2.0) Dada a express˜o aritm´tica abaixo, totalmente parentizada, mostre a e a situa¸˜o das pilhas durante: ca a) 1.0 - A convers˜o para a nota¸˜o polonesa reversa (pilha de operadores). a ca
b) 1.0 - O c´lculo do resultado da express˜o (para a pilha de operadores e operandos). a a
((((10 ∗ 2) + 12) − 23) ∗ (4 + (5 − (16/8))))
Questao 4 (3.0) Considere duas listas de n´meros inteiros simplesmente encadeada, u com n´ cabea. Considere que os n´meros inteiros podem estar desordenados e que pode o u haver n´meros repetidos em listas individuais! Seja L1 o nome do n´ cabe¸a da primeira