華北電力842數(shù)據(jù)結(jié)構(gòu)2013年真題

1、華北電力大學(xué)（北京）2013年攻讀碩士學(xué)位入學(xué)考試試題 考試科目： 數(shù)據(jù)結(jié)構(gòu) 試題編號(hào) 842 （注：答案必須寫在答題紙上，寫在試題上無(wú)效） 一、選擇題(30分)字符串的長(zhǎng)度是指（ ）。(A) 串中不同字符的個(gè)數(shù)(B) 串中不同字母的個(gè)數(shù)(C) 串中所含字符的個(gè)數(shù)(D) 串中不同數(shù)字的個(gè)數(shù)建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（ ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)兩個(gè)字符串相等的充要條件是（ ）。(A) 兩個(gè)字符串的長(zhǎng)度相等(B) 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等(C) 同時(shí)具備(A)和(B)兩個(gè)條件(D) 以上答案都不對(duì)設(shè)某散列表的長(zhǎng)度為100，

2、散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（ ）。(A) 99(B) 97(C) 91(D) 93在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（ ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2)設(shè)一個(gè)順序有序表A1:14中有14個(gè)元素，則采用二分法查找元素A4的過(guò)程中比較元素的順序?yàn)? )。(A) A1，A2，A3，A4(B) A1，A14，A7，A4(C) A7，A3，A5，A4(D) A7，A5 ，A3，A4設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（ ）。(A) 8(B) 7(C) 6(D) 5設(shè)一棵三叉樹中有2個(gè)度數(shù)為1

3、的結(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è)無(wú)向圖G中的邊的集合E=(a，b)，(a，e)，(a，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隊(duì)列是一種（ ）的線性表。(A) 先進(jìn)先出(B) 先進(jìn)后出(C) 只能插入(D) 只能刪除 二、填空題(48分)設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序

4、結(jié)束后的結(jié)果為_。下面程序段的功能是實(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;else if (t-datak) bstinsert(t-lchild,k);else_;設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列：s-n

5、ext=p-next; _;。設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_和head=_（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。設(shè)有向圖中不存在有向邊，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素Aij的值等于_。設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_。設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹上有_條邊。設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與_相互交換即可。三

6、、簡(jiǎn)答題（40分）1簡(jiǎn)述兩種主要的數(shù)據(jù)關(guān)系映像2描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)3簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）void algo3(Queue &Q) Stack S; int d;InitStack(S);while (!QueueEmpty(Q) DeQueue(Q, d); Push(S, d);while (!StackEmpty(S) Pop(S, d); EnQueue(Q, d);4請(qǐng)對(duì)下圖所示二叉樹進(jìn)行后序線索化，為每個(gè)空指針建立相應(yīng)的前驅(qū)或后繼線索。DDHCGFEAB5利用串的基本操作編寫對(duì)串求逆的遞歸算法。int i=1,n=StrLength(s);void switch(si,sn-i+1)chars t;t=si;si=sn-i+1;sn-i+1