西交《数据结构》在线作业
试卷总分：100 测试时间：--
单选题
多选题

、单选题（共 40 道试题，共 80 分。）
1. 设无向图的顶点个数为n，则该图最多有（ ）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
   满分：2 分
2. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A. O(n) O(n)
B. O(n) O(1)
C. O(1) O(n)
D. O(1) O(1)
   满分：2 分
3. 已知串S=‘aaab’,其Next数组值为（ ）。
A. 0123
B. 1123
C. 1231
D. 1211
   满分：2 分
4. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
   满分：2 分
5. 算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
A. ab+cde/*
B. abcde/+*+
C. abcde/*++
D. abcde*/++
   满分：2 分
6. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。
A. a
B. （）
C. （a,b,c,d）
D. （b,c,d）
   满分：2 分
7. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A. 9
B. 11
C. 15
D. 不确定
   满分：2 分
8. 表达式a*(b+c)-d的后缀表达式是( )。
A. abcd*+-
B. abc+*d-
C. abc*+d-
D. -+*abcd
   满分：2 分
9. （ ）的遍历仍需要栈的支持.
A. 前序线索树
B. 中序线索树
C. 后序线索树
D. 不确定
   满分：2 分
10. 下列排序算法中，占用辅助空间最多的是：( )
A. 归并排序
B. 快速排序
C. 希尔排序
D. 堆排序
   满分：2 分
11. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A. 前序
B. 中序
C. 后序
D. 按层次
   满分：2 分
12. 算法的时间复杂度取决于（ ）
A. 问题的规模
B. 待处理数据的初态
C. A和B
D. 变量个数
   满分：2 分
13. 下面关于算法说法错误的是（ ）
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
   满分：2 分
14. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序
A. 冒泡
B. 希尔
C. 快速
D. 堆
   满分：2 分
15. 求解最短路径的Floyd算法的时间复杂度为( )。
A. O（n）
B. O（n+c）
C. O（n*n）
D. O（n*n*n）
   满分：2 分
16. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A. (2,5,12,16)26(60,32,72)
B. (5,16,2,12)28(60,32,72)
C. (2,16,12,5)28(60,32,72)
D. (5,16,2,12)28(32,60,72)
   满分：2 分
17. 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
   满分：2 分
18. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）
A. CABDEFG
B. ABCDEFG
C. DACEFBG
D. ADCFEG
   满分：2 分
19. 由3 个结点可以构造出多少种不同的二叉树？（ ）
A. 2
B. 3
C. 4
D. 5
   满分：2 分
20. 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）
A. O（i）
B. O（1）
C. O（n）
D. O（i-1）
   满分：2 分
21. 若串S=’software’,其子串的数目是（ ）。
A. 8
B. 37
C. 36
D. 9
   满分：2 分
22. 若要求尽可能快地对序列进行稳定的排序，则应选（
A. 快速排序
B. 归并排序
C. 冒泡排序
D. 堆
   满分：2 分
23. 从逻辑上可以把数据结构分为（ ）两大类。
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
   满分：2 分
24. 栈和队都是（ ）
A. 顺序存储的
B. 线性结构
C. 链式存储的
D. 非线性结构
   满分：2 分
25. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。
A. 808
B. 818
C. 1010
D. 1020
   满分：2 分
26. 在下面的排序方法中，辅助空间为O（n）的是( )
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
   满分：2 分
27. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。
A. p->next=s;s->next=p->next;
B. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
D. p->next=s->next;p->next=s;
   满分：2 分
28. 线索二叉树是一种（ ）结构。
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性
   满分：2 分
29. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A. 求子串
B. 联接
C. 匹配
D. 求串长
   满分：2 分
30. 线性表是具有n个（ ）的有限序列（n>0）。
A. 表元素
B. 字符
C. 数据元素
D. 数据项
   满分：2 分
31. 用二分（对半）查找表的元素的速度比用顺序法( )
A. 必然快
B. 必然慢
C. 相等
D. 不能确定
   满分：2 分
32. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
A. 3
B. 10
C. 15
D. 25
   满分：2 分
33. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。
A. O(0)
B. O(1)
C. O(n)
D. O(n2)
   满分：2 分
34. 已知广义表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 分
35. 一个递归算法必须包括（ ）。
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
   满分：2 分
36. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
A. 8
B. 9
C. 10
D. ll
   满分：2 分
37. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
A. 直接插入
B. 直接选择
C. 堆
D. 快速
   满分：2 分
38. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定
B. n-i+1
C. i
D. n-i
   满分：2 分
39. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）
A. m-n
B. m-n-1
C. n+1
D. 条件不足，无法确定
   满分：2 分
40. 链表不具有的特点是（ ）
A. 插入、删除不需要移动元素
B. 可随机访问任一元素
C. 不必事先估计存储空间
D. 所需空间与线性长度成正比
   满分：2 分

西交《数据结构》在线作业
试卷总分：100 测试时间：--
单选题
多选题

、多选题（共 10 道试题，共 20 分。）
1. 下述哪些不是顺序存储结构的优点？（ ）
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
   满分：2 分
2. 下面关于串的的叙述中，正确的是？（ ）
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
   满分：2 分
3. 下面关于求关键路径的说法正确的是（ ）。
A. 求关键路径是以拓扑排序为基础的
B. ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D. 关键活动一定位于关键路径上
   满分：2 分
4. 下列关于m阶B-树的说法正确的是( )
A. 根结点至多有m棵子树
B. 所有叶子都在同一层次上
C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树
D. 根结点中的数据是有序的
   满分：2 分
5. 下列说法正确的是（ ）。
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 图的深度遍历不适用于有向图
C. 遍历的基本算法有两种：深度遍历和广度遍历
D. 图的深度遍历是一个递归过程
   满分：2 分
6. 下面几个符号串编码集合中，是前缀编码的是（ ）
A. {0,10,110,1111}
B. {11,10,001,101,0001}
C. {00,010,0110,1000}
D. {b,c,aa,ac,aba,abb,abc}
   满分：2 分
7. 下面说法正确的是( )。
A. 广义表的表头总是一个广义表
B. 广义表的表尾总是一个广义表
C. 广义表难以用顺序存储结构
D. 广义表可以是一个多层次的结构
   满分：2 分
8. 在下列情况中，不能为二叉树的是（ ）
A. 每个结点至多有两棵子树的树
B. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
   满分：2 分
9. 下面关于二分查找的叙述不正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
   满分：2 分
10. 以下数据结构中，哪些不是线性结构（ ）
A. 广义表
B. 二叉树
C. 稀疏矩阵
D. 串
   满分：2 分