全國(guó)2021年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

20211月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題全國(guó)2008年1月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題02142一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合標(biāo)題問題要求的的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1.在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是()A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)元素C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)文件2.k=1;p=p->next;p->next=h;后（p->next為p指向結(jié)點(diǎn)的指針域()A.p->next指針指向鏈尾結(jié)點(diǎn)B.h指向鏈尾結(jié)點(diǎn)C.刪除鏈尾前面的結(jié)點(diǎn)D.刪除鏈尾結(jié)點(diǎn)19200314個(gè)元素的存儲(chǔ)地址為()A.236B.239C.242D.245一個(gè)棧的入棧序列是a，b，c，d，e()A.dceabB.decbaC.edcbaD.abcde1n個(gè)單元的非空挨次棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應(yīng)修改為()A.top=topB.top=n-1C.top=top-1D.top=top+1()A.高度等于其結(jié)點(diǎn)數(shù)B.任一結(jié)點(diǎn)無左孩子C.任一結(jié)點(diǎn)無右孩子D.空或只有一個(gè)結(jié)點(diǎn)()A.左孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)10.()A.有向圖B.帶權(quán)有向圖C.有向圖或無向圖D.無向圖在一個(gè)具有n()A.n-1B.nC.n+1D.若構(gòu)造一棵具有n()B.nC.D.n+1堆積()A.由同義詞之間發(fā)生沖突引起的B.由非同義詞之間發(fā)生沖突引起的C.由同義詞之間或非同義詞之間發(fā)生沖突引起的D.由散列表”溢出”引起的10000個(gè)元素，若只想得到其中前10法是()快速排序B.堆排序C.插入排序D.二路歸并排序在排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）()A.希爾排序B.插入排序C.冒泡排序D.快速排序得分二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。數(shù)據(jù)的邏輯結(jié)構(gòu)通常包羅集合、線性結(jié)構(gòu)和圖狀結(jié)構(gòu)。設(shè)雙鏈表中結(jié)點(diǎn)的前趨指針和后繼指針的域名別離為t1和r1，指針s指向雙鏈表的一個(gè)結(jié)點(diǎn)（該結(jié)點(diǎn)既非頭結(jié)點(diǎn)，也非尾結(jié)點(diǎn)） ，則刪除s指針?biāo)赶蚪Y(jié)點(diǎn)的操作為”s->tl->r1=s->r1；”” 。對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是節(jié)。在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值為m的某結(jié)點(diǎn)，若查找成功，則需平均比的結(jié)點(diǎn)數(shù)。深度為15的滿二叉樹上，第11層個(gè)結(jié)點(diǎn)。對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的左孩子的號(hào)為 。一個(gè)具有4個(gè)頂點(diǎn)的無向完全圖條邊。一個(gè)有向圖G中若有孤、和，則在圖G的拓?fù)湫蛄兄?，頂點(diǎn)和Vk的相對(duì)置為 。在一棵二叉排序樹上遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于挨次存儲(chǔ)結(jié)構(gòu)，且其中元素?cái)[列必需是 的。文件的檢索有三種方式，它們是挨次存取、直接存取存取。在插入排序和選擇排序中，若原始記錄已基本有序，則較適合選。對(duì)n個(gè)元素的序列進(jìn)行冒泡排序時(shí)，最多需進(jìn)趟三、應(yīng)用本大題共5小題，每小題6分，共30分)29.寫出利用直接選擇排序方法對(duì)一組關(guān)鍵碼為（54，38，96，23，15，72，60）的記錄進(jìn)行排序時(shí)，每趟排序的結(jié)果。30.已知一棵二叉樹的中根遍歷序列和后根遍歷序列別離為BDAFEHGC 和DBFHGECA，試畫出這棵二叉樹。31設(shè)閉散列表容量為（散列地址空間0..，給定表3，3，4，5，34,H（K）=Kmod構(gòu)造散列表；34需要比力的次數(shù)。32圖所示，在棧的輸入端有6個(gè)元素，挨次為。能否在棧的輸出端得到序列DCFEBA及EDBFCA題32圖已知無向圖G33時(shí)的拜候序列。其中nil表示空。題33圖四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)編寫一個(gè)函數(shù)voidinsert(int*p,intsize,inta插入指針變量p指向的長(zhǎng)度為size折半查找的方法，找出要插入數(shù)據(jù)的位置；然后按升序?qū)?shù)據(jù)插入該數(shù)組中。ty