熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

第一章緒論習題練習

2013-11-15 15:48:45  來源: 數據結構 

簡述下列概念數據數據元素數據類型數據結構邏輯結構存儲結構線性結構非線性結構

試舉一個數據結構的例子敘述其邏輯結構存儲結構運算三個方面的內容     

常用的存儲表示方法有哪幾種?

設三個函數fgh分別為 f(n)=n+n+ g(n)=n+n h(n)=n+nlgn 請判斷下列關系是否成立
  () f(n)=O(g(n)) 
  () g(n)=O(f(n)) 
  () h(n)=O(n)
  () h(n)=O(nlgn)

設有兩個算法在同一機器上運行其執行時間分別為nn要使前者快於後者n至少要多大?

設n為正整數利用大O記號將下列程序段的執行時間表示為n的函數
() i=; k=
   while(i<n)
    { k=k+*i;i++;
    }
() i=; k=;
   do{
    k=k+*i; i++; 
    }
   while(i<n); 

() i=; j=
   while(i+j<=n) 
    {
     if (i>j) j++;
     else i++;
    }

()x=n; // n> 
  while (x>=(y+)*(y+))
   y++;

() x=; y=
    while(y>)
     if(x>)
      {x=x;y;}
     else x++;

算法的時間復雜度僅與問題的規模相關嗎?

按增長率由小至大的順序排列下列各函數
    (/)n(/)n nn n n! n lgn nlgn n(/)

有時為了比較兩個同數量級算法的優劣須突出主項的常數因子而將低次項用大O記號表示例如設T(n)=nlgn+n+=nlgn+O(n) T(n)=nlgnn=lgn+O(n) 這兩個式子表示當n足夠大時T(n)優於T(n)因為前者的常數因子小於後者請用此方法表示下列函數並指出當n足夠大時哪一個較優哪一個較劣?
  () T(n)=nn+lgn   
  () T(n)=n+n+lgn  
  () T(n)=n+lgn     
  () T(n)=n+nlgn


From:http://tw.wingwit.com/Article/program/sjjg/201311/23996.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.