數(shù)據(jù)結(jié)構(gòu)與算法試卷

安陽工學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程試卷學(xué)年第二學(xué)期安陽工學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程試卷學(xué)年第二學(xué)期___________系_______________專業(yè)_____________班級姓名________學(xué)號________________座號：__密封線內(nèi)不要答題———————————密———————————————封———————————————線————————————題號一二三四總分得分閱卷人注：請將所在的院（系）、專業(yè)、班級、姓名和學(xué)號寫在密封線內(nèi)，不要寫在其它地方注：請將所在的院（系）、專業(yè)、班級、姓名和學(xué)號寫在密封線內(nèi)，不要寫在其它地方得分一、填空題（每空2分，共12分）1.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的__數(shù)據(jù)元素之間的關(guān)系______有限集合。2.向一個長度為n的線性表中刪除第i個元素(1≤i≤n)時，需向前移動___n-i_____個元素。3.假設(shè)以S和X代表進(jìn)棧和出棧操作，則對輸入序列a,b,c,d,e進(jìn)行一系列操作SSXSXSSXXX之后，得到的輸出序列為___bceda_____。4.已知循環(huán)隊列的存儲空間為數(shù)組A[21]，front指向隊頭元素的前一個位置，rear指向隊尾元素，假設(shè)front和rear的值分別為8和3，則該隊列的長度為___16_____。5.在有序表A[0…17]中，采用折半查找法查找關(guān)鍵字等于A[7]的元素，需比較元素的下標(biāo)依次為83567。6.在堆排序、快速排序和歸并排序方法中，穩(wěn)定的排序方法是歸并排序。得分二、單項選擇題（每小題2分，共40分）1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（C）結(jié)構(gòu)。A.存儲B.物理C.邏輯D.物理和存儲2.算法分析的兩個主要方面是（A）A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性3.在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是（A）A.訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）B.在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）C.刪除第i個結(jié)點（1≤i≤n）D.將n個結(jié)點從小到大排序4．線性表Ｌ在（B）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。A.需經(jīng)常修改Ｌ中的結(jié)點值B.需不斷對Ｌ進(jìn)行刪除插入C.Ｌ中含有大量的結(jié)點D.Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜5.經(jīng)過以下棧運(yùn)算后，x的值是（A）InitStack(s);Push(s,'a');Push(s,'b');Pop(s,x);GetTop(s,x);A.aB.bC.1D.06.循環(huán)隊列存儲在數(shù)組A[0…m]中，則入隊時的操作為（D）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)7.按（B）遍歷二叉排序樹得到的序列是一個有序序列。A.先序B.中序C.后序D.層次8.下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）（B）.A．深度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑9.在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時通常設(shè)置一個打印緩沖區(qū)，該緩沖區(qū)應(yīng)該是一個（B）結(jié)構(gòu)。A.棧B.隊列C.數(shù)組D.線性表10．已知關(guān)鍵碼序列{78,19,63,30,89,84,55,69,28,83}采用基數(shù)排序，第一趟排序后的關(guān)鍵碼序列為（B）。A.{19,28,30,55,63,69,78,83,84,89}B.{30,63,83,84,55,28,78,19,69,89}C.{30,63,83,84,55,78,28,19,89,69}D.以上都不正確。11.無向圖G=（V,E），其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點序列正確的是(D).A.abecdfB.acfebdC.aebcfdD.aedfcb12.在一個單鏈表中，已知p結(jié)點，若在p后插入s結(jié)點，則須執(zhí)行（A）A．s->next=p->next;p->next=sB．p->next=s;s->next=pC．p->next=s->next;s->next=pD．s->next=p;p->next=s->next13.一個無向連通圖有5個頂點8條邊，則生成樹將要去掉（B）條邊。A.3B.4C.5D.614.設(shè)一棵二叉樹共有50個葉子結(jié)點，則共有（B）個度為2的結(jié)點。A.25B.49C.50D.5115.對數(shù)據(jù)序列{15,9,7,8,20,-1,7,4}，用堆排序的篩選法建立的初始小頂堆為（C）。A.{-1,4,8,9,20,7,15,7}B.{-1,7,15,7,4,8,20,9}C.{-1,4,7,8,20,15,7,9}D.以上都不對16.設(shè)數(shù)組a[0…59,0…69]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為（A）。A.9072B.6644C.8950D.650217.在下圖所示的平衡二叉樹中，插入關(guān)鍵字48后得到一棵新平衡二叉樹。在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左右子結(jié)點中保存的關(guān)鍵字分別是（C）A.1348B.2448C.2453D.249018.有向圖用鄰接矩陣存儲，其第i列的所有元素之和等于頂點i的(B)。A.度B.入度C.出度D.以上答案都不對19.建立線索二叉樹的目的是（A）A.方便查找某結(jié)點的前驅(qū)或后繼B.方便二叉樹的插入和刪除操作C．方便查找某結(jié)點的雙親D.使二叉樹的遍歷結(jié)果唯一20.如右圖所示二叉樹是由森林T1轉(zhuǎn)換而來的二叉樹，則森林T1中有（D）個度為0的結(jié)點。A.4B.5C.6D.7得分三、簡答題（每小題4分，共8分）1、簡要描述prim算法。2簡述拓?fù)渑判蛩惴?。得分四、?yīng)用題（每小題8分，共40分）1、假定用于通信的電文由8個字母A,B,C,D,E,F,G,H組成，各字母在電文中出現(xiàn)的頻率為：5，25，4，7，9，12，30，8，試畫出哈夫曼樹并為這8個字母設(shè)計哈夫曼編碼。2已知某完全二叉樹采用順序存儲，結(jié)點數(shù)據(jù)信息的存放順序是ABCDEFGH,畫出該完全二叉樹，并寫出對該二叉樹進(jìn)行先序遍歷、中序遍歷及后序遍歷得到的結(jié)點序列。3、以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速排序算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。4.設(shè)給定關(guān)鍵字輸入序列為（100，90，120，