數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2

一、選擇題〔1〕數(shù)據(jù)結(jié)構(gòu)往常是研究數(shù)據(jù)的〔A〕及它們之間的相互聯(lián)系。A.存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象C.聯(lián)系和抽象D.聯(lián)系與邏輯〔2〕在邏輯上能夠把數(shù)據(jù)結(jié)構(gòu)分紅：〔C〕。A.動(dòng)向結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)3〕數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地點(diǎn)和邏輯地點(diǎn)相同并且是連續(xù)的，稱之為C〕。A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.次序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)〔4〕算法剖析的兩個(gè)主要方面是〔A〕。A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)潔性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性〔5〕以下時(shí)間復(fù)雜度中最壞的是〔D〕。A.O〔1〕B.O〔n〕C.O〔log2n〕D.O〔n2〕6〕等概率情況下，在有n個(gè)結(jié)點(diǎn)的次序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為C〕。A．nB．(n-1)/2C．n/2D．(n+1)/27〕設(shè)有編號(hào)為1，2，3，4的四輛列車，次序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，以下不可能的出站次序?yàn)?D)A．1234B．1243C．1324D．1423〔8〕如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，那么出棧操作時(shí)〔B〕A．必須鑒別棧是否滿B．必須鑒別棧是否空C．必須鑒別棧元素種類D．隊(duì)?？刹蛔鋈魏舞b別〔9〕鏈棧與次序棧相比，有一個(gè)比較顯然的優(yōu)點(diǎn)是〔B〕。A．插入操作更加方便B．往常不會(huì)出現(xiàn)棧滿的情況。C．不會(huì)出現(xiàn)?？盏那闆rD．刪除操作根加方便〔10〕插入和刪除只能在一端進(jìn)行的線性表，稱為(C)。A．行列B．循環(huán)行列C．棧D．循環(huán)?！?1〕假定進(jìn)隊(duì)的序列為：A，B，C，D，那么出隊(duì)的序列是〔C〕。A．B，C，D，AB．A，C，B，DC．A，B，C，DD．C，B，D，A〔12〕假定用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)行列，且目前front和rear的值分別為3和0，當(dāng)從行列中刪除一個(gè)元素，再參加兩個(gè)元素后，front和rear的值分別為(B)。A．5和1B．4和2C．2和4D．1和5〔13〕S="morning"，執(zhí)行求子串函數(shù)SubStr(S,2,2)后的結(jié)果為(B)。A．"mo"B．"or"C．"in"D．"ng"〔14〕S1="good"，S2="morning"，執(zhí)行串通接函數(shù)ConcatStr(S1,S2)后的結(jié)果為(A)。A．"goodmorning"B．"goodmorning"C．"GOODMORNING"D．"GOODMORNING"精選〔15〕S1="good"，S2="morning"，執(zhí)行函數(shù)SubStr(S2,4,LenStr(S1))后的結(jié)果為(B)。A．"good"B．"ning"C．"go"D．"morn"16〕設(shè)串S1="ABCDEFG"，S2="PQRST",那么ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的結(jié)果串為(D)。A．BCDEFB．BCDEFGC．BCPQRSTD.BCDEFEF二維數(shù)組A[6][10]，每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，假定按行優(yōu)先次序存放數(shù)組元素a[3][5]的存儲(chǔ)地點(diǎn)是1000，那么a[0][0]的存儲(chǔ)地點(diǎn)是〔B〕。A．872B．860C．868D．864〔18〕在一棵擁有五層的滿二叉樹中，結(jié)點(diǎn)的總數(shù)為〔B〕A．16B．31C．32D．33〔19〕擁有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為〔C〕A．5B．6C．7〔20〕擁有n〔n>1〕個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i〔2i>n〕的左孩子結(jié)點(diǎn)是〔D〕。A．2iB．2i+1C．2i-1D．不存在〔假定2i<=n，那么答案為A〕〔21〕將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，那么編號(hào)為45的結(jié)點(diǎn)的左孩子編號(hào)為〔B〕。A．46B．47C．90D．91〔22〕將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，那么編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為〔B〕。A．98B．99C．50D．100〔23〕用5個(gè)權(quán)值{3,2,4,5,1}結(jié)構(gòu)的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是〔B〕。Ａ．32Ｂ．33Ｃ．34Ｄ．15〔先結(jié)構(gòu)哈夫曼樹，WPL=〔1+2〕*3+〔3+4+5〕*2=33〕〔24〕二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)的個(gè)數(shù)〔C〕。A．無(wú)關(guān)B．相等C．多一個(gè)D．少一個(gè)〔25〕關(guān)于一個(gè)擁有n個(gè)極點(diǎn)的有向圖的邊數(shù)最多有〔B〕。A．nB．n(n-1)C．n(n-1)/2D．2n〔26〕在一個(gè)擁有n個(gè)極點(diǎn)的無(wú)向圖中，要連通全部極點(diǎn)起碼需要〔C〕條邊。A．nB．n+1C．n-1D．n/227〕關(guān)于一個(gè)擁有n個(gè)極點(diǎn)和e條邊的無(wú)向圖，采用毗鄰表表示，那么表頭向量大小為C〕。A．n-1B．n+1C．nD．n+e〔28〕在圖的表示法中，表示形式唯一的是〔A〕。A．毗鄰矩陣表示法B．毗鄰表表示法精選C．逆毗鄰表表示法D．毗鄰表和逆毗鄰表表示法〔29〕對(duì)有14個(gè)元素的有序表A[1..14]作二分查找，查找元素A[4]時(shí)的被比較元素依次為〔C〕。A．A[1]，A[2]，A[3]，A[4]B．A[1]，A[14]，A[7]，A[4]C．A[7]，A[3]，A[5]，A[4]D．A[7]，A[5]，A[3]，A[4]〔30〕不可能生成以下列圖二叉排序樹的重點(diǎn)字的序列是〔A〕。A．45312B．42531C．45213D．42315425331〕排序方法中，從無(wú)序序列中選擇重點(diǎn)字最小的記錄，將其與無(wú)序區(qū)〔初始為空〕的第一個(gè)記錄互換的排序方法，稱為(D)。A．希爾排序B．合并排序C．插入排序D.選擇排序〔32〕每次把待排序方的區(qū)間區(qū)分為左、右兩個(gè)區(qū)間，其中左區(qū)間中元素的值不大于基準(zhǔn)元素的值，右區(qū)間中元素的值不小于基準(zhǔn)元素的值，此種排序方法叫做〔C〕。A．冒泡排序B．堆排序C．迅速排序D.合并排序〔33〕直接插入排序的方法是從第〔B〕個(gè)元素開(kāi)始，插入到前邊適合地點(diǎn)的排序方法。A．1B．2C．3D．n〔34〕堆的形狀是一棵〔C〕。A．二叉排序樹B．滿二叉樹C．完全二叉樹D．平衡二叉樹〔35〕一組記錄的排序碼為(25，48，16，35，79，82，23，40)，其中含有4個(gè)長(zhǎng)度為2的有序表，按合并排序的方法對(duì)該序列進(jìn)行一趟合并后的結(jié)果為：〔A〕。A，16253548234079823672B．16253548798223364072C．16254835798223364072D．1625354879233640728236〕一個(gè)數(shù)據(jù)序列的重點(diǎn)字為：〔46，79，56，38，40，84〕，采用迅速排序，并以第一個(gè)數(shù)為基準(zhǔn)獲得第一次區(qū)分的結(jié)果為：〔C〕A．〔38，40，46，56，79，84〕B．〔40，38，46，79，56，84〕C．〔40，38，46，56，79，84〕D．〔40，38，46，79，56，84〕二、填空題〔1〕假定一個(gè)算法中的語(yǔ)句頻度之和為T〔n〕=6n+3nlog2n，那么算法的時(shí)間復(fù)雜度為Onlog2n〕。2〕當(dāng)線性表的元素總數(shù)根本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最迅速度存取線性表中的元素時(shí)，應(yīng)采用次序存儲(chǔ)結(jié)構(gòu)?！?〕對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜?！?〕雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，那么需要執(zhí)行的操作為：精選p->prior->next=p->next?！?〕A+B/C-D*E的后綴表達(dá)式是：ABC/+DE*-?！?〕解決次序行列“假溢出〞的方法是采用循環(huán)行列?！?〕循環(huán)行列的隊(duì)首指針為front，隊(duì)尾指針為rear，那么隊(duì)空的條件為front==rear?！?〕設(shè)循環(huán)行列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)安閑元素，行列的最大空間為MAXLEN，那么隊(duì)滿標(biāo)志為：front==(rear+1)%MAXLEN?！?〕設(shè)循環(huán)行列的容量為40〔序號(hào)從0到39〕，現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有front=11，rear=19，那么循環(huán)行列中還有8個(gè)元素?！睱=(N＋rear－front)%N=〔40＋19－11〕%40=8〕〔10〕設(shè)S="MyMusic"，那么LenStr(s)=_8?！?1〕兩個(gè)字符串分別為：S1="Todayis"，S2="30July,2005",ConcatStr(S1,S2)的結(jié)果是：Todayis30July,2005?！?2〕求子串函數(shù)SubStr("Todayis30July,2005",13,4)的結(jié)果是：July?！?3〕在串的運(yùn)算中，EqualStr(aaa,aab)的返回值為<0?！?4〕多維數(shù)組的次序存儲(chǔ)方式有按行優(yōu)先次序存儲(chǔ)和按列優(yōu)先次序存儲(chǔ)兩種?！?5〕在多維數(shù)組中，數(shù)據(jù)元素的寄存地點(diǎn)能夠直接經(jīng)過(guò)地點(diǎn)計(jì)算公式算出，所以多維數(shù)組是一種隨機(jī)存取結(jié)構(gòu)?！?6〕tail(head((a,b),(c,d))=b?！?7〕設(shè)廣義表((a,b,c))，那么將c分離出來(lái)的運(yùn)算是head(tail(tail(head(L))))〔18〕廣義表LS=〔a,(b),((c,(d)))〕的長(zhǎng)度是3?！?9〕廣義表LS=〔a,(b),((c,(d)))〕的深度是4?！?1〕廣義表LS=〔a,(b),((c,(d)))〕的表尾是((b),((c,(d))))。數(shù)組元素a[0..2][0..3]的實(shí)際地點(diǎn)上2000，元素長(zhǎng)度是4，那么LOC[1,2]=2024?！?3〕n階下三角矩陣，因?yàn)閷?duì)角線的上方是同一個(gè)常數(shù)，需要n〔n-1〕/2+1個(gè)存儲(chǔ)單元?！?4〕稀疏矩陣的三元組有3列?！?5〕稀疏矩陣的三元組中第1列存儲(chǔ)的是數(shù)組中非零元素所在的行數(shù)?！?6〕n階對(duì)稱矩陣，如果只存儲(chǔ)下三角元素，只要要n〔n-1〕/2個(gè)存儲(chǔ)單元。(27)哈夫曼樹是帶權(quán)路徑長(zhǎng)度最小的二叉樹。(28)由二叉樹的后序和中序遍歷序列，能夠唯一確定一棵二叉樹?！?9〕某二叉樹的中序遍歷序列為:DEBAC，后序遍歷序列為：EBCAD。那么前序遍歷序列為：DABEC?！?0〕設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，精選那么二叉樹中葉結(jié)點(diǎn)是：E、F、H?！?1〕關(guān)于二叉樹來(lái)說(shuō)，第i層上至多有2i-1個(gè)結(jié)點(diǎn)?！?2〕深度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)?！?3〕采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，一共有2n個(gè)指針域?！?4〕采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，共有空指針n+1個(gè)?！?5〕將一棵完全二叉樹按層次編號(hào)，關(guān)于隨意一個(gè)編號(hào)為i的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的編號(hào)為：2*i?！?6〕圖常用的存儲(chǔ)方式有毗鄰矩陣和毗鄰表等?！?7〕圖的遍歷有：深度優(yōu)先搜和廣度優(yōu)先搜等方法。38〕設(shè)有一稀疏圖G，那么G采用_毗鄰表____存儲(chǔ)比較節(jié)儉空間。設(shè)有一濃密圖G，那么G采用_毗鄰矩陣____存儲(chǔ)比較節(jié)儉空間。在重點(diǎn)字序列〔7，10，12，18，28，36，45，92〕中，用二分查找法查找重點(diǎn)字92，要比較4次才找到。(41)二叉排序樹是一種動(dòng)向查找表。(42)哈希表是按散列存儲(chǔ)方式結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)(43)哈希法既是一種存儲(chǔ)方法，又是一種查找方法。(44)散列表的查找效率主要取決于散列表造表時(shí)選用的散列函數(shù)和辦理矛盾的方法。三、程序填空〔1〕在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試達(dá)成以下程序填空。structnode{elemtypedata;node*next;};voidlkinsert(node*head,elemtypex){node*s,*p;s=newnode;s->data=x;p=head->next;while(p!=NULL)&&(p->data!=a)____p=p->next;if(p==NULL)cout<<"不存在結(jié)點(diǎn)a!";else{_____s->next=p->next______;___p->next=s__________;}}(2)假定用一個(gè)循環(huán)單鏈表表示一個(gè)循環(huán)行列，該行列只設(shè)一個(gè)隊(duì)尾指針rear，試填空精選達(dá)成向循環(huán)行列中插入一個(gè)元素為x的結(jié)點(diǎn)的函數(shù)。typedefstructqueuenode//定義行列的存儲(chǔ)結(jié)構(gòu){intdata;structqueuenode*next;}QueueNode;InQueue(QueueNode*rear,intx)//向行列插入元素為x的函數(shù){QueueNode*rear;QueueNode*head,*s;s=newQueueNode;s->data=x;if(rear==NULL)//循環(huán)行列為空，那么成立一個(gè)結(jié)點(diǎn)的循環(huán)行列{rear=s;rear->next;}else{head=rear->next;//循環(huán)行列非空，那么將s插到后邊rear->next=s;rear=s;rear->next=head;}}〔3〕下面程序是把兩個(gè)串r1和r2首尾相連的程序，即：r1=r1+r2，試達(dá)成程序填空。typedefStruct{charvec[MAXLEN];//定義合并后串的最大長(zhǎng)度intlen;//len為串的長(zhǎng)度}St;voidConcatStr(Str*r1,Str*r2)//字符串通接函數(shù){inti;cout<<r1->vec<<r2->vec;if(r1->len+r2->len>MAXLEN)cout<<"兩個(gè)串太長(zhǎng)，溢出！";else{for(i=0;i<r2->len;i++)//把r2連結(jié)到r1r1->vec[r1->len+i]=r2->vec[i];r1->vec[r1->len+i]='\0';//添上字符串結(jié)束標(biāo)記r1->len=r1->len+r2->len;//改正新串長(zhǎng)度}}(4)下面算法是判斷字符串是否為回文〔即正讀和倒讀相同〕，試達(dá)成程序填空。#include"stdio.h"typedefstruct{charvec[MAXLEN];intlen;}str;voidPalindrome(strs)精選{inti=0;ingj=s.len-1;while(j-i>=1){if(s.vec[i]==s.vec[j]){i++;j--;continue}//(或j=j+1)elsebreak;}if(j-i>=1)cout<<"Itisnotapalindrome\n";elsecout<<"Itisapalindrome\n";}(5)voidBInsSort()//按遞增序?qū)[1]~R[n]進(jìn)行二分插入排序{inti,j,low,high,m;for(i=2;i<=n;i++){R[0]=R[i];//設(shè)定R[0]為監(jiān)督哨low=1;high=n；while(low<=high){m=(low+high)/2;if(R[0]<R[m])high=m-1;elselow=m+1;}for(j=i-1;j>=high+1;j--)R[j+1]=R[j];//元素后移R[high]=R[0];//插入}}四、應(yīng)用題〔1〕一棵二叉樹的后序遍歷和中序遍歷的序列分別為：ACDBGIHFE和ABCDEFGHI。請(qǐng)畫出該二叉樹，并寫出它的前序遍歷的序列。解：恢復(fù)的二叉樹為：EBFAD精選HCGI其前序遍歷的序列為：EBADCFHGI〔2〕把以下一般樹變換為二叉樹①1②A2BCD345EFGHI67J8解：①1②A2B3EC4FHD5JGI673〕把以下森林變換為二叉樹①②③AFHBCDGIJEK精選解：ABFCGHEDIKJ4〕把以下二叉樹還原為森林ABECFGDHI解：還原后的二叉樹為：①②③AEGBCDFHI5〕假定用于通信的電文僅由A、B、C、D、E、F、G8個(gè)字母組成，字母在電文中出現(xiàn)的頻次分別為7，19，2，6，32，3，21，10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。解：以權(quán)值：2、3、6、7、10、19、21、32結(jié)構(gòu)哈夫曼樹：〔左子為0，右子為1?！?0010字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻次040601A1010710B001919212832C1000021D100160精選1117E11320D100013101E0121〔6〕有向圖如以下列圖所示，畫出毗鄰矩陣和毗鄰表解：毗鄰矩陣12345

①②③④⑤101101200010300001410000500010毗鄰表1235∧24∧35∧41∧54∧〔7〕一個(gè)無(wú)向圖有6個(gè)結(jié)點(diǎn)，9條邊，這9條邊依次為(0,1)，(0,2)，(0,4)，(0,5)，(1,2)，(2,3)，(2,4)，(3,4)，(4,5)。試畫出該無(wú)向圖，并從極點(diǎn)0出發(fā)，分別寫出按深度優(yōu)先搜尋和按廣度優(yōu)先搜尋進(jìn)行遍歷的結(jié)點(diǎn)序列。解：01245精選3從極點(diǎn)0出發(fā)的深度優(yōu)先搜尋遍歷的結(jié)點(diǎn)序列：012345〔答案不唯一〕從極點(diǎn)0出發(fā)的廣度優(yōu)先搜尋遍歷的結(jié)點(diǎn)序列：012453〔答案不唯一〕〔8〕網(wǎng)G的毗鄰矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。0810110803013103040110407013070解：1最小生成樹：8111108233442341373455關(guān)于給定結(jié)點(diǎn)的重點(diǎn)字會(huì)合K={5，7，3，1，9，6，4，8，2，10}，〔1〕試結(jié)構(gòu)一棵二叉排序樹；〔2〕求等概率情況下的平均查找長(zhǎng)度ASL。解：〔1〕結(jié)構(gòu)二叉排序樹：〔2〕ASL=(1*1+2*2+3*4+4*3)/10=2.953714692810給定結(jié)點(diǎn)的重點(diǎn)字序列為：19，14，23，1，68，20，84，27，55，11，10，79。設(shè)散列表的長(zhǎng)度為13，散列函數(shù)為：H〔K〕=K%13。試畫出線性探測(cè)再散列解決矛盾時(shí)所結(jié)構(gòu)的散列表，并求出其平均查找長(zhǎng)度。解：線性探測(cè)再散列解決矛盾時(shí)所結(jié)構(gòu)的散列表：012345678910111214168275519208479231110①②①④③①①③⑨①①③平均查找長(zhǎng)度ASL=〔1*6+2*1+3*3+4*1+9*1〕/12=30/3=3精選給定結(jié)點(diǎn)的重點(diǎn)字序列為：47，7，29，11，16，92