2016-2学期《数据结构与算法》复习题

复习题

一.单项选择题

1.设计一个判定表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。

A.集合B.线性表C.队列D.栈

2.n个结点的线索二叉树上含有的线索数为（）。

A.2nB.n-1C.nD.n+1

3.由4个结点可以构造出（）种不同的二叉树。

A.12B.13C.14D.15

4.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为（）。

A.n*nB.n*n/2C.n*（n+l）/2D.（n+1）*（n+1）/2

5.两个指针p和q,分别指向单链表的两个元素，P所指元素是q所指元素的前驱，则（）。

A.p==qB.q->next=pC.p->next=qD.p-〉next=q->next

6.数组A中，每个元素的长度为4个字节，行下标i从1到5,列下标j从1到4,从首地址SA开始连续存

放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为（）。

A.SA+20B.SA+36C.SA+40D.SA+45

7.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为dl,则第i个结点的

地址为（）。

A.dl+（i-l）*mB.dl+i*mC.dl+（i+l）mD.dl-i*m

8.分析下列算法suanfal（n）的时间复杂度是（）。

voidsuanfal（intn）

{inti,j,x=l；

for（i=0；i<n；i++）

for（j=0；j<n；j++）

x=x*2；

）

A.0（2n）B.0（2"）C.0（n2）D.0（n2+2）

9.将一个A[L.10,1..10]的三对角矩阵，按行优先存入一维数组B[l,30]中，A中元素a[6,5]在B数组中的

位置i为（）。

A.15B.16C.55D.65

10.深度为6的二叉树最多有（）个结点。

A.62B.63C.64C.65

11.由3个结点可以构造出（）种不同的二叉树。

A.2B.3C.4D.5

12.栈的插入和删除操作在（）进行。

A.栈顶B.栈底C.指定位置D.随机位置

13.数组A中，每个元素的长度为3个字节，行下标i从1到5,列下标j从1到4,从首地址SA开始连续存

放在存储器内，该数组占用的字节数为（）。

A.20B.60C.80D.120

14.下面语句的时间复杂度为（）。

s=0;

for（i=l;i<=n;i++）

s=s+i;

A.O（n）B.0（n5）C.0（5"）D.0（/）

15.二叉树中，叶子的数组等于（）O

A.度为2的结点数加1B.度为2的结点数减1

C,度为2的结点数D.度为2的结点数的两倍

16.数制转换的算法，采用（）数据结构最佳。

A.集合B.线性表C.队列D.栈

17.线性表采用链式存储时，其地址是（）。

A.必须是连续的B.一定是不连续的

C.部分地址必须是连续的D.连续或不连续都可以

18.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）。

A.物理结构B.逻辑结构

C.顺序存储结构D.链式存储结构

19.线性表在（）时，宜用顺序表作存储结构。

A.经常随机存取B.经常作插入、删除

C.无足够连续存储空间D.经常作动态增减

二、填空题。

1.数据结构包含四种基本结构，它们是集合、、树形结构、。

2.二叉树的深度为k的二叉树最多有个结点，其中第i层最多有个结点。

3.n个结点的完全二叉树，使用一维数组t存储结点元素的值，假设t[i]存储第i个结点，那么t[i]的双亲

是，左小孩是,右小孩是t[2*i+l]。

4.由权值分别为11,8,6,2,5的叶子结点生成一颗哈夫曼树，它的带权路径长度为。

5.若串s="hell。"，其子串个数是。

6.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编

号为24的结点X的左孩子编号为,右孩子编号为。

7.长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为。

8.NPL(T)指的是树的,即每个叶子的权与根到该叶子的路径长度的乘积之和。

9.深度为k且有个结点的二叉树称为满二叉树。

10.3层完全二叉树至少有个结点。

四、简答题

1.画出二叉树的5种基本形态。

2