一、单选题(1题2分，共20分)堆栈和队列的共同特征是(a )。
a .仅允许在端点插入和删除元素
b .都是先进的后起之秀
c .均为先进先出
d .没有共同点且以链接方式存储的队列，在进行插入运算时(d )。
a .仅修改头指针
b .修改头、尾指针
c .只修改末尾指针
d .头、尾指针都有可能修改(尾插和头插) )以下数据结构中，哪个是非线形结构？ (d ) ) )。
a .队列
b .栈
c .线性表
d .假设二叉树[树形结构]中设有二维排列A[m][n]，A[0][0]的存储位置为644(10 )，A[2][2]的存储位置为676 ) 10 )，各要素占有一个空间C
A.688
B.678
C.692
D.696树最适合表示(c )。
a .有规律的数据要素
b .无序的数据元素
c .要素之间具有分支层次关系的数据
d .要素之间没有联系的数据二叉树的第k层的节点数最大(d )。
A.2k-1
B.2K 1
C.2K-1
在D. 2k-1一维排列A[19]中存储有18个要素的顺序表，第一个要素存储在A[1]中的情况下，如果现在进行二分搜索，则搜索A[3]的比较序列的下标依次为(d )
a.1、2和3
b.9、5、2和3
c.9、5和3
d.9、4、2、3对n个记录文件进行高速排序，所需辅助存储区域大致为(c )时间复杂度为n ) 2
A.o (一) )。
是乙. b.o(n )
c.o(1og2n ) ) )。
d.o(N2 )线性表) 7、34、55、25、64、46、20、10 )存储散列时，如果选择h ) k )=K %9作为散列函数，则散列地址为1的元素是) d
A.1
B.2
C.3
D.4设置了6个节点的无向图，该图至少要有(a )边才能确保是一个连通图。
A.5
B.6
C.7
D.8二、填空题(每空1分，共26分)通常从_准确性_、_可读性_、_健壮性_和_效率_ 4个方面评价算法质量。 一种算法的时间复杂度为(n3 n2log2n 14n )/n2，其数量级由(n_表示)。 一棵树的广义表表示为a(c，d ) e，f，g )，h ) I，j ) )，树中包含的节点数为_9_个，树的深度为_3_，树的度为_3_。 加装式9 2 3 - 10 2/-的值为_-1_。 与骑马订式(3 4X )-2Y/3对应后缀式为_3) 4x*2y*3/-_。 在链表中存储二叉树时，每个节点除了数据域外，还包含指向左边孩子和右边孩子的两个指针。 在此存储结构中，n个节点的二叉树共享_2n_个指针字段，其中_n-1_个指针字段存储地址，_n 1_个指针为空指针。 对于具有n个顶点和e条边的有向图和无向图，对应邻表中包含的边节点分别为_e_个和_2e_个。 AOV网是_有向无环_的图。 具有n个顶点的有向图包含_n(n-1 ) _条边，具有n个顶点的有向图包含_2n(n-1 ) _条边。 假设一个线性表为(12、23、74、55、63、40 )，在Key % 4的条件下分割相同的馀数要素成为一个子表，则得到的四个子表分别为) 12、40 _、_74_、_ 23 在累计排序过程中，对其中一个分支节点进行筛选运算的时间复杂度为_o(log2n )，累计排序过程整体时间复杂度为_no ) log2^n。 在快速排序、堆栈排序和合并排序中，_合并_排序很稳定。 三、算题(各题6分，共24分)将线性表链接保存在以下数组a中，表头指针为A [0].next，试着制作此线性表。
a 1234567 data 605078903440 next 3572041 (78、50、40、60、34、90 )请绘制下图中的邻接矩阵和邻接表。
_ 1234510102101013101141010150110010已知图的顶点集v和边集e分别为v={1、2、3、4、5、6、7}；
e={ (1，2 ) 3，1，3 ) 5，1，4 ) 8，2，5 ) 10，2，3 ) 6，3，4 ) 15，
(3，5 ) 12，3，6 ) 9，4，6 ) 4，4，7 ) 20，5，6 ) 18，(6，7 ) 25}；
尝试用巡航卷曲算法获得最小生成树，并导出在最小生成树中顺序获得的每条边。 (1，2 )3- ) (4，6 )4- ) (1，3 )5- ) (1，4 )8- ) (2，5 ) 10-”) 4，7 ) 20
每次向弱寒风堆中添加数据4、2、5、8、3时，都会描绘添加数据后堆的变化。 4
二四
2，4，5
2，4，5，8
二三五四八
四.阅读算法(每题7分，共14分)链接列表我的笔记)。
LinkList L){//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L；S1： while(p－>next) p=p－>next；S2： p－>next=q；q－>next=NULL； } return L； }请回答下列问题：
（1）说明语句S1的功能；
查询链表的尾结点
（2）说明语句组S2的功能；
将第一个结点链接到链表的尾部，作为新的尾结点
（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。
该算法的功能是：返回的线性表为（a2,a3,…,an,a1）递归地后序遍历链式存储的二叉树
五、算法填空（共8分）二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item){ if (BST==NULL) return false; //查找失败 else { if (item==BST->data){ item=BST->data;//查找成功 return _true_;} else if(item<BST->data) return Find(_BST->left_,item); else return Find(_BST->right_,item); }//if} 六、编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)