數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)習(xí)題答案嚴(yán)蔚敏李冬梅吳偉民23490數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

1、 第 1 章 緒論 習(xí)題 1．簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類型。 2．試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。 3．簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫(huà)出它們的關(guān)系圖。 4．存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？ 5．選擇題 （1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ） 。 A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C．線性結(jié)

2、構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) （2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（ ） 。 A．存儲(chǔ)結(jié)構(gòu) B．存儲(chǔ)實(shí)現(xiàn) C．邏輯結(jié)構(gòu) D．運(yùn)算實(shí)現(xiàn) （3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ） 。 A．?dāng)?shù)據(jù)具有同一特點(diǎn) B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致 C．每個(gè)數(shù)據(jù)元素都一樣 D．?dāng)?shù)

3、據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等 （4）以下說(shuō)法正確的是（ ） 。 A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位 B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu) （5）以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是（ ） 。 A．順序隊(duì)列 B. 鏈表 C. 有序表 D. 鏈棧 （6）以下數(shù)據(jù)結(jié)構(gòu)中， （ ）是非線性數(shù)據(jù)結(jié)構(gòu) A．樹(shù)

4、 B．字符串 C．隊(duì) D．棧 6．試分析下面各程序段的時(shí)間復(fù)雜度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i<n; i++) for (j=0; j<m; j++) a[i][j]=0; （3）s=0; for i=0; i<n; i++) 第 2 章 線性表

5、 1．選擇題 （1）一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 100，每個(gè)元素的長(zhǎng)度為 2，則第 5 個(gè)元素的地址是（ ） 。 A．110 B．108 C．100 D．120 （2）在 n 個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是 O(1)的操作是（ ） 。 A．訪問(wèn)第 i 個(gè)結(jié)點(diǎn)（1≤i≤n）和求第 i 個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n） B．在第 i 個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n

6、） C．刪除第 i 個(gè)結(jié)點(diǎn)（1≤i≤n） D．將 n 個(gè)結(jié)點(diǎn)從小到大排序 （3）向一個(gè)有 127 個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變， 平均要移動(dòng) 的元素個(gè)數(shù)為（ ） 。 A．8 B．63.5 C．63 D．7 （4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ ） 。 A．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B．只有一部分，存放結(jié)點(diǎn)值 C．只有一部分，存儲(chǔ)表示結(jié)點(diǎn)

7、間關(guān)系的指針 D．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù) （5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ） 。 A．必須是連續(xù)的 B．部分地址必須是連續(xù)的 C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以 （6）線性表Ｌ在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值 Ｂ．需不斷對(duì)Ｌ進(jìn)行刪除插入 C．Ｌ中含有大量的結(jié)點(diǎn) Ｄ．Ｌ中

8、結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 （7）單鏈表的存儲(chǔ)密度（ ） 。 A．大于 1 B．等于 1 C．小于 1 D．不能確定 （8）將兩個(gè)各有 n 個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（ ） 。 A．n B．2n-1 C．2n D．n-1 （9）在一個(gè)長(zhǎng)度為 n 的順序表中，在第 i 個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。

9、A．n-i B．n-i+1 C．n-i-1 D．i (10) 線性表L=(a1，a2,……an)，下列說(shuō)法正確的是（ ） 。 A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B．線性表中至少有一個(gè)元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。 (11) 若指定有 n 個(gè)元素的向量，則建立一個(gè)有序單鏈表的時(shí)間復(fù)雜