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

09級(jí)計(jì)本數(shù)據(jù)結(jié)構(gòu)期中考試卷(含答案)LtD計(jì)算機(jī)（本科）2009級(jí)《數(shù)據(jù)結(jié)構(gòu)/》試卷第4頁(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)@的語句頻度為()。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)于線性表的說法，下列哪個(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)@語句的頻度為()。intIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(_________){++i;++j;}else{_________;j=1;}}if(j>T[0])returni-T[0];elsereturn0;}S[i]==T[j](2分)i=i-j+2(3分)6、二維數(shù)組M的成員是6個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)的范圍從1到10，則存放M至少需要多少個(gè)字節(jié)？若M按行優(yōu)先方式存儲(chǔ)，元素M[8][5]的起始地址與當(dāng)M按列優(yōu)先的方式存儲(chǔ)時(shí)的什么元素的起始地址一致？540個(gè)字節(jié)。（2分）M[3][10]（3分）7、請(qǐng)畫出下列稀疏矩陣的十字鏈表。（答案略）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ù)元素非遞減有序。寫一算法將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--)（1分）a.elem[j+1]=a.elem[j];（2分）a.elem[i