課后總練習(xí)題

1、一、選擇題1組成數(shù)據(jù)的基本單位是( c )。 (A)數(shù)據(jù)項(xiàng) (B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素 (D)數(shù)據(jù)變量2數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的( c )以及它們之間的相互關(guān)系。(A)理想結(jié)構(gòu)，物理結(jié)構(gòu) (B)理想結(jié)構(gòu)，抽象結(jié)構(gòu)(c)物理結(jié)構(gòu)，邏輯結(jié)構(gòu) (D)抽象結(jié)構(gòu)，邏輯結(jié)構(gòu)3下列程序的時(shí)間復(fù)雜度為( A )for(i=0;im;i+)for(j=0;jt;j+) cij=0;for(i=0;im;i+)for(j=0;jt;j+)for(k=0;knext=s; s-prior=p; p-next-prior=s; s-next=p-next; (B) s-prior=p; s-next=p-next;

2、p-next=s; p-next-prior=s; (C) p-next=s; p-next-prior=s; s-prior=p; s-next=p-next; (D) s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 6已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，需( D )次比較可查找成功。 (A)1 (B)2 (C)3 (D)47在順序存儲(chǔ)的線性表R029上進(jìn)行順序查找的平均查找長(zhǎng)度為()，進(jìn)行二分查找的平均查找長(zhǎng)度為()，講行分塊查找（設(shè)分為5塊)的平均查找

3、長(zhǎng)度為() (A)15 (B)155 (C)16 (D)20 (A)4 (B)6215 (C)6415 (D)256 (A)6 (B)11 (C)5 (D)658若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)元素的值，則采用( B )存儲(chǔ)方式最節(jié)省時(shí)間。 (A)單鏈表 (B)雙向鏈表 (C)單循環(huán)鏈表 (D)順序表二、填空題1循環(huán)鏈表的主要優(yōu)點(diǎn)是_表的處理方便_。2在雙向循環(huán)鏈表中，在指針p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為_ f-prior=p; f-next=p-next; p-next=f; p-next-prior=f_s-prior=p; s-next=p-next; p-n

4、ext=s; p-next-prior=s; _3雙向循環(huán)鏈表的主要優(yōu)點(diǎn)是_克服單鏈表的單向性_。4在雙向循環(huán)表中，在p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn)，其操作為_f-prior_p;f一nextp一next;_ p-next-prior f;p一nextf。_5若要在一個(gè)單鏈表的*p結(jié)點(diǎn)之前插入一個(gè)*s結(jié)點(diǎn)時(shí)，可執(zhí)行下列操作s-next=_p-next_； p-next=s；t=p-data；p-data=_ s-data _；s-data=_t _。6假定對(duì)線性表R059進(jìn)行分塊查找，共分10塊，每塊長(zhǎng)度等于6。若假定查找索引表和塊均用順序查找法，則查找每一個(gè)元素的平均查找時(shí)間為_。7在

5、一個(gè)長(zhǎng)度為n的順序表中插入一個(gè)元素，最少需要移動(dòng)_0_個(gè)元素，最多需要移動(dòng)_n_個(gè)元素。8如果某線性表的每一個(gè)元素都沒(méi)有后繼元素，則其長(zhǎng)度最多是_1_。9設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(假設(shè)存在), 則需要修改指針的操作為_p-next=p-next-next_。三、判斷題1具有線性序關(guān)系的集合中，若a，b是集合中的任意兩個(gè)元素，則必有ab的關(guān)系。(錯(cuò))2在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從首結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。(錯(cuò) )3如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)，則必為線性表。（錯(cuò) ）4一個(gè)有序的單鏈表不能采用折半查找法進(jìn)行查找。(錯(cuò))

6、 5線性表的惟一存儲(chǔ)形式就是鏈表。( 錯(cuò) )四、讀程序填空1以下函數(shù)ins的功能是在順序表a中找到第一個(gè)值為x的元素，然后在該元素之前插入一個(gè)值為y的元素。如果找不到值為x的元素，則新元素成為順序表的最后一個(gè)元素。插入成功返回1，否則返回0。完成以下程序。(8分)typedef struct int elem100; int length;SQ; int ins(SQ *a, int x, int y) int k,i; if( _a=NULL_ ) return 0; for(k=0; klength; k+) if(a-elemk=x) break; if(k=a-length) k-;

7、else for(i=a-length-1; ik; i-) _a-elemi+1=a-elemi_ ; _a-elemk_ =y; return 1; 2在單鏈表(表首指針為head)的元素中找出最后一個(gè)值為e的元素，返回其指針；如果找不到，返回NULL。完成以下程序。(6分)Typedef struct LinkNode int data; Struct LinkNode *next;Node;Node *search_link(Node *head, int e)Node *p, *q;q=_head_ ;for(p=head; _p-next!=NULL_ ; p=p-next) if

8、(p-data=e) _q=p_;return q;3已知單鏈表的表首指針為head，下面的函數(shù)delete是從單鏈表中刪除指針為p的結(jié)點(diǎn)，并返回新的表首指針。請(qǐng)完成如下程序。(4分)typedef struct LinkNodeint data;struct LinkNode *next;Node;Node *delete(Node *head, Node *p)Node *pf;if(head=p) head=_head-next_; free(p);else for(pf=head; pf-next!=p; pf=pf-next); _p_ = p-next; free(p);retur

9、n head;4以下算法是將線性表L中所有負(fù)數(shù)元素刪除，返回被刪除的元素個(gè)數(shù)。完成以下算法。(7分)typedef struct int elem100; int length;SQ;int deln(SQ *L)* 算法思路是，對(duì)每個(gè)元素做以下循環(huán)，如果第i個(gè)元素大于等于0，且前面有c個(gè)小于0的元素，則將它前移c個(gè)位置*int i，c; * c將記錄小于0的元素個(gè)數(shù) *for(i=0,c=0; ilength; i+) if(_SQ-elemi_0) x-ei - _c_=x-ei; x-length=_x-length-c_;return c;5以下算法將元素遞增排列的順序存儲(chǔ)線性表A和B

10、的元素的交集存人線性表C中。在空格處填上合適的語(yǔ)句或表達(dá)式完成該算法。(每空2分)void SqList_Intersect(SqList A, SqList B, SqList &C int i=1,j=1,k=0; * 下標(biāo)初始化，A、B、C的下標(biāo)都從1開始 */ while(i=A.num & j=B.num) * A、B表均末到表尾 */ if(A.elemiB.elemj_) j+;if(A.elemi=B.elemj) * 當(dāng)發(fā)現(xiàn)了一個(gè)在A和B中都存在的元素 * C.elem_k+_=A.elemi; /* 添加到C中 */ i+; j+; /* while */C.num=k;

11、/* C表長(zhǎng)度置位 */ /* SqList_Intersect */6已知一個(gè)單鏈表的表首指針為h，每個(gè)結(jié)點(diǎn)含元素值data和下一結(jié)點(diǎn)的地址next。鏈表一共有5個(gè)結(jié)點(diǎn)，其元素值分別為100，200，300，400，500，經(jīng)過(guò)下列語(yǔ)句后，輸出什么結(jié)果?(3分) for(p=h; p-datanext); p-next=p-next-next; printf(%d, p-data);答案：300五、簡(jiǎn)答題1排序(1)寫出線性表(26，45，12，z0，30，5，15，29，16，2，18)采用基數(shù)排序后，第一趟結(jié)束時(shí)的結(jié)果。(4分)(2)線性表采用簡(jiǎn)單選擇排序算法對(duì)線性表(26，15，12，

12、16，5，30)進(jìn)行排序，進(jìn)行交換的第一對(duì)元素是哪兩個(gè)元素，在什么情況下，第一趟不需要進(jìn)行元素的交換?(6分) 2線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)述各自的優(yōu)缺點(diǎn)。（4分）l 順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：以數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示順序表中數(shù)據(jù)元素之間的邏輯關(guān)系，能隨機(jī)存取順序表中任一數(shù)據(jù)元素。但它也使得插入和刪除操作需移動(dòng)大量的數(shù)據(jù)元素。由于順序表需要一組地址連續(xù)的存儲(chǔ)單元，對(duì)于長(zhǎng)度可變的線性表就需要預(yù)分配足夠的空間，有可能使一部分存儲(chǔ)空間長(zhǎng)期閑置不能充分利用。也可能由于估計(jì)不足，當(dāng)表長(zhǎng)超過(guò)預(yù)分配的空間而造成溢出，在這種情況下，又難于擴(kuò)充連續(xù)的存儲(chǔ)空間。l 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)

13、是用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。不可以隨機(jī)存取表中的任一結(jié)點(diǎn)六、編程題1設(shè)a(a1，a2，am)和b(b1,b2，bn)是兩個(gè)循環(huán)鏈表寫出將這兩個(gè)表合并為循環(huán)鏈表c的算法。(15分) (a1，b1，a2，b2，am，bm，bm+1，bn) mnc= (a1，b1，a2，b2，an，bn，an+1，am) mn2已知一個(gè)單鏈表中每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)，并且其結(jié)點(diǎn)數(shù)不少于2。試編出算法以判斷該鏈表中從第二項(xiàng)起的每個(gè)元素值是否等于其序號(hào)的平方減去其前驅(qū)結(jié)點(diǎn)的

14、值，若滿足，返回True，否則返回False。(10分)答案：Bool LinkList_H(LinkList &H)p=H-next;j=2;q=p-next;p=p-next;while(p-next!=NULL&(p-next-data!=j*j-q-data)q=p-next;p=p-next;j+;If(p-next=NULL)return False;If(p-next-data=j*j-q-data)return True 3某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)單鏈表存于計(jì)算機(jī)中，鏈表的每個(gè)結(jié)點(diǎn)指出同樣價(jià)格的若干臺(tái)，現(xiàn)在又新到m臺(tái)價(jià)格為n元的電視機(jī)入庫(kù)，試

15、編寫倉(cāng)庫(kù)電視機(jī)鏈表增加電視機(jī)的算法。答案：LinkList LinkList_H(LinkList &H,int m,int n)p=H-next;while(p-next!=NULL)if(p-price!=n)p=p-next;p-data+=m;p=p-next;return H;4有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，編寫在值為x的結(jié)點(diǎn)之后插入m個(gè)結(jié)點(diǎn)的算法。(10 分)答案：LinkList LinkList_H(LinkList &H,int m,elemtype x)p=H-next;while(p-next!=NULL)if(p-data!=x)p=p-next;q=p;for(int i=

16、0;inext=q-next;q-next=s;q=p-next;free(q);return H;5我們用鏈表來(lái)存儲(chǔ)多項(xiàng)式, 其中, ,試編寫求微商的算法。（注，） 6已知線性表的元素按遞增順序排列，并以帶首結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。試編寫一個(gè)刪除表中所有值大于min且小于max的元素的算法。答案：LinkList LinkList_H(LinkLinst &H,int min,int max)p=H-next;whlie(p-datanext;q=p;whlie(p-datanext;q-next=p-next;p-next=q;free(q);return LinkList;7已知單鏈表

17、結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法判斷一個(gè)單鏈表中各結(jié)點(diǎn)的值是否由小到大排列。如果是(包括空表)，返回1，不是則返回0。(7分)Typedef struct LinkNode int data; Struct LinkNode *next;Node;答案：Typedef struct LinkNode int data; Struct LinkNode *next;Node;int LinkNode_H(Node H)p=H-next;whlie(p-next!=NULL& p-datanext-data)p=p-next;if(p-next=NULL)return 1;if(p-datap-next

18、-data)return 0;8已知順序表的數(shù)據(jù)結(jié)構(gòu)如下，編寫算法刪除順序表前面的10個(gè)元素。如果順序表中的元素少于10個(gè)，則刪完為止。(7分)typedef struct LinkNode int elem100; int length;SQ; 答案：typedef struct LinkNode int elem100; int length;SQ;LinkNode LinkNode_Delete(LinkNode &H)p=q=H-next;for(int i=0;inext!=NULL;i+)q=p-next-nxet;p=p-next;return H;9.已知單鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下

19、，編寫算法，刪除單鏈表的表首結(jié)點(diǎn)與表尾結(jié)點(diǎn)。 (7分)typedef struct LinkNodeint data;struct LinkNode *next;Node;答案：typedef struct LinkNodeint data;struct LinkNode *next;Node;LinkNode LinkNode_Delete(LinkNode &H)P=H-next;H-next=p-next;P=H-next;while(p-next!=NULL)q=p;p=p-next;q-next=NULL;return H;課后習(xí)題：選擇題：1、鏈表不具備的特點(diǎn)是 。 可隨機(jī)訪問(wèn)任一

20、節(jié)點(diǎn) 插入刪除不需要移動(dòng)元素 不必事先估計(jì)存儲(chǔ)空間 所需空間與其長(zhǎng)度成正比2、帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是 。 head=NULL head-next=NULL head-next=head head!=NULL3、如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用 存儲(chǔ)方式最節(jié)省時(shí)間。 單鏈表 雙向鏈表 單循環(huán)鏈表 順序表填空題:1、向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素（1in+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng) n-i+1 個(gè)元素。2、在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的 頭 結(jié)點(diǎn)。3、訪問(wèn)單鏈表中的結(jié)點(diǎn)，必須沿著 鏈域 進(jìn)行。4、在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)

21、點(diǎn)時(shí)，應(yīng)執(zhí)行 _s-next=p-next和 p-next=s的操作。編程題：1、建立帶表頭結(jié)點(diǎn)的單鏈表h；2、輸出單鏈表h中所有結(jié)點(diǎn)的數(shù)據(jù)域值；3、輸入x、y。在第1個(gè)數(shù)據(jù)域值為x的結(jié)點(diǎn)后插入y，若無(wú)這樣的結(jié)點(diǎn)x，則在表尾插入結(jié)點(diǎn)y；4、輸入k。刪除單鏈表中所有值為k的結(jié)點(diǎn)，并輸出被刪除結(jié)點(diǎn)個(gè)數(shù)。1. 解：void CreateList_H(LinkList &H,int n)H=( LinkList)malloc(sizeof(LNode);H-next=NULL;For(i=n;i0;i+)p=( LinkList)malloc(sizeof(LNode);scanf(&p-data);

22、p-next=H-next;H-next=p; /CreaterList_H2. 解：Status Listshuchu_H(LinkList &H)p=H;if(p-next=NULL)printf(“線性表為空”);return ERROR;elsewhile(p)printf(“%d”,p-data);p=p-next;return OK;3. 解：Status ListInsert_L(ListInsert &L,int x , ElemType y)p=L;if(p-next=NULL)printf(“線性表為空”);return ERROR;elsewhile(p&p-data!=

23、x)p=p-nexts=( LinkList)malloc(sizeof(LNode);s-data=y;s-next=p-next;4,解：Status ListDelete_L(ListInsert &L,int k, ElemType &e)p=L;m=0;if(p-next=NULL)printf(“線性表為空”);return ERROR;else if(p)while(p&p-data!=k)p=p-next;q=p-next;p-next=q-next;if(p)m=m+1;free(q);e=m;return OK;第3章 練習(xí)題一，選擇題：1設(shè)一數(shù)列的輸入順序?yàn)?，2，3，4

24、，5，6，通過(guò)棧操作不可能排成的輸出序列為( B ) (A)3，2，5，6，4，1 (B)l，5，4，6，2，3(C)2，4，3，5，1，6 (D)4，5，3，6，2，12設(shè)循環(huán)隊(duì)列Qln1的首尾指針為f和r，當(dāng)插入元素時(shí)尾指針r加1，首指針F總是指在隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素計(jì)數(shù)為( C )。 (A)r一f (B)n一(r一f) (C)(rf十n)n (D)(f一r十n)n3若有一個(gè)棧的輸入序列是l，2，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是( C )。 (A) n-i (B) n-i-1 (C) n-i+1 (D) 不確定4設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，

25、D，E，下列(C )是不可能的出棧序列 (A)A，B，C，D，E (B)B，C，D，E，A (C)E，A，B，C，D (D)E，D，C，B，A5隊(duì)列操作的原則是( A )。 (A)先進(jìn)先出 (B)后進(jìn)先出 (c)只能進(jìn)行插入 (D)只能進(jìn)行刪除二填空題：1對(duì)于一個(gè)以順序?qū)崿F(xiàn)的共享?xiàng)?n，棧頂指針?lè)謩e為top1和top2，top1由小到大，top2由大到小，其判斷下溢的條件是_top1n_。3對(duì)于一個(gè)以順序?qū)崿F(xiàn)的循環(huán)隊(duì)列Q0M-1，隊(duì)首、隊(duì)尾指針?lè)謩e為f和r，隊(duì)列判空的條件是 f=r.三判斷題：1不論adt棧是用數(shù)組實(shí)現(xiàn)，還是用指針實(shí)現(xiàn)，Pop(s)與Push(xs)的時(shí)間復(fù)雜度均(M)。 (

26、錯(cuò) )2進(jìn)棧操作push(x，s)作用子鏈接棧時(shí)，無(wú)需判滿。( 對(duì) )3進(jìn)棧操作時(shí)，必須判斷棧是否已滿。( 錯(cuò) )四程序填空：1己知STACK表示棧的數(shù)據(jù)結(jié)構(gòu)，push為將一個(gè)值為e的元素進(jìn)棧，若成功返回1，否則返回0。完成以下程序。(4分)Typedef struct int data100; int top; /* 棧頂元素的下標(biāo) */STACK;int push(STACK *s, int e)if(_top=100_) return 0;s-top+;_ s-top+_=e;return 1;五簡(jiǎn)答題：4何謂隊(duì)列的“假溢”現(xiàn)象？如何解決?(4分)l 當(dāng)front0,rear=M時(shí)，再有

27、元素入隊(duì)發(fā)生溢出假溢出l 解決方案隊(duì)頭位置固定。每次隊(duì)頭元素出隊(duì)，剩余元素向下移動(dòng)浪費(fèi)時(shí)間循環(huán)隊(duì)列。課后習(xí)題：一、單項(xiàng)選擇題1、棧的特點(diǎn)是 B ，隊(duì)列的特點(diǎn)是 A 。A）先進(jìn)先出 （B）先進(jìn)后出2、棧和隊(duì)列的共同特點(diǎn)是 C 。（A）都是先進(jìn)后出 （B）都是先進(jìn)先出 （C）只允許在端點(diǎn)處插入和刪除元素 （D）沒(méi)有共同點(diǎn)3、一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。（A）edcba （B）decba （C）dceab （D）abcde4、若已知一個(gè)棧的進(jìn)棧序列是p1，p2，p3， ，pn 。其輸出序列為1，2，3，n ，若p3=1，則p1為 C 。（A）可能是2（B）一

28、定是2（C）不可能是2 （D）不可能是35、設(shè)有一個(gè)空棧，棧頂指針為1000H（十六進(jìn)制，下同），現(xiàn)有輸入序列為1、2、3、4、5，經(jīng)過(guò)PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，輸出序列是 ，棧頂指針是 。5、4、3、2、1 2、1 2、3 3、4 1002H 1004H 1005H 1003H6、一個(gè)隊(duì)列的入隊(duì)序列是若1，2，3，4，則隊(duì)列的輸出序列是 B 。（A）4，3，2，1 （B）1，2，3，4（C）1，4，3，2 （D）3，2，4，17、若用一個(gè)大小為6的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元

29、素后，rear和front的值分別是 B 。（A）1和5 （B）2和4 （C）4和2 （D）5和1二、編程題 判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對(duì)。 提示：對(duì)表達(dá)式進(jìn)行掃描，凡遇到“（”就進(jìn)棧，遇到“）”就退掉棧頂?shù)摹埃ā?，表達(dá)式被掃描完畢，棧應(yīng)為空。Status matching() InitStack(OPTR); c=getchar( );int state=1;while(state)switch(c)case ”(”: Push(OPTR,e); c=getchar(); break;case ”)”: if( !StackEmpty(OPTR) & GetTop(OPTR)=”

30、(” ) Pop(OPTR,e) ;c=getchar();break; elsestate=0 break;if (StackEmpty(OPTR) & state) return OK; else return ERROR;第四章課后練習(xí)題一、選擇題1串的邏輯結(jié)構(gòu)與( D )的邏輯結(jié)構(gòu)不同。 (A)線性表 (B)棧 (C)隊(duì)列 (D)樹2串的長(zhǎng)度是(D )。 (A)串中不同字符的個(gè)數(shù) (B)串中不同字母的個(gè)數(shù) (C)串中所含字符的個(gè)數(shù)n(n0) (D)串中所含字符的個(gè)數(shù)n(n0)二、填空題1若字符串tababcab，前綴函數(shù)next5_三、判斷題如果一個(gè)串中的所有字符均在另一個(gè)串中出現(xiàn)，則

31、說(shuō)明前者是后者的子串。( 錯(cuò) )課后習(xí)題：一、選擇題 1、空串與空白串是相同的，這種說(shuō)法 B 。 （A）正確 （B）不正確 2、串是一種特殊的線性表，其特殊性體現(xiàn)在 D 。 （A）可以順序存儲(chǔ) （B）數(shù)據(jù)元素是一個(gè)字符 （C）可以鏈接存儲(chǔ) （D）數(shù)據(jù)元素可以是多個(gè)字符 3、 C 是C語(yǔ)言中”abcd321ABCD”的子串。 （A）abcd （B）321AB（C）”abcABC” (D)”21AB二、填空題 1、兩個(gè)串相等的充分必要條件是 兩個(gè)串的長(zhǎng)度相等，并且各對(duì)應(yīng)位置的字符都相等。 2、空串是 ，其長(zhǎng)度等于 0 。 3、空白串是 ，其長(zhǎng)度等于 1 。第5章 練習(xí)題一、選擇題1.個(gè)55的對(duì)稱矩

32、陣采用壓縮存儲(chǔ)，需要存儲(chǔ)( c)個(gè)元素。 (A)5 (B)10 (C)15 (D)202設(shè)有一個(gè)10階的對(duì)稱矩陣a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a00的存儲(chǔ)地址為100，每個(gè)元素占1個(gè)地址空間，則a32的地址為( D )。 (A)102 (B)105 (C)106 (D)108二、填空題1一個(gè)nn的對(duì)稱矩陣，如果以行或列為主序存人內(nèi)存，則其容量_n(n+1)/2 。2上三角矩陣壓縮存儲(chǔ)的下標(biāo)對(duì)應(yīng)關(guān)系k_i(i+1)/2+j_。三、程序填空1已知數(shù)組r有n個(gè)元素，并已經(jīng)由小到大排序。下面的函數(shù)serach的功能是采用折半查找法查找值為e的元素，并返回其下標(biāo)，如果找不到，返回-1。完成下面程

33、序。(4分)int search(elem r,int n,int e)int i1,i2,k;i1=0;i2=n-1;while(i1=i2) k=(i1+i2)/2; if(rk=e) _return k_; if(elchild=NULL_。4按_中序_遍歷二叉樹，可以得到按值遞增的關(guān)鍵碼序列，在下圖中所示的二叉樹中，檢索關(guān)鍵碼85的過(guò)程中，需與85進(jìn)行比較的關(guān)健碼序列為_。5設(shè)一棵二叉樹共用50個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，則它共有_49_個(gè)度為2的結(jié)點(diǎn)。6高度為h(0)的二叉樹，至少有_h_個(gè)結(jié)點(diǎn)，最多有_2h-1_個(gè)結(jié)點(diǎn)。7具有128個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_8_。8一顆Huffman

34、樹是由5個(gè)葉子結(jié)點(diǎn)形成的，該Huffman樹總共有_9_個(gè)結(jié)點(diǎn)。9二叉排序樹采用_中_序遍歷可以得到結(jié)點(diǎn)的有序序列。10如果指針p指向一棵二叉樹的一個(gè)結(jié)點(diǎn)，則判斷p沒(méi)有左孩子的邏輯表達(dá)式為_p-lchild=NULL_。11具有26個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_5_。12一棵深度為5的二叉樹，至少有_1_個(gè)葉子結(jié)點(diǎn), 只有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_6_。 13已知二叉樹中葉子數(shù)為50，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為_129_。三、判斷題1二叉排序樹的左、右子樹都是二叉排序樹。( 對(duì) )2先序遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問(wèn)序列不可能是鏈值遞增序列。( 錯(cuò) )3若有一個(gè)葉子結(jié)點(diǎn)是某

35、子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。( 對(duì) )4Huffman樹沒(méi)有度為1的結(jié)點(diǎn)。( 錯(cuò))5二叉排序樹中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。( 錯(cuò) )6二叉排序樹采用先序遍歷可以得到結(jié)點(diǎn)的有序序列。( 錯(cuò) )7對(duì)于二叉排序樹，根元素肯定是值最大的元素。( 錯(cuò) )8二叉樹的先序遍歷不可能與中序遍歷相同。( 錯(cuò) )9任何一棵二叉樹，不可能沒(méi)有葉子結(jié)點(diǎn)。( 錯(cuò) )10一棵二叉樹的中序遍歷序列與該二叉樹轉(zhuǎn)換成森林的后序遍歷序列相同。（ 錯(cuò) ）四、簡(jiǎn)答題1樹與二叉樹之間有何區(qū)別?(5分)解：二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說(shuō)明它是

36、左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。2一1設(shè)二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下：(4分)1234567891011121314151617181920EAFDHCGIB (1)根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫出二叉樹。 (2)寫出按先序、中序、后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。 (3)畫出二叉樹的后序線索化樹。解：(1)(2)先序節(jié)點(diǎn)序列：EADCBFHGI中序節(jié)點(diǎn)序列：ABCDEFGHI后序節(jié)點(diǎn)序列: BCDAGIHFE(3)3(1)給出下圖所示的二叉樹后序遍歷的結(jié)果。(5分)(2)如果下圖表示的是采用孩子兄弟法轉(zhuǎn)換后的一棵樹。試畫出原來(lái)的樹。(5分)（1）后序節(jié)點(diǎn)序列:DBGEFCA（2）4已知一棵二

37、叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，畫出這棵二叉樹。解： 5已知一棵二叉樹的中序遍歷結(jié)果為DBHEAFICG，先序遍歷結(jié)果為ABDEHCFIG，試畫出該二叉樹。 解： 6給出右圖所示二叉樹中序遍歷結(jié)果。(5分)解：DBAFGEC7(1)給出右圖所示樹的后序遍歷結(jié)果。(4分) (2)采用孩子-兄弟法將該樹轉(zhuǎn)換為一棵二叉樹。（5分）解：(1) 后序遍歷結(jié)果：BEFCDGA(2)8己知一棵樹的雙親表示存儲(chǔ)映像圖如下所示，試畫出該樹的邏輯示意圖解：9設(shè)下圖所示的二叉樹是由森林轉(zhuǎn)換而成的，試將它還原為森林。(5分)五、程序填空1下列算法是輸出一顆二叉樹的第i層的所有結(jié)點(diǎn)的值，假定根結(jié)點(diǎn)是第1層。(5分)Typedef struct LinkNode int data; Struct LinkNode *lchild, *rchild;Node;void o