数据结构期中考试题.docx

一、单项选择题（每小题3分，共30分）1、线性结构是数据元素之间存在的一种_。A、一对多关系B、多对多关系C、多对一关系D、一对一关系2、以下数据结构中，哪一个不是线性结构（）A生成树B.顺序栈C.单链表D.循环队列3、设n是偶数，则运行下列程序段的时间复杂度为（）。x=100;for(p=2;p=n;p+)for(q=2*i;qllink=Q；p-rlink=q-rlink;q-rlink=p；_.(空白处为一条赋值语句)A、q-llink=pB、q-rlink-llink=pC、p-rlink-llink=pD、p-llink-llink=p6、设循环队列的结构是：constintMaxsize=100;typedefintData Type;typedef struct Data Type dataMaxsize;Intfront, rear; Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（）A、Q.front= = Q.rear;B、Q.front - Q.rear= = Maxsize;C、Q.front + Q.rear= = Maxsize;D、Q.front= = (Q.rear+1)% Maxsize;7、已知L是一个不带表头的单链表,在表首插入结点*p的操作是（）。A. p = L;p-next = L;B. p-next = L;p = L;C. p-next = L;L = p;D. L = p;p-next= L;8、下面关于串的叙述中，哪一个是不正确的？( )A串是字符的有限序列 B.空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储9、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为()。A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，110、循环队列存储在数组A0.m-1中，则入队时需做的操作为（）。A. rear=rear+1B. rear=(rear+1)%(m-1)C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)二、填空题(每空3分，共30分)1、int x=n;int y=0;while(x=(y+10000)*(y+10000)y+;该程序的时间复杂度为O(n1/2)（1）2、给定串的连接操作函数：char *strcat(char *to, char *from); /将串from连接到串to的末尾，并返回连接后的串，若字符串s1=point,s2=to,则strcat(s1,strcat (s2,s1)的操作结果是（2）point to point。3、假设以S和X分别表示进栈和退栈操作，则对输入序列a, b, c ,d, e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列是（3）bceda4、假设二维数组A810按行优先顺序存储,若每个元素占2个存储单元,元素A00的存储地址为100,则元素A56的存储地址为（4）212。5、假设以一维数组作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A56的值存储在S（5）19中。6.设循环队列的元素存放在一维数组Q0.30中,front指向队头元素的前一个位置,rear指向队尾元素。若front=25, rear=5,则该队列中的元素个数为（6）11。7下列算法的功能是求带头结点的单链表的表长，请完善。intcount(LinkListhead)（7）LinkList*p=head-next;length=0;while (p!=NULL)length+ ;p=p-next（8;（9）return length;8设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而S5P4时，S5应与（7）p2比较。三、简答题（25分）1判断循环队列是否“满”，有哪些方法？请说明。（9分）使用一个计数器记录队列中元素个数（即队列长度）；判队满：count0 & rear=front判队空：count=0加设标志位，出队时置,入队时置,则可识别当前front=rear属于何种情况判队满：tag=1 & rear=front判队空：tag=0 & rear=front少用一个存储单元判队满：front=(rear+1)%MaxQueueSize判队空：rear=front2.按增长率从小到大顺序排列以下函数（5分）n, n-n4+7n5, nlogn, 2n/3, n4, logn, n1/3+logn, (3/2)n, n!, n2+lognlognnn1/3+lognnlognn2+lognn4n-n4+7n52n/3 (3/2)n n!3设有一个递归算法如下（11分）intx (intn)if (n=3)return1;elsereturnx(n-2)+x(n-4)+1;试问计算x(x(8)时需要计算（18）次x函数。请用图示描述函数的递归调用执行过程。4.求下列程序的时间复杂度（4分）（1）i=1；WHILE (inext;pb=Lb-next;*Lc=pc=La;/Lc的头结点利用La的头结点while( pa & pb )/将pa、pb结点按大小依次插入Lc中if( pa-datadata )pc-next=pa;pc=pa;pa=pa-next; el