算法與數(shù)據(jù)結構試題

1、精選文檔第一章 算法分析基礎1、下列時間復雜度最好的是( )A、O B、OC、O D、O2、 從邏輯上可以把數(shù)據(jù)結構分為哪兩大類？（ ）A、動態(tài)結構、靜態(tài)結構 B、順序結構、鏈式結構 C、線性結構、非線性結構 D、初等結構、構造型結構3、算法分析的主要任務是分析（）A算法是否具有較好的可讀性B算法中是否存在語法錯誤C算法的功能是否符合設計要求D算法的執(zhí)行時間和問題規(guī)模之間的關系4、下面程序段中帶下劃線的語句的執(zhí)行次數(shù)是 。for(i=0;i<=n;i+)for(j=0;j<=i;j+) x=x+1;5、下列程序的時間復雜度為 （）s=0;for(i=0;i<10;i+)for

2、(j=0;j<10;j+) s=s+1;A O（10）                     B O（20）C O （1）           DO（102）6、數(shù)據(jù)的最小單位是（）A.數(shù)據(jù)項        &#

3、160;                    B.數(shù)據(jù)類型 C.數(shù)據(jù)元素                      D.數(shù)據(jù)變量7、下列程序的時間復雜度為（）i=1；k=100；while（i<

4、;n） k=k+1； i=i+2； A.O（1）                     B. O（n） C. O（n3）                     D.O（n2）8、稱算法的時間復雜度

5、為O(logn)，其含義是指算法的執(zhí)行時間和_的數(shù)量級相同。第二章 線性表1、非空的循環(huán)單鏈表L的尾結點（由p所指）滿足（ ） A.p->next=NULL                  B. p=NULL C. p->next= L               

6、   D. p= L2、從一個長度為n的順序表中刪除第i個元素（1in）時，需向前移動的元素的個數(shù)是 （） A.n-i                            B.n-i+1 C.n-i-1         

7、;                D.i3、鏈表不具備的特點是 （）A可隨機訪問任一結點                    B插入刪除不需要移動元素C不必事先估計存儲空間       &

8、#160;         D所需空間與其長度成正比4、順序表的存儲密度為1，而鏈表的存儲密度 _。5、寫算法，順序查找一個元素值等于e的元素的邏輯序號。若這樣的元素不存在，則返回值為0。6、完善下列程序段。在一個單鏈表（已知每個結點含有數(shù)據(jù)域data和指針域next）中刪除p所指結點時，可執(zhí)行如下操作： 1）q=p->next; 2) p->data=_; 3) p->next=_; 4) free(q);題目如改成刪除p所指的結點的后繼結點, 為 7、設單鏈表中結點結構為(data,link)

9、.已知指針q所指結點是指針p所指結點的直接前驅，若在*q 與*p之間插入結點*s，則應執(zhí)行下列哪一個操作（      ） A   s->link=p->link;  p->link=s;      B  q->link=s; s->link=p C  p->link=s->link; s->link=p;    

10、;  D  p->link=s; s->link=q;8、若某線性表中最常用的操作是在第i個元素之前插入一個元素和刪除第i個元素，則采用什么存儲方式最節(jié)省時間。 ( )A、散列表 B、單鏈表 C、二叉鏈表 D、順序表9、寫一算法實現(xiàn)帶頭結點的單鏈表L的就地逆置，即在原表的存儲空間中將表（a1,a2,an）逆置為（an,a2,a1）。10、指出下述程序段的功能是什么? LinkList Demo(LinkList L) / L 是無頭結點單鏈表ListNode *Q,*P;if(L&&L->next)Q=L;L=

11、L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L;11、線性表（a1,a2,，an）以鏈接方式存儲，訪問第i個位置元素的時間復雜性為（）。A、O(i) B、O(1)C、O(n) D、O(i-1)12、設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用哪個最節(jié)省時間（）A、單鏈表 B、單循環(huán)鏈表C、帶尾指針的單循環(huán)鏈表 D、帶頭結點的雙循環(huán)鏈表13、雙向鏈表中有兩個指針域，llink和rlink，分別指向前驅和后繼，設p指向鏈表中的一個結點，q指向一待插入結點，想要求

12、在p前插入q，則正確的插入為（）A. p->llink=q; q->rlink=p; p-llink->rlink=q; q->llink=p->llink;B. q->llink=p->llink; p-llink->rlink=q; q->rlink=p; p->llink= q->rlink;C. q->rlink=p; p->llink=q; p-llink->rlink=q; q->rlink=p;D. p-llink->rlink=q; q->rlink=p; q->llin

13、k=p->llink; p->llink=q; 14、線性表L=（a1，a2，an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 。15、順序存儲結構是通過物理上相鄰表示元素之間的關系；鏈式存儲結構是通過 表示元素之間的關系的。第三章 棧和隊列1、循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（）A. rear=rear+1 B. rear=(rear+1) % (m-1)C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)2、有6個元素6,5,4,3,2,1的順序進棧，問下列哪一個不是合法的出棧序列?()

14、A、5 4 3 6 1 2 B、4 5 3 1 2 6C、3 4 6 5 2 1 D、2 3 4 1 5 6 3、棧和隊列的共同點是（）A、都是先進先出 B、都是先進后出C、只允許在端點處插入和刪除元素 D、沒有共同點4、對于棧操作數(shù)據(jù)的原則是（）A、先進先出 B、后進先出C、后進后出 D、不分順序5、順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top，則值為x的元素入棧的操作時 6、設一個棧的輸入序列為1、2、3、4，則借助一個棧所得到的輸出序列不可能的是哪個？ （ ）A、1，2，3，4 B、4，3，2，1 C、1，3，4，2 D、4，1，2，37、一個棧的入棧序列為a，b，c，則出棧序列不可

15、能的是 (     ) A c,b,a    Bb,a,cCc,a,b     Da,c,b8、設輸入序列為a，b，c，d。下面的四個序列中，借助一個棧能夠得到的輸出序列是 （ ） A、d，c，a，b B、c，a，d，b C、a，c，d，b D、d，a，b，c9、若一個棧以向量V1.n存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是哪個？ ( ) A、top=top+1； Vtop=x B、 Vtop=x；top=top+1 C、top=top-1； Vt

16、op=x D、 V top=x；top=top-110、表達式a*(b+c)-d的后綴表達式是 ( )A、abcd*+- B、abc+*d- C、abc*+d- D、-+*abcd11、順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進棧操作的主要語句為 （ ） A.s.elemtop=e；   B.s.elemtop+1=e； s.top=s.top+1；     s.top=s.top+1； C.s.top=s.top+1；    D.s.top=s.top+1； s.ele

17、mtop+1=e;   s.elemtop=e；12、循環(huán)隊列sq中，用數(shù)組elem025存放數(shù)據(jù)元素，sq.front指示隊頭元素的前一個位置，sq.rear指示隊尾元素的當前位置，設當前sq.front為20，sq.rear為12，則當前隊列中的元素個數(shù)為（） A.8   B.16 C.17   D.1813、假設為循環(huán)隊列分配的向量空間為Q20，若隊列的長度和隊頭指針值分別為13和17，則當前尾指針的值為_ _。14、在循環(huán)隊列中，存儲空間為0n-1,設隊頭指針front指向隊頭元素前一個空閑元素，隊尾指針指向隊尾元素，那么隊滿標志為front=(

18、rear+1)%n，隊空標志為_ _。15、有5個元素，其進棧次序為A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出棧（即C 第一個且D第二個出棧）的次序有哪幾個？16、指出下述程序段的功能是什么? void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( !StackEmpty(S) arrn+=Pop(S);for (i=0, i< n; i+) Push(S, arri); /Demo1第四章 數(shù)組1、設有一個二維數(shù)組A1020，按列為主序存放于一個連續(xù)的存儲空間中，A00的存儲地址是200，每個數(shù)組元素占1個存儲

19、字，則A62的存儲字地址是多少。2、二維數(shù)組A610按行優(yōu)先順序存儲，若每個數(shù)組元素占用4個存儲單元，A00的存儲地址為860，則數(shù)組元素A35的存儲地址為（） A1000                                B860 C1140   

20、;                             D1200第六章 樹和二叉樹1、設樹T的度為4，其中度為1、2、3和4的結點個數(shù)分別為4,2,1,1，則T中的葉子結點數(shù)為 （）A. 5 B. 6 C. 7 D. 82、二叉樹由 、 、 三個基本單元組成。3、試編寫算法求出二叉樹的深度。二叉樹的存儲結構為如下

21、說明的二叉鏈表：typedef struct BiTNode TDataType data; struct BiTNode *lchild,*rchild; BiTree;4、將算術表達式（a+b）+c*(d+e)+f）*(g+h)轉化為二叉樹。5、已知一棵二叉樹的中序序列： E C B H F D J I G A， 后序序列： ，試畫出該二叉樹6、設T是一棵二叉樹，除葉子結點外，其它結點的度數(shù)皆為2，若 T中有6個葉結點，試問：（1）T樹中共有多少非葉結點？（2）若葉結點的權值分別為1,2,3,4,5,6。請構造一棵哈曼夫樹，并計算該哈曼夫樹的帶權路徑長度wpl。7、按二叉樹的定義，具有3個

22、結點的二叉樹有幾種（ ）A3                B4C5                D68、對于一棵具有30個結點的完全二叉樹，若一個結點的編號為5，則它的左孩子結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號為 。9、由八個分別帶權值為7、19、2、6、32、3、21、10的葉

23、子結點構造一棵哈夫曼樹，則該樹的帶權路徑長度為_。10、已知一棵完全二叉樹中共有768 個結點，則該二叉樹中共有_個葉子結點。11、以二叉鏈表為存儲結構， 寫一算法交換各結點的左右子樹。12、給出樹如下圖所示，請寫出先序遍歷和中序遍歷的節(jié)點次序。13、已知二叉樹的先序遍歷的結果為ABCDEF，中序遍歷的結果為BCAEFD，請畫出這顆二叉樹。14、給定一組權值9，6，14，2，3，16，請構造哈夫曼樹，并計算其帶權路徑長度。15、若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)為 （）A.9       

24、;    B.11C.15           D.不確定16、線索二叉樹是一種 （ ）結構A邏輯 B邏輯和存儲C物理 D線性17、一棵完全二叉樹上有1001個結點，其中葉子結點的個數(shù)_ _18、給出樹如下圖所示，請寫出先序遍歷和中序遍歷的節(jié)點次序。19、已知二叉樹的先序序列和中序序列分別為HDACBGFE和ADCBHFEG,畫出該二叉樹.20、以二叉鏈表為二叉樹的存儲結構， 寫一算法計算所有結點個數(shù)。21、以4，5，6，7，8作為葉子結點的權值構造哈夫曼樹，并求其帶權路徑長

25、度及個結點對應的哈夫曼編碼。第七章 圖1、10個頂點的連通圖的深度游先生成樹的邊數(shù)為（）A、11 B、10 C、9 D、無法確定2、無向圖的鄰接矩陣是（）A、對稱矩陣 B、零矩陣C、上三角矩陣 D、對角矩陣3、設圖的鄰接鏈表如題12圖所示，則該圖的邊的數(shù)目是（） A4               B5 C10              D204、設

26、無向圖的頂點個數(shù)為n，則該圖最多有多少條邊。（ ）A、n-1 B、n(n-1)/2 C、n(n+1)/2 D、n/2 5、在一個具有n個頂點的無向連接通圖中，至少包含有 條邊，至多包含有 條邊。6、給出下圖對應的鄰接表7、畫出下圖的最小生成樹8、含n個頂點的有向圖中，每個頂點的度最大可達_ _。9、求最短路徑的Dijkstra算法的時間復雜度為 。10、給出下圖的從結點a開始的遍歷次序，1）深度優(yōu)先；2）廣度優(yōu)先。第8章 查找1、以下與數(shù)據(jù)的存儲結構無關的術語是（）A、循環(huán)隊列 B、鏈表 C、哈希表 D、棧2、設有一個長度為100的已排好序的表，用二分查找進行查找，若查找不成功，至少比較多少次

27、 （ ） A、9 B、8 C、7 D、63、設有n個關鍵字，哈希查找法的平均查找長度是（） AO(1)                        BO(n) CO(long2n)                DO(

28、n2)4、對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為（）A、（N+1）/2 B、N/2 C、N D、(1+N)*N/25、Hash函數(shù)應以取值域滿足什么的值（）A、最大概率 B、最小概率 C、平均概率 D、等概率6、哈希表是通過將查找碼按選定的 和 ，把節(jié)點按查找碼轉換為地址進行存儲的線性表。7、在有序表A20中按二分查找方法查找元素A13，依次比較的元素下標是多少？假設有序表的起始元素從A0開始存放。 ( )A、9，14，12，13 B、9，15，12，13 C、9，14，11，12，13 D、10，15，12，138、若對長度為10的有序表進行折半查找，則在等概率時查找成功的平均查找長度為_。第九章 排序1、算法模擬,設待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。（1）用直接插入排序。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排列。(2)直接選擇排序。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排列。2、以關鍵字序列(265，301，751，129，