2022年大连海事大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.332、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a，b，e，c，d，f，B.ac，f,e，b，dC.a，e，b，c，f,d，eD.a，d，f，c，b3、链表不具有的特点是（）。A.插入、删除不需要移动元素可随机B.访问任一元素C.不必事先估计存储空间所需空D.间与线性长度成正比4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.46、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只B有Ⅱ．CⅠ和Ⅱ．DⅠ和Ⅲ7、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树．所有叶B结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.21510、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）。A.选择排序法B.插入排序法C.快速排序法D.堆排序法二、填空题11、属于不稳定排序的有______。12、阅读下列程序，指出其功能，并写出空格处应填上的语句。13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。14、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。15、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。17、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、循环队列也存在空间溢出问题。（）22、数组不适合作为任何二叉树的存储结构。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）25、顺序存储结构的主要缺点是不利于插入或删除操作。（）26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）27、无环有向图才能进行拓扑排序。（）28、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）四、简答题29、已知n阶下三角矩阵A（即当i＜j时，有a=0），按照压缩存储的思想，可以将其ij主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素a的存放位置的公式。ij30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCA