2010年全國自考數(shù)據(jù)結構模擬試卷(二)及答案

《2010年全國自考數(shù)據(jù)結構模擬試卷(二)及答案》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、2010年全國自考數(shù)據(jù)結構模擬試卷(二)一、單項選擇題(本大題共15小題,每小題2分,共30分)在每小題列出的四個備選項目中只有一個是符號題目要求的,請將其代碼填寫的括號內.錯選、多選或未選均無分。1.非空的循環(huán)單鏈表head的尾結點(由指針p所指)滿足()A.p->next=NULLB.p=NULLC.p->next=headD.p=head答案：C2.鄰接表存儲結構下圖的深度優(yōu)先遍歷算法結構類似于二叉樹的()A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷答案：A3.設圖G采用鄰接表存儲，則拓撲

2、排序算法的時間復雜度為()A.O(n)B.O(n+e)C.O(n2)D.O(n×e)答案：B4.在Hash函數(shù)H(k)＝kMODm中，一般來講，m應取()A.奇數(shù)B.偶數(shù)C.素數(shù)D.充分大的數(shù)答案：C5.對于一個具有N個頂點的圖，如果我們采用鄰接矩陣法表示，則此矩陣的維數(shù)應該是()A.(N-1)×(N-1)B.N×NC.(N+1)×(N+1)D.不確定答案：B6.快速排序在最壞情況下的時間復雜度是()A.AB.BC.CD.D答案：B7.已知一個單鏈表中有3000個結點，每個結點存放一個整數(shù)，()可

3、用于解決這3000個整數(shù)的排序問題且不需要對算法作大的變動。A.直接插入排序方法B.簡單選擇排序方法C.快速排序方法D.堆排序方法答案：D8.設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結構最佳。A.線性表的順序存儲結構B.棧C.隊列D.線性表的鏈式存儲結構答案：B9.順序存儲結構()A.僅適合于靜態(tài)查找表的存儲B.僅適合于動態(tài)查找表的存儲C.既適合靜態(tài)又適合動態(tài)查找表的存儲D.既不適合靜態(tài)又不適合動態(tài)查找表的存儲答案：C10.用二分查找法對具有n個結點的線性表查找一個結點所需的平

4、均比較次數(shù)為()A.AB.BC.CD.D答案：D11.與其他查找方法相比，哈希查找法的特點是()A.通過關鍵字比較進行查找B.通過關鍵字計算記錄存儲地址進行查找C.通過關鍵字計算記錄存儲地址，并進行一定的比較進行查找D.通過關鍵字記錄數(shù)據(jù)進行查找答案：C12.倒排文件的主要優(yōu)點是()A.便于進行插入和刪除運算B.便于進行文件的合并C.能大大提高基于非關鍵碼數(shù)據(jù)項的查找速度D.能大大節(jié)省存儲空間答案：C13.設數(shù)組A［0，m］作為循環(huán)隊列sq的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行

5、入隊操作的語句是()A.sq.front=(sq.front+1)%mB.sq.front=(sq.front+1)%(m+1)C.sq.rear=(sq.rear+1)%mD.sq.rear=(sq.rear+1)%(m+1)答案：D14.串是一種特殊的線性表，其特殊性體現(xiàn)在()A.可順序存儲B.數(shù)據(jù)元素是一個字符C.可鏈接存儲D.數(shù)據(jù)元素可以是多個字符答案：B15.深度為k的二叉樹，所含葉子的個數(shù)最多為()A.AB.BC.CD.D答案：C二、填空題（本大題共10小題，每小題2分，共20分）請在每

6、小題的空格中填寫上正確答案。錯填、不填均無分。1.從樹的根結點到樹中的其余結點之間的路徑___惟一的。答案：是2.查找表中主關鍵字指的是___，次關鍵字指的是___。答案：能惟一標識數(shù)據(jù)元素的數(shù)據(jù)項不能惟一標識數(shù)據(jù)元素的數(shù)據(jù)項3.___的有向圖，其全部頂點有可能排成一個拓撲序列。答案：存在入度為0的結點且沒有回路4.如果一個圖中有n條邊，則此圖的生成樹含有___條邊，所以生成樹是圖的邊數(shù)___的連通圖。答案：n-1最少5.在散列技術中，處理沖突的方法有：___和___。答案：開放定址法拉鏈法6.對于

7、一個長度為n的線性表，假設表中各結點的查找概率相同，則在查找成功的情況下，平均查找長度為___，如果k不在表中，則需要進行___次比較后才能確定查找失敗。答案：(n+1)/2n+17.查找表按其所包括的運算的不同分為___查找表和___查找表。答案：靜態(tài)動態(tài)8.給定一個具有n個元素的向量，建立一個有序單鏈表的時間復雜度是___。答案：9.設線性表(a1,a2，…，a500)元素的值由小到大排列。對一個給定的k值，用二分法檢索查找表中與k相等的元素，在檢索不成功的情況下，至多需比較___次。答案：91

8、0.設有一元多項式A(x)＝7+3x+10x30-4x100+13x101，用單鏈表給出A(x)的存儲表示為___。答案：三、解答題（本大題共4小題，每小題5分，共20分）1.已知串S=‘(xyz)*’,t=‘(x+z)*y’,試利用串的基本運算將s串轉化為t串，t串轉化為s串。答案：t=CONCAT(Rep(sup(s,1,5),‘y’,‘+’),Rep(sub(s,6,1),‘*’,‘*y’))s=CONCAT(Rep(sub(t,1,5),‘+’,‘y’),Re