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

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

p=p->next;++k;

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

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

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

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

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

（3）p->next（4）L->next（5）將第a1結(jié)點(diǎn)鏈接到bn結(jié)點(diǎn)之后32．一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式，以二叉鏈表形式存儲(chǔ)在二叉樹(shù)T中，設(shè)計(jì)算法F1實(shí)現(xiàn)求值，并指出遍歷的方式。答：以二叉樹(shù)表示算術(shù)表達(dá)式，根結(jié)點(diǎn)用于存儲(chǔ)運(yùn)算符。若能先分別求出左子樹(shù)和右子樹(shù)表示的子表達(dá)式的值，最后就可以根據(jù)根結(jié)點(diǎn)的運(yùn)算符的要求，計(jì)算出表達(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è)計(jì)算法實(shí)現(xiàn)以逆鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖的拓?fù)渑判?。逆鄰接表存?chǔ)結(jié)構(gòu)定義如下：頂點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)結(jié)構(gòu)vexdatafirstinadjvexnfofirstarc#defineMAX_VERTEX_NUM20typedefstructArcNode{int adjvex;structArcNode*nextarc;InfoType *info;}ArcNode