2008年安徽工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題A卷-副本

1、2008年安徽工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題A卷一、單項(xiàng)選擇題1 .程序段 F0R(i=n-l;i>=0;i)F0R(j=l;j<=n;j+)IFAj>Aj+l與 Aj+1對(duì)換;其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是。A.0 (n) B.0(nlogn)C.0(nMD.0(n)2 .用鏈表表示線性表的優(yōu)點(diǎn)是oA.便于隨機(jī)存取B.花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少C.便于插入和刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同3 .帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A. head二二NULLB head->next=NULLC. head->next=headD.hea

2、d!二NULL4 .在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是一。A. p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B. p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C. s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D. s->prior=p;s->next=p->next

3、;p->next->prior=s;p->next=s;5 .棧應(yīng)用在 0A.遞歸調(diào)用B.子程序調(diào)用C .表達(dá)式求值D.A, B, C都對(duì)6 .設(shè)abcdef(a先進(jìn)棧)順序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許出棧操作，則下面得不到的序列為A. fedcbaB. bcafedC. dcefbaD. cabdef 注：序列 xyz 表示 x 先出棧;z 最后出棧。7 .若一個(gè)棧的輸入序列為1, 2, 3, 4, 5則輸出序列有 種可能。A. 14B. 120C. 60D. 428 .循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0. .m中，則入隊(duì)時(shí)隊(duì)尾的操作為。A. rear=rear+lB. rear=(re

4、ar+l)%(m-1)C. rear=(rear+1)%mD. rear=(rear+l)%(m+l)9 .在簡(jiǎn)單模式匹配中，當(dāng)模式串位j與主串位i的比較時(shí)，新一趟匹配開始，主串的位移公 式是。A. i=i+lB. i=j+lC. i=i-j+lD. i=i-j+210 .稀疏矩陣一般的壓縮方法是oA.二維數(shù)組和三維數(shù)組B.三元組和散列表C.三元組和十字鏈表D.散列和十字鏈表11 .若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B 1. (n(n+l)/2中，a00存放于數(shù)組Bl中，則在B中確定aij(i<j)的位置k的關(guān)系為一oA. i

5、*(i+l)/2+jB. j*(j+l)/2+iC. i*(i+l)/2+j+lD. j*(j+l)/2+i+l12 .設(shè)廣義表L=(a, b, c),則L的長(zhǎng)度和深度分別為一oA. 1 和 IB. 1 和 3C. 1 和 2D. 2 和 313 .有一個(gè)100*90的稀疏矩陣，非0元素有10個(gè)，設(shè)每個(gè)整型數(shù)占2字節(jié)，則用三元組表 示該矩陣時(shí)，所需的字節(jié)數(shù)是一0A. 60B. 66C. 18000D. 3314 .已知廣義表LS=(a, b, c), (d, e, f),運(yùn)用GetHead和GetTail函數(shù)取出LS中原子e的運(yùn)算是。A. GetHead(GetTaiKLS)B. B. Get

6、Head(GetTail(GetHead(GetTail(LS)C.GetTail(GetHead(LS)D. GetHead(GetTail(GetTai1(GetHead(LS)15.一棵三叉樹中，已知度為3的結(jié)點(diǎn)數(shù)等于度為2的結(jié)點(diǎn)數(shù)，且樹中葉子數(shù)為7,則度為2 的結(jié)點(diǎn)數(shù)目為 oA. 4B. 2C. 3D. 516.下面關(guān)于二叉樹的結(jié)論正確的是。A.二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)等于度為2的結(jié)點(diǎn)個(gè)數(shù)加1。B.二叉樹中結(jié)點(diǎn)個(gè)數(shù)必大于心C.完全二叉樹中，任何一個(gè)結(jié)點(diǎn)的度，或者為0,或者為2。D.二叉樹的度是217 .設(shè)X是樹T中的一個(gè)非根結(jié)點(diǎn)，B是T所對(duì)應(yīng)得二叉樹，在B中，X是其雙親的右孩子, 下

7、列結(jié)論正確的是OA.在樹T中，X是其雙親的第一個(gè)孩子。B.在樹T中，X一定無右邊兄弟。C.在樹T中，X一定是葉子結(jié)點(diǎn)。D.在樹T中，X 一定有左邊兄弟18 . 一棵有n個(gè)結(jié)點(diǎn)的k叉樹，樹中所有結(jié)點(diǎn)的度之和為 oA. n-lB. knC. nD. 2n19 .圖的廣度優(yōu)先搜索類似于樹的 次序遍歷。A.先根B.中根C.后根D.層次20 .欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧結(jié)構(gòu)，最佳方案是二叉樹采用 存儲(chǔ)結(jié)構(gòu)。A.三叉鏈表B.廣義表C.二叉鏈表D.順序21 . 一棵二叉樹滿足下列條件：對(duì)任一結(jié)點(diǎn)，若存在左、右子樹，則其值都小于它的左子樹 上所有結(jié)點(diǎn)的值，而大于右子樹上所有結(jié)點(diǎn)的值?，F(xiàn)

8、采用 遍歷方式就可以得到這棵二又樹上所有結(jié)點(diǎn)的遞減序列。A.先序B.中序C.后序D.層次22 .設(shè)給定權(quán)值的葉子總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為 oA.不確定 B. 2nC. 2n+lD. 2n-l23 .某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則此二叉樹一定是oA.空或只有一個(gè)結(jié)點(diǎn)B.完全二叉樹C.單支樹D.高度等于結(jié)點(diǎn)數(shù)24 .對(duì) 進(jìn)行相應(yīng)的遍歷仍需要棧的支持。A.先序線索樹B.中序線索樹C.后序線索樹D. A與B25 .具有7個(gè)頂點(diǎn)的有向圖至少應(yīng)有 條邊才能確保一個(gè)強(qiáng)連通圖。A. 6B. 7C. 8D. 9B26 .采用鄰接表存儲(chǔ)圖的深度優(yōu)先遍歷算法類似于樹的 oA.中根遍歷B.

9、先根遍歷C.后根遍歷D.層次遍歷27 .判斷有向圖是否存在回路，除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用。A.求關(guān)鍵路徑的方法B.求最短路徑的Di jkstra算法C.深度優(yōu)先遍歷算法D.廣度優(yōu)先遍歷算法28 .二叉排序樹的查找效率與二叉排序樹的 有關(guān)，當(dāng)時(shí)，查找效率最低，其查找長(zhǎng)度為A.高度；結(jié)點(diǎn)太多B.結(jié)點(diǎn)的個(gè)數(shù)：完全二叉樹C.形狀；呈單叉樹D.結(jié)點(diǎn)的位置：結(jié)點(diǎn)的結(jié)構(gòu)太復(fù)雜29 .假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入哈希表中，至少要 進(jìn)行多少次探測(cè)°A. k-1 次 B. k 次 C. k+1 次 D. k (k+1) /2 次30. 4.若需在O(nlog

10、n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排 序方法是。A.快速排序B.堆排序C.直接插入排序D.歸并排序二、填空1 .數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)基本上有順序、索引和散列等四種。2 .在鏈表中進(jìn)行操作的效率比在順序存儲(chǔ)結(jié)構(gòu)中進(jìn)行相同操作的效率高。3 .廣義表的深度定義為廣義表中括號(hào)被嵌套的。4 .設(shè)一棵完全二叉樹葉子結(jié)點(diǎn)數(shù)為k,最后一層結(jié)點(diǎn)數(shù)>2,則該二叉樹的高度為。5 . 一棵樹按照左孩子一右兄弟表示法轉(zhuǎn)換成對(duì)應(yīng)的二叉樹，則該二叉樹中樹根結(jié)點(diǎn)肯定沒有 C6 .設(shè)圖 G=(V, E), V=1, 2, 3, 4, E= <1, 2>, <b 3>, &l

11、t;2, 4>, <3, 4>,從頂點(diǎn) 1 出發(fā)，對(duì)圖G進(jìn)行廣度優(yōu)先搜索的序列有 種。7 .在哈希查找中，裝填因子為若用m表示哈希表的長(zhǎng)度，n表示哈希存儲(chǔ)的元素個(gè)數(shù)， 則a等于 08 .在順序表(8,11,15, 19, 25, 26, 30, 33, 42,48, 50)中,用折半法查找關(guān)鍵字值20,需做的關(guān) 鍵字比較次數(shù)為 o9 .快速排序的遞歸算法在平均情況下的空間復(fù)雜度為。10 .設(shè)圖的頂點(diǎn)數(shù)為n,則求解最短路徑的Dijkstra算法的時(shí)間復(fù)雜度為。三、判斷1 .數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與具體實(shí)現(xiàn)有關(guān)。()2 .在鏈?zhǔn)酱鎯?chǔ)表中存取表中的數(shù)據(jù)元素時(shí)，不一定要按順序訪問。

12、()3 .鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。()4 .消除遞歸不一定需要使用棧。()5 .循環(huán)隊(duì)列只能通過鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)。()6 .一個(gè)廣義表的表尾總是一個(gè)表。07 .若一個(gè)葉子結(jié)點(diǎn)是某二叉樹中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，那么它也是該二叉樹的先序 遍歷序列的最后一個(gè)結(jié)點(diǎn)。08 .對(duì)一個(gè)無向連通圖進(jìn)行一次深度優(yōu)先搜索可以訪問圖中的所有頂點(diǎn)。（）9 .鄰接矩陣適用于稀疏圖（邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)的平方），鄰接表適用于稠密圖（邊數(shù)接近于頂 點(diǎn)數(shù)的平方）。010 .對(duì)二叉排序樹進(jìn)行先序遍歷得到的結(jié)點(diǎn)的值的序列是一個(gè)有序序列。（）四、應(yīng)用題1 .已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECB

13、HGFA,畫出這棵二叉樹。 并寫出其先序遍歷序列。（5分）2 .已知廣義表：B= （b, c）C二（a, （d, e, f）D二（B, 0E= （a, E）設(shè)廣義表原子節(jié)點(diǎn)和表節(jié)點(diǎn)的存儲(chǔ)映像如下圖所示（其中hp表示表頭指針，tp表示表尾指 針），請(qǐng)畫出廣義表B、C、D、E的存儲(chǔ)映像圖。（5分）tag-0data匕/1即tp原子結(jié)點(diǎn)表結(jié)點(diǎn)3 .已知一個(gè)文件中有5個(gè)字符a、b、c、d、e,各個(gè)字符的出現(xiàn)的次數(shù)依次分別是3、4、8、 10、16,試為這5個(gè)字符編碼，以節(jié)省存儲(chǔ)空間。（5分）4 .對(duì)于下圖所示的無向連通圖，請(qǐng)用Prim算法構(gòu)造其最小生成樹，設(shè)算法從圖中頂點(diǎn)1 開始處理。（5分。注：要求

14、寫出求解過程）165 .給出待排序序列的關(guān)鍵字序列為87, 52, 61, 27, 37, 45）,請(qǐng)寫出對(duì)該序列進(jìn)行堆排序的過 程（注：升序排序，寫出每趟排序的過程）. （5分）6 .請(qǐng)將下列計(jì)算二叉數(shù)深度的算法補(bǔ)充完整，每個(gè)空格一分。（5分） intBtreeDepth(BTreeNode*BT)(1)if (BT= =NULL) return (1) else(3)int depl, dep2:(2)(3)depl=dep2=C5)if (depl>dcp2) return (4)return )(5)7.已知完全二叉樹的第8層有7片葉子，請(qǐng)指出所有可能的情況下的葉 子數(shù)目，不需要

15、畫出圖形，文字說明即可.（5分）五、算法設(shè)計(jì)題1.已知帶頭節(jié)點(diǎn)的單鏈表L,寫一算法，刪除其中的重復(fù)結(jié)點(diǎn)（15分）。設(shè)單鏈表節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)定義如下：TypedefstructnodeDa t aType dat a; /*每個(gè)元素?cái)?shù)據(jù)信息*/structnode*next ;/*存放后繼元素的地址*/ /Lnode, *LinkList;2,奇偶交換排序算法如下所述：第一趟對(duì)所有下標(biāo)i為奇數(shù)的元素，將ai與ai+l比較, 第二趟對(duì)所有下標(biāo)i為偶數(shù)的元素，將ai與ai+l 比較，如則將二者交換：第三趟對(duì)奇數(shù)i,第四趟對(duì)偶數(shù)i,，重復(fù)上述處 理過程直到整個(gè)文件有序（10分）。（1）問此種排序算法的結(jié)束條件是什么？ （3分）（2）用C語言實(shí)現(xiàn)此算法。（7分）設(shè)待排序文件采用如下存儲(chǔ)結(jié)構(gòu)：WdefineMAXSIZElOOtypedefstruct