Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    Algo1 2023 2024 TD6

    Uploaded by

    benallalamine2209
    The document contains a series of exercises involving linked lists. It includes exercises on checking properties of single and multiple lists, performing operations on lists like sorting, merging, and splitting them, as well as representing and manipulating integers and strings using linked lists.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Algo1 2023 2024 TD6

    Uploaded by

    benallalamine2209
    8 views6 pages
    The document contains a series of exercises involving linked lists. It includes exercises on checking properties of single and multiple lists, performing operations on lists like sorting, merging, and splitting them, as well as representing and manipulating integers and strings using linked lists.

    Original Title

    ALGO1-2023-2024-TD6

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains a series of exercises involving linked lists. It includes exercises on checking properties of single and multiple lists, performing operations on lists like sorting, merging, and splitting them, as well as representing and manipulating integers and strings using linked lists.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    8 views6 pages

    Algo1 2023 2024 TD6

    Uploaded by

    benallalamine2209
    The document contains a series of exercises involving linked lists. It includes exercises on checking properties of single and multiple lists, performing operations on lists like sorting, merging, and splitting them, as well as representing and manipulating integers and strings using linked lists.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 6

    Faculty of computer sciences, USTHB, 2023/2024

    Computer sciences domain,


    ALGO2 module

    Series of exercises No 3 : Linked lists

    Exercise 01 :
    Let L be a linked list of integers, write a parameterized action to solve each of the following problems :
    1. Checking if L is sorted in ascending order.
    2. Displaying list items starting with the last item.
    3. Removing the maximum value from a list.
    4. Inserting a given value val to a list sorted in ascending order.
    5. Creating the mirror list of L (without creating a new list);
    6. Removing identical elements;
    7. Splitting L into two lists : Lp containing the positive integers and Ln containing the negative
    integers. (Without creating new lists).

    Exercise 02 :
    Let L1 and L2 be two integers lists, write a parameterized actions to solving each of the following
    problems :
    1. Checking if L1 and L2 are identical (contain the same elements in the same order),
    2. Checking if L1 is included in L2 (all the elements of L1 are found in L2, the order does not
    count),
    3. Checking if L1 is a sublist of L2 (L1 is included in L2 in the same order).
    4. Checking if L1 and L2 are sorted in ascending order, then merging them into a sorted list L,
    sorted in the same order.
    Exercise 03 :
    Let T be an array of 26 lists of character strings. Such that element 1 contains the head of the list
    containing words starting with the letter 'A', element 2 contains the head of the list of words starting
    with the letter 'B', etc.
    1. Give the declaration of this data structure.
    2. Write a parameterized action allowing you to search for a given word M in this structure.

    Exercise 04 :
    Consider the following binary matrix :

    BitMap =
    1. Write a parameterized action allowing to construct a linear linked list containing the non-zero
    values of the BitMap matrix (we save the row and column numbers for each element).
    2. Write a parameterized action to delete duplicate lines from the Bitmap matrix (we keep one
    occurrence of each line).

    Exercise 5 :
    We want to construct a word based on the three letters A, B and C while respecting the following rules:
    At the beginning (at step 0) the word is reduced to A. Then at each step of evolution, A is trans-
    formed into ABC, B is transformed into C, and C is transformed into A.
    Examples : Step0 Step 1 Step 2 Step 3
    A → A B C → A B C C A → A B C C A A A B C → ...
    We want to know the word at step N, given N. Using a linked list, each cell contains a letter (A, B or
    C).
    1. Write a procedure to display the elements of a list of characters.
    2. Write an algorithm that tracks the evolution of the word and displays the word constructed at each
    step.

    Complementary Series

    Exercise 7 : Let T be an array of 26 lists of character strings. List1 contains words starting with the
    letter 'A', List2 contains words starting with the letter 'B'...etc.
    Declare T and write a function that checks for the existence of a word M in the structure.
    Exercise 8 :
    Given two lists (L1 and L2) of positive integer values:
    1. Give the declarations of the lists;
    2. Write a function that checks if L1 and L2 are disjoint (L1 ∩ L2 = Ø).
    3. Write a function that checks if L1 is prefix of L2 (L2 starts with L1).
    4. Write a parameterized action allowing to move (without allocation or free) the even values from L1
    to L2, and, to move the odd values from L2 to L1;

    Exercise 9 :
    Let L be a list of characters constituting words (a word is a sequence of characters not containing a
    blank) separated by a single blank character (space).
    Write a procedure that reverses the words in list L without creating a new list.
    Exercise 10 :
    In this exercise, we propose to develop a module allowing us to manipulate sparse polynomials. A
    sparse polynomial is a polynomial containing very few non-zero monomials.
    Exemple : P(x) = 5.6 x1280 + 0.8 x – 9 contains 1281 terms of which only 3 are non-zero.
    Each monomial is described by a Tmonome type record comprising the following 3 fields:
     Deg: integer representing the degree of the monomial;
     Coef: real representing the coefficient of the monomial;
     Next: pointer to the next monomial.
    The list representing the polynomial will be sorted in order of decreasing degree. An empty list (NULL)
    corresponds to the zero polynomial;

    1. Write an Add procedure which adds to a polynomial (Pol)


    the value of a monomial defined by its degree (Deg) and its
    coefficient (Coef).
    2. Write the Sum and Product procedures which respectively
    realize the sum and the product of two polynomials Pol1 and
    Pol2.
    3. Write a Value function which calculates the value of the
    polynomial for a value val of the variable x.
    4. Write a Derive procedure which determines the derivative
    DPol of a polynomial Pol.
    5. Write a Primitive procedure which determines the primitive
    PPol of a polynomial Pol, knowing that PPol(0)=1.

    Exercise 11 :
    Let L be a list of integers.
    1- Write a DETACHE procedure which returns the address of the minimum of the list L and de-
    taches it from the list without delete.
    2- Using the DETACHE procedure, write a SORT procedure which sorts the list L in descending order
    (without creating a new list).

    Exercise 12 : (2020 Exam)


    Given two integer files 'Pair.dat' and 'Impair.dat', we want to create an Average linked list 'My'
    where each element represents the average of the values having the same position in both files.
    1. Give the average list statement.
    2. Write a parameterized CreateL action to create the 'My' list.
    3. Write a DeleteL parameterized action deleting the averages lower than a value X in this list.

    Example :
    Exercise 13 : (2020 rattrapage)
    Let Finterval be an existing file containing intervals of integers where each element (interval) is defined
    by two limits a and b with a≤ b.
    1. Give the declaration of an element of the file.
    2. Write a function Lmax which determines the length of the longest interval in the Finterval
    file.
    3. Write a parameterized action CreateL to create a list of integers L containing the limits of the
    intervals of the Finterval file having the max length (Lmax).

    Example :

    Exercise 14 (2021 Exam)


    1. Let N be a strictly positive integer,
    Write a Decompose AP to create a list L representing the number N where each element of the list
    contains a digit of the number N between 0 and 9 (see example).
    2. Using a Decompose ÁP, write an algorithm allowing to:
     Enter 2 strictly positive integers A and B and create their respective lists L1 and L2.
     Create the list L representing the sum of the two lists L1 and L2.
     Display the integer represented by the list L.
    Examples:

    Exercise 15 : (rattrapage 2021)


    Let L be a list of words of maximum size 25 characters.
    1. Give the declaration of this list.
    2. Write a Palindrome function to check if a given word is palindrome.
    3. Write a DetachePal procedure which gives the address of the first palindrome word in the list L and
    detaches it from the list without deleting it.
    4. Using the DetachePal procedure, write a ListePal procedure to create a list LP containing all the
    palindrome words from list L in the reverse order of their appearance in L (without creating a
    new list).
    Example: L: “LMD” → “ICI” → “USTHB” → “ELLE” → “SS” → “ISIL” → “ACAD” → “RADAR”
    (Nil)
    After processing:
    L: “LMD” → “USTHB” → “ISIL” → “ACAD” (Nil)
    LP: “RADAR” → “SS” → “ELLE” → “ICI” (Nil)
    Exercise 16 : (Exam 2022)
    Let T be an array of N integers (2≤N≤100) already filled with strictly positive elements.
    1. Write a parameterized action MAXT to give the largest element of T and replace this element with
    the value 0 (replace only the first occurrence)
    2. Using MAXT, write a parameterized action to create, from the vector T, a list L sorted in ascending
    order.
    3. From the list L created previously, write a parameterized action allowing the first sequence of repeti-
    tive values to be deleted.
    4. Write a parameterized action allowing to:
    a) Create a list L1, without allocation, containing the non- repeating values of L.
    b) Create a list L2, with allocation, containing for each repetitive value of L, the value itself as
    well as its number of occurrences in L (declare the necessary structure).

    Example: For N = 10

    Exercise 17 (rattrapage 2022)


    1. Let NBR be a strictly positive integer, write a parameterized action to create a list L from NBR,
    with the first digit of NBR as the last element of the list and the last digit of NBR as the first ele-
    ment of list L (see example 1).The list L thus represents the NBR number.
    Example 1 :
    NBR=26374
    L : 4 → 7 → 3→ 6 → 2 (Nil)
    2. Let L be a list representing a strictly positive integer and an integer N between 1 and 9, write a pa-
    rameterized action to create a list LM representing the multiplication of L by N; without converting
    the list L into a number (see example 2).
    Examples 2 :
    L : 4 → 7 → 3 → 6 → 2 (Nil)
    N=2
    LM : 8 → 4 → 7 → 2 → 5 (Nil)

    L : 4 → 7 → 3 → 6 → 2 (Nil)
    N=9
    LM : 6 → 6 → 3 → 7 → 3 → 2 (Nil)
    3. Let L be a list representing a strictly positive integer and an integer N between 0 and 9, write a pa-
    rameterized action allowing all occurrences of N to be deleted from L (see example 3).
    Example 3:
    L : 6 → 6 → 3 → 7 → 3 → 2 (Nil)
    N=3
    L: 6 → 6 → 7 → 2 (Nil)
    4. Given a list L representing a strictly positive integer NBR, write a parameterized action allowing
    the number NBR to be given as a result (see example 4).
    Example 4:
    L : 6 → 6 → 7 → 2 (Nil)
    NBR = 2766

    You might also like