西安交通大学18年12月补考《数据结构》作业考核试题（100分）

hezuo001

【奥鹏】[西安交通大学]西安交通大学18年12月补考《数据结构》作业考核试题
试卷总分:100    得分:100
第1题,一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。
A、不确定
B、n-i+1
C、i
D、n-i



第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) MOD n=front
B、rear=front
C、rear+1=front
D、(rear-l) MOD n=front



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



第14题,设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
A、n-i
B、n-1-i
C、n+l-i
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、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；



第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、2m-1
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、正确