【正文】 均無分 。 (或無 )直接后繼 (第一個結(jié)點除外 )的數(shù)據(jù)結(jié)構(gòu)稱為 ，則最節(jié)省運算時間的存儲結(jié)構(gòu)是 1， 2， 3， … ， n，其輸出序列為 pl， p2， p3…. ， pn，若 p1 是 n，則 pi是 +l ，正 確的是 G 有 n 個結(jié)點，則它的邊的總數(shù)為 12 / 100 (n1) (n1)/2 D.(n1) 10 個度為 2 的結(jié)點， 5 個度為 1 的結(jié)點，則度為 0 的結(jié)點數(shù)是 ，在下面的 4 個序列中， 不符合 ． ． ． 深度優(yōu)先遍歷的序列是 ，排序算法時間復(fù)雜 度都是 O(n2)的排序方法是 G，要輸出其結(jié)點的有序序列，則采用的遍歷方法是 ISAM 和 VSAM 組織的文件都屬于 (15， 9， 7， 8， 20， 1， 4)進行排序，第一趟排序后的序列變?yōu)?(4， 9， 1， 8， 20，7， 15)，則采用的排序方法是 采用分塊查找時，數(shù)據(jù)的組織方式為 ，每塊內(nèi)數(shù)據(jù)有序 ，每塊中數(shù)據(jù)個數(shù)必須相同 ，每塊內(nèi)數(shù)據(jù)有序，塊間是否有序均可 ，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序 13 / 100 A.(00， 01， 10， 11) B.(0， 1， 00， 11) C.(0， 10， 110， 111) D.(1， 01， 000， 001) V[1..n]存儲，初始棧頂指針 top 為 n+l，則 x 進棧的正確操作是 =top1； V[top]=x [top]=x； top=top+1 =top+1； V[top]=x [top]=x； top=top1 head 為頭結(jié)點指針的非空單循環(huán)鏈表中，指針 p 指向鏈尾結(jié)點的條件是 data = 1 next = NULL next next=head next = head 二、填空題 (本大題共 10 小題，每小題 2 分，若有兩個空格，每個空格 1 分，共 20 分 )請在每個空格中填上正確答案。錯填、不填均無分。 ，與計算機無關(guān)的是 ______。 L=(a1,a2,… ， an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 ______。 50(序號從 0 到 49)，現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有① front=11， rear=29； ② front=29， rear=11；在這兩種情況下，循環(huán)隊列中的元素個數(shù)分別是 ______和 ______。 T 和 P 是兩個給定的串，在 T 中尋找等于 P 的子串的過程稱為 ______。 知三對角矩陣 A[10][10]的 每個元素占 2 個單元，現(xiàn)將其三條對角線上的元素逐行存儲在起始地址為 1000 的連續(xù)的內(nèi)存單元中，則元素 A[6][7] 的 地址為 ______。 (4， 5， 6， 7， 8)作為葉子結(jié)點的權(quán)值構(gòu)造哈夫曼樹，則其帶權(quán)路徑長度是 ______。 G 如圖所示，它的兩個拓撲排序序列分別為 ______和 ______。 14 / 100 (46， 79， 56， 38， 40， 84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為 ______。 A=(x， ((a， b)， c， ))，函數(shù) head(head(tail(A)))的運算結(jié)果是 ______。 ，也可以 ______。 三、解答題 (本大題共 4 小題，每小題 5 分，共 20 分 ) (26， 18， 60， 14， 7， 45， 13， 32)進行降序的堆排序，寫出構(gòu)建的初始堆 (小根堆 )及前兩趟重建堆之后序列狀態(tài)。 初始堆： 第一趟： 第二趟： H (key)=key ％ 11，散列地址空間為 010，對關(guān)鍵字序列 (27， 13， 55，32， 18， 49， 24， 38， 43)用線性探查法解決沖突，構(gòu)建散列表。現(xiàn)已有前 4 個關(guān)鍵字構(gòu)建的散列表如下所示，請將剩余 5 個關(guān)鍵字填入表中相應(yīng)的位置。 ： ABCDEFG 和 CBDAEGF，請畫出此二叉樹，并給出后序遍歷序列。 ，請畫出用普里姆算法從頂點 1 開始的最小生成樹的構(gòu)造過程。 四、算法閱讀題 (本大題共 4 小題，每小題 5 分，共 20 分 ) ，并回答下列問題： (1)簡述該算法的功能； (2)寫出分別輸入字 符串： abcba和 abcbde，調(diào)用算法函數(shù)的返回值。 15 / 100 int symmetry(void) { int i=0,j,k； . char str[80]； SeqStack s； InitStack(amp。s)； gets (str)； while (str[i]!= 39。＼ 039。) i++； for (j=0。ji/++) push(amp。s,str[j])； if (i％ 2!=0) k=i/2+1； else k=i／ 2； for (j=k。ji。j++) if (str[j]!=pop(amp。s)) return 0； return 1； } (1) (2) 遞減 ． ． 有序表 R 中插入元素 x，并保持表 R 的有序性。請在空缺處填入適當?shù)膬?nèi)容，使其成為一個完整的算法。 typedef struct { KeyType key； InfoTyep otherinfo； } RecType； typedef RecType SeqList [Maxlen] void BinInsert(SeqList R,int *n， RecType x) { int low=1， high=*n； int mid， i。 while (low=high) 16 / 100 { mid=(low+high)/2； if (R[mid].key) (1) ； else (2) ； } for (i=*n； i=low； i) R[i+1]=R[i]； (3) ； ++(*n)； } (1) (2) (3) ，并回答下列問題： (1)簡述該算法中標號 s1 所指示的循環(huán)語句的功能； (2)簡述該算法中標號 s2 所指示的循環(huán)語句的功能。 LinkList Insertmnode(LinkList head， char x， int m) { LinkNode*p， *q， *s。 int i。 char ch； p=headnext； s1： while (pamp。amp。pdata!=x) p=pnext； if (p==NULL)printf(error\n)； else { q=pnext； s2： for(i=1； i=m； i++) { s=(LinkNode *) malloc(sizeof(LinkNode))； scanf(％ c， amp。ch)； 17 / 100 sdata=ch； pnext=s； p=s； } pnext=q； } return head； } (1) (2) ，并回答下列問題： (1)該算法采用的是何種排序方法 ? (2)算法中的 R[n+1]的作用是什么 ? typedef struct { KeyType key； InfoType otherinfo； }RecType； typedef RecType SeqList[MaxLen]； void sort(SeqList R， int n) { //nMaxLen1 int k， i； for (k=n1。k=1。k) if (R[k].keyR[k+l].key) { R[n+1]=R[k]； for (i=k+1； R[i].keyR[n+1].key。i++) R[i1]=R[i]。 R[il]=R[n+1]； } 18 / 100 } (1) (2) 五、算法設(shè)計題 (本題 10 分 ) ，單鏈表的類型定義如下： typedef struct node { DataType data； Struct node *next； } LinkNode， * LinkList； 編寫算法，在一個頭指針為 head 且?guī)ь^結(jié)點的單鏈表中，刪除所有結(jié)點數(shù)據(jù)域值為 x 的結(jié)點。函數(shù)原型為： LinkList delnode (LinkList head， DataType x) 19 / 100 20 / 100 21 / 100 全國 2022 年 10月高等教育自學(xué)考試 數(shù)據(jù)結(jié)構(gòu)試題 課程代碼： 02331 一、單項選擇題（本大題共 15 小題，每小題 2 分，共 30 分） 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未 選均無分。 在數(shù)據(jù)的邏輯結(jié)構(gòu)中，樹結(jié)構(gòu)和圖結(jié)構(gòu)都是（ ） n 的順序表中插入一個元素的算法的時間復(fù)雜度為（ ） （ 1） （ log n） （ n） （ n2） p1 和 p2 分別指向兩個無頭結(jié)點的非空單循環(huán)鏈表中的尾結(jié)點，要將兩個鏈表鏈接成一個新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為（ ） －＞ next=p2－＞ next。p2－＞ next=p1－＞ next。 B. p2－＞ next=p1－＞ next。p1－＞ next=p2－＞ next。 C. p=p2－＞ next。 p1－＞ next=p。p2－＞ next=p1－＞ next。 D. p=p1－＞ next。 p1－＞ next= p2－＞ next； p2－＞ next=p。 ，入棧序列為 1， 2， 3， 4， 5， 6，若出棧序列為 2， 4， 3， 6， 5， 1，則操作過程中棧中元素個數(shù)最多時為（ ） 個 個 個 個 （ ） 在表的兩端進行插入和刪除 ，在另一端進行刪除 ﹟ define NodeSize 6 22 / 100 typedef struct node{ char data[NodeSize]。 struct node*next。 }LinkStrNode。 如果每個字符占 1 個字節(jié)，指針占 2 個字節(jié)，該鏈串的存儲密度為（ ） A=（ a,B,(a,B,(a,B,??）））的長度為（ ） 10 12 的二維數(shù)組 A，按“行優(yōu)先順序”存儲，每個元素占 1 個存儲單元，已知 A[1][1]的存儲地址為 420，則 A[5][5]的存儲地址為（ ） ，度為 2 的結(jié)點數(shù)為 15，度為 1 的結(jié)點數(shù)為 3，則葉子結(jié)點數(shù)為（ ） ，路徑長度是指（ ） 上各邊的權(quán)值之和 n 個頂點、 e 條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（ ） O（ n log n）時間復(fù)雜度進行穩(wěn)定的排序，可用的排序方法是（ ） 1000 個無序元素中盡快求得前 10 個最大元素，應(yīng)借用（ ） 23 / 100 ，元素比較的次數(shù)（ ） 表的長度和被查元素的位置有關(guān) （ ） 二、填空題（本大題共 10 小題，每小題 2 分，共 20 分） 請在每小題的空格中填上正確答案。錯填、不填均無分。 T（ n） =3n3200nlog2n+50n，則該算法的漸近時間復(fù)雜度為 __________. ，除了第 1 個元素結(jié)點外，任一結(jié)點的存儲位置均由 _____________指示。 __________的原則進行。 __________。 10 階的上三角矩陣 A 按行優(yōu)先順序壓縮存儲在一維數(shù)組 B 中，若矩陣中的第一個元素 a11 在 B 中的存儲位置 k=0，則元素 a55 在 B 中的存儲位置 k=__________。 n 個結(jié)點的嚴格二叉樹中，度為 1 的結(jié)點個數(shù)為 __________。 ，采用 __________表示法較為節(jié)省存儲空間。 ，如果 _____________，則稱其為外部排序。 ｛ 19， 14， 23， 1， 68， 12， 10， 78， 25｝，用鏈地址法構(gòu)造散列表，散列函數(shù)為 h（ key） =key％ 11,散列地址為 1 的鏈中有 __