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

第8頁(yè)共8頁(yè)（密封線內(nèi)不要答題）………密………………（密封線內(nèi)不要答題）………密………………封………………線……………專(zhuān)業(yè)______________________班級(jí)姓名______________學(xué)號(hào)f考試科目數(shù)據(jù)結(jié)構(gòu)考試時(shí)間2015.1.9考試方式閉卷成績(jī)題號(hào)一二三四五核總分得分評(píng)卷人（滿分100分,考試時(shí)間120分鐘）一、填空題（每空1分，共25分）1、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有和兩種基本方法，不論哪種存儲(chǔ)結(jié)構(gòu)都要存儲(chǔ)兩方面的內(nèi)容：和。2、算法分析的目的是：，算法分析的兩個(gè)主要方面是、。3、一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為；在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為。4、非空的循環(huán)單鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足。5、棧和隊(duì)列的主要區(qū)別在于：。6、在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素是棧底元素是。7、表達(dá)式a*（b+c）/d-e的后綴表達(dá)式是。8、在有n個(gè)葉子的哈夫曼樹(shù)中，葉子結(jié)點(diǎn)總數(shù)為，分支結(jié)點(diǎn)總數(shù)為。9、深度為k的二叉樹(shù)至少有個(gè)結(jié)點(diǎn)，至多有個(gè)結(jié)點(diǎn)。10、在一個(gè)有向圖中，所有頂點(diǎn)的度數(shù)之和等于所有弧數(shù)的倍。11、已知一個(gè)無(wú)向圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是。12、在一個(gè)有向圖中，若存在弧<vi，vj>、<vj，vk>、<vi，vk>，則在其拓?fù)湫蛄兄械?，頂點(diǎn)vi，vj，vk的相對(duì)次序?yàn)椤?3、如果要將序列(50，16，23，68，94，70，73)建成堆，只需把16與交換。14、在索引表中，每個(gè)索引項(xiàng)至少包含有和等信息。15、設(shè)有40000個(gè)記錄，通過(guò)分塊劃分為若干子表并建立索引，那么為了提高查找效率，每一個(gè)子表的大小應(yīng)設(shè)計(jì)為。二、選擇題（每題2分，共22分）1、使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以()A、節(jié)約存儲(chǔ)空間B、提高檢索速度C、更方便數(shù)據(jù)的插入和刪除D、很快回收存儲(chǔ)空間2、對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是()A、O(1)B、O(n)C、O(n2)D、O(nlog2n)（密封線內(nèi)不要答題）………（密封線內(nèi)不要答題）………密………………封………………線……………專(zhuān)業(yè)______________________班級(jí)姓名______________學(xué)號(hào)fA、s->next=p->next；p->next=s；B、q->next=s；s->next=p；C、p->next=s->next；s->next=p；D、p->next=s；s->next=q；4、設(shè)線性表有n個(gè)元素，以下操作中，()在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)的效率更高。A、輸出第i(1≤i≤n)個(gè)元素值B、交換第1個(gè)和第2個(gè)元素的值C、順序輸出所有n個(gè)元素D、查找與給定值x相等的元素在線性表中的序號(hào)5、下面的說(shuō)法中，不正確的是()A、數(shù)組是一種定長(zhǎng)的線性結(jié)構(gòu)B、數(shù)組是一種隨機(jī)存取結(jié)構(gòu)C、數(shù)組的基本操作有存取、修改、檢索等，沒(méi)有插入與刪除操作D、除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索等6、設(shè)主串S=“ababaababcb”，模式T=“ababc”，則該模式的next[3]值為()A、-1B、0C、1D、27、含n個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)

()A、1B、n/2C、n-1D、n8、討論樹(shù)、森林和二叉樹(shù)的關(guān)系，目的是為了()A、借助二叉樹(shù)上的運(yùn)算方法去實(shí)現(xiàn)對(duì)樹(shù)的一些運(yùn)算B、將樹(shù)、森林按二叉樹(shù)的存儲(chǔ)方式進(jìn)行存儲(chǔ)并利用二叉樹(shù)的算法解決樹(shù)的有關(guān)問(wèn)題C、將樹(shù)、森林轉(zhuǎn)換成二叉樹(shù)D、體現(xiàn)一種技巧，沒(méi)有什么實(shí)際意義9、按{12，24，36，90，52，30}的順序構(gòu)成的平衡二叉樹(shù)，其根結(jié)點(diǎn)是()A、24B、36C、52D、3010、長(zhǎng)度為20的有序表采用折半查找，共有()個(gè)元素的查找長(zhǎng)度為3。A、1B、2C、3D、411、下列排序方法中，時(shí)間性能與待排序記錄的初始狀態(tài)無(wú)關(guān)的是()A、插入排序和快速排序B、歸并排序和快速排序C、選擇排序和歸并排序D、插入排序和歸并排序 三、判斷題（每題1分，共10分）1、邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。（）2、線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取結(jié)構(gòu)。（）3、循環(huán)隊(duì)列的引入是為了克服假溢出。（）4、具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉子結(jié)點(diǎn)樹(shù)為50。（）5、二叉樹(shù)是度為2的樹(shù)。（）6、在線索二叉樹(shù)中，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索。（）7、圖的深度優(yōu)先遍歷類(lèi)似于樹(shù)的前序遍歷，它所用到的數(shù)據(jù)結(jié)構(gòu)是棧。（）8、在AOE網(wǎng)中一定只有一條關(guān)鍵路徑。（）9、二叉排序樹(shù)中，最小值結(jié)點(diǎn)的左指針一定為空。（）10、二叉排序樹(shù)的的查找和折半查找的時(shí)間性能相同。（）（密封線內(nèi)不要答題）………密………………（密封線內(nèi)不要答題）………密………………封………………線……………專(zhuān)業(yè)______________________班級(jí)姓名______________學(xué)號(hào)f1、對(duì)于一個(gè)n行m列的上三角矩陣A，如果以行優(yōu)先的方式用一維數(shù)組B從0號(hào)位置開(kāi)始存儲(chǔ)，，求元素aij(1≤i≤n，1≤j≤m)在數(shù)組B中的存儲(chǔ)位置。(3分)2、對(duì)下圖所示的一個(gè)無(wú)向帶權(quán)圖：(13分)(1)請(qǐng)給出該圖的鄰接矩陣存儲(chǔ)結(jié)構(gòu)表示。(2)請(qǐng)選用一種方法求出該圖的最小生成樹(shù)。(3)將(2)求出的樹(shù)轉(zhuǎn)換成二叉樹(shù)。1abedf1abedfc65526632題圖3、給定關(guān)鍵碼集合{26，25，20，34，28，24，45，64，42}，設(shè)定裝填因子為0.6。(5分)(1)請(qǐng)給出除留余數(shù)法的散列函數(shù)。(2)采用線性探測(cè)法處理沖突，試構(gòu)造閉散列表，并計(jì)算查找成功的平均查找長(zhǎng)度。4、已知數(shù)據(jù)序列為（24，10，18，40，12，62，48），對(duì)該數(shù)據(jù)序列排序，寫(xiě)出插入排序，