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

西安交通大学19年3月课程考试《数据结构》作业考核试题（100分)
【奥鹏】[西安交通大学]西安交通大学19年3月课程考试《数据结构》作业考核试题
奥鹏作业答案
奥鹏西安交通大学作业

试卷总分100得分100
第1题一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（）。
A、不确定
B、ni+1
C、i
D、ni
正确答案
第2题设用链表作为栈的存储结构则退栈操作（）
A、必须判别栈是否为满
B、必须判别栈是否为空
C、判别栈元素的类型
D、对栈不作任何判别
正确答案
第3题如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用（）存储结构。
A、散列
B、顺序
C、链式
D、任意
正确答案
第4题下列程序段的时间复杂度为（）。i=0，s=0；while(sn){s=s+i；i++；}
A、O(n)
B、O(n)
C、O(n)
D、O(n)
正确答案
第5题两个字符串相等的条件是（）。
A、两串的长度相等；
B、两串包含的字符相同；
C、两串的长度相等，并且两串包含的字符相同；
D、两串的长度相等，并且对应位置上的字符相同。
正确答案
第6题在二叉排序树中插入一个关键字值的平均时间复杂度为（）。
A、O(n)
B、O(1og2n)
C、O(nlog2n)
D、O(n)
正确答案
第7题在含n个顶点和e条边的无向图的邻接矩阵中零元素的个数为（）
A、e
B、2e    易百教育

C、n2－e
D、n2－2e
正确答案
第8题由两个栈共享一个向量空间的好处是：（）
A、减少存取时间，降低下溢发生的机率
B、节省存储空间，降低上溢发生的机率
C、减少存取时间，降低上溢发生的机率
D、节省存储空间，降低下溢发生的机率
正确答案
第9题哈希表的平均查找长度是()的函数。
A、哈希表的长度
B、表中元素的多少
C、哈希函数
D、哈希表的装满程度
正确答案
第10题深度优先遍历类似于二叉树的（）。
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
正确答案
第11题以下数据结构中哪一个是非线性结构？（）
A、队列
B、栈
C、线性表
D、二叉树
正确答案
第12题最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。
A、(rear+1)MODn=front
B、rear=front
C、rear+1=front
D、(rearl)MODn=front
正确答案
第13题设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
A、head==0
B、headnext==0
C、headnext==head
D、head!=0
正确答案
第14题设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
A、ni
B、n1i
C、n+li
D、不能确定
正确答案
第15题程序段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)
正确答案
第16题设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）
A、BADC
B、BCDA
C、CDAB
D、CBDA
正确答案
第17题有n个顶点的无向图的邻接矩阵是用（）数组存储。
A、一维
B、n行n列
C、任意行n列
D、n行任意列
正确答案
第18题设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）
A、pright=s；sleft=p；prightleft=s；sright=pright；
B、sleft=p；sright=pright；pright=s；prightleft=s；
C、pright=s；prightleft=s；sleft=p；sright=pright；
D、sleft=p；sright=pright；prightleft=s；pright=s；
正确答案
第19题设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
A、2，3，5，8，6
B、3，2，5，8，6
C、3，2，5，6，8
D、2，3，6，5，8
正确答案
第20题（）二叉排序树可以得到一个从小到大的有序序列。
A、先序遍历
B、中序遍历
C、后序遍历
D、层次遍历
正确答案
第21题
A、A
B、B
C、C
D、D
正确答案
第22题设某数据结构的二元组形式表示为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、图型结构
正确答案
第23题对于一些特殊矩阵，采用压缩存储的目的是（）。
A、使表达变得更简单
B、对矩阵元素的存取变得简单
C、去掉矩阵中的多于元素
D、减少不必要的存储空间
正确答案
第24题求字符串T在字符串S中首次出现的位置的操作称为（）。
A、串的模式匹配
B、求子串
C、求串的长度
D、串的连接
正确答案
第25题设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。
A、aedfcb
B、acfebd
C、aebcfd
D、aedfbc
正确答案
第26题设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
A、2m1
B、2m
C、2m+1
D、4m
正确答案
第27题在二叉排序树中插入一个结点的时间复杂度为（）。
A、O(1)
B、O(n)
C、O(log2n)
D、O(n)
正确答案
第28题任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（）。
A、不发生改变
B、发生改变
C、不能确定
D、以上都不对
正确答案
第29题设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。
A、1
B、2
C、3
D、4
正确答案
第30题对一棵二叉排序树进行（）遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。
A、前序
B、中序
C、后序
D、按层次
正确答案
第31题对连通图进行深度优先遍历可以访问到该图中的所有顶点。
A、错误
B、正确
正确答案
第32题二维数组是数组元素为一维数组的线性表，因此它是线性结构。
A、错误
B、正确
正确答案
第33题图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。
A、错误
B、正确
正确答案
第34题有向图的邻接表和逆邻接表中表结点的个数不一定相等。
A、错误
B、正确
正确答案
第35题
A、错误
B、正确
正确答案
第36题线性表的顺序存储结构没有比链式存储结构更好。
A、错误
B、正确
正确答案
第37题由树转化成二叉树，该二叉树的右子树不一定为空。（）
A、错误
B、正确
正确答案
第38题
A、错误
B、正确
正确答案
第39题堆是完全二叉树，完全二叉树不一定是堆。
A、错误
B、正确
正确答案
第40题调用一次深度优先遍历可以访问到图中的所有顶点。
A、错误
B、正确
正确答案
第41题不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
A、错误
B、正确
正确答案
第42题顺序查找法适用于存储结构为顺序或链接存储的线性表。()
A、错误
B、正确
正确答案
第43题算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。
A、错误
B、正确
正确答案
第44题通常使用两个类来协同表示单链表，即链表的结点类和链表类。
A、错误
B、正确
正确答案
第45题堆排序所需的时间与待排序的记录个数无关。（）
A、错误
B、正确
正确答案
第46题当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）
A、错误
B、正确
正确答案
第47题完全二叉树中的叶子结点只可能在最后两层中出现。（）
A、错误
B、正确
正确答案
第48题哈夫曼树中有度数为1的结点。
A、错误
B、正确
正确答案
第49题希尔排序算法的时间复杂度为O(n2)。
A、错误
B、正确
正确答案
第50题先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
A、错误
B、正确
正确答案


奥鹏作业答案