(高等教育)《数据结构》期中考试试卷_华工大

数据结构一 选择题（从下列答案选项中选出一个正确答案，每小题2分)1. 在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。A逻辑结构B顺序存储结构C链式存储结构D. 以上都对2. 线性表就是顺序表，这种说法（）。A正确B错误3. 若已知一个栈的入栈序列是1, 2, 3, 4, 5，不可能得到的输出序列是（ ）。A2,3,4,1,5 B 5,4,1,3,2 C2,3,1,4,5 D1,5,4,3,24. 串的逻辑结构与（）的逻辑结构不同。A. 栈B. 队列C. 树D. 线性表5. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）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，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。A. 13B. 33C. 18D. 409. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（ ）。A. 正确B. 错误10. 树形结构的特点是：一个结点可以有（）。 A、多个直接前趋 B、多个直接后继 C、多个前趋 D、一个后继11. 在一棵高度为h的满三叉树中，结点总数为（） A、3h-1 B、(3h-1)/2 C、(3h-1)/3 D、3h12. 设森林T中有4棵树，结点个数依次为n1, n2, n3, n4，当把森林T转换成一棵二叉树后，二叉树根结点的右子树上有（ ）个结点。An1-1Bn1Cn1+n2+n3Dn2+n3+n413. 任何一个无向连通图的最小生成树（）。A只有一颗B有一颗或多棵C一定有多棵D可能不存在14. 一个无向连通图的生成树是含有该连通图的全部顶点的（）。 A、极小连通子图 B、极小子图 C、极大连通子图 D、极大子图15. 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零，这种说法( )。A. 正确B. 错误16. 对于关键字序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（）的结点开始。A100B60C12D1517. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n）的是（） A、堆排序 B、冒泡排序 C、直接选择排序 D、快速排序18. 下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆19. 在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整使其平衡。ALLBLRCRLDRR 20. 常采用下面几种方式解决散列法中出现的冲突问题（）。A数字分析法、除余法、平方取中法 B数字分析法、除余法、线性探测法 C数字分析法、线性探测法、多重散列法 D线性探测法、多重散列法、链地址法二 填空题（每空2分）1. 以下程序段的时间复杂度是_ ，其中n为正整数。void fun(int n)int i=1,k=100;while(in) k=k+1; i+=2;2. 对于长度为n的顺序表，插入或删除元素的平均时间复杂度为_。对于顺序栈或顺序队列，插入或删除元素的时间复杂度为_。3. 一个nn的对称矩阵若采用压缩存储，需要存储_个元素。4. 设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序为b，d，c，f，e，a，则栈S的容量至少应该是_。5. 判定一个环形队列qu（最多元素为MaxSize）为空的条件是_，判定环形队列qu为满队列的条件是_ _ _。6. 已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为_。7. 取出广义表A=(x,y,z),(a,b,c,d)中原子b的函数是_。8. 无向图中的极大连通子图称为该无向图的_。9. 在有序表A1.20中，采用二分查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为_。10. 一个深度为k的，具有最少结点的完全二叉树按层次（同层次从左到右）用自然数依次对结点编号，则编号最小的叶子的序号是_；三 问答题：1. 在单链表中设置头结点的作用是什么？2. 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否稀疏矩阵？3. （已知二叉树的中序序列为DCEFBHGAKJLIM, 后序序列为DFECHGBKLJMIA，画出该二叉树。4. 已知如下一个无向图，要求；（1） 画出该无向图的邻接表；（2） 基于你给出的邻接表，画出以顶点A为出发点遍历图所得到的DFS序列。FDCBEGA5. 下图是用邻接表存储的图，画出此图，并画出由顶点C出发按深度优先遍历该图所得到的DFS生成树。6. 已知关键字的输入序列如下：（46，88，45，39，70，58，101，10，66，34），画出按关键字的输入次序生成的一棵二叉排序树，并求在等概率情况下查找成功的平均查找长度。7. 设有一组关键字序列：（29，18，25，47，58，12，51，10）要按照关键字值递增的次序进行排序。（1）若采用初始增量为4的希尔排序，写出第一趟排序的结果：（2）若采用以第一个元素为基准元素的快速排序法，写出第一趟排序的结果：8. 以下面的数据作为叶子结点的权值构造一颗哈夫曼树，并计算带权路径长度WPL。5，6，7，8，9，10，15，18，229. 已知散列地址空间为至14，散列函数H(K)=K%13，采用线性探查法处理冲突，将下列关键字序列依次存入散列表中，并求出在等概率情况下查找成功的平均查找长度ASL。（240，29，345，189，100，20，21，35，3，208，78，99，45，350） 四 算法填空：请仔细阅读下面的堆排序算法：n个待排序的学生成绩记录存放在一维数组R1.n中，结点类型及相关定义如下： #define n 200 typedef struct stud int num;char name20;float score; rectype; rectype Rn+1;要求按成绩(score)由高到低排列学生记录，将以下堆排序算法补充完整，使它们能正确工作。SIFT(R, i, m) /在数组Ri.Rm构成的完全二叉树中，已知Ri的左、右子树都是堆，rectype R ; /现将Ri为根的子树也调整为堆int i, m;int j; rectype temp;