数据结构中期考试试卷.doc
8页
《数据结构》期中考试试卷(供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-1 C. n D. n+15．用链表表示线性表的优点是 （ ）A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同6．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。
A．QU->rear==(QU->front+1) % m0 B．QU->rear==(QU->rear+1) % m0C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1) 7． 设有S1=“ABCDEFG”，S2=“PQRST”，函数con(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))的结果是( )A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（ ）个元素结点 (A)n／2 (B)n (C)(n+1)／2 (D)(n-1)／29．串的长度是( ) (A)串中不同字符的个数 (B)串中不同字母的个数 (C)串中所含字符的个数n(n>O) (D)串中所含字符的个数n(n≥0)10.表达式a*(b-c)+d的后缀表达式是（ ）。
A．abcd*-+ B. abc-*d+ C. abc*-d+ D. +-*abcd 11. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( ) A. front == rear B. front != NULL C. rear != NULL D. front == NULL12、带头结点的单链表first为空的判定条件是（ ） A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;13. 设有一个n´n的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于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(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（ ）次 A．n B．n+1 C．n+2 D．n-116、已知串S=“aaab”,其next数组的值为（ ）A. 1231 B. 1123C C. 0123 D. 121117．用不带头结点的单链表存储队列，在进行删除（出队）运算时（ ） A．仅修改头指针 B．仅修改尾指针 C．头尾指针都要修改 D．头尾指针可能都要修改18．一个非空广义表的表头（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子19．稀疏矩阵的压缩存储方法是只存储（ ）。
A．非零元素 B. 三元祖（i,j, aij） C. aij D. i,j20．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定A.非零元素 B.三元组(i,j,aij) C.③ aij D. i,j二、填空题，在空白处填写合适内容（每小题2分，共20分）1. 数据结构的存储结构包( 、 )、索引和散列存储等四种2．在一个单链表中p所指结点之后插入一个由指针s所指结点，可执行以下操作：（ s->next=p->next; p->next=s; ）3. 在链表中进行插入和( )操作的效率比在顺序存储结构中进行相同操作的效率高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，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为( )10．在一个长度为n的向量中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动（ ）个元素三、判断题，在每小题后面的括号内打√表示正确或打×表示错误（每小题1分，共10分）1．线性表的逻辑顺序与存储顺序总是一致的 )2. 顺序表和一维数组一样，都可以按下标随机（或直接）访问 )3. 用非递归方法实现递归算法时一般要使用递归工作栈 )4．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
）5.栈和队列都是限制存取点的线性结构（ ）6．设有两个串p和q，其中q是p的子串，把q在p中首次出现的位置作为子串q在p中的位置的算法称为匹配 ( )7．数据元素是数据的基本单位 ( )8．性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关 ）9．在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素( )10．数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 ( )四、简答题（每小题5分，共20分） 1. 设有一个二维数组A[m][n]，按行优先存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占2个存储单位，则：⑴ 写出二维数组（m*n）按行为主序存储后LOC(aij)地址计算公式是： ⑵ 当m=10,n=20时，数组元素A[8][10]的存储地址是多少？2．有下列程序段i=s=0While(s 其结点类型定义如下typedef struct node { char data; struct node *next; }LinkString; int comstr(LinkString s1,LinkString s2) { //s1和s2为两个链串的头指针 while(s1&&s2) { if (s1－>date
