《数据结构中期考试试卷》由会员分享，可在线阅读，更多相关《数据结构中期考试试卷（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、给定如下二叉树，请分别写出对
