《數(shù)據(jù)結(jié)構(gòu)》期末復(fù)習(xí)考試用

1、一、選擇題1、 根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)v1出發(fā)，所得到的頂點(diǎn)序列是_C_。A、 v1,v2,v3,v5,v4 B、 v1,v2,v3,v4,v5C、 v1,v3,v4,v5,v2 D、 v1,v4,v3,v5,v22、數(shù)據(jù)結(jié)構(gòu)被形式地定義為(K,R),其中K是 B 的有限集，R是K上的 D 有限集。 A、算法 B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)構(gòu) A、操作 B、映象C、存儲D、關(guān)系3、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成_C_。A、動態(tài)結(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)4、具有n個頂點(diǎn)的有向圖最多有( B )條邊。 A、n

2、B、 n(n-1) C、 n(n+1) D、 5、計(jì)算機(jī)算法指的是 C ，它必須具備輸入、輸出和 B 等5個特性。 A、計(jì)算方法B、排序方法 C、解決問題的有限運(yùn)算序列D、調(diào)度方法 A、可執(zhí)行性、可移植性和可擴(kuò)充性 B、可行性、確定性和有窮性C、確定性、有窮性和穩(wěn)定性D、易讀性、穩(wěn)定性和安全性6.下面關(guān)于線性表的敘述中，錯誤的為( D   ) A.順 序表使用一維數(shù)組實(shí)現(xiàn)的線性表         B.順序表必須占用一片連續(xù)的存儲單元 C.順序表的空間利用率

3、高于鏈表       D.在鏈表中，每個結(jié)點(diǎn)只有一個鏈域7.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是( B  ) A. head=NIL                 B. head.next=NIL C. head.next=head        

4、60;  D. head< >NIL8.隊(duì)列通常采用兩種存儲結(jié)構(gòu)是( A   ) A.順序存儲結(jié)構(gòu)和鏈 表存儲結(jié)構(gòu)         B.散列方式和索引方式C.鏈表存儲結(jié)構(gòu)和數(shù)組               D.線 性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)9.深度為5的二叉樹至多有(  A  

5、 )個結(jié)點(diǎn)。 A.16       B.32          C.31           D.1010.設(shè)有5 000個無序的元素，希望用最快的速度挑選出其中前50個最大的元素，最好選用(  C   )法。 A. 冒泡排序      &

6、#160;        B.快速排序C.堆排序   D.基數(shù)排序11、線性表采用鏈?zhǔn)酱鎯r，其地址(D) 。A、必須是連續(xù)的； B、部分地址必須是連續(xù)的； C、一定是不連續(xù)的； D、連續(xù)與否均可以。12、用鏈表表示線性表的優(yōu)點(diǎn)是 （C）。A、便于隨機(jī)存取B、花費(fèi)的存儲空間較順序存儲少C、便于插入和刪除D、數(shù)據(jù)元素的物理順序與邏輯順序相同13、 某鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用(D)存儲方式最節(jié)省運(yùn)算時間。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、帶頭結(jié)點(diǎn)的雙循環(huán)

7、鏈表14、 一個向量(一種順序表)第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是_B_。(易)A、110 B、108 C、100 D、12015、 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_A_。A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! = NULL;16、 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是_B_。A、head = = NULL; B、head->next = = NULL;C、head->next = = head; D、head! =

8、NULL;17、 在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行_B_。A、s->next=p; p->next=s; B、s->next=p->next; p->next=s;C、s->next=p->next; p=s; D、p->next=s; s->next=p; 18、 在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行_C_。A、s->next=p->next; p->next=s; B、p->next=s->next; s->ne

9、xt=p;C、q->next=s; s->next=p; D、p->next=s; s->next=q;19、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足_C_。A、 p->next= =NULL B、 p= =NULLC、 p->next= =head D、 p= =head 20、在一個單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_A_。A、p->next= p->next->next； B、 p= p->next; p->next= p->next->next；C、p->next= p->ne

10、xt; D、p= p->next->next；21、 判定一個循環(huán)隊(duì)列QU（最多元素為m, m= =Maxsize-1）為滿隊(duì)列的條件是_A_。A、(rear- front)+ Maxsize)% Maxsize = =mB、rear-front-1= =m C、front= =rear D、front= = rear+122、 循環(huán)隊(duì)列用數(shù)組A0，m-1存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊(duì)列中的元素個數(shù)是_A_。A、 (rear-front+m)%m B、 rear-front+1C、 rear-front-1 D、 rear-front23、 棧和隊(duì)

11、列的共同點(diǎn)是_C_。A、 都是先進(jìn)后出 B、 都是先進(jìn)先出C、 只允許在端點(diǎn)處插入和刪除元素 D、 沒有共同點(diǎn)24、棧操作的原則是(B) A、 先進(jìn)先出 B、 后進(jìn)先出 C、 只能進(jìn)行插入 D、 只能進(jìn)行刪除25、在順序棧中，判斷棧s為空的條件是(D) A、t.base = NULL B、st.top = st.stacksizeC、st.top-st.base>= st.stacksize D、st.top = st.base26、在順序棧中，判斷棧s滿的條件是(C) A、 st.base = NULL B、 st.top = st.stacksizeC、 st.top-st.base

12、>= st.stacksize D、 st.top = st.base27、 串的長度是(C)。(易)A、串中不同字母的個數(shù) B、 串中不同字符的個數(shù) C、串中所含的字符的個數(shù) D、 串中所含字符的個數(shù)，且大于028、以下敘述中正確的是 A 。A、串是一種特殊的線性表B、串的長度必須大于零C、串中無素只能是字母D、空串就是空白串29、串是一中特殊的線性表，其特殊性體現(xiàn)在 B_。A、 可以順序存儲 B、 數(shù)據(jù)元素是一個字符C、 可以鏈接存儲 D、 數(shù)據(jù)元素可以是多個字符30、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_B_。A、連接 B、模式匹配 C、求子串 D、求串長二、名詞解

13、釋：1、數(shù)據(jù) 2、數(shù)據(jù)元素 3、數(shù)據(jù)對象 4、數(shù)據(jù)結(jié)構(gòu) 5、數(shù)據(jù)類型 6、算法7、壓縮存儲8、特殊矩陣 9、稀疏矩陣 10、結(jié)點(diǎn)的度 11、葉結(jié)點(diǎn) 12、 分支結(jié)點(diǎn)13、雙親結(jié)點(diǎn) 14、無向圖中頂點(diǎn)的度 15、有向圖中頂點(diǎn)的度1、數(shù)據(jù)是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序處理的符號的總稱。2、數(shù)據(jù)元素數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常做為一個整體進(jìn)行考慮和處理。3、數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合。4、數(shù)據(jù)結(jié)構(gòu)：相互具有一種或多種關(guān)系的數(shù)據(jù)元素的集合。5、數(shù)據(jù)類型：是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個數(shù)據(jù)上的一組運(yùn)算，是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的概念。6、算

14、法：對特定問題求解步驟的一種描述，是有限指令的集合。7、壓縮存儲：為多個值相同的元分配一個存儲空間，對零元不分配存儲空間。8、特殊矩陣：值相同的元素或者是零元素分布的有規(guī)律則稱為特殊矩陣。9、稀疏矩陣：在一個m*n的矩陣中，有t個非0元，其稀疏因子為t/(m*n)，如果稀疏因子小于0.05就稱為稀疏矩陣。10、所謂結(jié)點(diǎn)的“度”，是指樹中一個結(jié)點(diǎn)擁有的子樹數(shù)目。因此，結(jié)點(diǎn)的度也就是該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的個數(shù)。11、樹中度為0的結(jié)點(diǎn)被稱為葉結(jié)點(diǎn)。葉結(jié)點(diǎn)也就是終端結(jié)點(diǎn)。12、樹中度大于0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或非終端結(jié)點(diǎn)。13、在樹中，把一個結(jié)點(diǎn)稱作是它所有后繼結(jié)點(diǎn)的雙親結(jié)點(diǎn)。雙親結(jié)點(diǎn)有時也被稱作父結(jié)點(diǎn)。

15、14、在無向圖中頂點(diǎn)vi的“度”，是指與它相鄰接的頂點(diǎn)的個數(shù)。15、在有向圖中一個頂點(diǎn)vi的度是指它的入度與出度之和。三、填空題1、下面程序段的時間復(fù)雜度是o(_m*n)_。 O(m*n) for (i=0;i<n;i+)for (j=0;j<m;j+)aij=0;2、下面程序段的時間復(fù)雜度是_o(n)_。O() i=s=0；while(s<n) i+; /* i=i+1 */ s+=i;/* s=s+i */3、下面程序段的時間復(fù)雜度是_o(n2)_。O() s=0;for (i=0;i<n;i+)for (j=0;j<n;j+)s+=bij;sum=s;5、數(shù)

16、據(jù)元素可以由若干（數(shù)據(jù)項(xiàng)）組成，（數(shù)據(jù)元素）是數(shù)據(jù)的基本單位，（數(shù)據(jù)項(xiàng)）是數(shù)據(jù)的最小單位。(易) 6、數(shù)據(jù)結(jié)構(gòu)分為兩部分，即（邏輯）結(jié)構(gòu)和（物理）結(jié)構(gòu)。7、數(shù)據(jù)的存儲方式分為(順序)存儲和(鏈?zhǔn)?存儲。 8、順序存儲是一種(隨機(jī)存取)的存儲方式，是用一組(連續(xù))的存儲空間存儲數(shù)據(jù)，而鏈?zhǔn)酱鎯κ怯靡唤M(任意)的存儲空間存儲數(shù)據(jù)。(易) 9、 有一棵樹如圖6、5所示，回答下面的問題： 這棵樹的根結(jié)點(diǎn)是_A_； 這棵樹的葉子結(jié)點(diǎn)是_EFGIJKLN_； 結(jié)點(diǎn)D的度是_2_； 這棵樹的度是_4_； 這棵樹的深度是_5_；圖6.5 一棵樹 結(jié)點(diǎn)H的子女是_LMN_； 結(jié)點(diǎn)H的雙親結(jié)點(diǎn)是_C_；(8)結(jié)點(diǎn)

17、N的祖先是_ACHM_。10、一個圖的(鄰接矩陣)表示法是唯一的，而(鄰接表)表示法是不唯一的。11、有向圖中的結(jié)點(diǎn)前驅(qū)后繼關(guān)系的特征是(一個結(jié)點(diǎn)可能有若干個前驅(qū)，也可能有若干個后繼)。12、二叉樹通常有（順序 ）存儲結(jié)構(gòu)和（鏈?zhǔn)剑┐鎯Y(jié)構(gòu)。13、二叉樹有不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其中最常用的是（二叉鏈表）與（三叉鏈表）。14、線索二叉樹的左線索指向其（某種遍歷序列的直接前驅(qū)結(jié)點(diǎn)），右線索指向其（某種遍歷序列的直接后繼結(jié)點(diǎn)）。15、遍歷一棵二叉樹包括訪問（根結(jié)點(diǎn)）、遍歷（左子樹）和遍歷（右子樹）三個方面。 16、在二叉樹中，某一結(jié)點(diǎn)x在第L層，x若有雙親，其雙親應(yīng)在（L-1 ）層；若有孩子，其孩子應(yīng)

18、在（L+1）層。17、 二維數(shù)組A1020510采用行序?yàn)橹鞣绞酱鎯?，每個元素占4個存儲單元，并且A105的存儲地址是1000，則A189的地址是（1208）。18、在一個m*n的矩陣中，若a00是第一個元素，則aij是第（i*n+j ）個元素。19、在線性表L=(a1,a2,an)中，L稱為線性表的(名字)，n稱為線性表的(長度)。20、在雙向鏈表中，若結(jié)點(diǎn)p是結(jié)點(diǎn)q的前驅(qū)，現(xiàn)要刪除結(jié)點(diǎn)q，需要完成的操作是(p.next=q.next)；(q.next.prior=q.prior)；21、空串是（零個字符的串），其長度等于（零）。22、已知圖G的鄰接表如圖7.4所示，其從頂點(diǎn)v1出發(fā)的深度有

19、限搜索序列為(v1,v2,v3,v6,v5, v4)，其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為(v1,v2,v5,v4,v3, v6)。v1v3v2v4v5v6v2v5v4v3v5v6v4v6v3圖7.4 圖G的鄰接表23、 對n個元素的序列進(jìn)行起泡排序時，最少的比較次數(shù)是（n-1）。四、 判斷題1、線性表的邏輯順序與存儲順序總是一致的。×2、順序存儲的線性表可以按序號隨機(jī)存取。3、順序表的插入和刪除一個數(shù)據(jù)元素，每次操作平均只有近一半的元素需要移動。4、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象。5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相

20、鄰的兩個元素在物理位置上并不一定緊鄰。×6、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。7、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。×8、在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時，移動元素的個數(shù)與該元素的位置有關(guān)。9、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。10、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲結(jié)構(gòu)。(易) ×11、線性表中，每一個元素均存在前驅(qū)。×12、線性表中，每一個元素均存在后繼。×13、線性表中，存在唯一一個被稱為第一元素的元素。14、線性表

21、中，存在唯一一個被稱為最后一個元素的元素。15、線性結(jié)構(gòu)是一種一對一的結(jié)構(gòu)。1、棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)2、帶頭結(jié)點(diǎn)的單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的頭結(jié)點(diǎn)，尾指針R指向隊(duì)列的最后一個結(jié)點(diǎn)。×1、空串是由空白字符組成的串×2、串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲單元存儲串值的字符序列，按照預(yù)定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。3、串的堆分配存儲表示是用一組地址連續(xù)的存儲單元存儲串值的字符序列，但它們的存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的。4、如果一個串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。×5、串是由有限個

22、字符構(gòu)成的連續(xù)序列，串長度為串中字符的個數(shù)，子串是主串中字符構(gòu)成的有限序列。×6、廣義表的表頭一定是列表。×7、廣義表的表尾一定是列表。8、空串的長度為零。9、廣義表的元素即可以是原子，也可以是子表。10、廣義表中的子表與串中的子串的含義一樣。×1、二叉樹中每個結(jié)點(diǎn)有兩個子女結(jié)點(diǎn)，而對一般的樹則無此限制，因此二叉樹是樹的特殊情形。×2、二叉樹中不存在度大于2的結(jié)點(diǎn)，當(dāng)某個結(jié)點(diǎn)只有一棵子樹時無所謂左、右子樹之分。×3、當(dāng)k1時，高度為k的二叉樹至多有2k-1個結(jié)點(diǎn)。×4、完全二叉樹的某結(jié)點(diǎn)若無左孩子，則它必是葉結(jié)點(diǎn)。5、若有一個結(jié)點(diǎn)是某

23、二叉樹子樹的中序遍歷序列中的最后一個結(jié)點(diǎn)，則它必是該子樹的前序遍歷序列中的最后一個結(jié)點(diǎn)。×6、存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果相同。7、中序線索二叉樹的優(yōu)點(diǎn)之一是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。8、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點(diǎn)沒有左子樹。×9、由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。10、在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹。×11、在哈夫曼編碼中，當(dāng)兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應(yīng)作特殊處理。×12、霍夫曼樹一定是滿二叉樹。×五、簡答題：1、什么是算法，其基本性質(zhì)是什么？

24、1、算法是對特定問題求解步驟的一種描述，是有限指令的集合。其基本性質(zhì)如下：1)有窮性：算法對任意合法的輸入均能在有限時間、有限步驟后完成。2)確定性：算法的每一步驟的含義都是唯一、確定的，對于相同的輸入均能得到相同的輸出。3)可行性：算法的每一個步驟和指令都應(yīng)在已實(shí)現(xiàn)的算法的基礎(chǔ)上完成。4)輸入：任一個算法必須有0個或多個輸入。5)輸出：任一個算法必須有1個或多個輸出。2、算法的要求是什么？1)正確性：算法能正確描述待求解問題的需求，沒有邏輯錯誤，據(jù)此算法書寫的程序，對于任何合法的輸入，都有得到正確的、說明需求的結(jié)果。2)可讀性：算法應(yīng)簡潔、明晰，易于閱讀和理解，便于算法的移植和交流，有利于增

25、加算法的生命力。3)健壯性：當(dāng)輸入的數(shù)據(jù)非法時，算法要能作出適當(dāng)?shù)奶幚?，不會產(chǎn)生難以預(yù)料的結(jié)果。4)高效率性：一般來說，對同一問題的多種算法，首先選擇執(zhí)行時間相對較短、存儲空間相對較少的算法，然后考慮易于實(shí)現(xiàn)的算法。3、結(jié)構(gòu)共分幾類？其各自的性質(zhì)是什么？結(jié)構(gòu)共分為四類，分別為：1)集合：所有元素除共在同一集合外，沒有其他關(guān)系。2)線性結(jié)構(gòu)：元素間是一對一的關(guān)系。3)樹型結(jié)構(gòu)：元素間是一對多的關(guān)系。4)圖型結(jié)構(gòu)：元素間是多對多的關(guān)系。4、請寫出下列廣義表的表長、表頭、表尾。(1) A=( ) (2) B=(e) (3) C=(a,b,(c,d,e) (4) D=(a,D)答案：(1) 表長為0，

26、表頭為( )，表尾為（） (2) 表長為1，表頭為e，表尾為（） (3) 表長為3，表頭為a，表尾為（b,(c,d,e)） (4) 表長為2，表頭為a，表尾為（D）5、試列出圖7.8中三種拓?fù)渑判蛐蛄小?152364 152634 1562346、具有3個結(jié)點(diǎn)的二叉樹有幾種形態(tài)，分別為什么？(易)答案：6、具有3個結(jié)點(diǎn)的二叉樹有五種形態(tài)，如圖所示：7、將左圖中的森林轉(zhuǎn)化成二叉樹(中)答案：7、轉(zhuǎn)化成的二叉樹如圖：8.畫出圖用鏈表實(shí)現(xiàn)樹的孩子表示法 答案：8、六、算法設(shè)計(jì)題：1、試寫一算法，求隨機(jī)輸入的三個整數(shù)的最大值。int max(int x,int y,int z) int t;t=x&g

27、t;y?x:y;t=t>z?t:z;return t;2、計(jì)算s=1-2!+3!-.+10!。答案：#include "stdio.h"main() int i,t=1; long p=1,s=0; for(i=1;i<=10;i+) p*=i; s+=t*p; t=-t; printf("%ldn",s);3、 百錢百雞問題。main()int x,y,z; for(x=1;x<20;x+) for(y=1;y<33;y+) z=100-x-y; if(100=5*x+3*y+z/3.0) printf(“%d,%d,%dn”,x,y,z); 4編寫一個程序，要求有鍵盤輸入三個數(shù)，計(jì)算以這三個數(shù)為邊長的三角形的面積(假定輸入的邊長是有效的)。答案：1、#include “math.h” * * * * main() float a,b,c,p,s;scanf(“%f%f%f”,&a,&b,&c);p=(a+b+c)/2;s=s