数据结构随堂测验

数据结构随堂测验

学号：［填空题］*

您的姓名：［填空题］*

1.判断：线性表中的所有元素都有一个前驱元素和一个后继元素。*［判断题］*

对

错（正确答案）

2.判断：单链表中一定要有头指针和头结点。*［判断题］*

对

错（正确答案）

3.判断：设计算法判断表达式括号是否匹配，应采用栈数据结构实现。*［判断题］

*

对（正确答案）

错

4.不论是入队操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。*

［判断题］*

对（正确答案）

错

5.判断：在一个图中所有顶点的度数之和等于图的边数的2倍。*［判断题］*

对

错

6.哈夫曼树中没有度为1的结点。*［判断题］*

对（正确答案）

错

7.数据的最小单位是（）。*［单选题］*

数据项

数据对象

数据元素

数据变量

8.下面关于线性表的叙述错误的是（）*［单选题］*

D.线性表采用顺序存储便于插入和删除操作的实现

A.线性表采用顺序存储必须占用一片连续的存储空间

C.线性表采用链式存储便于插入和删除操作的实现

B.线性表采用链式存储不必占用一片连续的存储空间

9.设一条单链表的头指针变量为head,如果该单链表有头结点则其判空条件为

0,如果无头结点则其判空条件为0O*［单选题］*

head==NULL;head->next==head;

head->next==head；head==NULL;

head->next==NULL；head==NULL;

head==NULL；head->next==NULL;

10.向一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要

移动的元素个数为（）*［单选题］*

62.5(正确答案)

63.5

62

63

11.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为

()*［单选题］*

1,5,4,6,2,3

3,1,2,5,4,6

3,2,5,6,4,1

5,3,4,6,1,2E确答案)

12.队列是一种()的线性表。*［单选题］*

先进先出

先进后出

只能插入

只能删除

13.数组作为循环队列的存储空间，大小为n,即data［n］,front为队头指针，rear为

队尾指针，则执行出队操作后其头指针front值为()，执行入队操作其尾指针

rear值为()。*［单选题］*

front=(front+1)%(n-l);rear=(rear+l)%(n-l);

front=(front-1)%n;rear=(rear-l)%n;

front=firont+2;rear=rear+1;

front=(front+1)%n；rear=(rear+l)%n；(正确答案)

14.二叉树的第k层最多有多少个结点()。*［单选题］*

2的k-1次方

2的k次方-1

2k+l

2k-1

15.n个结点的完全无向图含有边的数目（）o*［单选题］*

n*（n-l）

n*n

n*（n・l）/2（正确答案）

n*（n+l）

16.设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为（）。*

［单选题］*

n

e

2n

2e（正确答案）

17.n个顶点的连通图，至少有（）条边。*［单选题］*

n

n-l（正确答案）

n+1

2n

18.图的深度优先遍历类似于树的（），图的广度优先遍历类似于树的（）。*［单选题］

*

层序遍历,先序遍历

中序遍历；层序遍历

先序遍历；层序遍历

层序遍历；中序遍历

19.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）*

［单选题］*

第i列0元素的个数之和

第i行非。元素的个数之和

第i列非0元素的个数之和

第i行0元素的个数之和

20.请写出上图所示二叉树的先序遍历结果中序遍历结果

,后序遍历结果,层序遍历结果

［填空题］*

空1答案：ABCDEGF

空2答案:CBEDAGF

空3答案：CEDBFGA

空4答案：ABGCDFE

011100.

100010.

100010.

100001.

011000.

000100.

21.已知图中包含顶点A、B、