数据结构第1阶段练习题答案 江南大学2022年秋季

第10页/共NUMPAGES\*ARABIC10页江南大学网络教育第一阶段练习题答案，答案在最后一页。考试科目:《数据结构》第章至第章（总分100分）__________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一单选题(共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)1.设输入序列为ABC，输出序列为CBA，则经过的栈操作为（）。（2分）A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop2.设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（）。（2分）A.abB.cdefgC.abcdefgD.abcdefgab3.若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。（2分）A.1和5B.2和4C.4和2D.5和14.下列说法中错误的是（）。（2分）A.栈是一种非线性结构B.一个数据元素由一或多个数据项构成C.在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现D.语句的频度就是语句的执行次数5.串是一种特殊的线性表，其特殊性体现在（）。（2分）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符6.（）是数据的不可分割的最小单位。（2分）A.数据元素B.数据对象C.数据项D.数据结构7.顺序表中数据元素的存取方式为（）。（2分）A.随机存取B.顺序存取C.索引存取D.连续存取8.以下属单链表优点的是（）。（2分）A.顺序存取B.插入操作能在O(1)的时间复杂度上完成C.插入时不需移动数据元素D.节省存储空间9.若采用顺序映象，则数据元素在内存中占用的存储空间（）。（2分）A.一定连续B.一定不连续C.可连续可不连续10.设串s='abcdefgh'，则其子串数为（）。（2分）A.8B.37C.36D.9二多选题(共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)11.下列说法正确的是（）。（2分）A.在图形结构中，结点之间的关系可以是任意的;B.在树形结构中，数据元素之间没有明显的层次关系;C.在树形结构中，数据元素之间仅有线性关系;D.在线性表中，数据元素之间仅有线性关系12.算法设计的要求包括（）。（2分）A.正确性;B.可读性;C.健壮性;D.确定性13.两串相等必须有（）。（2分）A.串长度相等;B.串中各位置字符任意;C.串中各位置字符均对应相等;D.串长度不等;E.串长度任意14.下列属于算法的重要特征的是（）。（2分）A.有穷性;B.确定性;C.可行性;D.输入和输出15.下列不是顺序存储结构优点的有（）。（2分）A.存储密度大;B.插入运算方便;C.可方便的用于各种逻辑结构的存储表示;D.删除运算方便三判断题(共10题，总分值10分正确的填涂“A”，错误的填涂“B”。)16.循环链表可以做到从任一结点出发，访问到链表的全部结点。（1分）（

）17.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（1分）（

）18.在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。（1分）（

）19.算法分析的两个主要方面是时间复杂度和空间复杂度的分析。（1分）（

）20.若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。（1分）（

）21.2N和NN具有相同的增长速度。（1分）（

）22.n个元素进队的顺序和出队的顺序总是一致的。（1分）（

）23.单链表中引入头结点会使结点插入操作的时间复杂度降为常数阶。（1分）（

）24.所谓随机存取，就是通过首地址和元素的位序号值可以在O(1)的时间内找到指定的元素。（1分）（

）25.线性表采用链式存储表示时，所有结点之间的存储单元地址可以连续也可以不连续。（1分）（

）四简答题(共2题，总分值20分)26.设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？for(x=0;x<n;++x)for(y=0;y<n;++y)a+=2;（10分）27.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？（10分）五综合题(共3题，总分值40分)28.设a='colomn'，b='How

areyou!'，c='please'，试求：（1）StrLength(b)的返回值；（2）Index(a,'o',5)的返回值；（3）执行StrInsert(a,3,c)后串a的值；（4）执行Replace(c,'e','x')后串c的值；（5）执行SubString(s,b,5,3)后串s的值。（13分）29.设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。⑴在p所指结点之前插入s所指结点；⑵在L中最后一个结点之后插入s所指结点；⑶删除p所指结点的直接后继；⑷删除L中第一个结点。（13分）30.假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。（14分）

一单选题(共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。)1.参考答案为：B解析过程：2.参考答案为：D解析过程：3.参考答案为：B解析过程：4.参考答案为：A解析过程：5.参考答案为：B解析过程：6.参考答案为：C解析过程：7.参考答案为：A解析过程：8.参考答案为：C解析过程：9.参考答案为：A解析过程：10.参考答案为：B解析过程：二多选题(共5题，总分值10分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。)11.参考答案为：A,B,D解析过程：12.参考答案为：A,B,C解析过程：13.参考答案为：A,C解析过程：14.参考答案为：A,B,C,D解析过程：15.参考答案为：B,C,D解析过程：三判断题(共10题，总分值10分正确的填涂“A”，错误的填涂“B”。)16.参考答案为：T解析过程：17.参考答案为：F解析过程：18.参考答案为：F解析过程：19.参考答案为：T解析过程：20.参考答案为：F解析过程：21.参考答案为：F解析过程：22.参考答案为：T解析过程：23.参考答案为：F解析过程：24.参考答案为：T解析过程：25.参考答案为：T解析过程：四简答题(共2题，总分值20分)26.参考答案为：答：n2解析过程：27.参考答案为：答：CDEBACDBEACDBAE解析过程：五综合题(共3题，总分值40分)28.参考答案为：（1）12（2）0（3）’copleaselomn’（4）’plxasx’（5）’are’解析过程：29.参考答案为：⑴q=L;while(q->next!=p)q=q->next;//q指向p的直接前驱s->next=p;q->next=s;⑵q=L;while(q->next)q=q->next;s->next=NULL;q->next=s;⑶q=p->next;//q指向待删结点p->next=q->next;free(q);⑷q=L->next;L->next=q->next;free(q);解析过程：30.参考答案为：#defineMAXQSIZE100typedefstruct{ElemTypebase[MAXQSIZE];intrear;intlength;}Queue;StatusEnQueue(Queue&Q,ElemTypee){if(Q.length==MAXQSIZE)returnERROR;Q.rear