西交15年《数据结构》考查课试题一最新.docx

1、西交15年数据结构考查课试题一最新西安交通大学15年7月数据结构考查课试题西交数据结构在线作业试卷总分：100 测试时间：-单选题 多选题一、单选题（共 40 道试题，共 80 分。）V 1.栈和队都是（ ）A. 顺序存储的B. 线性结构C. 链式存储的D. 非线性结构 满分：2分2.已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ）。A. head（tail（tail（L）B. tail（head（head（tail（L）C. head（tail（head（tail（L）D. head（tail(head（tail（tail（L）)） 满分：2分3.已知串S

2、=aaab,其Next数组值为（ ）。A. 0123B. 1123C. 1231D. 1211 满分：2分4.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A. 插入B. 选择C. 希尔D. 二路归并 满分：2分5.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）A. m-nB. m-n-1C. n+1D. 条件不足，无法确定 满分：2分6.以下数据结构中，（ ）是非线性数据结构A. 树B. 字符串C. 队D. 栈 满分：2分7.线索二叉树是一种（ ）结

3、构。A. 逻辑B. 逻辑和存储C. 物理D. 线性 满分：2分8.具有12个关键字的有序表，折半查找的平均查找长度（ ）A. 3.1B. 4C. 2.5D. 5 满分：2分9.栈和队列的共同点是（ ）。A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点E. 限制存取点的线性结构F. 限制存取点的非线性结构 满分：2分10.散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。A. 最大概率B. 最小概率C. 平均概率D. 同等概率 满分：2分11.适用于折半查找的表的存储方式及元素排列要求为( )A. 链接方式存储，元素无序B. 链接方式存储，元素

4、有序C. 顺序方式存储，元素无序D. 顺序方式存储，元素有序 满分：2分12.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）A. 求子串B. 联接C. 匹配D. 求串长 满分：2分13.设广义表L=（a,b,c），则L的长度和深度分别为（ ）。A. 1和1B. 1和3C. 1和2D. 2和3 满分：2分14.n个结点的线索二叉树上含有的线索数为（ ）A. 2nB. nlC. nlD. n 满分：2分15.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。A. (rear+1) MOD n=frontB. rear=frontC.

5、 rear+1=frontD. (rear-l) MOD n=front 满分：2分16.在完全二叉树中，若一个结点是叶结点，则它没（ ）。A. 左子结点B. 右子结点C. 左子结点和右子结点D. 左子结点，右子结点和兄弟结点 满分：2分17.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6 满分：2分18.一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。A. 不确定B. n-i+1C. iD. n-i

6、 满分：2分19.表达式a*(b+c)-d的后缀表达式是( )。A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd 满分：2分20.若串S=software,其子串的数目是（ ）。A. 8B. 37C. 36D. 9 满分：2分21.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A. 5B. 6C. 7D. 8 满分：2分22.链表不具有的特点是（ ）A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比 满分：2分23.设给定权值总数有n 个，其哈夫曼树的结点总

7、数为( )A. 不确定B. 2nC. 2n+1D. 2n-1 满分：2分24.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）A. CABDEFGB. ABCDEFGC. DACEFBGD. ADCFEG 满分：2分25.树的后根遍历序列等同于该树对应的二叉树的( ).A. 先序序列B. 中序序列C. 后序序列D. 都不正确 满分：2分26.算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）A. ab+cde/*B. abcde/+*+C. abcde/*+D. abcde*/+ 满分：2分27.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为

8、宜。A. 直接插入B. 直接选择C. 堆D. 快速 满分：2分28.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A. 9B. 11C. 15D. 不确定 满分：2分29.有n个叶子的哈夫曼树的结点总数为（ ）。A. 不确定B. 2nC. 2n+1D. 2n-1 满分：2分30.下述文件中适合于磁带存储的是（ ）。A. 顺序文件B. 索引文件C. 散列文件D. 多关键字文件 满分：2分31.对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（ ）排序。A. 选择B. 快速C. 希尔D. 冒泡 满

9、分：2分32.从逻辑上可以把数据结构分为（ ）两大类。A. 动态结构、静态结构B. 顺序结构、链式结构C. 线性结构、非线性结构D. 初等结构、构造型结构 满分：2分33.字符串ababaabab 的nextval 为（ ）A. (0,1,0,1,04,1,0,1)B. (0,1,0,1,0,2,1,0,1)C. (0,1,0,1,0,0,0,1,1)D. (0,1,0,1,0,1,0,1,1 ) 满分：2分34.对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。A. (2,5,12,16)26(60,32,72)B. (5,16,2,12)28(6

10、0,32,72)C. (2,16,12,5)28(60,32,72)D. (5,16,2,12)28(32,60,72) 满分：2分35.对稀疏矩阵进行压缩存储目的是（ ）。A. 便于进行矩阵运算B. 便于输入和输出C. 节省存储空间D. 降低运算的时间复杂度 满分：2分36.图中有关路径的定义是（ ）。A. 由顶点和相邻顶点序偶构成的边所形成的序列B. 由不同顶点所形成的序列C. 由不同边所形成的序列D. 上述定义都不是 满分：2分37.就平均性能而言，目前最好的内排序方法是( )排序法。A. 冒泡B. 希尔插入C. 交换D. 快速 满分：2分38.一个算法应该是（ ）。A. 程序B. 问题求解步骤的描述C. 要满足五个基本特性D. A和C. 满分：2分39.具有10个叶结点的二叉树中有（ ）个度为2的结点，A. 8B. 9C. 10D. ll 满分：2分40.求解最短路径的Floyd算法的时间复杂度为( )。A. O（n）B. O（n+c）C. O（n*n）D. O（n*n*n） 满分：2分