注：不含主觀題第0章課程簡介第1章緒論第2章線性表第3章棧和隊列第4章數(shù)組第5章樹和二叉樹第6章圖第7章查找第8章排序第1題判斷題(1分)既然高級語言通常都內建了數(shù)據(jù)結構語法和API，學習數(shù)據(jù)結構就沒有必要了。第2題判斷題(1分)在開發(fā)實際項目時，應優(yōu)先考慮自己來實現(xiàn)常見的數(shù)據(jù)結構。第3題判斷題(1分)實現(xiàn)某種數(shù)據(jù)結構時，通常對使用的編程語言沒有限定。作業(yè)第1題單選題(1分)用計算機求解的問題可以分為（）？A簡單型問題、復雜型問題B文本型問題、二進制型問題C數(shù)值型問題、非數(shù)值型問題D基本型問題、結構型問題第2題單選題(1分)用計算機求解問題的一般步驟是什么？A分析問題、設計算法、編程/調試、得到結果B分析問題、建立數(shù)學模型、編程/調試、得到結果C分析問題、設計算法、建立數(shù)學模型、編程/調試、得到結果D分析問題、建立數(shù)學模型、設計算法、編程/調試、得到結果第3題單選題(1分)建模的本質包括（）。A從問題中抽取出關鍵對象B找出問題中關鍵對象之間的關系C以合適的語言(或符號)描述問題中的關鍵對象以及它們之間的關系D以上三者均是第4題單選題(1分)數(shù)據(jù)結構是一門介于（）三者之間的課程。A數(shù)學、程序設計、硬件系統(tǒng)B數(shù)學、操作系統(tǒng)、硬件系統(tǒng)C程序設計、操作系統(tǒng)、硬件系統(tǒng)D程序設計、計算機網(wǎng)絡、硬件系統(tǒng)作業(yè)1第1題單選題(1分)下列哪一個不是邏輯結構？A棧B鏈表C二叉樹D有向圖第2題單選題(1分)下列哪一個不是物理結構？A順序表B鏈表C二叉鏈表D哈希表第3題單選題(1分)Windows中的文件系統(tǒng)是一種（）。A隊列B樹C二叉樹D圖第4題單選題(1分)微信朋友圈的好友關系是一種（）。A樹B線性表C數(shù)組D圖作業(yè)2第1題單選題(1分)參與擊鼓傳花游戲的N個人是一種（）。A樹B線性表C數(shù)組D圖第2題單選題(1分)下列哪一個說法是正確的？A數(shù)據(jù)項是數(shù)據(jù)的基本組成單元B數(shù)據(jù)元素是數(shù)據(jù)的基本組成單元C數(shù)據(jù)項能拆分為更小的單元D結構類型一定由原子類型組合而成第3題單選題(1分)在實際應用中，決定選取何種物理結構時，一般不考慮（）。A數(shù)據(jù)元素要支持的操作B數(shù)據(jù)元素的總個數(shù)C數(shù)據(jù)元素的具體值D所用的編程語言實現(xiàn)該種結構是否方便第4題單選題(1分)京東/淘寶中的商品分類是一種（）。A樹B線性表C數(shù)組D圖作業(yè)第1題單選題(1分)抽象數(shù)據(jù)類型從（）結構的角度來描述（）、（）及（）。A邏輯、元素、關系、操作B邏輯、元素、關系、類型C物理、元素、關系、操作D物理、元素、關系、類型第2題單選題(1分)數(shù)據(jù)類型可分為原子類型和（）。A數(shù)值類型B非數(shù)值類型C數(shù)組類型D結構類型第3題單選題(1分)設某數(shù)據(jù)結構DS=(D,R)，D={1,2,3,4,5,6,7,8,9}，R={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>,<3,7>}，則DS是（）。A線性結構B樹型結構C物理結構D圖型結構第4題判斷題(1分)所有的編程語言都支持相同的數(shù)據(jù)類型。第5題判斷題(1分)不同的數(shù)據(jù)類型支持的操作可能不一樣。第6題判斷題(1分)C++的引用參數(shù)是對函數(shù)的實參而言的。作業(yè)第1題單選題(1分)算法必須具備輸入、輸出、（）等5個特性。A可行性、可移植性和可擴展性B確定性、有窮性和穩(wěn)定性C可行性、確定性和有窮性D可讀性、可擴展性和安全性第2題單選題(1分)算法能正確處理其接收的非法或惡意輸入，稱為算法的（）。A健壯性B安全性C可讀性D正確性第3題單選題(1分)下面的程序段違反了算法的（）。123456void

sum()

{

int

n=2;

while

(!odd(n))

n+=2;

printf(n);}A確定性B可行性C健壯性D有窮性作業(yè)1第1題單選題(1分)下列哪一個說法是錯誤的？A空間復雜度為O(1)是指算法只占用一個臨時存儲單元B時間復雜度通常是指最壞情況下的時間復雜度C所用編程語言和輸入數(shù)據(jù)都相同時，2個算法分別在同一臺計算機上運行，花費時間較長的算法可能具有更低的時間復雜度D同一個算法，分別用編譯型語言和解釋型語言編寫為程序，后者運行耗時可能更少第2題單選題(1分)某算法的時間復雜度為O(n^2)，表明該算法的（）。A問題規(guī)模是n^2B問題規(guī)模與n^2成正比C執(zhí)行時間等于n^2D執(zhí)行時間與n^2成正比第3題單選題(1分)分析算法的時間復雜度時，不用關注（）。A輸入的量B輸入的具體狀態(tài)C完成的功能D基本步驟的執(zhí)行總次數(shù)第4題單選題(1分)算法分析的目的是（）。A分析算法所用的數(shù)據(jù)結構是否合理B分析算法完成的功能C分析算法的時空效率以求改進D分析算法的可讀性和可擴展性作業(yè)2第1題單選題(1分)設n為偶數(shù)，下列偽碼中，注釋所在行的總執(zhí)行次數(shù)是（）。12345FOR

i

=

1

TO

n

DO

FOR

j

=

2*i

TO

n

DO

m

=

m

+

1;

//

此行的總執(zhí)行次數(shù)An^2B(n^2)/4C(n^2)/2D不確定第2題單選題(1分)下列程序段的時間復雜度是（）。

12345s=i=0;do

{

i++;

s+=i;}

while(i<=n);AO(n)BO(log2(n))CO(n*log2(n))DO(n^2)第3題單選題(1分)下列程序段的時間復雜度是（）。1234567for(i=0;

i<m;

i++)

for(j=0;

j<t;

j++)

c[i][j]=0;for(i=0;

i<m;

i++)

for(j=0;

j<t;

j++)

for(k=0;

k<n;

k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];AO(m+n+t)BO(m+n*t)CO(m*t+n)DO(m*n*t)作業(yè)第1題單選題(1分)線性表是具有n個（）的有限序列。A整數(shù)B字符C數(shù)據(jù)元素D數(shù)據(jù)項第2題判斷題(1分)線性表中的每個元素都有且僅有一個前驅。第3題判斷題(1分)線性表至少要包含一個元素。作業(yè)1第1題單選題(1分)設線性表長度為n，以下哪個操作在順序表上實現(xiàn)比其在鏈表上的效率更高？A交換第1個元素與第2個元素的值B輸出第i（1<=i<=n）個元素的值C依次輸出n個元素的值D輸出值為x的元素在線性表中的序號第2題單選題(1分)對于順序存儲的線性表，增加、刪除元素的時間復雜度為（）。AO(0)BO(1)CO(n)DO(n^2)第3題單選題(1分)若一維數(shù)組的首個元素是a0，每個元素占d個字節(jié)，則其隨機存取公式是（）?ALoc(ai)=Loc(a0)+(i+1)*dBLoc(ai)=Loc(a0)+i*dCLoc(ai)=Loc(a0)+(i-1)*dDLoc(ai)=Loc(a0)+i第4題單選題(1分)關于下列代碼段，錯誤的說法是（）？12345typedef

struct

{

ElemType

*elem;

int

length;

int

size;}

SqList;A可以把elem當做數(shù)組名來用Bsize是表容量，length是表長Csize一定大于或等于lengthDSqList是一個結構體變量名第5題單選題(1分)在一個長度為N的順序表中第i個元素（1<=i<=N+1）之前插入一個元素，需向后移動（）個元素？AiBN-iCN-i+1DN-i-1作業(yè)2第1題單選題(1分)在一個長度為N的順序表中第i個元素（1<=i<=N+1）之前插入一個元素，然后（前面的插入操作完成后）再刪除第i個（1<=i<=N+1）元素,需向前移動（）個元素。AiBN-iCN-i+1DN-i-1第2題判斷題(1分)對于C語言中的數(shù)組，&a[i]等價于a+i，后者中的i是指字節(jié)數(shù)。第3題判斷題(1分)高級語言通常不關心一個占了多個字節(jié)的數(shù)據(jù)元素的非首字節(jié)。第4題判斷題(1分)順序表就是以元素在內存中的相鄰來表示它們在邏輯上的相鄰。作業(yè)1第1題單選題(1分)下面關于鏈表L的說法正確的是（）？AL代表鏈表在內存中的整體結構BL是一個指針數(shù)組，其各元素分別指向鏈表的每個元素結點CL僅是指向鏈表頭結點的指針DL是鏈表的頭結點第2題單選題(1分)若某線性表最常用的操作是存取任意位置的元素，則（）存儲方式最合適。A順序表B雙向鏈表C雙向循環(huán)鏈表D單循環(huán)鏈表第3題單選題(1分)鏈表不具備的特點是（）。A可隨機訪問任一結點B插入刪除不需要移動元素C不必預估存儲空間容量D所需存儲空間與其長度成正比第4題單選題(1分)帶頭結點的單鏈表head為空表的條件是（）。Ahead==NULLBhead->next==NULLChead->next==headDhead!=NULL第5題單選題(1分)設p為單鏈表中某結點的指針（指向后繼的指針名為next），則在p結點后插入新結點（指針為s）的語句是（）和p->next=s。As->next=pBs=p->nextCs=pDs->next=p->next第6題單選題(1分)下面關于線性表的敘述中，錯誤的是哪一個？A線性表采用順序存儲，必須占用一段連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作C線性表采用鏈式存儲，也可以占用一段連續(xù)的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作第7題單選題(1分)指針p指向雙向循環(huán)鏈表L的表尾元素的條件是（）。Ap==LBp==NULLCp->prior==LDp->next==L第8題單選題(1分)在單鏈表中刪除p所指結點的后繼結點的語句是（）。Ap->next=p->next->next;Bp->next=NULL;Cp=p->next;Dp=p->next->next;第9題單選題(1分)刪除單鏈表中指針p所指結點的語句序列為（）。Aq=p->next;p->data=q->data;p->next=q->next;free(q);Bq=p->next;q->data=p->data;p->next=q->next;free(q);Cq=p->next;p->next=q->next;free(q);Dq=p->next;p->data=q->data;free(q);第10題單選題(1分)若希望以O(1)的時間復雜度找到當前結點的前驅，則鏈表最好采用（）。A單鏈表B單循環(huán)鏈表C雙向鏈表D以上均可作業(yè)2第1題單選題(1分)循環(huán)鏈表的主要優(yōu)點是（）？A不再需要頭指針了B已知某個結點的位置后，能很容易找到它的直接前驅結點C在進行刪除操作后，能保證鏈表不斷開D從表中任一結點出發(fā)，都能遍歷整個鏈表第2題單選題(1分)若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A順序表B單鏈表C單循環(huán)鏈表D雙向鏈表第3題判斷題(1分)對于單鏈表，要得到某個結點的值，只需要知道該結點的指針即可，因此，單鏈表也支持隨機存取。第4題判斷題(1分)若使用的編程語言不支持指針語法，則無法用該語言實現(xiàn)鏈表。第5題判斷題(1分)L指向以頭插法創(chuàng)建的單鏈表的頭結點，對L進行遍歷得到的序列與創(chuàng)建鏈表時的輸入序列一致。第6題判斷題(1分)刪除單鏈表的第i個結點不需要移動元素，故其時間復雜度為O(1)。作業(yè)第1題單選題(1分)以鏈式存儲并按指數(shù)遞增的2個多項式（各有n項）相加，最少的比較次數(shù)是（）？AnBn+1C2*nD2*n+1第2題判斷題(1分)以線性表存儲多項式，鏈式存儲一定比順序存儲好。第3題判斷題(1分)稀疏多項式適合以鏈表來存儲。作業(yè)第1題單選題(1分)下面的哪個例子不具有棧的特性？A多個人依次過獨木橋時，最前面的人發(fā)現(xiàn)前方有危險，需要退回到入口B彈夾的裝填與發(fā)射C一條單向車道上，最前面的車拋錨了，需要清空道路等待救援D多輛車依次通過高速收費站的某個窗口第2題單選題(1分)下列關于棧的說法錯誤的是？A棧具有后進先出特性B棧具有先進后出特性C元素的入棧順序和出棧順序相反D棧允許在中間位置插入、刪除元素第3題單選題(1分)入棧順序為1、2、3，共有（）種不同的出棧序列（2次入棧之間可能有0到多次出棧）。A6B5C3D1第4題判斷題(1分)棧頂元素和棧底元素有可能是同一個元素。第5題判斷題(1分)棧底元素不可能被刪除。第6題判斷題(1分)和線性表不同，棧不需要顯式指定插入和刪除的位置。作業(yè)第1題單選題(1分)6個元素按3，2，1，4，5，6的順序進棧（2次入棧間可能有零至多次出棧），下列哪個不是合法的出棧序列？A2，1，4，3，6，5B1，2，4，6，5，3C4，1，3，2，5，6D5，4，1，6，2，3第2題單選題(1分)設入棧序列是p1，p2，p3，…，pn（2次入棧間可能有零至多次出棧），出棧序列是1，2，3，…，n，若p3=3，則p1（）。A可能是2B一定是2C不可能是1D一定是1第3題單選題(1分)指針top指向鏈棧的棧頂，則出棧操作對應的語句為（）。Atop=top+1;Btop=top-1;Ctop->next=top;Dtop=top->next;第4題單選題(1分)對于順序棧和鏈棧，它們的入棧和出棧操作的時間復雜度均為（）。AO(n)BO(n^2)CO(1)DO(log2(n))作業(yè)第1題單選題(1分)使用棧將十進制數(shù)N轉換為r進制數(shù)時，每次入棧的是（）？AN/rBN%rCN-rDr第2題單選題(1分)使用棧判斷括號串是否匹配，當讀入左括號時應（），算法結束時，若棧（），則括號串是匹配的。A出棧、為空B出棧、非空C入棧、為空D入棧、非空作業(yè)第1題單選題(1分)一個遞歸算法必須包括（）。A遞歸部分B終結條件和遞歸部分C迭代部分D終結條件和迭代部分第2題單選題(1分)下列關于遞歸錯誤的說法是（）。A遞歸函數(shù)一定有返回值B遞歸算法一定有終結條件C遞歸算法執(zhí)行時會在內存中自動維護一個工作棧D遞歸算法一定包含循環(huán)結構第3題單選題(1分)將遞歸算法轉換成等價的非遞歸算法，通常應借助（）。A樹B隊列C數(shù)組D棧第4題判斷題(1分)將遞歸算法轉換成等價的非遞歸算法，一定要借助棧。第5題判斷題(1分)解決同一問題，遞歸形式的算法的執(zhí)行效率通常比非遞歸形式要高。第6題判斷題(1分)任何遞歸形式的算法，都可以轉換為非遞歸的形式。作業(yè)第1題單選題(1分)棧和隊列的共同特點是（）。A只允許在端點處插入和刪除元素B都是先進后出C都是先進先出D沒有共同點第2題單選題(1分)隊列中允許插入元素的一端稱為（），允許刪除元素的一端稱為（）。A隊尾、隊尾B隊尾、隊頭C隊頭、隊尾D隊頭、隊頭第3題單選題(1分)下列關于隊列的說法錯誤的是？A隊列具有先進先出特性B隊列具有后進后出特性C元素的入隊順序和出隊順序相反D隊列不允許在中間位置插入、刪除元素第4題單選題(1分)下面的場景中，不符合隊列操作特性的是？A食堂窗口取餐B發(fā)送到打印機的多個Word文件C按退格鍵刪除已輸入的字符D高速ETC收費車道第5題判斷題(1分)棧和隊列都是限制了存取點的線性表。作業(yè)第1題單選題(1分)容量為m的循環(huán)隊列Q，隊頭和隊尾位置分別是front和rear，則隊列滿的條件是（）？AQ.rear==Q.front+1B(Q.rear+1)%m==Q.frontCQ.rear+1==Q.frontDQ.rear==Q.front第2題單選題(1分)容量為m的循環(huán)隊列Q，隊頭和隊尾位置分別是front和rear，則隊列長度是（）？AQ.rear-Q.frontBQ.front-Q.rearC(Q.rear-Q.front+m)％mD(Q.front-Q.rear+m)％m第3題單選題(1分)容量為m的循環(huán)隊列Q，隊尾位置是rear，則入隊時對rear的操作是（）？AQ.rear=Q.rear-1BQ.rear=(Q.rear-1)%mCQ.rear=Q.rear+1DQ.rear=(Q.rear+1)%m第4題單選題(1分)容量為m的循環(huán)隊列Q，隊頭位置是front，則出隊時對front的操作是（）？AQ.front=Q.front-1BQ.front=(Q.front-1)%mCQ.front=Q.front+1DQ.front=(Q.front+1)%m第5題單選題(1分)循環(huán)隊列的容量為6，rear和front分別是0和3，則從隊列中刪除3個元素，再加入2個元素后，rear和front分別是（）？A2和6B2和0C0和2D6和2作業(yè)第1題判斷題(1分)無論是幾維數(shù)組，都可視為線性表。第2題判斷題(1分)通常不會對數(shù)組進行增刪元素的操作。第3題判斷題(1分)與其他數(shù)據(jù)結構不同，數(shù)組通常只采用順序存儲結構。作業(yè)1第1題單選題(1分)將M行N列的二維數(shù)組按行為主序存放，首個元素a00存于地址B（占d個字節(jié)），則元素aij的地址是（）？AB+(i*M+j)*dBB+(i*N+j)*dCB+(j*M+i)*dDB+(j*N+i)*d第2題單選題(1分)將M行N列的二維數(shù)組按列為主序存放，首個元素a00存于地址B（占d個字節(jié)），則元素aij的地址是（）？AB+(i*M+j)*dBB+(i*N+j)*dCB+(j*M+i)*dDB+(j*N+i)*d第3題單選題(1分)二維數(shù)組A[0..5][0..6]按列為主序存儲在起始地址為1000的內存單元中，每個元素占5個字節(jié)，則元素A[5][5]的地址是（）。A1175B1180C1205D1210第4題單選題(1分)設有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始順序存放，當用以列為主存放時，元素A[5，8]的存儲首地址為（）。ABA+141BBA+180CBA+222DBA+225第5題判斷題(1分)如果計算機主板上插有2根及以上的內存條，則此計算機的內存空間是二維的。第6題判斷題(1分)無論是幾維數(shù)組，都要轉換為一維數(shù)組才能存放到內存中。第7題判斷題(1分)故意不用編程語言原生提供的數(shù)組語法來實現(xiàn)數(shù)組這種數(shù)據(jù)結構，通常是沒有必要的。第8題判斷題(1分)所有高級語言的二維數(shù)組都是按行為主序存放的。作業(yè)2第1題判斷題(1分)所有高級語言的二維數(shù)組都是嚴格占據(jù)一段連續(xù)的存儲空間。第2題判斷題(1分)隨機存取是順序存儲才有的特性。第3題判斷題(1分)隨機存取就是隨機地讀寫一段連續(xù)內存中的某個位置。第4題判斷題(1分)訪問一段連續(xù)存儲空間中某個位置的時間復雜度與該段空間的大小和要訪問的位置有關。第5題判斷題(1分)將隨機存取中的“隨機”理解為“任意”、“隨意”、“直接”，更能體現(xiàn)隨機存取的本質。第6題判斷題(1分)機械硬盤的工作原理決定了其不支持隨機存取。作業(yè)第1題單選題(1分)10階對稱矩陣以行為主序存儲，a[1][1]為首個元素，其地址為1，每個元素占1個字節(jié)，則a[8][5]的地址是（）。A40B13C33D18第2題單選題(1分)將三對角矩陣A[1..100][1..100]按行為主序存入一維數(shù)組B[1..298]中，則元素A[66][65]在B中的位置為（）？A198B195C197D196第3題單選題(1分)三對角線矩陣A[1..n][1..n]以行序為主順序存儲，其存儲始址是b，每個元素占一個字節(jié)，則元素A[i][j](1≤i,j≤n)的存儲起始地址為（）。Ab+2*j+i-2Bb+2*i+j-2Cb+2*j+i-3Db+2*i+j-3作業(yè)第1題單選題(1分)對m行n列的未經(jīng)壓縮（即以二維數(shù)組表示）的稀疏矩陣進行轉置，時間復雜度是（）？AO(m)BO(n)CO(m*n)DO(max(m,n))第2題單選題(1分)以三元組順序表存儲的稀疏矩陣（m行n列，非零元個數(shù)為t）的常規(guī)轉置算法，時間復雜度是（）？AO(n*t)BO(m*t)CO(m*n)DO(m*n*t)第3題單選題(1分)以三元組順序表存儲的稀疏矩陣（m行n列，非零元個數(shù)為t）的快速轉置算法，時間復雜度是（）？AO(n*t)BO(n+t)CO(m+t)DO(m+n+t)第4題判斷題(1分)對稀疏矩陣進行壓縮存儲的目的是節(jié)省存儲空間。第5題判斷題(1分)稀疏矩陣被壓縮存儲后，仍具有隨機存取的特性。作業(yè)第1題單選題(1分)下列不是樹的是（）？A企業(yè)的部門組織架構BWindows中的文件系統(tǒng)C書的目錄D多個人之間的同學關系第2題單選題(1分)下列關于樹的說法正確的是（）？AParent經(jīng)常譯為“父母”、“雙親”，因此，樹中某個結點的雙親結點可能有2個。B結點的度與樹的度是同一個概念。C父節(jié)點是兄弟的那些結點互稱為堂兄弟。D樹是一種非線性結構。第3題判斷題(1分)樹的定義本身就是遞歸的。作業(yè)1第1題單選題(1分)二叉樹中孩子數(shù)為1和2的結點個數(shù)分別是10和20，則該二叉樹共有（）個結點。A41B51C49D39第2題單選題(1分)設一棵三叉樹中有50個度為0的結點，21個度為2的結點，則度為3的結點有（）個。A51B22C14D15第3題單選題(1分)規(guī)定根結點在第1層，則具有K層的二叉樹至少有（）個結點？AKBK-1C2^(K-1)D2^K-1第4題單選題(1分)規(guī)定根結點在第1層，則具有K層的二叉樹至多有（）個結點？AKBK-1C2^(K-1)D2^K-1第5題單選題(1分)設完全二叉樹的根結點序號為1，（）可判定序號分別為p和q的兩個結點在同一層。A?log2(p)?=?log2(q)?Blog2(p)=log2(q)C?log2(p)?+1=?log2(q)?D?log2(p)?=?log2(q)?+1第6題單選題(1分)若根的層次為1，具有61個結點的完全二叉樹的高度為（）。A5B6C7D8第7題單選題(1分)高度為h的二叉樹中只有度為0和2的結點，則此二叉樹的結點數(shù)至少有（）個。Ah+1B2*h+1C2*hD2*h-1作業(yè)2第1題單選題(1分)具有2048個結點的二叉樹的最小高度是（）？A11B12C13D2048第2題單選題(1分)下列有關二叉樹的說法正確的是（）。A二叉樹的度為2B一棵二叉樹的度可以小于2C二叉樹中至少有一個結點的度為2D二叉樹中任何一個結點的度都為2第3題單選題(1分)在一棵高度為k的滿二叉樹中，結點總數(shù)為（）。A2^(k-1)B2^kC2^k-1D向下取整(log2(k))+1第4題單選題(1分)一棵樹高為k的完全二叉樹至少有（）個結點。A2^k-1B2^(k-1)-1C2^(k-1)D2^k第5題單選題(1分)若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)是（）。A9B11C15D不確定作業(yè)第1題單選題(1分)以二叉鏈表存放一棵含有N個節(jié)點的二叉樹，共有（）個空指針？AN+1BN-1CND2*N第2題單選題(1分)以二叉鏈表存放一棵含有N個節(jié)點的二叉樹，共有（）個非空指針？AN+1BN-1CND2*N第3題單選題(1分)下列關于二叉樹的說法中錯誤的是（）？A若二叉樹使用順序方式存儲，則必須先將該二叉樹補全為滿二叉樹。B若二叉樹使用順序方式存儲，結點所在的下標對應著其在二叉樹中的編號。C以順序方式存儲的二叉樹可能會浪費大量空間。D若知道了二叉鏈表中根結點的指針，則整棵二叉樹就唯一確定了。作業(yè)第1題單選題(1分)在二叉樹的先序、中序和后序序列中，所有葉結點的先后順序（）。A都不相同B完全相同C先序和中序相同，而后序不同D中序和后序相同，而先序不同第2題單選題(1分)若二叉樹的先序序列為ABDECF，中序序列為DBEAFC，則其后序序列為（）。ADEBAFCBDEFBCACDEBCFADDEBFCA第3題單選題(1分)若二叉樹的中序序列為A+B*C-D/E，后序序列為ABC*+DE/-，則其先序序列為（）。A-A+B*C/DEB-A+B*CD/EC-+*ABC/DED-+A*BC/DE第4題單選題(1分)前序序列與中序序列相同的二叉樹為（）。A根結點無左孩子的二叉樹B所有結點只有右孩子的二叉樹C只有根結點的二叉樹D所有的結點只有左孩子的二叉樹第5題單選題(1分)前序序列和后序序列相同的二叉樹為（）。A根結點無左孩子的二叉樹B所有結點只有右孩子的二叉樹C只有根結點的二叉樹D所有的結點只有左孩子的二叉樹第6題判斷題(1分)給定先序序列和后序序列，不能唯一確定二叉樹。第7題判斷題(1分)一棵非空二叉樹一定滿足：某個結點若有左孩子，則其中序前驅一定沒有右孩子。作業(yè)第1題單選題(1分)在線索二叉樹中，結點t沒有左子樹的充要條件是（）。At->lchild==NULLBt->ltag==THREADCt->ltag==THREAD&&t->lchild==NULLD以上都不對第2題單選題(1分)n個結點的線索二叉樹上含有的非空線索數(shù)為（）。A2nBn-1Cn+1Dn第3題單選題(1分)二叉樹在線索后，仍不能有效求解的問題是（）？A先序線索二叉樹中求先序后繼B中序線索二叉樹中求中序后繼C中序線索二叉樹中求中序前驅D后序線索二叉樹中求后序后繼第4題判斷題(1分)二叉樹線索化后，任一結點均有指向其前驅和后繼的線索。第5題判斷題(1分)中序線索樹中，結點的前驅是其左子樹上最左的結點。第6題判斷題(1分)中序線索樹中，結點的后繼是其右子樹上最左的結點。第7題判斷題(1分)二叉樹的中序序列中，最后一個結點是整棵樹最右的那個結點。第8題判斷題(1分)二叉樹經(jīng)中序線索化后，不存在空指針。作業(yè)第1題單選題(1分)以孩子-兄弟表示法表示的樹，每個結點包含兩個指針成員，分別指向當前結點的（）和（）。A第一個孩子、第一個兄弟B下一個孩子、下一個兄弟C第一個孩子、下一個兄弟D下一個孩子、第一個兄弟第2題單選題(1分)如果BT是由樹T轉換而來的二叉樹，則對T的后序遍歷就是對BT的（）遍歷。A先序B中序C后序D層序第3題單選題(1分)利用二叉鏈表存儲樹，則根結點的右指針是（）。A指向最左孩子B指向最右孩子C空D非空第4題單選題(1分)下列哪一個不是樹的存儲形式？A雙親表示法B孩子鏈表表示法C孩子兄弟表示法D順序存儲表示法第5題判斷題(1分)一棵樹必須轉換成二叉樹后才能存儲。第6題判斷題(1分)樹的葉子數(shù)一定等于其對應的二叉樹的葉子數(shù)。第7題判斷題(1分)對樹進行先序遍歷，等價于以先序遍歷該樹對應的二叉樹。第8題判斷題(1分)對樹進行后序遍歷，等價于以后序遍歷該樹對應的二叉樹。作業(yè)第1題單選題(1分)關于哈夫曼樹的敘述正確的是（）。A樹的左分支必須編碼成0，右分支必須編碼成1B權值較大的結點對應的哈夫曼編碼通常較短C對于給定的若干結點，哈夫曼樹總是唯一的D給定M個葉結點，構造的哈夫曼樹共包含2M+1個結點第2題單選題(1分)由權值為9,2,5,7的四個葉子結點構造一棵哈夫曼樹，該樹的WPL為（）。A23B37C44D46第3題單選題(1分)根據(jù)使用頻率，為5個字符設計的哈夫曼編碼不可能是（）。A111,110,10,01,00B000,001,010,011,1C100,11,10,00,01D001,000,01,11,10第4題單選題(1分)哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較小的結點通常離根（）。A不確定B較近C較遠第5題單選題(1分)設給定權值的葉子總數(shù)有n個，其哈夫曼樹的結點總數(shù)為（）。A不確定B2nC2n+1D2n-1第6題判斷題(1分)哈夫曼編碼是前綴編碼。第7題判斷題(1分)在哈夫曼樹中，權值相同的葉結點一定在同一層。作業(yè)第1題單選題(1分)無向圖中一個頂點的度是指圖中（）。A通過該頂點的簡單路徑數(shù)B通過該頂點的環(huán)數(shù)C與該頂點相鄰接的頂點數(shù)D與該頂點連通的頂點數(shù)第2題單選題(1分)無向圖中所有頂點的度數(shù)之和等于所有邊數(shù)（）倍，有向圖中所有頂點的入度之和等于所有頂點出度之和的（）倍。A2，1B1，2C1/2，1D1，1/2第3題單選題(1分)下列關于圖和樹的說法，錯誤的是（）？A樹可以看作圖的特例B樹中有一個特殊的元素(根)，而圖中每個元素的“地位”是一樣的C圖和樹中的邊沿任意軸旋轉后，各元素間的邏輯關系保持不變D樹中任意兩個元素間有唯一的簡單路徑，而圖中任意兩個元素間可能有零或多條簡單路徑第4題判斷題(1分)有向圖中有一條邊，則v稱為弧頭。第5題判斷題(1分)N個頂點的有向完全圖有N(N-1)條邊。第6題判斷題(1分)有向圖中，頂點的入度是以v為弧尾的邊的數(shù)量。作業(yè)第1題單選題(1分)若含有N個頂點的有向圖的邊數(shù)遠小于N*(N-1)，且要方便地求得某個頂點的出度，則采用（）存儲結構較為合適。A鄰接矩陣B逆鄰接表C鄰接表D前述3者都一樣第2題單選題(1分)下列哪一種圖的鄰接矩陣是對稱矩陣？A有向圖B無向圖CAOV網(wǎng)D以上均是第3題單選題(1分)采用鄰接表表示有向圖，若圖中某頂點的入度和出度分別為d1和d2，則該頂點對應的單鏈表的表結點數(shù)為（）。Ad1Bd2Cd1-d2Dd1+d2第4題判斷題(1分)無向圖的鄰接矩陣一定是對稱矩陣。第5題判斷題(1分)若圖的鄰接矩陣不是對稱矩陣，則該圖一定是有向圖。第6題判斷題(1分)若圖的鄰接矩陣是對稱矩陣，則該圖一定是無向圖。第7題判斷題(1分)一個有向圖的鄰接表和逆鄰接表中結點的個數(shù)可能不相等。作業(yè)第1題單選題(1分)圖的深度優(yōu)先搜索類似于樹的（）遍歷，圖的廣度優(yōu)先搜索類似于樹的（）遍歷。A先序，層序B層序，先序C中序、層序D先序，中序第2題單選題(1分)下列關于圖的遍歷的說法，錯誤的是（）。A圖的遍歷是從給定的起始頂點出發(fā)，將每一個頂點訪問且僅訪問一次B深度優(yōu)先搜索可以不用遞歸方式來實現(xiàn)C從給定頂點開始，深度和廣度優(yōu)先搜索可能無法訪問到其他某些頂點D深度優(yōu)先搜索會先找到“最近解”第3題單選題(1分)無向圖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)}，對該圖進行深度優(yōu)先搜索，得到的頂點序列是（）。Aa,b,e,c,d,fBa,c,f,e,b,dCa,e,b,c,f,dDa,e,d,f,c,b第4題判斷題(1分)深度優(yōu)先搜索只適用于以鄰接矩陣存儲的圖。第5題判斷題(1分)廣度優(yōu)先搜索每訪問一個頂點后，都要將其放到棧中。作業(yè)1第1題單選題(1分)N個頂點的無向連通圖，至少有（）條邊，至多有（）條邊。AN，N*(N-1)BN-1，N*(N-1)/2CN-1，N*(N-1)DN，N*(N-1)/2第2題單選題(1分)N個頂點的有向連通圖，至少有（）條邊，至多有（）條邊。AN，N*(N-1)BN-1，N*(N-1)/2CN-1，N*(N-1)DN，N*(N-1)/2第3題單選題(1分)n個頂點的圖，最少有（）個連通分量，最多有（）個連通分量。A0，nB1，n-1C1，nD0，n-1第4題單選題(1分)有28條邊的非連通無向圖，至少有（）個頂點。A6B7C8D9第5題判斷題(1分)連通分量是圖的最小連通子圖。第6題判斷題(1分)生成樹是連通圖的最大連通子圖。作業(yè)2第1題判斷題(1分)求稠密圖的最小生成樹，最好用Prim算法。第2題判斷題(1分)連通圖上各邊權值均不相同，則該圖的最小生成樹一定是唯一的。第3題判斷題(1分)從有向圖G中的給定起始頂點v0出發(fā)，若能到達其他任一頂點，則G是強連通圖。第4題判斷題(1分)N個頂點的無向圖，若邊數(shù)大于2N，則該圖必是連通圖。作業(yè)第1題單選題(1分)對有向圖G進行拓撲排序的目的不是（）。A判斷G是否包含環(huán)B查看G中頂點所代表的活動的先后關系C檢查G表示的工序圖是否合理D將G中所有頂點按大小關系排序第2題單選題(1分)無向圖G=(V,E)，其中V={a,b,c,d,e}，E={,,,,,}，對該圖進行拓撲排序，下面哪一個不是其拓樸序列？Aa,d,c,b,eBd,a,b,c,eCa,b,d,c,eDa,b,c,e,d第3題單選題(1分)在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（）。AG中有一條從Vj到Vi的路徑BG中有一條從Vi到Vj的路徑CG中有弧DG中沒有弧第4題判斷題(1分)若有向圖的鄰接矩陣中，主對角線以下元素均為0，則該圖一定無環(huán)。第5題判斷題(1分)拓撲排序算法中，必須使用隊列來存放入度為0的頂點。作業(yè)第1題單選題(1分)對于下圖，以頂點1為起始頂點，使用Dijkstra算法依次找到的多條最短路徑所到達的終點分別是（）？A3，4，6，2，5B2，3，4，5，6C6，5，4，3，2D4，2，6，3，5作業(yè)第1題單選題(1分)查找表可分為（）？A定長查找表、變長查找表B靜態(tài)查找表、動態(tài)查找表C簡單查找表、復雜查找表D數(shù)值型查找表、非數(shù)值型查找表第2題單選題(1分)下列關于關鍵字的說法中正確的是（）？A學生的姓名可以作為主關鍵字B只要某個數(shù)據(jù)項是可比較的，其就能作為關鍵字C主關鍵字可能對應多個數(shù)據(jù)元素D關鍵字的具體數(shù)據(jù)類型會影響采用的查找算法第3題判斷題(1分)除非特別說明，談到平均查找長度，通常暗含了等概率和查找成功這兩個前提。作業(yè)第1題單選題(1分)在長度為n的查找表中做順序查找，查找成功時的平均查找長度是（）。A(n+1)/2Bn/2Cn+1Dn第2題單選題(1分)采用折半查找，在長度為18的有序順序表（下標從1開始）中查找第3個關鍵字，依次比較的關鍵字的下標是（）。A1,2,3B9,5,2,3C9,5,3D9,4,2,3第3題單選題(1分)下面關于折半查找（或二分查找）的敘述正確的是（）。A表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B表必須有序，且表只能以順序方式存儲C表必須有序且表中數(shù)據(jù)元素的類型必須是整型，實型或字符型D表必須有序，而且只能從小到大排列第4題單選題(1分)在n個關鍵字構成的有序順序表中進行折半查找，最大比較次數(shù)是（）。A向下取整(log2(n))B向上取整(log2(n))C向下取整(log2(n))+1Dn第5題單選題(1分)在長度為n的查找表中做順序查找，查找失敗時的平均查找長度是（）。A(n+1)/2Bn/2Cn+1Dn第6題單選題(1分)索引順序表的數(shù)據(jù)組織方式是（）？A數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序B數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)不必有序，但塊間必須有序，每塊內最大（或最小）的數(shù)據(jù)組成索引塊C數(shù)據(jù)分成若干塊，每塊內數(shù)據(jù)有序，每塊內最大（或最?。┑臄?shù)據(jù)組成索引塊D數(shù)據(jù)分成若干塊，每塊（除最后一塊外）的數(shù)據(jù)個數(shù)相同第7題判斷題(1分)順序查找僅適用于順序存儲。第8題判斷題(1分)折半查找不適用于鏈式存儲。第9題判斷題(1分)分塊查找同時使用了順序查找和折半查找，故一般而言，其性能介于順序查找和折半查找之間。第10題判斷題(1分)折半查找的查找性能一定高于順序查找。作業(yè)第1題單選題(1分)將序列{50,72,43,85,75,20,35,45,65,30}逐個插入初始為空的二叉排序樹后，查找30要進行（）次比較。A4B5C6D7第2題單選題(1分)對二叉排序樹進行（）遍歷將得到遞增序列。A先序B中序C后序D層序第3題單選題(1分)以二叉鏈表存儲二叉排序樹，關鍵字最大的結點（）。A左指針一定為空B右指針一定為空C左右指針均為空D左右指針均不空第4題單選題(1分)當BST每層僅有一個結點時，其查找算法退化成（），ASL上升為（）。A順序查找、(n+1)/2B順序查找、nC折半查找、(n+1)/2D折半查找、n作業(yè)第1題單選題(1分)高度為5的AVL樹至少有（）個結點。A10B12C15D17第2題判斷題(1分)平衡二叉樹中根結點的平衡因子是1，若新結點插入到根的左子樹上，則必定需要調整。第3題判斷題(1分)將長度為n的元素序列組織成AVL樹時，無論序列如何排列，總能保證樹的ASL為log2(n)的量級。作業(yè)第1題單選題(1分)采用哈希函數(shù)H(k)=k%7，依次存放關鍵字{38,25,74,63,52,48}到A[0..6]中，若采用線性探測法解決沖突，則該哈希表在查找成功時的平均查找長度為（）。A1.5B1.7C2D2.3第2題單選題(1分)下列以鏈地址法處理哈希表沖突的敘述中，錯誤的是（）。A此時的哈希表整體上是一個數(shù)組B此時的哈希表整體上是一個鏈表C此時的哈希表中可能存在空鏈表D位于同一個橫向鏈表中的結點的Hash地址都相同第3題單選題(1分)將10個元素存放到容量為100000的哈希表中，則（）產(chǎn)生沖突。A一定會B一定不會C仍可能會第4題單選題(1分)通過（）法構造的哈希函數(shù)一定不會發(fā)生沖突。A除留余數(shù)B平方取中C直接定址D以上均可能發(fā)生沖突第5題單選題(1分)k個關鍵字互為同義詞，采用線性探測法處理沖突，則至少要進行（）次探測？Ak(k-1)/2BkCk-1Dk(k+1)/2第6題單選題(1分)下面關于哈希函數(shù)的說法中正確的是（）。A哈希函數(shù)越復雜越好，因為這樣隨機性好，沖突可能性低B除留余數(shù)法是所有哈希函數(shù)中最好的C直接定址法是所有哈希函數(shù)中最好的D不存在特別好與壞的哈希函數(shù)，要視具體情況而定第7題判斷題(1分)在哈希表中查找元素時，元素的存放地址是算出來的，故無需比較元素。第8題判斷題(1分)Hash表的平均查找長度與處理沖突的方法無關。作業(yè)第1題判斷題(1分)通常將元素的比較和移動操作視為排序算法的基本步驟。第2題判斷題(1分)某個序列經(jīng)排序算法A排序后，相同關鍵字的先后位置沒有變化，則排序算法A是穩(wěn)定的。第3題判斷題(1分)某個序列經(jīng)排序算法A排序后，相同關鍵字的先后位置發(fā)生了變化，則排序算法A是不穩(wěn)定的。第4題判斷題(1分)穩(wěn)定的排序算法一定能修改成不穩(wěn)定的。第5題判斷題(1分)不穩(wěn)定的排序算法或許能修改成穩(wěn)定的。作業(yè)第1題單選題(1分)對關鍵字序列{15,9,7,8,20,-1,4}進行希爾排序，第一趟排序結果的首個關鍵字是15，則該趟采用的增量是（）。A1B2C3D4第2題單選題(1分)直接插入排序中，監(jiān)視哨的作用是暫存待插入的元素以及（）？A減少元素的比較次數(shù)B減少元素的移動次數(shù)C避免在元素比較過程中檢查當前位置是否越界D減少臨時空間的使用量第3題判斷題(1分)若待排序列越雜亂無序，則Shell排序的效率就越低。第4題判斷題(1分)Shell排序的最后一趟就是直接插入排序。第5題判斷題(1分)若選取的增量序列是{8,4,2,1}，Shell排序依然能正確工作。第6題判斷題(1分)對于同一待排序列，選取的增量序列不同，希爾排序的性能也不同。作業(yè)第1題單選題(1分)對n個元素進行冒泡排序，第一趟共要比較（）對元素。An-1Bn/2Cn+1Dn第2題單選題(1分)快速排序在最好和最壞情況下的空間復雜度分別是（）。AO(1og2(n))和O(1og2(n))BO(n)和O(1og2(n))CO(1og2(n))和O(n)DO(n)和O(n)第3題單