2024年高等教育工學類自考-02331數據結構歷年高頻考點試卷專家薈萃含答案（圖片大小可自由調整）第1卷一.參考題庫(共25題)1.下列排序方法中，哪一種方法的比較次數與紀錄的初始排列狀態無關（）A、直接插入排序B、起泡排序C、快速排序D、直接選擇排序2.在單鏈表中，NULL稱為（），它不指向任何結點，只起（）作用。3.數據的存儲結構是數據的邏輯結構的存儲映象。4.下面關于線性表的敘述錯誤的是（）A、線性表采用順序存儲必須占用一片連續的存儲空間B、線性表采用鏈式存儲不必占用一片連續的存儲空間C、線性表采用鏈式存儲便于插入和刪除操作的實現D、線性表采用順序存儲便于插入和刪除操作的實現5.下面敘述中，不正確的是（）。A、線性表中除第一個元素和最后一個元素外，其他每個元素都有且僅有一個直接前驅和一個直接后繼B、樹中有且僅有一個結點沒有前驅C、環形隊列中任何一個元素都有且僅有一個直接前驅和一個直接后繼D、在樹中，一個結點可以有多個直接后繼6.一棵二叉樹，有1個2度結點，，2個1度結點，則該樹共有（）個結點。7.建立一個長度為n的有序單鏈表的時間復雜度為（） A、AB、BC、CD、D8.若對n個元素進行直接插入排序，在進行第i趟排序時，假定元素r[i+1]的插入位置為r[j]，則需要移動元素的次數為（）。A、j-iB、i-j-1C、i-jD、i-j+19.把下列森林轉換為二叉樹。 10.簡述歸并排序的處理步驟。11.用數組Q表示一個環形隊列，f為當前對頭元素的錢一位置，r為隊尾元素的位置。假定隊列中元素個數總小于n，求隊列中元素個數公式是（）。12.對于一個具有n個結點的單鏈表，已知一個結點的指針p，在其后插入一個新結點的時間復雜度為（）；若已知一個結點的值為x，在其后插入一個新結點的時間復雜度為（）13.研究數據結構就是研究（）。A、數據的邏輯結構B、數據的存儲結構C、數據的邏輯結構和存儲結構D、數據的邏輯結構、存儲結構及其基本操作14.假設在算法描述語言中引入指針的二元運算“異或”，若a和b為指針，則a⊕b的運算結果仍為原指針類型，且a⊕（a⊕b）=（a⊕a）⊕b=b；（a⊕b）⊕b=a⊕（b⊕b）=a。則可利用一個指針域來實現雙向鏈表L。鏈表L中的每個結點只含兩個域：data域和LRPtr域，其中LRPtr域存放該結點的左鄰與右鄰結點指針（不存在時為NULL）的異或。若設指針L.Left指向鏈表中的最左結點，L.Right指向鏈表中的最右結點，則可實現從左向右或從右向左遍歷此雙向鏈表的操作。試寫一算法按任一方向依次輸出鏈表中各元素的值。15.在對一組記錄（50，40，95，20，15，70，60，45，80）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較（）次。16.已知一無向圖G=（V，E），其中V={a，b，c，d，e}E={（a，b），（a，d），（a，c），（d，c），（b，e）}現用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是（）方法。17.下列圖的深度優先遍歷序列為（）。 A、ABCDEFGHB、ABDHECFGC、ABEDHCFGD、ABCFGEDH18.數組是同類型值的集合。19.無向圖中，兩頂點之間有邊則互為（）。A、鄰接點B、兄弟C、堂兄弟D、鄰居20.線性表的鏈接存儲結構是一種（）存儲結構。A、?隨機存取B、?順序存取C、?索引存取D、?散列存取21.對一個連通圖進行一次深度優先搜索可以遍訪圖中的所有頂點。22.當結點之間存在M對N（M：N）的聯系時，稱這種結構為（）23.如果要將序列（50，16，23，68，94，70，73）建成堆，只需把16與（）交換。24.下列選項中是結構體普通變量或指針變量引用其成員時使用時的符號的是（）。A、->符號B、.符號C、->>符號D、#符號25.在長度為n的循環隊列中，刪除其節點為x的時間復雜度為（）。第2卷一.參考題庫(共25題)1.一個隊伍的入隊列是1234，則隊列的輸出順序是（）。2.查找3.在只有度為0和度為k的結點的k叉樹中，設度為0的結點有n0個，度為k的結點有nk個，則有n0=nk+1。4.利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（） A、AB、BC、CD、D5.樹的后根遍歷序列等同于與該樹對應的二叉樹的哪種序列？（）A、?前序序列B、?中序序列C、?后序序列D、?層序序列6.數據結構里，函數參數為哪項時，參數傳遞屬于值傳遞。（）A、數組B、指針C、字符數組D、int型7.數據結構里，結構體數組，即定義數組的每個元素都是一個結構體類型的。8.數據結構里，邏輯結構和存儲結構指的是同一件事。9.在一個具有n個頂點和e條邊的有向圖的鄰接表中，保存頂點單鏈接的表頭指針向量大小至少為（）A、nB、2nC、eD、2e10.數據結構是研討數據的（）和（），以及它們之間的相互關系，并對與這種結構定義相應的（），設計出相應的（）11.在隊列中，下列說法正確的是（）。A、每次插入總是在隊尾，每次刪除總是在隊頭B、每次插入總是在隊尾，每次刪除也總是在隊尾C、每次插入總是在隊頭，每次刪除也總是在隊頭D、每次插入總是在隊頭，每次刪除總是在隊尾12.對平衡二叉樹進行中根遍歷，可得到結點的有序序列。13.設計判斷單鏈表中元素是否是遞增的算法。14.算法和程序原則上沒有區別，在討論數據結構時二者是通用的。15.假定對長度n=50的有序表進行二分查找，則對應的判定樹高度為（），判定樹中前5層的結點數為（），最后一層的結點數為（）。16.在一個順序棧中，若棧頂指針等于（），則為空棧；若棧頂指針等于（），則為滿棧。17.下面程序段的時間復雜度為（） 18.廣義表19.連續存儲設計時，存儲單元的地址（）A、一定連續B、一定不連續C、不一定連續D、部分連續，部分不連續20.數據結構被形式地定義為＜D，R＞，其中R是（）的有限集。A、算法B、數據元素C、數據操作D、邏輯結構21.假定一個待哈希存儲的線性表為（32，75，29，63，48，94，25，46，18，70），哈希地址空間為HT[13]，若采用除留余數法構造哈希函數和線性探測法處理沖突，試求出每一元素在哈希表中的初始哈希地址和最終哈希地址，畫出最后得到的哈希表，求出平均查找長度。 22.以下與數據的存儲結構無關的術語是（）。A、循環隊列B、鏈表C、哈希表D、棧23.具有n個頂點的有向無環圖最多有多少條邊？24.在雙向循環鏈表中，在p指針所指的結點后插入一個指針q所指向的新結點，修改指針的操作是（）。A、p->next=q；q->prior=p；p->next->prior=q；q->next=q；B、p->next=q；p->next->prior=q；q->prior=p；q->next=p->next；C、q->prior=p；q->next=p->next；p->next->prior=q；p->next=q；D、q->next=p->next；q->prior=p；p->next=q；p->next=q；25.根據使用頻率為5的字符設計的哈夫曼編碼不可能是（）A、0，100，101，110，111B、0000，0001，001，01，1C、000，001，010，011，11D、00，01，10，110，111第3卷一.參考題庫(共25題)1.如果只想得到一個序列中第k個最小元素之前的部分排序序列，最好采用什么排序方法？為什么？對于序列{57，40，38，11，13，34，48，75，25，6，19，9，7}，得到其第4個最小元素之前的部分序列{6，7，9，11}，使用所選擇的排序算法時，要執行多少次比較？2.順序隊的“假溢出”是怎樣產生的？如何知道循環隊列是空還是滿？3.下面算法的時間復雜度為（） A、O（1）B、O（n）C、O（n2）D、O（n!）4.（）方法是對序列中的元素通過適當的位置交換將有關元素一次性地放置在其最終位置上。5.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的三項信息是（）、（）、（）。6.稀疏多項式采用的循環鏈表存儲結構LinkedPoly定義為： 試以循環鏈表作稀疏多項式的存儲結構，編寫求其導函數的方法，要求利用原多項式中的結點空間存放其導函數多項式，同時釋放所有無用結點。7.算法分析的兩個主要方面是（）。A、空間復雜度和時間復雜度B、正確性和簡單性C、可讀性和文檔性D、數據復雜性和程序復雜性8.帶權連通圖的最小生成樹的權值之和一定小于它的其它生成樹的權值之和。9.設無向圖G（如圖所示），給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。 10.如果將所有中國人按照生日來排序，則使用（）算法最快。A、歸并排序B、希爾排序C、快速排序D、基數排序11.若串S＝‘software’，其子串的數目是（）。A、8B、37C、36D、912.已知函數定義如下：intfun（inta[]） { ......；//函數體省略 }則該函數的參數傳遞屬于（）。A、值傳遞B、地址傳遞C、形參傳遞D、實參傳遞13.設計算法，將一個無向圖的鄰接表轉換成鄰接矩陣。14.在平衡二叉樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并已知A的左孩子的平衡因子為0右孩子的平衡因子為1，則應作（）型調整以使其平衡。A、LLB、LRC、RLD、RR15.對于一個有向圖，若一個頂點的度為k1，出度為k2，則對應鄰接表中該頂點單鏈表中的邊結點數為（）。A、?k1B、?k2C、?k1-k2D、?k1+k216.數據結構里，B有6個兄弟（不算自己），A是B的雙親，則A的度是（）。A、3B、6C、7D、817.線性表在物理存儲空間中也一定是連續的。18.如果有向圖中各個頂點的度都大于2，則該圖中必有回路。19.已知一組元素的排序碼為： （46，74，16，53，14，26，40，38，86，65，27，34）利用歸并排序的方法寫出每一趟二路歸并排序后的結果。20.什么叫二維數組的行序優先存儲？什么叫二維數組的列序優先存儲？21.集合與線性表的區別在于是否按關鍵字排序22.已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷的結果為（）A、CBEFDAB、FEDCBAC、CBEDFAD、不定23.寫出快速排序的非遞歸調用算法。24.廣義表（（a），a）的表尾是（）25.一組記錄的關鍵字序列為（12，45，22，4，6，50），利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為（）A、6，4，12，45，22，50B、6，4，12，22，45，50C、6，4，12，50，22，45D、4，6，12，22，45，50第1卷參考答案一.參考題庫1.參考答案:D2.參考答案:空指針；標志3.參考答案:正確4.參考答案:D5.參考答案:C6.參考答案:57.參考答案:C8.參考答案:D9.參考答案:10.參考答案:歸并排序的處理步驟為： A.記錄分段處理：將文件中的記錄按照可用內存大小劃分為若干段，依次將每段記錄讀入到內存中對其進行內部排序，并將排序結果輸出到子文件中。這樣可以生成多個有序的子文件（即文件內的記錄是有序的），通常稱經過排序后的段為初始歸并段。 B.文件歸并處理：對上一步得到的初始歸并段加以歸并，直至將多段中的記錄歸并為一個有序文件為止。11.參考答案:（r-f+n）%n12.參考答案:O（1）；O（n）13.參考答案:D14.參考答案:15.參考答案:316.參考答案:深度遍歷17.參考答案:B18.參考答案:錯誤19.參考答案:A20.參考答案:A21.參考答案:正確22.參考答案:網狀結構23.參考答案:5024.參考答案:A,B25.參考答案:O(n)第2卷參考答案一.參考題庫1.參考答案:1、2、3、42.參考答案:根據給定的關鍵字值，在特定的表中，確定一個其關鍵字與給定值相同的數據元素，并返回該數據元素在列表中的位置。這個過程叫查找。3.參考答案:錯誤4.參考答案:C5.參考答案:B6.參考答案:D7.參考答案:正確8.參考答案:錯誤9.參考答案:A10.參考答案:邏輯結構；物理結構；操作（運算）；算法11.參考答案:A12.參考答案:正確13.參考答案:14.參考答案:錯誤15.參考答案:6；31；1916.參考答案:–1；StackMaxSize-117.參考答案:O(n)18.參考答案:廣義表簡稱表，是零個或多個原子表所組成的有限序列。19.參考答案:A20.參考答案:C21.參考答案:22.參考答案:D23.參考答案:具有n個頂點的有向無環圖最多有n×（n—1）/2條邊。 這是一個拓撲排序相關的問題。—個有向無環圖至少可以排出一個拓撲序列，不妨設這n個頂點排成的拓撲序列為v1，v2，v3，?，vn，那么在這個序列中，每個頂點vi只可能與排在它后面的頂點之間存在著以vi為弧尾的弧，最多有n-i條，因此在整個圖中最多有（n-1）+（n-2）+?+2+1=n×（n-1）/2條邊。24.參考答案:C25.參考答案:C第3卷參考答案一.參考題庫1.參考答案:采用堆排序最合適，依題意可知只需取得第k個最小元素之前的排序序列時，堆排序的時間復雜度Ο（n+klog2n），若k≤nlog2n，則得到的時間復雜性是Ο（n）。 對于上述序列得到其前4個最小元素，使用堆排序實現時，執行的比較次數如下：初始建堆：比較20次，得到6； 第一次調整：比較5次，得到7； 第二次調整：比較4次，得到9； 第三次調整：比較5次，得到11。2.參考答案:一般的一維數組隊列的尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還有空位置，這就叫“假溢出”。 采用循環隊列是解決