《数据结构中期考试试卷》由会员分享,可在线阅读,更多相关《数据结构中期考试试卷(8页珍藏版)》请在金锄头文库上搜索。
1、数据结构期中考试试卷(供2012级计算机专业用)一、单项选择题,在括号内填写所选择的标号(每小题1分,共20分)1、算法指的是( ) A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列2、如下陈述中正确的是( ) A串是一种元素仅为字符的线性表B串的长度必须大于零 C串中元素只能是字母 D空串就是空白串3、 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。A. O(1)B. O(n2) C. O(n)D. O(n/2)4、 当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为( )。A. n-2 B. n-1C. n D. n+15用链表表示
2、线性表的优点是 ( )。(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位),front和rear分别为队列的队头指针和队尾指针 ) 中,当队列非空时,若插入一个新的数据元素,则其队尾指针rear的变化是( )。AQU-rear=(QU-front+1) % m0 BQU-rear=(QU-rear+1) % m0CQU-rear=(QU-front+1) DQU-rear=(QU-rear+1) 7 设有S1=“ABCDEFG”,S2=“PQRST”,函数con(
3、x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果是( )。ABCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较( )个元素结点。 (A)n2 (B)n (C)(n+1)2 (D)(n-1)29串的长度是( )。 (A)串中不同字符的个数 (B)串中不同字母的个数 (C)串中所含字符的个数n(nO) (D)串中所含字符的个
4、数n(n0)10.表达式a*(b-c)+d的后缀表达式是( )。 Aabcd*-+ B. abc-*d+ C. abc*-d+ D. +-*abcd 11. 假定一个链式队列的队头和队尾指针分别为front和rear,则判断队空的条件为( )。 A. front = rearB. front != NULL C. rear != NULL D. front = NULL12、带头结点的单链表first为空的判定条件是( )。A. first = NULL; B. first-link = NULL;C. first-link = first; D. first != NULL;13. 设有一个
5、nn的对称矩阵A,将其下三角部分按行存放在一个一维数组B中,A00存放于B0中,那么第i行的对角元素Aii存放于B中( )处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/214. 已知单链表A长度为m,单链表B长度为n,若将B联接在A的末尾,其时间复杂度应为( )。 A. O(1) B. O(m) C. O(n) D. O(m+n) 15. 设有一个递归算法如下 int fact(int n) /n大于等于0 if(nnext=p-next; p-next=s; )3. 在链表中进行插入和( )操作的效率比在顺序存储结构中进
6、行相同操作的效率高。4需要压缩存储的矩阵可分为特殊矩阵和( )矩阵两种。5栈的插入和删除只能在栈的顶端进行,后进栈的元素必定先被出栈,所以又把栈称作( )表;队列的插入和删除运算分别在两端进行,进行插入的一端叫做( ),进行删除的一端叫做( ),先进队的元素必定先出队,所以又把队列称作( )表。6. 某广义表A =( a ,( b , c , d ) ,e) ,则GetLength(A)=( ), GetHead(A)=( ),GetTail(A)=( )。7. 若有广义表表示为A=(a,(b,(c, d,(e, f)),则A的深度为( )。8. 链表适用于( )查找。9.设有一个顺序栈S,元
7、素S1,S2,S3,S4,S5,S6依次进栈,如果6个元素的出栈顺序为S2,S3,S4,S6,S5,S1,则顺序栈的容量至少应为( )。10在一个长度为n的向量中的第i个元素(1in)之前插入一个元素时,需向后移动( )个元素。三、判断题,在每小题后面的括号内打表示正确或打表示错误(每小题1分,共10分)1线性表的逻辑顺序与存储顺序总是一致的。( )2. 顺序表和一维数组一样,都可以按下标随机(或直接)访问。( )3. 用非递归方法实现递归算法时一般要使用递归工作栈。( )4在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。( )5.栈和队列都是限制存取点
8、的线性结构( )6设有两个串p和q,其中q是p的子串,把q在p中首次出现的位置作为子串q在p中的位置的算法称为匹配。 ( )7数据元素是数据的基本单位。 ( )8在线性表的顺序存储结构中,插入和删除时,移动元素的个数与该元素的位置有关。( )9在单链表中任何两个元素的存储位置之间都有固定的联系,因为可以从头结点进行查找任何一个元素( )。10数组是一种复杂的数据结构,数组元素之间的关系,既不是线性的,也不是树形的 ( )四、简答题(每小题5分,共20分) 1. 设有一个二维数组Amn,按行优先存放于一个连续的存储空间中,A00的存储地址是200,每个数组元素占2个存储单位,则: 写出二维数组(m*n)按行为主序存储后LOC(aij)地址计算公式是: 当m=10,n=20时,数组元素A810的存储地址是多少?2有下列程序段i=s=0While(sdatedate) return(1); if (s1dates2date) return(1);s1=s1-next; _ _; if (_ _) return(-1); if (s1!=NULL & s2=NULL) return(1); _ _ _; 5、给定如下二叉树,请分别写出对