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

山東工商學(xué)院2020學(xué)年第一學(xué)期數(shù)據(jù)結(jié)構(gòu)課程試題A卷（考試時(shí)間：120分鐘，滿分100分）特別提醒：1、所有答案均須填寫在960數(shù)字加起來(lái)827參考答案207上，寫在試題紙上無(wú)效。2、每份答卷上均須準(zhǔn)確填寫函授站、專業(yè)、年級(jí)、學(xué)號(hào)、姓名、課程名稱。一單選題（共20題，總分值40分）一棵度為3的樹中，度為3的結(jié)點(diǎn)有2個(gè)，度為2的結(jié)點(diǎn)有2個(gè)，度為1的結(jié)點(diǎn)有2個(gè)，則度為0的結(jié)點(diǎn)有（）。（2分）5個(gè)6個(gè)C.7個(gè)D.8個(gè)設(shè)廣義表L=（（a,（））,b,（c,d,e））,則Head（Tail（Tail（L）））的值為（）。（2分）bc（c）（c,d,e）下列關(guān)于文件的說(shuō)法,錯(cuò)誤的是（）。（2分）選擇文件的組織方式時(shí)應(yīng)考慮外存的性質(zhì)和容量不定長(zhǎng)文件指的是總長(zhǎng)度可變的文件對(duì)文件的操作主要是維護(hù)和檢索文件的存儲(chǔ)結(jié)構(gòu)指的是文件在外存上的組織方式串的長(zhǎng)度是指（）。（2分）串中所含不同字母的個(gè)數(shù)串中所含字符的個(gè)數(shù)串中所含不同字符的個(gè)數(shù)串中所含非空格字符的個(gè)數(shù)在一個(gè)可存放n個(gè)數(shù)據(jù)元素的順序棧中，假設(shè)以高地址端為棧底，以top為棧頂指針，當(dāng)向棧中壓入一個(gè)數(shù)據(jù)元素時(shí)，top的變化是（）。（2分）不變top=ntop++top--設(shè)有無(wú)向圖G=（V,E）,其中頂點(diǎn)集合V={a,b,c,d,e,f},邊集合E={（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）}。對(duì)G進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（）。（2分）a,b,e,c,d,fa,c,f,e,b,da,e,b,c,f,da,e,d,f,c,b適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。（2分）鏈接方式存儲(chǔ),元素?zé)o序鏈接方式存儲(chǔ),元素有序順序方式存儲(chǔ),元素?zé)o序順序方式存儲(chǔ),元素有序順序表中數(shù)據(jù)元素的存取方式為（）。（2分）A.隨機(jī)存取順序存取索引存取D.連續(xù)存取將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，最少進(jìn)行（）次比較。（2分）n2n-12nn-1下列排序算法中（）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。（2分）快速排序shell排序堆排序冒泡排序一棵二叉樹中第6層上最多有（）個(gè)結(jié)點(diǎn)。（2分）2313264下列說(shuō)法中錯(cuò)誤的是（）。（2分）數(shù)據(jù)對(duì)象是數(shù)據(jù)的子集數(shù)據(jù)元素間關(guān)系在計(jì)算機(jī)中的映象即為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)非順序映象的特點(diǎn)是借助指示元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素間邏輯關(guān)系抽象數(shù)據(jù)類型指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作串是一種特殊的線性表，其特殊性體現(xiàn)在（）。（2分）可以順序存儲(chǔ)數(shù)據(jù)元素是一個(gè)字符可以鏈接存儲(chǔ)數(shù)據(jù)元素可以是多個(gè)字符設(shè)表中含100個(gè)數(shù)據(jù)元素，用折半查找法進(jìn)行查找，則所需最大比較次數(shù)為（）。（2分）5025107下述文件中適合于磁帶存儲(chǔ)的是（）。（2分）A.順序文件B.索引文件C.散列文件多關(guān)鍵字文件設(shè)在一不帶頭結(jié)點(diǎn)的鏈隊(duì)列中，front和rear分別為其隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作是（）。（2分）rear=front->nextrear=rear->nextfront=front->nextfront=rear->next設(shè)有向圖G中有五個(gè)頂點(diǎn)，各頂點(diǎn)的度分別為3、2、2、1、2,則G中弧數(shù)為（）。（2分）TOC\o"1-5"\h\z4條5條6條D.無(wú)法確定在待排元素序列基本有序的前提下，效率最高的排序方法是（）。（2分）插入選擇快速歸并設(shè)串s='abcdefgh'，則其子串?dāng)?shù)為（）。（2分）TOC\o"1-5"\h\z837369設(shè)哈希表地址范圍為0~19，哈希函數(shù)H(key)=key%17,使用二次探測(cè)再散列法處理沖突。若表中已存放有關(guān)鍵字值為6、22、38、55的記錄，則再放入關(guān)鍵字值為72的記錄時(shí)，其存放地址應(yīng)為()。(2分)A.2B.3478F.以上都不對(duì)二簡(jiǎn)答題(共6題，總分值60分)設(shè)有上三角矩陣(aij)nXn,將其上三角元素逐行存于數(shù)組B[m]中(m充分大)，使得B[k]=aij,求用i和j表示k的下標(biāo)變換公式。(10分)已知單鏈表L中含有三類字符的數(shù)據(jù)元素，即字母字符、數(shù)字字符和其他字符，試編寫算法將L分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表只含一類字符。(10分)設(shè)給定關(guān)鍵字序列(68,55,27,43,58,12)，試構(gòu)造平衡的二叉查找樹。(10分)設(shè)二叉樹以二叉鏈表存儲(chǔ)，試設(shè)計(jì)算法，實(shí)現(xiàn)二叉樹的層序遍歷。(10分，設(shè)a='datastructure'，b='computer'，c='demo'，試求：⑴StrLength(a)的返回值；⑵執(zhí)行Strlnsert(b,4,c)后串b的值；⑶lndex(a,'u',1O)的返回值；⑷執(zhí)行Replace(a,'structure',b)后串a(chǎn)的值；⑸執(zhí)行SubString(s,b,3,3)后串s的值。(10分)設(shè)內(nèi)存有大小為5個(gè)記