数据结构第1阶段测试题.doc

江南大学现代远程教育 第一阶段测试卷 考试科目:《数据结构》第一章至第四章（总分100分） 时间：90分钟 ______________学习中心（教学点） 批次： 层次： 专业： 学号： 身份证号： 姓名： 得分： 一、选择题（每题3分，共30分） 1、（　　）是数据的不可分割的最小单位。 Ａ、数据元素　Ｂ、数据对象　Ｃ、数据项　Ｄ、数据结构 2、若采用顺序映象，则数据元素在内存中占用的存储空间（　　）。 Ａ、一定连续　Ｂ、一定不连续　Ｃ、可连续可不连续 3、下列说法中错误的是（　　）。 Ａ、栈是一种非线性结构 Ｂ、一个数据元素由一或多个数据项构成 Ｃ、在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现 Ｄ、语句的频度就是语句的执行次数 4、以下属单链表优点的是（　　）。 Ａ、顺序存取　Ｂ、插入操作能在O(1)的时间复杂度上完成 Ｃ、插入时不需移动数据元素　Ｄ、节省存储空间 5、顺序表中数据元素的存取方式为（　　）。 Ａ、随机存取　Ｂ、顺序存取　Ｃ、索引存取　Ｄ、连续存取 6、设输入序列为ABC，输出序列为CBA，则经过的栈操作为（　　）。 Ａ、push,pop,push,pop,push,pop　Ｂ、push,push,push,pop,pop,pop Ｃ、push,push,pop,pop,push,pop　Ｄ、push,pop,push,push,pop,pop 7、若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（　　）。 Ａ、1和5　Ｂ、2和4　Ｃ、4和2　Ｄ、5和1 8、串是一种特殊的线性表，其特殊性体现在（　　）。 Ａ、可以顺序存储　Ｂ、数据元素是一个字符 Ｃ、可以链接存储　Ｄ、数据元素可以是多个字符 9、设串s=abcdefgh，则其子串数为（　　）。 Ａ、8　Ｂ、37　Ｃ、36　Ｄ、9 10、设串s1=abcdefg，s2=ab，则Concat(s1,s2)的返回值（　　）。 Ａ、ab　Ｂ、cdefg　Ｃ、abcdefg　Ｄ、abcdefgab 二、（10分）设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？ for(x=0;xn;++x) for(y=0;yn;++y) a+=2; 三、（15分）设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。 ⑴在p所指结点之前插入s所指结点； ⑵在L中最后一个结点之后插入s所指结点； ⑶删除p所指结点的直接后继； ⑷删除L中第一个结点。 四、（10分）有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 五、（15分）设a=colomn，b=How are you!，c=please，试求： ⑴ StrLength(b)的返回值； ⑵ Index(a,o,5)的返回值； ⑶ 执行StrInsert(a,3,c)后串a的值； ⑷ 执行Replace(c,e,x)后串c的值； ⑸ 执行SubString(s,b,5,3)后串s的值。 六、（20分）假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。 答案： 一、选择题（每题3分，共30分） C、A、A、C、A、B、B、B、B、D 二、设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？ for(x=0;xn;++x) for(y=0;yn;++y) a+=2; 答：n2 三、设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。 ⑴在p所指结点之前插入s所指结点； ⑵在L中最后一个结点之后插入s所指结点； ⑶删除p所指结点的直接后继； ⑷删除L中第一个结点。 答： ⑴q=L; while(q-next!=p)q=q-next; //q指向p的直接前驱 s-next=p; q-next=s; ⑵q=L; while(q-next)q=q-n