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

西安交通大学19年3月课程考试数据结构作业考核试题1、B 2、B 3、C 4、A 5、D 一、单选题共30题，60分1、一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。A不确定Bn-i+1CiDn-i【答案】正确是：B2、设用链表作为栈的存储结构则退栈操作（）A必须判别栈是否为满B必须判别栈是否为空C判别栈元素的类型D对栈不作任何判别【答案】正确是：B3、如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用（ ）存储结构。A散列B顺序C链式D任意【答案】正确是：C4、下列程序段的时间复杂度为（）。i=0，s=0；while(s<n)s=s+i；i+；AO(n)BO(n)CO(n)DO(n)【答案】正确是：A5、两个字符串相等的条件是（ ）。A两串的长度相等；B两串包含的字符相同；C两串的长度相等，并且两串包含的字符相同；D两串的长度相等，并且对应位置上的字符相同。【答案】正确是：D6、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。AO(n)BO(1og2n)CO(nlog2n)DO(n)【答案】正确是：B7、在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为（）AeB2eCn2eDn22e【答案】正确是：D8、由两个栈共享一个向量空间的好处是：（）A减少存取时间，降低下溢发生的机率B节省存储空间，降低上溢发生的机率C减少存取时间，降低上溢发生的机率D节省存储空间，降低下溢发生的机率【答案】正确是：B9、哈希表的平均查找长度是( )的函数。A哈希表的长度B表中元素的多少C哈希函数D哈希表的装满程度【答案】正确是：D10、深度优先遍历类似于二叉树的（ ）。A先序遍历B中序遍历C后序遍历D层次遍历【答案】正确是：A11、以下数据结构中哪一个是非线性结构？（）A队列B栈C线性表D二叉树【答案】正确是：D12、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。A(rear+1) MOD n=frontBrear=frontCrear+1=frontD(rear-l) MOD n=front【答案】正确是：B13、设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。Ahead=0Bhead->next=0Chead->next=headDhead!=0【答案】正确是：C14、设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。An-iBn-1-iCn+l-iD不能确定【答案】正确是：C15、程序段s=i=0；doi=i+1；s=s+i；while(i<=n)；的时间复杂度为（）。AO(n)BO(nlog2n)CO(n)DO(n/2)【答案】正确是：A16、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）ABADCBBCDACCDABDCBDA【答案】正确是：A17、有n个顶点的无向图的邻接矩阵是用（ ）数组存储。A一维Bn行n列C任意行n列Dn行任意列【答案】正确是：B18、设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）Ap->right=s；s->left=p；p->right->left=s；s->right=p->right；Bs->left=p；s->right=p->right；p->right=s；p->right->left=s；Cp->right=s；p->right->left=s；s->left=p；s->right=p->right；Ds->left=p；s->right=p->right；p->right->left=s；p->right=s；【答案】正确是：D19、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。A2，3，5，8，6B3，2，5，8，6C3，2，5，6，8D2，3，6，5，8【答案】正确是：C20、（）二叉排序树可以得到一个从小到大的有序序列。A先序遍历B中序遍历C后序遍历D层次遍历【答案】正确是：B21、 AABBCCDD【答案】正确是：B22、设某数据结构的二元组形式表示为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图型结构【答案】正确是：B23、对于一些特殊矩阵，采用压缩存储的目的是（ ）。A使表达变得更简单B对矩阵元素的存取变得简单C去掉矩阵中的多于元素D减少不必要的存储空间【答案】正确是：D24、求字符串T在字符串S中首次出现的位置的操作称为（ ）。A串的模式匹配B求子串C求串的长度D串的连接【答案】正确是：A25、设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。AaedfcbBacfebdCaebcfdDaedfbc【答案】正确是：A26、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A2m-1B2mC2m+1D4m【答案】正确是：B27、在二叉排序树中插入一个结点的时间复杂度为（）。AO(1)BO(n)CO(log2n)DO(n)【答案】正确是：B28、任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（ ）。A不发生改变B发生改变C不能确定D以上都不对【答案】正确是：A29、设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。A1B2C3D4【答案】正确是：C30、对一棵二叉排序树进行（ ）遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。A前序B中序C后序D按层次【答案】正确是：B二、判断题共20题，40分1、对连通图进行深度优先遍历可以访问到该图中的所有顶点。A错误B正确【答案】正确是：B2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。A错误B正确【答案】正确是：A3、图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。A错误B正确【答案】正确是：B4、有向图的邻接表和逆邻接表中表结点的个数不一定相等。A错误B正确【答案】正确是：A5、 A错误B正确【答案】正确是：B6、线性表的顺序存储结构没有比链式存储结构更好。A错误B正确【答案】正确是：B7、由树转化成二叉树，该二叉树的右子树不一定为空。（ ）A错误B正确【答案】正确是：A8、 A错误B正确【答案】正确是：A9、堆是完全二叉树，完全二叉树不一定是堆。A错误B正确【答案】正确是：B10、调用一次深度优先遍历可以访问到图中的所有顶点。A错误B正确【答案】正确是：A11、不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。A错误B正确【答案】正确是：B12、顺序查找法适用于存储结构为顺序或链接存储的线性表。 ( )A错误B正确【答案】正确是：B13、算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。A错误B正确【答案】正确是：B14、通常使用两个类来协同表示单链表，即链表的结点类和链表类。A错误B正确【答案】正确是：B15、堆排序所需的时间与待排序的记录个数无关。（ ）A错误B正确【答案】正确是：A16、当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）A错误B正确【答案】正确是：B17、完全二叉树中的叶子结点只可能在最后两层中出现。（ ）A错误B正确【答案】正确是：B18、哈夫曼树中有度数为1的结点。A错误B正确【答案】正确是：A19、希尔排序算法的时间复杂度为O(n2)。A错误B正确【答案】正确是：A20、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。A错误B正确【答案】正确是：B