一、填空
資料結構按物理結構可分為線性結構和集合。
在單鏈表中，要刪除某一指定的結點，必須先找到該結點的( )結點。
對於乙個具有n個結點的單鏈表，在*p結點後插入乙個新結點的時間複雜度是( )；在給定值x的結點後插入乙個新結點的時間複雜度是( )。
**性結構、樹形結構和圖形結構中，直接前驅和直接後繼結點之間分別存在著 、1：n和的聯絡。
一棵有n個節點的滿二叉樹有個度為1的節點。
中綴表示式a-(b+c/d)*e的字尾表示式是
具有n個頂點的完全無向圖具有條邊，利用鄰接矩陣表示的完全無向圖具有行，若無向圖的鄰接矩陣不存在邊，則賦值_______。
平衡二叉樹是每個結點的左、右子樹的高度至多相差______。
乙個有向圖g中若有弧、和,圖g的拓撲序列為
直接插入排序的時間複雜度是 ，它(是/否？) 穩定的。
廣義表((a, b), c, d)的表頭是 ，表尾是
限定在同一端進行插入、刪除的線性表稱為 ；該端稱為 。
內排序演算法中空間複雜度最大的演算法是
設順序棧s為空，若6個元素入棧順序為a1,a2,a3,a4,a5,a6，出棧順序為a2,a4,a3,a6,a5,a1，則棧s的容量至少為 。
g是乙個非連通無向圖，共有28條邊，則該圖至少有________個頂點。
一棵有n個結點滿二叉樹有個度為1的結點，有個分支結點和個葉子結點，該滿二叉樹的深度為 。
深度為6（根的層次為1）的完全二叉樹至多有_________結點，至少有_________結點。
g是乙個非連通無向圖，共有28條邊，則該圖至少有________個頂點。
從鄰接矩陣a=中可以看出，該圖共有________個頂點。如果是有向圖，該圖共有________條弧，如果是無向圖，則共有________條邊。
乙個有向圖g中若有弧、和, 則在圖g的拓撲序列中，頂點vi,vj和vk的相對位置為
二、選擇題
將s結點插入到p結點之後實現語句為（ ）。
a. s->next=p->next; p->next=sb. (*p).next=s; (*s).next=(*p).next;
c. s->next=p->next; p->next=s->next; d. s->next=p+1; p->next=s;
將一棵有100個節點的完全二叉樹從上到下，從左到右編號，根節點的編號為1，則編號為49的節點的右孩子編號是（ ）。
a．97 b．98 c．99 d．100
帶頭結點的單鏈表head為空的判定條件是
a. head=nullb. head==null
c. head->next=nulld.head->next==null
（ ）是c語言中 」abcd321abcd」 的子串。
a. abcd b. 321ab c. 「abcabc」 d. 「21ab」
若廣義表a滿足head (a) = tail (a)，則a為
abcd
有5個頂點的圖，若為連通圖，則至少有（ ）條邊。
a．3 b．4 c．5 d．6
一組記錄的關鍵碼為（46,79,56,38,40,84），則利用快速排序的方法，以第乙個記錄為基準得到的一次劃分結果為（ ）。
a. 38，40，46，56，79，84 b. 40，38，46，79，56，84
c. 40，38，46，56，79，84 d. 40，38，46，84，56，79
有5個頂點的圖，若為強連通圖，至少有（ ）條邊。
a．3 b．4 c．5 d．6
下列不屬於內排序演算法的是（ ）。
a. 歸併排序 b. 基數排序 c. 拓撲排序 d. 堆排序
已知廣義表ls=((a,c), (b,d))，運算head和tail函式取出ls中元素b的運算是（ ）。
a．head(tail(lsb．tail(head(ls))
c．head(tail((tail(lsd．head(head(tail(ls)))
線性鍊錶中各鏈結點之間的位址（ ）。
a. 必須連續 b. 部分位址必須連續 c. 不一定連續 d. 以上答案都錯誤
是c語言中」abcd321abcd」的子串。
a．abcd b. 321ab c. 』』abcabcd. 「21ab「
若串s=「software「，其子串的個數是
a．8b. 9c. 36d. 37
在乙個單鏈表中，刪除*p結點的直接後繼結點，則執行（ ）。
a. p=p->nextb. p=p->next->next
c. p->next=pd. p->next=p->next->next
前序遍歷和後序遍歷結果相同的二叉樹具有（ ）特徵。
a. 一般二叉樹b. 只有左子樹的二叉樹
c. 只有右子樹的二叉樹 d. 只有根結點的二叉樹
採用折半查詢法查詢長度為n的線性表，每個元素的平均查詢長度為（ ）。
a. o(n2b. o(nlog2nc. o(n) d. o(log2n)
有乙個長度為12的有序表，按折半查詢法對該錶進行查詢，在表內各元素等概率情況下查詢成功所需的平均比較次數為（ ）
a. 35/12 b. 37/12 c. 39/12 d. 43/12
有乙個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當折半查詢值82的結點時，（ ）次比較後查詢成功。
a. 1 b. 2 c. 4 d. 8
從平均時間效能上看效能最佳，所需時間最省。
a． 堆排序 b．歸併排序 c．基數排序 d． 快速排序
評價乙個演算法時間效能的主要標準是（ ）。
a 演算法易於除錯b 演算法易於理解
c 演算法的穩定性和正確性d 演算法的時間複雜度
若廣義表a滿足head (a) = tail (a)，則a為
abcd
排序演算法的穩定性是指（ ）。
a. 經過排序之後，能使值相同的資料保持原順序中的相對位置不變
b. 經過排序之後，能使值相同的資料保持原順序中的絕對位置不變
c. 排序演算法的效能與被排序元素的數量關係不大
d. 排序演算法的效能與被排序元素的數量關係密切
雜湊函式除留餘數法，h(k)=k%m的m一般取（ ）。
a．自然數b. 整數c.素數d. 有理數
對線性表進行折半查詢時，要求線性表必須（ ）。
a. 以順序方式儲存 b. 以鏈結方式儲存
c. 以順序方式儲存，且結點按關鍵字有序排序
d. 以鏈結方式儲存，且結點按關鍵字有序排序
不帶頭結點的單鏈表head為空的判定條件是
a. head=nullb. head==null
c. head->next=nulld.head->next==null
有乙個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當折半查詢值82的結點時，（ ）次比較後查詢成功。
a. 1 b. 2 c. 4 d. 8
迴圈佇列用陣列a[0,m-1]存放其元素值，已知其頭尾指標分別是front 和 rear，則當前佇列中的元素個數是( )
a. (rear-front+m) % mb. rear-front+1
c. rear-front+1d. rear-front
若用乙個大小為6的一維陣列來實現迴圈佇列，且當前rear和front的值分別為0和3，當從佇列中刪除乙個元素，再加入兩個元素後，rear和front的值分別是( )
a. 1 和 5 b. 2 和 4 c. 4 和 2 d. 5 和 1
將一棵有100個節點的完全二叉樹從上到下，從左到右編號，根節點的編號為1，則編號為49的節點的右孩子編號是（ ）。
資料結構複習題
1.資料結構可用三元式表示 d，s，p 其中 d是資料物件，s是d上的關係，p是對d的基本操作集。f 2 簡單地說,資料結構是帶有結構的資料元素的集合。t 3 判斷帶頭結點的非空迴圈單鏈表 頭指標為l 中指標p所指結點是最後乙個元素結點的條件是 p next l。t 4 線性表的鏈式儲存結構具有可直...
資料結構複習題
資料結構複習題 2004年6月 一 單項選擇題 1 鏈棧和順序棧相比，有乙個較明顯的優點是 a.通常不會出現棧滿的情況 b.通常不會出現棧空的情況 c.插入操作更加方便c.刪除操作更加方便 2 若待排序物件序列在排序前已按其排序碼遞增順序排序，則採用 方法比較次數最少。a 直接插入排序b 分劃交換排...
資料結構複習題
1 如果以鍊錶作為棧的儲存結構，則退棧操作時 a.必須判別棧是否滿 b.對棧不作任何判別 c.必須判別棧是否空 d.判別棧元素的型別 2 設陣列data 0.m 作為迴圈佇列sq的儲存空間，front為隊頭指標，rear為隊尾指標，則執行出隊操作的語句為 a.front front 1 b.fron...