數據結構演算法題

1. 數據結構演算法題

int BTreeCount(BinTreeNode* BT, char x){

if(BT){
if(BT->data>x) return BTreeCount(BT->left,x)+BTreeCount(BT->right,x)+1;
else return BTreeCount(BT->left,x)+BTreeCount(BT->right,x);
}}

2. 數據結構與演算法題

數據結構復習
重點是了解數據結構的邏輯結構、存儲結構、數據的運算三方面的概念及相互關系，難點是演算法復雜度的分析方法。
需要達到<識記>層次的基本概念和術語有:數據、數據元素、數據項、數據結構。特別是數據結構的邏輯結構、存儲結構及數據運算的含義及其相互關系。數據結構的兩大類邏輯結構和四種常用的存儲表示方法。
需要達到<領會>層次的內容有演算法、演算法的時間復雜度和空間復雜度、最壞的和平均時間復雜度等概念，演算法描述和演算法分析的方法、對一般的演算法要能分析出時間復雜度。
對於基本概念，仔細看書就能夠理解，這里簡單提一下:
數據就是指能夠被計算機識別、存儲和加工處理的信息的載體。
數據元素是數據的基本單位，有時一個數據元素可以由若干個數據項組成。數據項是具有獨立含義的最小標識單位。如整數這個集合中，10這個數就可稱是一個數據元素.又比如在一個資料庫(關系式資料庫)中，一個記錄可稱為一個數據元素，而這個元素中的某一欄位就是一個數據項。

數據結構的定義雖然沒有標准，但是它包括以下三方面內容:邏輯結構、存儲結構、和對數據的操作。這一段比較重要，我用自己的語言來說明一下，大家看看是不是這樣。

比如一個表(資料庫)，我們就稱它為一個數據結構，它由很多記錄(數據元素)組成，每個元素又包括很多欄位(數據項)組成。那麼這張表的邏輯結構是怎麼樣的呢? 我們分析數據結構都是從結點(其實也就是元素、記錄、頂點，雖然在各種情況下所用名字不同，但說的是同一個東東)之間的關系來分析的，對於這個表中的任一個記錄(結點)，它只有一個直接前趨，只有一個直接後繼(前趨後繼就是前相鄰後相鄰的意思)，整個表只有一個開始結點和一個終端結點，那我們知道了這些關系就能明白這個表的邏輯結構了。

而存儲結構則是指用計算機語言如何表示結點之間的這種關系。如上面的表，在計算機語言中描述為連續存放在一片內存單元中，還是隨機的存放在內存中再用指針把它們鏈接在一起，這兩種表示法就成為兩種不同的存儲結構。(注意，在本課程里，我們只在高級語言的層次上討論存儲結構。)

第三個概念就是對數據的運算，比如一張表格，我們需要進行查找，增加，修改，刪除記錄等工作，而怎麼樣才能進行這樣的操作呢? 這也就是數據的運算，它不僅僅是加減乘除這些算術運算了，在數據結構中，這些運算常常涉及演算法問題

3. 數據結構演算法題：

無向圖：
先畫出全部的頂點，並用v1~v6依次標注，頂點的位置不重要，但可以配合邊的情況排布得盡量美觀；
然後，對於每一個包含在E中的頂點對，用一條邊連接兩個頂點。
鄰接表：
由於是無向圖，而且E中也沒有給出邊的權值，所以鄰接表實際上就是把E中的頂點對抄一遍，如：
V1 V2
V1 V4
……

4. 數據結構與演算法題需要回答

《數據結構與演算法》模擬題
一、填空題：（共15分）（每空一分）
按照排序時，存放數據的設備，排序可分為<1> 排序和<2> 排序。內部排序和外部排序
圖的常用的兩種存儲結構是<3> 和<4> 。鄰接矩陣和鄰接表
數據結構中的三種基本的結構形式是<5> 線性結構 和<6> 樹型結構 、圖型結構<7> 。
一個高度為6的二元樹，最多有<8> 63 個結點。
線性查找的時間復雜度為：<9> O(n^2) ，折半查找的時間復雜度為：<10> O(nlogn) 、堆分類的時間復雜度為：<11> O(nlogn) 。
在採用散列法進行查找時，為了減少沖突的機會，散列函數必須具有較好的隨機性，在我們介紹的幾種散列函數構造法中，隨機性最好的是<12> 隨機數 法、最簡單的構造方法是除留余數法<13> 。
線性表的三種存儲結構是：數組、<14> 鏈表 、<15> 靜態鏈表 。
二、回答下列問題：（共30分）
現有如右圖的樹，回答如下問題：看不見圖
根結點有：
葉結點有：
具有最大度的結點：
結點的祖先是：
結點的後代是：
棧存放在數組A[m]中，棧底位置是m-1。試問：
棧空的條件是什麼？top=m-1
棧滿的條件是什麼？top=-1
數據結構和抽象數據型的區別與聯系：
數據結構（data structure)—是相互之間存在一種或多種特定關系的數據元素的集合。數據元素相互之間的關系稱為結構。
抽象數據類型（ADT）：是指一個數學模型（數據結構）以及定義在該模型（數據結構）上的一組操作。

5. 一道數據結構題目 演算法

過程的目的就是使得x,y,z,成為遞減的順序
首先判斷x,y，如果x,y不是遞減，即x<y，那麼交換x和y，這樣就保證了x,y是遞減的順序，即x>=y
然後判斷y和z的順序，如果y和z已經保證遞減順序，也就是y>=z的話，那麼什麼也不用做，因為這是x,y,z肯定是遞減關系了
如果y<z的話，那就要看x和z誰大誰小，如果x比較大，那麼順序就是x,z,y，所以要交換z和y。如果z比較大，那麼順序就是z,x,y，那麼三個數都要變：y=x,x=z,z=y

當然所有的交換都要引入臨時變數temp
另外，從小到大很簡單，只要輸出的時候反過來就可以了，本來是順序輸出x,y,z，現在是順序輸出z,y,x

6. 數據結構關於折半演算法的題

修改了4處：

#include<stdio.h>

#include<stdlib.h>

#defineN15

intBinSrch(intl[],intk)

{

intlow,high,mid;

low=1;

high=10;

while(low<=high)

{

mid=(low+high)/2;

if(k==l[mid])

return(mid);

elseif(k<l[mid])

high=mid-1;

else

low=mid+1;

}

return(low);/*第1處修改*/

}

main()

{

intq,p,i,a[N];

for(i=1;i<=10;i++)

a[i]=i;

printf("請輸入要插入的值：");

scanf("%d",&p);

q=BinSrch(a,p);

if(a[q]<=p)/*a[q]是函數中彈出來的下標的相應值*/

{

for(i=10;i>=q;i--)/*第2處修改*/

a[i+1]=a[i];/*第3處修改*/

a[q]=p;

}

else

{

for(i=10;i>=q;i--)/*第4處修改*/

a[i+1]=a[i];

a[q]=p;

}

for(i=1;i<=11;i++)

printf("%d",a[i]);

}

運行測試：