《算法与数据结构》-期中试卷.pdf

《算法与数据结构》-期中试卷--第1页

《算法与数据结构》课程期中试卷

得分评卷人一、判断题（本大题共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页

《算法与数据结构》-期中试卷--第1页

《算法与数据结构》-期中试卷--第2页

10.线性的数据结构可以顺序存储，也可以链接存储；非线性的数据结构只能链接存储。（错）

比如完全二叉树。

得分评卷人二、单项选择题（本大题共15小题。每小题2分，共30分。）

（注意：以下各题只有一个正确答案，请将选择的结果填入以下表格中。）

123456789101112131415

DCBAAAACACDABBC

1.下面程序段的时间复杂度为________。

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.691B.692C.689D.其它

[B]行序优先LOC(aij)=loc(a00)+i*n+j(P53)

676=