大學《數(shù)據(jù)結構》試題及答案
數(shù)據(jù)結構是計算機存儲、組織數(shù)據(jù)的方式。以下是由陽光網(wǎng)小編整理關于大學《數(shù)據(jù)結構》試題的內(nèi)容，希望大家喜歡!
大學《數(shù)據(jù)結構》試題及答案(一)
1.屬性與服務相同的對象構成類，類中的每個對象稱為該類的一——·
2.在類的繼承結構中，位于上層的類叫做一——，其下層的類則 叫做 類.
3.若設串S=“documentHash.doc\O”，則詼字符串S的長度為——·
4.線性表的鏈接存儲只能通過—————————順序訪問。
5.設鏈棧中結點的結構為(data，link)，棧頂 指針為top，則向該鏈棧插入、—個新結點*p
時，應依次執(zhí)行—————————————和一————操作。
6.廣義表的深度定義為廣義表中括號被嵌套的——一·
7.在一棵高度為h的完全二又樹中，最少含有——個結點.假定樹根結點的高度為O.
8.從有序擊(12，10，30，43，56，78，02，95)中折半搜索56和98元素時，其搜索長度分別為——和——·
9。n個(n>o)頂點的連通無向圖中各頂點的度之和最少為————·
10.設圖的頂點數(shù)為n，則求解最短路徑的Dijkstra算法的時間復雜度為————·
11.給定一組數(shù)據(jù)對象的關鍵碼為{46，79，56，38，40，84}，則利用堆排序方法建立的初始最大堆的堆首和堆尾的關鍵碼分別為——和——·L2.在索引表中，著一個索引項對應數(shù)據(jù)對象表中的一個表項，0C稱此索引為稠密索引
若對應數(shù)據(jù)對象表中的若干表項，則稱此索引為——一索引.
答案
1.實例
2.基類 派生(或于類)
3. 16
4.鏈接指針
5.p一>Link=top top=p
6.重數(shù)
7.2h
8. 3 2
9.2(n-1)
10。O(n2)
11.84 46
12。稀疏
大學《數(shù)據(jù)結構》試題及答案(二)
1、填空題。(每小題2分，本題滿分20分)
(1) C++語言中，數(shù)組是按行優(yōu)先順序存儲的，假設定義了一個二維數(shù)組A[20][30]，每個元素占兩個字節(jié)，其起始地址為2140，則二維數(shù)組A的最后一個數(shù)據(jù)元素的地址為 2140+2*(30*20-1) = 3338(3338,3339) 。
(2) 若A，B是兩個單鏈表，鏈表長度分別為n和m，其元素值遞增有序，將A和B歸并成一個按元素值遞增有序的單鏈表，并要求輔助空間為O(1)，則實現(xiàn)該功能的算法的時間復雜度為 O(m+n) 。
(3) 快速排序的平均時間復雜度是______________。
(4) 假設有一個包含9個元素的最小堆，存放在數(shù)組A中，則一定比A[3]大的元素有個;一定比A[3]小的元素有個。(元素從第0個位置開始存放)
(5) 廣義表(((A)),(B,C), D, ((A), ((E,F)))) 的長度是，深度是。
(6) 有10個元素的有序表，采用折半查找，需要比較4次才可找到的元素個數(shù)為。 (7)當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組A[n]表示，兩棧頂指針為top[0]與top[1]，則棧滿時的判斷條件為___top[0]+1=top[1]_ 或者 top[0] = top[1]+1 ___。 (8) 假設計算斐波那契數(shù)的'函數(shù)Fib(long n)定義如下：
long Fib(long n){ if(n<=1) return n;
else return Fib(n-1)+Fib(n-2) }
計算Fib(5)時的遞歸調(diào)用樹(即指明函數(shù)調(diào)用關系的樹)的高度是___4 _____。假設葉子結點所在的高度為0。
(9) 完全二叉樹按照層次次序，自頂向下，同層從左到右順序從0開始編號時，編號為i的結點的左子結點的編號為___2*i+1______。
(10) 假設用子女—兄弟鏈表方式表示森林，對應的二叉樹的根結點是p，那么森林的第三棵樹的根結點在二叉樹中對應的結點是： ___p->rightchild->rightchild____________。假
2、選擇題。(每小題2分，本題滿分20分)
(1) 如果能夠在只知道指針p指向鏈表中任一結點，不知道頭指針的情況下，將結點*p從鏈
表中刪除，則這個鏈表結構應該是： ( B,C )(多選題) A. 單鏈表 B. 循環(huán)鏈表 C. 雙向鏈表 D. 帶頭結點的單鏈表 (2) 以下哪種矩陣壓縮存儲后會失去隨機存取的功能?( A )
A. 稀疏矩陣 B. 對稱矩陣 C. 對角矩陣 D. 上三角矩陣
(3) 下面哪一方法可以判斷出一個有向圖是否有環(huán)(回路)：( B ) (選A，B也對)
A. 廣度優(yōu)先遍歷 B. 拓撲排序 C. 求最短路徑 D.求關鍵路徑 (4) n個結點的線索二叉樹(沒有頭結點)上含有的線索數(shù)為( B )
A. 2n B. n-l C. n+l D. n
(5) 循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時隊尾指針rear的操作為( D )
A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
(6) 使用加權規(guī)則得到改進的Union操作WeightedUnion，其目的是： ( B )
A. 提高Union操作的時間性能 B. 提高Find操作的時間性能 C. 減少Union操作的空間存儲 D. 減少Find操作的空間存儲
【大學《數(shù)據(jù)結構》試題及答案】相關文章：