《算法与数据结构》课程期中试卷
得分 评卷人 一、判断题（本大题共10小题。每小题1分，共10分。） （注意：将判断结果填入以下表格中。对的打√，错的打×。）
1. 算法分析的目的是研究算法中输入和输出的关系。（ 错 ） 2. 可以随机访问任一元素是链表具有的特点。（ 错） 3. 用一维数组存储一棵完全二叉树是有效的存储方法。（对 ） 4. 在队列第i个元素之后插入一个元素不是队列的基本运算。（ 错 ） 5. Tail（Tail（Head（((a,b),(c,d))）））= (b)。（ ）
6. 如果一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历下的最后
一个结点。（ 错）
比如只有根节点和左子树的特殊情况。
7. 由权值分别为3, 8, 6, 2的叶子生成一棵哈夫曼树，它的带权路径长度为35。（对 ） 带权路径长度=1*8+2*6+3*3+3*2=35（书P146）
8. Head（Tail（Head（((a,b),(c,d))）））= (b)。（ ）
9. 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。（对 ）
逻辑结构、存储结构和数据的操作（运算）三个方面
2014－2015下 计算机学院《算法与数据结构》期中试卷 第1页，共17页
10. 线性的数据结构可以顺序存储，也可以链接存储；非线性的数据结构只能链接存储。（错 ） 比如完全二叉树。 得分 评卷人 二、单项选择题（本大题共15小题。每小题2分，共30分。）
（注意：以下各题只有一个正确答案，请将选择的结果填入以下表格中。） 1 2 D C 3 B 4 A 5 A 6 A 7 A 8 C 9 A 10 11 12 13 14 15 C D A B B C 1. 下面程序段的时间复杂度为________。
s=0；
for (i=1；i A. O(1) B. O(logn) C. O(n) D. O(n) [D] 就是s= s +i*j；运算次数 ，T=(1+2+3…………n)=n(n+1)/2,为n^2 2. 以下数据结构中哪一个是线性结构_ ___。 A. 有向图 B. 线索二叉树 C. 队列 D. 二叉排序树 2 [C]堆栈，线性表（循序表，链表），队列都是线性结构。 3. 设有一个二维数组A[m][n]，若首元素存放地址为644，A[2][2]存放地址为676，每个元素占 用一个空间，下界从0开始，行序优先；则A[3][3]存放的地址为_______。 A. 691 B. 692 C. 689 D. 其它 [B] 行序优先 LOC(aij)=loc(a00)+i*n+j (P53) 676=644+2*n+2, n=15 A[3][3]=644+3*15+3=692 4. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链 2014－2015下 计算机学院《算法与数据结构》期中试卷 第2页，共17页 表中某个结点，则在s所指结点之后插入上述链表应执行的语句为________。（说明：以下next分量等同于link分量） A. q->next=s->next；s->next=p； C. p->next=s->next；s->next=q； B. s->next=p；q->next=s->next；(吊链了) D. s->next=q；p->next=s->next； [A] s所指结点之后插入上述链表, s->next=p.注意循序。 5. 已知单链表A长度为m，单链表B长度为n，若将A联接在B的末尾，其时间复杂度应为 __________。 A. O(1) B. O(m) C. O(n) D. O(m+n) 【A】, 单链表,链接修改指针即可，将A联接在B的末尾，B->next=A. 6. 在计算机内实现递归算法时所需的辅助数据结构是________。 A. 栈 B. 队列 C. 树 [A]堆栈，利用其后进先出特点。 7. 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_________ 个不同的字符串。 A. 6 B. 5 C. 4 D. 其它 D. 图 [A] A,B,C的全排列6。 (1)ABC依次进栈，出栈为CBA. (2)ACB依次进栈，出栈为BCA. (3)BAC依次进栈，出栈为CAB. (4)BCA依次进栈，出栈为ACB.(5) CAB依次进栈，出栈为BAC.(6) CBA依次进栈，出栈为ABC 8. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为________。 A. n-1 B. n C. n+l 2014－2015下 计算机学院《算法与数据结构》期中试卷 第3页，共17页 D. 2n