江南大学现代远程教育-2015数据结构第1阶段测试题1b

江南大学现代远程教育 第一阶段测试卷考试科目:数据结构第一章至第四章（总分100分） 时间：90分钟_学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、选择题（每题3分，共30分）1、在树形结构中，数据元素间存在（B）的关系。、一对一、一对多、多对多、除同属一个集合外别无关系2、下列说法中错误的是（B）。、数据对象是数据的子集、数据元素间关系在计算机中的映象即为数据的存储结构、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系、抽象数据类型指一个数学模型及定义在该模型上的一组操作3、下列不属算法特性的是（D）。、有穷性、确定性、零或多个输入、健壮性4、在长为n的顺序表中删除一个数据元素，平均需移动（D）个数据元素。、n、n-1、n/2、(n-1)/25、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。、顺序表、双链表、带头结点的双向循环链表、单循环链表6、在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（D）。、不变、top=n、top+、top-7、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（C）。、rear=front-next、rear=rear-next、front=front-next、front=rear-next8、判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（D）。、S、S-next、S-next=NULL、!S9、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（C）。、front-next、rear-next、front=rear、front!=rear10、串的长度是指（B）。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数二、（10分）设为正整数，试确定如下程序段中语句“x+;”的频度。for (i=1;i=n;i+)for (j=1;j=i;j+)for (k=1;k=n;k+)x+;答：n2(n+1)/2三、（15分）设单链表如图所示：画出执行如下程序段后，各指针变量及单链表的示意图。p=L;for(i=1;idata=i*3;q-next=p-next;p-next=q;答：369四、（10分）设元素的入栈次序为a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。答：dabc dbac dbca cadb cdab bdac adbc五、（15分）设a=data structure，b=computer，c=demo，试求： StrLength(a)的返回值； 执行StrInsert(b,4,c)后串b的值； Index(a,u,10)的返回值； 执行Replace(a,structure,b)后串a的值； 执行SubString(s,b,3,3)后串s的值。答：14 comdemoputer 12 data computer mpu六、（20分）已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将L分割为三个循环链表，其中每个循环链表只含一类字符。答：Void parition(LinkList &L,LinkList &LC,