02142数据结构导论复习题

#数据结构导论模拟试题一、考试题型及分值分布：1、单项选择题（本大题共15小题，每小题2分，共30分）2、填空题（本大题共13小题，每小题2分，共26分）3、应用题（本大题共5小题，每小题6分，共30分）4、算法设计题（本大题共2小题，每小题7分，共14分）二、单项选择题和填空题样题参考（一）单项选择题.在二维数组中，每个数组元素同时处于（）个向量中。A.0 B.1 C.2 D.n已知单链表长度为，单链表长度为，它们分别由表头指针所指向，若将整体连接到的末尾，其时间复杂度应为（）。A.O（1） B.O（m） C.O（n）假定一个链式队列的队头和队尾指针分别为 和，则判断队空的条件为若让元素1,2依,次3进栈，则出栈次序不可能出现（种情）况。A.3,2,1 B.2,1,3图的广度优先搜索类似于树的（）遍历。先根 中根 后根 层次下面程序段的时间复杂度为（。）设有两个串和，求在中首次出现的位置的运算叫做（）。求子串 模式匹配 串替换 串连接8利用双向链表作线性表的存储结构的优点是（）。便于单向进行插入和删除的操作 便于双向进行插入和删除的操作节省空间 便于销毁结构释放空间设链式栈中结点的结构为（ ）,且 是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针所指的结点，则应执行 操作。.一棵具有35个结点的完全二叉树的高度为（。假）定空树的高度为-1。TOC\o"1-5"\h\zA.5 B.6 C.7一个有个顶点和条边的无向图一定是 的。A连通 .不连通.无回路 .有回路在一个长度为的顺序表的任一位置插入一个新元素的时间复杂度为（）。A.O（n） B.O（n/2） 2） C.O（E知广义表为 ，从中取出原子的运算是（）。.在一棵树的静态双亲表示中，每个存储结点包含（个）域。15有.向图中的一个顶点的度数等于该顶点的（。）A入度 .出度入度与出度之和 .入度出度2.与邻接矩阵相比，邻接表更适合于存储（。）A无向图.连通图 .稀疏图 .稠密图.较快的数据搜索方法是（）搜索方法。顺序 折半 单链散列.在闭散列表中，散列到同一个地址而引起的“堆积”问题是由于（）引起的。

同义词之间发生冲突 非同义词之间发生冲突同义词之间或非同义词之间发生冲突 散列表“溢出”根据个元素建立一个有序单链表的时间复杂度为（）。A.O（1） B.2O）（n） 2Dn.）CO.（nOl（ong假定一个顺序存储的循环队列的队头和队尾指针分别为 和，则判断队空的条件为（。）假定一棵二叉树的第层上有个结点，则第 层上最多有个结点。A.3i B.6i C.9i D对于具有条边的无向图，它的邻接表中共有 个边结点。A．e-1 ．e+1B．2eC．3eD23对图的深度优先搜索遍历类似于树的（）次序遍历。先根 中根 后根 层次.栈最多能容纳个元素。现有个元素按 的顺序进栈问下列哪一个序列是可能的出栈序列?（ 边25．将一棵有10个0结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：（边26对对下列关键字序列用快速排序法进行排序时，速度最快的情形是：（边27．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为顺序表 用头指针表示的单循环链表用尾指针表示的单循环链表 单链表.假设以第一个元素为分界元素，对字符序列（）进行快速排序，则第一次划分的结果是：（边面是三个关于有向图运算的叙述：(1)求有向图结点的拓扑序列，其结果必定是唯一的(2)求两个指向结点间的最短路径，其结果必定是唯一的()求 网的关键路径，其结果必定是唯一的其中哪个(些)是正确的？只有() ()和() 都正确 都不正确.若进栈序列为 ，则通过入出栈操作可能得到的 的不同排列个数为31.以下关于广义表的叙述中,正确的是：( )广义表是由个或多个单元素或子表构成的有限序列广义表至少有一个元素是子表广义表不能递归定义广义表不能为空表若2.排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？( )堆排序直接插入排序 快速排序 冒泡排序.已知一个有向图的邻接矩阵表示，要删除所有从第个结点发出的边，应该：将邻接矩阵的第行删除 将邻接矩阵的第行元素全部置为将邻接矩阵的第列删除 将邻接矩阵的第列元素全部置为4有一个含头结点的双向循环链表，头指针为 则其为空的条件是：TOC\o"1-5"\h\z若5在.顺序表(若,6,8,10,12,15中,，用1折6半,法查1找8关,键码值11，所需的关键码比较次数为：( )A.2 B.若 C.4若6.以下哪一个不是队列的基本运算？( )从队尾插入一个新元素 从队列中删除第个元素判断一个队列是否为空 读取队头元素的值7对包含个元素的哈希表进行查找，平均查找长度为：不直接依赖于TOC\o"1-5"\h\z若8.将一棵有10个0结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：( )A.48 B.49C.50 D.51.某二叉树结点的中序序列为 后序序列为 E则其左子树中结点数目为：A.若 B.2 C.40下面是顺序存储结构的优点。存储密度大 插入运算方便查找方便 适合各种逻辑结构的存储表示.下面关于串的叙述中，是不正确的。串是字符的有限序列 空串是由空格构成的串模式匹配是串的一种重要运算 串既可以采用顺序存储，也可以采用链式存储.的邻接矩阵是对称矩阵。有向图 无向图 网 网.用链式方式存储的队列，在进行删除运算时，。仅修改头指针 仅修改尾指针头、尾指针都要修改 头、尾指针可能都要修改.二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是。先序序列： 中序序列：A.E B.F C.G D・下面方法可以判断出一个有向图中是否有环。深度优先遍历 拓朴排序 求最短路径 求关键路径4・6从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为排序法。插入 选择 冒泡都不是7一个栈的入栈序列是 ，则栈的不可能的输出序列是。A.edcba B.decba C.dceab8个节点的完全二叉树，编号为的节点是叶子结点的条件是。A.i<nB.2*i<=n C.2*i+1>n49・向一个有12个8元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素。O在一个单链表中，若要在指针所指结点的后面插入一个由指针所指向的结点，则执行。1对一个满二叉树，个树叶，个结点，深度为，则有。A.n=h+mB.h+m=2n C.m=h-1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。选择排序 冒泡排序插入排序 希尔排序.用链式方式存储的队列，在进行插入运算时，。仅修改头指针 仅修改尾指针头、尾指针都要修改 头、尾指针可能都要修改4在一个长度为的顺序存储的线性表中，向第个元素（WW）插入一个新元素时，需要从后向前依次后移个元素。A.n-i 冒.n-i-1 C.n-i+1.一个栈的入栈序列是 3则栈的不可能的输出序列是。A.23415 冒.54132 C.231456个顶点的有向图最多有条弧。A.5 冒.20 C.4.假定一个链队的队首和队尾指针分别为 和a则判断队空的条件为。.若某线性表中最常用的操作是提取第个元素及找第个元素的前驱元素，则采用（ ）存储方式最省时间。单链表 双链表 单向循环链表 顺序表5・9将含有10个0结点的完全二叉树从根开始自上向下，每层从左到右依次编号，且设根结点的编号为1，则编号69的结点的双亲的编号为（ ）。无法确定序单循环链表的主要优点是（ ）。不再需要头指针了已知某结点的位置后，很容易找到其前驱在进行插入、删除运算时，能更好地保证链表不断开从表中任一结点出发都能扫描到整个链表.一个栈的入栈顺序是1、2、3、4、5，则此栈不可能的输出顺序为（ ）。62.串是一种特殊的线性表，其特殊性表现在（ ）。可以顺序存储 数据元素是一个字符可以链式存储 数据元素是多个字符个顶点的无向图中最多有（）条边。A.n（n-1）/2 B.n（n-1） C.n（n64.个顶6点的无向图中，至少有（）条边才能保证是一个连通图。A.5 B.6 C.76．5若某线性表中最常用的操作是删除第1个元素，则不宜采用（ ）存储方式。单链表 双链表 单向循环链表顺序表.在一棵完全二叉树的顺序存储方式中，若编号的结点有右孩子，则其右孩子的编号为（）。67序按照二叉树的定义，具有3个结点的二叉树有（ ）种不同形态。在长为的顺序表中，删除第个元素1W 需要向前移动（ ）个元素。TOC\o"1-5"\h\z69序一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（ ）。70序栈是一种特殊的线性表，其特殊性表现在（ ）。可以顺序存储 只能从端点进行插入和删除可以链式存储 可以在任何位置进行插入和删除一棵二叉树中，第层上最多有（ ）个结点。72序一棵有18个结点的二叉树，其高度最小为（ ）层。73有序向图中，所有顶点入度和是所有顶点出度和的（ ）倍。（二）填空题数据元素之间存在的相互关系称为。数据结构从逻辑上分为结构和 结构。线性表的顺序存储结构称为。所有插入在表的一端进行，而所有删除在表的另一端进行的线性表称为深度为的二叉树最少有 个结点。折半查找要求待查表为表。个记录按其关键字大小递增或递减的次序排列起来的过程称为。存储数据时不仅要存储数据元素的还要存储元素之间的相互。9将一棵有 个结点的完全二叉树按层编号，则编号为的结点X其双亲EN的编号为。0一个字符串相等的充要条件是和。1在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有和结点。1在一个长度为的顺序表中向第 个元素（w）之前插入一个新元素时，需要向后移动个元素。2是只允许在表的一端进行插入，而在另一端进行删除的线性表。、设主串=" "模式串="x则第次匹配成功。4在一棵二叉树中，第层上的结点数最多为。（根的层次为）5假设一个阶的上三角矩阵按列优先顺序压缩存储在一维数组中，其中［］存储矩阵中第个元素，则 中存放的元素是。6有个结点的二叉链表中，其中空的指针域为,指向孩子的指针个数为。、二叉树后序遍历的顺序是 C则该二叉树的根结点是。8对于一个具有个顶点和条边的无向图，若采用邻接表表示，则整个邻接表中的结点总数是。、在单链表上难以实现的排序方法有和。0查找法的平均查找长度与元素个数无关。1在有个元素的顺序表的任意位置插入一个元素所需移动结点的平均次数为、是插入和删除元素都在表的同一端进行的线性表。、广义表=（ ）则其长度为。4在树中，除跟结点外，其他结点都有且只有一个结点。、在串“ ”中，以为首字符的子串有个。7广度优先搜索遍历类似于树的按遍历的过程。8E知一棵完全二叉树中共有 个结点为，则该树中共有个叶子结点。、在有序表（ ）中二分查找关键字时所需进行的关键字比较次数为。、两个长度分别和（）的排好序的表归并成一个排好序的表，至少要进行次键值比较。通常从四个方面评价算法的质量： 、、和 _1 一个算法的时间复杂度为 2其数量级表示为 。、、2 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，个结点的二叉树共有 个指针域，其中有个指针域是存放了地址，有、、、、、、、、个、指、针、是、空、指、针、。、、 对于一个具有个顶点和条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有、、、、个、和、、、、、、个、。、、、4 在一个具有个顶点的无向完全图中，包含有 条边，在一个具有个顶点的有向完全图中，包含有、、、、条、边、。、、、6在.快速排序、堆排序、归并排序中，、、、、、排、序、是、稳、定的。37.中序遍历二叉排序树所得到的序列是 序列。、8快.速排序的最坏时间复杂度为、、、、、、，、平、均、时、间、复杂度为、、、、、。、、、、、、、设.一组初始记录关键字序列为（5，56，、4，4、8，75，8，0、，156，）则利用筛选法建立的初始堆为、、、、、、、、、、、、、、。、、、、、、、、、、、、、40．数据的物理结构主要包括、、、、和、、、、、两、种、情、况、。41设.一棵完全二叉树中有50个0结点，则该二叉树的深度为 ；_若_用_二_叉_链表作为该完全二叉树的存储结构，则共有 个_空_指_针_域_。42、设输入序列为1、2、3，则经过栈的作用后可以得到 种_不_同_的_输_出序列。3设有向图用邻接矩阵 作为存储结构，则该邻接矩阵中第行上所有元素之和等于顶点的，第列上所有元素之和等于顶点的。设哈夫曼树中共有个结点，则该哈夫曼树中有 个_度_数_为_1的结点。设有向图中有个顶点条有向边，所有的顶点入度数之和为，则和的关系为 。 遍_历_二_叉_排_序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。设查找表中有 个元素，如果用二分法查找方法查找数据元素，则最多需要比较次就可以断定数据元素是否在查找表中。不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为次次次次次次。次次次次次次设有个结点的完全二叉树，如果按照从自上到下、从左到右从开始顺序编号，则第个结点的双亲结点编号为 ，右孩子结点的编号为 。设一组初始记录关键字为（7，27，371，2，394，16，5，）则以记录关键字72为基准的一趟快速排序结果为次次次次次次次次次。次次次次次次次次次设有向图中有向边的集合，，，，，，，，， ,则该图的一种拓扑序列为次次次次次次次次次次。次次次次次次次次次次下列算法实现在顺序散列表中查找值为的关键字，请在下划线处填上正确的语句。，下列算法实现在二叉排序树上查找关键值，请在下划线处填上正确的语句。，设有个无序的记录关键字，则直接插入排序的时间复杂度为 ，快速排序的平均时间复杂度为次次次次次。次次次次设指针变量指向双向循环链表中的结点X则删除结点需要执行的语句序列为次次次次次次次次次次次次次次次次次次次次次次次次次次次次次（次设次结次点次中次的次两次个次指次针次域次分别为和 ）。根据初始关键字序列12 ,, 建立的二叉排序树的高度为 3_。 深度为的完全二叉树中最少有 个结点。设初始记录关键字序列为K，-，）则用筛选法思想建堆必须从第 个元12 n素开始进行筛选。59、设哈夫曼树中共有99个结点，则该树中有 个_叶_子_结_点；若采用二叉链表作为存储结构，则该树中有___个_空_指针域。、设有一个顺序循环队列中有个存储单元，则该循环队列中最多能够存储 个队列元素；当前实际存