類和面向對象數據結構練習題與答案.docx

該【類和面向對象數據結構練習題與答案 】是由【1660287****】上傳分享，文檔一共【17】頁，該文檔可以免費在線閱讀，需要了解更多關于【類和面向對象數據結構練習題與答案 】的內容，可以使用淘豆網的站內搜索功能，選擇自己適合的文檔，以下文字是截取該文章內的部分文字，如需要獲得完整電子版，請下載此文檔到您的設備，方便您編輯和打印。類和面向對象&數據結構練****題與答案類和面向對象局部
1、以下有關類的說法不正確的選項是OO


(正確答案)

答案解析:對象是類的一個實例,類與對象的關系和數據與變量的關系相似,所以一個類可以有多個對象。
2、下面()項是對構造函數和析構函數的正確定義。
voidX::X(),voidX::^X()
乂:《(參數)”::~乂()(正確答案)
X::X(參數),X::?X(參數)
voidX::X(參數),voidX::~X(參數)
答案解析:構造函數無返回類型、可帶參數、可重載;析構函數無返回類型、不可帶參數、不可重載。
3、()的功能是對象進行初始化。


(正確答案)

答案解析:當一個對象定義時,C++編譯系統自動調用構造函數建立該對象并進行初始化;當一個對象的生命周期結束時,C++編譯系統自動調用析構函數注銷該對象并進行善后工作。
4、以下選項中不屬于面向對象程序設計特征的是()o

3、計算機中的算法指的是解決某一個問題的有限運算序列,它必須具備輸入、輸出、()等5個特性。
、可移植性和可擴充性
、有窮性和確定性(正確答案)
、有窮性和穩定性
、穩定性和確定性
答案解析:算法是指為解決某個特定問題而采取確實定且有限的步驟。一個算法應當具有以下五個特性:1)、有窮性:一個算法包含的操作步驟應該是有限的。2)、確定性:算法中每一條指令必須有確切的含義,不能有二義性,對于相同的輸入必須能得到相同的執行結果。3)、可行性:算法中指定的操作,都可以通過已經驗證過可以實現的基本運算執行有限次后實現。4)、有0個或多個輸入:在計算機上實現的算法是用來處理數據對象的,在大多數情況下這些數據對象需要通過輸入來得到。5)、有一個或多個輸出:算法的目的是為了求解,這些解只有通過輸出才能得到(注意:算法要有一個以上的輸出)。
4、下面程序段的時間復雜度是()o
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i];
[單項選擇題]
0(m2)
0(n2)
0(mn)(正確答案)
0(m+n)
答案解析:解析:for(i=0;i<m;i++)/m+1次/for(j=0;j<n;j++)/m(n+1)次/a[i][j]=ij;/mn次/
T=2mn+2m+l=0(mn)o
5、某算法的語句執行頻度為(3n+nlog2n+n2+8),其時間復雜度表示()。
0(n)
0(nlog2n)
0(n2)(正確答案)
0(log2n)
答案解析:算法的時間度量依據算法中最大語句頻度來估算,它是問題規模n的某個函數f(n),算法的時間度量記作:T(n)=O(f(n))
6、通常從正確性、易讀性、健壯性、高效性等4個方面評價算法的質量,以下解釋錯誤的選項是()。

,以便調試、修改和擴充
,算法能適當地做出反響或進行處理,不會產生不需要的運行結果
(正確答案)
答案解析:高效性除了考慮時間性能,還要考慮空間性能。
7、在一個長度為n的順序表中,在第i個元素之前插入一個新元素時,需向后移動()個元素。
n-i
n-i+1(正確答案)
n-i-1
i
答案解析:除了第i個元素之前的元素,其余元素均需要移動,所以移動元素個數為n-(i-l)=n-i+lo
8、非空的循環單鏈表head的尾結點p滿足()。
p->next==head(正確答案)
p->next~NULL
p==NULL
p-head
答案解析:循環單鏈表首尾節點相連,因此p->next==head。
9、鏈表不具有的特點是()o
(正確答案)



答案解析:鏈表只能順序訪問,只能從第一個元素開始逐個地讀取元素,不能隨機訪問任一元素。
10、在雙向循環鏈表中,在P指針所指的結點后插入一個指針q所指向的新結點,修改指針的操作是()o
p->next=q;q->prior=p;p->next->prior=q;q->next=q;
p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;(正確答案)
q->next=p->next;q->prior=p;p->next=q;p->next=q;
答案解析:需先賦值插入節點的信息,再修改當前節點,防止節點信息喪失。
n、從表中任一結點出發,都能掃描整個表的是()。


(正確答案)

答案解析:只有循環鏈表能從任一結點出發,找到所有元素。
12、線性表L=(al,a2,……,an),以下說法正確的選項是()。



,其余每個元素都由一個且僅有一個直接前驅和直接后繼(正確答案)
答案解析:A第一個和最后一個元素不符合條件;B線性表可以為空表;C線性表不要求排序。
13、在以下對順序表進行的操作中,算法時間復雜度為0(1)的是()o
(1<)(正確答案)
()
()

答案解析:假設順序表L,長度為n,求第i個節點L[i],直接取因此為。⑴。
答案B需要移動n-i+l個節點,因此為0(n)
答案C也需要移動n-i個節點
答案D根據排序方法不同最慢0(/2),最快O(nlogn)
14、在以下的表達中,正確的選項是()o


(正確答案)

答案解析:順序表和鏈表各有優劣,適用于不同的場景,鏈表在插入或刪除元素是不需要移動其他元素,插入刪除效率更高,所以C正確。
15、在一個單鏈表中,q所指結點是p所指結點的前驅結點,假設在q和p之間插入一個結點S,那么執行()O
s->next=p->next;p->next=s;
p->next=s->next;s->next=p;
q->next=s;s->next=p;(正確答案)
p->next=s;s->next=q;
答案解析:原來的節點關系為q、P,即q->next=p,插入s后的節點關系為q、s、q,因此,先讓p指向s,即q->next=s;然后讓s指向q,即s->next=p。
16、一個棧的輸入序列為:a,b,c,d,e,那么棧的不可能輸出的序列是
a,b,c,d,e
d,e,c,b,a
d,c,e,a,b(正確答案)
e,d,c,b,a
答案解析:棧是先進后出的結構,對于C,由于e出棧時,a、b已進棧且還沒有出棧,因此,b應該比a出,所以C錯誤。
17、設計一個判別表達式中括號是否配對的算法,采用()數據結構最正確。



(正確答案)
答案解析:右括號需要匹配最近的左括號,具有后進先出的特點,因此用棧更合適。
18、棧和隊列都是()o


(正確答案)

答案解析:由于棧和隊列都屬于線性表,所以線性表的順序存儲結構和鏈式存儲結構同樣適用于棧和隊列。隊列(Queue)是一種先進先出(FIFO)的線性表,隊列是只允許在一端進行插入,另一端進行刪除運算的線性表。允許刪除的那一端稱為隊首(Front),允許插入運算的另一端稱為隊尾(Rear)。棧(Stack)是限定僅在表尾進行插入或刪除操作的線性表。表尾端稱為棧項(top),表頭端稱為棧底(bottom)o故棧是后進先出(LIFO)的線性表?？梢?棧和隊列都是限制存儲點的線性結構
19、設循環隊列的容量為70,現經過一系列的入隊和出隊操作后,front為20,rear為11,那么隊列中元素的個數為()。
9
31
61(正確答案)
39
答案解析:一個循環隊列Q的存儲空間大小為M,其隊頭和隊尾指針分別為front和rear,那么循環隊列中元素的個數為(rear-front+M)%M
20、設a,b為一棵二叉樹上的兩個結點,在中序遍歷時,a在b前面的條件是
()O
a在b的右方
a在b的左方(正確答案)
a是b的祖先

答案解析:中序遍歷首先遍歷左子樹,然后訪問根結點,最后遍歷右子樹。
21、設一棵二叉樹的中序遍歷序列:badce,后序遍歷序列:bdeca,那么二叉樹先序遍歷序列為Oo
adbce
decab
debac
abcde(正確答案)
答案解析:由后序bdeca,確定a是根節點,由中序badce,確定a節點左邊有b節點,右邊是cde節點。
總的樹的形狀a
\
c
\
e
前序abcde
22、在一棵具有5層的滿二叉樹中結點總數為()o
31(正確答案)
32
33
16
答案解析:具有n層的滿二叉樹節點總數為2、-1
23、任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序
()O
(正確答案)



答案解析:先序、中序和后序遍歷的區別在根節點的顯示次序,不影響葉子節點的相對次序。
24、假定在一棵二叉樹中,度為2的結點數為15,度為1的結點數為30,那么葉子結點數為()個。
15
16(正確答案)
17
47
答案解析:葉子節點的度為0,度0=度2+1;
25、排序方法中,從未排序序列中依次取出元素與已排序序列中的元素進行比較,將其放入已排序序列的正確位置上的方法,稱為()。


(正確答案)

答案解析:插入排序,一般也被稱為直接插入排序。對于少量元素的排序,它是一個有效的算法[1]。插入排序是一種最簡單的排序方法,它的基本思想是將一個記錄插入到已經排好序的有序表中,從而一個新的、記錄數增1的有序表。
26、有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100),當折半查找值為82的結點時,()次比擬后查找成功。
1
4(正確答案)
2
8
答案解析:表長為13。
①第一次和第7位數45比擬,發現比45大,就看45后的數字
②第二次和77比擬,比77大,看77后面數字
③第三次和95比擬,比95小,看前面
④第四次和82比擬,相同,即完畢。

(正確答案)

答案解析:面向對象設計是建立在“對象”概念上的方法學,對象是面向對象語言中類的實體,其特點包括:①標識唯一性,對象可區分;②分類性,可以將具有相同屬性和操作的對象抽象成類;③多態性,同一個操作對于不同對象表現不同的行為;④封裝性,屏蔽數據的具體結構以及操作的算法;⑤模塊獨立性好,對象內部各種元素結合緊密,內聚性強。
5、拷貝構造函數具有的以下特點中,()是錯誤的。
,系統將自動生成一個默認的
,并且是該類對象的引用

(正確答案)
答案解析:如果一個類中沒有定義拷貝構造函數時,系統將自動生成一個默認的;拷貝構造函數只有一個參數,并且是該類對象的引用;拷貝構造函數的名字與類同名,并且不被指定返回類型;拷貝構造函數是一種成員函數。
6、關于靜態成員的描述中,()是錯誤的。

(正確答案)


答案解析:靜態成員可分為靜態數據成員和靜態成員函數;靜態數據成員被定義后,必須對它進行初始化,初始化在類體外進行,一般放在該類的實現局部最合適,也可以放在其他位置,例如,放在主函數前面等;靜態數據成員初始化與該類的構造函數和析構函數無關;在靜態成員函數的實現中,可以直接引用靜態成員,但不能直接引用非靜態成員。
7、關于友元的描述中,()是錯誤的。
,它被說明在類體內(正確答案)