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]）；
資料結構C語言版部分習題及答案
第二章習題與解答 一判斷題 1 線性表的邏輯順序與儲存順序總是一致的。2 順序儲存的線性表可以按序號隨機訪問。3 順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。4 線性表中的元素可以是各種各樣的，但同一線性表中的資料元素具有相同的特性，因此是屬於同一資料物...
資料結構C語言版部分習題及答案
第二章習題與解答 一判斷題 1 線性表的邏輯順序與儲存順序總是一致的。2 順序儲存的線性表可以按序號隨機訪問。3 順序表的插入和刪除操作不需要付出很大的時間代價，因為每次操作平均只有近一半的元素需要移動。4 線性表中的元素可以是各種各樣的，但同一線性表中的資料元素具有相同的特性，因此是屬於同一資料物...
資料結構 C語言版
考試大綱將陸續公布 計算機應用基礎考試大綱 主要考查計算機應用基礎知識，參考參考用書課後練習內容。其它同型別的計算機應用基礎教材均可作為複習用書 高等數學考試大綱 一 函式 二 極限 1 數列極限的概念 2 數列極限的性質 3 函式極限的概念 4 函式極限的定理 5 無窮小量和無窮大量 6 兩個重要...