一、單選:
1.資料結構通常是研究資料的(a )及它們之間的相互關係.
a.儲存和邏輯結構
b.儲存和抽象
c.理想與抽象
d.理想與邏輯
2.資料在計算機儲存器內表示時,實體地址與邏輯位址相同並且是連續的,稱為(c )
a.儲存結構
b.邏輯結構
c.順序儲存結構
d.鏈式儲存結構
3.非線性結構是資料元素之間是存在的一種( b)
a.一對多關係
b.多對多關係
c.多對一關係
d.一對一關係
4.非線性結構中,每個結點(d )
a.無直接前趨.
b.只有乙個直接前驅和後繼
c.只有乙個直接前驅和個數不受限制的直接後繼
d.有個數不受限制的直接前驅和後繼.
5.除了考慮儲存資料結構本身所占用的空間外,實現演算法所用輔助空間的多少稱為演算法的: b
a.時間效率
b.空間效率
c.硬體效率
d.軟體效率
二、填空
1、資料結構包括資料的_邏輯結構__,資料的_儲存結構_,資料的_運算_,這三個方面的內容 .
2、資料結構按邏輯結構可分為兩大類,分別是_線性結構和非線性結構_.
3、資料的儲存結構可用四種基本的儲存方法表示,分別是_順序、鏈式、索引和雜湊_.
4、線性結構反映結點間的邏輯關係是_一對一關係_.非線性結構反映結點間的邏輯關係是多對多關係.
5、乙個演算法的效率可分為時間效率和_空間效率_.
三、簡答：
分別寫出下列兩個演算法的時間複雜度.
1、x=0;
for(i=1;i答：o（n2）
2、x=0;
for(i=1;i答：o（n2）
一、填空
1、在棧中訪問資料的原則是：_先進後出_
2、在棧中，出棧操作的時間複雜度為：_ o(1)_
3、棧與一般線性表的區別主要在於_棧只允許在表尾進行插入和刪除操作_
4、順序棧是空棧的條件是：_
5、插入和刪除只能在一端進行的線性表，稱為：_受限線性表_
6、設迴圈向量有m個元素，迴圈向量中有乙個迴圈佇列，在迴圈佇列中設隊頭指標front指向隊頭元素，隊尾無名指是針指向隊尾元素後的乙個空閒元素。
.在迴圈佇列中，隊空標誌為_front==rear_隊滿標誌為_front==(rear+1)%m_
.當rear>=front時，佇列長度為_rear-front__；當rear8、在佇列結構中，允許插入的一端稱為__隊尾__，允許刪除的一端稱為：__隊頭__
9、s1="abcd",s2="cd"，則s2在s1中的位置是___3___
10、__不含任何字元的串____稱為空串，____僅含有空格字元的串___稱為空白串。
二、簡答：
1、設長度為n的鏈佇列用單迴圈鍊錶表示，若只設頭指標，則入隊，出隊操作的時間是什麼？如果只設尾指標呢？
答：若只設頭指標，則出隊時間為1，入隊時間需要n。因為每次入隊均需從頭指標開始查詢，找到最後乙個元素時方可進行入隊操作。
若只設尾指標，則出入隊時間均為1。因為是迴圈鍊錶，尾指標所指的下乙個元素就是頭指標所指的元素，所以出隊時不需要遍歷整個佇列。
2、設t[0..n-1]="abaabaabcaabaa" p[0..m-1]="aab",當用模式串p匹配目標串t時，請給出所有的有效位移。樸素匹配返回的位移是哪乙個？
答：所有的有效位移i的值為：2，5，9。樸素匹配的返回值是第乙個有效位移，因此是2。
3、如果目標串一共有10個字元，模式串共有2個字元，問，當匹配不成功的時候，最多比較了多少個字元？舉例說明。
答：串匹配演算法最壞情況下需比較字元的總次數為（n-m+1）m。n為主串長，m為子串長。
即（10-2+1）*2=18
4、如果目標串一共有10個字元，模式串共有2個字元，問，當匹配成功的時候，最多比較了多少個字元？舉例說明。
答：串匹配演算法最壞情況下需比較字元的總次數為（n-m+1）m。n為主串長，m為子串長。
即（10-2+1）*2=18
資料結構練習
華東理工大學網路學院 資料結構 ch1緒論和ch2線性表 班級學號姓名成績 一 名詞解釋 每小題2分，共10分 1.資料結構 2.線性結構 3.儲存結構 4.邏輯結構 5.非線性結構 答 1.資料結構 指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容 資料的邏輯結構 儲存結構和資料...
資料結構練習二
一 選擇 1 用單鏈表方式儲存的線性表,儲存每個結點需要兩個域,乙個是資料域,另乙個是 b a.當前結點所在位址域.b.指標域.c.空指標域.d.空閒域.2 在具有n個結點的單鏈表中,實現 a 的操作,其演算法的時間複雜度是o n a.遍歷鍊錶和求鍊錶的第i個結點.b.在位址為p的結點之後插入乙個結...
資料結構練習卷
華北科技學院 一 選擇題 每題2 分，共 10 題，總計 20 分 1 下列資料中是非線性資料結構。a 棧 b.佇列 c.完全二叉樹 d.陣列 2 乙個棧的輸入序列為123 n，若輸出序列的第乙個元素是n，輸出第i 1 i n 個元素是 a.不確定b.n i 1c.id.n i 3 下面關於線性表的...