(word完整版)2017年数据结构期末考试题及答案A,推荐文档

单元练习2

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）

（×）（1）线性表的链式存储结构优于顺序存储。

（×）（2）链表的每个结点都恰好包含一个指针域。

（√）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（×）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（√）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（√）（8）线性表采用顺序存储，必须占用一片连续的存储单元。

（×）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（ㄨ）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题

（1） 顺序表中逻辑上相邻的元素在物理位置上 必须 相连。

（2） 线性表中结点的集合是有限的，结点间的关系是 一对一 关系。

（3） 顺序表相对于链表的优点是： 节省存储 和随机存取。

（4） 链表相对于顺序表的优点是： 插入、删除 方便。

（5） 采用 顺序 存储结构的线性表叫顺序表。

（6） 顺序表中访问任意一个结点的时间复杂度均为 O(1) 。

（7） 链表相对于顺序表的优点是插入、删除方便；缺点是存储密度 小 。

（8） 在双链表中要删除已知结点*P，其时间复杂度为 O(1) 。

（9） 在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。

（10） 单链表中需知道 头指针 才能遍历整个链表。

（11） 线性表中第一个结点没有直接前趋，称为 开始 结点。

全真模拟试题（一）

一、 单项选择题（在每小题的4个备选答案中，选出正确的答案，并将其号码填在

题干的括号内。每小题2分，共24分）

1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

①单链表 ②双链表 ③单向循环 ④顺序表

2． 串是任意有限个（ ）

①符号构成的序列 ②符号构成的集合

③字符构成的序列 ④字符构成的集合

3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：

aij≠0(i≥j, l≤i, j≤ 10)

aij=0 (i

现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为

①2340 ②2336 ③2164 ④2160

4． 如果以链表作为栈的存储结构，则退栈操作时（ ）

① 必须判别栈是否满

② 对栈不作任何判别

③ 必须判别栈是否空

④ 判别栈元素的类型

5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）

①front=front+1 ②front=(front+1)% m

③rear=(rear+1)%m ④front=(front+1)%(m+1)

6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。

① 64 ②32 ③31 ④63

7． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写 上姓名和学号。

一、单项选择题(每小题2分，共20小题，共计40分)

1 .某算法的空间复杂度为 0(1),则。

A.该算法执行不需要任何辅助空间

B.该算法执行所需辅助空间大小与问题规模 n无关

C.该算法执行不需要任何空间

D.该算法执行所需全部空间大小与问题规模 n无关

2 .在长度为n的顺序表中插入一个元素，对应算法的时间复杂度为 。

A.0(1) B.O(log2n) C.0(n) D.0(n2)

3 .设线性表中有n个元素，以下运算中， 在单链表上实现要比在顺序表上实现 效率更高。

A.删除指定位置元素的后一个元素

B.在最后一个元素的后面插入一个新元素

C.顺序输出前k个元素

D.交换第i个元素和第n-i+1个元素的值(i=1, 2,…，n)

4 .以下数据结构中元素之间为非线性关系的是 。

A.栈 B.队列 C.线性表 D.以上都不是

5 .若一个栈用数组 data[1..n]存储，初始栈顶指针 top为n+1,则以下元素x进栈的正

确操作是。

A.top++;data[top]=x; B.data[top]=x;top++;

C.top-- ;data[top]=x; D.data[top]=x;top --;

6 .若某循环队列有队首指针 front和队尾指针 rear,在队不满时进队操作仅会改

变。

A.front B.rear C.front 和 rear D.以上都不队

7 .设循环队列中数组的下标是 0〜N-1,其队头、队尾指针分别为f和r(f指向队首元 素的前一位置，r指向队尾元素)，则其元素个数为。

A.r-f B.r-f-1 C.(r-f)%N+1 D.(r-f+N)%N

8 .设树T的度为4,其中度为1、2、3、4的结点个数分别为 4、2、1、1,则T中的

叶子结点个数是。

A.5 B.6 C.7 D.8

一、单选题（每题1 分，共15分）

1、设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。

A． 线性结构 B. 树型结构 C. 物理结构 D. 图型结构

2、栈的插入和删除操作在( )进行。

A.栈顶 B栈底 C.任意位置 D．指定位置

3、下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++）

{ t=1；

for(j=1；j<=i；j++)

t=t*j；

s=s+t；}

A. O(n) B).O(n2) C.O(n3) D. O(n4)

4、栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素 B.都是先进后出

C.都是先进先出 D.没有共同点

5、设链式栈中结点的结构为(data，link)，且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行( )操作。

A．top->link=s B．s->link

C．Slink=top；top=s D．S-->link=top; top=top->link

6、二叉树的第k层的结点数最多为( ).

A．2k-1 B.2K+1 C.2K-1 D. 2k+1

7、设有两个串t和p，求p在t中首次出现的位置的运算叫做( )。

A.求子串 B．模式匹配 C.串替换 D.串连接

8、数据的最小单位是（ ）。