數(shù)據(jù)結(jié)構(gòu)試卷

1、數(shù)據(jù)結(jié)構(gòu)考卷課程名稱數(shù)據(jù)結(jié)構(gòu)使用專業(yè)管理科學(xué)與工程班級姓名學(xué)號 一、單項選擇題（每題 2 分，共 40 分）1.若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行和刪除運(yùn)算，則利用（A順序表）方式最節(jié)省時間。B雙鏈表 D單循環(huán)鏈表N 的數(shù)組空間中，若該隊列的隊首和隊尾C結(jié)點的雙循環(huán)鏈表2.一個隊列順序在一個長度為指針分別用 front 和 rear 表示，則該隊列中的元素個數(shù)為（）。A(rear+N)%N C(rear-front+N)%N一個棧的輸入序列為B(rear-front)%N D(front+N)%N123n，若輸出序列的第一個元素是 n，輸出第 i3.（1<=i&l

2、t;=n）個元素是（）。A不確定Bn-i+1CiDn-i4.若語句 S 的執(zhí)行時間為O(1)，那么下列程序段的時間復(fù)雜度為（ For(i = 0; i <= n ; i+)For(j = 0; j <=n ;j+)S;）。BO(n2)AO(n)利用二叉鏈表A指向最左孩子C空CO(n*log2n)DO(n*i)5.樹，則根結(jié)點的右指針是()B指向最右孩子D非空6.由權(quán)值分別為 3，8，10，2，6 的葉子結(jié)點生成一棵哈夫曼樹，則其中非終端結(jié)點數(shù)為（A2）。B3C4D57.設(shè)樹T 的度為 5，其中度為 1，2，3，4 和 5 的結(jié)點個數(shù)分別為 5，4，3，2，1 則T 中的葉子結(jié)點數(shù)為

3、（）。A19B20C21D221試題得分一二三四五總分8.n 個結(jié)點的二叉樹上空指針數(shù)目為（）CnlA2nBnlDn9.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF, 中序遍歷結(jié)果為CBAEDF, 則后序遍歷的結(jié)果為（）。ACBEFDAB FEDCBAC CBEDFAD不定10.具有 65 個結(jié)點的完全二叉樹的高度為（）（根的層次號為 1）。A8B7C6D911.設(shè)有 6 個結(jié)點的無向圖，該圖至少應(yīng)有()條邊才能確保是通圖。A5在有向圖的鄰接表A頂點 v 的度C頂點 v 的入度B6C7D812.結(jié)構(gòu)中，頂點 v 在鏈表中出現(xiàn)的次數(shù)是（B頂點 v 的出度D依附于頂點 v 的邊數(shù)）。13.數(shù)據(jù)表中有

4、 10000 個元素，如果僅要求求出其中最大的 10 個元素，則采用（ ）算法最節(jié)省時間。A堆排序C快速排序二分查找法適用于B希爾排序 D直接選擇排序）的、按關(guān)鍵字排好序的線性表。B順序D鏈?zhǔn)?4.結(jié)構(gòu)為（A順序C索引或鏈?zhǔn)?5.現(xiàn)存在一個有序表為(10,15,17,18,25,29,48,52,58,69,90)，當(dāng)二分查找值為 58的元素時，(A1)次比較后方可查找B2。C3D416.散列表的地址區(qū)間為 0-17，散列函數(shù)為 H(K)=K mod 17。采用線性探測法處理，并將關(guān)鍵字序列 (26,25,72,38,8,18,59)依次到散列表中。查找元素 59 需要搜索的次數(shù)是（）。A2B

5、3C4D517.對下列關(guān)鍵字序列用快速排序法進(jìn)行排序時，速度最快的排序方法是（）。A (5,9,17,21,23,25,30)C (21,25,5,17,9,23,30)B (21,9,17,30,25,23,5)D (25,23,30,17,21,5,9)18.一組的排序碼為46,79,56,38,40,84，則利用大根堆排序的方法建立的初始堆為（）。A79,46,56,38,40,80C84,79,56,46,40,38B84,79,56,38,40,46D84,56,79,40,46,38219.設(shè)有一組的關(guān)鍵字為19,14,23,1,68,20,84,27,55,11,10,79，用鏈

6、地址法構(gòu)造哈希表，哈希函數(shù)為 H( key )=key mod 13，則哈希地址為 1 的鏈中有（ ）個。A4B3C2D120.下面關(guān)于求關(guān)鍵路徑的說法不正確的是（A求關(guān)鍵路徑是以拓?fù)渑判驗榛A(chǔ)的）。B一個C一個的最早開始時間與以該的最遲開始時間為以該為尾的弧的活動最早開始時間相同為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D關(guān)鍵活動一于關(guān)鍵路徑上二、綜合應(yīng)用題 （每題 6 分，共 30 分）21.依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹：(1) 試畫出生成之后的二叉排序樹;(2) 假定每個元素的查找概率相等，試計算該

7、二叉排序樹的平均查找長度。22.有 5 個元素，其入棧次序為 A、B、C、D、E。請問在各種可能的出棧序列中，第一個出棧元素為C 且第二個出棧元素為 D 的出棧序列有哪幾個。323.給出一組關(guān)鍵字：29，18，25，47，58，12，51，10，先建成一個大頂堆， 然后從堆頂取下一個元素，再將堆調(diào)整成大頂堆，這時的關(guān)鍵字序列是什么？24.考慮下圖：根據(jù)普利姆(Prim)算法求它的最小生成樹。25.有一份電文中共使用 8 個字符：a,b,c,d,e,f,g,h。它們的出現(xiàn)頻率依次為15,3,14,2,6,9,16,17，請畫出對應(yīng)的赫夫曼樹（按左子樹根結(jié)點的權(quán)值小于等于右子樹根結(jié)點的權(quán)值的次序構(gòu)

8、造），并求出每個字符的赫夫曼編碼。4三、程序閱讀題（2*5 分=10 分）26. 閱讀下面的算法：LinkList mynote(LinkList L)/L 是不結(jié)點的單鏈表的頭指針if (L && L->next)q = L;L = L -> next; p = L;While ( p -> next) p = p -> next; p -> next = q;q -> next = NULL;return L;如果鏈表表示的線性表為（a1, a2, , an），寫出算法執(zhí)行后的返回值所表示的線性表。27. 簡述以下算法的功能（棧和隊列的元

9、素類型均為void algo2(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);int）。5四、算法填空題（5 分）28. 完善下列折半排序算法。說明：struct node 為已定義的結(jié)構(gòu)體類型，其中包含 key 成員，是該結(jié)構(gòu)體的關(guān)鍵字。以下函數(shù)中，形參r 為傳入的結(jié)構(gòu)體數(shù)組，需要根據(jù)關(guān)鍵字對該數(shù)組進(jìn)行從小到大排序；形參n 為數(shù)組的大小。void binasort（struct noderMAXSIZE，int n）for（i=2；i<=n；i+） r0=ri；low=1；high=i-1； while（low<=high）mid=（1）；if（r0.key<rmid.key） high=（2）；else low=（3）_；for（j=i-1；j>=low；j- -）_（4）；rlow=（5）；五、算法設(shè)計題（共 15 分，第 1 題 7 分，第 2 題 8 分）29. 有一個結(jié)點的單鏈表中（不同結(jié)點的數(shù)據(jù)域的值可能相同），其頭指針為 head，試設(shè)計一個算法，刪除數(shù)據(jù)域為 x 的所有結(jié)點，并返回刪除的結(jié)