数据结构试题试卷
- 格式：docx
- 大小：38.67 KB
- 文档页数：3
数据结构试题试卷
南京工业大学数据结构试题（b）卷（闭）
2021--2021学年第二学期使用班级地信0401-02班级学号姓名
题号罚球一二三四五总分一、选择题（15×2’＝30’）
1.算法的计算量的大小称为计算的。a．效率b．复杂性c．现实性d．难度
2.从逻辑上可以把数据结构分成两大类。a．动态结构、静态结构b．顺序结构、链式结构c．线性结构、非线性结构d．初等结构、构造型结构
3.以下数据结构中，是非线性数据结构。a．树b．线性表c．队d．栈
4.下面观点错误的就是。
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n之下，复杂度o(n)的算法在时间上总是强于复杂度o(2n)的算法(3)所谓时间复杂度就是指最坏情况下，估计算法继续执行时间的一个上界(4)同一个算法，同时实现语言的级别越高，继续执行效率就越高a．（1）b．（1）（2）c．（3）d．（1）（4）
5.下述哪一条是顺序存储结构的优点？a．存储密度大b．插入运算方便c．删除运算方便d．可方便地用于各种逻辑结构的存储表示
6.设一个链表最常用的操作方式就是在末尾填入结点和删掉尾结点，则采用最节省时间。a．单链表中b．单循环链表c．拎尾指针的单循环链表d．率先垂范结点的双循环链表
7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂
德博瓦桑县(1<=i<=n+1)。。a．o(0)b．o(1)c．o(n)d．o(n2)
南京工业大学第1页共3页
8.下面关于串的的描述中，哪一个就是不恰当的？。a．串成就是字符的非常有限序列b．空串就是由空格形成的串c．模式匹配就是串成的一种关键运算d．串成既可以使用顺序存储，也可以使用链式存储
9.设有数组a[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数 胡海宾内存首地址ba已经开始顺序放置，当用来列入主放置时，元素a[5，8]的存储首地址为a．ba+141b．ba+180c．ba+222d．ba+225
10.设树t的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则t中的叶子数
为。a．二叉树的度为2b．一棵二叉树的度可以大于2c．二叉树中至少存有一个结点的度为2d．二叉树中任何一个结点的度都为2
11.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是。a．9b．11c．15d．条件不足，无法
12.．一棵全然二叉树上加1001个结点，其中叶子结点的个数就是a．250b．500c．254d．以上都不对
13.一个n个顶点的连通无向图，其边的个数至少为。a．n-1b．nc．n+1d．nlogn
14.以下哪一种图的邻接矩阵就是等距矩阵？。a．有向图b．定义明确图c．aov网d．aoe网
15.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称
该排序算法就是不稳定的。就是不稳定的排序方法。a．腹满排序b．福兰县排序c．轻易插入排序d．直观挑选排序
二、填空题（10×2’＝20’）
1．抽象数据类型的定义仅依赖于它的一组__（1）_，而与_（2）_毫无关系，即为不论其内部结构例如
何变化，只要它的_（3）_不变，都不影响其外部使用。
2．栈就是____（4）___的线性表，其运算遵从___（5）____的原则。
3．高度为8的完全二叉树至少有___（6）___个叶子结点。
南京工业大学第2页共3页
4．在图g的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的
___（7）___；对于有向图来说等同于该顶点的___（8）___。
5．文件可按其记录的类型不同而分成两类，即___（9）___和__（10）____文件。 三、简答题（4×6’＝24’）
1．描述以下3个概念的区别：头指针、头结点、首元结点。
2．什么就是队列的骗人溢现象？如何去化解这种现象？
3．用一维数组存放一棵完全二叉树：abcdefghijkl。请写出后序遍历该二叉树的访问结点序
列于。
4．对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其
中哪种方法？其次挑选出哪种方法？若仅考量排序结果的稳定性，则必须挑选出其中哪种方法？若仅从平均值情况下排序最快这一点考量，则必须挑选出其中哪些方法？
四、下面的邻接表表示一个给定的无向图（16’）
1．得出从顶点v1已经开始,对图g用深度优先搜寻法展开不下历时的顶点序列；(8’)2．得出从顶点v1已经开始,对图g用广度优先搜寻法展开不下历时的顶点序列。(8’)
五、编程理解题（10’）
用链表则表示的数据的直观挑选排序，结点的域为数据域data，指针域next；链表首指针为head，链表独眼结点。selectsort(head)p=head;
while(p（1）){q=p;r=(2)_______while((3)______){if((4)_______)q=r;r=(5)_______;}
tmp=q->data;q->data=p->data;p->data=tmp;
p=(6)_______;南京工业大学第3页共3页
