2022年唐山师范学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年唐山师范学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序C.归并排序D.直接插入排序2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.NB.2N-1C.2ND.N-13、算法的计算量的大小称为计算的（）。A.效率B.复杂性C.现实性D.难度4、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.45、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341566、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。A.（2，5，12，16）26（60，32，72）B.（5，16，2，12）28（60，32，72）C.（2，16，12，5）28（60，32，72）D.（5，16，2，12）28（32，60，72）二、填空题11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元组表示弧<a，b>及弧上的权d。E(G)为E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。13、在单链表L中，指针P所指结点有后继结点的条件是______。14、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。15、文件可按其记录的类型不同而分成两类，即______和______文件。16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。18、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排文件的目的是为了多关键字查找。（）21、在链队列中，即使不设置尾指针也能进行入队操作。（）22、二维以上的数组其实是一种特殊的广义表。（）23、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）24、树形结构中元素之间存在一对多的关系。（）25、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）26、归并排序辅助存储为O（1）。（）27、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。（）排序的结果为：12，13，15，18，20，60（）排序的结果为：13，15，18，12，20，60（）排序的结果为：13，15，20，18，12，60（）排序的结果为：12，13，20，18，15，6030、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。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、已知指针p指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG，LLINK，INFO，RLlNK，RTAG），且规定线索树的最左下结点的LLINK域和最右下结点的RLINKt域指向表头。33、设二叉树用二指针结构存储（可以是动态存储结构），元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。34、若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。35、试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为：

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】B4、【答案】C5、【答案】C6、【答案】A7、【答案】D8、【答案】B9、【答案】C10、【答案】B二、填空题11、【答案】n（n-1）/212、【答案】50；413、【答案】P->next!=NULL14、【答案】逻辑结构；物理结构；操作（运算）；算法15、【答案】操作系统文件；数据库16、【答案】0；n+1；top[1]+1=top[2]17、【答案】O（m+n）18、【答案】93三、判断题19、【答案】×20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、简答题29、答：①快速排序②起泡排序③直接插入排序④堆排序30、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：31、答：（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。算法可分为以下两步：①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新