7.不稳定的排序方法是( )
a.直接插入排序 b.冒泡排序。
c.堆排序 d.二路归并排序。
8.设散列表表长m=14，散列函数为h（k）=k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是( )
a.3 b.5
c.8 d.9
9.若元素1，2，3依次进栈，则退栈不可能出现的次序是( )
a.3，2，1 b.2，1，3
c.3，1，2 d.1，3，2
10.直接插入排序的时间复杂度是( )
11.稀疏矩阵是指( )
a.元素少的矩阵 b.有少量零元素的矩阵。
c.有少量非零元素的矩阵 d.行数、列数很少的矩阵。
12.深度为k（k≥1）的二叉树，结点数最多有( )
a.2k b.2k-1
c.2k-1 d.2k-1-1
13.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为( )
a.23 b.37
c.44 d.46
14.有n个顶点的有向完全图的弧数为( )
b.2nd.2n（n+1）
15.图的深度优先搜索类似于二叉树的( )
a.先根遍历 b.中根遍历。
c.后根遍历 d.层次遍历。
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.下列程序段的时间复杂度为。
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x++;17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是。
18.在表长为n的顺序表上做删除运算，平均要移动的结点个数为。
19.在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是。
20.队列又称为___的线性表。
21.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是。
22.对于任何一棵二叉树t，如果其终端结点数为n0，度为2的结点数为n2，则n2
23.一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有___个。
24.若连通图g的顶点个数为n，则图g的生成树的边数为。
25.一个具有n个顶点的无向图的边数最多为。
26.中根遍历二叉排序树所得到的结点访问序列是键值的___序列。
27.冒泡排序的平均时间复杂度为。
28.将序列建成堆，则只需把20与___互相交换。
三、应用题(本大题共5小题，每小题6分，共30分)
29.如题29图所示，在栈的输入端元素的输入顺序为a，b，c，d，进栈过程中可以退栈，写出在栈的输出端以a开头和以b开头的所有输出序列。
题29图。30.一棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。
题30图。31.将题31图所示的一棵二叉树转换成森林。
题31图。32.对于有向无环图：
1）叙述求拓扑排序算法的基本步骤；
2）对于题32图，写出它的4个不同的拓扑排序序列。
题32图。33.判别以下序列是否为堆。如果不是，则把它调整为堆。
四、算法设计题(本大题共2小题，每小题7分，共14分)
个结点的完全二叉树按结点编号将值顺序存放在一维数组元素a［1］至a［n］中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。
35.试写出冒泡排序算法。
数据结构导论试题
一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 二00一年下半年全国高等教育自学考试。数据结构导论试卷。一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 2.在一个具有n个结点的单链表达中查找值为m的某结点，若查找成功，则...
全国数据结构导论试题
全国2011年10月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.设栈s和队列q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈s，元素退栈后即进入队列q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈s的容量至少为 a...
全国数据结构导论试题
全国2013年1月高等教育自学考试。数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.数据的基本单位是。a.数据元素 b.数据项。c.字段 d.域。2.算法的空间复杂度是指。a.算法中输入数据所占用的存储空间的大小。b.算法本身所占用的存储空间的大小。c....