2002级数据结构及算法分析半期试题

1四川大学计算机学院2002级数据结构及算法分析半期试题学院____________学号___________________姓名_________________一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）1．假设执行语句S的时间为O（1），则执行下列程序段for(i=1;i=n;i++)for(j=i;j=n;j++)S;的时间为()A）O（n）B）O（n2）C）O（n*i）D）O（n+i）2．设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能的出栈序列是（）。A）1，2，3，4，5，6B）2，1，3，4，5，6C）3，4，2，1，5，6D）4，3，2，1，5，63．设单链表的结点结构为(data,next)，已知指针q所指结点是指针p所指结点的直接前驱，如在*q与*p之间插入结点*s，则应执行的操作为（）。A）s-next=p-next;p-next=s;B）q-next=s;s-next=p;C）p-next=s-next;s-next=p;D）p-next=s;s-next=q;4．串S=”ABCDEF”的串长为（）。A）3B）4C）7D）85．若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是()。A)O(1)B)O(n)C)O(n2)D)O(nlog2n)6．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较()。个结点。A)nB)n／2C)(n-1)／2D)(n+1)／27．研究数据结构就是研究()。A．数据的逻辑结构B．数据的存储结构C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其数据在运算上的实现8．二维数组A[10．．20，5．．10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的地址是（）。A）1208B）1212C）1368D）136429．利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：L1(apple,pear,banana,orange)A）Head(Tail(Tail(L1)))B）Head(Head(Tail(Tail(L1))))C）Head(Tail(Tail(Tail(L1))))D）Head(Head(Tail(L1)))10．如下陈述中正确的是（）。A）串是一种特殊的线性表B）串的长度必须大于零C）串中的元素只能是字母D）空串就是空白串二、填空题（每空1分，共15分）1．当一个传值型形式参数所占空间较大时，最好说明为()，以节省参数值传输时间和存储参数的空间。2．一个算法的时间复杂度为(5n6-3n2log2n+7n-9)/(3n2+1)，其数量级表示为()。3．有一矩阵为a[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a(-1,4)的地址为（）。4．一维数组的逻辑结构是（）。5．在有n个结点的单链表la中，删除指定结点p的操作delete(la,p)的时间复杂度为（）。6．栈的插入与删除操作在()进行，出栈操作时，需要修改()。7．表达式3*(x+2)-5的后缀表达式为（）。8．假设有一个9阶上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[0]存储矩阵中第一个元素A1,1，则B[31]中存放的元素是()。9．数据的逻辑结构是从逻辑关系上描述数椐，它与数据的()无关，是独立于计算机的。10．设head为单链表的头结点，则判断单链表为空的条件是()。11．在具有n个单元的循环队列中，队满时共有()个元素。12．设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈序列为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为（）。13．广义表A=(a，b，A)的长度为()，其深度为()。三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）1．数据的逻辑结构是指数据元素之间的逻辑关系。（）2．数组不是一种随机存取结构。（）3．顺序表在物理存储空间中一定是连续的。（）4．设一个栈的入栈序列是ABCD，则借助于一个栈能得出栈序列ACDB。（）5．串的长度是指串中不同字符的个数。（）36．矩阵压缩存储的方法都是用三元组表存储矩阵元素。（）7．具有线性序关系的集合中，若a，b是集合中的任意两个原子，则必定有ab的关系。（）8．算法和程序没有区别，所以在数据结构中二者是通用的。（）9．在顺序表中取出第i个元素所花费时间与i成正比。（）10．队列和栈都是运算受限的线性表。（）四、简答题（每小题4分，共20分）1．在双向循环链表中p所指结点之后插入s所指结点，设结点结构为(priou,data,next)，试给出语句序列。2．已知串a=“1234+-*”、b=“1+2-3*4”，请用串的各种基本运算将串a转换为串b。规定：运算中不能引入新的字符串，所有的字符串只能从串a中取得。3．写出下列中缀表达式的后缀形式：(1)(A+B)*D+E/(F+A*D)+C(2)A&&B||!(EF)/*注：按C++的优先级*/4．画出下列广义表的图形表示和它们的存储表示：(1)D(A(c),B(e),C(a,L(b,c,d)))(2)J1(J2(J1,a,J3(J1)),J3(J1))5．稀疏矩阵的三元组表可以用带行指针数组的二元组表代替。稀疏矩阵有多少行，在行指针数组中就有多少个元素：第i个元素的数组下标i代表矩阵的第i行，元素的内容即为稀疏矩阵第i行的第一个非零元素在二元组表中的存放位置。二元组表中每个二元组只记录非零元素的列号和元素值，且各二元组按行号递增的顺序排列。试对右图所示的稀疏矩阵，分别建立它的三元组表和带行指针数组的二元组表。五、算法题（共25分）1．程序填空题(每空2分，共8分)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同，如果last不合理则显示出错信息并退出运行，实现从表中删除所有其值重复的元素的函数如下：templateTypevoidSeqListType::DelDouble(){if(last==-1){cerr“Listisempty!”endl;____________;}inti=0,j,k;Typetemp;while(i=last){//循环检测j=i+1;temp=data[i];while(__________){//对于每一个i,重复检测一遍后续元素if(temp==data[j]){//如果相等,后续元素前移for(k=j+1;k=last;k++)________________;last--;//表最后元素位置减14}else________}i++;//检测完data[i],检测下一个}}2．程序填空题(每空2分，共8分)编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。includeiostream.hincludestring.hvoidfrequency(String&s,char&A[],int&C[],int&k){//s是输入字符串，数组A[]中记录字符串中有多少种不同的字符，C[]中记录每//一种字符的出现次数。这两个数组都应在调用程序中定义。k返回不同字符数。inti,j,len=s.length();if(!len){coutThestringisempty.endl;k=0;return;}else{A[0]=s[0];C[0]=1;k=1;/*语句s[i]是串的重载操作*/for(i=1;ilen;i++)__________;/*初始化*/for(i=1;ilen;i++){/*检测串中所有字符*/j=0;while(jk&&A[j]!=s[i])j++;/*检查s[i]是否已在A[]中*/if(j==k){___________;C[k]++;__________}/*s[i]从未检测过*/else____________;/*s[i]已经检测过*/}}}测试数据s=castcastsatatatasa\0AcastbC274553．(9分)阅读下面的算法，试回答：（1）此算法的功能是什么？（2），若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为：String&String::Replace(String&t,String&v){if((intid=Find(t))==-1)//没有找到，当前字符串不改，返回{coutThe(replace)operationfailed.endl;return*this;}测试结果5Stringtemp(ch);//用当前串建立一个空的临时字符串ch[0]='\0';curLen=0;//当前串作为结果串，初始为空intj,k=0,l;//存放结果串的指针while(id!=-1){for(j=0;jid;j++)ch[k++]=temp.ch[j];//摘取temp.ch中匹配位置if(curLen+id+v.curLen=maxLen)l=v.curLen;//确定替换串v传送字符数lelsel=maxLen-curLen-id;for(j=0;jl;j++)ch[k++]=v.ch[j];//连接替换串v到结果串ch后面curLen+=id+l;//修改结果串连接后的长度if(curLen==maxLen)break;//字符串超出范围for(j=id+t.curLen;jtemp.curLen;j++)temp.ch[j-id-t.curLen]=temp.ch[j];//删改原来的字符串temp.curLen-=id+t.curLen;id=temp.Find(t);}return*this;}六、写算法（共20分）1．(12分)设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。2．(8分)若使用循环链表来表示队列，p是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空。【解答】链式队列的类定义templateclassTypeclassQueue;//链式队列类的前视定义templateclassTypeclassQueueNode{//链式队列结点类定义friendclassQueueType;private:Typedata;//数据域6QueueNodeType*link;//链域public:QueueNode(Typed=0,QueueNode*l=NULL):data(d),link(l){}//构造函数};templateclassTypeclassQueue{//链式队列类定义public:Queue():p(NULL){}//构造函数~Queue();//析构函数voidEnQueue(constType&item);//将item加入到队列中TypeDeQueue();//删除并返回队头元素TypeGetFront();//查看队头元素的值voidMakeEmpty();//置空队列，实现与~Queue()相同intIsEmpty()const{returnp==NULL;}//判队列空否private:QueueNodeType*p;//队尾指针（在循环链表中）};队列的析构函数templateclassTypeQueueType::~Queue(){//队列的析构函数QueueNodeType*s;while(p!=NULL){s=p;p=p-link;d