數(shù)據(jù)結(jié)構(gòu)考試題

單項(xiàng)選擇數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中,數(shù)據(jù)元素的①C、數(shù)據(jù)信息在計(jì)算機(jī)中的②A以及一組有關(guān)的運(yùn)算等的課程。①A．操作對(duì)象Ｂ．計(jì)算措施Ｃ．邏輯構(gòu)造Ｄ．?dāng)?shù)據(jù)映象②A．存儲(chǔ)構(gòu)造Ｂ．關(guān)系Ｃ．運(yùn)算Ｄ．算法如下數(shù)據(jù)構(gòu)造中,D是線性構(gòu)造。A．廣義表Ｂ．二叉樹Ｃ．稀疏矩陣Ｄ．串從邏輯上可以把數(shù)據(jù)構(gòu)造分為C兩大類。A．動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造Ｂ．次序構(gòu)造和鏈?zhǔn)綐?gòu)造Ｃ．線性構(gòu)造和非線性構(gòu)造Ｄ．初等構(gòu)造和構(gòu)造型構(gòu)造如下數(shù)據(jù)構(gòu)造中,D是線性構(gòu)造。A．廣義表Ｂ．二叉樹Ｃ．稀疏矩陣Ｄ．串如下數(shù)據(jù)構(gòu)造中,D是非線性構(gòu)造。A．棧Ｂ．二叉樹Ｃ．隊(duì)列Ｄ．字符串?dāng)?shù)據(jù)構(gòu)造DS(DataStruct)可以被形式地定義為DS=（D，R），其中D是①B的有限集合，R是D上的②D有限集合。①A．算法Ｂ．?dāng)?shù)據(jù)元素Ｃ．?dāng)?shù)據(jù)操作Ｄ．?dāng)?shù)據(jù)對(duì)象②A．操作Ｂ．映象Ｃ．存儲(chǔ)Ｄ．關(guān)系線性表的次序存儲(chǔ)構(gòu)造是一種①A的存儲(chǔ)構(gòu)造,線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造是一種的②B存儲(chǔ)構(gòu)造。A．隨機(jī)存?。拢涡虼嫒。茫饕嫒。模⒘写嫒【€性表的邏輯次序與存儲(chǔ)次序總是一致的，這種說(shuō)法__B_。A.對(duì)的B.不對(duì)的下面那一條是次序存儲(chǔ)構(gòu)造的長(zhǎng)處?(A)A.存儲(chǔ)密度大B.插入運(yùn)算以便C.刪除運(yùn)算以便D.可以以便的用于多種邏輯構(gòu)造的存儲(chǔ)表達(dá)線性表采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造時(shí),規(guī)定內(nèi)存中可用的存儲(chǔ)單元的地址.A.必須是持續(xù)的B.部分地址必須是持續(xù)的C.一定不持續(xù)D.持續(xù)和不持續(xù)都可以表長(zhǎng)為n的次序存儲(chǔ)的線性表,當(dāng)在任何位置上插入和刪除一種元素的概率相等時(shí),插入一種元素所需要移動(dòng)元素的平均次數(shù)為E,刪除一種元素所需要移動(dòng)元素的平均次數(shù)為AA.(n-1)/2B.nC.n+1D.n-1E.n/2F.(n+1)/2G.(n-2)/2帶頭結(jié)點(diǎn)的單鏈表head為空的鑒定條件是_B___。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL在一種單鏈表中,若刪除p所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn),則執(zhí)行_A___。A.p->next=p->next->nextB.p=p->next;p->next=p->next->nextC.p=p->next->nextD.p=p->next若已知一種棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為_C___。A.iB.n=iC.n-i+1D.不確定設(shè)棧的輸入次序?yàn)?1,2,3,4,5,則不也許是其出棧序列.A.54321B.45321C.43512D.12345一種遞歸算法必須包括BA.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行刪除操作時(shí)DA僅修改頭指針B.僅修改尾指針C.頭尾指針都要修改D.頭尾指針也許都要修改數(shù)組A[m]寄存循環(huán)隊(duì)列的元素,其頭尾指針?lè)謩e是front和rear,則目前隊(duì)列的元素個(gè)數(shù)是__A__。A.(rear-front+m)%mB.(front-rear+m)%mC.front-rear+1D.rear-front+1棧和隊(duì)列的共同特點(diǎn)__C__。A.都是先進(jìn)先出B.都是先進(jìn)后出C.容許在端點(diǎn)插入和刪除元素D.沒(méi)有共同點(diǎn)一種棧的入棧序列a，b，c，d，e，則棧的輸出序列是__A__。A.edcbaB.decbaC.dceabD.abcde棧的特點(diǎn)是__B__，隊(duì)列的特點(diǎn)是__A__。A.先進(jìn)先出B.先進(jìn)后出從一種棧頂指針HS的鏈表中刪除一種結(jié)點(diǎn),用x保留被刪除的結(jié)點(diǎn)值,執(zhí)行的語(yǔ)句為__C__。A.x=HS;HS=HS->nextB.HS=HS->next;x=HS->dataC.x=HS->data;HS=HS->nextD.HS->next=HS;x=HS->data在鏈隊(duì)列Q中,插入s所指向的結(jié)點(diǎn)執(zhí)行的語(yǔ)句為__C__。A.Q.front->next=s;B.Q.rear->next=s;Q.rear=sC.s->next=Q.rear;Q.rear=sD.s->next=Q.front;Q.front=s空串與空格串是相似的，這種說(shuō)法__B__。A.對(duì)的B.不對(duì)的下面有關(guān)串的論述,哪一種是不對(duì)的的__B__。A.串是字符的有限序列B.空串是由空格構(gòu)成的串C.匹配模式是串的一種重要運(yùn)算D.串可以采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造設(shè)有兩個(gè)串p和q，求q在p中初次出現(xiàn)的位置的運(yùn)算稱作__B__。A.連接 B.模式匹配C.求子串 D.求串長(zhǎng)若串s='software',其子串的數(shù)目為BA.8B.37C.36D.9二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始持續(xù)寄存在存儲(chǔ)器內(nèi)，該數(shù)組按行寄存時(shí)，數(shù)組元素A[7][4]的起始地址為__C__。A.SA+141B.SA+144C.SA+222D.SA+225對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是__C__.A.便于進(jìn)行矩陣運(yùn)算B.便于輸入輸出C節(jié)省存儲(chǔ)空間D.減少運(yùn)算的時(shí)間復(fù)雜度在如下論述中對(duì)的的是B線性表的線性存儲(chǔ)構(gòu)造優(yōu)于鏈表存儲(chǔ)構(gòu)造二維數(shù)組可以當(dāng)作是其數(shù)據(jù)元素為線性表的線性表?xiàng)５牟僮鞣绞绞窍冗M(jìn)先出隊(duì)列的操作方式是先進(jìn)后出廣義表((a),a)的表頭為C,表尾為C.A.()B.aC.(a)D.((a))已知廣義表L=((x,y,z),a,(u,t,w)),從L中取出原子項(xiàng)t的運(yùn)算為__D__。A.Head(Tail(Tail(L)))B.Tail(Head(Head(Tail(L))))C.Head(Tail(Head(Tail(L))))D.Head(Tail(Head(Tail(Tail(L)))))樹最適合用來(lái)表達(dá)BA.有序的數(shù)據(jù)元素B.數(shù)據(jù)之間具有分支層次關(guān)系的數(shù)據(jù)C.無(wú)序的數(shù)據(jù)元素D.無(wú)太多關(guān)系的數(shù)據(jù)元素假如某二叉樹的前根次序遍歷成果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序?yàn)開_B__。A.uwvtsB.vwutsC.wuvtsD.wutsv某二叉樹的前序遍歷結(jié)點(diǎn)訪問(wèn)次序是abdgcefh，中序遍歷的結(jié)點(diǎn)訪問(wèn)次序是dgbaechf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)次序是__D__。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊__A__。A.只有右子樹上的所有結(jié)點(diǎn)B.只有右子樹上的部分結(jié)點(diǎn)C.只有左子樹上的部分結(jié)點(diǎn)D.只有左子樹上的所有結(jié)點(diǎn)設(shè)m和n是一棵二叉樹上的兩個(gè)結(jié)點(diǎn),在中序遍歷,n在m前的條件是CA.n在m的右方B.n是m的祖先C.n在m的左方D.n是m的子孫深度為5的二叉樹至多有__C__個(gè)結(jié)點(diǎn)。A.16B.32C.31D.10由權(quán)(8,2,5,7)的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹,該樹的帶權(quán)途徑長(zhǎng)度為DA.23B.37C.46D.43運(yùn)用二叉鏈表存儲(chǔ)樹,則根結(jié)點(diǎn)的右指針是CA.指向最左孩子B.指向最右孩子C.空D.非空下列存儲(chǔ)方式中,哪一種不是樹的存儲(chǔ)形式?DA.雙親表達(dá)法B.孩子鏈表表達(dá)法C.孩子兄弟表達(dá)法D.次序存儲(chǔ)表達(dá)法在一種無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的__C__倍。A.1/2B.1C.2D.4具有n個(gè)頂點(diǎn)和多于n-1條邊的無(wú)向圖B.A.有也許是樹B.一定不是樹C.一定是樹D.以上答案都不對(duì)具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有__A__條邊才能保證是一種連通圖。A.5B.6C.7D.8無(wú)向圖G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},則對(duì)該圖進(jìn)行深度優(yōu)先遍歷,得到的序列為:DA.abecdfB.acfebdC.aebcfdD.aedfcb下述幾種排序措施中，規(guī)定內(nèi)存量最大的是__D__。A.插入排序B.選擇排序C.迅速排序D.歸并排序排序措施中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的對(duì)的位置上的措施，稱為__C__。A.希爾排序B.起泡排序C.插入排序D.選擇排序在待排序的元素序列基本有序的前提下，效率最高的排序措施是__A_。插入排序B.選擇排序C.迅速排序D.歸并排序下列排序算法中,哪一種是穩(wěn)定的排序算法?BA.直接選擇排序B.二分法插入排序C.希爾排序D.迅速排序?qū)蓚€(gè)各有n個(gè)元素的有序表歸并成一種有序表,其至少的比較次數(shù)AA.nB.2n-1C.2nD.n-1填空題算法的五個(gè)重要特性是有窮性,確定性,可行性,輸入和輸出.數(shù)據(jù)的樹型構(gòu)造和圖(網(wǎng))狀構(gòu)造合稱非線性構(gòu)造.抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性,而與數(shù)據(jù)在計(jì)算機(jī)中的表達(dá)和實(shí)現(xiàn)無(wú)關(guān).評(píng)價(jià)算法質(zhì)量的指標(biāo)是對(duì)的性,易讀性,強(qiáng)健性,高效性.數(shù)據(jù)構(gòu)造中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是:時(shí)間復(fù)雜度和空間復(fù)雜度.分析下面算法（程序段），的時(shí)間復(fù)雜度是__O(mn)__。s=0;for(i=0;i<n;i++)for(j=0;j<m;j++)s+=B[i][j];當(dāng)線性表元素的總數(shù)基本穩(wěn)定,且很少進(jìn)行刪除和插入操作時(shí),不過(guò)規(guī)定以最快的速度存取線性表中的元素,應(yīng)當(dāng)采用次序存儲(chǔ)構(gòu)造.次序表中邏輯上相鄰的元素的物理位置必然相鄰,而單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰.在各個(gè)結(jié)點(diǎn)查找概率相等的狀況下,從n個(gè)結(jié)點(diǎn)的單鏈表中查找一種結(jié)點(diǎn),平均要訪問(wèn)n/2個(gè)結(jié)點(diǎn).在單鏈表中設(shè)置頭指針的作用是:簡(jiǎn)化操作,減少邊界條件的判斷.在單鏈表中,除首元結(jié)點(diǎn)外,任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)的指針域指示.對(duì)于一種具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知p所指向結(jié)點(diǎn)后插入一種新結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(1),在值域?yàn)榻o定值的結(jié)點(diǎn)后插入一種新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n).在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一種指向_前驅(qū)結(jié)點(diǎn)__，另一種指向__后繼結(jié)點(diǎn)___。根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中每一結(jié)點(diǎn)包括的指針個(gè)數(shù),將線性表提成單鏈表和多重鏈表.在非空雙向鏈表中,在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過(guò)程如下,請(qǐng)補(bǔ)充p->prior=q->prior;q->prior->next=p;p->next=q;q->prior=p;一般狀況下,將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)當(dāng)設(shè)置棧.在處理計(jì)算機(jī)主機(jī)與打印機(jī)速度不匹配問(wèn)題時(shí),一般設(shè)置一種打印數(shù)據(jù)緩沖區(qū),該緩沖區(qū)一般是一種隊(duì)列數(shù)據(jù)構(gòu)造.循環(huán)隊(duì)列的引入,目的是為了克服假溢出現(xiàn)象.在棧頂指針為HS的鏈棧中,判斷?？盏臈l件是HS=NULL.在具有n個(gè)單元的循環(huán)隊(duì)列中,假如不專門設(shè)置隊(duì)滿標(biāo)志,則隊(duì)滿時(shí)共n-1有個(gè)元素.實(shí)現(xiàn)字符串拷貝的函數(shù)如下,請(qǐng)補(bǔ)足Voidstrcpy(char*s,char*t){while((*s++=*t++)!='\0');}空格串是__由一種或多種空格字符構(gòu)成的串__，其長(zhǎng)度等于_其包括的空格個(gè)數(shù)?？沾遣话ㄈ魏巫址拇?其長(zhǎng)度為0.設(shè)s='IAMASTUDENT',其長(zhǎng)度為:14.構(gòu)成串的元素只能是:字符.設(shè)s1='Good',s2='',s3='bye!',則s1,s2和s3連接的成果是Goodbye!若廣義表中每個(gè)元素都是原子時(shí),廣義表便成為線性表.廣義表的表尾是指除第一種元素外,剩余元素構(gòu)成的表.廣義表A=((a,b,c,d))的表頭為(a,b,c,d),表尾為().數(shù)組的存儲(chǔ)構(gòu)造采用次序存儲(chǔ)方式.設(shè)二維數(shù)組a[0..5,0..6],其每個(gè)字節(jié)占5個(gè)字節(jié),第一種元素的存儲(chǔ)地址為1000,若按列存儲(chǔ),則元素a[5,5]存儲(chǔ)地址為1175.高度為k的完全二叉樹至少有個(gè)葉子結(jié)點(diǎn).若一棵二叉樹有50個(gè)葉子結(jié)點(diǎn),則該二叉樹的總結(jié)點(diǎn)數(shù)至少是99.有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹的結(jié)點(diǎn)總數(shù)為2n-1.根據(jù)二叉樹的定義,具有三個(gè)結(jié)點(diǎn)的二叉樹有4種.某棵二叉樹的中序遍歷序列為abcdefg,后序遍歷序列為bdcafge,則該二叉樹的前序遍歷序列eacbdgf,該二叉樹對(duì)應(yīng)的森林包括2棵二叉樹.若二叉樹采用二叉鏈表存儲(chǔ)構(gòu)造,要互換其所有分支結(jié)點(diǎn)的左,右子樹的位置,運(yùn)用中序遍歷措施最為合適.線索二叉樹的左線索指向其前驅(qū),右線索指向其后繼.樹所對(duì)應(yīng)的二叉樹其根結(jié)點(diǎn)的右子樹一定為空.運(yùn)用樹的孩子兄弟表達(dá)法存儲(chǔ),可以將一棵樹轉(zhuǎn)化成二叉樹.設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有n(n-1)/2條邊.n個(gè)頂點(diǎn)的連通圖至少有n-1條邊.已知一種圖用領(lǐng)接矩陣表達(dá),計(jì)算第i個(gè)結(jié)點(diǎn)的入度的措施是求第i列非零元素的和.G是一種非連通的無(wú)向圖,共有28條邊,則該圖至少有9個(gè)頂點(diǎn).一種圖的鄰接矩陣表達(dá)法是唯一的，而鄰接表表達(dá)法是不唯一的。從鄰接矩陣可以看出,該圖共有3個(gè)頂點(diǎn),假如是無(wú)向圖,則共有2條邊.n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表達(dá)時(shí),則該矩陣至少有2(n-1)個(gè)頂點(diǎn).設(shè)圖中有n個(gè)頂點(diǎn),e條邊,假如用鄰接表表達(dá)圖,進(jìn)行深度優(yōu)先搜索遍歷的時(shí)間復(fù)雜度為O(n+e),假如用鄰接矩陣表達(dá)圖,時(shí)間復(fù)雜度為從平均時(shí)間性能而言,迅速排序排序最佳.堆排序是一種選擇排序,堆實(shí)質(zhì)上是一棵完全二叉樹結(jié)點(diǎn)的層次序列.對(duì)于具有n個(gè)元素的排序,堆排序的時(shí)間復(fù)雜度為.所需附加的存儲(chǔ)結(jié)點(diǎn)是O(1).用圖表回答問(wèn)題設(shè)某通信系統(tǒng)使用A，B，C，D，E，F(xiàn)，G，H個(gè)字符，出現(xiàn)的頻率w={５，２９，７，８，１４，２３，３，１１}，試構(gòu)造對(duì)應(yīng)的哈夫曼樹（請(qǐng)按左子樹根結(jié)點(diǎn)的權(quán)不不小于右子樹樹根結(jié)點(diǎn)的權(quán)的次序構(gòu)造）?答案如圖:DD8F23H111942A5B29C7E14G38152958100根據(jù)下面的鄰接鏈表，畫出對(duì)應(yīng)的圖，寫出每個(gè)頂點(diǎn)的度,并用鄰接矩陣表達(dá).v1v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3^^答案如圖所示:v1v2v1v2v3v4v5V6V2:2V3:3V4:2V5:4V6:2畫出下列樹對(duì)應(yīng)的二叉樹，并寫出其先根遍歷序列：BBDFCAEG先根遍歷序列：ABDEGFC答案如圖所示:BBEGDFCA畫出和下列二叉樹對(duì)應(yīng)的森林：AAAAABBBCCC答:AAAAABBBCCC閱讀下列算法，按規(guī)定做答.下面是刪除單鏈表L中最大元素所在結(jié)點(diǎn)的類C語(yǔ)言算法,請(qǐng)補(bǔ)足缺失部分使其完整.voidDelMax(LinkListL){r=L;p=L->next;if(p){m=p->data;(1);p=p->next;while(p){if((2)){(3);m=p->data;}(4);p=p->next;}q=r->next;(5);free(q);}}答案:(1)L->next=NULL;(2)p!=NULL;(3)q!=NULL;(4)p->next=r->next(5)r->next=p.閱讀下列算法，闡明該算法的作用。Statusalgorithm1(LinkQueue&Q){ SqStack Stack; QElemType Element; InitStack(Stack); while(!QueueEmpty(Q)){ DeQueue(Q,Element); Push(Stack,Element); } while(!StackEmpty(Stack)){ Pop(Stack,Element); EnQueue(Q,Element); }}答:運(yùn)用棧實(shí)現(xiàn)隊(duì)列的逆置.閱讀下列算法，闡明該算法的作用。Statusalgorithm2(StackS,inte){ Stack T; int d; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e)Push(T,d); }while(!StackEmpty(T)){ Pop(T,d); Push(S,d); }}答:運(yùn)用輔助棧T,將棧S中的元素e刪除.將下面程序改寫成遞歸過(guò)程.voidalgorithm3(intn){ int i=n;while(i>1){ printf(i--); }}答:voidalgorithm4(intj){if(j>1){printf(j);algorithm4(j-1) }}閱讀下列算法，闡明該算法的作用。BiTreealgorithm5(ElemTypePre[],ElemTypeIn[]){ intPreLen,InLen; inti,j; BiTreeBT; ElemType*subPre,*subIn; PreLen=strlen(Pre); InLen=strlen(In); if(PreLen!=InLen||PreLen==0)returnNULL; for(i=0;i<InLen&&In[i]!=Pre[0];i++); if(i==InLen)returnNULL; BT=(BiTNode*)malloc(sizeof(BiTNode)); BT->data=Pre[0]; subPre=(ElemType*)malloc((i+1)*sizeof(ElemType)); subIn=(ElemType*)malloc((i+1)*sizeof(ElemType)); for(j=0;j<i;j++){ subPre[j]=Pre[j+1]; subIn[j]=In[j]; } subPre[j]='\0';subIn[j]='\0'; BT->lchild=CreatBT(subPre,subIn); subPre=(ElemType*)malloc((PreLen-i)*sizeof(ElemType)); subIn=(ElemType*)malloc((PreLen-i)*sizeof(ElemType)); for(j=i+1;j<PreLen;j++){ subPre[j-i-1]=Pre[j]; subIn[j-i-1]=In[j]; } subPre[j-i-1]='\0';subIn[j-i-1]='\0'; BT->rchild=CreatBT(subPre,subIn); returnBT;}答:運(yùn)用一棵二叉樹的先序遍歷和中序遍歷還原該二叉樹.算法設(shè)計(jì)題設(shè)次序表L中的數(shù)據(jù)元素遞增有序.試寫一種算法,將e插入次序表中,規(guī)定插入后保持該表的有序性.voidInsertElem(SqList&L,ElemType){j=L.length-1;whi