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}} 排序方法小結 方法比較。綜合比較各種內部排序方法，其效能如下入所示 方法 平均時間 最壞情況 輔助空間 穩定性 特點。插入排序 o n2 o n2 o 1 n 30常用。希爾排序 o o o 1 不常用。起泡排序 o n2 o n2 o 1 初學。快速排序 o nlnn o n2 o n 常用，易惡... include include defineinfinity0 definemax vertex num10 最大頂點數 definemax edge num40 最大邊數typedefenumgraphkind typedefcharvertextype 頂點資料型別typedefstructar... include include include define datatype int define maxsize 1000 typedef struct nodebitreenode datatype bt maxsize bitreenode buildbtree datatype bt,in...資料結構中的排序問題，急，資料結構 排序問題
C語言資料結構，C語言 資料結構
資料結構c語言描述，資料結構（C語言描述）