西安交通大学19年3月课程考试《数据结构》作业考核试题辅导答案

1、西安交通大学19年3月课程考试数据结构作业考核试题一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i正确答案:B设用链表作为栈的存储结构则退栈操作（）A.必须判别栈是否为满B.必须判别栈是否为空C.判别栈元素的类型D.对栈不作任何判别正确答案:B如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用（）存储结构。A.散列B.顺序C.链式D.任意正确答案:C下列程序段的时间复杂度为（）。i=0，s=0；while(sn)s=s+i；i+；A.O(n)B.O(n)C.O(n)D.O(n)正确答案:A两个字符串相等的条件是（）。A.两串的长度相等；B.两串包含的字符相同；C.两串的长度相等，并且两串包含的字符相同；D.两串的长度相等，并且对应位置上的字符相同。正确答案:D在二叉排序树中插入一个关键字值的平均时间复杂度为（）。A.O(n)B.O(1og2n)C.O(nlog2n)D.O(n)正确答案:B在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（）A.eB.2eC.n2eD.n22e正确答案:D

2、由两个栈共享一个向量空间的好处是：（）A.减少存取时间，降低下溢发生的机率B.节省存储空间，降低上溢发生的机率C.减少存取时间，降低上溢发生的机率D.节省存储空间，降低下溢发生的机率正确答案:B哈希表的平均查找长度是()的函数。A.哈希表的长度B.表中元素的多少C.哈希函数D.哈希表的装满程度正确答案:D深度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历正确答案:A以下数据结构中哪一个是非线性结构？（）A.队列B.栈C.线性表D.二叉树正确答案:D最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)MODn=frontB.rear=frontC.rear+1=frontD.(rear-l)MODn=front正确答案:B设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。A.head=0B.head-next=0C.head-next=headD.head!=0正确答案:C设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。A.n-iB

3、.n-1-iC.n+l-iD.不能确定正确答案:C程序段s=i=0；doi=i+1；s=s+i；while(i=n)；的时间复杂度为（）。A.O(n)B.O(nlog2n)C.O(n)D.O(n/2)正确答案:A设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）A.BADCB.BCDAC.CDABD.CBDA正确答案:A有n个顶点的无向图的邻接矩阵是用（）数组存储。A.一维B.n行n列C.任意行n列D.n行任意列正确答案:B设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）A.p-right=s；s-left=p；p-right-left=s；s-right=p-right；B.s-left=p；s-right=p-right；p-right=s；p-right-left=s；C.p-right=s；p-right-left=s；s-left=p；s-right=p-right；D.s-left=p；s-right=p-right；p-right-left=s；p-right=s；正确答

4、案:D设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8正确答案:C（）二叉排序树可以得到一个从小到大的有序序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历正确答案:BA.AB.BC.CD.D正确答案:B设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09，则数据结构A是（）。A.线性结构B.树型结构C.物理结构D.图型结构正确答案:B对于一些特殊矩阵，采用压缩存储的目的是（）。A.使表达变得更简单B.对矩阵元素的存取变得简单C.去掉矩阵中的多于元素D.减少不必要的存储空间正确答案:D求字符串T在字符串S中首次出现的位置的操作称为（）。A.串的模式匹配B.求子串C.求串的长度D.串的连接正确答案:A设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(

5、d，f)，(f，c)，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。A.aedfcbB.acfebdC.aebcfdD.aedfbc正确答案:A设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A.2m-1B.2mC.2m+1D.4m正确答案:B在二叉排序树中插入一个结点的时间复杂度为（）。A.O(1)B.O(n)C.O(log2n)D.O(n)正确答案:B任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对正确答案:A设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。A.1B.2C.3D.4正确答案:C对一棵二叉排序树进行（）遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。A.前序B.中序C.后序D.按层次正确答案:B对连通图进行深度优先遍历可以访问到该图中的所有顶点。A.错误B.正确正确答案:B二维数组是数组元素为一维数组的线性表，因此它是线性结构。A.错误B.正确正确答案:A图的深

6、度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。A.错误B.正确正确答案:B有向图的邻接表和逆邻接表中表结点的个数不一定相等。A.错误B.正确正确答案:AA.错误B.正确正确答案:B线性表的顺序存储结构没有比链式存储结构更好。A.错误B.正确正确答案:B由树转化成二叉树，该二叉树的右子树不一定为空。（）A.错误B.正确正确答案:AA.错误B.正确正确答案:A堆是完全二叉树，完全二叉树不一定是堆。A.错误B.正确正确答案:B调用一次深度优先遍历可以访问到图中的所有顶点。A.错误B.正确正确答案:A不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。A.错误B.正确正确答案:B顺序查找法适用于存储结构为顺序或链接存储的线性表。()A.错误B.正确正确答案:B算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。A.错误B.正确正确答案:B通常使用两个类来协同表示单链表，即链表的结点类和链表类。A.错误B.正确正确答案:B堆排序所需的时间与待排序的记录个数无关。（）A.错误B.正确正确答案:A当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）A.错误B.正确正确答案:B完全二叉树中的叶子结点只可能在最后两层中出现。（）A.错误B.正确正确答案:B哈夫曼树中有度数为1的结点。A.错误B.正确正确答案:A希尔排序算法的时间复杂度为O(n2)。A.错误B.正确正确答案:A先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。A.错误B.正确正确答案:B

《西安交通大学19年3月课程考试《数据结构》作业考核试题辅导答案》由会员奋斗分享，可在线阅读，更多相关《西安交通大学19年3月课程考试《数据结构》作业考核试题辅导答案》请在金锄头文库上搜索。