2021年計算機(jī)軟件技術(shù)基礎(chǔ)試題庫

一、單項(xiàng)選取題一種算法應(yīng)當(dāng)是（）。A)程序 B)問題求解環(huán)節(jié)描述C)要滿足五個基本屬性 D)A和C算法指是（）。A)計算機(jī)程序 B)解決問題計算辦法C)排序算法 D)解決問題有限運(yùn)算序列。與數(shù)據(jù)元素自身形式、內(nèi)容、相對位置、個數(shù)無關(guān)是數(shù)據(jù)（）。A)存儲構(gòu)造 B)邏輯構(gòu)造 C)算法 D)操作從邏輯上可以把數(shù)據(jù)構(gòu)造分為（）兩大類。A)動態(tài)構(gòu)造、靜態(tài)構(gòu)造 B)順序構(gòu)造、鏈?zhǔn)綐?gòu)造C)線性構(gòu)造、非線性構(gòu)造 D)初等構(gòu)造、構(gòu)造型構(gòu)造下列論述中對的是()。A）一種邏輯數(shù)據(jù)構(gòu)造只能有一種存儲構(gòu)造B）數(shù)據(jù)邏輯構(gòu)造屬于線性構(gòu)造，存儲構(gòu)造屬于非線性構(gòu)造C）一種邏輯數(shù)據(jù)構(gòu)造可以有各種存儲構(gòu)造，且各種存儲構(gòu)造不影響數(shù)據(jù)解決效率D）一種邏輯數(shù)據(jù)構(gòu)造可以有各種存儲構(gòu)造，且各種存儲構(gòu)造影響數(shù)據(jù)解決效率數(shù)據(jù)基本單位是（） A)數(shù)據(jù)項(xiàng) B)數(shù)據(jù)類型 C)數(shù)據(jù)元素 D)數(shù)據(jù)變量下列程序時間復(fù)雜度為（）i=0；s=0；while（s<n）{i++；s=s+i；}A)O（） B)O（） C)O（n） D)O（n2）下列程序段漸進(jìn)時間復(fù)雜度為（）。for(inti=1;i<=n;i++)for(intj=1;j<=m；j++)A[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）(m+n)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++；其中n為正整數(shù)，則最后一行語句頻度在最壞狀況下是（）。A）O(n） B)O(nlogn) C)O(n3) D)O(n2)在下面程序段中，對x賦值語句頻度為（）。for(i=1；i>=n；i++)for(j=1；j>=n；j++)x:=x+1;A)O(2n) B)O(n) C)O(n2) D)O(log2n)程序段for(i:=n-1；i<=1；i--）for(j:=1；j>=i；j++)if(a[j]>a[j+1]){t=a[j]；a[j]=a[j+1]；a[j+1]=t；}其中n為正整數(shù)，則最后一行語句頻度在最壞狀況下是（）。A)O(n） B)O(nlogn) C)O(n3) D)O(n2)設(shè)有一種遞歸算法如下：intfact(intn){/*不不大于等于0*/if(n<=0)return1;elsereturnn*fact(n-1);}則計算fact(n)需要調(diào)用該函多次數(shù)為（）。A)n B)n+1 C)n+2 D)n-1下述程序段中語句①頻度是（）。s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)s+=j;A) B) C) D)若某線性表中最慣用操作是在最后一種元素之后插入一種元素和刪除第一種元素，則最節(jié)約運(yùn)算時間存儲方式是（）。A)單鏈表 B)僅有頭指針單循環(huán)鏈表C)雙鏈表 D)僅有尾指針單循環(huán)鏈表求循環(huán)鏈表中當(dāng)前結(jié)點(diǎn)后繼和前驅(qū)時間復(fù)雜度分別是（）。A)O(n)和O(1) B)O(1)和O(1) C)O(1)和O(n) D)O(n)和O(n)求單鏈表中當(dāng)前結(jié)點(diǎn)后繼和前驅(qū)時間復(fù)雜度分別是（）。 A)O（n）和O（1） B)O（1）和O（1） C)O（1）和O（n） D)O(n)和O（n）非空單循環(huán)鏈表頭指針為head,尾指針為rear，則下列條件成立是（）。 A)rear->next==head B)rear->next->next==head C)head->next==rear D)head->next->next==rear從一種長度為n順序表中刪除第i個元素（1≤i≤n）時，需向前移動元素個數(shù)是（）。A)n-i B)n-i+1 C)n-i-1 D)已知一種有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)二分檢索值為90元素時，檢索成功需比較次數(shù)是（）。A)1 B)2 C)3 D)假設(shè)以行優(yōu)先順序存儲三維數(shù)組R[6][9][6]，其中元素R[0][0][0]地址為2100，且每個元素占4個存儲單元，則存儲地址為2836元素是（）。A)R[3][3][3] B)R[3][3][4] C)R[4][3][5] D)R[4][3][4]設(shè)有一種10階對稱矩陣A，采用壓縮存儲方式以行序?yàn)橹餍虼鎯?，a00為第一種元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a45地址為（）。A)13 B)35 C)17 D)36線性表采用鏈?zhǔn)酱鎯r，節(jié)點(diǎn)存儲地址（）。A)必要是不持續(xù) B)持續(xù)與否均可C)必要是持續(xù) D)和頭節(jié)點(diǎn)存儲地址相持續(xù)用鏈表表達(dá)線性表長處是（）。A)便于隨機(jī)存取 B)耗費(fèi)存儲空間比順序表少C)數(shù)據(jù)元素物理順序與邏輯順序相似D)便于插入與刪除鏈表不具備特點(diǎn)是（）。A)插入、刪除不需要移動元素 B)可隨機(jī)訪問任一元素C)不必事先預(yù)計存儲空間 D)所需空間與線性長度成正比在長度為n順序表中刪除第i個元素(1≤i≤n)時，元素移動次數(shù)為()。A)n-i+1 B)i C)i+1 D)n-i采用順序搜索辦法查找長度為n順序表達(dá)，搜索成功平均搜索長度為（）。A)n B)n/2 C)(n-1)/2將長度為n單鏈表鏈接在長度為m單鏈表之后算法時間復(fù)雜度為（）。A)O(1) B)O(n) C)O(m) D)O(m+n)若不帶頭結(jié)點(diǎn)單鏈表頭指針為head，則該鏈表為空鑒定條件是()。A)head==NULL B)head->next==NULL C)head!=NULL D)head->next==head某線性表中最慣用操作是在最后一種元素之后插入一種元素和刪除第一種元素，則采用（）存儲方式最節(jié)約運(yùn)算時間。A)單鏈表 B)僅有頭指針單循環(huán)鏈表C)雙鏈表 D)僅有尾指針單循環(huán)鏈表若容許表達(dá)式內(nèi)各種括號混合嵌套，則為檢查表達(dá)式中括號與否對的配對算法，普通選用輔助構(gòu)造是（）。 A)棧 B)線性表 C)隊(duì)列 D)二叉排序樹順序棧S中top為棧頂指針，指向棧頂元素所在位置，elem為存儲棧數(shù)組，則元素e進(jìn)棧操作重要語句為（）。A)s.elem［top］=e； s.top=s.top+1； B)s.elem［top+1］=e；s.top=s.top+1；C)s.top=s.top+1； s.elem［top+1］=e； D)s.top=s.top+1；s.elem［top］=e；循環(huán)隊(duì)列sq中，用數(shù)組elem［0··25］存儲數(shù)據(jù)元素，sq.front批示隊(duì)頭元素前一種位置，sq.rear批示隊(duì)尾元素當(dāng)前位置，設(shè)當(dāng)前sq.front為20，sq.rear為12，則當(dāng)前隊(duì)列中元素個數(shù)為（）。A)8 B)16 C)17 D)18鏈?zhǔn)綏Ｅc順序棧相比，一種比較明顯長處是（）。A)插入操作更加以便 B)普通不會浮現(xiàn)棧滿狀況C)不會浮現(xiàn)?？諣顩r D)刪除操作更加以便一種遞歸定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)營時間來看，普通遞歸過程比非遞歸過程（）。A)較快 B)較慢 C)相似 D)不定若已知一種棧入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為（）。 A)i B)n==i C)n-i+1 D)不擬定一種棧入棧序列是a,b,c,d,e，則棧不也許輸出序列是()。A)edcba B)decba C)dceab D)abcde若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，則不也許浮現(xiàn)出棧序列是()。A)2，4，3，1，5，6 B)3，2，4，1，6，5C)4，3，2，1，5，6 D)2，3，5，1，6，4對于棧操作數(shù)據(jù)原則是（）。A)先進(jìn)先出 B)后進(jìn)先出 C)后進(jìn)后出 D)不分順序棧和隊(duì)列共同點(diǎn)是（）。A)都是先進(jìn)先出 B)都是先進(jìn)后出C)只容許在端點(diǎn)處插入和刪除元素 D)沒有共同點(diǎn)一種隊(duì)列入隊(duì)序列是1，2，3，4，則隊(duì)列輸出序列是（）。A)4,3,2,1 B)1,2,3,4 C)1,4,3,2 D)3,2,4,1設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出對操作后其頭指針front值為（）。A)front=front+1 B)front=(front+1)%(m-1)C)front=(front-1)%m D)front=(front+1)%m引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化操作是()。A)出隊(duì) B)入隊(duì) C)取隊(duì)頭元素 D)取隊(duì)尾元素設(shè)以數(shù)組A[m]存儲循環(huán)隊(duì)列元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中元素個數(shù)為（）。A）(rear-front+m)%mB）rear-front+1 C）(front-rear+m)%mD）二維數(shù)組A[12][18]采用列優(yōu)先存儲辦法，若每個元素各占3個存儲單元，且A[0][0]地址為150，則元素A[9][7]地址為()。A)429 B)432 C)435設(shè)有一種10階對稱矩陣A[10][10]，采用壓縮方式按行將矩陣中下三角某些元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中（）位置。A)32 B)33 C)41若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切卧?涉及主對角線上所有元素)依次存儲于一維數(shù)組B［1..(n(n+1))/2］中，則在B中擬定aij（i<j）位置k關(guān)系為()。A)i*(i-1)/2+j B)j*(j-1)/2+i C)i*(i+1)/2+j D)j*(j+1)/2+i對稀疏矩陣進(jìn)行壓縮存儲目是（）。A)便于進(jìn)行矩陣運(yùn)算 B)便于輸入和輸出C)節(jié)約存儲空間 D)減少運(yùn)算時間復(fù)雜度對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))成果是()。A)(e,f) B)((e,f)) C)(f) D)()設(shè)廣義表L=（（a,b,c）），則L長度和深度分別為（）。A)1和1 B)1和3 C)1和2 D)2和樹中所有結(jié)點(diǎn)度之和等于所有結(jié)點(diǎn)數(shù)加（）。A)0 B)1 C)-1 D)2在一棵具備n個結(jié)點(diǎn)二叉鏈表中，所有結(jié)點(diǎn)空域個數(shù)等于（）。A)n B)n-1 C)n+1 D)2*n某二叉樹先序序列和后序序列正好相反，則該二叉樹一定是（）二叉樹。A)空或只有一種結(jié)點(diǎn) B)高度等于其節(jié)點(diǎn)數(shù)C)任一結(jié)點(diǎn)無左孩子 D)任一結(jié)點(diǎn)無右孩子具有10個結(jié)點(diǎn)二叉樹中，度為0結(jié)點(diǎn)數(shù)為4，則度為2結(jié)點(diǎn)數(shù)為（）A)3 B)4 C)5 D)6除第一層外，滿二叉樹中每一層結(jié)點(diǎn)個數(shù)是上一層結(jié)點(diǎn)個數(shù)（）A)1/2倍 B)1倍 C)2倍 D)3倍對一棵有100個結(jié)點(diǎn)完全二叉樹按層編號，則編號為49結(jié)點(diǎn)，它父結(jié)點(diǎn)編號為（）A)24 B)25 C)98 D)99可以惟一地轉(zhuǎn)化成一棵普通樹二叉樹特點(diǎn)是（）A)根結(jié)點(diǎn)無左孩子 B)根結(jié)點(diǎn)無右孩子 C)根結(jié)點(diǎn)有兩個孩子 D)根結(jié)點(diǎn)沒有孩子設(shè)高度為h二叉樹上只有度為0和度為2結(jié)點(diǎn)，則此類二叉樹中所包括結(jié)點(diǎn)數(shù)至少為（）。A)2h B)2h-1 C)2h+1 D)h+1在一棵度為3樹中，度為3節(jié)點(diǎn)個數(shù)為2，度為2節(jié)點(diǎn)個數(shù)為1，則度為0節(jié)點(diǎn)個數(shù)為（）。 A)4 B)5 C)6 D)設(shè)森林F相應(yīng)二叉樹為B，它有m個結(jié)點(diǎn)，B根為p，p右子樹結(jié)點(diǎn)個數(shù)為n,森林F中第一棵 子樹結(jié)點(diǎn)個數(shù)是（）。A)m-n B)m-n-1 C)n+1 D)條件局限性，無法擬定將一株有100個節(jié)點(diǎn)完全二叉樹從上到下，從左到右依次進(jìn)行編號，根節(jié)點(diǎn)編號為1，則編號為49節(jié)點(diǎn)左孩子編號為（）。A)98 B)89 C)50 D)沒有孩子下列圖示順序存儲構(gòu)造表達(dá)二叉樹是(A)樹最適合用來表達(dá)（）。A)有序數(shù)據(jù)元素 B)無序數(shù)據(jù)元素 C)元素之間具備分支層次關(guān)系數(shù)據(jù) D)元素之間無聯(lián)系數(shù)據(jù)在一種非空二叉樹中序遍歷序列中，根結(jié)點(diǎn)右邊（）。 A)只有右子樹上所有結(jié)點(diǎn) B)只有右子樹上某些結(jié)點(diǎn)C)只有左子樹上某些結(jié)點(diǎn) D)只有左子樹上所有結(jié)點(diǎn)任何一棵二叉樹葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中相對順序（）。 A)不發(fā)生變化 B)發(fā)生變化 C)不能擬定 D)以上都不對深度優(yōu)先遍歷類似于二叉樹（）。A)先序遍歷 B)中序遍歷 C)后序遍歷 D)層次遍歷廣度優(yōu)先遍歷類似于二叉樹（）。A)先序遍歷 B)中序遍歷 C)后序遍歷 D)層次遍歷任何一種無向連通圖最小生成樹（）。A)只有一棵 B)一棵或多棵 C)一定有多棵 D)也許不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權(quán)之和或樹權(quán)最小狀況唯一）在分析折半查找性能時經(jīng)常加入失敗節(jié)點(diǎn)，即外節(jié)點(diǎn)，從而形成擴(kuò)充二叉樹。若設(shè)失敗節(jié)點(diǎn)i所在層次為Li，那么查找失敗到達(dá)失敗點(diǎn)時所做數(shù)據(jù)比較次數(shù)是（）。A)Li+1 B)Li+2 C)Li-1 D)Li向一種有127個元素原順序表中插入一種新元素并保存本來順序不變，平均要移動（）個元素。 A)8 B)63.5 C)63 D)7由同一組核心字集合構(gòu)造各棵二叉排序樹()。A)其形態(tài)不一定相似，但平均查找長度相似B)其形態(tài)不一定相似，平均查找長度也不一定相似C)其形態(tài)均相似，但平均查找長度不一定相似D)其形態(tài)均相似，平均查找長度也都相似衡量查找算法效率重要原則是（）。A)元素個數(shù) B)所需存儲量 C)平均查找長度D)算法難易限度適合對動態(tài)查找表進(jìn)行高效率查找組織構(gòu)造是（）。A)有序表 B)分塊有序表 C)二叉排序樹D)迅速排序能進(jìn)行二分查找線性表,必要以（）。A)順序方式存儲，且元素按核心字有序B)鏈?zhǔn)椒绞酱鎯?，且元素按核心字有序C)順序方式存儲，且元素按核心字分塊有序D)鏈?zhǔn)椒绞酱鎯?，且元素按核心字分塊有序?yàn)槭蛊骄檎议L度達(dá)到最小,當(dāng)由核心字集合{05,11,21,25,37,40,41,62,84}構(gòu)建二叉排序樹時,第一種插入核心字應(yīng)為（）A) 5 B)37 C)41 D)62對核心字序列(56,23,78,92,88,67,19,34)進(jìn)行增量為3一趟希爾排序成果為()。A)(19,23,56,34,78,67,88,92) B)23,56,78,66,88,92,19,34)C)(19,23,34,56,67,78,88,92) D)(19,23,67,56,34,78,92,88)用某種排序辦法對核心字序列{35,84,21,47,15,27,68,25,20}進(jìn)行排序時，序列變化狀況如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用辦法是（）。A)直接選取排序 B)希爾排序 C)堆排序 D)迅速排序一組記錄排序碼為(46,79,56,38,40,84)，則運(yùn)用迅速排序辦法，以第一種記錄為基準(zhǔn)得到第一次劃提成果為（）。 A)38,40,46,56,79,84 B)40,38,46,79,56,84 C)40,38,46,56,79,84 D)迅速排序在最壞狀況下時間復(fù)雜度是（）A)O(n2log2n) B)O(n2) C)O(nlog2n) D)O(log2n)下列排序算法中不穩(wěn)定是（）。A)直接選取排序 B)折半插入排序 C)冒泡排序 D)迅速排序?qū)Υ判蛟匦蛄羞M(jìn)行劃分，將其分為左、右兩個子序列，再對兩個子序列進(jìn)行同樣排序操作，直到子序列為空或只剩余一種元素為止。這樣排序辦法是（）。A)直接選取排序 B)直接插入排序 C)迅速排序 D)冒泡排序?qū)?個不同數(shù)據(jù)進(jìn)行排序，至多需要比較（）次。A)8B)9 C)10 D)25排序算法中，第一趟排序后，任一元素都不能擬定其最后位置算法是（）。A)選取排序 B)迅速排序 C)冒泡排序 D)插入排序排序算法中，不穩(wěn)定排序是（）。A)直接插入排序 B)冒泡排序 C)堆排序 D)選取排序排序辦法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中元素進(jìn)行比較，將其放入已排序序列對的位置上辦法，稱為（）.A)希爾排序 B)冒泡排序C)插入排序D)選取排序從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）一端辦法，稱為（）。A)希爾排序 B)歸并排序C)插入排序D)選取排序?qū)Γ顐€不同排序碼進(jìn)行冒泡排序，在下列哪種狀況下比較次數(shù)最多。（）A)從小到大排列好 B)從大到小排列好C)元素?zé)o序 D)元素基本有序?qū)Γ顐€不同排序碼進(jìn)行冒泡排序，在元素?zé)o序狀況下比較次數(shù)為（）。A)n+1B)n C)n-1 D)n(n-1)/2迅速排序在下列哪種狀況下最易發(fā)揮其長處。（）A)被排序數(shù)據(jù)中具有各種相似排序碼B)被排序數(shù)據(jù)已基本有序C)被排序數(shù)據(jù)完全無序D)被排序數(shù)據(jù)中最大值和最小值相差懸殊對有n個登記表作迅速排序，在最壞狀況下，算法時間復(fù)雜度是（）。A)O(n) B)O(n2) C)O(nlog2n) D)O(n3)若一組記錄排序碼為（46，79，56，38，40，84），則運(yùn)用迅速排序辦法，以第一種記錄為基準(zhǔn)得到一次劃提成果為（）。A)38，40，46，56，79，84B)40，38，46，79，56，84C)40，38，46，56，79，84 D)40，38，46，84，56，79下列核心字序列中，（）是堆。A)16，72，31，23，94，53 B)94，23，31，72，16，53C)16，53，23，94，31，72 D)16，23，53，31，94，72堆是一種（）排序。A)插入 B)選取 C)互換 D)歸并堆形狀是一棵（）。A)二叉排序樹B)滿二叉樹 C)完全二叉樹D)平衡二叉樹若一組記錄排序碼為（46，79，56，38，40，84），則運(yùn)用堆排序辦法建立初始堆為（）。A)79，46，56，38，40，84 B)84，79，56，38，40，46C)84，79，56，46，40，38 D)84，56，79，40，46，38下述幾種排序辦法中，規(guī)定內(nèi)存最大是（）。A)插入排序 B)迅速排序 C)歸并排序D)選取排序有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序篩選辦法建立初始堆為（）。A)-1，4，8，9，20，7，15，7 B)-1，7，15，7，4，8，20，9C)-1，4，7，8，20，15，7，9 D)A，B，C均不對。51．下列四個序列中，哪一種是堆（）。A)75,65,30,15,25,45,20,10 B)75,65,45,10,30,25,20,15C)75,45,65,30,15,25,20,10 D)75,45,65,10,25,30,20,15如下序列不是堆是()。A)(100,85,98,77,80,60,82,40,20,10,66) B)(100,98,85,82,80,77,66,60,40,20,10)C)(10,20,40,60,66,77,80,82,85,98,100) D)(100,85,40,77,80,60,66,98,82,10,20)迅速排序辦法在（）狀況下最不利于發(fā)揮其長處。A)要排序數(shù)據(jù)量太大 B)要排序數(shù)據(jù)中具有各種相似值C)要排序數(shù)據(jù)個數(shù)為奇數(shù) D)要排序數(shù)據(jù)已基本有序?qū)诵拇a序列28，16，32，12，60，2，5，72迅速排序，從小到大一次劃提成果為（）。A)(2,5,12,16)26(60,32,72) B)(5,16,2,12)28(60,32,72)C)(2,16,12,5)28(60,32,72) D)(5,16,2,12)28(32,60,72)對下列核心字序列用迅速排序法進(jìn)行排序時，速度最快情形是（）。A){21,25,5,17,9,23,30} B){25,23,30,17,21,5,9}C){21,9,17,30,25,23,5} D){5,9,17,21,23,25,30}二、填空題數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計算程序設(shè)計問題中計算機(jī)操作對象以及它們之間關(guān)系和運(yùn)算等學(xué)科。數(shù)據(jù)構(gòu)造被形式地定義為（D，R），其中D是數(shù)據(jù)元素有限集合，R是D上關(guān)系有限集合。數(shù)據(jù)構(gòu)造涉及數(shù)據(jù)邏輯構(gòu)造、數(shù)據(jù)存儲構(gòu)造和數(shù)據(jù)運(yùn)算這三個方面內(nèi)容。數(shù)據(jù)構(gòu)造按邏輯構(gòu)造可分為兩大類，它們分別是線性構(gòu)造和非線性構(gòu)造。線性構(gòu)造中元素之間存在一對一關(guān)系，樹形構(gòu)造中元素之間存在一對多關(guān)系，圖形構(gòu)造中元素之間存在多對多關(guān)系。在線性構(gòu)造中，第一種結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn)；最后一種結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，別的每個結(jié)點(diǎn)有且只有1個后續(xù)結(jié)點(diǎn)。在樹形構(gòu)造中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，別的每個結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，別的每個結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)數(shù)可以任意各種。在圖形構(gòu)造中，每個結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意各種。數(shù)據(jù)存儲構(gòu)造可用四種基本存儲辦法表達(dá)，它們分別是順序、鏈?zhǔn)?、索引和散列。?shù)據(jù)運(yùn)算最慣用有5種，它們分別是插入、刪除、修改、查找、排序。一種算法效率可分為時間效率和空間效率。對于給定n個元素,可以構(gòu)造出邏輯構(gòu)造有集合，線性表，樹，圖四種。順序映象特點(diǎn)是借助元素在存儲器中相對位置來表達(dá)數(shù)據(jù)元素之間邏輯關(guān)系。非順序映象特點(diǎn)是借助是批示元素存儲地址指針表達(dá)數(shù)據(jù)元素之間邏輯關(guān)系。任何一種算法設(shè)計取決于選定邏輯構(gòu)造，而算法實(shí)現(xiàn)依賴于采用存儲構(gòu)造。數(shù)據(jù)類型是一組___________性質(zhì)相似值集合以及定義在這個值集合上一組操作總稱。數(shù)據(jù)對象是___________性質(zhì)相似數(shù)據(jù)元素集合，是數(shù)據(jù)一種子集。如果操作不變化原邏輯構(gòu)造“值”，而只是從中提取某些信息作為運(yùn)算成果，則稱該類運(yùn)算為型運(yùn)算。引用算法健壯特性是指做為一種好算法，當(dāng)輸入數(shù)據(jù)非法時，也能恰本地做出對的反映或進(jìn)行相應(yīng)解決，而不會產(chǎn)生某些莫名其妙輸出成果。算法分析不是針對實(shí)際執(zhí)行時間精準(zhǔn)算出算法執(zhí)行詳細(xì)時間分析，而是針對算法中語句執(zhí)行次數(shù)做出預(yù)計，從中得到算法執(zhí)行時間信息。T(n)=O(f(n))，它表達(dá)隨問題規(guī)模n增大算法執(zhí)行時間增長率和f(n)增長率相似，稱作算法漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。若算法執(zhí)行時所需要輔助空間相對于輸入數(shù)據(jù)量而言是個常數(shù)，則稱這個算法為原地工作，輔助空間為O(1)。在帶有頭結(jié)點(diǎn)單鏈表中L中，第一種元素結(jié)點(diǎn)指針是。L->next在一種帶頭節(jié)點(diǎn)單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)直接前驅(qū)，則指向頭結(jié)點(diǎn)指針head可用p表達(dá)為head=。p->next->next設(shè)單鏈表結(jié)點(diǎn)構(gòu)造為(data,next)，next為指針域，已知指針px指向單鏈表中data為x結(jié)點(diǎn)，指針py指向data為y新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行如下語句：py->next=px->next；px->next=py。對于棧操作數(shù)據(jù)原則是。后進(jìn)先出設(shè)以數(shù)組A[m]存儲循環(huán)隊(duì)列元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中元素個數(shù)為。(rear-front+m)%m若已知一種棧入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為。n-i+1隊(duì)列是被限定為只能在表一端進(jìn)行插入運(yùn)算，在表另一端進(jìn)行刪除運(yùn)算線性表。普通程序在調(diào)用另一種程序時，都需要使用一種棧來保存被調(diào)用程序內(nèi)分派局部變量。形式參數(shù)存儲空間以及返回地址。棧下溢是指在___棧空_____時進(jìn)行出棧操作。用P表達(dá)入棧操作，D表達(dá)出棧操作，若元素入棧順序?yàn)?234，為了得到1342出棧順序，相應(yīng)P和D操作串為_______。PDPPDPDD在具備n個單元循環(huán)隊(duì)列中，隊(duì)滿共有n-1個元素。隊(duì)列是被限定為只能在表一端進(jìn)行插入運(yùn)算，在表另一端進(jìn)行刪除運(yùn)算線性表。循環(huán)隊(duì)列引入，目是為了克服_______假溢出。所謂稀疏矩陣指是_______非零元很少(t<<m*n)且分布沒有規(guī)律。在稀疏矩陣表達(dá)所相應(yīng)三元組線性表中，每個三元組元素按行為主序，列號為輔序順序排列。二位數(shù)組Am×n按行優(yōu)先順序存儲在內(nèi)存中，元素a00地址為loc(a00),每個元素在內(nèi)存中占d個字節(jié)，元素aij地址計算公式為loc(aij)=loc(a00)＋(i*n+j)*d。樹內(nèi)個結(jié)點(diǎn)度最大值稱為樹度。一種二叉樹第5層節(jié)點(diǎn)最多有16個。已知完全二叉樹T第5層只有7個結(jié)點(diǎn)，則該樹共有____11____個葉子結(jié)點(diǎn)。在一棵二叉樹中，度為零結(jié)點(diǎn)個數(shù)為N0,度為2結(jié)點(diǎn)個數(shù)為N2,則有N0=______N2+1。假設(shè)用于通信電文由8個字母構(gòu)成，其頻率分別為7,19,2,6,32,3,27,10。設(shè)計哈夫曼編碼，其中字母編碼長度最大是5位。一棵具備257個結(jié)點(diǎn)完全二叉樹，它深度為。9散列法存儲基本思想是由核心字值決定數(shù)據(jù)存儲地址。大多數(shù)排序算法均有兩個基本操作：。比較和移動由于查找算法基本運(yùn)算是核心字之間比較操作，因此可用平均查找長度來衡量查找算法性能。查找有靜態(tài)查找和動態(tài)查找，當(dāng)查找不成功時動態(tài)查找會將查找核心字插入在表中。順序查找法中設(shè)立監(jiān)視哨，可以起到防止越界作用。假設(shè)列表長度為n，那么查找第i個數(shù)據(jù)元素時需進(jìn)行n-i+1次比較。假設(shè)查找每個數(shù)據(jù)元素概率相等，即Pi=1/n，則順序查找算法平均查找長度為：ASL=(n+1)/2。折半查找法又稱為二分法查找法，這種辦法規(guī)定待查找列表必要是按核心字大小有序排列順序表。假定將長度為n表提成b塊，且每塊含s個元素，則b=n/s。又假定表中每個元素查找概率相等，在有序表(12,24,36,48,60,72,84)中二分查找核心字72時所需進(jìn)行核心字比較次數(shù)為2。折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。在各種查找辦法中，平均查找長度與結(jié)點(diǎn)個數(shù)n無關(guān)查找辦法是散列查找。當(dāng)核心字集合很大時，核心字值不同元素也許會映象到哈希表同一地址上，即k1≠k2，但H（k1）=H（k2），這種現(xiàn)象稱為沖突.在散列函數(shù)H(key)=keyMODp中，p應(yīng)取素數(shù)。設(shè)哈希表長m=14，哈希函數(shù)H(key)=keyMOD11.表中已有4個結(jié)點(diǎn)；addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，別的地址為空。如用二次探測再散列解決沖突，核心字為49結(jié)點(diǎn)地址是。9希爾排序是屬于插入排序改進(jìn)辦法。給出一組核心字T＝（20,4,34,5,16,33,18,29,2,40,7），規(guī)定從下到大進(jìn)行排序，試給出迅速排序（選一種記錄為樞紐）第一趟排序成果。7,4,2,85,16,18,20,,29,33,40,34大多數(shù)排序算法均有兩個基本操作：比較和移動。在對一組記錄（54,38,96,23,15,72,60,45,83）進(jìn)行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。6。在插入和選取排序中，若初始數(shù)據(jù)基本正序，則選用插入；若初始數(shù)據(jù)基本反序，則選用選取。在堆排序和迅速排序中，若初始記錄接近正序或反序，則選用堆排序；若初始記錄基本無序，則最佳選用迅速排序。對于n個記錄集合進(jìn)行冒泡排序，在最壞狀況下所需要時間是O(n2)。若對其進(jìn)行迅速排序，在最壞狀況下所需要時間是O(n2)對于n個記錄集合進(jìn)行歸并排序，所需要平均時間是O(nlog2n)，所需要附加空間是O(n)。7．對于n個登記表進(jìn)行2路歸并排序，整個歸并排序需進(jìn)行┌l(fā)og2n┐趟（遍）。8.設(shè)要將序列（Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X）中核心碼按字母序升序重新排列，則：冒泡排序一趟掃描成果是HCQPAMSRDFXY；初始步長為4希爾（shell）排序一趟成果是PACSQHFXRDMY；二路歸并排序一趟掃描成果是HQCYAPMSDRFX；迅速排序一趟掃描成果是FHCDPAMQRSYX；堆排序初始建堆成果是ADCRFQMSYPHX。9.在堆排序、迅速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)一方面選用辦法，另一方面選用迅速排序辦法，最后選用歸并排序辦法；若只從排序成果穩(wěn)定性考慮，則應(yīng)選用歸并排序辦法；若只從平均狀況下最快考慮，則應(yīng)選用堆排序、迅速排序和歸并排序辦法；若只從最壞狀況下最快并且要節(jié)約內(nèi)存考慮，則應(yīng)選用堆排序辦法。三、程序填空題如下程序功能是實(shí)現(xiàn)帶附加頭結(jié)點(diǎn)單鏈表數(shù)據(jù)結(jié)點(diǎn)逆序連接，請?zhí)羁胀晟浦?。voidreverse(pointerh)/*h為附加頭結(jié)點(diǎn)指針；*/{pointerp,q;p=h->next；h->next=NULL;while((1)________){q=p；p=p->next；q->next=h->next；h->next=(2)________；}}(1)p!=null∥鏈表未到尾就始終作(2)q∥將當(dāng)前結(jié)點(diǎn)作為頭結(jié)點(diǎn)后第一元素結(jié)點(diǎn)插入下列算法在順序表L中依次存儲著線性表中元素，在表中查找與e相等元素，若L.elem[i]=e,則找到該元素，并返回i+1，若找不到，則返回“-1”，請?zhí)羁胀晟浦?/p>

int

Locate(SeqListL，inte){

i=0;

/*i為掃描計數(shù)器，初值為0，即從第一種元素開始比較*/

while((i<=L.last)&&(L.elem[i]!=e))

i++;

/*順序掃描表，直到找到值為key元素,或掃描到表尾而沒找到*/

if

(i<=L.last)

return(i+1);

/*若找到值為e元素，則返回其序號*/

else

return(-1);

/*若沒找到，則返回空序號*/

}下列算法在順序表L中第i個數(shù)據(jù)元素之前插入一種元素e。插入前表長n=L->last+1，i合法取值范疇是1≤i≤L->last+2，請?zhí)羁胀晟浦?/p>

void

InsList(SeqList*L，inti，inte){intk;if((i<1)||(i>L->last+2))printf(“插入位置i值不合法”)；

if(L->last>=maxsize-1)printf(“表已滿無法插入”)；for(k=L->last;k>=i-1;k--)

/*為插入元素而移動位置*/