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

數(shù)據(jù)結(jié)構(gòu)試卷 一 數(shù)據(jù)結(jié)構(gòu)試卷 一 一 單選題 每題一 單選題 每題 2 分 共分 共 20 分 分 1 棧和隊(duì)列的共同特點(diǎn)是 A 只允許在端點(diǎn)處插入和刪除元素 B 都是先進(jìn)后出 C 都是先進(jìn)先出 D 沒有共同點(diǎn) 2 用鏈接方式存儲(chǔ)的隊(duì)列 在進(jìn)行插入運(yùn)算時(shí) A 僅修改頭指針B 頭 尾指針都要修改 C 僅修改尾指針D 頭 尾指針可能都要修改 3 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu) A 隊(duì)列B 棧C 線性表D 二叉樹 4 設(shè)有一個(gè)二維數(shù)組 A m n 假設(shè) A 0 0 存放位置在 644 10 A 2 2 存放位置在 676 10 每個(gè)元素占一個(gè)空間 問 A 3 3 10 存放在什么位置 腳注 10 表示用 10 進(jìn)制 表示 A 688B 678C 692D 696 5 樹最適合用來表示 A 有序數(shù)據(jù)元素B 無序數(shù)據(jù)元素 C 元素之間具有分支層次關(guān)系的數(shù)據(jù)D 元素之間無聯(lián)系的數(shù)據(jù) 6 二叉樹的第 k 層的結(jié)點(diǎn)數(shù)最多為 A 2 k 1 B 2K 1C 2K 1D 2 k 1 7 若有 18 個(gè)元素的有序表存放在一維數(shù)組 A 19 中 第一個(gè)元素放 A 1 中 現(xiàn)進(jìn)行二 分查找 則查找 A 3 的比較序列的下標(biāo)依次為 A 1 2 3B 9 5 2 3 C 9 5 3D 9 4 2 3 8 對 n 個(gè)記錄的文件進(jìn)行快速排序 所需要的輔助存儲(chǔ)空間大致為 A O 1 B O n C O 1og2n D O n2 9 對于線性表 7 34 55 25 64 46 20 10 進(jìn)行散列存儲(chǔ)時(shí) 若選用 H K K 9 作為散列函數(shù) 則散列地址為 1 的元素有 個(gè) A 1B 2C 3D 4 10 設(shè)有 6 個(gè)結(jié)點(diǎn)的無向圖 該圖至少應(yīng)有 條邊才能確保是一個(gè)連通圖 A 5B 6C 7D 8 二 填空題 每空二 填空題 每空 1 分 共分 共 26 分 分 1 通常從四個(gè)方面評價(jià)算法的質(zhì)量 和 2 一個(gè)算法的時(shí)間復(fù)雜度為 n3 n2log2n 14n n2 其數(shù)量級表示為 3 假定一棵樹的廣義表表示為 A C D E F G H I J 則樹中所含的結(jié)點(diǎn)數(shù) 為 個(gè) 樹的深度為 樹的度為 4 后綴算式 9 2 3 10 2 的值為 中綴算式 3 4X 2Y 3 對應(yīng)的后綴算式 為 5 若用鏈表存儲(chǔ)一棵二叉樹時(shí) 每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外 還有指向左孩子和右孩子的兩個(gè)指 針 在這種存儲(chǔ)結(jié)構(gòu)中 n 個(gè)結(jié)點(diǎn)的二叉樹共有 個(gè)指針域 其中有 個(gè) 指針域是存放了地址 有 個(gè)指針是空指針 6 對于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的有向圖和無向圖 在其對應(yīng)的鄰接表中 所含邊結(jié)點(diǎn) 分別有 個(gè)和 個(gè) 7 AOV 網(wǎng)是一種 的圖 8 在一個(gè)具有 n 個(gè)頂點(diǎn)的無向完全圖中 包含有 條邊 在一個(gè)具有 n 個(gè)頂點(diǎn)的有 向完全圖中 包含有 條邊 9 假定一個(gè)線性表為 12 23 74 55 63 40 若按 Key 4 條件進(jìn)行劃分 使得同一余數(shù)的元 素成為一個(gè)子表 則得到的四個(gè)子表分別為 和 10 向一棵 B 樹插入元素的過程中 若最終引起樹根結(jié)點(diǎn)的分裂 則新樹比原樹的高度 11 在堆排序的過程中 對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 整個(gè)堆排序 過程的時(shí)間復(fù)雜度為 12 在快速排序 堆排序 歸并排序中 排序是穩(wěn)定的 三 計(jì)算題 每題三 計(jì)算題 每題 6 分 共分 共 24 分 分 1 在如下數(shù)組 A 中鏈接存儲(chǔ)了一個(gè)線性表 表頭指針為 A 0 next 試寫出該線性表 A01234567 data605078903440 next3572041 2 請畫出下圖的鄰接矩陣和鄰接表 3 已知一個(gè)圖的頂點(diǎn)集 V 和邊集 E 分別為 V 1 2 3 4 5 6 7 E 1 2 3 1 3 5 1 4 8 2 5 10 2 3 6 3 4 15 3 5 12 3 6 9 4 6 4 4 7 20 5 6 18 6 7 25 用克魯斯卡爾算法得到最小生成樹 試寫出在最小生成樹中依次得到的各條邊 4 畫出向小根堆中加入數(shù)據(jù) 4 2 5 8 3 時(shí) 每加入一個(gè)數(shù)據(jù)后堆的變化 四 閱讀算法 每題四 閱讀算法 每題 7 分 共分 共 14 分 分 1 LinkList mynote LinkList L L 是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if L ABC BT right cout data data item BST data 查找成功 return else if itemdata returnFind item elseretu