《数据结构》期中考试试卷_华工大

《《数据结构》期中考试试卷_华工大》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》一．选择题（从下列答案选项中选出一个正确答案，每小题2分)1.在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。A．逻辑结构B．顺序存储结构C．链式存储结构D.以上都对2.线性表就是顺序表，这种说法（）。A．正确B．错误3.若已知一个栈的入栈序列是1,2,3,4,5，不可能得到的输出序列是（）。A．2,3,4,1,5 B．5,4,1,3,2 C．2,3,1,4,5D．1,5,4,3,24.串的逻辑结构与（）的逻辑结构不同。A.栈B.队列C.树D.线性表5.如果一个串中的所有字符均在另一串中出现，则说前者是后

2、者的子串。（）A.正确B.错误6.设有两个串P和Q，求Q在P中首次出现的位置的操作称为（）。A.连接B.模式匹配C.求子串D.求串长7.已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（）。A.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1B.0，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1C.-1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，D.-1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，18.设有一个10阶的对称矩阵A，采用压

3、缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。A.13B.33C.18D.409.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（）。A.正确B.错误10.树形结构的特点是：一个结点可以有（）。A、多个直接前趋7B、多个直接后继C、多个前趋D、一个后继1.在一棵高度为h的满三叉树中，结点总数为（）A、3h-1B、(3h-1)/2C、(3h-1)/3D、3h2.设森林T中有4棵树，结点个数依次为n1,n2,n3,n4，当把

4、森林T转换成一棵二叉树后，二叉树根结点的右子树上有（）个结点。A．n1-1B．n1C．n1+n2+n3D．n2+n3+n43.任何一个无向连通图的最小生成树（）。A．只有一颗B．有一颗或多棵C．一定有多棵D．可能不存在4.一个无向连通图的生成树是含有该连通图的全部顶点的（）。A、极小连通子图B、极小子图C、极大连通子图D、极大子图5.在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零，这种说法(   )。A.正确B.错误6.对于关键字序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，

5、必须从关键字值为（）的结点开始。A．100B．60C．12D．157.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n）的是（）A、堆排序B、冒泡排序C、直接选择排序D、快速排序71.下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。A、选择B、冒泡C、归并D、堆2.在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整使其平衡。A．LLB．LRC．RLD．RR3.常采用下面几种方式解决散列法中出现的冲突问题（）。A

6、．数字分析法、除余法、平方取中法B．数字分析法、除余法、线性探测法C．数字分析法、线性探测法、多重散列法D．线性探测法、多重散列法、链地址法一．填空题（每空2分）1.以下程序段的时间复杂度是_____________，其中n为正整数。voidfun(intn){inti=1,k=100;while(i

7、储，需要存储___________________________个元素。4.设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序为b，d，c，f，e，a，则栈S的容量至少应该是________________。5.判定一个环形队列qu（最多元素为MaxSize）为空的条件是__________________________________________，判定环形队列qu为满队列的条件是__________________________________________

8、。6.已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为______________。7.取出广义表A=((x,y,z),(a,b,c,d))中原子