全国2023年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.2 b.
3 c.4 d.6
2.设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为( )
a.线性表的顺序存储结构 b.队列 c.线性表的链式存储结构 d.栈。
3.下列程序段的时间复杂度为( )
i=0；s=0；
while（s
4.设a是n×n的对称矩阵，将a的对角线及对角线上方的元素aij(1≤i,j≤n,i≤j)以列优先顺序存放在一维数组元素b［1］至b［n(n+1)/2］中，则元素aij(i≤j)在b中的位置为( )
5.在有向图g的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是( )
中有弧 中有一条从vi到vj的路径 中没有弧 中有一条从vj到vi的路径。
6.下列序列中，由第一趟快速排序可得到的序列（排序的关键字类型是字符串）是( )
a.［da，ax，eb，de，bb］ff［ha，gc］ b.［cd，eb，ax，da］ff［ha，gc，bb］
c.［gc，ax，eb，cd，bb］ff［da，ha］ d.［ax，bb，cd，da］ff［eb，gc，ha］
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.2n d.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图题31图题32图。
30.一棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。
31.将题31图所示的一棵二叉树转换成森林。
32.对于有向无环图：
1）叙述求拓扑排序算法的基本步骤；
2）对于题32图，写出它的4个不同的拓扑排序序列。
33.判别以下序列是否为堆。如果不是，则把它调整为堆。
四、算法设计题(本大题共2小题，每小题7分，共14分)
个结点的完全二叉树按结点编号将值顺序存放在一维数组元素a［1］至a［n］中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。
35.试写出冒泡排序算法。
全国数据结构导论试题
全国2013年1月高等教育自学考试。数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.数据的基本单位是。a.数据元素 b.数据项。c.字段 d.域。2.算法的空间复杂度是指。a.算法中输入数据所占用的存储空间的大小。b.算法本身所占用的存储空间的大小。c....
全国数据结构导论试题
全国2012年1月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.结点按逻辑关系依次排列形成一条 锁链 的数据结构是 a.集合 b.线性结构 c.树形结构 d.图状结构。2.下面算法程序段的时间复杂度为 for int i 0 ifor int j 0 ...
数据结构导论试题
一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 二00一年下半年全国高等教育自学考试。数据结构导论试卷。一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 2.在一个具有n个结点的单链表达中查找值为m的某结点，若查找成功，则...