數(shù)據(jù)結(jié)構(gòu)II+A卷答案

PAGEPAGE7課程名稱:數(shù)據(jù)結(jié)構(gòu)II東北大學(xué)繼續(xù)教育學(xué)院數(shù)據(jù)結(jié)構(gòu)II試卷（作業(yè)考核線上1）A卷學(xué)習(xí)中心：院校學(xué)號：姓名（共6頁）總分題號一二三四五六七八九十得分一、單選題（共30題，每題2分）[A]1．抽象數(shù)據(jù)類型的三個組成部分分別為A．?dāng)?shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作B．?dāng)?shù)據(jù)元素、邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)C．?dāng)?shù)據(jù)項、數(shù)據(jù)元素和數(shù)據(jù)類型D．?dāng)?shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型[B]2．要求相同邏輯結(jié)構(gòu)的數(shù)據(jù)元素具有相同的特性，其含義為A.數(shù)據(jù)元素具有同一的特點B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)相同，而且其對應(yīng)數(shù)據(jù)項的類型要一致C.每個數(shù)據(jù)元素都一樣D.僅需要數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)相同[D]3．下列各式中，按增長率由小至大的順序正確排列的是A．，n！，2n，n3/2B．n3/2，2n，nlogn，2100C．2n，logn，nlogn，n3/2D．2100，logn,2n,nn[B]4.在下列哪種情況下，線性表應(yīng)當(dāng)采用鏈表表示為宜A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變[C]5．設(shè)指針p指向雙鏈表的某一結(jié)點，則雙鏈表結(jié)構(gòu)的對稱性是A.p->prior->next=p->next->next;B.p->prior->prior=p->next->prior;C.p->prior->next=p->next->prior;D.p->next->next=p->prior->prior;[A]6.已知指針p和q分別指向某帶頭結(jié)點的單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后插入上述鏈表應(yīng)執(zhí)行的語句為A.s->next=q；p->next=s->next；B.s->next=p；q->next=s->next；C.p->next=s->next；s->next=q；D.q->next=s->next；s->next=p；[A]7.棧和隊列的共同特點是A.只允許在端點處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點[D]8.對于鏈隊列，在進(jìn)行插入運算時.A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改[B]9．設(shè)有一個順序棧的入棧序列是1、2、3，則3個元素都出棧的不同排列個數(shù)為A．4B．5C.6D.7[D]10．設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能是A．A，B，C，DB．D，C，B，AC.A，C，D，BD.D，A，B，C[C]11．表達(dá)式a*(b+c)-d的后綴表達(dá)式是A．a(chǎn)bcd*+-B．a(chǎn)bc*+d-C．a(chǎn)bc+*d-D．-+*abcd[B]12．某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點一定是A.空或只有一個結(jié)點B.高度等于其結(jié)點數(shù)C.任一結(jié)點無左孩子D.任一結(jié)點無右孩子[B]13．下面的說法中正確的是(1)任何一棵二叉樹的葉子結(jié)點在種遍歷中的相對次序不變。(2)按二叉樹定義，具有三個結(jié)點的二叉樹共有6種。A．(1)，(2)B．(1)C．(2)D．(1)，(2)都錯[B]14．樹有先序遍歷和后序遍歷，樹可以轉(zhuǎn)化為對應(yīng)的二叉樹。下面的說法正確的是A．樹的后序遍歷與其對應(yīng)的二叉樹的先序遍歷相同B．樹的后序遍歷與其對應(yīng)的二叉樹的中序遍歷相同C．樹的先序序遍歷與其對應(yīng)的二叉樹的中序遍歷相同D．以上都不對[A]15．下列說法正確的是(1)二又樹按某種方式線索化后，任一結(jié)點均有前趨和后繼的線索(2)二叉樹的先序遍歷序列中，任意一個結(jié)點均處于其子孫結(jié)點前(3)二叉排序樹中任一結(jié)點的值大于其左孩子的值，小于右孩子的值A(chǔ)．(1)(2)(3)B．(1)(2)C．(1)(3)D．都不對[D]16.二叉樹的第k層的結(jié)點數(shù)最多為A．2k-1B.2K+1C.2K-1D.2k-1[D]17．以下說法不正確的是A．無向圖中的極大連通子圖稱為連通分量B．連通圖的廣度優(yōu)先搜索中一般采用隊列來暫存剛訪問過的頂點C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點D．有向圖的遍歷不可采用廣度優(yōu)先搜索[D]18．有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中A.第i行1的元素之和B.第i列1的元素之和C.第i行0的元素個數(shù)D.第i列非0的元素個數(shù)[A]19.設(shè)有6個結(jié)點的無向圖，該圖確保是一個連通圖的有效邊條數(shù)至少應(yīng)是A.5B.6C.7D.8[C]20．.下圖的鄰接表中，從頂點V1出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點序列是A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V2[A]21．關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長的回路D．最短的回路[D]22．設(shè)哈希表長為14，哈希函數(shù)H(key)=key％11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個，現(xiàn)將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是A．8B．3C．5D．9[B]23．.在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)調(diào)整以使其平衡，所作的平衡旋轉(zhuǎn)是A.LL型B.LR型C.RL型D.RR型[A]24．下列排序算法中，在待排序數(shù)據(jù)已基本有序時，效率最高的排序方法是A．插入排序B．選擇排序C．快速排序D．堆排序[A]25．下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0(nlog2n)是A.堆排序B.冒泡排序C.直接選擇排序D.快速排序[B]26.有一程序段:i=1；WHILE(i<n)i=i*2;其中帶下劃線語句的執(zhí)行次數(shù)的數(shù)量級是A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)[C]27.無頭結(jié)點的鏈隊列Q為空的條件是A.Q->front->next==Q->real=NULLB.Q->front==Q->real<>NULLC.Q->real==Q->front=NULLD.Q->real->next==Q->front<>NULL[A]28.有向圖G可拓?fù)渑判虻呐袆e條件是A.不存在環(huán)B.存在環(huán)C.存在入度為零的結(jié)點D.存在出度為零的結(jié)點[C]29.對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間A.O（1）B.O（n）C.O（1og2n）D.O（n2）[B]30.下列排序算法中，在待排序數(shù)據(jù)已基本有序時，效率最高的排序方法是A．插入排序B．選擇排序C．快速排序D．堆排序二、綜合題（共4題，每題10分）31、閱讀算法，在橫線處填入語句或注釋。voidexchange_L(Linklist&L，intm){//帶頭結(jié)點的單鏈表中前m個結(jié)點和后n個結(jié)點的整體互換

if(m&&L->next){//鏈表非空p=L->next;（1）//k取值while(k<m&&p){//（2）

p=p->next;++k;

}//whileif(p&&（3）){//n!=0時才需要修改指針

ha=L->next;//以指針ha記a1結(jié)點的位置L->next=p->next;//將b1結(jié)點鏈接在頭結(jié)點后

p->next=（4）;//設(shè)am的后繼

q=L->next;//令q指向b1結(jié)點while(q->next)q=q->next;//查找bn結(jié)點q->next=（5）//將第a1結(jié)點鏈接到bn結(jié)點之后}//if(p)

}//if(m)}//exchange_L（1）k=1;（2）查找第am個結(jié)點

（3）p->next（4）L->next（5）將第a1結(jié)點鏈接到bn結(jié)點之后32．一個僅包含二元運算符的算術(shù)表達(dá)式，以二叉鏈表形式存儲在二叉樹T中，設(shè)計算法F1實現(xiàn)求值，并指出遍歷的方式。答：以二叉樹表示算術(shù)表達(dá)式，根結(jié)點用于存儲運算符。若能先分別求出左子樹和右子樹表示的子表達(dá)式的值，最后就可以根據(jù)根結(jié)點的運算符的要求，計算出表達(dá)式的最后結(jié)果。floatPostValue(BiTreeT){floatlv,rv;if(T){lv=PostValue(T->lchild);rv=PostValue(T->rchild);seitch(T->optr){case'+':value=lv+rv;break;case'-':value=lv-rv;break;case'*':value=lv*rv;break;case'/':value=lv/rv;break;}returnvalue;}}33．設(shè)計算法實現(xiàn)以逆鄰接表為存儲結(jié)構(gòu)的有向圖的拓?fù)渑判?。逆鄰接表存儲結(jié)構(gòu)定義如下：頂點結(jié)構(gòu)表結(jié)點結(jié)構(gòu)vexdatafirstinadjvexnfofirstarc#defineMAX_VERTEX_NUM20typedefstructArcNode{int adjvex;structArcNode*nextarc;InfoType *info;}ArcNode