5．選擇題：ccbdca
6．試分析下面各程式段的時間複雜度。
（1）o（1）
（2）o（m*n）
（3）o（n2）
（4）o（log3n）
（5）因為x++共執行了n-1+n-2+……＋1= n(n-1)/2，所以執行時間為o（n2）
（6）o()
1．選擇題
babadbcabdcddac
2．演算法設計題
（6）設計乙個演算法，通過一趟遍歷在單鏈表中確定值最大的結點。
elemtype max (linklist l )
return pmax->data;
（7）設計乙個演算法，通過遍歷一趟，將鍊錶中所有結點的鏈結方向逆轉，仍利用原表的儲存空間。
void inverse(linklist &l)
}（10）已知長度為n的線性表a採用順序儲存結構，請寫一時間複雜度為o(n)、空間複雜度為o(1)的演算法，該演算法刪除線性表中所有值為item的資料元素。
[題目分析] 在順序儲存的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除線性表中所有值為item的資料元素，並未要求元素間的相對位置不變。因此可以考慮設頭尾兩個指標（i=1，j=n），從兩端向中間移動，凡遇到值item的資料元素時，直接將右端元素左移至值為item的資料元素位置。
void delete（elemtype a[ ]，int n）
∥a是有n個元素的一維陣列，本演算法刪除a中所有值為item的元素。
[演算法討論] 因元素只掃瞄一趟，演算法時間複雜度為o（n）。刪除元素未使用其它輔助空間，最後線性表中的元素個數是j。
1．選擇題
ccdaadabcdddbcb
2.演算法設計題
（2）回文是指正讀反讀均相同的字串行，如「abba」和「abdba」均是回文，但「good」不是回文。試寫乙個演算法判定給定的字元向量是否為回文。(提示：將一半字元入棧)
根據提示，演算法可設計為：
//以下為順序棧的儲存結構定義
#define stacksize 100 //假定預分配的棧空間最多為100個元素
typedef char datatype;//假定棧元素的資料型別為字元
typedef structseqstack;
int ishuiwen( char *t)
void enqueue ( type & item );
type dequeue ( );
type getfront ( );
void makeempty ( ) //判佇列空否
int isfull ( ) const //判佇列滿否
private:
int rear, front, tag隊尾指標、隊頭指標和隊滿標誌
type *q存放佇列元素的陣列
int m佇列最大可容納元素個數
}建構函式
template
queue:: queue ( int sz ) : rear (0), front (0), tag(0), m (sz)
插入函式
template
void queue :: enqueue ( type &item )
刪除函式
template
type queue :: dequeue ( )
讀取隊頭元素函式
template
type queue :: getfront ( )
1．選擇題
bbcabbbcbbabdcbc
2.綜合應用題
（1）已知模式串t=『abcaabbabcab』寫出用kmp法求得的每個字元對應的next和nextval函式值。
模式串t的next和nextval值如下：
（3）陣列a中，每個元素a[i,j]的長度均為32個二進位,行下標從-1到9，列下標從1到11，從首位址s開始連續存放主儲存器中，主儲存器字長為16位。求：
存放該陣列所需多少單元？
存放陣列第4列所有元素至少需多少單元？
陣列按行存放時，元素a[7,4]的起始位址是多少？
陣列按列存放時，元素a[4,7]的起始位址是多少？
每個元素32個二進位制位，主存字長16位，故每個元素佔2個字長，行下標可平移至1到11。
（1）242 （2）22 （3）s+182 （4）s+142
(4)請將香蕉banana用工具 h( )—head( )，t( )—tail( )從l中取出。
l=(apple,(orange,(strawberry,(banana)),peach),pear)
h（h（t（h（t（h（t（l）））））））
（5）寫乙個演算法統計在輸入字串中各個不同字元出現的頻度並將結果存入檔案（字串中的合法字元為a-z這26個字母和0-9這10個數字）。
void count（）
//統計輸入字串中數字字元和字母字元的個數。
｛int i，num[36]；
char ch；
for（i＝0；i<36；i++）num[i]＝０；// 初始化
while（（ch＝getchar表示輸入字串結束。
if（『0』<=ch<=『9』）｛i=ch－48;num[i數字字元
else if（『a』<=ch<=『z』）｛i=ch-65+10;num[i]++；｝// 字母字元
for（i=0；i<10；i++） // 輸出數字字元的個數
printf（「數字％d的個數＝％d\n」，i，num[i]）；
for（i＝10；i<36；i++）// 求出字母字元的個數
printf（「字母字元％c的個數＝％d\n」，i＋55，num[i]）；
資料結構課後習題答案
1.填空 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。解答 資料元素 是資料的最小單位，是討論資料結構時涉及的最小資料單位。解答 資料項，資料元素 分析 資料結構指的是資料元素以及資料元素之間的關係。從邏輯關係上講，資料結構主要分為和 解答 集合，線性結構，樹結構，圖結構 資料的儲...
資料結構課後習題答案總結
第一章第1章作業 1.1,1.2,1.6 1 3 1.8 1.1 簡述下列概念 資料 資料元素 資料型別 資料結構 邏輯結構 儲存結構 線性結構 非線性結構。資料 指能夠被計算機識別 儲存和加工處理的資訊載體。資料元素 就是資料的基本單位，在某些情況下，資料元素也稱為元素 結點 頂點 記錄。資料元素...
資料結構課後習題
1.1 簡述資料與資料元素的關係與區別 資料元素 data element 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。有時，乙個資料元素可由若干個資料項組成 1.2 資料結構和資料型別有什麼區別 資料結構是指計算機處理的資料元素的組織形式和相互關係，而資料型別是某種程式語言已實現...