國家開放大學《數(shù)據(jù)結構（本）》期末復習題參考答案

國家開放大學《數(shù)據(jù)結構（本）》期末復習題參考答案一、單選題1.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（）。A.存儲結構B.物理和存儲結構C.物理結構D.邏輯結構2.在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分為（）。A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C.內(nèi)部結構和外部結構D.線性結構和非線性結構3.線性結構中數(shù)據(jù)元素之間的關系是（）A.一對一B.一對多C.多對一D.多對多4.樹形結構中數(shù)據(jù)元素之間的關系是（）A.一對一B.一對多C.多對一D.多對多5.數(shù)據(jù)的存儲結構包括數(shù)據(jù)元素的表示和（）。A.數(shù)據(jù)處理的方法B.相關算法C.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關系的表示6.每個存儲結點只存儲一個數(shù)據(jù)元素，各結點存儲在連續(xù)的存儲空間，該存儲方式是（）存儲方式。A.順序B.鏈接C.索引D.散列7.線性表中（）稱為線性表的長度。A.數(shù)據(jù)最大值B.數(shù)據(jù)最小值C.數(shù)據(jù)元素個數(shù)D.表的行數(shù)8.設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（）。A.n-iB.n-i-1C.n-i+1D.i9.設有一個長度為n的順序表，要刪除第i個元素,則需移動元素的個數(shù)為（）。A.iB.n-i-1C.n-iD.n-i+110.有關線性表的正確說法是（）。A.線性表至少要求一個元素B.每個元素都有一個直接前驅和一個直接后繼C.表中的元素必須按由小到大或由大到下排序D.除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅和一個直接后繼11.在線性表的順序結構中，以下說法正確的是（）。A.邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機訪問的C.進行數(shù)據(jù)元素的插入、刪除效率較高D.邏輯上相鄰的元素在物理位置上也相鄰12.在非空雙向循環(huán)鏈表的*p結點之前插入*q結點的操作是（）。A.p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;B.p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;C.q->next=p;q->prior=p->prior;p->prior=q;p->prior->next=q;D.q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;13.對鏈表,以下敘述中正確的是（）。A.不能隨機訪問任一結點B.插入刪除元素的操作一定要要移動結點C.結點占用的存儲空間是連續(xù)的D.可以通過下標對鏈表進行直接訪問14.非空的單向循環(huán)鏈表的尾結點滿足（）（設頭指針為head，指針p指向尾結點）。A.p->next==headB.p==NULLC.p==headD.p->next==NULL15.設頭指針為head的非空的單向鏈表，指針p指向尾結點,則通過以下操作（)可使其成為單向循環(huán)鏈表。A.head=p;B.p=head;C.C.p->next=NULL;D.p->next=head;16.鏈表不具有的特點是（）。A.不必事先估計存儲空間B.可隨機訪問任一元素C.邏輯上相鄰的元素在物理位置上不一定相鄰D.插入刪除不需要移動元素17.在一個單鏈表Head中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行（）。A.Head=p;p->next=Head;B.p->next=Head;Head=p;C.p->next=Head;p=Head;D.p->next=Head->next;Head->next=p;18.在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執(zhí)行（）。A.p->next=s;s->next=p->next;B.p->next=s->next;C.p=s->next;D.s->next=p->next;p->next=s;19.對于一個線性表，若要求既能進行較快地插入和刪除，又要求存儲結構能夠反映數(shù)據(jù)元素之間的邏輯關系，則應該（）。A.以順序存儲方式B.以鏈接存儲方式C.以索引存儲方式D.以散列存儲方式20.若Head為一個帶表頭結點的單鏈表的表頭指針，則該表為空表的條件是（）。A.Head==NULLB.Head->next==NULLC.Head->next==HeadD.Head!=NULL21.每個存儲結點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（）存儲方式。A.順序B.鏈接C.索引D.散列22.非空的單向循環(huán)鏈表L的尾結點（由p所指向）滿足（）。A.p==NULLB.p->next==NULLC.p==LD.p->next==L23.在雙向循環(huán)雙鏈表中，刪除*p結點需要（）。A.p->next->prior=p->prior;p->prior->next=p->next;B.p->prior->next=p->next;p->next->prior=p->prior;C.p->prior->next=p;p->prior=p->prior->prior;D.p->prior=p->next->next;p->next=p->prior->prior;24.鏈表所具備的特點是（）。A.可以隨機訪問任一結點B.占用連續(xù)的存儲空間C.插入刪除元素的操作不需要移動元素結點D.可以通過下標對鏈表進行直接訪問25.帶頭結點的雙向循環(huán)鏈表L為空表的條件是（）。A.L==NULLB.L->next->prior=NULLC.L->next==LD.L->prior==NULL26.在一個帶頭結點的單向鏈表中，若要在指針q所指結點后插入p指針所指結點，則執(zhí)行（）。A.p->next=q->next;q->next=p;B.q->next=p->next;p=q;C.p->next=q->next;p->next=q;D.q->next=p->next;p->next=q;27.若某表最常用的操作是在最后一個結點之后插入一個結點，則采用_____最節(jié)省運算時間。A.單鏈表B.給出表頭指針的單向循環(huán)鏈表C.雙鏈表D.帶頭結點的雙向循環(huán)鏈表28.設有兩個長度為n的單向鏈表，結點類型相同，分別是循環(huán)鏈表和非循環(huán)鏈表，則（）。A.對于兩個鏈表來說，刪除第一個結點的操作，其時間復雜度都是O(1)B.對于兩個鏈表來說，刪除最后一個結點的操作，其時間復雜度都是O(n)C.循環(huán)鏈表要比非循環(huán)鏈表占用更多的內(nèi)存空間D.循環(huán)鏈表與非循環(huán)鏈表占用相同的內(nèi)存空間29.單向線性鏈表的結點包含data域和（）域。A.nextB.rightC.leftD.head30.帶頭結點的單向鏈表為空的判斷條件是（）（設頭指針為head）。A.head==NULLB.head!=NULLC.head->next==headD.head->next==NULL31.當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==-1表示?？?，則入棧應該執(zhí)行（）語句修改top指針。A.top++B.top—C.top=0D.！top32.從順序棧中刪除新元素時，應當（）。A.先移動棧頂指針，再存入元素B.先讀取元素，再移動棧頂指針C.先后次序無關緊要D.同時進行3.（）的一個重要應用是在程序設計中實現(xiàn)遞歸調(diào)用。A.雙向鏈表B.循環(huán)鏈表C.棧D.隊列34.棧是一種操作受限的線性表，其限制是（）。A.僅允許在表的一端進行插入和刪除操作B.僅允許進行插入操作C.僅允許進行刪除操作D.僅允許在表的一端進行插入，而在另一端進行刪除操作35.表達式3*(x+y)/(2-x)的后綴表達式是（）。A.3xy+2*2x-/B.3x*y+2x-/C.3xy2x*+/-D.3xy+*2x-/36.當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？?，則入棧應該執(zhí)行（）語句修改top指針。A.top++B.top—C.top=0D.！top37.在一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪結點的值，則執(zhí)行（）。A.x=top;top=top->next;B.x=top->data;C.top=top->next;x=top->data;D.x=top->data;top=top->next;38.關于單鏈表實現(xiàn)的鏈棧，下面說法正確的是（）。A.表頭為棧頂效率高B.表尾為棧頂效率高C.表中為棧頂效率高D.以上答案均不對39.表達式8/5+4的后綴表達式是（）。A.854/+B.85/+4C.84+5/D.85/4+40.棧頂指針通常命名為（）A.nextB.topC.rearD.front41.元素4，6，8，10按順序依次進棧，按該棧的可能輸出序列依次入隊列，該隊列的可能輸出序列是（）（進棧出棧可以交替進行）。A.10，8，4，6B.10，6，4，8C.8，4，6，10D.10，8，6，442.一般情況下，將遞歸算法轉換成等價的非遞歸算法應該設置（）。A.棧B.隊列C.堆?；蜿犃蠨.數(shù)組43.棧的基本運算包括（）A.求棧長B.修改棧元素C.取棧底元素D.取棧頂元素44.若讓元素a，b，c依次進棧，則出棧順序不可能為（）。A.c，b，aB.b，a，cC.c，a，bD.a，c，b45.通常的使用順序?；蛘哝湕崿F(xiàn)遞歸算法，下面哪個說法正確（）。A.順序棧效率高B.鏈棧效率高C.順序棧和鏈棧性能基本相同D.視情況而定46.一個棧的進棧序列是10，20，30，40，50，則棧的不可能輸出序列是（）（進棧出棧可以交替進行）。A.10,20,30,40,50B.40,30,50,10,20C.40,50,30,20,10D.50,40,30,20,1047.向順序棧中壓入新元素時，應當（）。A.先移動棧頂指針，再存入元素B.先存入元素，再移動棧頂指針C.先后次序無關緊要D.同時進行48.鏈棧和順序棧相比，有一個比較明顯的優(yōu)點，即（）。A.插入操作更加方便B.通常不會出現(xiàn)棧滿的情況C.不會出現(xiàn)棧空的情況D.刪除操作更加方便49.以下數(shù)據(jù)結構中（）是線性結構。A.有向圖B.堆C.完全二叉樹D.棧50.表達式a*(b+c)-d的后綴表達式是（）。A.abcd*+-B.abc+*d-C.abc*++d-D.-+*abcd51.在一個棧頂指針為top的鏈棧中，將一個p指針所指的結點入棧，應執(zhí)行（）。A.top->next=p;B.p->next=top->next;top->next=p;C.p->next=top;top=p;D.p->next=top->next;top=top->next52.一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（）。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，153.判斷一個順序隊列sq（最多元素為m）為空的條件是（）。A.sq->rear-sq->front==mB.sq->rear-sq->front-1==mC.sq->front==sq->rearD.sq->front==sq->rear+154.以下（）不是隊列的基本運算。A.向隊尾插入一個新元素B.判斷一個隊列是否為空C.從隊列中刪除第i個元素D.讀取隊首元素的值55.假設鏈隊的隊首和隊尾指針是F和R，那么隊空的條件是（）。A.F==RB.F！=NULLC.R=NULLD.F！=R56.隊列是一種操作受限的線性表，其限制是（）。A.僅允許在表的一端進行插入和刪除操作B.僅允許進行插入操作C.僅允許進行刪除操作D.僅允許在表的一端進行插入，而在另一端進行刪除操作57.順序隊列中，隊首元素位置為5，則隊首指針位置為（）。A.3B.4C.5D.658.（）的一個重要應用是解決主機和打印機之間速度不匹配的問題。A.雙向鏈表B.循環(huán)鏈表C.棧D.隊列59.下面關于串的敘述中，正確的是（）。A.串其實是字母序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串只能采用順序存儲60.空串與空格串（）。A.相同B.不相同C.可能相同D.無法確定61.下列是”abcd321ABCD”的子串的選項是（）。A.“21ABC”B.“abcABCD”C.“abcD”D.“321a”62.串是什么？（）。A.多個字母的序列B.任意個字母的序列C.有限個字符的序列D.無數(shù)個字符的序列63.以下陳述中正確的是（）。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串64.下列說法不正確的是（）。A.串不是線性結構B.串中元素可能是字母、數(shù)字或其他字符C.空串和空白串不一樣D.串的長度可能等于零65.兩個字符串相等的條件是（）。A.串的長度相等B.含有相同的字符集C.都是非空串D.兩個串的長度相等且對應位置的字符相同66.以下四個串中最小的是（）。A.“ABADF”B.“ABAFD”C.“ABADFA”D.“ABAF”67.串函數(shù)Strcat（a,b）的功能是進行串（）。A.比較B.復制C.賦值D.連接68.字符串處理函數(shù)Strcmp（a,b）的功能是進行串（）。A.連接B.比較C.復制D.模式匹配69.設有兩個串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（）。A.求子串B.連接C.模式匹配D.求串長70.兩個字符串相等的條件是（）。A.兩串的長度相等B.兩串包含的字符相同C.兩串的長度相等，并且兩串包含的字符相同D.兩串的長度相等，并且對應位置上的字符相同71.某串的長度小于一個常數(shù)，則采用（）存儲方式最節(jié)省空間。A.鏈式B.順序C.堆結構D.無法確定72.如果進行串的比較，下列哪個串最大？（）A.“BEIJING”B.“BEI”C.“BEFANG”D.“BEFI”73.廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長度是()。A.6B.10C.8D.474.一個非空廣義表的表頭（）。A.不可能是原子B.只能是子表C.只能是原子D.可以是子表或原子75.下列廣義表中的線性表是（）。A.E(a,(b,c))B.E(a,E)C.E(a,b)D.E(a,L())76.廣義表(a,(d,a,b),h,(e,((i,j),k)))深度是()。A.6B.10C.8D.477.廣義表（a，a，b，d，e，（（i，j），k））的表頭是（）。A.（a）B.aC.a,（a，b）D.（a，a，b）78.設有一個廣義表A(a)，其表尾為（）。A.aB.(())C.()D.(a)79.深度為5的二叉樹至多有（）個結點。A.16B.32C.31D.1080.在一棵二叉樹中，若編號為8的結點存在右孩子，則右孩子的順序編號為（）。A.18B.16C.15D.1781.在二叉樹的第4層最多含有（）個結點。A.8B.15C.16D.1782.假定一棵二叉樹中，葉子結點數(shù)為10，單分支結點數(shù)為30，則雙分支結點數(shù)為（）。A.7B.8C.9D.1983.在一棵二叉樹上，第5層的結點數(shù)最多為（）。A.8B.15C.16D.3284.一棵高度為4的二叉樹，最多含有（）個結點。A.8B.15C.16D.1785.在一棵樹中，度為0的結點稱作（）。A.葉子結點B.分支結點C.孩子結點D.雙親結點86.樹中所有結點的度等于所有結點數(shù)加（）。A.1B.0C.2D.-187.在一棵度具有5層的滿二叉樹中結點總數(shù)為（）。A.31B.32C.33D.1688.二叉樹的按層遍歷算法需要使用（）A.隊列B.棧C.廣義表D.二維數(shù)組89.對一棵二叉樹中順序編號為i的結點，若它存在左孩子，則左孩子結點的編號為（）。A.2iB.2i+1C.2i-1D.i/290.權值為{1，2，6，8}的四個結點構成的哈夫曼樹的帶權路徑長度是（）。A.18B.28C.19D.2991.利用2、4、5、10這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹的帶權路徑長度為（）。A.18B.16C.38D.3092.哈夫曼樹只有（）的結點的二叉樹。A.度為0B.度為2C.度為2和度為0D.度為2或度為093.設a，b為一棵二叉樹的兩個結點，在后續(xù)遍歷中，a在b前的條件是（）。A.a在b上方B.a在b下方C.a在b左方D.a在b右方94.由六個葉子結點a、b、c、d、e、f構造的哈夫曼樹（）。A.唯一B.不唯一C.不確定D.以上都不對95.設一棵哈夫曼樹有20個葉子結點，該樹共有（）個非葉子結點。A.19B.20C.39D.4096.無向圖的鄰接矩陣是一個（）。A.對稱矩陣B.零矩陣C.上三角矩陣D.對角矩陣97.在無向圖中定義頂點vi與vj之間的路徑為從vi到vj的一個（）。A.頂點序列B.邊序列C.權值總和D.邊的條數(shù)98.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。A.1/2B.1C.2D.499.一個具有n個頂點的有向完全圖包含（）條邊。A.n（n-1）B.n（n+1）C.n（n-1）/2D.n（n+1）/2100.在一個無向圖中，若兩頂點之間的路徑長度為k，則該路徑上的頂點數(shù)為（）。A.kB.k+1C.k+2D.2k101.鄰接表是圖的一種（）。A.順序存儲結構B.鏈式存儲結構C.索引存儲結構D.散列存儲結構102.在有向圖的鄰接表中，每個頂點鄰接表鏈接著該頂點所有（）鄰接點。A.入邊B.出邊C.入邊和出邊D.不是入邊也不是出邊103.對有18個元素的有序表作二分查找，則查找A[3]的比較序列的下標可能為（）。A.1、2、3B.9、5、2、3C.9、5、3D.9、4、2、3104.已知一個有序表為{11,22,33,44,55,66,77,88,99}，則順序查找元素55需要比較（）次。A.3B.4C.5D.6105.有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A.37/12B.39/12C.41/12D.35/12106.有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A.29/10B.31/10C.26/10D.29/9107.對線性表進行二分查找時，要求線性表必須（）。A.以順序存儲方式B.以鏈接存儲方式C.以順序存儲方式，且數(shù)據(jù)元素有序D.以鏈接存儲方式，且數(shù)據(jù)元素有序108.對于順序存儲的有序表{5，12，20，26，37，42，46，50，64}，若采用折半查找，則查找元素26的比較次數(shù)是（）。A.2B.3C.4D.5109.一組記錄的關鍵字序列為（80，57，41，39，46，47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（）。A.39，47，46，80，41，57B.41，39，46，47，57，80C.39，46，41，57，80，47D.39，80，46，47，41，57110.每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的關鍵字均小于等于基準記錄的關鍵字，右區(qū)間中記錄的關鍵字均大于等于基準記錄的關鍵字，這種排序稱為（）。A.插入排序B.快速排序C.堆排序D.歸并排序111.設有2000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（）排序法。A.快速排序B.基數(shù)排序C.冒泡排序D.堆排序112.一組記錄的關鍵字序列為（26，59，36，18，20，25），利用堆排序的方法建立的初始小根堆為（）。A.18，20，36，59，26，25B.18，20，25，59，26，36C.26，18，59，20，36，25D.26，59，36，18，20，25113.對數(shù)據(jù)元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結果時的結果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（）。A.插入排序法B.選擇排序法C.冒泡排序法D.堆排序法114.就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關系是（）。A.堆排序>快速排序>歸并排序B.堆排序<快速排序<歸并排序C.堆排序<歸并排序<快速排序D.堆排序>歸并排序>快速排序115.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。A.插入排序B.交換排序C.選擇排序D.歸并排序116.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。A.插入排序B.交換排序C.選擇排序D.歸并排序117.一組記錄的關鍵字序列為（60，47，80，57，39，41，46，30），利用歸并排序的方法,第一趟歸并后的結果為（）。A.47，57，60，80，30，39，41，46B.30，39，41，46，47，57，60，80C.30，47，80，57，39，41，46，60D.47，60，57，80，39，41，30，46118.將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（）。A.2n-1B.n-1C.2nD.n119.已知10個數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，26，43），對該數(shù)列從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）。A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.16，28，34，54，62，60，73，26，43，95D.28，16，34，54，62，60，73，26，43，95二、判斷題1.通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成樹型結構。（×）2.數(shù)據(jù)結構的基本操作的設置最重要的準則是實現(xiàn)應用程序與存儲結構的獨立。（√）3.數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。（√）4.數(shù)據(jù)結構中,元素之間存在多對多的關系稱為樹狀結構。（×）5.只有用面向對象的計算機語言才能描述數(shù)據(jù)結構算法。（×）6.算法可以用不同的語言描述,如果用C語言或PASCAL語言等高級語言來描述,則算法實際上就是程序了。（×）7.數(shù)據(jù)元素可以由一個或多個數(shù)據(jù)項組成。（√）8.數(shù)據(jù)元素之間的抽象關系稱為物理結構。（×）9.數(shù)據(jù)的物理結構是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。（√）10.健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。（√）11.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（×）12.通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結構抽象成線性結構。（×）13.數(shù)據(jù)元素是對數(shù)據(jù)操作的基本單位。（√）14.類C語言是對C語言的簡化和擴展，強化了C語言的表達能力。（√）15.數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構。（×）16.順序表屬于邏輯結構。（×）17.算法和程序都應具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（×）18.順序存儲方式的優(yōu)點是存儲密度大,且插入、刪除運算效率高。（×）19.數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。（×）20.數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素構成的集合。（√）21.線性表是一個有限序列，不可以為空。（×）22.線性結構采取鏈式存儲時，其元素地址一定是連續(xù)的。（×）23.求線性表各元素的平均值是線性表的基本運算之一。（×）24.向一個長度為n的順序表中的第i個元素（1≤i≤n）之前插入一個元素時，需向后移動n-i個元素。（×）25.若頻繁地對一個線性表進行插入和刪除操作，則使用順序表比較好。（×）26.用順序結構存儲的線性表稱為順序表。（√）27.長度為0的線性表稱為空表。（√）28.對于一個線性表，既要求能夠較快地進行插入和刪除，又要求存儲結構能夠反映數(shù)據(jù)元素之間的邏輯關系，則應采用鏈式存儲方式。（√）29.在線性表的順序存儲中，元素之間的邏輯關系是通過物理存儲位置決定的；在線性表的鏈式存儲中，元素之間的邏輯關系是通過鏈域的指針值決定的。（√）30.一個新結點插入鏈表中只需要修改一個指針域即可，而不需要移動數(shù)據(jù)元素。（×）31.在單鏈表中，要刪除某一指定的結點，必須找到該結點的直接前驅結點。（√）32.設有一個不帶頭結點的單向循環(huán)鏈表，結點的指針域為next，指針p指向尾結點，現(xiàn)要使p指向第一個結點，可用語句p=p->next;。（√）33.要在一個帶頭結點的單向循環(huán)鏈表中刪除頭結點，得到一個新的不帶頭結點的單向循環(huán)鏈表，若結點的指針域為next，頭指針為head，尾指針為p，則可執(zhí)行head=head->next;p->next=head；。（√）34.如果不知道單向鏈表的頭指針，就無法訪問該鏈表的任意結點。（√）35.各種鏈表只需定義有兩個域的結點。（×）36.在雙向循環(huán)鏈表上，刪除最后一個結點，其算法的時間復雜度為0(1)。（√）37.設有一個單向循環(huán)鏈表，結點的指針域為next，頭指針為head，指針p指向表中某結點，若邏輯表達式p->next==head;的結果為真，則p所指結點為尾結點。（√）38.訪問單鏈表中的結點，必須沿著指針鏈依次進行。（√）39.要在一個單向鏈表中p所指向的結點之后插入一個s所指向的新結點，若鏈表中結點的指針域為next，可執(zhí)行p->next=s;s->next=p->next；的操作。（×）40.要在一個單向鏈表中刪除p所指向的結點，已知q指向p所指結點的直接前驅結點，若鏈表中結點的指針域為next，則可執(zhí)行q->next=p->next。（√）41.采用鏈式存儲的線性表稱作鏈表。（√）42.設有一個單向鏈表，結點的指針域為next，頭指針為head，p指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。（√）43.鏈式棧與順序棧相比，一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。（√）44.遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。（×）45.進棧運算是棧的基本運算之一。（√）46.若讓元素a,b,c依次進棧，則出棧次序c,a,b是不可能出現(xiàn)的情況。（√）47.遞歸算法可讀性差，但是效率高（×）48.往棧中插入元素的操作方式是：先寫入元素，后移動棧頂指針。（×）49.棧是限定在表的一端進行插入和刪除操作的線性表，又稱為先進后出表。（√）50.棧是限定在表的兩端進行插入和刪除操作的線性表，又稱為先進先出表。（×）51.不考慮棧空，順序棧刪除元素操作是，先讀出元素，再移動棧頂指針（√）52.順序棧永遠不會出現(xiàn)棧滿的狀態(tài)（×）53.鏈棧永遠不會出現(xiàn)?？盏臓顟B(tài)（×）54.遞歸定義的數(shù)據(jù)結構通常用遞歸算法來實現(xiàn)對它的操作。（√）55.用數(shù)組實現(xiàn)順序棧，棧底可以是數(shù)組空間的任何一端（√）56.鏈棧通常不會出現(xiàn)棧滿的狀態(tài)（√）57.隊列的特性是先進后出。（×）58.雙向循環(huán)鏈表構建的隊列，可以只設立隊首指針，也可以只設隊尾指針（√）59.在隊列的順序存儲結構中，當插入一個新的隊列元素時，尾指針后移，當刪除一個元素隊列時，頭指針后移。（√）60.將新元素插入到隊列任意位置是隊列的基本運算之一。（×）61.隊列允許刪除的一端稱為隊尾，允許插入的一端稱為隊頭。（×）62.順序隊列的入隊算法是先檢查隊列是否為滿，若不滿則將新元素值賦給隊頭指針所指向的數(shù)據(jù)單元，再將隊頭指針加1。（×）63.在一個順序存儲的循環(huán)隊列中,隊頭指針指向隊頭元素的后一個位置。（×）64.串中的元素只可能是字母。（×）65.字符串屬于線性的數(shù)據(jù)結構（√）66.串函數(shù)StrCmp（“ABCd”，“ABCD”）的值為-1。（×）67.長度為0字符串稱為空白串。（×）68.兩個字符串比較時，較長的串比較短的串大（×）69.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。（√）70.串即可以采用順序存儲，也可以采用鏈式存儲（√）71.一個空格的串的長度是0。（×）72.空串的長度是1。（×）73.一個廣義表的表尾總是一個表。（√）74.一個廣義表的表頭總是一個廣義表。（×）75.數(shù)組通常具有的操作是順序存取。（×）76.廣義表的表頭總是一個廣義表。（×）77.遞歸算法執(zhí)行時，每次遞歸可將原問題的規(guī)?？s小。（√）78.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行號、列號和元素值三項信息。（√）79.廣義表A（（a,b,c）,(d,e,f)）的表尾為（(d,e,f)）。（√）80.一個廣義表((a),((b),c),(((d))))的長度為3，深度為4。（√）81.設廣義表L=（（），（）），則其表頭是（（））。（×）82.樹是一種重要的非線性數(shù)據(jù)結構。（√）83.對完全二叉樹按從上到下、從左到右的順序依次編號1,2,...,n，則有當2i≤n時，結點i的左孩子編號為2i，否則無左孩子。（√）84.在二叉樹的鏈接存儲中，每個結點設置三個域：值域、左指針域和右指針域。（√）85.對于一棵深度為h，度為3的樹最多有（3h-1）/2個結點。（×）86.一棵完全二叉樹深度為5，最少有16個結點。（√）87.完全二叉樹中沒有度為1的結點。（×）88.若樹的度為2時，該數(shù)為二叉樹。（×）89.二叉樹的存儲結構有兩種，分別為順序存儲和鏈式存儲。（√）90.森林是m（m≥0）棵互不相交的樹的集合。（√）91.樹的所有結點有且只有一個前驅結點。（×）92.樹中全部結點的度均大于0。（×）93.深度為5的二叉樹最多有3層。（×）94.父親李貴有兩個兒子李萬勝和李萬利，李萬勝又有三個兒子李建新、李建中和李建國，這個家庭可以用樹結構來描述。（√）95.如果結點A有3個兄弟3個孩子，而且B是A的雙親，則A的度是3。（×）96.具有12個結點的完全二叉樹的深度為4。（√）97.一棵二叉樹每一層的結點數(shù)都達到最大值，則這個二叉樹是完全二叉樹。（×）98.完全二叉樹和滿二叉樹比較合適采用順序存儲。（√）99.具有32個葉子結點的滿二叉樹共有63個結點。（√）100.二叉樹只能采用二叉鏈表來存儲。（×）101.如果結點A有3個兄弟，而且B是A的雙親，則B的度是4。（√）102.對于一棵深度為4的滿三叉樹，其結點數(shù)為40。（√）103.哈夫曼樹只存在著雙支結點，不存在單支結點。（√）104.如果一個葉子結點是某二叉樹中序遍歷序列的最后一個結點，那么它也是該二叉樹的先序遍歷序列的最后一個結點。（√）105.哈夫曼樹一定是完全二叉樹或滿二叉樹。（×）106.二叉樹的遍歷就是按照一定次序訪問樹中所有結點，并且每個結點的值僅被訪問一次的過程。（√）107.已知一棵樹的先序序列和后序序列，一定能構造出該樹。（×）108.圖的連通分量是無向圖的極大連通子圖。（√）109.在一個具有n個頂點和e條邊的無向圖的鄰接表中，邊結點的個數(shù)為e。（×）110.由一個具有n個頂點的連通圖生成的最小生成樹中，具有n-1條邊。（√）111.強連通分量是有向圖的極大連通子圖。（√）112.有向圖用鄰接矩陣表示后，頂點i的出度等于第i行中非0且非無窮的元素個數(shù)。（√）113.對于一個無向圖，每個頂點的入度等于出度。（√）114.對任意一個圖從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點。（×）115.一個有向圖的鄰接表和逆鄰接表中的節(jié)點個數(shù)一定相等。（√）116.有n個結點的無向圖中，若邊數(shù)大于n-1，則該圖是連通的。（√）117.無向圖的鄰接矩陣一定是對稱的。（√）118.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（√）119.在一個連通圖中存在著1個連通分量。（√）120.鄰接表只能用于存儲有向圖，而鄰接矩陣則可存儲有向圖和無向圖。（×）121.有向圖的鄰接矩陣一定是非對稱的。（×）122.圖的廣度優(yōu)先搜索序列是惟一的。（×）123.采用鄰接表存儲的圖的廣度優(yōu)先遍歷方法類似于二叉樹的按層次遍歷方法。（√）124.圖的最小生成樹只有一棵。（×）125.根據(jù)圖的存儲結構進行某種次序的遍歷，得到的頂點序列是唯一的。（×）126.使用鄰接矩陣存儲圖的時候，占用空間大小與圖的結點個數(shù)沒有關系。（×）127.用鄰接矩陣存儲圖的時候，占用空間大小不但與圖的結點個數(shù)有關還與圖的邊數(shù)有關。（×）128.假設在有序線性表A[1..20]上進行折半查找，則比較五次查找成功的結點數(shù)為5。（√）129.在一個查找表中，能夠唯一地確定一個記錄的關鍵字稱為主關鍵字。（√）130.折半查找只適用于順序存儲結構的有序表。（√）131.采用順序查找法對長度為n（n為偶數(shù)）的線性表進行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個元素的平均查找長度為(n+2)/4。（√）132.在順序查找、折半查找、哈希表查找3種方法中，平均查找長度與結點個數(shù)n無關的查找方法是折半查找。（×）133.二叉排序樹的建立過程實際上是從空樹逐次插入的過程。（√）134.二叉排序樹中某一結點的左兒子一定小于樹中任一個結點的右兒子。（×）135.根據(jù)無序序列構造二叉排序樹的過程，也是對無序序列排序的過程。（√）136.使用折半查找算法的前提條件是，查找表中記錄相應的關鍵字值必須按升序或降序排列。（√）137.二叉樹為二叉排序樹的充分必要條件是，任一個分支結點的值都大于其左孩子的值，小于右孩子的值。（×）138.在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是哈希表查找。（√）139.理想情況下，哈希表查找等概率查找成功的時間復雜度是O(1)。（√）140.采用分塊查找時，數(shù)據(jù)的組織方式是把數(shù)據(jù)分成若干塊，塊內(nèi)數(shù)據(jù)不必有序，但塊間必需有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引表。（√）141.折半查找的前提條件是，查找表中記錄相應的關鍵字值必須有序或者部分有序。（×）142.折半查找方法運用在升序序列比降序序列效率更高，所以降序序列最好先轉換為升序序列。（×）143.一個好的哈希函數(shù)，應該使哈希地址均勻地分布在整個哈希表的地址區(qū)間中，完全避免沖突的發(fā)生。（×）144.二叉排序樹中任一棵子樹都是二叉排序樹。（√）145.分塊查找是一種介于順序查找和折半查找之間的查找方法。（√）146.按{18，42，10，86，52，20}的順序構成的二叉排序樹，其根結點為18。（√）147.線性表用關鍵字的順序方式存儲，可以用二分法排序。（×）148.對二叉排序樹進行后序遍歷，可以使遍歷所得到的序列是有序序列。（×）149.二叉排序樹在呈單支二叉樹時，查找效率最低。（√）150.采用分塊查找時，若線性表中共有324個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊，每塊應分12個結點最佳。（×）151.按照一定規(guī)則，在二叉排序樹上插入、刪除結點，仍能保持二叉排序樹的性質。（√）152.分塊查找分為兩個步驟：第一步是要對索引表進行查找；第二步是在塊中查找。這兩步查找都可以采用折半查找或者順序查找方法。（×）153.序列3,1,7,18,6,9,13,12經(jīng)一趟歸并排序的結果為1,3,7,18,6,9,13,12。（×）154.在歸并排序中，在第3趟歸并中，是把長度為4的有序表歸并為長度為8的有序表。（√）155.對記錄序列排序是指按記錄的某個關鍵字排序，記錄序列按主關鍵字排序結果是唯一的。（√）156.對16個元素的序列用冒泡排法進行排序，最多需要進行15趟冒泡。（√）157.待排序的序列為8,3,4,1,2,5,9，采用直接選擇排序算法，當進行了兩趟選擇后，結果序列為1,2,8,3,4,5,9。（×）158.在對一組記錄（50，40，95，20，15，70，60，45，80）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需要比較2次。（×）159.冒泡排序是一種比較簡單的交換排序方法。（√）160.8個元素進行冒泡法排序，至多需要進行7趟冒泡,其中第5趟冒泡共需要進行3次元素間的比較。（√）161.在堆排序和快速排序中，若原始記錄接近正序和反序，則最好選用快速排序。（×）162.簡單插入排序是不穩(wěn)定的排序算法。（×）163.序列15,13,16,14,19,17，采用冒泡排序算法(升序)，經(jīng)一趟冒泡后，結果序列是13,15,14,16,17,19。（√）三、綜合題1.設SeqStack為順序棧，寫出下列程序段執(zhí)行后的結果。

SeqStackS;

InitStack(S);

Push(S,3);

Push(S,4);

Push(S,5);

intx=Pop(S)+2*Pop(S);

Push(S,x);

inti,a[4]={5,8,12,15};

for(i=0;i<4;i++)Push(S,a[i]);

while(!StackEmpty(S))Printf(“%d”,Pop(S));A.151285133B.358121315C.151312853D.1512133852.設有一個不帶頭結點的單向鏈表，頭指針為head，p、prep是指向結點類型的指針，該鏈表在輸入信息時不慎把相鄰兩個結點的信息重復輸入，以下程序段是在該單向鏈表中查找這相鄰兩個結點，把該結點的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程序中的空格。

prep=head;

p=prep->next;

while(p->data!=prep->data)

{prep=p;

____①____;

}

printf(“%d”,p->data);

prep->next=____②____;A.①p=p->next②p->nextB.①prep->data②p->nextC.①p->next②p=p->nextD.①p->next②p->data3.設有一個頭指針為head的單向鏈表中（結點類型為NODE），p為指向該鏈表中某個結點的指針。以下程序段為插入一個指針為s的結點，使它成為p結點的直接前驅，請選擇其中空格的選項。

NODE*q;

q=head;

while(q->next!=p)

________;

s->next=p;

q->next=s;A.p=p->nextB.q=q->nextC.s=s->nextD.head=head->next4.設有一個頭指針為head的不帶頭結點單向鏈表中（結點類型為NODE），p為指向該鏈表中某個結點的指針。以下程序段為插入一個指針為s的結點，使它成為p結點的直接前驅，請把合適選項填寫到空行處。

NODE*q;

q=head;

while(q->next!=p)

q=q->next;

s->next=p;

________;A.p->next=qB.p->next=sC.q->next=sD.q->next=p5.設線性表以不帶頭結點的單向鏈表存儲，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結點中的數(shù)據(jù)域data，完成程序中空格部分。

#defineNULL0

voidmain()

{NODE*head,*p;

p=head;/*p為工作指針*/

do

{printf(“%d\n”,p->data);

p=p->next;

}while(________);

}A.p==NULLB.p!=NULLC.p!=headD.p==head6.假設隊列順序存儲結構為：

structSeqQueue{

ElemTypedata[MaxSize];

intfront,rear;

};

structSeqQueue*sq;

請補充下面出隊算法（不考慮空間循環(huán)使用）。

voidOutQueue(structSeqQueue*sq,ElemtTypex){

if(1){

printf(“隊列已空，不能出隊\n”);

exit(1);

}

2

returnsq->data[sq->front-1];

}

其中，1和2處應該補充的代碼是（）A.sq->front==sq->rear,sq->front++B.sq->rear==sq->front,sq->rear++;C.sq->front=sq->rear,sq->front++D.sq->rear=sq->front,sq->rear++;7.以下程序段執(zhí)行后，c的值為（）。

char*a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}

inti,c=0

for(i=0;i<5;i++)

if(strcmp(a[i],”1237”)==0)c++;A.2B.5C.0D.12378.假設鏈表結點存儲結構為：

structnode{

intdata;

structnode*next;

};

structnode*front,*next;

InitQueue()、InQueue()、OutQueue()、QueueEmpty()分別是鏈隊的初始化、入隊、出隊、判空操作。

下面程序執(zhí)行后，運行結果是（）。

inti;

InitQueue();

for(i=0;i<6;i++)InQueue(i++);

while(!QueueEmpty())

printf(“%d”,OutQueue());

printf(“\n”);A.012345B.123456C.01491625D.以上答案均不對9.在下面空格處填寫一條語句，以使下面的順序隊列入隊算法完整。

voidInQueue(structSeqQueue*sq,intx)

{if(sq->rear==MaxSize)

{printf(“隊列已滿！\n”);

exit(1);

}

______________

sq->rear++;

}A.x=sq->data[sq->rear];B.x=sq->rear[sq->data];C.sq->rear[sq->data]=x;D.sq->data[sq->rear]=x;10.假設隊列順序存儲結構為：

structSeqQueue{

ElemTypedata[MaxSize];

intfront,rear;

};

structSeqQueue*sq;

請補充下面入隊算法（不考慮空間循環(huán)使用）。

voidInQueue(structSeqQueue*sq,ElemtTypex){

if(1){

printf(“隊列已滿\n”);

exit(1);

}

sq->data[sq->rear]=x;

2

}

其中，1和2處應該補充的代碼是（）A.sq->front==Maxsize,sq->rear++;B.sq->rear==Maxsize,sq->rear++;C.sq->front==Maxsize,sq->front++;D.sq->rear==Maxsize,sq->front++;11.寫出下列程序段執(zhí)行后的結果

SeqQueueQ;

InitQueue(Q);

inti,a[4]={5,8,12,15};

for(i=0;i<4;i++)InQueue(Q,a[i]);

InQueue(Q,OutQueue(Q));

InQueue(Q,30);

InQueue(Q,OutQueue(Q)+10);

while(!QueueEmpty(Q))printf(“%d”,OutQueue(Q));A.58121530B.121553018C.812153018D.12155183012.在下面空格處填寫一條語句，以使下面的循環(huán)隊列出隊算法完整。

ElemTypeOutQueue(structSeqQueue*sq)

{if(sq->rear==sq->front)

{printf(“隊列已空，不能進行出隊操作！\n”);

exit(1);

}

________

sq->front=(sq->front+1)%MaxSize;

returnx;

}A.x=sq->data[sq->front-1];B.x=sq->data[sq->front+1];C.x=sq->data[sq->front];D.x=sq->data[sq->rear];13.在下面空格處填寫一條語句，以使下面的串比較算法完整。

intstrcmp(char*s1,char*s2)

{inti;

for(i=0;s1[i]!=’\0’&&s2[i]!=’\0’;i++)

if(s1[i]>s2[i])

return1;

else

if(s1[i]<s2[i])

return-1;

if(s1[i]==’\0’&&s2[i]==’\0’)

_________

else

if(s1[i]!=’\0’)

return1;

else

return-1;

}A.return0;B.return-1;C.return1;D.returni;14.以下程序段的結果是：c的值為（）

chara[]=”abcdefgjh”；

int*p=a,c=0;

While(*p++)c++;A.8B.9C.10D.1115.設查找表為：

用折半查找在該查找表成功查找到元素55需要經(jīng)過（）次比較。A.1B.2C.3D.416.設查找表為(16,15,20,53,64,7)，用冒泡法對該表進行排序，在排序后的有序表的基礎上進行折半查找，在等概率條件下,成功查找的平均查找長度為（）。A.3.5B.3C.19/6D.14/617.設查找表為(1,10,11,14,23,27,29,55,68)，對上述查找表進行折半查找，為了成功查找到元素14,需要依次與元素（）進行比較。A.23,10,1,14B.23,29,27,14C.23,10,11,14D.23,29,55,1418.設有數(shù)據(jù)集合{50，39，17，83，91，14，65}，此二叉排序樹的（）遍歷是有序序列。A.先序B.中序C.后序D.按層19.設有查找表為(5,14,2,6,18,7,4,16,3),依次取表中數(shù)據(jù)，構造一棵二叉排序樹，對該二叉樹進行后序遍歷的結果序列為（）。A.3,4,2,7,6,16,18,14,5B.2,3,4,5,6,7,14,16,18C.5,2,14,4,6,18,3,7,16D.5,2,4,3,14,6,7,18,1620.以下為求二叉樹深度的算法，完成程序中空格部分。

intBTreeDepth(BTreeNode*BT)

{if(BT==NULL)

return0;

else

{intdep1=BTreeDepth(BT->left);/*計算左子樹的深度*/

intdep2=BTreeDepth(BT->right);/*計算右子樹的深度*/

if(________)

returndep1+1;

else

returndep2+!;

}

}A.dep1>dep2B.dep1<dep2C.BT->left==NULLD.BT->right==NULL21.以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結點）。

voidPreorder(structBTreeNode*BT)

{if(BT!=NULL)

{_________________;

Preorder(BT-->left);

Preorder(BT-->right);

}

}A.printf(“%c”,BT->left)B.printf(“%c”,BT->right)C.printf(“%c”,BT->data)D.printf(“%d”,BT->data)22.設數(shù)據(jù)序列為：{53,30,37,12,45,24,96}，從空二叉樹開始逐個插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應該選擇的序列是（）。A.45,24,53,12,37,96,30B.37,24,12,30,53,45,96C.12,24,30,37,45,53,96D.30,24,12,37,45,96,5323.設一組記錄的關鍵字序列為（49，83，59，41，43，47），采用堆排序算法建立初始小根堆，在該小根堆上逐次取走堆頂元素后，經(jīng)調(diào)整得到的4個元素的堆為（）。A.47，49，59，83B.47，59，49，83C.47，83，49，59D.49，59，47，8324.以下是直接插入排序算法對存放在a[0],a[1],……,a[n-1]中，長度為n的記錄序列按關鍵字key由小到大排序，完成程序中空格部分。

voiddisort(NODEa[],intn)

{inti,j;

NODEtemp;

for(i=1;i<n;i++)

{temp=a[i];

j=i-1;

while(j>=0&&temp.key<a[j].key)

{a[j+1]=a[j];

_______;

}

a[j+1]=temp;

}

}A.j++B.i++C.j—D.i--25.一組記錄的關鍵字序列為（36，69，46，28，30，84），對該序列進行直接選擇排序（每次選擇最小關鍵字），第二趟排序后的結果序列為（）。A.28，69，46，36，30，84B.28，30，46，36，69，84C.36，46，69，28，30，84D.28，30，36，69，46，8426.設關鍵字序列為：（36，69，46，28，30，74），將此序列用快速排序的方法，以第一個記錄