微信小程序数据结构期末复习题一
一、单选题
1.对一个算法的评价，不包括如下( B )方面的内容。
A．健壮性和可读性
B．并行性
c．正确性
D.时空复杂度
2．在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A)。
A.p->next=HL->next; HL->next=p;
B. p->next=HL; HL=p;
C.p->next=HL; p=HL;
D.HL=p; p->next=HL;
3．对线性表，在下列哪种情况下应当采用链表表示?( B )
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
c.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
4.一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是( C )
A.2 3 1
B.3 2 1
C.3 1 2
D.1 2 3
5. AOV网是一种( D )。
A．有向图
B.无向图
c．无向无环图
D.有向无环图
6.采用开放定址法处理散列表的冲突时，其平均查找长度( B )。
A.低于链接法处理冲突
B.高于链接法处理冲突
c．与链接法处理冲突相同
D．高于二分查找
7．若需要利用形参直接访问实参时，应将形参变量说明为( D )参数。
A．值
B．函数
c．指针
D．引用
8．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ).
A．行号
B．列号
c．元素值
D.非零元素个数
9．快速排序在最坏情况下的时间复杂度为( D )。
A. O(log2n)
B. O(nlog2n)
c. 0(n)
D. 0(n2)
10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。
A.O(n)
B.O(1)
c.O(log2n)
D.O(n2)
二、运算题
1.数据结构是指数据及其相互之间的__联系____。当结点之间存在M对N(M:N)的联系时，称这种结构为____图（或图结构)_____
2.队列的插入操作是在队列的_____尾_____进行，删除操作是在队列的____首____进行。
3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是_____top==0__(要超出才为满)_____。
4．对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为___o( 1)____，在表尾插入元素的时间复杂度为____o(n)____。
5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7﹐列下标j从0到3，则二维数组W的数据元素共占用__128____个字节。W中第6行的元素和第4列的元素共占用___44___个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为___108_____。
6.广义表A= (a,(a,b),((a,b),c)),则它的深度为__3__，它的长度为___3___。
7.二叉树是指度为2的___有序__树。一棵结点数为N的二叉树，其所有结点的度的总和是____n-1_____。
8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个____有序序列__。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的___后缀表达式（或逆波兰式)____。
9.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为___2n__个，其中__n-1___个用于指向孩子，___n+1__个指针是空闲的。
10.若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为___2i+1___,右孩子元素为___2i+2___，双亲元素为___(i-1)/2____。
11.在线性表的散列存储中，处理冲突的常用方法有___开放定址法___和____链接法___两种。
12.当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用___快速___排序;当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用____归并___排序。
三、运算题
1.已知一个6×5稀疏矩阵如下所示，
试:
( 1)写出它的三元组线性表;
((1,5,1),(3,2,-1).(4,5,-2),(5,1,5),(6,3,7))
- 给出三元组线性表的顺序存储表示。
三元组线性表的顺序存储表示如图7示。
- 设有一个输入数据的序列是{46,25,78,62,12,80}，试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
如图8所示
3.对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出:
(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树;
DFS:①②③④⑤
- 从顶点②出发进行广度优先搜索所得到的广度优先生成树;
BFS: ②③④⑤①
4.已知一个图的顶点集V和边集E分别为:
中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
拓朴排序为:4 3 6 5 7 21
四、阅读算法
(1)指出该算法的功能;
判断n是否是素数（或质数)
- 该算法的时间复杂度是多少?2.写出下述算法的功能:void AJ(adjlist
答： 
功能为:从初始点vi出发广度优先搜索由邻接表GL所表示的图
五、算法填空
如下为二分查找的非递归算法，试将其填写完整
答：(low+high)/2；high=mid-1；low=mid+1
六、编写算法
HL 是单链表的头指针，试写出删除头结点的算法
ElemType DeleFront(LNode*& HL)
请先 ！