09級計本數(shù)據(jù)結構期中考試卷(含答案)

09級計本數(shù)據(jù)結構期中考試卷(含答案)LtD計算機（本科）2009級《數(shù)據(jù)結構/》試卷第4頁（共4頁）考試時間2010年考試時間2010年11月11日下午系(院):年級:專業(yè):班別:學號:姓名:座位號:——————————————————————————————————————————————————————密封線內不要答題∞裝訂∞線∞（2010——2011學年度第一學期）命題教師：劉恒命題教師所在系：數(shù)計系課程名稱：數(shù)據(jù)結構考試專業(yè)：計算機考試年級：09級題號一二三四五總分應得分3010104010滿分：100實得分評分：評卷人簽名一、單項選擇題（每題2分，共30分，把正確答案填入表格中）12345678BCDACBDA9101112131415CBADCBA1、下列哪項不是衡量算法優(yōu)劣的標準()。A、健壯性B、可行性C、可讀性D、效率與低存儲量2、設n為正整數(shù)，則下列程序段中前置以記號@的語句頻度為()。k=0;for(i=1;i<=n;i++){for(j=i;j<=n;j++)@k++;}A、B、n-1C、n(n+1)/2D、3、關于線性表的說法，下列哪個是不正確的()。A、數(shù)據(jù)元素同構。B、數(shù)據(jù)元素個數(shù)n為表長度。C、當n=0時，線性表為空表。D、數(shù)據(jù)項能出現(xiàn)缺項。4、在順序表中，只要知道()，就可在相同時間內求出任一結點的存儲地址。A、基地址和結點大小B、結點大小C、基地址D、向量大小5、在()運算中，使用順序表比鏈表好。A、插入B、刪除C、根據(jù)序號查找D、根據(jù)元素值查找6、設N為正整數(shù)，試確定下列程序段中前置以記號@語句的頻度為()。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個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到8，列下標的范圍從1到10，則存放M至少需要多少個字節(jié)？若M按行優(yōu)先方式存儲，元素M[8][5]的起始地址與當M按列優(yōu)先的方式存儲時的什么元素的起始地址一致？540個字節(jié)。（2分）M[3][10]（3分）7、請畫出下列稀疏矩陣的十字鏈表。（答案略）8、設head[p]為求廣義表p的表頭函數(shù)，tail[p]為求廣義表p的表尾函數(shù)，其中[]是函數(shù)符號，給出下列廣義表的運算結果。(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分）五、算法設計題：設順序表Va中的數(shù)據(jù)元素非遞減有序。寫一算法將x插入到順序表的適當位置上，以保持該表的有序性。（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