09级计本数据结构期中考试卷(含答案)

09级计本数据结构期中考试卷(含答案)LtD计算机（本科）2009级《数据结构/》试卷第4页（共4页）考试时间2010年考试时间2010年11月11日下午系(院):年级:专业:班别:学号:姓名:座位号:——————————————————————————————————————————————————————密封线内不要答题∞装订∞线∞（2010——2011学年度第一学期）命题教师：刘恒命题教师所在系：数计系课程名称：数据结构考试专业：计算机考试年级：09级题号一二三四五总分应得分3010104010满分：100实得分评分：评卷人签名一、单项选择题（每题2分，共30分，把正确答案填入表格中）12345678BCDACBDA9101112131415CBADCBA1、下列哪项不是衡量算法优劣的标准()。A、健壮性B、可行性C、可读性D、效率与低存储量2、设n为正整数，则下列程序段中前置以记号@的语句频度为()。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、数据元素同构。B、数据元素个数n为表长度。C、当n=0时，线性表为空表。D、数据项能出现缺项。4、在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。A、基地址和结点大小B、结点大小C、基地址D、向量大小5、在()运算中，使用顺序表比链表好。A、插入B、删除C、根据序号查找D、根据元素值查找6、设N为正整数，试确定下列程序段中前置以记号@语句的频度为()。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、二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标的范围从1到10，则存放M至少需要多少个字节？若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先的方式存储时的什么元素的起始地址一致？540个字节。（2分）M[3][10]（3分）7、请画出下列稀疏矩阵的十字链表。（答案略）8、设head[p]为求广义表p的表头函数，tail[p]为求广义表p的表尾函数，其中[]是函数符号，给出下列广义表的运算结果。(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中的数据元素非递减有序。写一算法将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