2022年江苏科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年江苏科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.332、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是该函数的程序段，请将未完成的部分填入，使之完整。②执行程序，f（6，4）=______。12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。13、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。14、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有______检索和______检索。15、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。16、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、倒排文件是对次关键字建立索引。（）21、串是一种数据对象和操作都特殊的线性表。（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。（）23、二叉树是一般树的特殊情形。（）24、树形结构中元素之间存在一对多的关系。（）25、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（）26、在任何情况下，归并排序都比简单插入排序快。（）27、B-树中所有结点的平衡因子都为零。（）28、无环有向图才能进行拓扑排序。（）四、简答题29、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54，需依次与哪些元素比较?（3）若查找元素90，需依次与哪些元素比较?（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。31、已知一个整数序列A＝（a0，a1，…，an－1），其中0≤ai＜n（0≤i≤n），若存在ap1＝ap2＝…＝apm＝x且m＞n/2（0≤pk≤n，1≤k≤m），则称x为A的主元素。例如A＝（0，5，5，3，5，7，5，5），则称5为主元素；又如A＝（0，5，5，3，5，1，5，7）则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出－1。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C＋＋或Java语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。五、算法设计题32、结点类型和存储结构如下：试设计一个排序算法，要求不移动结点的存储位置，只在结点的count字段记录结点在排序中的序号，并将排序结果按升序输出。33、设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为O（n）。34、借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[1..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“notfind”信息。请编写出算法并简要说明算法思想。35、在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。顺序存储结构的线性表描述为：

参考答案一、选择题1、【答案】B2、【答案】A3、【答案】B4、【答案】B5、【答案】A6、【答案】C7、【答案】D8、【答案】C9、【答案】D10、【答案】A二、填空题11、【答案】①1；1；f（m，n-1）；n②912、【答案】480+8=488；480-32=44813、【答案】归并；堆14、【答案】关键字；记录号；记录号；顺序；直接15、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null16、【答案】（）；（（））；2；217、【答案】（rear+1）%（n-m+1）==front18、【答案】23；100CH三、判断题19、【答案】√20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。（2）证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。30、答：（1）判定树如图所示：（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。（4）31、答：（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步：①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1