第1章緒論
判斷：（中科院1999）
順序儲存方式只能用於儲存線性結構。－錯
順序查詢法適用於儲存結構為順序或鏈結儲存的線性表。－對
填空：（中科院1999）
對於給定的n個元素，可以構造出的邏輯結構有四種。
－集合線性結構－樹形結構－圖結構
計算機演算法必須具備輸入、輸出等5個特性。 b.可行性、確定性和有窮性
簡述演算法的5個特性。
第2章線性表
問答：（北京航空1998）
在非空雙向迴圈表中q所指的結點後面插入p所指的結點的過程已經依次進行了3步：p->llink:=q；p->rlink:
=q->rlink；q->rlink:=p；第4步應是什麼動作？
－q->
問答：若較頻繁地對乙個線性表進行插入和刪除操作，該線性表宜採用何種儲存結構？為什麼？
－鏈式儲存結構
簡答：（北京科技大學2002）
設單鏈表中結點的資料域為data，指標域為next，指標p為表中某一結點的位址，請寫出在p結點之前插入乙個s結點的c語言描述語句。
－s->.next:=p
選擇：（武漢理工2002）
指標p所指的元素是雙向迴圈鍊錶l的尾元素的條件是（ ） >rlink=l
乙個迴圈鍊錶可以由所給定的頭指標或者尾指標惟一地確定。－對
寫乙個演算法，建立雙向迴圈鍊錶
簡答：寫出在雙向鍊錶指標p之後插入結點s的操作序列
－s->right=p->right；if(p->right) p->right->left=s； s->left=p； p->right=s
選擇：（南京理工2002）
在乙個單鏈表中，若刪除p結點的後繼結點，則（ ）p->next=p->next->next
迴圈鍊錶的主要優點是（ ）從表中任一結點出發都能遍歷整個鍊錶
第3章棧和佇列
選擇：（程式設計師2004）
判斷乙個表示式中左右括號是否匹配，採用（ d.棧 ）實現較為方便
用單鏈表表示的鏈式佇列的對頭在鍊錶的（ 鏈頭 ）位置
判斷：（中科院1999）
棧和佇列都是限制取點的線性結構－正確
消除遞迴不一定需要使用棧－正確
棧、先進先出佇列、優先順序佇列、雙端佇列等都可以看作是乙個容器類的派生類。該容器代表限制訪問位置的順序訪問結構。－正確
迴圈佇列a[0..m-1]存放其元素，用front和rear分別表示隊頭和隊尾，則迴圈佇列滿的條件是（ ）
a.（演算法：（中科院2000）
設順序棧s中有2n個元素，從棧頂到棧底的元素依次是a2n，a2n-1，。。。，a2，a1，要求通過乙個輔助的迴圈佇列及相應的入棧、出棧、入隊、出隊操作來重新排列棧中元素，使得從棧頂到棧底的元素依次是a2n，a2n-2，。。。，a4，a2，a2n-1，a2n-3，。。。
，a3，a1，請寫出一演算法實現該操作，要求附加的空間是o(n)，時間複雜度為o(n)。
簡答： a、b、c三個元素進棧s的次序是a、b、c，利用push(s,x)，pop(s)表示入棧、出棧操作，寫出所有可能的出棧序列和獲得每個序列的相應操作，並指明哪個序列不會是出棧序列。
－cba bca acb abc bac
－cab
在操作序列push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之後，棧頂元素和棧底元素分別是什麼？－6－1
在操作序列qinsert(1)，qinsert(2)，qdelete，qinsert(5)，qinsert(7)，qdelete，qinsert(9)之後，隊頭元素和隊尾元素分別是什麼？－5－9
第4章串
選擇：（程式設計師2004）
字串是一種線性表，其特殊性表現在（ 1 ）
a.它的資料元素是乙個字元 b.它可以鏈式儲存
c.它可以順序儲存d.它的資料元素可以是多個字元
第5章陣列和廣義表
選擇：（程式設計師2005）
設陣列a[1..10,5..15]的元素以行為主序存放，每個元素占用4個儲存單元，則陣列元素a[i,j](1≤i≤10,5≤j≤15)的位址計算公式為
－d選擇：（程式設計師2004）
對於二維陣列a[1..4,3..6]，設每個元素佔兩個儲存單元，若分別以行和列為主序儲存，則元素a[3,4]相對於陣列空間起始位址的偏移量分別是（ 4 ）和（ 1 ）
a.12 b.14 c.16 d.18
若廣義表l=((1,2,3))，則l的長度和深度分別是（ 2 ）
a.1和1 b.1和2 c.1和3 d.2和2
填空：（中國科技大學1998）
設廣義表l=((),())，則head(ltail(ll的長度是（ ）；l的深度是head(l)=();－tail(l)=(());－2－2
選擇：（北京郵電1998）
已知廣義表l=((x,y,z),a,(u,t,w))，從l表中取出原子項t的運算是
將乙個a[1..100,1..100]的三對角矩陣，按行優先存入一維陣列b[1..
298]中，a中元素a66,65（即元素下標）在b中的位置k為（ 2 ）a.198 b.195 c.
197三對角線矩陣a[1..n][1..n]以行序為主順序儲存，其儲存始址是b，每個元素佔乙個儲存單元，則元素a[i][j]的儲存起始位址為（ ）(1≤i,j≤n)
第6章樹和二叉樹
選擇：（程式設計師2004）
在一顆非空二叉樹中，葉子節點的總數比度為2的節點總數多（ 1 ）個
在一棵完全二叉樹中，其根的序號為1，可判定序號為p和q的兩個結點是否在同一層。│log2p」=│log2q」
如果根的層次為1，具有61個結點的完全二叉樹的高度為（ 6 ）
若二叉樹的先序遍歷序列為abdecf，中序遍歷序列dbeafc，則其後序遍歷序列為（ debfca
由權值為9,2,5,7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為（ 44 ）
（ ）的遍歷仍需要棧的支援 c.後序線索樹
對於前序遍歷和中序遍歷結果相同的二叉樹為（ f.所有結點只有右孩子的二叉樹，前序遍歷和後序遍歷結果相同的二叉樹為b.只有根結點的二叉樹
哈夫曼樹是帶權路徑長度最短的樹，路徑上長度結點離根（ ）
b.較小 d.較遠
簡述二叉哈夫曼樹的建樹方法
簡答：（北京科技大學2002）
設記錄的關鍵字（key）集合k=，以k為權值集合，構建一棵哈夫曼樹，依次取k中各值，構建一棵二叉排序樹
判定：高度為k的二叉樹至多有2k-1（k≥1）個結點－錯誤
選擇：（南京理工2002）
**索化二叉樹中，結點t沒有左子樹的充要條件是》ltag=1
第7章圖
選擇：（程式設計師2004）
採用鄰接表表示一有向圖，若圖中某頂點的入度和出度分別為d1和d2，則該頂點對應的單鏈表的結點數為（ ）
具有n（n>0）個頂點的無向圖最多含有（ ）條邊
無向圖中乙個頂點的度是指圖中c.與該頂點相鄰接的頂點數
乙個具有n（n>0）個頂點的連通無向圖至少有條邊
第9章查詢
選擇：（軟體設計師2005）
利用逐點插入法建立序列（50,72,43,85,75,20,35,45,65,30）對應的二叉排序樹以後，查詢元素30要進行（5 ）次元素間的比較
在常用的描述二叉排序樹的儲存結構中，關鍵值最大的結點（ ） b.右指標一定為空
已知乙個線性表（38,25,74,63,52,48），假定採用雜湊函式h(key)=key%7計算雜湊位址，並雜湊存放在雜湊表a[0..6]中，若採用線性探測方法解決衝突，則在該雜湊表上進行等概率成功查詢的平均查詢長度為（ ） c.2.
0設h(x)是一雜湊函式，有k個不同的關鍵字（x1,x2,x3,…,xk）滿足h(x1)=h(x2)=…=h(xk)，若用線性探測法將這k個關鍵字存入雜湊表中，至少要探測（ ）次
第10章內部排序
選擇：（程式設計師2005）
從未排序的序列中依次取出乙個元素與已排序序列中的元素進行比較，然後將其放在已排序序列的合適位置上，該排序方法稱為（ ）a.插入排序
選擇：（武漢理工2002）
對n個資料進行排序，不穩定排序是（ 排序 ），快速排序是一種（ b.交換排序 ），關鍵字序列（ ）是乙個堆 d.20,35,23,80,54,76
簡答：（北京科技大學2002）（清華大學1998類似）
請指出三個穩定和三個不穩定的內部排序方法
－基數排序、簡單選擇排序、插入排序、歸併排序、氣泡排序
－快速排序、堆排序、希爾（shell）排序
若要求排序是穩定的，且關鍵字為實數，則在下列排序方法中應選為宜。直接插入
若關鍵字是非負整數，則下列排序中平均速度最快的排序是（ ）；若要求輔助空間為o(1)，則平均速度最快的排序是（ ）；若要求排序是穩定的，且關鍵字為實數，則平均速度最快的排序是（ ）
資料結構習題集
第一章緒論 1 下面是幾種資料的邏輯結構s d，r 分別畫出對應的資料邏輯結構，並指出它們分別屬於何種結構。d r a r b r c r 2 分析下列程式段的時間複雜度 a for i 0 ifor j 0 j b i j 0 b s 0 for i 0 ifor j 0 j s b i j c ...
資料結構習題集
資料結構 練習冊 陝西理工學院計算機系 資料結構精品課建設小組編 電腦科學與技術系 前言 資料結構 練習冊按照 資料結構 課程的教學大綱編著，分為九章，主要題型包括 選擇題 判斷題 填空題和程式題，每章都從基礎出發，有少部分難度較大題型。編寫的目的是為了給學生提供乙個練習和提高的平台。可作為我校電腦...
資料結構習題集
第一章緒論 1 下面是幾種資料的邏輯結構s d，r 分別畫出對應的資料邏輯結構，並指出它們分別屬於何種結構。d r a r b r c r 2 分析下列程式段的時間複雜度 a for i 0 ifor j 0 j b i j 0 b s 0 for i 0 ifor j 0 j s b i j c ...