تبلیغات
دست نوشته ها - نمونه سوالات درس ساختمان داده | برنامه نویسی + لینوکس و متن باز + روزنوشت + موسیقی

دست نوشته ها - نمونه سوالات درس ساختمان داده

برنامه نویسی + لینوکس و متن باز + روزنوشت + موسیقی
  • نمونه سوالات درس ساختمان داده

  • نویسنده: "feeruzy"، ارسال شده در: " درسی ،"، زمان ارسال: "8 آبان 87 ساعت 00:45"

    آرایه:
    آرایه سه قطری a یک آرایه n*n است که در آنij [a-j] 1 = a [i][j] = 0 حداکثر تعداد عناصر غیر صفر در چنین آرایه ای چیست. چگونه این عناصر می توانند در یک آرایه یک بعدی بطور ترتیبی ذخیره شود ؟
    2- پشته دوگانه : از یک آرایه یک بعدی دوتایی برای پیاده سازی دو پشته استفاده میکنیم بطوریکه عناصر پشته اول با شروع ار ابتدای آرایه و عناصر پشته دوم با شروع ار انتهای آرایه در آن قرار گیرند . توابع مربوط به ایجاد پشته خالی ، حذف عنصری از پشته ، افزودن عنصری به پشته را برای هر یک از دو پشته بنویسید .
    1-n 2-n 3-n 2 1 0


    P   


    A
    مثال :
    TOP 1 TOP 2
    S1 S2
    S1 S2

    بقیه در ادامه مطلب ...

     3- فرض کنید برای نگهداری یک سری عدد صحیح از یک صف حلقوی queue[100] استفاده نموده ایم بطوریکه queue[0] ، حاوی مقدار queue[1] , front حاوی مقدار near ( انتهای صف ) بکار میرود و queue[2] تا queue[q a] برای نمایش عناصر صف حلقوی بكار می روند. توابع ایجاد ، اضافه کردن مقداری به صف حلقوی و حذف مقداری از آن را بجای این مورد بنویسید .
    4- الف ) حداکثر تعداد عناصر صفر یک ماتریس سه قطری چند است ؟ب) آرایه سه بعدی A[4][6][7] مفروض است . اگر آدرس شروع این آرایه a باشد آدرس شروع عنصر A[3][1][4] را محاسبه کنید .
    5- از یک آرایه یک بعدی با طول n می توان برای پیاده سازی دو پشته استفاده نمود به طوری که عناصر پشته اول با شروع از ابتدای آرایه و عناصر پشته دوم با شروع از انتهای آرایه در آن قرار گیرند . توابع مربوط به ایجاد پشته خالی ، حذف عنصری از پشته و افزودن عنصری به پشته را برای هر یک از دو پشته بنویسید .
    6- الف ) توضیح دهید که چرا در پیاده سازی صف حلقوی با آرایه ، یک خانه از صف باید خالی بماند . ب) توابع مربوط به افزودن عنصری به صف حلقوی و حذف عنصری از آن را بنویسید .
    7- یک ماتریس 15*10 که هر یک از عناصر آن ، شش بایتی هستند را در نظر بگیرید . تعداد عناصر غیر صفر این ماتریس چقدر میتواند باشد که نگهداری آن به شکل ویژه اسپارس ، از لحاظ حافظه به صرفه تر از نگهداری معمولی آن به شکل آرایه دو بعدی باشد ؟ فضای لازم برای ذخیره شماره سطر و ستونهای عناصر صفر را دو بایت در نظر بگیرید .
    8- الف ) حداکثر تعداد عناصر غیر صفر یک ماتریس سه قطری چند است ؟ب ) عناصر غیر صفر یک ماتریس بالا مثلثی محض را به چه ترتیبی می توان در یک ارایه یک بعدی ذخیره نمود ؟ رابطه دستیابی این عناصر را بدست آورید .
    9 – عبارت زیر را به شکل میانوندی داده شده است . با ذکر مراحل ، معادل پسوندی آنرا بیابید . سپس عبارت پسوندی را به ازای مقادیر داده شده با ذکر مراحل ، ارزیابی کنید .
    Infix = 6+a/b-(3/x*2) +1)/5         a = 2 b=3 x=6
    10- كاربرى صف اولویت و انواع آن را توضیح دهید . چگونه می توان صف اولویت را با استفاده از آرایه صعودی پیاده سازی نمود ؟ در هر مورد دستورات لازم برای حذف و اضافه عنصر به صف اولویت به تفکیک نوع آن را ذکر کنید .
    11- عبارت میانوندی زیر را با رسم تغییرات پشته به پسوندی تبدیل کنید . سپس با نوشتن تابع ارزیابی ، عبارت پسوندی حاصل را به ازای مقادیر داده شده ارزیابی کنید . -A + (B/C * A-2) ^ K*B A=2              B=6        C=3     K=4
    12- أرایه ای به طول m موجود است . می خواهیم n صف ساده را در این آرایه پیاده سازی کنیم دستورات لازم برای ایجاد صف شماره i ، حذف عنصری از صف شماره i و افزودن عنصری به صف شماره i را بنویسید .
    13- الف ) تابعی بنویسید که یک ماتریس اسپارس را که به شکل ویژه ذخیره شده است دریافت نموده و ترانها ده آن را بدست آورد . ب) 60 درصد عناصر یک ماتریس 200 * 200 غیر صفر هستند هر عنصر ماتریس ، یک ساختار 15 بایتی است ، توضیح دهید که آیا پیاده سازی این ماتریس به روش ویژه بهتر است یا خیر ؟
    14- تابعی بنویسید که دو آرایه مرتب را از ورودی دریافت کند و آنها را طوری ادغام کند که آرایه حاصل نیز مرتب باشد .
    15- عبارت میانوندی زیر را با رسم مراحل ، به عبارت پسوندی تبدیل کنید . سپس با ذکر مراحل ، عبارت پسوندی حاصل را به ازای مقادیر داده شده ارزیابی نمایید . Infix = a+b/((c-d)*e)           a= 2 b=3 c=4 d=5 e=6
    16- الف ) ماتریس اسپارس روبرو را به شکل ویژه نمایش دهید .ب) ترانهاده آن را بیابید .ج) میزان حافظه لازم برای ذخیره نمودن این ماتریس را در دو حالت ذخیره معمولی و ویژه بدست آورید .
    0 4 2 0 0
    0 0 0 0 0
    6 3 0 0 0
    0 0 3 0 5
    0 1 0 0 5
    0 0 0 0 0

    15- مشکلات پیاده سازی صف ساده را با آرایه با یک مثال توضیح دهید . سپس تابع افزودن عنصری به صف حلقوی را بنویسید .
    16- ماتریس A ( m * n ) را در نظر بگیرید . اگر عنصری مانند a[i][j] در این ماتریس وجود داشته باشد بگونه ای که مقدار این عنصر ، کمترین مقدار در سطر شماره i و بزرگترین مقدار در ستون شماره j باشد ، گوییم که ماتریس A دارای saddle point است . تابعی بنویسید که یک ماتریس m *n را دریافت کرده و در صورت یافتن saddle point موقعیت آنرا مشخص نماید .
    17- توابع مربوط به ایجاد یک صف حلقوی ، افزودن عنصری به صف حلقوی و حذف عنصری از آن را با استفاده از آرایه items [n] بنویسید . رابطه ای برای محاسبه تعداد عناصر موجود در صف حلقوی بدست آورید .
    18- فرض کنید آرایه A به طول m موجود است . می خواهیم n پشته را با استفاده از این آرایه نمایش دهیم بگونه ای که سهم هر پشته m/n خانه های پشته باشد . در حالت ساده فرض کنید هر پشته تنها مجاز به حرکت در محدوده مربوط به خود میباشد . فرض کنید آرایه ای به نام top [n] وجود دارد بگونه ای که top [i] ، مشخص کننده اندیس عنصر بالای پشته شماره i است . توابع مربوط به ایجاد پشته i ام ( مقدار دهی اولیه آرایه top ) ، حذف عنصری از پشته i ام و افزودن عنصری به پشته i ام را بنویسید . m–1 ............. 2[m/n]-1 [m/n]-1 0   .............      
    19- الف) آرایه سه بعدی A[7][6][4] مفروض است . اگر ادرس شروع حافظه در ذخیره این ارایه a باشد ، عنصر A[3][2][1] در چه آدرسی نسبت به a در حافظه قرار میگیر د ؟ ب) ماتریس قطری n*n مفروض است ( یاداوری : در ماتریس قطری فقط عناصر روی قط اصلی غیر صفر هستند ) برای چه مقادیر n ذخیره سازی این ماتریس به شکل ویژه اسپارس از لحاظ حافظه مقرون به صرفه تر است ؟
    20- الف) توابع مربوط به پیاده سازی پشته را با لیست پیوندی ، شامل ایجاد پشته خالی ، افزودن عنصری به بالای پشته و حذف عنصری از بالای پشته را بنویسید ب) تابعی برای افزودن گرهی به یک لیست پیوندی ساده مرتب بنویسید .

    درخت:
    1.پیاده سازی درخت با استفاده از آرایه را توضیح دهید . روش را برای یک درخت نمونه پیاده کرده و توضیح دهید این روش برای چه درختهایی مناسب است و برای چه درختهایی مناسب نمیباشد .
    2- تابعی بنویسید که بزرگترین عنصر موجود در یک درخت جستجوی دودویی (BST) راحذف کند .
    3.الف) پیاده سازی درخت با استفاده از آرایه را توضیح دهید . روش را برای یک درخت نمونه پیاده کنید .ب) بطور کامل و با ذکر دلیل توضیح دهید این روش برای چه درختهایی مناسب است و برای چه درختهایی مناسب نمیباشد .
    4- تابعی بنویسید که آدرس گره ریشه یک درخت دودویی را دریافت کرده و آن درخت را به یک درخت دودویی نخی سمت راست تبدیل کند . - تابع حذف یک گره از یک درخت جستجوی دودویی (BST) را بنویسید حالتهای بدون فرزندی ، تک فرزندی و دو فرزندی را در نظر بگیرید .
    5- حاصل پیمایش RLV (زیر درخت راست ، زیر درخت چپ و سپس زیشه ) درخت دودویی زیر ، چیست ؟
    6- تعداد درخت های دودویی متمایزی که با چهار نود می توان رسم نمود چند تا است ، آنها را رسم کنید .
    ثابت کنید برای هر درخت دودویی ، رابطه زیر برقرار است : n0 = n2 + 1
    n0 : تعداد نود های بدون فرزند     n2 : تعداد نودهای با دو فرزند
     
    7- الف ) ثابت کنید تعداد گروه های یک درخت دودویی پر با عمق d برابر است با تعداد گره های غیر برگ این درختها را نیز مشخص کنید . ب) برای عبارت زیر درخت دودویی رسم کنید . سپس با پیمایش درخت ، عبارت پیشوندی و پسوندی آن را مشخص کنید .
    ((A * (B+C)) / (D-(E+F))) * (G/ (H/I * J)))
    8- تابعی برای ساخت یک درخت جستجوی دودویی نخی چپ و راست بنویسید . در این درخت از فیلد right بدون استفاده برای اشاره به گره بعدی که در پیمایش inorder ظاهر میشود و از فیلد leftبدون استفاده برای اشاره به گره قبلی که در پیمایش inorder ظاهر میشود استفاده میشود . در هر گره علاوه بر داده و فیلد, rthread فیلدی مانند lthread نیز در نظر بگیرید تا مشخص کننده نخی بدون یا نبودن فیلد left هر گره باشد.
    9- تابع حذف یک گره از درخت جستجوی دودویی را بنویسید .
    10-درخت جستجوی دودویی نخی راست حاصل از اعداد زیر را رسم كنید. 27 67 60 43 45 50 25 20 40
    11- تابع پیمایش preorder درخت دودویی نخی راست را بنویسید.
    12- پیمایش های inorder ، preorder یك درخت داده شده اند. درخت را رسم كنید.
    inorder: GFHKDLAWRQPZ
    preorder: FGHDKALWPQRZ

    لیست:
    1- روشهای مختلف پیاده سازی ماتریس اسپارس با لیست پیوندی را برای ماتریس زیر ترسیم نموده ، مزایا و معایب هر یک را توضیح دهید .
    0 0 6 0
    0 0 2 0
    0 0 0 0
    0 1 0 0

    2- تابعی بنویسید که آدرس شروع یک لیست پیوندی ساده را دریافت کرده و به صورت غیر بازگشتی و تنها با یکبار پیمایش آن ، لیست را معکوس کند .
    3- گاهی اوقات برای حذف یک نود از لیست پیوندی به جای آزاد نمودن فضای حافظه آن نود ، آن را به لیستی به نام av اضافه میکنند تا در صورت نیاز مجدد به حافظه از آن استفاده کنند . فرض کنید میخواهیم کلیه نودهای یک لیست حلقوی را حذف کنیم . با بکارگیری روش فوق ، کلیه نودهای این لیست حلقوی باید در لیست av قرار گیرند . تابعی بنویسید که آدرس شروع یک لیست حلقوی و لیست ساده av را دریافت کرده و بدون پیمایش هیچ یک از دو لیست ( بدون حلقه تکرار ) آنها را به هم متصل نماید و آدرس شروع لیست حاصل را بر گردانید .
    4- تابعی بنویسید که آدرس شروع یک لیست پیوندی نامرتب را دریافت نموده و لیست جدیدی بسازد که شامل عناصر لیست اولیه بصورت مرتب باشد و این لیست را بر گرداند .
    5- ماتریس اسپارس زیر را با کاملترین ساختار لیست پیوندی نمایش دهید.
    0 0 2 4 0
    0 0 0 0 0
    0 0 0 3 6
    5 0 0 0 0
    5 0 0 1 0
    0 0 0 0 0

    6- گره راس در لیست پیوندی چه گرهی است و به چه منظور به لیست اضافه می شود ؟ توابع حذف و اضافه گرهی به لیست پیوندی ساده با گره راس را بنویسید . 
    7- تابعی بنویسید که آدرس شروع یک لیست دو پیوندی و شماره یک گره را دریافت نموده و گره با آن شماره را از لیست حذف نماید .(گره ها با شروع از شماره یک ، شماره گذاری شده اند ) 
    8- دستورات لازم را برای پیاده سازی پشته با لیست پیوندی شامل ایجاد پشته خالی ، افزودن عنصری به پشته و حذف عنصری از پشته را بنویسید .
    9- تابعی بنویسید که جملات یک چند جمله ای را از کاربر دریافت كند و پس از تشکیل لیست پیوندی آن ، چند جمله ای را به ازای مقدار ورودی x ارزیابی نماید .
    10- الف ) چند جمله ای زیر را با یک استفاده از یک لیست پیوندی ساده با گره راس نمایش دهید . P(x) = 8 x ^ 7 – x ^ 5 + 12 x ^ 4 + 5 x ^ 2 – x + 3ب) تابعی بنویسید که آدرس شروع یک چند جمله ای و عدد k را بعنهوان پارامتر پذیرفته و ضریب x^k را در چند جمله ای برگرداند .
    11- تابعی بنویسید که آدرس گرههای راس لیست پیوندی مربوط به دو چند جمله ای اسپارس را دریافت کرده و حاصلضرب آن دو چند جمله ای را در لیست پیوندی سوم ( حاوی گره راس ) قرار دهد ( لیست حاصلضرب باید فاقد جملاتی با توانهای یکسان با شد ) .
    12- زیر برنامه ای بنویسید که آدرس شروع یک لیست دو پیوندی و عدد صحیح k را دریافت کند و گرهی با محتویات k را طوری به لیست اضافه کند که ترتیب صعودی عناصر لیست ، حفظ شود . ( لیست دو پیوندی ، صعودی و مرتب است )

    گراف:
    1- تابعی بنویسید که با توجه به یک ماتریس همجواری و گره j , i از یک گراف ، تعداد مسیر های با طول معین بین آن دو گره را محاسبه کند.
     2- گراف وزن دار زیر مفروض است . کمترین درخت پوشا برای این گراف را بهمراه رسم درخت پوشای مینیمال ( کمینه ) به روش وارشال مشخص کنید . - با شروع از گره A پیمایش عرضی و عمقی برروی گراف انجام داده نتیجه را مشخص کنید .
    3- در یک گراف بدون جهت همبند ( connect) به یك یال " پل " گفته میشود اگر با حذف آن از گراف ، گراف غیر همبند شود . برنامه ای بنویسید که یک گراف را دریافت کرده و یالهای پل آنرا مشخص نماید( یادآوری : گرافی همبند است که بین هر دو گره آن ، مسیری وجود داشته با شد ) 
    4- گراف زیر داده شده است : الف با شروع از گره A پیمایش عرضی و عمقی گراف را بنویسید .ب ) پس از نوشتن ماتریس همجواری ، ماتریس مسیر آنرا نیز بدست آمورید .ج) گراف را بدون جهت فرض نموده ، به روش kruskal (وارشال ) درخت پوشای کمینه معادل آن را بدست آورید .
    6-در گراف زیر ، كوتاهترین مسیر از راس صفر تا بقیه رئوس را به روش دیكسترا بدست آورید. ب)جستجوی عرضی و عمقی را با شروع از راس صفر انجام دهید.



    آخرین ویرایش در: "- ساعت -"


    نظرات
    sepehr salam
    khoobin ?
    mamnooon soalate zibaie bud ,.
    ama soalate ba javab man lazem daram .
    age soalate ba javab darid mano rahnamaie konid
    ارسال شده در 2 خرداد 89 17:01

    feeruzy:

    دوست عزیز. برخی از سایت ها و وبلاگها این کار رو انجام دادن و سوالات ترم های جدید رو هم می تونید از اونها بگیرید. در ضمن میتونید از دوستان ترم های بالاتر بخواهید تا پاسخ نامه ها رو از گلستان بگیرن و برای شما ارسال کنند.
    موفق باشید.

    yasaman salam doste aziz


    az webet mamnoonam

    jaleb bood

    man donbale matalebi dar morede derakhte b ya b+ o ina hasam ,, shooma siti sorgh nadarin

    mamnoon misham komakam koni

    rasi yadam raft begam

    : yasaman hasam daneshjoye mohandesiye It

    khoshvaghtam

    ya hagh
    ارسال شده در 15 بهمن 87 00:21