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

1、山東工商學(xué)院2020學(xué)年第一學(xué)期數(shù)據(jù)結(jié)構(gòu)課程試題A卷（考試時(shí)間：120分鐘，滿分100分）特別提醒：1、所有答案均須填寫(xiě)在960數(shù)字加起來(lái)827參考答案207上，寫(xiě)在試題紙上無(wú)效。2、每份答卷上均須準(zhǔn)確填寫(xiě)函授站、專(zhuān)業(yè)、年級(jí)、學(xué)號(hào)、姓名、課程名稱。一單選題（共20題，總分值40分）一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)有2個(gè)，度為2的結(jié)點(diǎn)有2個(gè)，度為1的結(jié)點(diǎn)有2個(gè)，則度 為0的結(jié)點(diǎn)有（）。（2分） TOC o 1-5 h z 5個(gè)6個(gè)7個(gè)8個(gè)設(shè)廣義表 L=（a,（）,b,（c,d,e），則 Head（Tail（Tail（L）的值為（）。（2 分）bc（c）（c,d,e）下列關(guān)于文件的說(shuō)法，錯(cuò)誤的是（）

2、。（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）, （

3、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分）隨機(jī)存取順序存取索引存取連續(xù)存取將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，最少進(jìn)行（）次比較。（2分） TOC o 1-5 h z n2n-12nn-1下列排序算法中（）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。（2分）快速排序shell 排序堆排序

4、冒泡排序一棵二叉樹(shù)中第6層上最多有（）個(gè)結(jié)點(diǎn)。（2分） TOC o 1-5 h z 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ù)類(lèi)型指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作串是一種特殊的線性表，其特殊性體現(xiàn)在（）。（2分）可以順序存儲(chǔ)數(shù)據(jù)元素是一個(gè)字符可以鏈接存儲(chǔ)數(shù)據(jù)元素可以是多個(gè)字符設(shè)表中含100個(gè)數(shù)據(jù)元素，用折半查找法進(jìn)行查找，則所需最大比較次數(shù)為（）。（2分） TOC o 1-5 h z 5025107下述文件中適合于磁帶存儲(chǔ)的是（）。（2分）

5、順序文件索引文件散列文件多關(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 z 4條5條6條無(wú)法確定在待排元素序列基本有序的前提下，效率最高的排序方法是（）。（2分）插入選擇快速歸并設(shè)串s=abcdefgh，則其子串?dāng)?shù)為（）。（2分） TOC o 1-5 h z 837369設(shè)哈希表地址范圍為01

6、9，哈希函數(shù)H（key）=key%17,使用二次探測(cè)再散列法處理沖突。若表 中已存放有關(guān)鍵字值為6、22、38、55的記錄，則再放入關(guān)鍵字值為72的記錄時(shí)，其存放地址應(yīng) 為（）。（2分） TOC o 1-5 h z 23478以上都不對(duì)二簡(jiǎn)答題供6題，總分值60分）設(shè)有上三角矩陣（aij）nXn,將其上三角元素逐行存于數(shù)組Bm中（m充分大），使得Bk=aij, 求用i和j表示k的下標(biāo)變換公式。（10分）已知單鏈表L中含有三類(lèi)字符的數(shù)據(jù)元素，即字母字符、數(shù)字字符和其他字符，試編寫(xiě)算法將 L分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表只含一類(lèi)字符。（10分）設(shè)給定關(guān)鍵字序列（68, 55, 27, 43, 58, 12），試構(gòu)造平衡的二叉查找樹(shù)。（10分）設(shè)二叉樹(shù)以二叉鏈表存儲(chǔ)，試設(shè)計(jì)算法，實(shí)現(xiàn)二叉樹(shù)的層序遍歷。（10分）設(shè) a=data structure，b=computer，c=demo，試求：StrLength（a）的返回值；執(zhí)行StrInsert（b,4,c）后串b的值；Index（a,u,10）的返回值； 執(zhí)行 Replace（a,structure,b）后串 a 的值； 執(zhí)行 SubString（s,b,3,3）后串 s 的值。（10 分）設(shè)內(nèi)存有大小為5個(gè)記錄的