《算法与数据结构》-期中试卷选编.doc

2014－2015下 计算机学院《算法与数据结构》期中试卷 　第 PAGE 17页，共 NUMPAGES 17页 《算法与数据结构》课程期中试卷 得分评卷人一、判断题（本大题共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. 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。（对　　） 逻辑结构、存储结构和数据的操作（运算）三个方面 10. 线性的数据结构可以顺序存储，也可以链接存储；非线性的数据结构只能链接存储。（错　　） 比如完全二叉树。 得分评卷人二、单项选择题（本大题共15小题。每小题2分，共30分。） （注意：以下各题只有一个正确答案，请将选择的结果填入以下表格中。） 1　23456789101112131415DCBAAAACACDABBC1. 下面程序段的时间复杂度为________。 s=0； for (i=1；in；i++) for (j=1；ji；j++) s += i*j； A. O(1) B. O(logn) C. O(n) D. O(n2) [D] 就是s= s +i*j；运算次数 ，T=(1+2+3…………n)=n(n+1)/2,为n^2 2. 以下数据结构中哪一个是线性结构_ ___。 A. 有向图 B. 线索二叉树 C. 队列 D. 二叉排序树 [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指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为________。（说明：以下next分量等同于link分量） A. q-next=s-next；s-next=p； B. s-next=p；q-next=s-next；(吊链了) C. p-next=s-next；s-next=q； 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. 树 D. 图 [A]堆栈，利用其后进先出特点。 7. 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_________个不同的字符串。 A. 6 B. 5 C. 4 D. 其它 [A] A,B,C的全排列6。 (1)ABC依次进栈，出栈为CBA. (2)ACB依次进栈，出