西安交通大学15年7月数据结构考查课试题

西安交通大学15年7月《数据结构》考查课试题西交《数据结构》在线作业试卷总分：100 测试时间：--单选题多选题一、单选题(共40道试题，共80分。V1.栈和队都是()顺序存储的线性结构链式存储的非线性结构满分：2分已知广义表L=((x,y,z)，a,(u，t，w)),从L表中取出原子项t的运算是()Ohead(tail(tail(L)))tail(head(head(tail(L))))head(tail(head(tail(L))))head(tail(head(tail(tail(L)))))满分：2分已知串S=‘aaa其Next数组值为()。01231123TOC\o"1-5"\h\z12311211满分：2分从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 （）排序法。插入选择希尔二路归并满分：2分设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）TOC\o"1-5"\h\zm-nm-n-1n+1条件不足，无法确定满分：2分以下数据结构中，（）是非线性数据结构树字符串队栈满分：2分线索二叉树是一种（）结构。逻辑逻辑和存储物理线性满分：2分TOC\o"1-5"\h\z具有12个关键字的有序表，折半查找的平均查找长度（ ）3.142.55满分：2分栈和队列的共同点是（）。都是先进先出都是先进后出只允许在端点处插入和删除元素没有共同点限制存取点的线性结构F限制存取点的非线性结构满分：2分散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。最大概率最小概率平均概率同等概率满分：2分适用于折半查找的表的存储方式及元素排列要求为 ()链接方式存储，元素无序链接方式存储，元素有序顺序方式存储，元素无序顺序方式存储，兀素有序满分：2分设有两个串p和q,其中q是p的子串，求q在p中首次出现的位置的算法称为()求子串联接匹配求串长满分：2分设广义表L=((a,b,c)),则L的长度和深度分别为()。1和1TOC\o"1-5"\h\z1和31和22和3满分：2分n个结点的线索二叉树上含有的线索数为（）2nn—In+1n满分：2分最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。（rear+1）MODn=frontrear二frontrear+1二front（rear-l）MODn=front满分：2分在完全二叉树中，若一个结点是叶结点，则它没（ ）。左子结点右子结点左子结点和右子结点左子结点，右子结点和兄弟结点满分：2分有六个元素6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？()543612453126346521234156满分：2分一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是()。不确定TOC\o"1-5"\h\zn-i+1in-i满分：2分表达式a*(b+c)-d的后缀表达式是()。abcd*+-abc+*d-abc*+d--+*abcd满分：2分若串S='software其子串的数目是()。TOC\o"1-5"\h\z837369满分：2分设树T的度为4，其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数为（）5678满分：2分链表不具有的特点是（）插入、删除不需要移动元素可随机访问任一元素不必事先估计存储空间所需空间与线性长度成正比满分：2分设给定权值总数有n个，其哈夫曼树的结点总数为（）不确定2n2n+12n-1满分：2分一棵二叉树的前序遍历序列为ABCDEFG它的中序遍历序列可能是（）CABDEFGABCDEFGDACEFBGADCFEG满分：2分树的后根遍历序列等同于该树对应的二叉树的（）.先序序列中序序列后序序列都不正确满分：2分算术表达式a+b*（c+d/e）转为后缀表达式后为（）ab+cde/*abcde/+*+abcde/*++abcde*/++满分：2分若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。直接插入直接选择堆快速满分：2分若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）TOC\o"1-5"\h\z91115不确定满分：2分有n个叶子的哈夫曼树的结点总数为（）。不确定TOC\o"1-5"\h\z2n2n+12n-1满分：2分下述文件中适合于磁带存储的是（）。顺序文件索引文件散列文件多关键字文件满分：2分对序列｛15,9,7,8,20,-1,4｝进行排序，进行一趟后数据的排列变为｛4，9，-1，8，20，7,15｝;则采用的是()排序。选择快速希尔冒泡满分：2分从逻辑上可以把数据结构分为()两大类。动态结构、静态结构顺序结构、链式结构线性结构、非线性结构初等结构、构造型结构满分：2分字符串‘ababaabab的'nextval为()(0,1,0,1,04,1,0,1)(0,1,0,1,021,0,1)(0,1,0,1,0,0,0,1,1)(0,1,0,1,0,1,0,1,1)满分：2分对关键码序列28,16,32,12,60,2,5,72快速排序，从小到大一次划分结果为()。(2,5,12,16)26(60,32,72)(5,16,2,12)28(60,32,72)(2,16,12,5)28(60,32,72)(5,16,2,12)28(32,60,72)满分：2分对稀疏矩阵进行压缩存储目的是()。便于进行矩阵运算便于输入和输出节省存储空间降低运算的时间复杂度满分：2分图中有关路径的定义是()。由顶点和相邻顶点序偶构成的边所形成的序列由不同顶点所形成的序列由不同边所形成的序列上述定义都不是满分：2分()排序法()排序法冒泡希尔插入交换快速满分：2分—个算法应该是()。程序问题求解步骤