20232023学年安工大其次学期期末考试《数据结构B》试卷(B)

本文格式为Word版，下载可任意编辑——20232023学年安工大其次学期期末考试《数据结构B》试卷(B)………………装………………订…………………线………………课程________________________班级________________________姓名__________________________学号________________________………………密………………封…………………线………………安徽工业大学试题纸（一）题号得分一二三四五六七八九十十一十二十三十四十五十六十七十八十九二十总分2023~2023学年其次学期期末考试《数据结构B》试卷（B）一、单项选择题（1.5×16＝24分）1.假定初始序列是递增的,并且按递增序排列,则()排序方法花时间最少。A.快速B.shellC.直接插入D.冒泡2.二维数组a[0..8,1..10]按行存放时元素a[8,5]的起始地址与按列存放时元素()的起始地址一致。A.a[8,5]B.a[3,10]C.A[5,8]D.A[0,9]3.分别以以下序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。A．(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90)C.(100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)4．在循环链表中设立一个头结点的理由是()。A.便于找到链表的首结点B.可以用头结点记录链表长度C.可以使得作插入,删去时不必顾及插入的或删去的结点是否链表的首结点。D.可以把首结点与尾结点公开5.在有n个叶子结点的哈夫曼树中，其结点总数为()。A.不确定B.2nC.2n+1D.2n-16.任何一个无向连通图的最小生成树()。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在7．下面关于串的表达中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储8.设有—顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，假使6个元素出栈的顺序是s2,s4,s3,s6,s5,s1，则栈的容量至少应当是（）。A．3B．4C．5D．69.线性表中正确的说法是（）。A.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个元素C.表中的元素必需按由小到大或由大到小排序D.除了第一个和最终一个元素外，其余元素都有一个且仅有一个直接前驱和直接后继10.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为()。A.98B.99C.50D.4811.某线性表中最常用的操作是在最终一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表12.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．813．循环队列A[m]存放其元素，用front和rear分别表示队头及队尾，则循环队列空的条件是（）。A．(Q->rear+1)%m==Q->frontB．Q->rear==Q->front+1C．Q->rear+1==Q->frontD．Q->rear==Q->front14.以下关于算法的说法，正确的是（）。A．算法最终必需由计算机程序实现。B．算法的可行性是指指令不能有二义性。C．为解决某问题的算法与为该问题编写的程序含义是一致的。D．程序一定是算法。15.图的广度优先探寻类似于树的()遍历。A.先序B.中序C.后序D.层次16..对线性表进行二分查找时，要求线性表必需（）。A.以链接方式存储B.以顺序方式存储C.以链接方式存储且结点按关键字排序D.以顺序方式存储但结点必需按关键字排序………………装………………订…………………线………………课程________________________班级________________________姓名__________________________学号________________________………………密………………封…………………线………………安徽工业大学试题纸（二）二、填空题（1×16＝16分）1．具有7层结点的完全二叉树至少有（）个结点，至多有（）个结点。2．在图形结构中，每个结点的前驱节点数和后续结点数可以有（），6个顶点的无向图至少要（）条边才是连通图。3．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的状况下，平均需要比较（）个结点。4．二维数组A[6][8]采用行序为主方式存储，每个元素占4个存储单元，已知A的起始存储地址(基地址)是1000，则A[2][3]的地址是（）。5．已知二叉树先序为ABDEGCF，中序为DBGEACF，则后序一定是（）。6．求以下广义表的运算结果：GetTail(GetHead(((a,b),(c,d))))是（）。7．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率状况下查找成功所需的平均比较次数为（）。8．用冒泡排序法对n个记录进行排序，第一趟要比较（）个元素,其次趟要比较（）个元素。9．（）法设计的Hash函数一定不会发生冲突。10．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是（）、（）、（）、（）。三、判断题（10X1=10分）1．二叉树是度为2的有序树。（）2．顺序表可以用一维数组表示，因此顺序表与一维数组在结构上是一致的，可以通用。（）3．任何一个递归过程都可以转换成非递归过程。（）4．广义表中的元素可以是一个不可分割的原子，或者是一个非空的广义表。（）5．有向图中顶点V的入度等于其邻接矩阵中第V列中的1的个数。（）6．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（）7．排序算法中的比较次数与初始元素序列的排列无关。（）8．数据的规律结构说明数据元素之间的顺序关系,它依靠于计算机的储存结构.()9．串是一种数据对象和操作都特别的线性表。（）10．二叉树中序线索化后，不存在空指针域。()四、应用题。（共30分）1．已知10个待排序的记录，其关键码分别为75，87，68，92，88，61，77，96，80，72，用简单项选择择排序、快速排序和堆排序对其进行排序，写出第一趟排序后结果。(9分)2．设电文由6个字符A，B，C，D，E，F组成，在电文中出现的次数分别为：10,4,8,3，2,7。试画出用于编码的哈夫曼树，并列出每个字符的编码。(7分)3．已知一组元素为(30,15,28,20,24,10,12,68,35,50,46,55)，试画出按元素排列次序生成的一棵二叉排序树(6分)4．（共8分）设有以下带权无向图：v1192133v51816v211v6