大數(shù)據(jù)結(jié)構(gòu)精彩試題及問題詳解免費(fèi)

1、實(shí)用文檔 文案大全 數(shù)據(jù)結(jié)構(gòu)試卷（十一） 一、選擇題(30分) 1設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有（ ）條邊。 (A) n (B) n-1 (C) 2n (D) 2n-1 3設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ ）。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40

2、，60，85，55，80 4（ ）二叉排序樹可以得到一個(gè)從小到大的有序序列。 (A) 先序遍歷 (B) 中序遍歷 (C) 后序遍歷 (D) 層次遍歷 5設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（ ）。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6程序段s=i=0；do i=i+1； s=s+i；while(inext=0 (C) head-next=head (D) head!=0 8設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（ ）。 (A) 20 (B) 256 (C) 512 (D) 1024 9設(shè)

3、一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（ ）。 (A) 1 (B) 2 (C) 3 (D) 4 10.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（ ）。 (A) top=top+1; (B) top=top-1; (C) top-next=top; (D) top=top-next; 二、判斷題(20分) 1不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（ ） 2當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ） 3設(shè)某堆中有n個(gè)

4、結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ ） 4完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（ ） 5哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（ ） 6對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（ ） 7先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。（ ） 8由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ） 9線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ ） 10.帶權(quán)無向圖的最小生成樹是唯一的。（ ） 三、填空題(30分) 1. 1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_=p；s

5、-right=p-right；_=s； p-right-left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。 2. 2. 設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有_條有向條；設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中共有_條無向邊。 3. 3. 設(shè)關(guān)鍵字序列為(Kl，K2，Kn)，則用篩選法建初始堆必須從第_個(gè)元素開始進(jìn)行篩選。 實(shí)用文檔 文案大全 4. 4. 解決散列表沖突的兩種方法是_和_。 5. 5. 設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有_個(gè)。 6. 6. 高度為h的完全二叉樹中最少有_個(gè)結(jié)點(diǎn)，最多有_個(gè)結(jié)點(diǎn)。 7

6、. 7. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是_。 8. 8. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡(jiǎn)單選擇排序結(jié)束后的結(jié)果的是_。 9. 9. 設(shè)一棵二叉樹的前序序列為ABC，則有_種不同的二叉樹可以得到這種序列。 10. 10. 下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 struct record int key;datatype others; void quickpass(struct record r, int s, int t, int &i) int j=t

7、; struct record x=rs; i=s; while(ij) while (ix.key) j=j-1; if (ij) ri=rj;i=i+1; while (_) i=i+1; if (ileft=p，p-right 2. 2. n(n-1)，n(n-1)/2 3. 3. n/2 4. 4. 開放定址法，鏈地址法 5. 5. 14 6. 6. 2h-1，2h-1 7. 7. (12，24，35，27，18，26) 8. 8. (12，18，24，27，35，26) 9. 9. 5 10. 10. ij & ri.keynext=0) return; for(q=head; q!

8、=0;q=q-next) min=q-data; s=q; for(p=q-next; p!=0;p=p-next) if(minp-data)min=p-data; s=p; if(s!=q)t=s-data; s-data=q-data; q-data=t; 2. 2. 設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。 void substring(char s , long start, long count, char t ) long i,j,length=strlen(s); if (startlength) printf(The copy position is wrong); else i

9、f (start+count-1length) printf(Too characters to be copied); else for(i=start-1,j=0; ikey=x) return; else if (bt-keyx) level(bt-lchild,x); else level(bt-rchild,x); 數(shù)據(jù)結(jié)構(gòu)試卷（十二） 一、選擇題(30分) 1. 1. 字符串的長(zhǎng)度是指（ ）。 (A) 串中不同字符的個(gè)數(shù) (B) 串中不同字母的個(gè)數(shù) (C) 串中所含字符的個(gè)數(shù) (D) 串中不同數(shù)字的個(gè)數(shù) 2. 2. 建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（ ） (A) O(n)

10、 (B) O(1) (C) O(n2) (D) O(log2n) 3. 3. 兩個(gè)字符串相等的充要條件是（ ）。 (A) 兩個(gè)字符串的長(zhǎng)度相等 (B) 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等 (C) 同時(shí)具備(A)和(B)兩個(gè)條件 (D) 以上答案都不對(duì) 4. 4. 設(shè)某散列表的長(zhǎng)度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（ ）。 (A) 99 (B) 97 (C) 91 (D) 93 5. 5. 在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（ ）。 (A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2) 6. 6. 設(shè)一個(gè)順序有序表A1

11、:14中有14個(gè)元素，則采用二分法查找元素A4的過程中比較元素的順序?yàn)? )。 (A) A1，A2，A3，A4 (B) A1，A14，A7，A4 (C) A7，A3，A5，A4 (D) A7，A5 ，A3，A4 7. 7. 設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（ ）。 (A) 8 (B) 7 (C) 6 (D) 5 8. 8. 設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（ ）個(gè)度數(shù)為0的結(jié)點(diǎn)。 (A) 5 (B) 6 (C) 7 (D) 8 實(shí)用文檔 文案大全 9. 9. 設(shè)無向圖G中的邊的集合E=(a，b)，(a，e)，(a

12、，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（ ）。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc 10. 10. 隊(duì)列是一種（ ）的線性表。 (A) 先進(jìn)先出 (B) 先進(jìn)后出 (C) 只能插入 (D) 只能刪除 二、判斷題(20分) 1. 1. 如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（ ） 2. 2. 設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（ ） 3. 3. 分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵

13、字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（ ） 4. 4. 二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（ ） 5. 5. 向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（ ） 6. 6. 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（ ） 7. 7. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（ ） 8. 8. 不論線性表采用順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（ ） 9. 9. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。（ ） 10. 10. 稀疏矩陣的壓縮存儲(chǔ)可以

14、用一個(gè)三元組表來表示稀疏矩陣中的非0元素。（ ） 三、填空題(30分) 1 1 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_。 2 2 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct nodeint data;struct node *lchild;struct node *rchild;bitree; void bstinsert(bitree *&t,int k) if (t=0 ) _;t-data=k;t-lchild=t-rchild=0;

15、else if (t-datak) bstinsert(t-lchild,k);else_; 3 3 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s-next=p-next; _;。 4 4 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_和head=_（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。 5 5 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_。 6 6 完全二叉樹中第5層上最少有_個(gè)結(jié)點(diǎn)，最多有_

16、個(gè)結(jié)點(diǎn)。 7 7 設(shè)有向圖中不存在有向邊，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素Aij的值等于_。 8 8 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_。 9 9 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹上有_條邊。 10 10 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與_相互交換即可。 四、算法設(shè)計(jì)題(20分) 1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。 2. 2. 設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。 實(shí)用文檔 文案大

17、全 數(shù)據(jù)結(jié)構(gòu)試卷（12）參考答案 一、選擇題 1C 2C 3C 4B 5B 6C 7B 8C 9A 10A 二、判斷題 1對(duì) 2錯(cuò) 3對(duì) 4錯(cuò) 5錯(cuò) 6對(duì) 7對(duì) 8對(duì) 9對(duì) 10對(duì) 三、填空題 1. 1. (49，13，27，50，76，38，65，97) 2. 2. t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k) 3. 3. p-next=s 4. 4. head-rlink，p-llink 5. 5. CABD 6. 6. 1，16 7. 7. 0 8. 8. (13，27，38，50，76，49，65，97) 9. 9. n

18、-1 10. 10. 50 四、算法設(shè)計(jì)題 1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。 void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count); 2. 2. 設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。 typedef struct int vertexm; int edgemm;gadjmatrix; typedef struct node1int info;int adjvertex; struc

19、t node1 *nextarc;glinklistnode; typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 ) int i,j; glinklistnode *p; for(i=0;i=n-1;i+) g2i.firstarc=0; for(i=0;i=n-1;i+) for(j=0;jadjvertex=j; p-nextarc=gi.firstarc; gi.firstarc=

20、p; p=(glinklistnode *)malloc(sizeof(glinklistnode);p-adjvertex=i; p-nextarc=gj.firstarc; gj.firstarc=p; 數(shù)據(jù)結(jié)構(gòu)試卷（13） 一、選擇題(30分) 1下列程序段的時(shí)間復(fù)雜度為（ ）。 for(i=0； im； i+) for(j=0； jt； j+) cij=0； 實(shí)用文檔 文案大全 for(i=0； im； i+) for(j=0； jt； j+) for(k=0； kright=s； s-left=p； p-right-left=s； s-right=p-right； (B) s-lef

21、t=p；s-right=p-right；p-right=s； p-right-left=s； (C) p-right=s； p-right-left=s； s-left=p； s-right=p-right； (D) s-left=p；s-right=p-right；p-right-left=s； p-right=s； 6下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（ ）。 (A) 快速排序 (B) 堆排序 (C) 歸并排序 (D) 冒泡排序 7設(shè)輸入序列1、2、3、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出元素是（ ）。 (A) n-i (B) n-1-i (C)

22、 n+l -i (D) 不能確定 8設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素?cái)?shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù) 9設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ ）個(gè)。 (A) 4 (B) 5 (C) 6 (D) 7 10.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ ）條邊。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 11.設(shè)順序表

23、的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（ ）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2 12.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（ ）次比較。 (A) 1 (B) 2 (C) 3 (D) 4 13.設(shè)順序線性表的長(zhǎng)度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長(zhǎng)度為（ ）。 (A) 6 (B) 11 (C) 5 (D) 6.5 14.設(shè)有向無環(huán)圖G中的有向邊集合E=，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?）。 (A) 1，2，3，4 (B) 2，3，4，1 (

24、C) 1，4，2，3 (D) 1，2，4，3 15.設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ ）。 (A) 4 (B) 5 (C) 6 (D) 7 二、填空題(30分) 1 1 設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為： 1) s-next=_；2) p-next=s；3) t=p-data； 4) p-data=_；5) s-data=t； 2 2 設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，則該二叉樹中有_個(gè)葉子結(jié)點(diǎn)。 3 3 設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指

25、針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲(chǔ)_隊(duì)列元素。 實(shí)用文檔 文案大全 4 4 對(duì)一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_，在整個(gè)排序過程中最多需要進(jìn)行_趟排序才可以完成。 5 5 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_排序，如果從節(jié)省存儲(chǔ)空間的角度來考慮則最好選擇_排序。 6 6 設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長(zhǎng)度是_。 7 7 設(shè)一

26、棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為_。 8 8 設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為_。 9 9 設(shè)一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_。 10 10 設(shè)無向圖G（如右圖所示），則其最小生成樹上所有邊的權(quán)值之和為_。 三、判斷題(20分) 1 1 有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。( ) 2 2 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。( ) 3 3

27、 子串“ABC”在主串“AABCABCD”中的位置為2。( ) 4 4 若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( ) 5 5 希爾排序算法的時(shí)間復(fù)雜度為O(n2)。( ) 6 6 用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( ) 7 7 中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。( ) 8 8 入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。( ) 9 9 順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。（ ） 1010堆是完全二叉樹，完全二叉樹不一定是堆。（ ） 五、算法

28、設(shè)計(jì)題(20分) 1 1 設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。 2 2 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。 3 3 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。 數(shù)據(jù)結(jié)構(gòu)試卷（13）參考答案 一、選擇題 1A 2A 3A 4C 5D 6D 7C 8B 9C 10A 11C 12C 13D 14A 15A 二、填空題 1. 1. p-next，s-data 2. 2. 50 3. 3. m-1 4. 4. 6，8 5. 5. 快速，堆 6. 6. 19/7 實(shí)用文檔 文案大全 7. 7. CBDA 8. 8. 6 9. 9. (24，65，33，80，70，56，48) 10. 10. 8 三、

29、判斷題 1錯(cuò) 2對(duì) 3對(duì) 4對(duì) 5錯(cuò) 6錯(cuò) 7對(duì) 8對(duì) 9錯(cuò) 10對(duì) 四、算法設(shè)計(jì)題 1 1 設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。 void sum(bitree *bt,int &s) if(bt!=0) s=s+bt-data; sum(bt-lchild,s); sum(bt-rchild,s); 2 2 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。 void quickpass(int r, int s, int t) int i=s,j=t,x=rs; while(ij) while (ij & rj%2=0) j=j-1; if (ij) ri=rj;i=i+1; while (ij

30、& ri%2=1) i=i+1; if (inext=0) return(1);else for(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) return(0); return(1); 數(shù)據(jù)結(jié)構(gòu)試卷（十四） 一、選擇題(24分) 1下列程序段的時(shí)間復(fù)雜度為（ ）。 i=0，s=0； while (snext=p-next；p-next=-s； (B) q-next=s； s-next=p； (C) p-next=s-next；s-next=p； (D) p-next=s；s-next=q； 4設(shè)輸入序列為1、2、3、4、5、6

31、，則通過棧的作用后可以得到的輸出序列為（ ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 5設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線），按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A54地址與A00的地址之差為（ ）。 實(shí)用文檔 文案大全 (A) 10 (B) 19 (C) 28 (D) 55 6設(shè)一棵m叉樹中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有（ ）個(gè)葉子結(jié)點(diǎn)。 (A) ?miiNi1)1( (B) ?miiN1

32、(C) ?miiN2 (D) ?miiNi2)1(1 7. 二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ ）根結(jié)點(diǎn)的值。 (A) (C) = (D) != 8. 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長(zhǎng)度為（ ）。 (A) 129 (B) 219 (C) 189 (D) 229 9. 設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（ ）次線性探測(cè)。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2 10.設(shè)某棵二叉樹中只有度數(shù)為0和度

33、數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（ ）個(gè)結(jié)點(diǎn)。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 11.設(shè)一組初始記錄關(guān)鍵字的長(zhǎng)度為8，則最多經(jīng)過（ ）趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9 12.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（ ）。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y (C) A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X (D) H，C，Q，P，A，M

34、，S，R，D，F(xiàn)，X，Y 二、填空題(48分，其中最后兩小題各6分) 1. 1. 設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_次，至多需要比較_次。 2. 2. 快速排序算法的平均時(shí)間復(fù)雜度為_，直接插入排序算法的平均時(shí)間復(fù)雜度為_。 3. 3. 設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_次。 4. 4. 設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_個(gè)。 5. 5. 設(shè)一棵m叉樹脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其存儲(chǔ)結(jié)構(gòu)，則該樹中有_個(gè)空指針域。 6. 6. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的語句

35、序列為： q=p-next；p-data=q-data；p-next=_；feee(q)； 7. 7. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：_、_和_。 8. 8. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為_；用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_。 9. 9. 設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k % 7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長(zhǎng)度是_。 10. 10. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10

36、)，則第3趟冒泡排序結(jié)束后的結(jié)果為_。 11. 11. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡(jiǎn)單選擇排序后的結(jié)果為_。 12. 12. 設(shè)有向圖G中的有向邊的集合E=，則該圖的一個(gè)拓?fù)湫蛄袨開。 實(shí)用文檔 文案大全 13. 13. 下面程序段的功能是建立二叉樹的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct nodeint data;struct node *lchild;_;bitree; void createbitree(bitree *&bt) scanf(“%c”,&ch); if(ch=#) _;else bt=(bitre

37、e*)malloc(sizeof(bitree); bt-data=ch; _;createbitree(bt-rchild); 14. 14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct node int data; struct node *next; lklist; void lklistcreate(_ *&head ) for (i=1;idata);p-next=0; if(i=1)head=q=p;else q-next=p;_; 三、算法設(shè)計(jì)題(22分) 1 1 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。 2 2

38、 設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。 3 3 設(shè)關(guān)鍵字序列(k1，k2，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，kn-1，x)調(diào)整為堆。 數(shù)據(jù)結(jié)構(gòu)試卷（14）參考答案 一、選擇題 1A 2D 3B 4B 5B 6D 7A 8D 9D 10C 11B 12D 二、填空題 1. 1. 4，10 2. 2. O(nlog2n)，O(n2) 3. 3. n 4. 4. 1，2 5. 5. n(m-1)+1 6. 6. q-next 7. 7. 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu) 8. 8. O(n2)， O(n+e) 9. 9. 8/3 10. 10. (38，13，27，10，65，76，97

39、) 11. 11. (10，13，27，76，65，97，38) 12. 12. 124653 13. 13. struct node *rchild，bt=0，createbitree(bt-lchild) 14. 14. lklist，q=p 三、算法設(shè)計(jì)題 1. 1. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0; while(ha!=0 & hb!=0) 實(shí)用文檔 文案大全 if(ha-datadata)if(s=0) hc=s=ha; else s-next=

40、ha; s=ha;ha=ha-next; else if(s=0) hc=s=hb; else s-next=hb; s=hb;hb=hb-next; if(ha=0) s-next=hb; else s-next=ha; 2. 2. 設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。 bitree *bstsearch1(bitree *t, int key) bitree *p=t; while(p!=0) if (p-key=key) return(p);else if (p-keykey)p=p-lchild; else p=p-rchild; return(0); 3. 3. 設(shè)關(guān)鍵字序列(k1，

41、k2，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，kn-1，x)調(diào)整為堆。 void adjustheap(int r ,int n) int j=n,i=j/2,temp=rj-1; while (i=1) if (temp=ri-1)break; elserj-1=ri-1; j=i; i=i/2; rj-1=temp; 數(shù)據(jù)結(jié)構(gòu)（十五） 一、 單選題（每題 2 分，共20分） 1. 1. 對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（B ）方面的內(nèi)容。 A健壯性和可讀性 B并行性 C正確性 D時(shí)空復(fù)雜度 2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL; 3. 3. 對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) A.經(jīng)常需要隨機(jī)地存取元素 B.經(jīng)常需要進(jìn)行插入和刪除操作 C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間 D.表中元素的個(gè)數(shù)不變 4. 4. 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5. AOV網(wǎng)是一種（