Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α21.10 · Ν-οστό Στοιχείο Λίστας

Εξέταση Σεπτεμβρίου 2026, Θέμα 4 · Δυσκολία ★★☆ · programming · Κεφάλαια: 21, 13, 15

Ν-οστό Στοιχείο Λίστας [25 Μονάδες]

Γράψτε μια συνάρτηση nth η οποία παίρνει ως όρισμα μια λίστα από πίνακες χαρακτήρων τύπου List μαζί με έναν αριθμό n και επιστρέφει μια νέα λίστα με μοναδικό στοιχείο το n-οστό στοιχείο της λίστας. Αν δεν υπάρχει n-οστό στοιχείο, το πρόγραμμα θέλουμε να τερματίζει με κωδικό εξόδου 1. Για παράδειγμα, αν δοθεί η ακόλουθη λίστα:

"foo" -> "bar" -> "zonk" -> "baz" -> "hello" -> NULL

και n=3 περιμένουμε να επιστραφεί η ακόλουθη νέα λίστα (0-indexing όπως στην C):

"baz" -> NULL

Ποια είναι η χρονική και η χωρική πολυπλοκότητα του αλγορίθμου σας (8/25 της βαθμολογίας); Ο τύπος List δίνεται παρακάτω:

typedef struct node {
  char value[32];
  struct node * next;
} * List;

Υπόδειξη

Προχωρήστε n βήματα από την κεφαλή ακολουθώντας τα next, ελέγχοντας σε κάθε βήμα μήπως τελείωσε η λίστα (και τι γίνεται αν η λίστα είναι κενή ή το n αρνητικό). Η νέα λίστα είναι ένας καινούργιος κόμβος από malloc: αντιγράψτε το value (δεν ανατίθεται ως πίνακας) και βάλτε next = NULL, αντί να επιστρέψετε δείκτη μέσα στην παλιά λίστα. Για την πολυπλοκότητα, μετρήστε πόσους κόμβους επισκέπτεστε και πόση επιπλέον μνήμη δεσμεύετε.

Αριθμός στον οδηγό: Α21.10 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: exam-2026-sep-q4 · Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2026-sep-q4.html · Markdown (GitHub)