1樓：匿名使用者
1 錯。給的條件能確定連結串列含1個元素，而非空。
2 錯。
3 錯。m階b樹要求（葉上）至少m/2個元素，上面所謂的葉就是倒數第二層了，而三階平衡樹最底層可以有1個元素。
1. 下面程式段時間複雜度為________
for (int i=0;i for (int j=0;j s+=i; o(n*k) 2 資料結構的儲存結構包括順序，________，索引和雜湊四種。 連結 3.設森林t中有三棵樹，第一，二，三棵樹的結點個數分別為n1,n2,n3,將森林轉換成二叉樹後，其根結點的左子樹上有________個結點。 n1-1。 森林轉為二叉樹之後，原第一棵樹t1的根節點將成為二叉樹tn的根節點，其餘的採取貌似於長兄如父的方式排列，原先是父子關係的還是步子，但是原先是兄弟的也變成了父子，對於其他樹的根節點的有分支，會分到左分支的另一派左分支上。所以是n1-1 4.對二叉搜尋樹進行________遍歷，可以得到按關鍵字從小到大排列的結點序列。 中序 二叉搜尋樹為了搜尋的方便，根節點大於左邊的，小於右邊的。所以中序遍歷才會得到所要序列 三.選擇題 1.已知單連結串列a長度為m，單連結串列b長度為n，若將b聯接在a的末尾，其時間複雜度應為________。 a. o(1) b. o(m) c. o(n) d.o(m+n) b。步進m次（即o(m)）以達到其尾節點，然後將該節點的next指向b。如果給定了條件是連結串列既存有頭，又存有尾，那麼就是o(1).這裡選b。 2.設有一個遞迴演算法如下： int fact(int n) 則計算fact(n)需要呼叫該函式的次數為________次。 a. n b. n+1 c. n+2 d.n-1 b可樂答的不錯。可以保證。我做的結果一樣。 2樓：**的可樂 大略看了下，錯了請見諒。 ------------- 一.判斷題 1.（ ）帶表頭結點的雙向迴圈連結串列判空的條件是：first->next==first(first為表頭指標)。 錯。給的條件能確定連結串列含1個單元，而非空。 2.（ ）一個有向圖的鄰接表和逆鄰接表中的結點個數一定相等。 錯。但是有向圖的弧(指相鄰點vi到vj的有向邊)數等於鄰接表(逆鄰接表)個出邊表結點(入邊表結點)的數目。 3.（ ）一棵3階b樹是平衡的3路搜尋樹，反之，一棵平衡的3路搜尋樹是3階b樹。 錯。二.填空題 1. 下面程式段時間複雜度為________ for (int i=0;i for (int j=0;j s+=i; o(n*k) 2.資料結構的儲存結構包括順序，________，索引和雜湊四種。 連結3.設森林t中有三棵樹，第一，二，三棵樹的結點個數分別為n1,n2,n3,將森林轉換成二叉樹後，其根結點的左子樹上有________個結點。 n1-1。 森林轉為二叉樹之後，原第一棵樹t1的根節點將成為二叉樹tn的根節點，其右子樹的根節點為原來t2的根節點，左子樹的節點數顯然為原來t1的總結點數減去成為tn根節點的原t1的根節點，即n1-1。 4.對二叉搜尋樹進行________遍歷，可以得到按關鍵字從小到大排列的結點序列。 中序三.選擇題 1.已知單連結串列a長度為m，單連結串列b長度為n，若將b聯接在a的末尾，其時間複雜度應為________。 a. o(1) b. o(m) c. o(n) d.o(m+n) b。之前答錯了…… 已知單連結串列a，我們需要步進m次（即o(m)）以達到其尾節點，然後將該節點的next指向b，即可完成拼接。因此選b。 2.設有一個遞迴演算法如下： int fact(int n) 則計算fact(n)需要呼叫該函式的次數為________次。 a. n b. n+1 c. n+2 d.n-1 選b（取n=0，特殊情況）。 3樓：匿名使用者 哥們給的分好高啊，可惜我回答不了。 資料結構試題求解 4樓：匿名使用者 (1)b 刪第一個結點，時間複雜度分別為o(1)和o(n)兩個連結串列用相同型別變數，佔相同大專小空間屬(2)c 第h層和第h-1層都有可能有葉子結點 第h-1層有可能存在度為1的結點 (3)a 參照b樹的插入演算法 (4)c q是p的前驅結點 (5)b (6)c (7)d tail(a)=((d,e,f)) head(tail(a))=(d,e,f)tail(head(tail(a)))=(e,f)(8)a (9)d 前面三個不一定是生成樹 (10)c 過程很複雜 (11)b 關鍵是建立起huffman樹 5樓：匿名使用者 6樓：匿名使用者 第9題選c把 c是k演算法 d是p演算法 但圖由邊構成 不是由點構成 7樓：匿名使用者 caddb acbac a 8樓：匿名使用者 1～5bcacb 5～10 cdadc 11 b 資料結構試題，急求解。 9樓：匿名使用者 可以是順序結構。 順序佇列容易產生「溢位」現象，順序佇列還容易產生「假溢位」現象。因此，以迴圈佇列作為佇列的順序儲存結構，並採用「犧牲」一個儲存結點的方法，可以簡單地表達迴圈佇列的隊空和隊滿條件。 10樓：匿名使用者 本章介紹的是棧和佇列的邏輯結構定義及在兩種儲存結構(順序儲存結構和鏈式儲存結構)上如何實現棧和佇列的基本運算。本章的重點是掌握棧和佇列在兩種儲存結構上實現的基本運算，難點是迴圈佇列中對邊界條件的處理。 1.棧的邏輯結構、儲存結構及其相關演算法(綜合應用): 棧的邏輯結構和我們先前學過的線性表相同，如果它是非空的，則有且只有一個開始結點，有且只能有一個終端結點，其它的結點前後所相鄰的也只能是一個結點(直接前趨和直接後繼),但是棧的運算規則與線性表相比有更多的限制，棧(stack)是僅限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按後進先出的原則進行的，我們又稱棧為lifo表(last in first out). 棧的基本運算有六種： 構造空棧：initstack(s)、 判棧空: stackempty(s)、 判棧滿： stackfull(s)、 進棧： push(s,x)、可形象地理解為壓入，這時棧中會多一個元素 退棧： pop(s) 、 可形象地理解為彈出，彈出後棧中就無此元素了。 取棧頂元素：stacktop(s),不同與彈出，只是使用棧頂元素的值，該元素仍在棧頂不會改變。 由於棧也是線性表，因此線性表的儲存結構對棧也適用，通常棧有順序棧和鏈棧兩種儲存結構，這兩種儲存結構的不同，則使得實現棧的基本運算的演算法也有所不同。 我們要了解的是，在順序棧中有"上溢"和"下溢"的概念。順序棧好比一個盒子，我們在裡頭放了一疊書，當我們要用書的話只能從第一本開始拿(你會把盒子翻過來嗎?真聰明^^)，那麼當我們把書本放到這個棧中超過盒子的頂部時就放不下了(疊上去的不算，哼哼)，這時就是"上溢","上溢"也就是棧頂指標指出棧的外面，顯然是出錯了。 反之，當棧中已沒有書時，我們再去拿，看看沒書，把盒子拎起來看看盒底，還是沒有，這就是"下溢"。"下溢"本身可以表示棧為空棧,因此可以用它來作為控制轉移的條件。 鏈棧則沒有上溢的限制，它就象是一條一頭固定的鏈子，可以在活動的一頭自由地增加鏈環(結點)而不會溢位，鏈棧不需要在頭部附加頭結點，因為棧都是在頭部進行操作的，如果加了頭結點，等於要在頭結點之後的結點進行操作，反而使演算法更復雜，所以只要有連結串列的頭指標就可以了。 以上兩種儲存結構的棧的基本操作演算法是不同的，我們主要要學會進棧和退棧的基本演算法以解決簡單的應用問題。 2.佇列的邏輯結構、儲存結構及其相關演算法(綜合應用)。 佇列(queue,念q音)也是一種運算受限的線性表，它的運算限制與棧不同，是兩頭都有限制，插入只能在表的一端進行(只進不出)，而刪除只能在表的另一端進行(只出不進)，允許刪除的一端稱為隊尾(rear)，允許插入的一端稱為隊頭 (front) ,佇列的操作原則是先進先出的，所以佇列又稱作fifo表(first in first out) 佇列的基本運算也有六種： 置空隊 ：initqueue(q) 判隊空： queueempty(q) 判隊滿： queuefull(q) 入隊 ： enqueue(q,x) 出隊 ： dequeue(q) 取隊頭元素： queuefront(q),不同與出隊，隊頭元素仍然保留 佇列也有順序儲存和鏈式儲存兩種儲存結構，前者稱順序佇列，後者為鏈隊。 對於順序佇列，我們要理解"假上溢"的現象。 我們現實中的佇列比如人群排隊買票，隊伍中的人是可以一邊進去從另一頭出來的，除非地方不夠，總不會有"溢位"的現象，相似地，當佇列中元素完全充滿這個向量空間時，再入隊自然就會上溢，如果佇列中已沒有元素，那麼再要出隊也會下溢。 那麼"假上溢"就是怎麼回事呢? 因為在這裡，我們的佇列是儲存在一個向量空間裡，在這一段連續的儲存空間中，由一個佇列頭指標和一個尾指標表示這個佇列，當頭指標和尾指標指向同一個位置時，佇列為空，也就是說，佇列是由兩個指標中間的元素構成的。在佇列中，入隊和出隊並不是象現實中，元素一個個地向前移動，走完了就沒有了,而是指標在移動，當出隊操作時，頭指標向前(即向量空間的尾部)增加一個位置，入隊時，尾指標向前增加一個位置，在某種情況下，比如說進一個出一個，兩個指標就不停地向前移動，直到佇列所在向量空間的尾部，這時再入隊的話，尾指標就要跑到向量空間外面去了，僅管這時整個向量空間是空的，佇列也是空的，卻產生了"上溢"現象，這就是假上溢。 為了克服這種現象造成的空間浪費，我們引入迴圈向量的概念，就好比是把向量空間彎起來，形成一個頭尾相接的環形，這樣，當存於其中的佇列頭尾指標移到向量空間的上界(尾部)時，再加1的操作(入隊或出隊)就使指標指向向量的下界，也就是從頭開始。這時的佇列就稱迴圈佇列。 通常我們應用的大都是迴圈佇列。由於迴圈的原因，光看頭尾指標重疊在一起我們並不能判斷佇列是空的還是滿的，這時就需要處理一些邊界條件，以區別佇列是空還是滿。方法至少有三種，一種是另設一個布林變數來判斷(就是請別人看著，是空還是滿由他說了算)，第二種是少用一個元素空間，當入隊時，先測試入隊後尾指標是不是會等於頭指標，如果相等就算隊已滿，不許入隊。 第三種就是用一個計數器記錄佇列中的元素的總數，這樣就可以隨時知道佇列的長度了，只要佇列中的元素個數等於向量空間的長度，就是隊滿。 以上是順序佇列，我們要掌握相應演算法以解決簡單應用問題。 佇列的鏈式儲存結構稱為鏈佇列，一個鏈佇列就是一個操作受限的單連結串列。為了便於在表尾進行插入(入隊)的操作，在表尾增加一個尾指標，一個鏈佇列就由一個頭指標和一個尾指標唯一地確定。鏈佇列不存在隊滿和上溢的問題。 在鏈佇列的出隊演算法中，要注意當原隊中只有一個結點時，出隊後要同進修改頭尾指標並使佇列變空。 3.棧和佇列的應用(領會) 教材中舉了幾個例子，對於我們初學者來說，看上去比較繁，我們只要掌握一點，那就是，對於什麼情況下用棧和佇列作為解決問題的資料結構。 判斷的要點就是：如果這個問題滿足後進先出(lifo)的原則，就可以使用棧來處理。如果這個問題滿足先進先出(fifo)的原則，就可以使用佇列來處理。 比如簡單的說，有一個陣列序列，我們輸入時按順序輸入，但是輸出時需要逆序輸出，那麼它就可以利用棧來處理，把這個陣列存入一個棧中就可以容易地按逆序輸出結果了 假溢位是是佇列在一端進入插入，top值就會增加，在另一端刪除，當判斷top==max-1是，就會說明已經隊滿，但實際在佇列的另一端還是有儲存空間的，這就是「假溢位」。 解決方法：設定佇列為迴圈佇列就可以了。top=（top+1）mod （max-1）。 下面是一個例項， 不過這個實現會浪費一個元素的儲存空間。如果不想浪費佇列的儲存空間， 就需要設定一個監視變數。 public class queue public boolean enqueue(t t)else }public t dequeue()else }public boolean isempty()else }public boolean isfull()else}} 你要的演算法是隻要描述還是要上機可以通過的語句啊？先回答第8題吧。1 38，49，65，97，76，13，27，492 38，49，65，97，76，13，27，493 38，49，65，97，76，13，27，494 38，49，65，76，97，13，27，495 13，38，49，65，76，... void inorder bitree root else 這就是中序遍歷的演算法 include include define maxsize 64 typedef char datatype typedef struct node bitree bitree creatree r q r s i... 資料結構是計算機儲存 組織資料的方式。資料結構是指相互之間存在一種或多種特定關係的資料元素的集合。通常情況下，精心選擇的資料結構可以帶來更高的執行或者儲存效率。一 資料的邏輯結構 指反映資料元素之間的邏輯關係的資料結構，其中的邏輯關係是指資料元素之間的前後件關係，而與他們在計算機中的儲存位置無關。邏...資料結構考試題，資料結構 考試題
資料結構考試題，資料結構試卷
資料結構問題，資料結構（java）