09級(jí)計(jì)本數(shù)據(jù)結(jié)構(gòu)期中考試卷(含答案)

計(jì)算機(jī)（本科）2009級(jí)《數(shù)據(jù)結(jié)構(gòu)/》試卷第3頁(yè)（共4頁(yè)）考試時(shí)間2010年考試時(shí)間2010年11月11日下午系(院):年級(jí):專業(yè):班別:學(xué)號(hào):姓名:座位號(hào):——————————————————————————————————————————————————————密封線內(nèi)不要答題∞裝訂∞線∞（2010——2011學(xué)年度第一學(xué)期）命題教師：劉恒命題教師所在系：數(shù)計(jì)系課程名稱：數(shù)據(jù)結(jié)構(gòu)考試專業(yè)：計(jì)算機(jī)考試年級(jí)：09級(jí)題號(hào)一二三四五總分應(yīng)得分3010104010滿分：100實(shí)得分評(píng)分：評(píng)卷人簽名一、單項(xiàng)選擇題（每題2分，共30分，把正確答案填入表格中）12345678BCDACBDA9101112131415CBADCBA1、下列哪項(xiàng)不是衡量算法優(yōu)劣的標(biāo)準(zhǔn)()。A、健壯性B、可行性C、可讀性D、效率與低存儲(chǔ)量2、設(shè)n為正整數(shù)，則下列程序段中前置以記號(hào)@的語(yǔ)句頻度為()。k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}A、B、n-1C、n(n+1)/2D、3、關(guān)于線性表的說(shuō)法，下列哪個(gè)是不正確的()。A、數(shù)據(jù)元素同構(gòu)。B、數(shù)據(jù)元素個(gè)數(shù)n為表長(zhǎng)度。C、當(dāng)n=0時(shí)，線性表為空表。D、數(shù)據(jù)項(xiàng)能出現(xiàn)缺項(xiàng)。4、在順序表中，只要知道()，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A、基地址和結(jié)點(diǎn)大小B、結(jié)點(diǎn)大小C、基地址D、向量大小5、在()運(yùn)算中，使用順序表比鏈表好。A、插入B、刪除C、根據(jù)序號(hào)查找D、根據(jù)元素值查找6、設(shè)N為正整數(shù)，試確定下列程序段中前置以記號(hào)@語(yǔ)句的頻度為()。x=91;y=100;while(y>0){@if(x>100){x-=10;y-=2;}elsex++;}A、1100B、550C、110D、557、“假上溢”現(xiàn)象會(huì)出現(xiàn)在()中。A、循環(huán)隊(duì)列B、鏈隊(duì)列C、棧D、順序隊(duì)列8、對(duì)單鏈表執(zhí)行下列程序段，請(qǐng)選出不正確的一項(xiàng)()。H2H234555┅690^PQRST=Q;While(T->next!=NULL){T->data=T->data*3;T=T->next;}A、R->data=27B、Q->data=12C、H->data=2D、P->data=39、一個(gè)棧的入棧序列是abcde，則棧的不可能的輸出序列是()。A、edcbaB、decbaC、dceabD、abcde10、在一個(gè)鏈隊(duì)中，假設(shè)F和R分別是隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算是()。A、R=F->next;B、F=F->next;C、R=R->next;D、F=R->next;11、串是一種特殊的線性表，其特殊性體現(xiàn)在()。A、數(shù)據(jù)元素是一個(gè)字符B、可以順序存儲(chǔ)C、可以鏈接存儲(chǔ)D、數(shù)據(jù)元素可以是多個(gè)字符12、設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。A、線性表的順序存儲(chǔ)結(jié)構(gòu)B、隊(duì)列C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、棧13、設(shè)數(shù)組B[1..3，1..5]中的任一元素均占4個(gè)單元，從首地址SA=2010開(kāi)始把數(shù)組B按列優(yōu)先存儲(chǔ)，則元素B[2，4]的地址為()。A、2042B、2074C、2050D、210814、對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了()。A、便于進(jìn)行矩陣運(yùn)算B、節(jié)約存儲(chǔ)空間C、便于輸入和輸出D、降低運(yùn)算的時(shí)間復(fù)雜度15、下列說(shuō)法哪個(gè)是不正確的：()。A、廣義表(((a)))的表頭是(a)。B、廣義表((a),((b),c),(((d))))長(zhǎng)度為3。C、廣義表((a),((b),c),(((d))))深度為4。D、廣義表((a),((b),c),(((d))))的表尾是(((b),c),(((d))))。二、填空題（每題1分，共10分）數(shù)據(jù)結(jié)構(gòu)是一門研究____________的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。（非數(shù)值計(jì)算）空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度，記作____________。（S(n)=O(f(n))）一個(gè)順序表的開(kāi)始地址是1000，每個(gè)元素的長(zhǎng)度是8，則第7個(gè)元素的存儲(chǔ)地址是____________。（1048）在無(wú)頭結(jié)點(diǎn)的單鏈表中，第1個(gè)結(jié)點(diǎn)的地址存放在頭指針中，其他結(jié)點(diǎn)的存儲(chǔ)地址存放在____________結(jié)點(diǎn)的next域中。（前驅(qū)）當(dāng)程序中同時(shí)使用____________個(gè)棧時(shí)，讓它們共享同一向量空間可減少上溢的發(fā)生。（2）假設(shè)以數(shù)組Sq[M]存放循環(huán)隊(duì)列，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含的元素個(gè)數(shù)，則判別隊(duì)滿的條件是____。（quelen==M）假設(shè)每個(gè)字符占1個(gè)字節(jié)，若結(jié)點(diǎn)大小為4的鏈串的存儲(chǔ)密度為50%，則其每個(gè)指針占____________個(gè)字節(jié)。（4）在多維數(shù)組中，數(shù)據(jù)元素的存放地址直接可通過(guò)地址計(jì)算公式計(jì)算出。因此，數(shù)組是一種____________存取結(jié)構(gòu)。（隨機(jī)）矩陣的壓縮存儲(chǔ)就是為多個(gè)相同的非零元素分配_________個(gè)存儲(chǔ)空間，不為零元素分配空間。（1）10、廣義表是線性表的推廣，它們之間的區(qū)別在于_________。（能否使用子表）三、名詞解釋（每題2分，共10分）1、算法的可行性一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。（2分）2、數(shù)據(jù)項(xiàng)有獨(dú)立含義的數(shù)據(jù)最小單位，也稱域。（2分）3、順序表用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表稱為順序表。（2分）4、隊(duì)列隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。（2分）5、空串零個(gè)字符的串稱為空串。（2分）（答案略）8、設(shè)head[p]為求廣義表p的表頭函數(shù)，tail[p]為求廣義表p的表尾函數(shù)，其中[]是函數(shù)符號(hào)，給出下列廣義表的運(yùn)算結(jié)果。(1)head[tail[(a,b,c)]](2)tail[head[((a,b),(c,d))]](3)head[head[((a,b),(c,d))]](1)b(1分)(2)(b)（2分）(3)a（2分）五、算法設(shè)計(jì)題：設(shè)順序表Va中的數(shù)據(jù)元素非遞減有序。寫(xiě)一算法將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。（10分）statusinsertorderlist(sqlist&a,elemtypex)（1分）{if(a.length==a.listsize)return(overflow);（1分）else{i=a.length-1;（1分）while(i>=0&&x<a.elem[i])i--;（1分）for(j=a.length-1;j>=i+1;j--)