2016年云南昆明理工大學計算機學科專業(yè)基礎(chǔ)綜合考研真題A卷

1、2016年云南昆明理工大學計算機學科專業(yè)基礎(chǔ)綜合考研真題A卷數(shù)據(jù)結(jié)構(gòu)部分一、 單項選擇題（共25題，每題1分，共25分）1. 對一個算法的評價，不包括如下（ ）方面的內(nèi)容。(A)健壯性和可讀性 （B）并行性 （C）正確性 （D）時空復雜度2.  對線性表，在下列哪種情況下應(yīng)當采用鏈表表示？( )（A）經(jīng)常需要隨機地存取元素 （B）經(jīng)常需要進行插入和刪除操作（C）表中元素需要占據(jù)一片連續(xù)的存儲空間 （D）表中元素的個數(shù)不變3. 下面程序段的時間復雜度是（ ）。j=0; s=0; while (s<n) j+; s=s+j; (A) O（n） (B) O（2 n） (C) O（n）

2、 (D) O（n2）4. 從一個長度為n的順序表中，如果刪除第i個元素時，需要向前移動（ ）個元素。(A) n-i (B) n- i +1 (C ) n- i -1 (D) i 5. 設(shè)單鏈表中指針p指向結(jié)點，若要刪除之后的結(jié)點（結(jié)點若存在），則需修改指針的操作是（ ）。(A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) next=p6. 若某線性表最常用的操作是讀取任一指定序號的元素和在最后進行插入和刪除運算，則采用 （ ）存儲方式最省時間。(A) 順序表 (B) 雙鏈表 (C )

3、帶頭結(jié)點的雙循環(huán)鏈表 (D) 單循環(huán)鏈表7. 用鏈接方式存儲的隊列，在進行插入運算時( ). (A) 僅修改頭指針 (B) 頭、尾指針都要修改 (C ) 僅修改尾指針 (D) 頭、尾指針可能都要修改8. 在順序棧中，假定以高端地址作為棧底，以top作為棧頂，則當做出棧處理時，top 的變化為( )。(A) 不變 (B) top=0 (C ) top=top -1 (D) top=top+19. 一個棧的入棧序列為1 2 3，入棧時可以出棧，則下列序列中不可能是出棧序列的是( )(A) 2 3 1(B) 3 2 1(C) 3 1 2 (D) 1 2 310. 輸入受限的雙端隊列是指元素只能從隊列

4、的一端輸入，但可以從隊列的兩端輸出，如圖所示。若有8、1、4、2依次進入輸入受限的雙端隊列，則得不到輸出序列( ).。 輸入受限的雙端隊列 (A). 2、8、1、4 (B). 1、4、8、2 ( C) . 4、2、1、8 (D). 2、1、4、811. 棧和隊列的共同特點是( )。 (A)只允許在端點處插入和刪除元素 (B)都是先進后出 (C)都是先進先出(D)沒有共同點 12. 給定一個有n個元素的有序線性表。若采用順序存儲結(jié)構(gòu)，則在等概率前提下，刪除其中的一個元素平均需要移動 個元素。 ( A). (n+1)/2 (B) . n/2 (C) . (n-1)/2 (D). 113. 在具有n

5、個單元的順序存儲的循環(huán)隊列中，假定front、rear 分別為隊首和隊尾指針，則判斷隊滿的條件是( ).。 （A）(rear%n)= front （B）(front+1%n)=rear （C）(rear-1) %n)= front （D）(rear+1)%n)=front14. 一個中綴算術(shù)表達式a+（b-x）*y，則對應(yīng)的后綴算術(shù)表達式為 ( ).。(A) a b x y - * +; (B) a b x - + y *;(C) a b x - y * +; (D) a b x y * - +;15. 設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)

6、，每個元素占一個空間，問A33(10)存放在什么位置？( ).腳注(10)表示用10進制表示。(A)688 (B)678 (C) 692 （D）69616. 樹最適合用來表示( )。 (A)有序數(shù)據(jù)元素 (B)無序數(shù)據(jù)元素 (C)元素之間具有分支層次關(guān)系的數(shù)據(jù) (D)元素之間無聯(lián)系的數(shù)據(jù)17. 在有n個結(jié)點的二叉鏈表中，值非空的鏈域的個數(shù)為( )。(A) n-1 (B) 2n-1 (C) n+1 (D) 2n+1 18. 在一個具有n個頂點的無向圖中，最多包含有( )邊。(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) n219. 在一個具有n個頂點的無向圖中，

7、要連通全部頂點至少需要( )條邊。 (A) n (B) n+1 (C) n-1 (D) n/220. 任何一個無向連通圖的最小生成樹( )(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D)可能不存在。21. 在有向圖的鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有( )鄰接點；在有向圖的逆鄰接表中，每個頂點的鄰接表鏈接著該頂點的所有( )鄰接點；(A) 出邊，入邊 (B) 入邊，出邊22. 在線性表的存儲結(jié)構(gòu)中，( )查找（按關(guān)鍵字查找）、插入、刪除速度慢，但順序存取和隨機存取第i個元素速度快；( )查找和存取速度快，但插入、刪除速度慢；( )查找、插入和刪除速度快，但不能進行順序存取

8、；( )插入、刪除和順序存取速度快；但查找速度慢。(A) 散列表，順序有序表，順序表，鏈接表(B) 順序表，順序有序表，散列表，鏈接表 (C) 鏈接表，順序有序表，散列表，順序表 (D) 順序有序表，順序表，鏈接表，散列表23. 用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ）(A)選擇排序 （B）希爾排序 （C）歸并排序 （D）快速排序24

9、. 已知一個有序表為（12，18，24，35，47，50，62，83，90，115，134），當二分查找值為90的元素時，( )次比較后查找成功；當二分查找值為47的元素時，( )次比較后查找成功。 (A) 1，4 (B) 2，4 (C) 3，2 (D) 4，225. 在順序存儲的線性表A30上進行順序查找的平均查找長度為( )。 (A) 15 (B) 15.5 (C) 16 (D) 20二、綜合題：（共3題，共50分）1. 在算法設(shè)計中，存儲結(jié)構(gòu)的設(shè)計與什么因素有關(guān)？（10分）312456128155420108962. 在幾個居民點鋪設(shè)煤氣管道，每兩個居民間的鋪設(shè)費用是可以估算的（如右圖所

10、示）。1) 如果要求鋪設(shè)的總費用最小，從圖的理論上，這實際上是什么求解問題。（8分）2) 請用Prim算法思想，從V1點開始，畫出鋪設(shè)方案選邊的圖示過程。（12分）3. 一組待排序的記錄為（46,79,56,38,40,84），寫出從小到大： 利用冒泡排序第一,二趟的變化序列; （10分） 利用快速排序第一趟的變化序列; （10分）計算機網(wǎng)絡(luò)部分一、單項選擇題（每空1分，總分20分）1、Internet 中域名與IP地址之間的翻譯是由_(1)_ 來完成的。A. 域名服務(wù)器B. 代理服務(wù)器CFTP 服務(wù)器DWeb 服務(wù)器2、瀏覽器與WWW服務(wù)器之間傳輸信息時使用的協(xié)議是_(2)_。 A

11、HTTPBHTMLCFTP DSNMP 3、屬于物理層的互連設(shè)備是_(3)_。A中繼器B網(wǎng)橋C.交換機D.路由器4、路由器是一種常用的網(wǎng)絡(luò)互連設(shè)備，它工作在OSIRM的（4） 上，在網(wǎng)絡(luò)中它能夠根據(jù)網(wǎng)絡(luò)通信的情況（5） ，并識別（6）·相互分離的網(wǎng)絡(luò)經(jīng)路由器互連后（7） 。(4)：A物理層 B數(shù)據(jù)鏈路層 C網(wǎng)絡(luò)層 D傳輸層(5)：A動態(tài)選擇路由 B控制數(shù)據(jù)流量 C調(diào)節(jié)數(shù)據(jù)傳輸率 D改變路由結(jié)構(gòu) (6)：AMAC地址 B網(wǎng)絡(luò)地址 CMAC地址和網(wǎng)絡(luò)地址 DMAC地址和網(wǎng)絡(luò)地址的共同邏輯地址 (7)：A形成了一個更大的物理網(wǎng)絡(luò) B仍然還是原來的網(wǎng)絡(luò) C形成了一個邏輯上單一的網(wǎng)絡(luò)

12、 D成為若干個互連的子網(wǎng) 5、ADSL對應(yīng)的中文術(shù)語是_(8)_。A分析數(shù)字系統(tǒng)層 B非對稱數(shù)字線C非對稱數(shù)字用戶線 D異步數(shù)字系統(tǒng)層6、以下網(wǎng)絡(luò)設(shè)備中，工作于網(wǎng)絡(luò)層的設(shè)備是_(9)_ 。A調(diào)制解調(diào)器B. 以太網(wǎng)交換機C. 集線器D. 路由器7、在Windows 中，可以提供WWW服務(wù)的軟件是_(10)_ 。A. IIS B. ISAC. ISP D. ASP8、網(wǎng)絡(luò)/22 中最多可用的主機地址是_(11)_ 。A. 1024B. 1023C. 1022D. 10009、通過_(12)_ 命令可以查看當前計算機的TCP 連接狀態(tài)。A. route B. pingC. n

13、etstat D. ipconfig10、在下列網(wǎng)絡(luò)服務(wù)中，_(13)_ 是遠程登陸服務(wù)，默認端口號為_(14)_ 。（13）A. WWW B. FTP C. BBS D. Telnet（14）A21B23C25D8011、在網(wǎng)絡(luò)地址中劃分出10個大小相同的子網(wǎng)，每個子網(wǎng)最多有_(15)_個可用的主機地址。 A2046B2048C4094D4096 12、在瀏覽Web頁面時，發(fā)現(xiàn)了自己需要經(jīng)常使用的Web頁面，此時最好的方法是_(16)_。 A將該Web頁面的地址加入到"收藏夾" B將該Web頁面的地址加入到&qu

14、ot;地址簿" C將該Web頁面的地址加入到"notepad" D將該Web頁面的地址加入到"歷史記錄"13、在Windows的網(wǎng)絡(luò)屬性配置中， “默認網(wǎng)關(guān)”應(yīng)該設(shè)置為_(17)_的地址。ADNS服務(wù)器BWeb服務(wù)器 C路由器D交換機14、電子郵件通常使用的協(xié)議有_(18)_。ASMTP和POP3BSMTP和RMON CRMON和SNMP DSNMP和POP315、Internet中用于文件傳輸?shù)氖莀(19)_。ADHCP服務(wù)器 BDNS服務(wù)器 CFTP服務(wù)器 D路由器16、代理服務(wù)器可以提供_(20)_功能。A信息轉(zhuǎn)發(fā) B

15、路由選擇 C域名解析D幀封裝二、綜合應(yīng)用題（總分55分）1、制作交叉雙絞線(一端按EIA/TIA 568A線序，另一端按EIA/TIA 568B線序)時，其中一端的線序如圖(a)所示，另一端線序如圖(b)所示，將圖(b)中(1)(8)處空缺的顏色名稱填寫出來（每空2.5分，20分）。2、某公司內(nèi)部有一個采用TCP/IP作為傳輸協(xié)議的100Base-TX局域網(wǎng)，包括1臺服務(wù)器和20臺客戶機，通過一臺16端口的交換機與一臺8端口共享集線器級連，其網(wǎng)絡(luò)結(jié)構(gòu)如下圖所示。服務(wù)器上運行DHCP服務(wù)軟件，客戶機的IP地址由DHCP服務(wù)程序自動分配。（15分）問題1連接主機A與交換機的單根網(wǎng)線的最大長度為多少? (5分)問題2該局域網(wǎng)中的集線器每個端口平均享有的帶寬是多少? (5分)問題3為了控制局域網(wǎng)用戶訪問Internet時只能進行WWW瀏覽，網(wǎng)管應(yīng)該在路由器上采取什么措施? (5分)3、某一網(wǎng)絡(luò)地址塊中有5臺主機A、B、C、D和E，它們的IP地址及子網(wǎng)掩碼如下表所示。（20分）主機IP地址及子網(wǎng)掩碼表主機IP地址子網(wǎng)掩碼A840B192.168.