数据结构期中试题(答案).doc

在以下题目中任意选择做 求下列程序段的时间复杂度（每小题5分） （1）for(i=0;in;i++) for(j=0; ji; j++) for(k=0; kj; k++) ｘ＝ｘ＋delta； O(n3) （2）i=1； while (in) i=i*2; O(log2n) （3） i=n*n; while (i!=1) i=i/2; O(log2n2) 2.按增长率从小到大顺序排列以下函数（5分） n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, n!, n2+logn 答 ： logn，n1/2+logn，n, nlogn, n2+logn, n3, n-n3+7n5, 2n/2, (3/2)n, n! 3．问答题 (1)．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度分别为多少？(3分) 答：访问节点复杂度为O(1), 增加、删除结点的时间复杂度为O(n); (2)．若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？(5分) 答:采用顺序存储结构.因为顺序存储存取操作复杂度为O(1),效率高. (3)．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，请写出其插入操作序列。（6分） 答:q-rlink=p; q-llink=p-llink, p-llink-rlink=q;p-llink=q; （这是答案之一，还可以有其它答案） (4)．在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? (3分) 答： 单链表不行，双向链表可以。 (5)．给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR)。（5分） 答： （R-F+N）% N (6). 若串S1=”ABCDEFGHIJK”, S2=”9898” ,S3=”###”执行 replace(S1,0，substr(S1,length(S2),length(S3)),S3)后，其结果是什么？（5分） 答: ABCD###HIJK （7）．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，请求出Loc[5，5]的值。 （5分） 答：Loc(5,5)=10+((5-1)*100+(5-1))*2=818 （8）. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？（5分） 非0元素占10*3*2=60字节；控制结构占3*2=6字节。共66字节。 4．填空与选择 (1)．以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.(每空3分) void mergelink(SLNode *p, SLNode *q) { SLNode *h,*r; （1）_h=(SLNode *)malloc(sizeof(SLNode);_____ h-next= NULL; r=h; while((p!=NULL) (q!=NULL)){ if (p-data=q-data){ （2）r-next=p___； r=p; p=p-next； } else{ （3）r-next=q____； r=q; q=q-next; } } if(p==NULL) r-next=q; （4）if(q==NULL) r-next=p____; } （以下选择题每题4分） (2)．一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 (3) 输入序列为ABC，可以变为CBA时，经过的栈操作为（ B ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop (4) 栈和队列的共同点是（ C ）。 A. 都是先进先出