




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、數(shù)據(jù)結構試題(100分)(供2005級信息管理與信息系統(tǒng)本科專業(yè)使用)學號: 姓名: 座號: 系別: 年級: 專業(yè): 題號一二三四五六七八總計得分 總分合計人: 復核人: 說明:本試卷分為兩部分,第I卷(選擇題和判斷題)必須在“答題卡”上按規(guī)定要求填、涂;第II卷直接在試卷上作答。不按規(guī)定答題、填涂,一律無效。第I卷得分評卷人一、試題類型:單項選擇題(每小題2分,共40分)(類型說明:在每小題列出的四個選項中只有一個選項是符合題目要求的,請選出正確選項并在“答題卡”的相應位置上涂黑。多涂、少涂、錯誤均無分。)1. 算法分析的兩個主要方面是: ( )(A) 空間復雜性和時間復雜性 (B) 正確性
2、和簡明性(C) 可讀性和文檔性 (D) 數(shù)據(jù)復雜性和程序復雜性2. 計算機算法指的是: ( )(A) 計算方法 (B) 排序方法 (C) 解決問題的有限運算序列 (D) 調度方法3 數(shù)據(jù)在計算機存儲器內表示時,物理地址與邏輯地址相同并且是連續(xù)的,稱為:( )(A)存儲結構 (B)邏輯結構 (C)順序存儲結構 (D)鏈式存儲結構4.一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是 。 ( )(A)110 (B)108 (C)100 (D)1205. 鏈接存儲的存儲結構所占存儲空間: ( )(A)分兩部分,一部分存放結點值,另一部分存放表示結點間關系的指針(B)只有一
3、部分,存放結點值(C) 只有一部分,存儲表示結點間關系的指針(D) 分兩部分,一部分存放結點值,另一部分存放結點所占單元數(shù)6. 線性表若采用鏈式存儲結構時,要求內存中可用存儲單元的地址: ( )(A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的 (D)連續(xù)或不連續(xù)都可以7. 棧中元素的進出原則是: ( ) ()先進先出 ()后進先出 ()棧空則進 ()棧滿則出8. 若已知一個棧的入棧序列是1,2,3,n,其輸出序列為p1,p2,p3,pn,若p1=n,則pi為: ( ) () i () n=i () n-i+1 () 不確定9. 串是一種特殊的線性表,其特殊性體現(xiàn)在: ( )
4、()可以順序存儲 ()數(shù)據(jù)元素是一個字符 ()可以鏈式存儲 ()數(shù)據(jù)元素可以是多個字符10. 設串s1=ABCDEFG,s2=PQRST,函數(shù)con(x,y)返回x和y串的連接串,subs(s, i, j)返回串s的從序號i開始的j個字符組成的子串,len(s)返回串s的長度,則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結果串是: ( ) ()BCDEF ()BCDEFG ()BCPQRST ()BCDEFEF11. 假設有60行70列的二維數(shù)組a160, 170以列序為主序順序存儲,其基地址為10000,每個元素占2個存儲單元,那么第32行第
5、58列的元素a32,58的存儲地址為 。(無第0行第0列元素) ( ) ()16902 ()16904 ()14454 ()答案A, B, C均不對12二叉樹是非線性數(shù)據(jù)結構,所以 。 ( )()它不能用順序存儲結構存儲; ()它不能用鏈式存儲結構存儲; ()順序存儲結構和鏈式存儲結構都能存儲; ()順序存儲結構和鏈式存儲結構都不能使用 13. 具有n(n>0)個結點的完全二叉樹的深度為 。 ( )() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1
6、9;14把一棵樹轉換為二叉樹后,這棵二叉樹的形態(tài)是 。 ( )()唯一的 ()有多種()有多種,但根結點都沒有左孩子 ()有多種,但根結點都沒有右孩子15. 已知圖的鄰接表如下所示,則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是( )(A) 0 1 3 2 (B) 2 0 3 1 (C) 1 3 2 0 (D) 0 1 2 316. 已知圖的鄰接表如下所示,根據(jù)算法,則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是( )(A)0 3 2 1 (B) 1 2 3 0 (C)3 2 1 0 (D) 3 0 1 217折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,
7、則它將依次與表中 比較大小,查找結果是失敗。 ( )(A)20,70,30,50 (B)30,88,70,50 (C)20,50 (D)30,88,5018鏈表是一種采用 存儲結構存儲的線性表。 ( )(A)順序 (B)鏈式 (C)星式 (D)網(wǎng)狀19不含任何結點的空樹 。 ( )()不是一棵樹; ()不是一棵二叉樹; ()是一棵樹也是一棵二叉樹; ()既不是樹也不是二叉樹20在一個圖中,所有頂點的度數(shù)之和等于圖的邊數(shù)的 倍。 ( ) A1/2 B. 1 C. 2 D. 4 得分評卷人二、試題類型:判斷題(每小題1分,共10分)(類型說明:判斷正確答案,選項并在“答題卡”的相應位置填涂,認為正
8、確的涂“A”錯誤的涂“B ”。多涂、少涂、錯誤均無分。)21. 二叉樹中每個結點的兩棵子樹是有序的。 ( )22. 順序存儲方式只能用于存儲線性結構。 ( )23. 二叉樹中每個結點的關鍵字值大于其左非空子樹(若存在的話)所有結點的關鍵字值,且小于其右非空子樹(若存在的話)所有結點的關鍵字值。 ( )24. 棧和隊列的存儲方式既可是順序方式,也可是鏈接方式。 ( )25. 二叉樹中所有結點,如果不存在非空左子樹,則不存在非空右子樹。 ( )26. 隊列是一種先進后出型結構。 ( )27. 一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。 ( )28. 棧是一種對所有插入、刪除操
9、作限于在表的一端進行的線性表,是一種后進先出型結構。 ( )29. 線性表在物理存儲空間中也一定是連續(xù)的。 ( )30. 線性表在順序存儲時,邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。( )第II卷得分評卷人三、試題類型:填空題(每空1分,共10分)(類型說明:請將正確答案填于試題預留的橫線上。)31. 棧是一種特殊的線性表,允許插入和刪除運算的一端稱為 。不允許插入和刪除運算的一端稱為 。32. 向一個長度為n的向量的第i個元素(1in+1)之前插入一個元素時,需向后移動 個元素。33. 向一個長度為n的向量中刪除第i個元素(1in)時,需向前移動 個元素。34. 假設有二維數(shù)組A6&
10、#215;8,每個元素用相鄰的6個字節(jié)存儲,存儲器按字節(jié)編址。已知A的起始存儲位置(基地址)為1000,則數(shù)組A的體積(存儲量)為 ;末尾元素A57的第一個字節(jié)地址為 ;若按行存儲時,元素A14的第一個字節(jié)地址為 ;若按列存儲時,元素A47的第一個字節(jié)地址為 。35. 設S=“A;/document/Mary.doc”,則strlen(s)= , “/”的字符定位的位置為 。得分評卷人四、試題類型:簡答題(每小題5分,共30分)(類型說明: )36. 已知二維數(shù)組Am,m采用按行優(yōu)先順序存放,每個元素占K個存儲單元,并且第一個元素的存儲地址為Loc(a11),請寫出求Loc(aij)的計算公式
11、。37. 用三元組表表示下列稀疏矩陣: 38. 試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結點序列。 39. 把如圖所示的樹轉化成二叉樹。40. 已知如圖所示的有向圖,請給出該圖的鄰接表。41. 請對下圖的無向帶權圖,求其最小生成樹;得分評卷人五、試題類型:分析題(每小題5分,共5分)(類型說明: )42. 已知一組關鍵字序列: 49 38 65 97 13 27按照快速排序方法對此序列進行排序,寫出每趟排序的結果。得分評卷人六、試題類型:編程題(每小題5分,共5分)(類型說明: )43. 設順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法,將x插入到順序表的適當位置上,以保持該表的有
12、序性。順序表的存儲結構如下:typedef struct ElemType *elem; /指向存放線性表中數(shù)據(jù)元素的基地址 int length; /線性表的當前長度 int listsize; /當前分配的存儲容量 SqList;Status InsertSqList(SqList &va,int x)/把x插入遞增有序表va中 if(va.length+1>va.listsize) return ERROR; 數(shù)據(jù)結構A卷信管本科專業(yè)標準答案及評分標準(按試題順序排列)一、單項選擇題(每小題2分,共40分)1、A 2、C 3、C 4、 B 5、A 6、
13、D 7、B 8、C 9、B 10、D 11、A 12、C 13、C 14、A 15、D 16、A 17、A 18、B 19、C 20、C 二、判斷題(每小題1分,共10分)21. A 22. B 23. B 24. A 25. B 26. B 27. B 28. A 29. B 30. B 三、填空題(每空1分,共10分) 31. 棧頂 棧底 32. n-i+1 33. n-i 34. 288 B 1282 1072 1276 35. 20 3四、簡答題(每小題5分,共30分) 36. Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K66416-2259435653
14、 37. 38. 先序: A B D F J G K C E H I L M-2分 中序: B F J D G K A C H E L I M-2分 后序: J F K G D B H L M I E C A-1分39. 40. 41. 五、試題類型:分析題(每小題5分,共5分)42. 初始序列:49 38 65 97 13 27第一趟排序結果:27 38 13 49 97 65第二趟排序結果:13 27 38 49 65 97六、試題類型:編程題(每小題5分,共5分)43. va.length+; for(i=va.length-1;va.elemi>
15、;x&&i>=0;i-) va.elemi+1=va.elemi; va.elemi+1=x; return OK; 數(shù)據(jù)結構試題(100分)(供2005級信息管理與信息系統(tǒng)本科專業(yè)使用)學號: 姓名: 座號: 系別: 年級: 專業(yè): 題號一二三四五六七八總計得分 總分合計人: 復核人: 說明:本試卷分為兩部分,第I卷(選擇題和判斷題)必須在“答題卡”上按規(guī)定要求填、涂;第II卷直接在試卷上作答。不按規(guī)定答題、填涂,一律無效。第I卷得分評卷人一、試題類型:單項選擇題(每小題2分,共
16、40分)(類型說明:在每小題列出的四個選項中只有一個選項是符合題目要求的,請選出正確選項并在“答題卡”的相應位置上涂黑。多涂、少涂、錯誤均無分。)1. 非線性結構是數(shù)據(jù)元素之間存在一種 。 ( )(A) 一對多關系 (B) 多對多關系 (C) 多對一關系 (D) 一對一關系2. 數(shù)據(jù)結構中,與所使用的計算機無關的是數(shù)據(jù)的 結構。 ( )(A) 存儲 (B) 物理 (C) 邏輯 (D) 物理和存儲 3. 算法分析的兩個主要方面是 。 ( )(A) 空間復雜性和時間復雜性 (B) 正確性和簡明性(C) 可讀性和文檔性 (D) 數(shù)據(jù)復雜性和程序復雜性4. 計算機算法指的是 。 ( )(A) 計算方法
17、 (B) 排序方法 (C) 解決問題的有限運算序列 (D) 調度方法5. 數(shù)據(jù)在計算機存儲器內表示時,物理地址與邏輯地址相同并且是連續(xù)的,稱之為 。 ( )(A)存儲結構 (B)邏輯結構 (C)順序存儲結構 (D)鏈式存儲結構6. 一個向量第一個元素的存儲地址是500,每個元素的長度為2,則第10個元素的地址是 。 ( ) (A)510 (B)508 (C)518 (D)5207. 在n個結點的順序表中,算法的時間復雜度是O(1)的操作是 。 ( )(A)訪問第i個結點(1in)和求第i個結點的直接前驅(2in) (B)在第i個結點后插入一個新結點(1in)(C)刪除第i個結點(1in)(D)
18、將n個結點從小到大排序8. 線性表若采用鏈式存儲結構時,要求內存中可用存儲單元的地址 。( )(A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的 (D)連續(xù)或不連續(xù)都可以9. 線性表在 情況下適用于使用鏈式結構實現(xiàn)。 ( )()需經(jīng)常修改中的結點值 ()需不斷對進行刪除插入 ()中含有大量的結點 ()中結點結構復雜10. 棧中元素的進出原則是 。 ( )() 先進先出 () 后進先出 () ??談t進 () 棧滿則出11. 若已知一個棧的入棧序列是1,2,3,n,其輸出序列為p1,p2,p3,pn,若p1=n,則pi為 。 ( )() i () n=i () n-i+1 () 不
19、確定12. 設有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作 。 ( )() 連接 () 模式匹配 () 求子串 () 求串長13. 串是一種特殊的線性表,其特殊性體現(xiàn)在 。 ( )() 可以順序存儲 () 數(shù)據(jù)元素是一個字符 () 可以鏈式存儲 () 數(shù)據(jù)元素可以是多個字符 14. 假設有60行70列的二維數(shù)組a160, 170以列序為主序順序存儲,其基地址為10000,每個元素占2個存儲單元,那么第32行第58列的元素a32,58的存儲地址為 。(無第0行第0列元素) ( )() 16902 () 16904 () 17262 () 答案A, B, C均不對15. 二叉樹是非線性數(shù)據(jù)結
20、構,所以 。 ( )()它不能用順序存儲結構存儲; ()它不能用鏈式存儲結構存儲;()順序存儲結構和鏈式存儲結構都能存儲; ()順序存儲結構和鏈式存儲結構都不能使用16. 具有n(n>0)個結點的完全二叉樹的深度為 。 ( )() élog2(n)ù () ë log2(n)û () ë log2(n) û+1 () élog2(n)+1ù 17. 對22個記錄的有序表作折半查找,當查找失敗時,至少需要比較 次關鍵字。( )(A) 3 (B) 4 (C) 5 (D) 6 18. 鏈表適用于 查找。 ( )(A
21、) 順序 (B) 二分法 (C) 順序,也能二分法 (D) 隨機 19. 堆的形狀是一棵 。 ( )() 二叉排序樹 () 滿二叉樹 () 完全二叉樹 () 平衡二叉樹 20. 下列關鍵字序列中, 是堆。 ( )() 16, 72, 31, 23, 94, 53 () 94, 23, 31, 72, 16, 53 () 16, 53, 23, 94,31, 72 () 16, 23, 53, 31, 94, 72 得分評卷人二、試題類型:判斷題(每小題1分,共10分)(類型說明:判斷正確答案,選項并在“答題卡”的相應位置填涂,認為正確的涂“A”錯誤的涂“B ”。多涂、少涂、錯誤均無分。)21.
22、 順序表結構適宜于進行順序存取,而鏈表適宜于進行隨機存取。 ( )22. 順序存儲方式只能用于存儲線性結構。 ( )23. 線性表的邏輯順序與存儲順序總是一致的。 ( )24. 棧是一種對所有插入、刪除操作限于在表的一端進行的線性表,是一種后進先出型結構。 ( )25. 一個棧的輸入序列是12345,則棧的輸出序列不可能是12345。 ( )26. 若二叉樹用二叉鏈表作存貯結構,則在n個結點的二叉樹鏈表中只有n1個非空指針域。 ( )27. 對于一棵非空二叉樹,它的根結點作為第一層,則它的第i層上最多能有2i1個結點。 ( )28. 用二叉鏈表法(link-rlink)存儲包含n個結點的二叉樹
23、,結點的2n個指針區(qū)域中有n+1個為空指針。 ( )29. 二叉樹中每個結點的兩棵子樹是有序的。 ( )30. 二叉樹中每個結點的關鍵字值大于其左非空子樹(若存在的話)所有結點的關鍵字值,且小于其右非空子樹(若存在的話)所有結點的關鍵字值。 ( )第II卷得分評卷人三、試題類型:填空題(每小題1分,共20分)(類型說明:請將正確答案填于試題預留的橫線上。)31. 數(shù)據(jù)結構被形式地定義為(D, R),其中D是數(shù)據(jù)元素的有限集合,R是D上的 有限集合。32. 數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的 這三個方面的內容。33. 數(shù)據(jù)結構按邏輯結構可分為兩大類,它們分別是線性結構和 。34.
24、 線性結構中元素之間存在一對一關系,樹形結構中元素之間存在一對多關系,圖形結構中元素之間存在 關系。35. 在 中,第一個結點沒有前驅結點,其余每個結點有且只有 1個前驅結點;最后一個結點沒有后續(xù)結點,其余每個結點有且只有1個后續(xù)結點。36. 在 中,樹根結點沒有前驅結點,其余每個結點有且只有1個前驅結點;葉子結點沒有后續(xù)結點,其余每個結點的后續(xù)結點數(shù)可以任意多個。37. 在圖形結構中,每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以 。38. 數(shù)據(jù)的存儲結構可用四種基本的存儲方法表示,它們分別是順序 、 鏈式 、 索引 和 。39. 一個算法的效率可分為 效率和空間效率。40. 設要將序列(Q, H,
25、C, Y, P, A, M, S, R, D, F, X)中的關鍵碼按字母序的升序重新排列,則冒泡排序一趟掃描的結果是 。41. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是 。42. 線性有序表(a1,a2,a3,a256)是從小到大排列的,對一個給定的值k,用二分法檢索表中與k相等的元素,在查找不成功的情況下,最多需要檢索 次。43. 假設在有序線性表a20上進行折半查找,平均查找長度為 。44. 散列法存儲的基本思想是由 決定數(shù)據(jù)的存儲地址。45. 有8個結點的無向連通圖最少有 條邊。46. 在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的 倍。47. 在一個圖中,所有
26、頂點的度數(shù)之和等于圖的邊數(shù)的 倍。48. 在具有n個單元的循環(huán)隊列中,隊滿時共有 個元素。49. 棧是一種特殊的線性表,允許插入和刪除運算的一端稱為 。50. 是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表。得分評卷人四、試題類型:綜合題(每小題5分,共25分)(類型說明: )51. 請對下圖的無向帶權圖,寫出它的鄰接矩陣,并按普里姆算法求其最小生成樹;52. 寫出下圖AOE-網(wǎng)的關鍵路徑。53. 寫出下圖的拓撲排序序列。54. 已知某二叉樹的中序遍歷序列結點序列是B F J D G K A C H E L I M、后序遍歷結點序列J F K G D B H L M I E C A是,試寫出其先序遍歷結點序列并畫出此二叉樹。55. 下圖是某樹的二叉樹表示法,試畫出此樹。 A B E C K F H D L G I M J 得分評卷人五、試題類型:編程(每小題5分,共5分)(類型說明: )56. 已知11個元素的有序表為(05 13 19 21 37 56 64 75 80 88 92), 請寫出折半查找的算法程序,查找關鍵字為key的數(shù)據(jù)元素。數(shù)據(jù)結構B卷信管本科專業(yè)標準答案及評分標準(按試題順序排列)一、單項選擇題(每小題2分,共
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- DB32/T 4705.2-2024口罩有毒有害物質的測定第2部分:禁用偶氮染料
- 飼料廠可行性方案研究報告
- 呼吸??谱o理分析
- 軟裝設計師核心能力體系
- 初中數(shù)學總復習優(yōu)化設計方案
- 食管癌食管穿孔的護理
- 職場女性康復
- 新聞報道設計方案
- 骨科常見疾病的功能鍛煉方法
- 學校安全保衛(wèi)課件
- 江蘇有限空間作業(yè)安全操作規(guī)范DB32∕T-3848-2020
- 《中醫(yī)美容》課件
- 10.2事件的相互獨立性 說課課件高一下學期數(shù)學人教A版(2019)必修第二冊
- 民辦學校檔案管理制度
- 工業(yè)固體廢棄物的資源化處理
- DB11 637-2015 房屋結構綜合安全性鑒定標準
- 教學評一體化含義
- 24秋國家開放大學《馬克思主義基本原理》專題測試參考答案
- 下月監(jiān)理工作計劃模板
- 科技查新報告樣例
- 2024株洲市中考地理試題
評論
0/150
提交評論