數(shù)據(jù)結(jié)構(gòu)中期考試(試題) 電子科技大學(xué).doc

系別 班次 學(xué)號(hào) 姓名 .密封線以內(nèi)答題無效電子科技大學(xué)成都學(xué)院二零零八至二零零九學(xué)年第一學(xué)期 數(shù)據(jù)結(jié)構(gòu) 課堂測(cè)試（60分鐘） 閉卷 考試時(shí)間：題號(hào)一二三總分評(píng)卷教師分?jǐn)?shù)一填空題（每空2分，共40分）；1. 數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和_兩種方法衡量其效率。2. 下面程序段的時(shí)間復(fù)雜度為_。(n1) for(i = 1; i = n; i+)for(j = 1; j = i; j+) x = x + 1; 3. 靜態(tài)鏈表中指針表示的是_。4. 線型表、棧和隊(duì)列都是_結(jié)構(gòu)，可以在線型表的_位置插入和刪除元素；對(duì)于棧只能在_插入和刪除元素；對(duì)于隊(duì)列只能在_插入元素和_刪除元素。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_個(gè)元素。6. 在一個(gè)長(zhǎng)度為n 的順序表中第i 個(gè)元素（1=inext=NULL Chead- next=head Dhead!=NULL13. 15.在雙向鏈表指針p 的結(jié)點(diǎn)前插入一個(gè)指針q 的結(jié)點(diǎn)操作是（ ）。A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;14. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_個(gè)結(jié)點(diǎn)。AnBn/2C(n1)/2D(n+1)/215. 設(shè)串s1=ABCDEFG,s2=PQRST,函數(shù)con(x,y)返回x和y串的連接串，subs（s,i,j）返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的字串， len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,len(s2), subs(s1,len(s2),2)的結(jié)果串是A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF三綜合題（每題6分，共30分）1. 線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五個(gè)元素的線性表L=23，17，47，05，31，若它以單鏈表方式存儲(chǔ)在下列100119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié),由大寫字母表示）組成，如下所示：其中指針p，q，r，s，t的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？(共6分)答：p= q = r = s= t= 首址= 末址= 2. 如果想將輸入的一個(gè)字符序列逆序輸出，如輸入“abcdef ”，輸出“fedcba”，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出的可能性？ (共6分)3. 寫出刪除順序表中第i個(gè)元素的算法：(共6分)Status ListDelete_sq(SqList &L, int i, ElemType &e)4. 寫出順序棧的入棧算法(共6分)Status Push(SqStack &S, SelemType e)5.