【奥鹏】[西安交通大学]西安交通大学19年3月课程考试《数据结构》作业考核试题.docxVIP

【奥鹏】[西安交通大学]西安交通大学 19 年 3 月课程考试《数据结构》作业考核试题 试卷总分:100 得分:100 第 1 题,一个栈的输入序列为 123?n，若输出序列的第一个元素是 n，输出第 i（1=i=n）个元素是（ ）。 A、不确定 B、n-i+1 C、i D、n-i 正确答案:B 第 2 题,设用链表作为栈的存储结构则退栈操作（） A、必须判别栈是否为满 B、必须判别栈是否为空 C、判别栈元素的类型 D、对栈不作任何判别 正确答案:B 第 3 题,如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用（ ）存储结构。 A、散列 B、顺序 C、链式 D、任意 正确答案:C 第 4 题,下列程序段的时间复杂度为（）。i=0，s=0；while(sn){s=s+i；i++；} A、O(n) B、O(n) C、O(n) D、O(n) 正确答案:A 第 5 题,两个字符串相等的条件是（ ）。 A、两串的长度相等； B、两串包含的字符相同； C、两串的长度相等，并且两串包含的字符相同； D、两串的长度相等，并且对应位置上的字符相同。 正确答案:D 第 6 题,在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 A、O(n) B、O(1og2n) C、O(nlog2n) D、O(n) 正确答案:B 第 7 题,在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为（） A、e B、2e C、n2－e D、n2－2e 正确答案:D 第 8 题,由两个栈共享一个向量空间的好处是：（） A、减少存取时间，降低下溢发生的机率 B、节省存储空间，降低上溢发生的机率 C、减少存取时间，降低上溢发生的机率 D、节省存储空间，降低下溢发生的机率 正确答案:B 第 9 题,哈希表的平均查找长度是( )的函数。 A、哈希表的长度 B、表中元素的多少 C、哈希函数 D、哈希表的装满程度 正确答案:D 第 10 题,深度优先遍历类似于二叉树的（ ）。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 正确答案:A 第 11 题,以下数据结构中哪一个是非线性结构？（） A、队列 B、栈 C、线性表 D、二叉树 正确答案:D 第 12 题,最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ ）。 A、(rear+1) MOD n=front B、rear=front C、rear+1=front D、(rear-l) MOD n=front 正确答案:B 第 13 题,设带有头结点的单向循环链表的头指针变量为 head，则其判空条件是（）。 A、head==0 B、head-next==0 C、head-next==head D、head!=0 正确答案:C 第 14 题,设输入序列 1、2、3、?、n 经过栈作用后，输出序列中的第一个元素是 n，则输出序列中的第 i 个输出元素是（）。 A、n-i B、n-1-i C、n+l-i D、不能确定 正确答案:C 第 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) 正确答案:A 第 16 题,设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为（） A、BADC B、BCDA C、CDAB D、CBDA 正确答案:A 第 17 题,有 n 个顶点的无向图的邻接矩阵是用（ ）数组存储。 A、一维 B、n 行 n 列 C、任意行 n 列 D、n 行任意列 正确答案:B 第 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； 正确答案:D 第 19 题,设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字 5 为基准进行一趟快速排序的结果为（）。 A、2，3