西安交通大学--数据结构_江开系统成人高考函授考试答案

西安交通大学--数据结

3,栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。,A.正确 B.错误,

3,在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。,A.正确 B.错误,

3,具有n个结点的完全二叉树的高度为┖log2n┘+1。,A.正确 B.错误,

3,为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。,A.正确 B.错误,

3,闭散列法通常比开散列法时间效率更高。,A.正确 B.错误,

3,一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。,A.正确 B.错误,

3,有向图的邻接表和逆邻接表中表结点的个数不一定相等。( ),A.正确 B.错误,

3,对链表进行插入和删除操作时不必移动链表中结点。( ),A.正确 B.错误,

3,希尔排序算法的时间复杂度为O(n2)。( ),A.正确 B.错误,

3,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( ),A.正确 B.错误,

3,通常使用两个类来协同表示单链表，即链表的结点类和链表类。,A.正确 B.错误,

3,顺序表用一维数组作为存储结构，因此顺序表是一维数组。,A.正确 B.错误,

3,二维数组是数组元素为一维数组的线性表，因此它是线性结构。,A.正确 B.错误,

3,算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。,A.正确 B.错误,

3,堆是完全二叉树，完全二叉树不一定是堆。（）,A.正确 B.错误,

3,顺序表查找指的是在顺序存储结构上进行查找。（）,A.正确 B.错误,

3,入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( ),A.正确 B.错误,

3,中序遍历一棵二叉排序树可以得到一个有序的序列。( ),A.正确 B.错误,

3,用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( ),A.正确 B.错误,

3,希尔排序算法的时间复杂度为O(n)。( ),A.正确 B.错误,

3,若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( ),A.正确 B.错误,

3,子串“ABC”在主串“AABCABCD”中的位置为2。( ),A.正确 B.错误,

3,对链表进行插入和删除操作时不必移动链表中结点。( ),A.正确 B.错误,

3,有向图的邻接表和逆邻接表中表结点的个数不一定相等。( ),A.正确 B.错误,

3,稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（）,A.正确 B.错误,

3,图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）,A.正确 B.错误,

3,不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）,A.正确 B.错误,

3,非空的双向循环链表中任何结点的前驱指针均不为空。（）,A.正确 B.错误,

3,如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）,A.正确 B.错误,

3,向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）,A.正确 B.错误,

3,二维数组和多维数组均不是特殊的线性结构。（）,A.正确 B.错误,

3,分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）,A.正确 B.错误,

3,设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）,A.正确 B.错误,

3,如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）,A.正确 B.错误,

3,带权无向图的最小生成树是唯一的。（）,A.正确 B.错误,

3,线性表中的所有元素都有一个前驱元素和后继元素。（）,A.正确 B.错误,

3,由树转化成二叉树，该二叉树的右子树不一定为空。（）,A.正确 B.错误,

3,先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）,A.正确 B.错误,

3,对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）,A.正确 B.错误,

3,哈夫曼树中没有度数为1的结点。（）,A.正确 B.错误,

3,完全二叉树中的叶子结点只可能在最后两层中出现。（）,A.正确 B.错误,

3,设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（）,A.正确 B.错误,

3,当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）,A.正确 B.错误,

3,不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）,A.正确 B.错误,

3,快速排序是排序算法中平均性能最好的一种排序。（）,A.正确 B.错误

3,中序遍历二叉排序树可以得到一个有序的序列。（）,A.正确 B.错误,

3,线性表的顺序存储结构比链式存储结构更好。（）,A.正确 B.错误,

3,设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）,A.正确 B.错误,

3,层次遍历初始堆可以得到一个有序的序列。（）,A.正确 B.错误,

3,设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）,A.正确 B.错误,

3,满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）,A.正确 B.错误,

3,冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）,A.正确 B.错误,

3,分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）,A.正确 B.错误,

3,调用一次深度优先遍历可以访问到图中的所有顶点。（）,A.正确 B.错误,

1,设有100个数据元素，采用折半搜索时，最大比较次数为（）,A.6 B.7 C.8 D.10,

1,在一棵具有5层的满二叉树中结点数为（）,A.31 B.32 C.33 D.16,

1,下列存储形式中，（）不是树的存储形式,A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D. 顺序表示法,

1,对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。,A.8 B.10 C.15 D.25,

1,用链表表示线性表的优点是（）,A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同,

1,在一个顺序存储的循环队列中，队头指针指向队头元素的（）,A.前一个位置 B.后一个位置 C.队头元素位置 D.队尾元素的前一位置,

1,若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）,A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵,

1,不定长文件是指（）,A.文件的长度不固定 B.记录的长度不固定 C.字段的长度不固定 D.关键字项的长度不固定,

1,适于对动态查找表进行高效率查找的组织结构是（）,A.有序表 B.分块有序表 C.三叉排序树 D.线性链表,

1,"假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )",A.O(n) B.O(e) C.O(n+e) D.O(n*e),

1,"在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )",A.e B.2e C.n2－e D.n2－2e,

1,对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）,A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序,

1,链式栈与顺序栈相比，一个比较明显的优点是（）,A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便,

1,与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）,A.存储结构 B.逻辑结构 C.算法 D.操作,

1,设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。,A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子,

1,设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。,A.第i行非0元素的个数之和 B.第i列非0元素的个数之和 C.第i行0元素的个数之和 D.第i列0元素的个数之和,

1,设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。,A.O(n) B.O(n) C.O(nlog2n) D.O(1og2n),

1,二路归并排序的时间复杂度为（）。,A.O(n) B.O(n) C.O(nlog2n) D.O(1og2n),

1,顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。,A.O(n) B.O(n) C.O(n) D.O(1og2n),

1,时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。,A.堆排序 B.冒泡排序 C.希尔排序 D.快速排序,

1,设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。,A.head==0 B.head->next==0 C.head->next==head D.head!=0,

1,设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。,A.6 B.7 C.8 D.9,

1,设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。,A.2n B.n+l C.2n-1 D.2n+l,

1,设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。,A.n B.n(n+1) C.n(n+1)/2 D.n(n-1)/2,

1,设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。,A.129 B.219 C.189 D.229,

1,二叉排序树中左子树上所有结点的值均（）根结点的值。,A.< B.> C.= D.!=,

1,设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。,A.10 B.19 C.28 D.55,

1,设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。,A.5，3，4，6，1，2 B.3，2，5，6，4，1 C.3，1，2，5，4，6 D.1，5，4，6，2，3,

1,设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。,A.s->next=p->next；p->next=-s； B.q->next=s； s->

1,设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。,A.单向链表 B.单向循环链表 C.双向链表 D.双向循环链表,

1,下列程序段的时间复杂度为（）。i=0，s=0； while (s

1,设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。,A.4 B.5 C.6 D.7,

1,设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。,A.1，2，3，4 B.2，3，4，1 C.1，4，2，3 D.1，2，4，3,

1,设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。,A.6 B.11 C.5 D.6.5,

1,设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。,A.1 B.2 C.3 D.4,

1,设顺序表的长度为n，则顺序查找的平均比较次数为（）。,A.n B.n/2 C.(n+1)/2 D.(n-1)/2,

1,设完全无向图中有n个顶点，则该完全无向图中有（）条边。,A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D.(n-1)/2,

1,设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。,A.4 B.5 C.6 D.7,

1,设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。,A.小于等于m的最大奇数 B.小于等于m的最大素数 C.小于等于m的最大偶数 D.小于等于m的最大合数,

1,设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。,A.n-i B.n-1-i C.n+l -i D.不能确定,

1,下列各种排序算法中平均时间复杂度为O(n)是（）。,A.快速排序 B.堆排序 C.归并排序 D.冒泡排序,

1,设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。,A.top=top+1; B.top=top-1; C.top->next=top; D.top=top->next;,

1,"设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ?）。",A.1 B.2 C.3 D.4,

1,设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。,A.20 B.256 C.512 D.1024,

1,设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。,A.head==0 B.head->next==0 C.head->next==head D.head!=0,

1,程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。,A.O(n) B.O(nlog2n) C.O(n) D.O(n/2),

1,设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ ?）。,A.2i+1 B.2i C.i/2 D.2i-1,

1,（）二叉排序树可以得到一个从小到大的有序序列。,A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历,

1,设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（ ?）,A.40，42，60，55，80，85 B.42，45，55，60，85，80 C.42，40，55，60，

1,设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。,A.n B.n-1 C.2n D.2n-1,

1,设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。,A.2n B.n C.n/2 D.n(n-1),

1,设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。,A.99 B.100 C.101 D. 102,

1,设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。,A.O(n+e) B.O(n) C.O(ne) D.O(n),

1,设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ?）。,A.front->next=s；front=s； B.s->next=rear；rea

1,设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。,A.3 B.4 C.5 D.6,

1,一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。,A.堆排序 B.冒泡排序 C.快速排序 D.希尔排序,

1,执行一趟快速排序能够得到的序列是（）。,A.[41，12，34，45，27] 55 [72，63] B.[45，34，12，41] 55 [72，63，27] C.[63，12，34，45，27] 55 [41，72] D.[12，

1,设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）,A.20 B.30 C.40 D.45,

1,设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。,A.N0=N1+1 B.N0=Nl+N2 C.N0=N2+1 D.N0=2N1+l,

1,设用链表作为栈的存储结构则退栈操作（）,A.必须判别栈是否为满 B.必须判别栈是否为空 C.判别栈元素的类型 D.对栈不作任何判别,

1,设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。,A.3 B.4 C.5 D.8,

1,在二叉排序树中插入一个结点的时间复杂度为（）。,A.O(1) B.O(n) C.O(log2n) D.O(n),

1,设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。,A.n B.e C.2n D.2e,

1,设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。,A.O(n) B.O(nlog2n) C.O(1) D.O(n),

1,下列四种排序中（）的空间复杂度最大。,A.插入排序 B.冒泡排序 C.堆排序 D.归并排序,

1,设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ?）方法可以达到此目的。,A.快速排序 B.堆排序 C.归并排序 D.插入排序,

目前为： 1/2 页首页上页下页尾页

负责人：王老师 19139051760(拨打)

圆梦题库移动版 ICP证：豫ICP备11005330号-1