《數(shù)據(jù)結(jié)構(gòu)》期末試卷(A)

1、數(shù)據(jù)結(jié)構(gòu)期末考試試卷（A）題號(hào)一二二四五總分得分室教1場(chǎng)考問(wèn)時(shí)試考號(hào)學(xué)名姓級(jí)班得分評(píng)卷人一、判斷題：（正確者在括號(hào)內(nèi)打“，”，錯(cuò)誤者打“x 每小題1分，共10分）1.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。（）.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。（）.十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。（）. Hash表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。（）.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）.就平均查找長(zhǎng)度而言，分塊查找最小，折半查找次之，順序查找最大。（）7.對(duì)于一棵非空二叉樹(shù)，它的根2點(diǎn)作為第一層，則它的第i層上最多能有2i-1個(gè)結(jié)點(diǎn)。8.有e條邊的無(wú)向圖，在鄰接表中有e個(gè)結(jié)點(diǎn)9.順序

2、存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。 （）10.在查找樹(shù)（二叉樹(shù)排序樹(shù)）中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。（得分評(píng)卷人線上，每小題2分，共20分）、選擇題：（將每小題正確答案的選項(xiàng)填寫(xiě)在題后的橫1.在下面的程序段中，對(duì)x的賦值語(yǔ)句的頻度為 =FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;A. O(2n) B. O(n) C. O(n2)D. O(log2n)2.下面關(guān)于用的的敘述中，哪一個(gè)是不正確的？ oA.用是字符的有限序列B .空用是由空格構(gòu)成的用C.模式匹配是用的一種重要運(yùn)算D.用既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)3.棧和隊(duì)列的

3、共同特點(diǎn)是。A.只允許在端點(diǎn)處插入和刪除元素 B .都是先進(jìn)后出C.都是先進(jìn)先出D .沒(méi)有共同點(diǎn)4. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是 50,每個(gè)元素的長(zhǎng)度為4,則第5個(gè)元素的地址是 oA. 70 B. 66 C. 50 D. 78.設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作，則下面得不到的序列為？ 。A. fedcba B. bcafed C. dcefba D. cabdef.若用S= software ,若空用不算其子用，則其子用的數(shù)目是A.8B.37C.36D.9.具有10個(gè)葉結(jié)點(diǎn)的二叉樹(shù)中有多少個(gè)度為2的結(jié)點(diǎn) oA . 8B.9C.10D. 11.若有18個(gè)元素的有序

4、表存放在一維數(shù)組 A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找 A 3的比較序列的下標(biāo)依次為A. 1 , 2, 3B. 9 , 5, 2, 3C. 9 , 5, 3D. 9, 4, 2, 39.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為（20, 15, 14, 18, 21, 36, 40,10）,則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為 cA.10 ,15,14,18,20,36,40,21B.10 ,15,14,18,20,40,36,21C,10 ,15,14,20,18,40,36,2lD.15 , 10, 14,.在下述結(jié)論中，18, 20, 止確的是:36,40,21只有一個(gè)結(jié)點(diǎn)的

5、二叉樹(shù)的度為 0;二叉樹(shù)的度為2;二叉樹(shù)的左右子樹(shù)可任意交換；深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。A. B . C . D .2.由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有種形態(tài)。室教1場(chǎng)考得分評(píng)卷人三、填空題：(每小題2分，共20分。)1.數(shù)據(jù)的邏輯結(jié)構(gòu)分為兩大類(lèi)，它們是線性結(jié)構(gòu)和. 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。.數(shù)組的第一個(gè)元素的存儲(chǔ)地址是 5000,每個(gè)元素長(zhǎng)度是5,則第11個(gè)元 素的地址是。.廣義表(a, (b,c) ,d,e, (f,g ) ,h)的長(zhǎng)度為，深度為.對(duì)于n個(gè)關(guān)鍵字的集合進(jìn)行冒泡排序，在最壞情況下所需要的時(shí)間為。. INDEX(DATASTRUCT

6、URE STR) =。.折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表 中元素20,它將依次與表中元素 比較大小。.按照排序過(guò)程涉及的存儲(chǔ)設(shè)備的不同，排序可分為 排序和外部排 序。void BubbleSort(RecordType r ,int length)/* change 為特征位,定義為布爾型*/ n=length; ;for(i=1; i=&; i+)for(j=1;jrj+1.key)x=aj;rj=rj+1;rj+1=x; 3.以下列數(shù)據(jù)為輸入序列構(gòu)造二叉排序樹(shù)，畫(huà)出構(gòu)造結(jié)果。100 , 50, 30, 120, 150,

7、 110, 40, 70, 90, 200, 115, 105, 10問(wèn)時(shí)試考 號(hào)學(xué) 名姓 級(jí)班(5) S-next=L; Q=P; P=Q;(11) P=L;(13) L=P;(1)每個(gè)頂點(diǎn)的入/出度；(2)鄰接矩陣；(3)鄰接表；頂點(diǎn)1234入度出度4、已知如圖所示的有向圖，請(qǐng)給出該圖的10.具有8個(gè)頂點(diǎn)的無(wú)向圖，邊的總數(shù)最多為 。得分,評(píng)卷人 四、綜合題：(第一小題8分，第二小題6分，第三小題6 分，第四小題10分，第五小題10分共40分)1.已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表，且 P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié) 點(diǎn)，試從下列提供的答案中選擇合適的語(yǔ)句序列。a.在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列

8、是 ob.在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是 oc.在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是 od.在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是 o(1) P-next=S; (2) P-next=P-next-next;(3) P-next=S-next; (4) S-next=P-next;(6) S-next=NULL;(8) while(P-next!=Q) P=P-next;(10) while(P-next!=NULL) P=P-next;(12) L=S;2.以下為冒泡排序的算法。請(qǐng)分析算法，并在 上填充適當(dāng)?shù)恼Z(yǔ)句得分評(píng)卷人五、算法設(shè)計(jì)題:(10 分)1.寫(xiě)一算法，在帶頭結(jié)點(diǎn)的單鏈線性表 L中，刪除第i個(gè)元素，并由e返回其值) 室 教(5.假設(shè)用于通信的電文由字符集a,b,c,d,e,f,g,h 8個(gè)字母構(gòu)成。它們?cè)陔娢闹谐霈F(xiàn)的頻度分別