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

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