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

1、第一章：時(shí)間復(fù)雜度：例如：1.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其中（）數(shù)據(jù)項(xiàng)A.只能包含一個(gè)B.不包括C.可以包含多個(gè)D.可以包括也可以不包括2.邏輯關(guān)系是指數(shù)據(jù)元素的（）A.關(guān)系 B.存儲(chǔ)方式 C.結(jié)構(gòu) D.數(shù)據(jù)項(xiàng)3.算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（）A.正確性 B.易讀性C.高效性 D.健壯性4.數(shù)據(jù)的基本單位是_5.一個(gè)算法應(yīng)具備_、_、_、_、_5個(gè)特性6.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_(kāi)、_、_、_四種。7.計(jì)算下列算法的時(shí)間復(fù)雜度x = 1;for(i = 1,i <= n;i+)for(j = 1;j <= n/2;j+)for(k = 1;k <= n;k+)x+

2、; 第二章帶頭結(jié)點(diǎn)的單鏈表，其頭指針為L(zhǎng)，則它為空表的條件是？ 在一個(gè)單鏈表中的p所指的結(jié)點(diǎn)之前插入一個(gè)s所指向的結(jié)點(diǎn)，操作如下：s->next = _;p->next = s;t=p->data;p->data=_;s->data=_; 在一個(gè)雙鏈表中，在p所指向的結(jié)點(diǎn)之后插入q所指向的結(jié)點(diǎn)的操作是？ 在一個(gè)雙鏈表中，在*p結(jié)點(diǎn)之前插入*q結(jié)點(diǎn)的操作是？ 在雙鏈表中，刪除*p結(jié)點(diǎn)的操作是？ 在雙鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是？(不釋放空間) 若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或者刪除最后一個(gè)結(jié)點(diǎn)，在采用_存儲(chǔ)方式最節(jié)省時(shí)間。A單鏈表

3、B給出表頭指針的循環(huán)單鏈表C雙鏈表 D帶頭結(jié)點(diǎn)的循環(huán)雙鏈表 某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除第一個(gè)結(jié)點(diǎn)，則采用_存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A單鏈表 B僅有頭結(jié)點(diǎn)的單循環(huán)鏈表C雙鏈表 D僅有尾結(jié)點(diǎn)指針的單循環(huán)鏈表 線性表是具有n個(gè)（）的有限序列A.表元素 B.字符C.數(shù)據(jù)元素 D.數(shù)據(jù)項(xiàng) 線性表采用鏈表存儲(chǔ)時(shí)，其地址（）A.必須是連續(xù)的 B.一定是不連續(xù)的C.部分地址必須是連續(xù)的 D.連續(xù)與否均可以 線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)_決定的，而在鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)_決定的。 向一個(gè)長(zhǎng)度為n的順序表中的第i個(gè)元素（1<=i<=n）之

4、前插入一個(gè)元素，需向后移動(dòng)_個(gè)元素。 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素時(shí)，需要向前移動(dòng)_個(gè)元素。 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素（0<=i<=n-1）時(shí)，需向前移動(dòng)_個(gè)元素。 線性表中所有元素的排列順序必須是由小到大或者由大到?。?帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的判定條件是（）A.L= =NULL B.L->next =NULLC.L->next=L D.L!=NULL 在一個(gè)長(zhǎng)度為n（n>1）的帶頭結(jié)點(diǎn)的單鏈表h上，另設(shè)有尾指針r（指向最后一個(gè)結(jié)點(diǎn)），執(zhí)行（ ）操作時(shí)其復(fù)雜度與鏈表的長(zhǎng)度有關(guān)。A.刪除單鏈表的第一個(gè)元素B.刪除單鏈表的最后一個(gè)元素C.在單

5、鏈表第一個(gè)元素前插入一個(gè)新元素D.在單鏈表最后一個(gè)元素后插入一個(gè)新元素 在單鏈表中，要?jiǎng)h除某一個(gè)指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的_結(jié)點(diǎn)。 在一個(gè)單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是_ 在一個(gè)單鏈表（已知每個(gè)結(jié)點(diǎn)含有數(shù)據(jù)域data和指針域next）中刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行如下操作：(1)q=p->next;(2)p->next =_;(3)free(q); 線性表是具有n個(gè)_的有限序列。 線性表采用鏈表存儲(chǔ)時(shí) ，其元素地址（）A.必須連續(xù)B.一定不連續(xù)C.部分必須連續(xù)D.連續(xù)與否都可以 先行表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼？（） 帶頭結(jié)點(diǎn)的單鏈表head為空的條件是

6、_。 鏈表不具備的特點(diǎn)是（） 可隨機(jī)訪問(wèn)任意結(jié)點(diǎn) 插入刪除不需要移動(dòng)元素 不必事先估計(jì)存儲(chǔ)空間 所需空間與其長(zhǎng)度成正比 設(shè)線性表有2n個(gè)元素，（）在單鏈表上實(shí)現(xiàn)要比順序表實(shí)現(xiàn)效率高？A.刪除指定元素B.在最后一個(gè)元素后面插入一個(gè)新元素C.順序輸出前k個(gè)元素D.交換第i個(gè)元素和第2n-i-1個(gè)元素的值刪除順序表的_元素，需要移動(dòng)的元素最多。算法設(shè)計(jì) 已知有某帶頭結(jié)點(diǎn)的單鏈表，其頭指針為head，現(xiàn)在需要尋找表中的元素20，并在其后添加一個(gè)元素30，請(qǐng)編寫(xiě)能執(zhí)行添加的函數(shù)，函數(shù)的原型如下：NODE* insert(NODE * head ,int x,int y) 其中x 是要尋找的元素,y是要添

7、加的元素，結(jié)構(gòu)體的定義就借鑒以前的內(nèi)容。第三章請(qǐng)編寫(xiě)程序，讓四個(gè)字符ABCD按照DCBA的順序入棧，但是出棧順序是CDAB，應(yīng)如何安排他們進(jìn)棧和出棧 棧是操作受限制的線性表，插入操作和刪除操作都必須在表的_進(jìn)行。 它的元素在棧中的進(jìn)出遵循_原則。 棧中沒(méi)有元素，稱為_(kāi)，如果元素個(gè)數(shù)達(dá)到了順序棧所能容納的最大值，稱為_(kāi)。 棧中總是設(shè)置一個(gè)表示棧頂元素下標(biāo)的變量，叫做_。 有一個(gè)棧，元素A，B，C，D只能依次進(jìn)棧，則出棧序列中以下哪個(gè)是不可能得到的（）A. D、C、B、A B. C、B、A、DC. A、B、C、D D. D、C、A、B 有一單向鐵路行駛道，（1）如果進(jìn)站的車廂序列為123，則可能得

8、到的出站車廂的序列有哪些可能性。（2）如果進(jìn)站的車廂序列為123456，則能否得到435612和135426的序列，說(shuō)明為什么不能得到或者如何得到。 設(shè)n個(gè)元素進(jìn)棧序列是1,2,3.,n，輸出序列是p1,p2,.pn,若p1=3,則p2的值（）A.一定是2 B.一定是1C.不可能是1 D.以上都不對(duì) 有5個(gè)元素，它們的進(jìn)棧順序是A,B,C,D,E,在可能的出棧順序中，以元素CD最先出棧的次序有哪幾個(gè)？ 判定一個(gè)順序棧st為空的條件是（）A.st.top=0; B.st.top!=0;C.st.top!=MAX;D.st.top=MAX; 判定一個(gè)順序棧st為棧滿的條件是（）；A.st.top=

9、0; B.st.top!=0;C.st.top!=MAX-1;D.st.top=MAX-1; 將f=1+1/2+1/3+.+1/n轉(zhuǎn)化成遞歸函數(shù)，其遞歸出口（終結(jié)條件）是_遞歸公式是_。 隊(duì)列也是操作受到限制的線性表，它只能在表的_插入，這一端稱為_(kāi)在表的_刪除,這一端稱為_(kāi)。 隊(duì)列中元素在表中的進(jìn)出遵循_的原則。 順序隊(duì)列在多次出隊(duì)和入隊(duì)操作之后，會(huì)出現(xiàn)一種元素并沒(méi)有裝滿，卻無(wú)法再次入隊(duì)的情況，我們稱為_(kāi)現(xiàn)象。 在隊(duì)列中我們常常設(shè)置一個(gè)指針front，指向_的位置，我們稱為隊(duì)首指針，又設(shè)置一個(gè)指針rear,志向_的位置，我們稱為_(kāi)。 循環(huán)隊(duì)列qu，已滿的條件是（）A.（qu.rear+1）%

10、MAX=(qu.front+1)%MAXB. （qu.rear+1）%MAX=qu.front+1C.（qu.rear+1）%MAX=qu.frontD.qu.rear=qu.front 循環(huán)隊(duì)列qu，已空的條件是（）A.（qu.rear+1）%MAX=(qu.front+1)%MAXB. （qu.rear+1）%MAX=qu.front+1C.（qu.rear+1）%MAX=qu.frontD.qu.rear=qu.front 某循環(huán)隊(duì)列中數(shù)組下標(biāo)是0n-1，其頭指針front和rear值分別為f和r，則元素的個(gè)數(shù)為_(kāi)。 帶頭結(jié)點(diǎn)的鏈隊(duì)qu，對(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)

11、空的條件是（）A.qu.front=qu.rearB.qu.front!=NULLC.qu.rear!=NULLD.qu.front=NULL 某鏈隊(duì)qu,目前只有一個(gè)元素，要將此元素刪除，應(yīng)當(dāng)怎么做。p=qu->front->next;qu->front->next =_;_ = qu->front;free(p);5.在棧中允許插入和刪除的一端稱為_(kāi)，另一端稱為_(kāi)。棧的插入操作通常稱為_(kāi)，而刪除操作則稱為_(kāi)。棧中無(wú)元素時(shí)稱為_(kāi)。6.已知一個(gè)棧的進(jìn)棧序列是1234n，其輸出序列的第一個(gè)元素是i，則第j個(gè)出棧元素是（i-j+1）。A.I B.n-IC.j-i+1

12、D.不確定7.設(shè)n個(gè)元素進(jìn)棧序列是123.n，其輸出序列是p1p2,.pn,則p33，則p2的值（）。A. 一定是2 B.一定是1C.不可能是2 D.不可能是36.順序棧中元素值的大小是有序的？7.N個(gè)元素進(jìn)棧后，他們的出棧順序一定和進(jìn)棧順序正好相反。8.棧頂元素和棧底元素可能是同一個(gè)元素。9.判定一個(gè)順序棧st為空的條件是（）；A.st.top=0; B.st.top!=0;C.st.top!=MAX;D.st.top=MAX;10.判定一個(gè)順序棧st為棧滿的條件是（）；A.st.top=0; B.st.top!=0;C.st.top!=MAX-1;D.st.top=MAX-1;C.f(0)

13、=1 D.f(n)=n第四章第五章有如下矩陣，則用三元組法表示應(yīng)該如何表示？第六章有某樹(shù)中序序列為DGBAECF 后序序列為GDBEFCA，請(qǐng)構(gòu)造出此二叉樹(shù)。 給定某樹(shù)的中序遍歷序列為BDCAEHGKF，后序遍歷為：DCBHKGFEA，請(qǐng)畫(huà)出樹(shù)的形態(tài)圖。 某通信系統(tǒng)中可能出現(xiàn)8個(gè)字符a,b,c,d,e,f,g,h，出現(xiàn)的頻度分別為(5,29,7,8,14,23,3,11)，為此8個(gè)字符設(shè)計(jì)哈夫曼編碼。 按照樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（）種 A.3B.4 C.5D.6 一個(gè)滿二叉樹(shù)，有n個(gè)結(jié)點(diǎn)和m個(gè)葉子,深度為h，則 A.n=h+mB.h+m=2n C.m=h-1D.n=2h-1 在一棵完

14、全二叉樹(shù)中，結(jié)點(diǎn)數(shù)目為n，從1開(kāi)始從上到下，從左到右編號(hào)，編號(hào)最大的分支結(jié)點(diǎn)編號(hào)是_。 二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則二叉樹(shù)的總結(jié)點(diǎn)數(shù)目至少有多少個(gè)？ 在一非空二叉樹(shù)的中序編列序列中，根結(jié)點(diǎn)的左邊（） A.只有右子樹(shù)上的所有結(jié)點(diǎn) B.只有右子樹(shù)上的部分結(jié)點(diǎn) C.只有左子樹(shù)上的所有結(jié)點(diǎn) D.只有左子樹(shù)上的部分結(jié)點(diǎn) 任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在三種遍歷序列中的相對(duì)次序（） A.不發(fā)生改變B.發(fā)生改變 C.不能確定D.以上都不對(duì) 一棵二叉樹(shù)的先序遍歷序列為ABCDEFG，它的中序序列可能是（） A.CABDEFGB.ABCDEFG C.DACEFBGD.ADCFEGB 一棵二叉樹(shù)的先序序列是ABCDEF，中序?yàn)镃BAEDF，則后序?yàn)椋ǎ?A.CBEFDAB.FEDCBA C.CBEDFAD.不確定 二叉樹(shù)先序序列和中序序列相同的條件是_。 n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)目為 A.2nB.n-1 C.n+1D.n 線索二叉樹(shù)中左線索指向_，右線索指向_. 引入線索二叉樹(shù)的目的是（） A.加快查找結(jié)點(diǎn)前驅(qū)和后繼的速度 B.為了能在樹(shù)中方