《数据结构》期中考试试卷
(供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) D. n+1
4、 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。 A. n-2 B. n-1 C. n 5．用链表表示线性表的优点是 （ ）。
(A)便于随机存取
(B)花费的存储空间较顺序存储少 (C)便于插入和删除
(D)数据元素的物理顺序与逻辑顺序相同
6．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。
A．QU->rear==(QU->front+1) % m0 B．QU->rear==(QU->rear+1) % m0 C．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. BCDEFEF 8、在一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较（ ）个元素结点。
(A)n／2 (B)n (C)(n+1)／2 (D)(n-1)／2 9．串的长度是( )。
(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 C. rear != NULL
B. front != NULL D. front == NULL
12、带头结点的单链表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 为（ ）。 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); }
C. (2n-i+1)*i/2 D. (2n-i-1)*i/2
14. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应
则计算fact(n)需要调用该函数的次数为（ ）次。 A．n B．n+1 C．n+2 D．n-1 16、已知串S=“aaab”,其next数组的值为（ ）。
A. 1231 B. 1123C C. 0123 D. 1211
17．用不带头结点的单链表存储队列，在进行删除（出队）运算时（ ） A．仅修改头指针 B．仅修改尾指针 C．头尾指针都要修改 D．头尾指针可能都要修改 18．一个非空广义表的表头（ ）
A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子
19．稀疏矩阵的压缩存储方法是只存储（ ）。
A．非零元素 B. 三元祖（i,j, aij） C. aij D. i,j
20．基于三元组的稀疏矩阵，对每个非零元素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=0 While(s i++; s+=i; } 其渐近时间复杂度是： /* i=i+1 */ /* s=s+i */ 3. 若栈采用顺序存储方式存储，现两栈共享空间s[1….m]，top[i]代表第i个栈（i =1,2）的栈顶，栈空时栈1的底在s[1]，top[1]=1，栈2的底在s[m]，top[2]=m，则栈满的条件是什么？ Top[1]+1=top[2]//top[2]-1=top[1] 4.下列算法comstr的功能是比较两个链串的大小，请在划线处填入适当的内容。其结点类型定义如下 typedef struct node { char data; struct node *next; }LinkString; int comstr(LinkString s1,LinkString s2) { //s1和s2为两个链串的头指针 while(s1&&s2) { if (s1－>date s1=s1->next; ___________ ______ ； } if ( _____ _____) return(-1)； if (s1!=NULL && s2==NULL) return(1)； _______ _ ________； } 5、给定如下二叉树，请分别写出对该二叉树进行前序、中序和后序遍历的结果。 6．假设用于通信的电文仅由6个字母组成(设为A B C D E F )，字母在电文中出现的频率分别为：7，19，2，6，32，3。试为这6个字母设计哈夫曼编码并画出哈夫曼树(构造哈夫曼树时按子树根结点值左小右大的规则进行)。 7. 已知用有序链表存储整数集合的元素，其中a和b分别为指向存储集合{2，4，5，7，9，12}和{2，4，5，7，9}的链表的头指针；阅读算法f44，并回答下列问题： ①写出执行f44（a,b）的返回值； ②简述算法f41的功能； ③写出算法f41的时间复杂度。 算法如下： int f44(LinkList ha,LinkList hb) { //LinkList是带有头结点的单链表 //ha和hb分别为指向存储两个有序整数集合的链表的头指针 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构中期考试试卷在线全文阅读。
相关推荐：