【正文】 考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺 ......... 俱樂部名稱：自考樂園 。俱樂部 id： 5346389（請牢記它哦 ~在百度貼吧的搜索框中輸入俱樂部 id，可以直接進入俱樂部） 。俱樂部 url 地址： url 進入俱樂部。） (4)p=pnext 五、算法設(shè)計題 (本題 10 分 ) A=(a1,a2,a3,?,an) 以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。編寫一個函數(shù)，對 A 進行調(diào)整，使得當 n 為奇數(shù)時 A=(a2,a4,?,an 1,a1,a3,?,an) ，當 n 為偶數(shù)時 A=(a2,a4,?,an,a1,a3,?,an 1)。 typedef struct node { int x。 struct node *next。 } NODE。 typedef NODE * LinkList。 void adjust( LinkList header ) { NODE *pTmp = header。 //用來保存偶數(shù)鏈表尾指針 NODE *pCur = headernext。 //鏈表遍歷指針 NODE *pOddHdr = headernext。//奇數(shù)鏈表頭指針 NODE *pOddTail = headernext。//奇數(shù)鏈表尾指針 int bIsOdd = true。 //奇數(shù)結(jié)點標志，第一個結(jié)點是奇數(shù)結(jié)點 if( NULL == pCur )//空鏈表，不需要處理 return。 while( pCurnext != NULL )//從第二 個結(jié)點開始遍歷 { pCur = pCurnext。 bIsOdd = !bIsOdd。 if( bIsOdd ) //（這步錯誤，未將原鏈表的接點連接） {//奇數(shù)結(jié)點，加入奇數(shù)鏈表表尾 pOddTailnext = pCur。 pOddTail = pCur。 } else {//偶數(shù)結(jié)點，加入偶數(shù)鏈表表尾 pTmpnext = pCur。 pTmp = pCur。 } } pOddTailnext = NULL。//奇數(shù)鏈表表尾結(jié)點的 next 置空 pTmpnext = pOddHdr。//奇數(shù)鏈表插入偶數(shù)鏈表表尾（這步錯誤，未考慮最后接點的奇偶性。） ☆ 自考樂園 心境隨緣，誠與天下自考人共勉?。?！ ☆ 自考樂園 分享快樂，你的快樂老家?。?！ ☆ 自考樂園 引領(lǐng)成功，你的 精神樂園?。。? ☆ 自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺 ......... 俱樂部名稱：自考樂園 。俱樂部 id： 5346389（請牢記它哦 ~在百度貼吧的搜索框中輸入俱樂部 id，可以直接進入俱樂部） 。俱樂部 url 地址： url 進入俱樂部。） return。 } 全國 2022 年 1 月高等教育自學考試 數(shù)據(jù)結(jié)構(gòu)試題 課程代碼： 02331 一、單項選擇題（本大題共 15 小題，每小題 2 分，共 30分） 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。 1．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成（ ） A．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B．線性結(jié)構(gòu)和非線性結(jié)構(gòu) C．緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu) D．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) 2．在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（ ） A．數(shù)據(jù)元素的相鄰地址表示 B．數(shù)據(jù)元素在表中的序號表示 C．指向后繼元素的指針表示 D．數(shù)據(jù)元素的值表示 3．設(shè) p 指向單鏈表中的一個結(jié)點， s 指向待插入的結(jié)點，則下述程序段的功能是（ ） s next = p next。 p next = s。 t = p data。 p data = s data。 s data = t。 A．結(jié)點 *p 與結(jié)點 *s 的數(shù)據(jù)域互換 B．在 p 所指結(jié)點的元素之前插入元素 C．在 p 所指結(jié)點的元素之后插入元素 D．在結(jié)點 *p 之前插入結(jié)點 *s 4．棧和隊列都是（ ） A．限制存取位置的線性結(jié)構(gòu) B．順序存儲的線性結(jié)構(gòu) C．鏈式存儲的線性結(jié)構(gòu) D．限制存取位置的非線性結(jié)構(gòu) 5．若數(shù)組 s[0..n1]為兩個棧 s1 和 s2 的共用存儲空間，且僅當 s[0..n1]全滿時，各棧才不能進行進棧操作，則為這兩個棧分配空間的最佳方案是： s1 和 s2 的棧頂指針的初值分別為（ ） A． 1 和 n+1 B． 1 和 n/2 C．－ 1 和 n D．－ 1 和 n+1 6．執(zhí)行下列程序段后，串 X 的值為（ ） S=〞 abcdefgh〞 。 T=〞 xyzw〞 。 substr (X,S,2,strlen(T))。 substr (Y,S, stelen(T),2)。 strcat (X,Y)。 A．〞 cdefgh〞 B．〞 cdxyzw〞 C．〞 cdefxy〞 D．〞 cdefef〞 ☆ 自考樂園 心境隨緣，誠與天下自考人共勉?。?！ ☆ 自考樂園 分享快樂，你的快樂老家！?。?☆ 自考樂園 引領(lǐng)成功，你的 精神樂園！??！ ☆ 自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺 ......... 俱樂部名稱：自考樂園 。俱樂部 id： 5346389（請牢記它哦 ~在百度貼吧的搜索框中輸入俱樂部 id，可以直接進入俱樂部） 。俱樂部 url 地址： url 進入俱樂部。） 7．多維數(shù)組之所以有行優(yōu)先順 序和列優(yōu)先順序兩種存儲方式是因為（ ） A．數(shù)組的元素處在行和列兩個關(guān)系中 B．數(shù)組的元素必須從左到右順序排列 C．數(shù)組的元素之間存在次序關(guān)系 D．數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu) 8．從廣義表 LS＝（ (p, q), r, s）中分解出原子 q 的運算是（ ） A． tail (head (LS)) B． head (tail (head (LS))) C． head (tail (LS)) D． tail (tail (head (LS))) 9．在具有 n 個葉子結(jié)點的嚴格二叉樹中，結(jié)點總數(shù)為（ ） A． 2n+1 B． 2n C． 2n1 D． 2n2 10．若 vi, vj是有向圖的一條邊，則稱（ ） A． vi 鄰接于 vj B． vj 鄰接于 vi C． vi 和 vj 相互鄰接 D． vi 與 vj172。不相鄰接 11．在一個帶權(quán)連通圖 G 中，權(quán)值最小的邊一定包含在 G 的（ ） A．最小生成樹中 B．深度優(yōu)先生成樹中 C．廣度優(yōu)先生成樹中 D．深度優(yōu)先生成森林中 12．當在二叉排序樹中插入一個新結(jié)點時，若樹中不存在與待插入結(jié)點的關(guān)鍵字相同的結(jié)點，且新結(jié)點的關(guān)鍵 字小于根結(jié)點的關(guān)鍵字，則新結(jié)點將成為（ ） A．左子樹的葉子結(jié)點 B．左子樹的分支結(jié)點 C．右子樹的葉子結(jié)點 D．右子樹的分支結(jié)點 13．希爾排序的增量序列必須是（ ） A．遞增的 B．隨機的 C．遞減的 D．非遞減的 14．如果在排序過程中，每次均將一個待排序的記錄按關(guān)鍵字大小加入到前面已經(jīng)有序的子表中的適當位置，則該排序方法稱為（ ） A．插入排序 B．歸并排序 C．冒泡排序 D．堆排序 15．設(shè)置溢出區(qū)的文件是（ ） A．索引非順序文 件 B． ISAM 文件 C． VSAM 文件 D．順序文件 二、填空題（本大題共 10 小題，每小題 2 分，共 20 分） 請在每小題的空格中填上正確答案。錯填、不填均無分。 16．下列程序段的時間復(fù)雜度為 _O(n^2)_ product = 1。 for (i = n。i0。 i) for (j = i+1。 jn。 j++) product *=j。 17．已知指針 p 指向單鏈表中某個結(jié)點，則語句 p next =p next next 的作用是 ________________。 刪除 *P 的直接后繼結(jié)點 18．假設(shè)元素只能按 a,b,c,d 的順序依次進棧，且得到的出棧序列中的第一個元素為 c，則可能得到的出棧序列為 ________________，不可能得到的出棧序列為 ________________ 1)cbad, cbda, cdba 2)cabd, cadb, cdab ☆ 自考樂園 心境隨緣，誠與天下自考人共勉?。?！ ☆ 自考樂園 分享快樂，你的快樂老家?。。?☆ 自考樂園 引領(lǐng)成功，你的 精神樂園?。?！ ☆ 自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺 ......... 俱樂部名稱：自考樂園 。俱樂部 id： 5346389（請牢記它哦 ~在百度貼吧的搜索框中輸入俱樂部 id，可以直接進入俱樂部） 。俱樂部 url 地址： url 進入俱樂部。） 19．若鏈串結(jié)點中的指針占 4 個字節(jié)，每個字符占 1 個字節(jié)，則結(jié)點大小為 2 的鏈串的存儲密度為 ________________。 2 / ( 4 + 2 ) = 1/3 20．右圖表示的廣義表為 ________________。 [img]/ [img] ( ( e ), ( ( e ), ( b, c ) ), ( L ) ) 21．若一棵滿三叉樹中含有 121 個結(jié)點，則該 樹的深度為 ________________。 5 // ( 3^5 1 ) / ( 3 1 ) = 121 22．若以鄰接矩陣表示有向圖，則鄰接矩陣上 第 i 行中非零元素的個數(shù)即為頂點 vi 的 ________________。 出度 23．若希望只進行 8 趟排序便能在 4800 個元素中找出其中值最小的 8 個元素，并且要求排序過程中所進行的關(guān)鍵字比較次數(shù)盡可能少，則應(yīng)該 選用 ________________排序方法。 24．在含 20 個關(guān)鍵字的 3 階 B 樹（ 2－ 3 樹）上查找一個關(guān)鍵字，至多需要訪問 ___________次外存。 25．文件上的兩類主要操作為 ________________和 ________________。 檢索 和 維護 三、解答題（本大題共 4 小題，每小題 5 分，共 20 分） 26．設(shè)棧 S1 的入棧序列為 1 2 3 4（每個數(shù)字為 13 個元素），則不可能得到出棧序列 3142。但可通過增設(shè)棧 S2 來實現(xiàn)。例如，按下圖中的箭頭指示，依次經(jīng)過棧 S1 和 S2，便可得到序列3 1 4 2。 如果用 H1 和 H2 分別表示棧 S1 和 S2 的進棧操作，用 P1 和 P2 分別表示兩個棧的出棧操作，則得到 3 1 4 2 的一個操作步驟 為 H1， H1， H1， P1， H2， P2， P1， H2， P1， H2， P2， H1， P1， H2， P2， P2 請仿照上例寫出利用兩個棧從 1 2 3 4 得到 4 1 3 2 的操作步驟。 H1,P1,H2,H1,H1,H1,P1,H2,P2,P2,P1,H2,P2,P1,H2,P2 ☆ 自考樂園 心境隨緣，誠與天下自考人共勉?。?！ ☆ 自考樂園 分享快樂，你的快樂老家?。?！ ☆ 自考樂園 引領(lǐng)成功，你的 精神樂園！?。? ☆ 自考樂園俱樂部，專注于自考，致力于成為全國最全，最優(yōu)的自考學習交流，資料共享平臺 ......... 俱樂部名稱：自考樂園 。俱樂部 id： 5346389（請牢記它哦 ~在百度貼吧的搜索框中輸入俱樂部 id，可以直接進入俱樂部） 。俱樂部 url 地址： url 進入俱樂部。） 27．已知樹如右圖所示， （ 1）寫出該樹的后序序列； （ 2）畫出由該樹轉(zhuǎn)換得到的二叉樹。 1) EBJKFGHICDA 2) 樹變二叉樹 :兄弟相連 ,保留長子的連線 . A . / . B . / \\ . E C . / \\ . F D . / \\ . J G . \\ \\ . K H . \\ . I 28．為關(guān)鍵字（ 17， 33， 31， 40， 48）構(gòu)造一個長度為 7 的散列表，設(shè)散列函數(shù)為 h(key)=key%7,用開放定址法解決沖突的探查序列是 hi = (h(key) + i(key%5+1))%7