數據結構期末綜合練習四（算法分析題）

本文格式為Word版，下載可任意編輯——數據結構期末綜合練習四（算法分析題）數據結構（本科）期末綜合練習四（算法分析題）

1.指出算法的功能并求出其時間繁雜度。intfun(intn)

{inti=1,s=1;

while(s

voidunknown(TA[],intn){

intfree=0;

for(inti=0;i#include“SeqList.h〞

template

voidunknown(SeqListexit(1);}inti=0;

Ttemp=L.First();

{

while(i=selse{temp=L.Next();i++;}}

算法執(zhí)行后順序表中的數據：

算法執(zhí)行后順序表的長度：

5.設字符串String具有以下操作：intLength()const;//計算字符串的長度

chargetData(k);//提取字符串第k個字符的值若字符串Tar的值為“ababcabcacbab〞，Pat的值為“abcac〞時，給出算法執(zhí)行后函數返回的結果。

#include“String.h〞

intunknown(String

while(jlink;while(p){

if(pp=p->link;}else{

q->link=___(2)___;delete(p);p=___(3)___;}

}//while

}//purge_linkst

(1)(2)(3)

7.設單鏈表的存儲結構為ListNode=(data,link)，表頭指針為LH，所存線性表L=(?a?,?b?,?c?,?d?,?e?,?f?,?g?)，若執(zhí)行unknown(LH)調用下面程序，則寫出執(zhí)行終止后的輸出結果。voidunknown（LinkNode*Ha）{//Ha為指向單鏈表的頭指針if(Ha){

unknown(Ha->link);coutdata;}}

8.設單鏈表結點的結構為LNode=(data,link)，閱讀下面的函數，指出它所實現(xiàn)的功能。intAA(LNode*Ha)

{//Ha為指向帶表頭附加結點的單鏈表的表頭指針intn=0;

LNode*p=Ha->link;while(p){n++;

p=p->link;}

return(n);

3

}

算法功能：

9.設單鏈表結點的結構為ListNode=(data,link)，下面程序段執(zhí)行后將生成由L所指向的帶頭結點的單鏈表，給出該單鏈表所對應的線性表。ListNode*L=newListNode;

ListNode*p=L;

for(inti=0;ilink=newListNode;p=p->link;

p->data=i*2-1;

}//for

p->link=NULL;

10.這是一個統(tǒng)計單鏈表中結點的值等于給定值x的結點數的算法，其中有兩行錯誤，請指出錯誤行的行號并改正。

intcount(ListNode*Ha,ElemTypex)①

{//Ha為不帶頭結點的單鏈表的頭指針

intn=0;②

while(Ha!=NULL){③

Ha=Ha->link;④if(Ha->data==x)n++;⑤}//while

returnn;⑥

}//count

錯誤語句號:修改如下:

11.寫出以下程序段的輸出結果:voidmain(){

stackS;

charx,y;

S.InitStack();x='c';y='