24年10月自考13003數(shù)據(jù)結(jié)構(gòu)與算法試題及答案

絕密★考試結(jié)束前2024年10月高等教育自學(xué)考試一、單項選擇題：本大題共15小題，每小題2分，共 A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.p->next=s;s->next=q;D.q->next=s;s->next=p;A.3A.f,e,g,d,a,c,bB.c,d,b,e,f,a,gC.e,f,d,g,c,b,aD.d,e,c,f,b,g,a浙13003#數(shù)據(jù)結(jié)構(gòu)與算法試題第1頁(共5頁)6.若以1,2,3,4作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得A.1,2,3,4C.4,2,3,1D.4,A.(g)B.(d)C.c8.若串S="software",其子串的數(shù)目是A.89.帶頭結(jié)點的單鏈表的頭指針為head,表為空的判定條件是A.head==NULL;B.head->nC.head!=NULL;D.head->next==heaA.稀疏矩陣的所有零元素及其位置C.三元組線性表元素之間的關(guān)系11.對n個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為A.(n+1)/2C.nD.(1+12.某二叉樹的先序遍歷序列是abdgcefh,中序遍歷序列是dgbaechf,則其后序遍歷A.gdbehfcaB.abcdefghC.gdbaefchD.ghbcdefa13.在一個具有n個頂點的有向圖中，所有頂點的出度之和為d,則所有頂點的入度A.nA.以順序方式存儲B.以順序方式存儲且元素有序C.以鏈?zhǔn)椒绞酱鎯.以鏈?zhǔn)椒绞酱鎯η以赜行駻.希爾排序B.堆排序C.選擇排序D.歸并排序浙13003#數(shù)據(jù)結(jié)構(gòu)與算法試題第2頁(共5頁)17.設(shè)順序表的每個元素占8個存儲單元。若第1個元素的存儲首地址為100,則第22.一棵二叉樹共有20個結(jié)點，其中葉結(jié)點為5個，則度為1的結(jié)點的個數(shù)是24.若用起泡排序方法對序列11,15,27,29,42,53進行降序排序，則需要進行 浙13003#數(shù)據(jù)結(jié)構(gòu)與算法試題第3頁(共5頁)}(1)設(shè)線性表L=(19,-6,-9,26,0,-21,74,35,-30),寫出執(zhí)行func(&L(2)簡述算法func的功能。typedefintKeyType;typedefstructNodeType;typedefNodeTypeSqList[MAXLEN];if(R[m].key==X.key)elsereturnfunc(R,X,m+1,q);浙13003#數(shù)據(jù)結(jié)構(gòu)與算法試題第4頁(共5頁)(1)若順序表R的關(guān)鍵字序列為(3,6,15,28,53,70,115),分別寫出X.key=19(2)簡述算法func的功能。j=i-1;j=j-1;}}typedefstructnode浙13003#數(shù)據(jù)結(jié)構(gòu)與算法試題第5頁(共5頁)數(shù)據(jù)結(jié)構(gòu)與算法試題答案及評分參考24.1526.①計算哈希函數(shù)所需的時間。(1分)②關(guān)鍵字的長度。(1分)③哈希表的大小。(1分)④關(guān)鍵字的分布情況。(1分)⑤記錄的查找頻率。(1分)27.①輸入：有0或多個輸入值。(1分)②輸出：有1或多個輸出值。(1分)個數(shù)為n×n。(1分)無向圖的鄰接矩陣是對稱矩陣，對于G中的任一條邊，在鄰接矩陣中都會對應(yīng)兩個1,即A[i][j]和A[j][i]均為1。(1分)所以，圖G的鄰接矩陣中有2e個1,(1分)0的個數(shù)為n×n-2e。(2分)pop(2),pop(1),.(1分)push(3),push(4),(1分)30.①|(zhì)|(1分)②ERROR(1分)31.①L=(19,26,0,74,35)(3分)32.①-1;(1分)3(1分)中的位置(或下標(biāo)),(1分)否則返回-1。(1分)33.①直接插入排序；(2分)該算法穩(wěn)定。(1分){if(root!=NULL)