東北大學(xué)15秋學(xué)期《數(shù)據(jù)結(jié)構(gòu)Ⅰ》在線作業(yè)3答案

1、15秋學(xué)期數(shù)據(jù)結(jié)構(gòu)在線作業(yè)3 單選題 一、單選題（共 20 道試題，共 100 分。）1. 采用ISM或VSM組織的文件是 . 索引非順序文件 . 順序文件 . 索引順序文件 . 散列文件-選擇： 2. . 對長度為15的有序順序表進行二分查找，在各記錄的查找概率均相等的情況下，查找成功時所需進行的關(guān)鍵字比較次數(shù)的平均值為 . 39/15 . 49/15. . 51/15 . 55/15-選擇： 3. 假設(shè)一棵完全二叉樹按層次遍歷的順序依次存放在數(shù)組Tm中，其中根結(jié)點存放在T0，若Ti中的結(jié)點有左孩子，則左孩子存放在 . Ti/2 . T2*i-1 . T2*i . T2*i+1-選擇： 4.

2、 for（i=0；im；i+） for（j=0；jt；j+）ij=0；for（i=0；im；i+）for（j=0；jt；j+）for（k=0；kn；k+）ij=ij+ik*kj； 上列程序的時間復(fù)雜度為 . O（m+nt） . O（m+n+t） . O（mnt） . O（mt+n）-選擇： 5. FS算法可用來解決單源最短路徑問題的條件是當各邊上的權(quán)值. 均相等 . 均互不相等 . 不一定相等 . 任意值-選擇： 6. 高度為5的完全二叉樹中含有的結(jié)點數(shù)至少為 . 16. 17. 31. 32-選擇： 7. 下列序列中，不構(gòu)成堆的是. （1，2，5，3，4，6，7，8，9，10）. （10，5

3、，8，4，2，6，7，1，3）. （10，9，8，7，3，5，4，6，2）. （1，2，3，4，10，9，8，7，6，5）-選擇： 8. 多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲方式是因為. 數(shù)組的元素處在行和列兩個關(guān)系中 . 數(shù)組的元素必須從左到右順序排列. 數(shù)組的元素之間存在次序關(guān)系 . 數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)-選擇： 9. 用二叉鏈表表示具有n個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為 . n-1. n. n+1. 2n-選擇： 10. 在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是 . 插入 . 刪除 . 排序 . 查找-選擇： 11. 導(dǎo)致棧上溢的操作是. 棧滿

4、時執(zhí)行的出棧 . 棧滿時執(zhí)行的入棧. ?？諘r執(zhí)行的出棧 . 棧空時執(zhí)行的入棧-選擇： 12. 判斷兩個串大小的基本準則是. 兩個串長度的大小 . 兩個串中首字符的大小. 兩個串中大寫字母的多少 . 對應(yīng)的第一個不等字符的大小-選擇： 13. 可有效提高次關(guān)鍵字查找效率的文件是 . 順序文件 . 倒排文件 . 散列文件 . VSM文件-選擇： 14. 若是有向圖的一條邊，則稱 . vi鄰接于vj . vj鄰接于vi . vi和vj相互鄰接 . vi與vj?不相鄰接-選擇： 15. 某二叉樹中序序列為,E,F,G，后序序列為,F,G,E 則該二叉樹對應(yīng)的森林包括的樹的棵樹是 . 1. 2. 3.

5、概念上是錯誤的 -選擇： 16. 在一個單鏈表中，已知q結(jié)點是p結(jié)點的前驅(qū)結(jié)點，若在q 和p之間插入結(jié)點s，則執(zhí)行操作 . s-next=p-next;p-next=s; . s-next=p; q-next=s . q-next=s;s-next=p; . p-next=s;s-next=q;. q-next=s;s-next=p; . p-next=s;s-next=q;-選擇： 17. 下面說法錯誤的是 (1）算法原地工作的含義是指不需要任何額外的輔助空間 （2）在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時間上總是優(yōu)于復(fù)雜度O(2n)的算法 （3）所謂時間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界 （4）同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低. (1) . (1),(2) . (1),(4) . (3)-選擇： 18. n個頂點的有向完全圖中含有向邊的數(shù)目最多為. n-1 . n . n(n-1)/2 . n(n-1)-選擇： 19. 對有18個元素的有序表作二分查找，則查找3的比較序列的下標為 . 1，2，3 . 9，5，2，3 . 9，5，3 . 9，4，2，3-選擇： 20. 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)