06數(shù)據(jù)構(gòu)造〔50分〕一、單項選擇題（在每題的四個備選答案中，選出一個正確的答案，并將其號碼填寫在題干后面的括號內(nèi)。每題1分，共10分）.數(shù)據(jù)的根本單位是（）A.數(shù)據(jù)項 B.數(shù)據(jù)類型 C.數(shù)據(jù)對象 D.數(shù)據(jù)元素.假設(shè)頻繁的對線性表進(jìn)展插入和刪除操作，則該線性表應(yīng)當(dāng)承受存儲構(gòu)造。（）A.挨次 B.鏈?zhǔn)?C.散列D.任意.假設(shè)進(jìn)棧序列為3,5,7,9,進(jìn)棧過程中可以出棧，則不行能的出棧次序是（）A.7,5,3,9 B.9,7,5,3 C.7,5,9,3 D.9,5,7,3.下面的說法中，正確的選項是（）A.字符串的長度指串中包含的字母的個數(shù)B.字符串的長度指串中包含的不同字符的個數(shù)C.一個字符串不能說是其自身的一個子串D.假設(shè)T包含在S中，則T肯定是S的一個子串5.廣義表（（a,b）,（c,d））的表尾是（）A.d B.c,dC.（c,d）D.（c,d）.n個頂點的連通圖，其生成樹有條邊。（）A.n-1 B.nC.n+1D.不確定.假設(shè)一棵二叉樹有8個度為2的結(jié)點，則該二叉樹的葉節(jié)點個數(shù)為（）A.7 B.8 C.9D.不確定.在有n個節(jié)點的二叉鏈表中有個空鏈域。（）A.n+1 B,n C.n-1 D.不確定.在等概率的狀況下，承受挨次插查找法查找長度為n的線性表，平均查找長度為（A.n B.n/2 C.（n+l）/2 D.（n-l）/2.以下排序方法中，排序的比較次數(shù)與序列的初始排列狀態(tài)無關(guān)的是（）A.選擇排序 B.插入排序 C.冒泡排序 D.快速排序二、填空題（本大題共10小題，每題1分，共10分）.假定一個挨次隊列的隊首和隊尾分別為f和r,則推斷隊空的條件為o.在挨次存儲的線性表中插入或刪除一個元素平均約移動表中的元素。.設(shè)有一個二維數(shù)組A[5][4],按行序優(yōu)先存儲，A[O][O]的存儲地址是10,每個數(shù)組元素占2個字節(jié)，則A[3H2]的存儲地址是0.深度為k的二叉樹至多有個結(jié)點。（k》l）.在有n個結(jié)點，e條邊的有向圖的鄰接表中有個表結(jié)點。.對一棵二叉樹進(jìn)展遍歷時，得到的結(jié)點序列是一個關(guān)鍵字的有序序列。.在一個圖中，全部頂點的度數(shù)之和是邊數(shù)的倍。.假設(shè)有序表（15,21,33,46,58,80,87）中折半查找元素33時，與關(guān)鍵字比較次查找成功。.設(shè)哈希表長m=14,哈希函數(shù)H（key）=keyMOD11。表中己有4個元素：01234 5 67 8910111213口I I115|38|61|84||| | | | |假設(shè)用二次探測再散列處理沖突，關(guān)鍵字為49的記錄的存儲位置是.具有n個頂點的無向完全圖，有條邊。三、推斷題（本大題共5小題，每題1分，共5分）.算法在執(zhí)行時，對同樣的輸入可以得到不同的結(jié)果。（）.線性表的鏈?zhǔn)酱鎯?gòu)造的內(nèi)存單元地址肯定不連續(xù)。（）.隊列允許插入的一段成為隊尾，允許刪除的一端稱為隊頭。（）.拓?fù)渑判蚴莾?nèi)部排序。（）.樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹肯定為空。（）四、綜合應(yīng)用題（本大題共3小題，每題5分，共15分）.畫出具有三個結(jié)點的二叉樹的全部形態(tài)（不考慮數(shù)據(jù)信息的組合狀況）。（5分）.寫出以下圖的鄰接矩陣，并寫出其從VI動身的深度優(yōu)先搜尋遍歷序列（5分）.將以下圖所示的樹轉(zhuǎn)換成二叉樹，并寫出該二叉樹的先序遍歷序列。（5分）五、算法設(shè)計（本大題共1小題，共10分）.線性表承受鏈?zhǔn)酱鎯?gòu)造，結(jié)點類型定義如下，試編寫一個算法，在帶頭結(jié)點的單鏈表L中，刪除全部值為x的結(jié)點。typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*Linklist;07 數(shù)據(jù)構(gòu)造〔50分〕一、單項選擇題（10分，每題1分）.按二叉樹的定義，具有3個結(jié)點的二叉樹有種。（）A.3 B.4 C.5 D.6.假設(shè)一個棧的入棧序列是1,2,3 n,其輸出序列為pl,p2,p3,…，pn,假設(shè)pl=n,則pi為（）A.i B.n=i C.n-i+qD.不確定.下面結(jié)論是正切的。（）A.樹的先根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列一樣B.樹的后根遍歷序列與其對應(yīng)的二叉樹的先序遍歷序列一樣C.樹的先根遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列一樣D.以上都不對.評價一個算法時間性能的主要標(biāo)準(zhǔn)是（）A.算法易于調(diào)試 B.算法易于理解C.算法的穩(wěn)定性和正確性 D.算法的時間簡單度.線性表的挨次存儲構(gòu)造是一種的存儲構(gòu)造。（）A.隨機(jī)存取 B.挨次存取 C.索引存取 D.散列存取.在挨次表中，只要知道,就可在一樣時間內(nèi)求出任一結(jié)點的存儲地址。（A.基地址 B.結(jié)點大小 C.向量大小 D.基地址和結(jié)點大小.在中序線索二叉樹中，假設(shè)某結(jié)點有右孩子，則該結(jié)點的直接后繼是（）A.左子樹的最右下結(jié)點 B.右子樹的最右下結(jié)點C.左子樹的最左下結(jié)點 D.右子樹耳朵最左下結(jié)點.一個棧的入棧序列是abcde,則棧的不行能輸出序列是（）A.edcba B.decbaC.dceabD.abcde廣義表是線性表的推廣，它們之間的區(qū)分在于（）A.能否使用子表 B.能否使用原子項C.表的長度 D.是否能為空.假設(shè)一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為。的結(jié)點的個數(shù)是（）A.9 B.llC.12 D.不確定二、填空題（每空1分，共10分）.挨次表中規(guī)律上相鄰的元素的物理位置 。.在分塊查找方法中，首先查找索引表，然后再用挨次查找方法查找相應(yīng)的.安排排序的兩個根本過程是.在拓?fù)渑判蛑校負(fù)湫蛄械牡谝粋€頂點必定是為0的頂點。.有n個結(jié)點的二叉鏈表中。其中空的指針域為。.有向圖的鄰接表表示適于求頂點的o.有向圖的鄰接矩陣表示中，第i 上非零元素的個數(shù)為頂點vi的入度。.在樹的表示法中，求指定結(jié)點的雙親或祖先格外便利，但是求指定結(jié)點的孩子或其他后代可能要遍歷整個數(shù)組。.由五個分別帶權(quán)值為9,2,3,5,14的葉子結(jié)點構(gòu)成一棵哈夫曼樹，該樹的帶權(quán)路徑長度為.具有n個頂點的有向圖最多有條邊。三、填空題（30分）.寫出頭插法建立單鏈表的算法（5分）.求單源最短路徑（從源點。開頭），要求寫出過程。（5分）.某二叉樹的中序遍歷序列：dfaechi后序遍歷序列：fdbehica請構(gòu)造出該二叉樹；（3分）寫出前序遍歷序列：（2分）.設(shè)查找的關(guān)鍵字序列｛15,4,30,41,11,22,1｝。畫出對應(yīng)的二叉排序樹。（5分）.寫出圖的廣度優(yōu)先搜尋算法（用鄰接表存儲）（5分）.線性表的關(guān)鍵字集合：[19,14,23,01,68,20,84,27,55,11,10,79｝散列函數(shù)為：H（k）=k%13,承受拉鏈法處理沖突，并設(shè)計出鏈表構(gòu)造。（5分）08 數(shù)據(jù)構(gòu)造〔50分〕一、單項選擇題（10分，每題1分）.假設(shè)一個棧的輸入序列為1,2,3,…，n,輸出序列的第一個元素是i,則第i個輸出元素是（）A.i-j-1B.i-jC.j-i+1 D.不確定的.循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊的操作為0A.rear=rear+1 B.rear=（rear+l）mod（m-l）C.rear=（rear-i-l）modm D.rear=（rear+1）mod（m+1）.二維數(shù)組A的每個元素是由6個字符組成的串，其行下表i=0,1 8,列下表j=l,2,....10o假設(shè)A按行序為主序存儲，元素A[8][5]的起始地址與當(dāng)A按列序為主序存儲時的元素的起始地址一樣。（設(shè)每個字符占一個字節(jié)）（）A.A[8][5] B.A[3][10] C.A[5][8] D.A[0][9].下面說法不正確的選項是0A.廣義表的表頭總是一個廣義表 B.廣義表的表尾總是一個廣義表C.廣義表難以用挨次存儲構(gòu)造 D.廣義表可以是一個多層次的構(gòu)造.算術(shù)表達(dá)式A+B*C-D/E轉(zhuǎn)為前綴表達(dá)式后為{）A.-A*C/DEB.-A+B*CD/EC.-+ABC/DED.-+A*BC/DE.有n個葉子的哈夫曼樹的結(jié)點總數(shù)為0A.不確定 B.2nC.2n+iD.2n-1.假設(shè)X是中序線索二叉樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為（）A.X的雙親 B.X的右子樹中最左的結(jié)點C.X的左子樹中最右結(jié)點 D.X的左子樹中最右葉結(jié)點.無向圖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)先遍歷，得到的頂點序列正確的選項是（）A.a,b,e,c,d,f B.a,c>f,e,b,dC.a,e,b,c,f,d D.a,e,d,f,c,b.假定有k個關(guān)鍵字互為同義詞，假設(shè)用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)展探測。（）A.k-1次B.k次C.k+1次D.k（k+1）/2次.以下排序算法中，在每一趟都能選出一個元素放到其最終位置上，并且其時間性能受數(shù)據(jù)初始特性影響的是（）A.直接插入排序 B.快速排序 C.直接選擇排序 D.堆排序二、填空題（5分，每題1分）.在有序表中，承受折半查找算法查等于A[12]的元素，所比較的元素下標(biāo)依次為.求圖的最小生成樹有兩種算法，算法適合于求稀疏圖的最小生成樹。.一棵左子樹為空的二叉樹在先序線索化后，其中的空鏈域的個數(shù)為。.在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是o.一個深度為k,具有最少結(jié)點數(shù)的完全二叉樹按層次，（同層次從左到右）用自然數(shù)依次對結(jié)點編號，則編號是i的結(jié)點所在的層次號是（跟所在的層次號規(guī)定為1層）。三、推斷題（5分，每題1分）.鏈表是承受鏈?zhǔn)酱鎯?gòu)造的線性表，進(jìn)展插入、刪除操作時，在鏈表中比在挨次存儲構(gòu)造中效率高。 （）TOC\o"1-5"\h\z.對一棵二叉樹進(jìn)展層次遍歷時，應(yīng)借助于一個棧。 （）.將一棵樹轉(zhuǎn)成二叉樹，跟節(jié)點沒有左子樹。 （）.一個有向圖的鄰接表和逆鄰接表中結(jié)點的個數(shù)可能不等。 （）.在待排序數(shù)據(jù)有序的狀況下，快速排序效果好。 （）四、應(yīng)用題（20分，每題5分）.用集合｛46,88,45,39,70,58,101,10,66,34｝建立一棵二叉排序樹，畫出該樹，并求在等概率狀況下的平均查找長度。.設(shè)一組關(guān)鍵字｛9,01,23,14,55,20,84,27｝,承受哈希函數(shù)：H（key）=keymod7和二次探測再散列法解決沖突，對該關(guān)鍵字序列構(gòu)造表長為10的哈希表。.假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中消滅的頻率分別為0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10,試為這8個數(shù)字設(shè)計哈夫曼編碼。.用普里姆算法構(gòu)造以下圖的一棵最小生成樹，并給出選點挨次。（以①為起點）五、算法設(shè)計題（10分）編寫一個算法來交換單鏈表中指針P所指接點與其后繼結(jié)點，HEAD是該鏈表的頭結(jié)點，P指向該鏈表中的某一結(jié)點。山東省2022年一般高等教育專升本統(tǒng)一考試

數(shù)據(jù)構(gòu)造（50分）一、單項選擇題（io分，每題1分）.【答案】D【解析】棧的根本性質(zhì)是后進(jìn)先出，此題中，在輸出序列第一個元素是i時，只能確定1-i-1這些元素的輸出的先后次序，但是不能確定出第i個元素具體輸出哪個元素。.【答案】D【解析】在循環(huán)隊列中，rear指針指示隊尾，此題中存儲數(shù)組實質(zhì)上為A[m+1]。所以，入隊列的操作應(yīng)當(dāng)是修改rear=（rear+l）%（m+l）,答案C是錯誤的。.【答案】B【解析】此題中二維數(shù)組屬于9行10歹IJ。所以，首先確定以行序為主序的存儲中，A[8][5]在全部元素排列中的位置為第85位，同樣確實定以列序為主序的第85個存儲元素的元素應(yīng)當(dāng)為A[3][10]。.【答案】A

【解析】構(gòu)成廣義表的數(shù)據(jù)元素可以是單個元素，也可以是廣義表。廣義表的表頭就是廣義表中的第一個元素，可以是單個元素，也可以是子表。選項B、C、D都是正確的。.【答案】D【解析】在算數(shù)表達(dá)式的前綴表達(dá)式實質(zhì)上就是運算符寫在兩個運算數(shù)的前面，固然在實現(xiàn)轉(zhuǎn)換時，要考慮運算數(shù)的相對位置不變，而且考慮運算的優(yōu)先級問題。固然，也可以采用二叉樹表示出算數(shù)表達(dá)式，這樣，前序遍歷挨次即為前綴表達(dá)式（波蘭式），后序遍歷即位后綴表達(dá)式（逆波蘭式），此題答案選D。.【答案】D【解析】哈夫曼樹的特點是沒有度為1的結(jié)點，依據(jù)二叉樹的性質(zhì)3,nO=n2+l,所以，具有n個葉子結(jié)點的二叉樹具有n-1個度為2的結(jié)點，因此，答案選D。.【答案】C【解析】由于在中序線索二叉樹中，結(jié)點X有左子樹，所以，該結(jié)點前驅(qū)在左子樹中，左子樹中最右的結(jié)點是子樹中最終一個遍歷的結(jié)點，該結(jié)點可能為葉子結(jié)點，也可能是度為1的結(jié)點（即有左孩子）。.【答案】A【解析】依據(jù)此題無向圖的定義，可以圖G如右圖所示： 、,依據(jù)廣度優(yōu)先遍歷的算法思想，可以確定A是正確的，選項B、C、D都是錯誤的。.【答案】D【解析】實行線性探測法存儲這k個同義詞，則第一個關(guān)鍵字可以直接存儲，其余的k-1個元素中，抱負(fù)的狀況下，第1個元素探測1次可以存儲，第2個元素探測2次才能存儲，以此類推，因此，至少需要探測的次數(shù)為k（k+l）/2。.【答案】B【解析】直接插入排序的算法思想是從第2到最終一個元素，依次插入到前面的有序序列中,因此，每趟執(zhí)行完畢，不能確定出一個元素最終的位置；快速排序的每趟可以確定出樞軸元素的最終位置，而且，當(dāng)元素根本有序時，其排序性能會降低，所以選B?選項C、D能符合第一條要求，但是其時間性能跟待排元素的序列無關(guān)。二、填空題（本大題共10小題，每題1分，共10分）.【答案】6、9、11、12【解析】依據(jù)有序表的折半查找的mid的取值為（low+high）/2,可以確定判定樹的形態(tài)如下，查找下標(biāo)為12的元素時，先后要與下標(biāo)為：6、9、11、12四個元素進(jìn)展比較。.【答案】克魯斯卡爾（Kruskal）【解析】求解最小生成樹的算法主要有兩種，普里姆算法（Prim）時間簡單度為O（n2）,與網(wǎng)中的邊數(shù)無關(guān)，因此適合于求邊稠密的網(wǎng)的最小生成樹；而克魯斯卡爾（Kruskal）算法時間簡單度為O（eloge）,因此，適合于求邊稀疏的網(wǎng)的最小生成樹。.【答案】2【解析】左子樹為空，則根結(jié)點沒有前驅(qū)，左孩子指針域為空，另外，根結(jié)點右子樹中最終一個結(jié)點沒有后繼，右孩子指針域也為空，所以，該二叉樹中空鏈域的個數(shù)為2。.【答案】p->next!=NULL（或文字說明”指針P所指結(jié)點的指針域不等于NULL”）【解析】在單鏈表L中，指針p所指結(jié)點有后繼，前提是指針P所指結(jié)點的指針域不等于NULL,假設(shè)指針域默認(rèn)為next,則可以表示為“p->next!=NULL”.（注：NULL肯定是大寫）Llogz-J+l.【答案】 2【解析】深度為K的結(jié)點已經(jīng)構(gòu)成完全二叉樹，所以前i個結(jié)點也為完全二叉樹，所以依據(jù)性質(zhì)4可以確定第i個結(jié)點的深度為L°g2。三、推斷題（5分，每題1分）1.【答案】V【解析】鏈?zhǔn)酱鎯?gòu)造的線性表的優(yōu)點就在于實現(xiàn)插入和刪除操作時，不需要大量元素的移動，因此，比挨次存儲構(gòu)造中實現(xiàn)插入刪除操作效率高。2【答案】X【解析】實現(xiàn)二叉樹的按層遍歷時，應(yīng)借助于一個隊列作為關(guān)心構(gòu)造。3【答案】V【解析】樹轉(zhuǎn)換為二叉樹是依據(jù)的孩子兄弟表示法這種存儲構(gòu)造，樹根沒有兄弟，所以，一棵樹轉(zhuǎn)換成二叉樹，對應(yīng)二叉樹根結(jié)點沒有左子樹。4【答案】X【解析】有向圖的鄰接表中結(jié)點的個數(shù)與逆鄰接表中結(jié)點的個數(shù)是相等的，都等于圖中全部頂點的入度和（或出度和）的值。5【答案】X【解析】就平均時間而言，快速排序目前被認(rèn)為是最好的一種內(nèi)部排序方法，但是，當(dāng)待排序列根本有序時，快速排序?qū)⑼懟癁槊芭菖判颍虼耍判蛐Ч炊档汀Ｋ摹⒕C合應(yīng)用題（本大題共3小題，每題5分，共15分）.答：依據(jù)結(jié)點畫出二叉排序的過程如下圖：

/10=3.2等概率狀況下，平均查找長度為：15*2+4*2+3*3+2*2+1*1)/10=3.2構(gòu)造哈希表如下圖:.答：依據(jù)哈希函數(shù)和處理沖突的方法為二次探測再散列,構(gòu)造哈希表如下圖:141923842755202567893 40 1【解析】留意關(guān)鍵字的挨次,9%7=2;1%7=1;23%7=2,沖突，但是(2+12)%10=3;14%7=0;55%7=6;20%7=6,沖突，但是(6+12)%10=7;84%7=0,沖突，但是(0+12)%10=1,已經(jīng)占用，由于函數(shù)值已經(jīng)是0了，在這里不能再摸索?12,因此(0+22)%10=4,所以84存儲在下標(biāo)4的單元格內(nèi)。最終27%7=6,沖突，(6+12)%10=7,仍舊沖突，(6-12)%10=5,所以27存儲在下標(biāo)5的單元格內(nèi)。.答：依據(jù)每個字符消滅的頻率，我們可以求解哈夫曼樹，為便利求解，不妨將頻率變?yōu)檎麛?shù)，則權(quán)值分別為：7,19,2,6,32,3,21,10,由此構(gòu)造哈夫曼如圖：由此可以設(shè)定每個字符的哈夫曼編碼：0.02：00000；0.03:(X)001;0.06:0001;0.07:0010;0.1:0011;0.32:01;0.19:10;02711。.答:依據(jù)普里姆算法構(gòu)造最小生成樹，如以下圖所示：五、算法設(shè)計（本大題共1小題，共10分）答：Linklistexchange（Linklist&head,Linklistp）{q=head->next;pre=head;〃初始化q、pre指針，當(dāng)q指針移動到與P指針相等時，貝ijpre指針正好指向前驅(qū)結(jié)點；while（q!=NULL&&q!=p）{pre=q;q=q->next;}if（p->next==NULL）printf（"p無后繼結(jié)點\n"）；else{q=p->next;〃利用q、pre、p三個指針聯(lián)合實現(xiàn)當(dāng)前結(jié)點與前驅(qū)結(jié)點的交換；pre->next=q;p->next=q->next;q->next=p;}）山東省2022年一般高等教育專升本統(tǒng)一考試計算機(jī)科學(xué)與技術(shù)專業(yè)綜合二試卷參考答案數(shù)據(jù)構(gòu)造（50分）一、單項選擇題（每題1分，共10分）.【答案】C【解析】具有三個結(jié)點的二叉樹的形態(tài)共有5種，而具有三個結(jié)點的樹的形態(tài)是2種。.【答案】C【解析】假設(shè)輸出的第一個元素為n,則全部元素均已經(jīng)入棧，所以出棧挨次即為元素的逆序排列，因此，輸出的第i個元素的值為n-i+L.【答案】A【解析】依據(jù)樹與二叉樹的相互轉(zhuǎn)換數(shù)關(guān)系，以及樹及二叉樹的遍歷挨次，有以下結(jié)論：（1）樹的先根遍歷挨次與對應(yīng)二叉樹的先序遍歷挨次一樣；（2）樹的后根遍歷挨次與對應(yīng)二叉樹的中序遍歷挨次一樣。.【答案】D【解析】算法的時間性能的評價主要使用算法的時間簡單度，算法的空間性能的評價主要承受空間簡單度。.【答案】A【解析】線性表的挨次存儲構(gòu)造要求安排連續(xù)的存儲空間，因此，可以實現(xiàn)數(shù)據(jù)元素的順序存取以及隨機(jī)存取。但元素的插入和刪除需要涉及大量元素的移動；而線性表的鏈?zhǔn)酱鎯Ρ憷谠氐牟迦肱c刪除，但是不能實現(xiàn)隨機(jī)存取，只能進(jìn)展挨次存取。.【答案】D【解析】挨次表要求存儲空間是連續(xù)，所以，只要知道基地址，知道每個元素所占的字節(jié)數(shù)，就可以求每個元素的存儲起始地址。.【答案】D【解析】在中序線索二叉樹中，假設(shè)某結(jié)點有右子樹，則在訪問完該結(jié)點后要訪問右子樹中最左邊的結(jié)點，所以答案選D。.【答案】C【解析】棧的根本性質(zhì)是后進(jìn)先出，在入棧序列為abcde,出棧的第一個元素為d時，則已經(jīng)入棧，所以，此時“abc”三個元素的出棧序列中，肯定是cba的挨次，而不能消滅cab的挨次，所以選項C是錯誤的。.【答案】A【解析】構(gòu)成廣義表的數(shù)據(jù)元素可以單個元素，也可以是由假設(shè)干個元素所組成的子表。廣義表屬于特別的線性表，特別的地方在于廣義表的元素中能否使用子表。.【答案】B【解析】依據(jù)二叉樹的根本性質(zhì)3,對于任意一棵二叉樹，滿足度為0的結(jié)點為度為2的結(jié)點數(shù)加1。所以，答案選B二、填空題（本大題共10小題，每題1分，共10分）.【答案】肯定相鄰【解析】挨次表承受連續(xù)存儲空間作為元素的存儲構(gòu)造，所以，規(guī)律上相鄰的數(shù)據(jù)元的物理存儲空間也肯定相鄰。.【答案】塊【解析】在索引挨次表中，將全部的關(guān)鍵字進(jìn)展分塊，塊與塊之間關(guān)鍵字大小有序，在每個塊內(nèi)部元素排列無序，可以把每個組中最大元素值作為該組的索引參加到索引表中排列，所以，索引表中元素排列是有序的，因此，在查找元素時，先查找索引表，獲得查找元素所在組后，再使用挨次查找去查找相應(yīng)的塊。.【答案】安排和收集【解析】安排法排序?qū)儆谝环N典型的多關(guān)鍵字排序，安排排序的根本思想是排序過程無須比較關(guān)鍵字，而是通過“安排”和“收集”過程來實現(xiàn)排序。.【答案】入度【解析】拓?fù)渑判蛎看味歼x擇沒有前驅(qū)的結(jié)點進(jìn)展輸出，其中結(jié)點沒有前驅(qū)，即入度為0。.【答案】n+1【解析】二叉鏈表中，每個結(jié)點有2個指針域，具有n個結(jié)點的二叉鏈表一共有2n個指針域，其中，除根結(jié)點外，每個結(jié)點需要一個指針來指向，所以空的指針域的個數(shù)為n+1。6.【答案】出度【解析】有向圖的鄰接表是指:全部頂點建立頂點結(jié)點，以每個頂點為弧尾的全部弧對應(yīng)的另外一個頂點序號構(gòu)成表結(jié)點鏈接形成的單鏈表。所以，通過計數(shù)每個單鏈表中表結(jié)點的個數(shù)，可以計算每個頂點的出度。.【答案】列【解析】有向圖的鄰接矩陣的特點是，通過求解每一行上1的個數(shù)，可以求解每個頂點的出度；通過求解每一列上1的個數(shù)，可以求解每個頂點的出度。無向圖的鄰接矩陣屬于對稱矩陣，每個頂點的度即為行或列上1的個個數(shù)。.【答案】雙親【解析】樹的表示方法一共有三種，雙親表示法、孩子表示法以及孩子兄弟表示法。其中雙親表示法為每個樹中元素建立一個結(jié)點，包括存儲數(shù)據(jù)元素本身，以及該結(jié)點的雙親結(jié)點的存儲下標(biāo)，所以，該存儲方法可以很簡潔的求解結(jié)點的雙親以及祖先，但是求解結(jié)點的孩子及后代需要遍歷整個數(shù)組。樹的帶權(quán)路徑長度為:樹的帶權(quán)路徑長度為:(2+3)*4+5*3+9*2+14*1=67.【答案】n(n-l)【解析】在有n個頂點的有向完全圖中，從每個頂點出去的弧有n-1條，所以總弧數(shù)為n(n-l)o四、綜合題(30分，每題5分).答：viodcreat(Linklist&L){L=(Linklist)malloc(sizeof(Lnode));L->next=NULL;for(i=n;i>0;i++){p=(Linklist)malloc(sizeof(Lnode));scanf(&p->data);p->next=L->next;L->next=p;)留意：除了使用頭插法，還有尾插法，可以查閱資料寫出算法。.答：

求頂點0其余各頂點的最短路徑110(0,1)///260(0,1,2)50(0,3,2)/330(0,3)30(0,3)//4100(0,4)100(0,4)90(0,3,4)60(0,3,2,4)添加頂點132.答：依據(jù)（1）中序遍歷的特點：左子樹、根、右子樹的遍歷挨次；（2）后序遍歷的特點：左子樹、右子樹、根；（3）二叉樹的每棵子樹也符合該特性。所以，該二叉樹的構(gòu)造過程為：由此可得到二叉樹的前序遍歷挨次為：abdfceih.答：該鄰接表的構(gòu)造描述如下：ftdefineVERTEXMAX100typedefstructnode{intadjvex;structnode*next;}Edgenode; 〃表結(jié)點的類型定義typedefstructvnode{vextypevertex;Edgenode*firstedge;}VertexNode; 〃頂點結(jié)點的類型定義Typedefstruct{VertexNodeadjlist[VERTEX_MAX];intn,e; 〃頂點數(shù)和邊數(shù)}ALGraph; 〃鄰接表的類型定義voidBFS(ALGraph*G){for(v=0;v<g->n;v++) visited[v]=FALSE;InitQueue(Q)；for(v=0;v<g->n;v++)if(!visited[v]){visited[v]=TURE;Printf(a%c",G->adjlist[v].vertex);EnQueue(Q,v)while(!QueueEmpty(Q)){DeQueue(Q,u)；for(p=G->adjlist[u].firstedge;p;p=p->next)if(!visited[p->adjvex]){visited[p->adjvex]=TRUE;Printf(a%cff,G->adjlist[p->adjvex].vertex);EnQueue(Q,p->adjvex);.答：依據(jù)哈希函數(shù)以及拉鏈法解決沖突，構(gòu)造如下哈希表:山東省2022年一般高等教育專升本統(tǒng)一考試數(shù)據(jù)構(gòu)造（50分）一、單項選擇題（每題1分，共10分）.【答案】D【解析】全部能輸入到計算機(jī)中的符號的總稱為數(shù)據(jù)，數(shù)據(jù)元素是構(gòu)成數(shù)據(jù)的根本單位，數(shù)據(jù)元素可以由假設(shè)干條記錄組成，每條記錄又可由假設(shè)干數(shù)據(jù)項組成。一樣性質(zhì)的數(shù)據(jù)元素的集合構(gòu)成數(shù)據(jù)對象。數(shù)據(jù)元素的類型稱為數(shù)據(jù)類型。.【答案】B【解析】承受挨次存儲構(gòu)造的線性表在進(jìn)程插入和刪除元素時需要涉及大量元素的移動問題。而鏈?zhǔn)酱鎯?gòu)造可以很簡潔的實現(xiàn)插入和刪除操作，因此選B。.【答案】D【解析】假設(shè)9作為第一個出棧元素，前提是3,5,7已經(jīng)依次入棧了，所以，此時輸出挨次只能為9,7,5,3。選項D是錯誤的。.【答案】D【解析】字符串的長度應(yīng)當(dāng)是串中全部包含的字符的個數(shù)，所以選項A只提到了字母，選項B提到了不同字符的個數(shù)，均是錯誤的，每個字符串都屬于自己的子串，因此選項C錯誤。.【答案】D【解析】廣義表的表頭是廣義表中的頭元素，廣義表的表尾是指除去表頭元素，其余元素所組成的廣義表，因此，答案選D而不是C,更不是A和B。.【答案】A【解析】圖的生成樹是指包含圖中全部的n個頂點，但僅包含連通這個n個頂點的n-1條邊。.【答案】C【解析】依據(jù)二叉樹的根本性質(zhì)3：對于任意一棵二叉樹滿足n0=n2+l,所以，當(dāng)度為2的結(jié)點數(shù)為8時，葉子結(jié)點個數(shù)為9。.【答案】A【解析】在二叉鏈表中每個結(jié)點有兩個指針域，而除了根結(jié)點外，每個結(jié)點均需要占用其中一個指針域，所以空的指針域個數(shù)為：2*n-(n-l)=n+l個..【答案】C【解析】在等概率的狀況下，每個元素的查找概率都是1/n,其中查找最終一個元素需要比較I次，查找第n-1個結(jié)點需要比較2次，依次類推，查找第1個結(jié)點需要比較n次，平均查找長度為：(1+2+3+,,)/n=(n+D/2。.【答案】A【解析】對含有n個元素的線性表，執(zhí)行選擇排序時，無論序列的初始排列如何，均需要進(jìn)展n-1趟排序，每次都需要n-i次比較，確定出第i個位置上的元素來，所以答案選A。而插入排序、冒泡排序當(dāng)元素已經(jīng)有序時，比較次數(shù)可以降低為n-1次：快速排序當(dāng)元素排列根本有序時，性能反而降低。二、填空題(本大題共10小題，每題1分，共10分).【答案】f==r【解析】在循環(huán)隊列中，分別用f指示隊頭，r指向隊尾。所以當(dāng)f==r時，表示隊列中沒有元素存在，通常當(dāng)(r+l)%maxsize==f時，表示該循環(huán)隊列已滿。(以犧牲一個存儲空間偉代價)。在此留意是“=="，而不是。.【答案】1/2【解析】假設(shè)在長度為n的挨次表中插入元素時，插入位置有n+1個，平均需要移動元素數(shù)量為(0+1+2,,+n)/(n+l)=n/2；當(dāng)刪除元素時，刪除位置有n個，平均需要移動的元素個數(shù)為：(0+l+2+?+(n-D)/n=(n-l)/2.都接近1/2的元素個數(shù)。.【答案】38【解析】二位數(shù)組每行中有5個元素，每個元素占2個字節(jié)，因此LOC(3,2)=LOC(0,0)+(3*4+2)*2=38.【答案】2K-1【解析】二叉樹的根本性質(zhì)2。.【答案】e【解析】有向圖的鄰接表是以圖中全部頂點作為頭結(jié)點，將全部以該頂點為弧尾的弧生成表結(jié)點構(gòu)成的。所以，表結(jié)點數(shù)與弧數(shù)是一一對應(yīng)的。.【答案】中序【解析】二叉排序樹中全部左子樹中結(jié)點均比根結(jié)點的值小，所以右子樹中結(jié)點值均比根結(jié)點的值大，假設(shè)左右子樹不空，左右子樹都滿足該特性，所以二叉排序樹的中序遍歷挨次是由小到大的挨次排列的。.【答案】2【解析】無論在有向圖還是在無向圖中，每條邊或弧在計算頂點的度時均被用過2次，所以，得到的頂點的度的和就是邊數(shù)的2倍。.【答案】3【解析】該有序表中包含7個元素，因此先與第4個元素進(jìn)展比較，然后和第2個元素進(jìn)展比較，最終和第3個元素進(jìn)展比較，所以共需要比較3次成功。.【答案】9【解析】依據(jù)哈希函數(shù)求得函數(shù)值為5,查找覺察沖突，依據(jù)二次探測再散列，分別將函數(shù)值+12、-12、+2、-2z“，并對表進(jìn)步行取余，進(jìn)展摸索。所以答案填9。.【答案】n(n-l)/2【解析】在有n個頂點的無向完全圖中，從每個頂點出去的邊有n-1條邊，但每條邊被用過2次，所以總邊數(shù)為n(n-l)/2。三、推斷題(本大題共5小題，每題1分，共5分).【答案】X【解析】算法的特性包含確定性。確定性就是指每條指令必需是確定的含義，不能產(chǎn)生二義性，并且，在任何條件下，算法只有唯一的一條執(zhí)行路徑，即對一樣的輸入只能得出一樣的輸出。.【答案】X【解析】線性表的鏈?zhǔn)酱鎯?gòu)造的存儲單元地址不要求連續(xù)，但是可以連續(xù)；而線性表的挨次存儲構(gòu)造肯定要求安排連續(xù)的存儲單元。.【答案】V【解析】隊列屬于特別的線性表，要求在表的一端進(jìn)展插入，在表的另一端進(jìn)程刪除，能夠插入的一端稱為隊尾，能夠刪除的一端稱為對頭。.【答案】X【解析】內(nèi)部排序指的是待排記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)展的排序過程，外部排序指的是待排記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)展訪問的排序過程。拓?fù)渑判虿粚儆趦?nèi)部排序。.【答案】V【解析】一棵樹轉(zhuǎn)化為二叉樹，其根結(jié)點肯定沒有右孩子，即該二叉樹沒有右子樹。只有2棵及以上的非空樹組成的森林轉(zhuǎn)化為二叉樹，才能使得對應(yīng)二叉樹有右子樹。四、綜合應(yīng)用題(本大題共3小題，每題5分，共15分)VlfV4fV5-V2-V3或VI—V2-V5-V4-V3或VlfV3-V2fV5-V4或VlfV3-V4-V5fV23.答：樹轉(zhuǎn)換為二叉樹為：其中該二叉樹的先序遍歷挨次為A,B,C,E,F,G,D五、算法設(shè)計(本大題共1五、算法設(shè)計(本大題共1小題，共10分)答：Linklistdelete(Linklist&L,Elemtypex){Linklistp,q;q=L;p=L->next; 〃初始化p指向第一個結(jié)點，q始終指向P結(jié)點的前驅(qū);while(p!=NULL){if(p->data==xwhile(p!=NULL){if(p->data==x){q->next=p->next;free(p);p=q->next;}else{q=P；

p=p->next;〃找到符合條件的結(jié)點;〃刪除該結(jié)點，并修改P指針;〃先使q后移，P向后移動。06C語言程序設(shè)計〔50分〕六、單項選擇題(在每題的四個備選答案中，選出一個正確的答案，并將其號碼填寫在題干后面的括號內(nèi)。每題1分，共15分)LC語言程序的根本單位是()A.程序行 B.語句C.函數(shù) D.字符.可用作C語言用戶標(biāo)識符的一組字符串是()A.voiddefineWORDB.a3_b3_123IFC.ForabcCaseD.2aDOsizeof.設(shè)inta=12,則執(zhí)行完語句a+=a-=a*a后，a的值是()A.552 B.264 C.144 D.-264.以下表達(dá)正確的選項是()A.do-while語句構(gòu)成的循環(huán)不能用其它語句構(gòu)成的循環(huán)來代替。B.do-while語句構(gòu)成的循環(huán)只能用break語句退出。C.用do-while語句構(gòu)成的循環(huán)，在while后的表達(dá)式為非零時完畢循環(huán)。D.用do-while語句構(gòu)成的循環(huán)，在while后的表達(dá)式為零時完畢循環(huán)。.設(shè)有說明int(*ptr)[10]其中的標(biāo)識符ptr是()A.10個執(zhí)行整型變量的指針B.指向10個整型變量函數(shù)指針C.一個指向具有10個整型元素的一維數(shù)組的指針D.具有10個指針元素的一維指針數(shù)組，每個元素都只能指向整型量.有以下程序段typedefstructNODE(intnum;structNODE*next;JOLD;則以下表達(dá)中正確的選項是()A.以上的說明形式非法 B.NODE是一個構(gòu)造體類型C.OLD是一個構(gòu)造體類型 D.OLD是一個構(gòu)造體變量.以下不能正確計算代數(shù)式值的C語言表達(dá)式是()A.l/3*sin(l/2)*sin(l/2) B.sin(O.5)*sin(O.5)/3C.pow(sin(0.5),2)/3 D.l/3.0*pow(sin(1.0/2),2).C語言規(guī)定，程序中各函數(shù)之間()A.既允許直接遞歸調(diào)用也允許間接遞歸調(diào)用B.不允許直接遞歸調(diào)用也不允許間接遞歸調(diào)用C.允許直接遞歸調(diào)用不允許間接遞歸調(diào)用D.不允許直接遞歸調(diào)用允許間接遞歸調(diào)用.在宏定義#definePI3.14159中，用宏名PI代替一個()A.單精度數(shù) B.雙精度數(shù)C.常量 D.字符串.在C語言中，要求運算數(shù)必需是整型的運算符是()A.% B./ C.< D.!.為表示關(guān)系x》y》z,應(yīng)使用的C語言表達(dá)式是()A.(x>=y)&&(y>=z) B.(x>=y)AND(y>=z)C.(x>=y>=z) D.(x>=y)&(y>=z).有以下程序段intk=0,a=3,b=4,c=5;k=a>c?c:k;執(zhí)行該程序段后，k的值是()A.3 B.2 C.l D.O.假設(shè)定義char*s="\\"Name\\Address\n",則指針s所指字符串的長度為()A.19 B.15 C.18 D.說明不合法.下述對C語言字符數(shù)組的描述中錯誤的選項是()A.字符數(shù)組可以存放字符串B.字符數(shù)組中的字符串可以整體輸入、輸出C.可以在賦值語句中通過賦值運算符對字符數(shù)組整體賦值D.不行以用關(guān)系運算符對字符數(shù)組中的字符串進(jìn)展比較.設(shè)有如下的函數(shù)exam(floatx){printf("\n%f)則函數(shù)的類型為()A.與參數(shù)x的類型一樣B.是voidC.是int D.無法確定七、閱讀以下程序，寫出其運行結(jié)果(每題5分，共25分)1、程序：main{inti,j,x;for(i=l;i<=4;i++){for(j=l;j<=4-i;j++)printf("")；for(j=0;j<=2*i+1;j++)printf(");printf(a\n")；))答案：2、程序：main{intk=3,n=0;while(k>0){switch(k){case1:n+=k;n+=k;default:break;)k—;)printf(<4%d\n”,n);)答案：3、程序：main{intij,row,column,m;staticintarray[3][3]={{100,200,300},{28,72,-30},{-850,2,6)};m=array[0][0];for(i=0;i<3;i++)for(j=0;j<3;j++)if(array[i][j]<m){m=array[i]|jl；row=i;column=j;}printf(w%d,%d,%d\n,m,row,column);)答案：4、程序#include<stdio.h>intp(intk,inta[]){intm,i,c=0;for(m=2;m<=k;m++)for(i=2;i<m;i++){if(!(m%i))break;if(i==m)a[c++]=m;)returnc;#defineMAXN20maininti,m,s[MAXN];m=p(13,s);for(i=O;i<m;i++)printf(u%4d"聞i]);printf(u\n");)答案：5.程序：intf(intn){if(n==0||n==1)return1;returnf(n-2)+2*f(n-l);)main{intn=5;printf(u%d“,f(5))；)答案：八、程序填空：按要求完成下面的程序(函數(shù))(每空2分，共10分).本函數(shù)用對分查找法，在以按字母次序從小到大排序的字符數(shù)組list中查找字符C,假設(shè)C在數(shù)組中，函數(shù)返回字符C在數(shù)組中的下標(biāo)，否則返回-1。intsearch(charlist||,charc,intlen){intlow.hige,k;low=0;high=len-l;while((1)){k=(low+high)/2;if((2))returnk;elseif(⑶)high=k-l;elselow=k+1;}retu