专升本《数据结构》-试卷及答案.docx

专升本数据结构一、（共75题，共150分）.数据的基本单位是（）o （2分）A.数据元素B.记录C.数据对象 D.数据项.标准答案：A1 .（）是数据的不可分割的最小单位。（2分）A.数据对象B.数据元素 C.数据类型 D.数据项.标准答案：D.算法的空间复杂度是对算法（）的度量。（2分）A.时间效率 B.空间效率 C.可读性 D.健壮性.标准答案：B.（）是限制了数据元素的部结构仅为一个字符的线性表。（2分）A.栈B.队列C.串D.数组.标准答案：B.串的长度是指串中所含（）的个数。（2分）A.不同字符 B.不同字母 C.相同字符 D.所有字符.标准答案：D2 .采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（） 次。（2分）A. 1B. 2C. 3D. 4.标准答案：B.线性表的顺序存储结构是一种（）的存储结构。（2分）A.顺序存取B.随机存取 C.索引存取 D. Hash存取.标准答案：B.数组采用顺序存储,al和地址分别为1024和1150,每个元素占2字节，则m是O。（2分）A. 64B. 32C. 16D. 8.标准答案：A9.深度为h的二叉树，第h层最多有（）个结点。（2分）A. hB. 2-1C. 2,_,D. 2h.标准答案：C. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分）A. mB. m+1C. 2mD. m-l.标准答案：B.下面叙述错误的是O o （2分）A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系B.对于空队列进行出队操作过程中发生下溢现象C.有向图的邻接矩阵一定是对称的D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的.标准答案：C.以下与数据的存储结构无关的术语是（）o （2分）A.循环队列 B.双向链表 C.哈希表 D.数组.标准答案：D.在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分）A.0（l）B.O（log n）C.O（n）D.O（n2）.标准答案：A.在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分）A. kB. k-1C. 2kD. k+1.标准答案：D10 .在关键字序列（10,20,30,40,50）中，采用折半法查找20,关键字之间比较 需要（）次。（2分）A. 1B. 2C. 3D. 4.标准答案：C16 . 16某二叉树的后序遍历序列和和中序遍历序列均为abed,该二叉树的前序遍 历序列是（）。（2分）A. abedB. debaC. aebdD. dbea.标准答案：B. n个顶点的无向连通图的生成树，至少有（）个边。（2分）A. n（n-l） B. n（n-l）/2 C. 2n D. n-1.标准答案：D.可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分）A.队列B.树.标准答案：A17 .可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分）A.队列B.树.标准答案：AA.队列B.树.标准答案：AA.队列B.树.标准答案：AC.栈D.集合.假设以数组A O.nT存放循环队列的元素，其头指针front指向队头元 素、尾指针rear指向队尾元素一个，则在少用一个元素空间的前提下，队列空的 判定条件为()。(2分)A. rcar= =frontB. (front+1) %n= =rcarC. rcar+l= =frontD. (rcar+1) %n= =front.标准答案：A.序列(21, 19, 37, 5, 2)经冒泡排序法由小到大排序，第一趟后所得结果为 ()o (2 分)A. (19, 21, 37, 5, 2)B. (19, 21, 5, 2, 37)C. (19, 21, 5, 37, 2)D. (19, 21, 2, 5, 37).标准答案：B.二叉链表适合作为()的存储结构。(2分)A.队列B.二叉树 C.树D.森林.标准答案：B,C,D20 .设哈希(Hash)函数为H(k)=k % 17,其中k为关键字，关键字。是同义词。(2分)A. 44,5,15 B. 28,45,62 C. 6,57,125 D. 201,31,48.标准答案：B.C.D.下列各项键值()序列不是堆的。(2分)A. 94, 68, 23, 16, 5B. 94, 23, 68, 5, 16C. 94, 23, 16, 68, 5D. 94, 16, 68, 23, 5.标准答案：C.D.在下列排序方法中，()的空间复杂度为0(n)。其中，n为参加排序的元素个数。 (2分)A. .择排序 B.快速排序 C.归并排序D.冒泡排序.标准答案：B,C.十字链表适合于()选作存储结构。(2分)A.队列B.稀疏矩阵C.边或瓠数较少的图D.二叉树.标准答案：B.C.基于数据的逻辑关系，数据的逻辑结构划分为()基本结构。(2分)A. 6类B. 5类C. 4类D. 3类.标准答案：C.（）不是算法具有的5个特性之一。（2分）A.有穷性 B.确定性 C.可行性 D.正确性.标准答案：D（2分）D.健壮性（2分）D.健壮性（2分）D.健壮性27 .算法的时间复杂度是对算法（）的度量。A.时间效率 B.空间效率 C.可读性.标准答案：A.线性表若采用锥式存储结构时，要求结点的存储单元地址（）o （2分）A.必须是连续的B.部分地址必须是连续的C.必须是不连续的D.连续或不连续都可以.标准答案：D.二维数组通常采用顺序存储，其优点是（）,（2分）A.便于增加存储空间B.防止下标溢出C.避免数据元素的移动D.便于依据下标进行随机存取.标准答案：D.采用顺序存储的线性表，若表长为n,在第i号元素之后插入一个元素时，需 要移动（）个元素。（2分）A. i+1B. iC. n-iD. n-i+1.标准答案：C.若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为_（2分）A. 1、4、3、2B.3、4、1、2C.4、3、2、1D.2、3、4、1.标准答案：B.数组aL. 256采用顺序存储，a的首地址为10,每个元素占2字节，则a21的地址是（）o （2分）A. 10B. 30C. 50D. 70.标准答案：C.深度为h的完全二叉树至少有（）个叶子结点。（2分）A.2,"+1B. 2（"）+1C.D. 2口.标准答案：D.若二叉树对应的二叉链表共有m个非空链域，则该二叉树有（）个结点的二叉 树。（2分）A. mB. m-1.标准答案：BA. mB. m-1.标准答案：BC. m+1D. 2m.下面叙述错误的是()o (2分)A.单链表是借助指针表示数据元素之间的逻辑关系B.在顺序栈的入栈操作过程中可能发生上溢现象C.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树是唯一的D.无向图的邻接矩阵一定是对称的.标准答案：C.以下()术语与数据的存储结构无关(2分)A.栈B.哈希表 C.线索树 D.双向链表.标准答案：A.在一个长度为n的链式队列中入队实现算法的时间复杂度为()o (2分)A.O(l)B.O(log n)C.O(n)D.0(n2).标准答案：A.队列的出队操作是指()操作。(2分)A.队尾删除 B.队头删除 C.队尾插入D.队头插入.标准答案：B.在关键字序列(10,15,20,25,30)中采用折半法查找25,依次与()关键字 进行了比较。(2分)A. 30,25B. 20,25C. 20, 30, 25 D. 25.标准答案：B4L 16某二叉树的前序遍历序列和和中序遍历序列分别为abed和bead,该二叉树的后序遍历序列是()o (2分)A. cbdaB. debaC. abedD. deba.标准答案：A42 .所占用的存储空间大小仅与图的顶点个数相关的存储结构是()o (2分)A.邻接表B.逆邻接表C.十字链表D.邻接矩阵.标准答案：D43 .可以采用()这种数据结构，实现图的深度优先遍历运算。(2分)A.队列B.树C.栈D.集合.标准答案：C44.线性表采用带头结点单链表实现，head为头指针，则判断表空的条件为()o (2 分)A. head= NULLC. head->next=NULL.标准答案：CB.head!:NULLD.head->next !=NULL45.在关键字序列（35, 10, 15, 20, 25）中采用最低位优先排序（LSD）基数排序，第一趟之后所得结果为（）o （2分）A. 10, 20, 15, 25, 35C. 20, 10, 35, 25, 15 .标准答案：BB.10, 20, 35, 15, 25D.20, 10, 35, 15, 2546.下列逻辑结构中，（）为线性结构。（2分）A.栈B.队列.标准答案：A.B.CC.串D.二叉树47.深度为3的二叉树可能的结点个数是（）。（2分）A. 1B. 2.标准答案：A.BC. 3D.448.下列各项键值（）序列是大顶堆的。（2分）49.下列（）是限制了插入和删除操作的特殊线性表。（2分）A. 23, 68, 94, 16, 5C. 94, 23, 68, 16, 5 .标准答案：B.CB. 94, 68, 23, 16, 5D. 94, 16, 68, 23, 5A.栈B.队列.标准答案：A.BC.串D.数组50.对一棵二叉排序树，用（） 列。（2分）A.先根遍历B.中根遍历.标准答案：A.C.D方法进行遍历，不一定得到各结点键值的有序序C.后根遍历D.层次遍历51.数据的最小单位是（）oA.数据元素B.记录.标准答案：D（2分）C.数据对象D.数据项52.算法是对某一类问题求解步骤的有限序列。其中，（）是算法具有的5个特性.（）是数据的逻辑结构。（2分）之一。（2分）A.有穷性B.正确性.标准答案：AC.可读性D.健壮性A.顺序表 B.链表C.线性表 D.十字链表.标准答案：C.（）是限制了插入和删除操作在一端进行的线性表。（2分）A.栈B.队列C.串D.数组.标准答案：A.（）是限制了插入和删除操作分别在两端进行的线性表。（2分）A.栈B.队列C.串D.数组.标准答案：B53 .用链表表示线性表的优点是（）。（2分）A.便于插入和删除便于随机存取C.花费的存储空间较顺序存储少D.数据元素的物理顺序与逻辑顺序相同.标准答案：A57.若已知一个栈的入栈序列是1、2、3、4,其出栈序列不可能为（）o 分）A. 1、4、3、2B.2、3、4、1C.4、3、2、1D.3、4、1、2.标准答案：D58.串下列关于串的叙述中，正确的是（）。（2分）A.2个串的长度相等，则2个串相等B.空串至少包一个空格C.替换操作可以实现字符的删除D. 一个串的长度至少是1.标准答案：C.深度为h的二叉树，第h层至少有（）个结点。（2分）A. 0B. 1C.8D. 16.标准答案：B.假设n20,在程序段y=0；wh i1e（y+1）*（y+1）A.nB.n2.标准答案：C.下面叙述错误的是（）o （2分）A.在集合1, 2, 3, 4, 5中元素1是2的直接前驱B.二叉排序树的中序遍历序列一定是有序的C.有3个结点的不同形态二叉树的数目为5D.哈夫曼树中所有结点的孩子数目只可能为2或者为0 .标准答案：A61 .以下数据结构中，（）是线性结构。（2分）A.广义表B.二叉树C.稀琉矩阵D.串 .标准答案：D.在一个长度为n的顺序表中删除一个元素的算法的时间复杂度为（）o （2 分）A.O（l）B.O（logn）C.O（n）D.0（n2）.标准答案：C.如果一个huffman树含有n个叶子，则该树必有（）的结点。（2分）A. n+1B. 2n+lC. 2nC. 2n-l .标准答案：D65.在关键字序列（10,15,20,25,30）中，采用折半法查找25,关键字之间比较 需要（）次。（2分）A. 1B.2C. 3D.4.标准答案：B16某二叉树的前序遍历序列和和中序遍历序列均为abed,该二叉树的后序遍 历序列是（）。（2分）A. abedB. debaC. aebdD. dbea .标准答案：BC. mC. mC. m66. m个顶点的有向完全图有（）个瓠。（2分） A. m （m- 1）/2B. m+1D. m（m-l） .标准答案：D68.下列各项键值（）序列不是堆的。（2分）A. 94, 68, 23, 16, 5B. 94, 23, 68, 5,16C. 94, 23, 68, 16, 5D. 94, 16, 68, 23,5 .标准答案：D69.设单链表中指针p指向结点A, q指向新元素结点，若要A之后插入一个新元 素，则所需修改指针的操作为O o （2分）A. p->next=q, q->next=p->nextq->next=p->next, p->next=qp->next=q->next, q->next=pD.p->next=p, q->next=p->next .标准答案：B70.在关键字序列（149,138,165,197,176,113, 127）中采用最低位优先排序（LSD）基数排序， A.149, 138, 165, B. 128, 149, 165, C.128, 149, 165, D.113, 127, 138, .标准答案：B第一趟之后所得结果为197, 176, 113, 127197, 113, 176, 127197, 113, 127, 176149, 165, 176, 197O O（2分）.下列术语表示的数据中，（）是同义语。（2分）A.结点B.数据元素C.顶点D.数据项.标准答案：A.B.C.对于采用链式结构的队列，（）运算的实现算法的时间复杂度为0（1）。（2分）A.入队B.出队C.求队长D.队清空.标准答案：A,B.在n个数据元素中进行查找，（）方法的最坏时间复杂度为0（n）。（2分）A.顺序查找B.折半查找C.二叉排序树查找D.斐波那契查找.标准答案：A.C71 .下列是二叉树4种常见的遍历方法。其中，()属于深度优先遍历。(2 分)A.前序遍历B.中序遍历C.后序遍历D.层序遍历 .标准答案：A,B,C.下列()哈希函数构造方法所得的哈希函数，使得查找时间复杂度通常不能到 达 0(1)。(2 分)A.直接定地法B.数字分析法C.平方取中法D.折叠法 .标准答案：B,C,D数据结构概论试卷及答案姓名：专业：计算机科学与技术学号：学习中心：成绩：一、单项选择题（请将答案填写在后面的表格中，每小题2分，共30分）1.查找n个元素的有序表时，最有效的查找方法是（）A.顺序查找B.分块查找C.折半查找D.二叉排序树查找.对于哈希函数H（key）=key%13,被称为同义词的关键字是（）A. 35 和 41B. 23 和 39C. 15 和 441）.25 和 5110 .有一个有序表为 1, 3, 9, 12, 32, 41, 45, 62, 77, 88, 92, 100）,用折半查找法，若要找 63,要经过（）次与63比较。A. 12B. 6C. 4D. 512.下述几种排序方法中，稳定的排序算法是（）A.直接插入排序B.快速排序C.堆排序D.希尔排序B.希尔排序D.快速排序B.删除操作更加方便D.不会出现上涉的情况.具有12个关键字的有序表，查找成功时折半查找的平均查找长度是（）A. 3. 1B. 4C. 2. 5D. 5.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间豆杂度是（）A. 0（1）B. 0（n）C. O（nlogn）D. 0（n2）.对平均性能而言，以下最好的内排序方法是（）«A.冒泡排序C.交换排序.链栈与顺序栈相比，比较明显的优点是（A.插入操作更加方便c.不会出现卜.湖的情况.具有n个顶点的无向图至少要有（）条边才能确保是一个连通图。A. n（n+l）B. n-1C. n+1D. n （n-1）.二叉树是非线性数据结构，所以（）A.它不能用顺序存储结构存储B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储D.顺序存储结构和链式存储结构都不能使用.有8个结点的无向图最多有（）条边。A. 14B. 28C. 56D. 1126 .二叉树中第5层上的结点个数最多为（）A. 8B. 15C. 16D. 32.以下数据结构中，（）是非线性数据结构。A.树B.字符串C.队D.栈.一个向量的第一个元素的地址是100,每个元素的尺度是2 ,则第五个元素的地址是（）.A. 102B. 110C. 108D. 120单项选择题答题表格（请将答案填写在下表中）二、填空题（每小题2分，共30分）题号12345678910答案CABI)I)CACAD题号1112131415答案CABCC.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）A. 0 3 2 1B. 0 1 2 3C. 0 1 3 2D. 0 3 1 2（第9题配图：数组的下标为0,1,2, 3）.下面程序段的时间复杂度为_0（n）.sum=l: for（i=0:sum<n:i+） sum+=l;.设数组为最大空间个数）作为循环队列Q的存储空间，front为队头指针（指向第一个存放数 据的位置），rear为队尾指针（指向最后一个存放数据位置的下一个），则判定Q队列的队满条件是 _fron t= （rear+1） %M。1 .春已加一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是_FEGHDCB。2 .散列法存储的基本思想是由 关键码的值 决定数据的存储地址。3 .在一棵度为3的树中，度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是 2。4 .设一棵完全二叉树有700个结点，则共有350_个叶子结点。5 . n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为0 （n*n）:若采用邻接表存储时，该算法的时间复杂度为_0 （n+c）。8 .在堆排序和快速排序中，若初始记录接近正序或反序，则选用一堆排序；若初始记录 基本无序，则最好选用快速排序。9 .若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔算法来求解.10 . 一棵深度为6的满二叉树有 _31 个分支结点和32个叶子。11 .用5个权值2, 4, 5, 1构造的哈夫受（Huffman）树的带权路径长度是33。12 .有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的出度o三、解答题（每小题9分，共27分）.已知以下的有向图，用Dijkstra算法求出从顶点1出发到各顶点的最短路径（按步给分）。1到各结点的长度62 47 36 25 15 21 3262 47 36 25 15 21 3262 47 36 25 15 21 3262 47 36 25 15 21 3247 32 36 25 15 21 6236 32 21 25 12 47 6232 25 21 15 36 47 62 25 15 21 32 36 47 6221 15 25 32 36 47 6215 21 25 32 36 47 6278 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 9078 84 903. 一棵度为2的有序树与一棵二叉树有何区别？1、度不同度为2的树要求每个节点最多只能有两棵子树，并且至少有一个节点有两棵子树。二 叉树的要求是度不超过2,节点最多有两个叉，可以是1或者0。在任意一棵二叉树中，叶子结点总是比度为2的结点多一个。2、分支不同度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能随意颠倒。3、次序不同度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。 即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使 是一个孩子也有左右之分。第一轮100088添加路径1->2第二轮10CO oO13添加路径第三轮10 815 13添加路径1->2->4第四轮10 1715 13添加路径1->2-.4->323452.待排序的序列为：25, 47, 36, 21,90, 84, 62, 78, 15, 32。写出用（大根）堆排序的每一趟的结果。构建最大堆2525252590排序调整84 78 6278 47 624747219081627815327890846221153278903662211532784736622115322547:、;66221153225473632211590251436322184904790783636848484四、程序设计题（共13分）1、已知r口为一维数组，其中r0到为待排序的n个元素，排序好的元素仍放在r0到rn 1中，请写出对该数组进行非递归的直接插入排序算法,取名为insertsort （elemtype r, intn） o#include < iostream>include <utility>using namespace std;template <typename elemtype> void insertsort(elemtype* r, int n); template <typename elemtype> void insertElement(elemtype* r, int n, int k, elemtype& e);int main() int a4 = 4,321;insertsort(a, 4); for (auto e : a) cout << e ; ) cout << endl;float b6 = 1.0,3.0,5.0,4.0,20,0.0 ;insertsort(b, 6);for(auto e:b) cout << e )template < typename elemtype> void insertsort(elemtype* r, int n) if (n <= 1) return;for (int j = lj < n;j+) int k = j - 1;for Ck >= 0;k-) if (rk < rj) elemtype tmp = r(j; insertElement(r, j, k+1, tmp); break;) ) if (k = -1) elemtype tmp = rj; insertElement(r, j, k+1, tmp);template <typename elemtype>void insertElement(elemtype* r, int n, int k, elemtype& e) if (n = k) rk = e;return ;)memmove(r+k + 1, r+k, (n - k) * sizeof(elemtype);rk = e;)