東北師范大學23春“計算機科學與技術”《數(shù)據(jù)結構》補考試題庫附答案

東北師范大學23春“計算機科學與技術”《數(shù)據(jù)結構》補考試題庫附答案第I卷一.綜合考核(共15題)1.最小生成樹問題是構造帶權連通圖(網(wǎng))的最小代價生成樹。()A.錯誤B.正確2.棧和隊列都是限制存取點的線性結構。()A.正確B.錯誤3.鄰接矩陣適用于有向圖和無向圖的存儲，但不能存儲帶權的有向圖和無向圖，而只能使用鄰接表存儲形式來存儲它。()A.正確B.錯誤4.()的遍歷仍需要棧的支持。A.前序線索二叉樹B.中序線索二叉樹C.后序線索二叉樹D.前三種均需要5.在待排數(shù)據(jù)基本有序的情況下，快速排序效果最好。()A.錯誤B.正確6.順序存儲結構的主要缺點是不利于插入、刪除操作。()A.錯誤B.正確7.求圖的最小(代價)生成樹問題，考慮的是下面的哪一種圖?()A.有向圖B.無向圖C.帶權的有向圖D.帶權的無向圖8.直接選擇排序算法對n個記錄排序，在最好情況下的時間復雜度為O(n)。()A.錯誤B.正確9.在下列情況中，可稱為二叉樹的是()。A.每個結點至多有兩棵子樹的樹B.哈夫曼樹C.每個結點至多有兩棵子樹的有序樹D.每個結點只有一棵右子樹10.二叉樹在線索化后，仍不能有效求解的問題是()。A.后序線索二叉樹中求后序后繼B.前序線索二叉樹中求前序后繼C.中序線索二叉樹中求中序后繼D.中序線索二叉樹中求中序前驅(qū)11.用ISAM組織文件適合于()。A.磁盤B.磁帶C.外存儲器D.光盤12.下列描述中正確的是()。A.選擇合適的數(shù)據(jù)結構是解決應用問題的關鍵步驟B.線性表的邏輯順序與存儲順序總是一致的C.每種數(shù)據(jù)結構都具備查找、插入和刪除三種基本運算D.數(shù)據(jù)結構實質(zhì)上包括邏輯結構和存儲結構兩方面的內(nèi)容13.數(shù)據(jù)的存儲結構是數(shù)據(jù)的邏輯結構在計算機存儲器上的實現(xiàn)，它是依賴于計算機的。()A.正確B.錯誤14.在鏈隊列中，假設f和r分別為隊首和隊尾指針，則刪除一個結點的操作是()。A.r=r->nextB.r=f->nextC.f=r->nextD.f=f->next15.在一個單鏈表中，已知q所指結點是p所指結點的前驅(qū)結點，若在p之前插入s所指結點，則執(zhí)行()。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s;s->next=qD.p->next=s->next;s->next=p第II卷一.綜合考核(共15題)1.若輸入序列為1，2，3，4，5，6，則通過一個?？梢暂敵鲂蛄?，2，5，6，4，1。()A.正確B.錯誤2.經(jīng)過下列棧的操作后，GetTop(ST)的值是()。InitStack(ST);push(ST，‘a(chǎn)’);push(ST，‘b’);pop(ST，x);A.aB.bC.1D.23.AOV網(wǎng)的含義是以頂點表示活動的網(wǎng)。()A.正確B.錯誤4.二叉樹中除葉結點外，任一結點X，其左子樹根結點的值小于該結點X的值;其右子樹根結點的值大于等于該結點X的值，則此二叉樹一定是二叉排序樹。()A.正確B.錯誤5.(101，88，46，70，34，39，45，58，66，10)是堆。()A.錯誤B.正確6.設s1=“abc”，則strlen(s1)=()。A.3B.2C.1D.07.歸并排序的輔助存儲空間代價為O(1)。()A.正確B.錯誤8.下列說法不正確的是()。A.圖的遍歷是從給定的源點出發(fā)每個頂點僅被訪問一次B.遍歷的基本方法有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷C.圖的深度優(yōu)先遍歷不適用于有向圖D.圖的深度優(yōu)先遍歷是一個遞歸過程9.非空的二叉樹一定滿足：某結點若有左子女，則其中序前驅(qū)一定沒有右子女。()A.錯誤B.正確10.遞歸過程的實現(xiàn)需用到()。A.線性表B.鏈表C.棧D.隊列11.若要求盡可能快地對序列進行穩(wěn)定的排序，則應選()。A.快速排序B.歸并排序C.起泡排序D.希爾排序12.一棵左右子樹均不空的二叉樹在前序線索化后，其中空的鏈域的個數(shù)是()。A.不確定B.2C.1D.013.在下面的排序方法中，其比較次數(shù)與待排序記錄的初始排列狀態(tài)無關的是()。A.直接插入排序B.快速排序C.直接選擇排序D.歸并排序14.下面關于串的敘述中，哪一個是不正確的?()A.空串是由空格構成的串B.模式匹配是串的一種重要運算C.串是字符的有限序列D.串既可以采用順序存儲，也可以采用鏈式存儲15.鏈表中的表頭指針與表頭結點起到相同的作用。()A.正確B.錯誤第III卷一.綜合考核(共15題)1.程序一定是算法。()A.正確B.錯誤2.將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先次序存入一維數(shù)組B[1..298]中，A中元素A[66，65]在數(shù)組B中的位置K為()。A.199B.197C.195D.1933.在下面的敘述中，正確的是()。A.樹的先根遍歷序列與其對應的二叉樹的前序遍歷序列相同B.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同C.樹的先根遍歷序列與其對應的二叉樹的后序遍歷序列相同D.樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同4.對于插入、刪除運算來說，鏈接存儲結構一定優(yōu)于順序存儲結構。()A.錯誤B.正確5.在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的幾倍()。A.1/2B.1C.2D.46.設根結點的層數(shù)為0，若高度為h的二叉樹上只有度為0和度為2的結點，則此二叉樹上所包含的結點數(shù)至少為()。A.h+1B.2h-1C.2hD.2h+17.快速排序的速度在所有排序方法中最快，而且所需附加空間也最少。()A.錯誤B.正確8.廣義表(a，b，c，d)的表頭是()。A.(b，c，d)B.(a，b，c，d)C.aD.(a)9.串是一種特殊的線性表，其特殊性體現(xiàn)在()。A.數(shù)據(jù)元素是一個字符B.數(shù)據(jù)元素可以是多個字符C.可以順序存儲D.可以鏈接存儲10.下面哪些方法可以判斷出一個有向圖是否有環(huán)(回路)?()A.求最短路徑B.求關鍵路徑C.拓撲排序D.廣(寬)度優(yōu)先遍歷11.在對n個元素的序列進行排序時，堆排序所需要的附加存儲空間是()。A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)12.有n個頂點的有向圖的邊數(shù)最多為()。A.nB.n(n-1)C.n(n-1)/2D.2n13.文件系統(tǒng)采用索引結構是為了節(jié)省存儲空間。()A.錯誤B.正確14.對于3個結點a、b、c，可構成不同的二叉樹的棵數(shù)為()。A.32B.30C.28D.2415.有n個頂點的無向圖的邊數(shù)最多為()。A.nB.n(n-1)C.n(n-1)/2D.2n第I卷參考答案一.綜合考核1.參考答案：B2.參考答案：A3.參考答案：B4.參考答案：C5.參考答案：A6.參考答案：B7.參考答案：D8.參考答案：A9.參考答案：B10.參考答案：A11.參考答案：A12.參考答案：A13.參考答案：A14.參考答案：D15.參考答案：B第II卷參考答案一.綜合考核1.參考答案：A2.參考答案：A3.參考答案：A4.參考答案：B5.參考答案：B6.參考答案：A7.參考答案：B8.參考答案：C9.參考答案：B10.參考答案：C11.參考答案：B12.參考答案：C13.參考答案：C14.