数据结构前两年的期中考试题型.doc

2010-2011第一学期数据结构期中考试题 原创 2010-10-29 12:36:57 字号：大 中 小 在以下题目中任意选择做1 求下列程序段的时间复杂度（每小题5分,最多选做2题，多做不给分）（1）i=1；WHILE (in) i：=i*2（2）下面程序段的时间复杂度为( )s=0；for(i=1；in；i+)for(j=1；j=(y+1)*(y+1)y+;2.按增长率从小到大顺序排列以下函数（5分）1、按增长率由小至大的顺序排列下列各函数：2100, (3/2)n, (2/3)n, nn , n(1/2), n! , 2n , lgn , nlgn , n(3/2) 3问答题(1)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？(5分)(2)双向链表中有两个指针域，prep和next，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，请写出其插入操作序列。（6分）(3)设单链表的结点结构为（data,next），data为整数，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，请写出将py指向结点插入为px指向结点的直接后继所执行的语句。（6分）(4). 若串S1=“I am a teacher”, S2=“teacher” ,S3=“student”执行replace(S1,0，substr(S1,length(S2),length(S3),S3)后，其结果是什么？（5分）（5）假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为118，请求出Loc5，15的值。 （5分） （6）. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？（5分）（7）下列二分搜索算法BinarySearch是否正确，请说明原因。(6分)int BinarySearch(Datatype a,Datatype x,int n)int left=0;int right=n-1;int middle；while(leftamiddle)left=middle;else right=middle;return -1（8)阅读下面的算法（15分）LinkList mynote(LinkList L)/L是不带头结点的单链表的头指针if(L&L-next)q=L；L=Lnext；p=L；S1： while(p-next) p=pnext；S2： pnext=q；qnext=NULL； return L；请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。 4填空与选择(1)以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.(每空3分)void mergelink(SLNode *p, SLNode *q)SLNode *h,*r;/建立头结点（1）_h-next= NULL; r=h;while(p!=NULL)& (q!=NULL) if (p-datadata)/（2）_； r=p; p=p-next； else/（3）_； r=q; q:=q-next; ;if(p=NULL) r-next=q;/（4）_;（以下选择题每题4分） （1）下面程序段的时间复杂度为（ ）int f(int n) if(n=0 | n=1) return 1;else return n*f(n-1); A. O(1) B. O(n) C. O(n2) D. O(n !) （2）设栈的输入序列为（1，2，3，4），则（）不可能是输出序列。A.1423 B.2134 C.1432 D.3214（3） 假设以数组Am存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )A.(rear-length+m+1)m B.(rear-length+m)mC.(rear-length+m-1)m D.(rear-length)m（4）判定一个顺序循环队列q（数据元素最多为Max）为队满的条件是（ ）。A. q.real-q.front=Max B.q.front=q.rearC.q.rear-q.front-1=Max D.q.front=(q.rear+1)%Max5.程序设计题1).已知两个单链表A和B,其头指针分别为heada和headb，编写一个函数从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。（15分）2).设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，请编写一个函数判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。(15分)6设有下列递归算法:int vol(int n)if(n=0) return 0;elsereturn vol(n-1)+2;如该函数被调用时，参数n值为3,函数调用结束时返回值为多少?用图示描述函数的递归调用执行过程。(15分)20092010第一学期数据结构期中考试 原创 2009-11-3 8:30:41 字号：大 中 小 在以下题目中任意选择做1 求下列程序段的时间复杂度（每小题5分,最多选做2题，多做不给分）（1）for(i=0;in;i+)for(j=0; ji; j+)for(k=0; kj; k+)delta；（2）i=1；WHILE (inext= NULL; r=h;while(p!=NULL)& (q!=NULL) if (p-datadata)/（2）_； r=p; p=p-next； else/（3）_； r=q; q:=q-next; ;if(p=NULL) r-next=q;/（4）_;（以下选择题每题4分） (2)一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。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时，经过的栈操作为（ ）A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,popC. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop(4) 栈和队列的共同点是（）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点（5）对稀疏矩阵进行压缩存储目的是（ ）A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度5.程序设计题（1）已知两个单链表A和B,其头指针分别为heada和headb，编写一个函数从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。（15分）(2) 利用两个栈sl,s2模拟一个队列时，编程实现用栈的运算实现队列的插入，删除以及判队空运算。（15分）（3）设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，请