Guvernul Karnataka, Departamentul de Educaț ie Tehnică

Diplomă în Informatică ș i Inginerie

Semestrul Trei
Subject: DATA STRUCTURES USING C
Contact Hrs / week: 4 Total hrs: 64

Table of Contents

Capitol Nr Subiect No. of Hrs Note

Secț iunea I
1 Indicii 08 18
2 Alocare dinamică a memoriei 04 6
3 Fiș iere 06 14
Secț iunea II
4 Introducere în structuri de date 02 4
5 Stiva 08 22
6 Cozi 06 14
Secț iunea III
7 Liste legate 08 20
8 Păduri 06 16
9 Sortare 06 15
10 Căutare 02 6
Seminarii ș i prelegeri invitati de la
05
Industrie ș i Institut
Teste 03
Total hrs 64 145

Conț inut Detaliat

1Puncte
1.1 Conceptul de pointeri
1.2 Declararea ș i ini ț ializarea pointerilor
1.3 Accesarea variabilelor folosind pointeri
1.4 Arithmetica pointerilor
1.5 Indicii ș i tablouri
1.6 Indicii ș i ș iruri de caractere
1.7 Puncte ș i func ț ii
1.8 Punctator ca argument de func ț ie
1.9 Poin ț i către func ț ie
1.10 indicatoare ș i structuri
Alocarea dinamică a memoriei
2.1 Introducere
2.2 Allocarea dinamică a memoriei
2.3 Alocarea unui bloc de memorie: Malloc
 2.4 Alocarea mai multor blocuri de memorie: Calloc
2.5 Eliberarea spa ț iului utilizat : Gratuit
2.6 Modificarea dimensiunii memoriei: Realloc
3Fi ș iere
3.1 Introducere
3.2 Definirea ș i deschiderea unui fi ș ier
3.3 Închiderea unui fi ș ier
3.4 Opera ț iuni de intrare / ie ș ire pe fi ș iere
3.5 Gestionarea erorilor în timpul opera ț iunilor I/O
3.6 Acces aleator la fi ș iere
3.7 Argumente de linie de comandă
Introducere în structurile de date
4.1 Introducere
4.2 Date ș i informa ț ii
4.3 Tipuri de structuri de date
4.4 Structuri de date primitive ș i non-primitive ND opera ț iuni
Stiva
5.1 Defini ț ie ș i exemple
5.2 Opera ț iuni primitive - Push ș i Pop
5.3 Reprezentarea stivelor în C
5.4 Implementarea opera ț iunilor Push ș i Pop în C
5.5 Aplica ț iile Stivelor
5.6 Expresii infix, postfix ș i prefix
5.7 Algoritm pentru evaluarea unei expresii - Infix la prefix, Infix la Postfix
5.8 Recursie
5.9 Defini ț ie recursivă
5.10 Înmul ț irea numerelor naturale
5.11 Func ț ia factorială
Func ț ia GCD 5.12
5.13 Proprietă ț ile algoritmilor/func ț iilor recursive
5.14 Recursie în C
6Cozi
6.1 Coada ș i reprezentarea sa secven ț ială
Implementarea Cozilor în C 6.2 ș i opera ț iile acestora
Implementarea coadelor circulare în C 6.3 ș i opera ț iunile acestora
6.4 Cozi de de ș euri ș i cozi de prioritate (doar concepte)
Liste înlăn ț uite
7.1 Liste liniare legate
7.2 Inserting and removing nodes from a list
7.3 Implementarea legată a stivei ș i coadelor
7.4 Implementarea listelor folosind arii în C ș i limitările acesteia
7.5 Lista legată utilizând variabile dinamice în C
7.6 Compararea implementării dinamice ș i a celei pe tablou a listelor
7.7 Liste legate circulare (Concepte doar, fără implementări)
7.8 Listă dublu legată
8Arbori
8.1 Introducere
8.2 Termeni de bază
 8.3 Arbori binari
8.4 Arbore binar complet
8.5 Reprezentarea arborelui binar
8.6 Opera ț ie pe arbore binar
8.7 Traversarea unui arbore binar
9Sortare
9.1 Sorte de schimb
9.2 --Sortare prin bule
9.3 --Sortare rapidă (Fără implementare)
9.4 Selecia ș i sortarea arborelui
9.5 --Sortare prin selec ț ie directă
9.6 --Sortarea arborelui binar
9.7 Sortări prin inser ț ie
9.8 --Sortare simplă prin inserare
9.10 --Sortare shell (Fără implementare)
9.11 Sortare prin fuziune ș i sortare prin sistemul de baze (Fără implementare)

10Căutare
10.1 Introducere
10.2 Căutare
10.3 Căutare liniară (secven ț ială) (fără a crea listă înlăn ț uită)
10.4 Căutare binară

Obiective generale:

1 În ț elegeț i conceptul de pointeri ș i opera ț iile lor

2 În ț elege conceptul de alocare dinamică a memoriei
3 În ț elege gestionarea fi ș ierelor în C
Cunoaș te conceptele structurilor de date liniare, operaț iile acestora ș i
4 aplica ț ii
Cunoaș te conceptele structurilor de date non liniare, operaț iile acestora ș i
5 aplica ț ii
6 În ț elegeț i diferitele tehnici de sortare ș i căutare

Specific Objectives:

Puncte
Scoate în evidenț ă conceptele de pointeri
Învăț aț i să declaraț i ș i să iniț ializaț i pointeri
Învăț aț i să accesaț i variabile folosind pointeri
Explicaț i conceptele de aritmetică a pointerilor
{"use_of_pointers":{"arrays":"Punctele pot fi utilizate pentru a accesa elementele unui array prin referinț ă, permitând iterarea ș i manipularea eficientă a datelor.","character_strings":"În cazul ș irurilor de caractere, pointerii sunt utilizaț i pentru a gestiona datele de tip text ș i pentru a manipula conț inutul acestora fără a copia întreaga secvenț ă.","functions":"Pointerii permit transmiterea de argumente la funcț ii prin referinț ă, economisind memorie ș i timpul de copiere a datelor.","structures":"Folosit în structuri, pointerii facilitează accesul ș i manipularea dinamică a datelor complexe, creând legături între diferitele entităț i ale structurii."}}

Fiș iere
Definiț i Fiș ier
Învăț aț i operaț iile I/O pe fiș iere
{"sequential_access_files":"fiș iere cu acces secvenț ial","random_access_files":"fiș iere cu acces aleator"}
Învă ț aț i să gestiona ț i erorile în fi ș iere ș i argumentele din linia de comandă
Introducere în structuri de date
Define Information ,data and data structures
Distinge între diferitele tipuri de tipuri de date: primitive ș i non-primitive
Defineș te stiva cu exemple
Explicaț i operaț iile primitive - Push ș i Pop efectuate pe stivă.
Scrie programe pentru a implementa operaț iile de Push ș i Pop în C
Învăț aț i aplicaț iile stivelor
Învaț ă despre expresiile infix, postfix ș i prefix
Învăț aț i să convertiț i expresii, adică din infix în postfix ș i prefix,
Învăț aț i să convertiț i expresiile Postfix în infix ș i prefix, Prefix în infix ș i Postfix.
Înț elege recursivitatea: de exemplu. Înmulț irea numerelor naturale, Factorialul ș i MCD
Învaț ă despre cozi cu exemple ș i reprezentarea lor secvenț ială
Învaț ă implementarea coadelor în C ș i operaț iile acestora
Învăț aț i implementarea C a coada circulară ș i operaț iile acesteia
Învaț ă conceptele de Dequeue ș i cozi de prioritate
Lista legată
Învăț aț i conceptele listelor liniare legate, avantajele ș i dezavantajele acestora
Scrie programe pentru inserarea ș i eliminarea nodurilor dintr-o listă
Scrie programe pentru a implementa stive ș i cozi
Învăț aț i implementarea array-urilor de liste în C ș i limitările acestora
Implementaț i o listă înlănț uită folosind variabile dinamice în C
Exemple de operaț iuni pe liste în C
Compararea implementării dinamice ș i a celor pe bază de aranjamente a listelor
Învaț ă conceptele listelor circulare ș i ale celor dublu legate
Păduri
Definiț i arborii binari ș i învăț aț i conceptele lor
Înț elege operaț iile pe arbori
Învăț are ș i implementare a operaț iunilor de traversare a arborilor binari

Sortare
Pentru a înț elege diferitele tehnici de sortare cu exemple
Pentru a implementa tehnici de sortare în C
Căutare
Pentru a înț elege tehnicile de căutare liniară ș i binară cu exemple
Pentru a învăț a ș i a implementa tehnici de căutare liniară ș i binară în C

Carte de text:

1. Pentru Capitolul 1 până la 3 --Programare în ANSI C, [Link], 4E, Tata

McGraw Hill, ISBN: 9780070648227
2. Pentru Capitolele 5, 6, 7, 9, 10 - STRUCTURI DE DATE UTILIZÂND C Ș I C++

Langsam yedidyah, Augenstein moshe j., Aron M. Tenenbaum, Al doilea

Editie, PHI
3. Pentru Capitolele 4 ș i 8 --Introducere în Structuri de Date în C, Ashok N
Kamthane, A treia impresie 2009, Pearson Education, ISBN :
9788131713921
Cărț i de referinț ă:
1. C ș i structuri de date, Dr. N.B. Venkateshwarulu ș i Dr. E.V. Prasad,
Publicaț iile S Chand
2. Structurile de date Folosind C, Aron M. Tenenbaum,lento yedidyah,
Augenstein Moshe J., PHI
3. C ș i Structuri de Date, Prof. P S Deshapande ș i Prof. O G Kakde
 Guvernul Karnataka, Departamentul de Educaț ie Tehnică
Diplomă în Informatică și Inginerie
Semestrul Trecut
Subiect: Structuri de date utilizând C

Max. Marks: 100 Timp maxim: 3 Ore

Model de Întrebare

Notă: 1. Sec ț iunea I este obligatorie.

2. Răspundeț i la ORICE DOUĂ întrebări din fiecare dintre secț iunile rămase.

Note

Secț iunea – I
1. a) Completa ț i spa ț iile goale cu cuvinte/scorespunzătoare 5x1=5
i. …… este o variabilă care reț ine adresa unei alte variabile.
ii. ……. este un exemplu pentru o structură de date non liniară

iii. Procesul prin care o funcț ie se apelează singură se numeș te…………

iv. ……. este folosit pentru a deschide un fiș ier.

v. Numărul total de noduri într-un arbore binar complet este dat de …..
b) Scrieț i o notă despre argumentele din linia de comandă. 5

Secț iunea – II

2. a) Define ț i pointerul. Explica ț i aritmetica pointerilor. 6

b) Diferen ț iaț i între apel prin valoare ș i apel prin referin ț ă a parametrului
tehnici de passing cu exemplu. 9

3. a) Scrie un program pentru a sorta N numere folosind malloc( ). 6

b) Define ț i Fi ș ierul ș i explica ț i diferitele moduri de Fi ș ier. 6
c) Cum să gestionăm erorile în fi ș iere? 3
4. a) Distinge ț i între structurile de date liniare ș i cele neliniare. 5
b) Scrie un algoritm pentru a efectua operaț iile PUSH ș i POP în Stivă. 10
Secț iunea – III
5. a) Ce este recursivitatea? Explica ț i cu un exemplu. 7
b) Transformati urmatoarele expresii in postfix 6
(A + B) * (C - D) $ E * F
ii. ((A – (B + C) * D) $ (E + F)
c) Defineț i coada. 2
6. a) Scrie un program pentru a implementa Cozi Circulare în C 10
b) Scrieț i o notă despre cozile de prioritate. 5
7. a) Scrie un algoritm pentru a insera un nod într-o listă legată. 8
b) Compară Implementarea Dinamică ș i Implementarea pe Baze de Aranjamente a Listelor. 7

Secț iunea – IV

8. a) Explica lista dublu înlă ț uită. 5

b) Scrieț i algoritmii de parcurgere a copacului. 10
9. a) Construie ș te arborele binar pentru următoarele date 5
15,4,8,9,2,13,1,6,10,11,14
b) Scrieț i un program pentru a implementa un sortare prin inserț ie simplă ș i pentru a urmări

cu un exemplu. 10
10. a) Explicaț i sortarea prin arbore cu un exemplu. 8
b) Scrie un program pentru a efectua căutare binară folosind recursivitatea. 7