|
|
一、单项选择题(共36题，每题2分，共72分)
1. (教材第6章树和二叉树)树最适合用来表示（ ）。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有层次关系的数据
D. 元素之间无联系的数据
2. (教材7.1.2图的基本术语)有8个顶点的无向连通图最少有（ ）条边。
A. 5
B. 6
C. 7
D. 8
3. (教材4.1.1串的定义)串是一种特殊的线性表，其特殊性体现在（ ）
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链式存储
D. 数据元素可以是多个字符
4. (教材2.3.1单链表的定义)链式存储结构所占存储空间（ ）。
A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B. 只有一部分，存放结点值
C. 只有一部分，存储表示结点间关系的指针
D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数
5. (教材9.2.1直接插入排序)在下列算法中，（ ）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。
A. 堆排序
B. 冒泡排序
C. 直接插入排序
D. 快速排序
6. (教材1.2.2算法分析)算法分析的目的是（ ）。
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易懂性和文档性
7. (教材7.1.2图的基本术语)在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
A. 1/2
B. 1
C. 2
D. 4
8. (教材3.1.1栈的基本概念)一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）
A. edcba
B. decba
C. dceab
D. abcde
9. (教材3.1.1栈的基本概念)栈中元素的进出原则是（ ）
A. 先进先出
B. 后进先出
C. 栈空则进
D. 栈满则出
10. (教材4.1.1串的定义)两个串相等必有串长度相等且（ ）。
A. 串的各位置字符任意
B. 串中各对应位置字符均相等
C. 两个串含有相同的字符
D. 两个所含字符任意
11. (教材4.1.1串的定义)以下（ ）是"abcd321ABCD"串的子串。
A. abcd
B. 321AB
C. "abcABC"
D. "21AB"
12. (教材8.2.2折半查找)对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。
A. 3
B. 4
C. 5
D. 6
13. (教材8.2.1顺序查找)某顺序表中有90000个元素，已按关键项的值的升序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为（ ）
A. 25000
B. 30000
C. 45000
D. 90000
14. (教材3.1.1栈的基本概念)已知一个栈的进栈序列是1，2，3，…，n，其输出序列的第一个元素是i（1≤i≤n）则第j（1≤j≤n）个出栈元素是（ ）。
A. i
B. n-i
C. j-i+1
D. 不确定
15. (教材2.2.2线性表基本运算在顺序表上的实现) 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ ）。
A. 访问第i个结点（1≤i≤n）和求第i（2≤i≤n）个结点的前驱结点
B. 在第i（1≤i≤n）个结点后插入一个新结点
C. 删除第i个结点（1≤i≤n）
D. 将n个结点从小到大排序
16. (教材9.2.1直接插入排序)对数据序列{15,9,7,8,20,-1,4}进行排序，进行一趟后数据的排序变为{9,15,7,8,20,-1,4}，则采用的是（ ）算法。
A. 简单选择排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
17. (教材1.2.2算法分析)算法分析的两个主要方面是（ ）。
A. 空间复杂性和时间复杂性
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
18. (教材8.2.2折半查找)折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
A. 20,70,30,50
B. 30,88,70,50
C. 20,50
D. 30,88,50
19. (教材5.1.2数组的存储结构)假设有60行70列的二维数组a[1..60,1..70]（数组下标从1开始）以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ ）。
A. 16902
B. 16904
C. 14454
D. 以上都不对
20. (教材8.2.1顺序查找)链表适用于（ ）查找
A. 顺序
B. 二分法
C. 二分法
D. 随机
21. (教材1.1.3存储结构)数据在计算机存储器内表示时，物理地址与逻辑地址相对顺序相同并且是连续的，称之为（ ）存储结构。
A. 存储结构
B. 逻辑结构
C. 顺序存储结构
D. 链式存储结构
22. (教材9.2.1直接插入排序)对有n个记录的表进行直接插入排序，在最坏情况下需进行（ ）次关键字比较。
A. n-1
B. n+1
C. n/2
D. n(n-1)/2
23. (教材5.2特殊矩阵的压缩存储)对特殊矩阵采用压缩存储的目的主要是为了（ ）。
A. 表达变得简单
B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素
D. 减少不必要的存储空间
24. (教材7.1.2图的基本术语)在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。
A. 1/2
B. 1
C. 2
D. 4
25. (教材6.1.1树的定义)树是结点的有限集合，它（ ）根结点，记为T。
A. 有0个或1个
B. 有0个或多个
C. 有且只有1个
D. 有1个或1个以上
26. (教材1.1.1什么是数据结构)数据结构中与所使用的计算机无关的是数据的（ ）结构。
A. 存储
B. 物理
C. 逻辑
D. 物理和存储
27. (教材7.1.2图的基本术语)有8个顶点的无向图最多有（ ）条边。
A. 14
B. 28
C. 56
D. 112
28. (教材2.2.3顺序表的插入和删除算法分析)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。
A. 8
B. 63.5
C. 63
D. 7
29. (教材5.2特殊矩阵的压缩存储)设矩阵a是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组b[1..n(n-1)/2]中（数组下标均从1开始），对下三角部分中任一元素ai,j（i≤j）在一维数组b中下标k的值是（ ）。
A. i(i-1)/2+j-1
B. i(i-1)/2+j
C. i(i+1)/2+j-1
D. i(i+1)/2+j
30. (教材3.1.1栈的基本概念)设一个栈的进栈序列是A、B、C、D（即元素A～D依次通过该栈），则借助该栈所得到的输出序列不可能是（ ）
A. A,B,C,D
B. D,C,B,A
C. A,C,D,B
D. D,A,B,C
31. (教材6.7.1森林/树转换成二叉树)把一棵树转换为二叉树后，这棵二叉树的形态是（ ）
A. 唯一的
B. 有多种
C. 有多种，但根结点都没有左孩子
D. 有多种，但根结点都没有右孩子
32. (教材6.7.1森林/树转换成二叉树)每棵树都能唯一地转换成与它对应的二叉树，由一棵树转换成的二叉树中，一个结点N的左孩子是N在原树里对应结点的（ ③ ）。
A. 最左孩子结点
B. 最右孩子结点
C. 最邻近的右兄弟
D. 最邻近的左兄弟
33. (教材1.1.2逻辑结构)线性结构中数据元素之间是（ ）关系
A. 一对多
B. 多对多
C. 多对一
D. 一对一
34. (教材5.2特殊矩阵的压缩存储)一个n×n的对称矩阵，如果采用压缩存储以行或列为主序放入内存，则压缩存储的容量是（ ）。
A. n2
B. n2/2
C. n(n+1)/2
D. (n+1)2/2
35. (教材9.2.1直接插入排序)内排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）
A. 希尔排序
B. 冒泡排序
C. 直接插入排序
D. 简单选择排序
36. (p85教材3.2.1队列的基本概念)队列中元素的进出原则是（ ）。
A. 先进先出
B. 后进先出
C. 栈空则进
D. 栈满则出
二、简答题(共16题，每题1分，共16分)
37. (教材p30，2.2.3顺序表的插入和删除算法分析)对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？
点此输入资料
38. (教材p7，1.1.5数据结构、数据类型和抽象数据类型)数据结构和数据类型两个概念之间有区别吗？
点此输入资料
39. (教材p195，7.2.1邻接矩阵, 7.2.2邻接表)从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？
点此输入资料
40. (教材p67，2.5两类存储结构的优缺点比较)试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
点此输入资料
41. (教材p281-p283，9.2.3希尔排序)给出关键字序列{4,5,1,2,8,6,7,3,10,9}的希尔排序过程。
点此输入资料
42. (教材p276-p300，第9章排序中的内排序)简要叙述如何选择好的内排序方法。
点此输入资料
43. (教材p75, 第2章线性表，第3章栈和队列)简要说明线性表、栈与队的异同点。
点此输入资料
44. (教材p143，6.2.1二叉树的定义)一棵度为2的树与一棵二叉树有何区别？
点此输入资料
45. (教材p3，1.1.2逻辑结构)简述线性结构、树形结构和图形结构的不同点。
点此输入资料
46.
(教材p216-p219，7.5.1单源最短路径算法)对于图7.2所示的带权有向图，求从顶点0到其他各顶点的最短路径。
[点击放大]
图7.2 一个有向带权图
点此输入资料
47. (教材p238，8.2.2折半查找)折半查找适不适合链表结构的序列，为什么？用折半查找的查找速度必然比线性查找的速度快，这种说法对吗？
点此输入资料
48. (教材p105，4.1.1串的定义)设s为一个长度为n的串，其中的字符各不相同，则s中的互异的非平凡子串（非空且不同于s本身）的个数是多少？
点此输入资料
49. (教材p237-244，8.2静态查找表)简述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，三种查找法在查找成功时的平均查找长度各是多少？
点此输入资料
50. (教材p87-p92，3.2.2队列的顺序存储结构)顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
点此输入资料
51. (教材p105，4.1.1串的定义)若s1和s2为串，给出使s1//s2=s2//s1成立的所有可能的条件（其中，“//”表示两个串连接运算符）。
点此输入资料
52. (教材p144-p146，6.2.2二叉树的性质)试求含有n0个叶子结点的完全二叉树的总结点数。
点此输入资料
三、算法设计题(共4题，每题3分，共12分)
53. (教材p188，7.1.2图的基本术语；p201，7.3.1深度优先遍历算法)假设以邻接表作为图的存储结构，设计一个算法求出无向图G的连通分量个数。
点此输入资料
54. (教材p125-p126，5.1.2数组的存储结构，5.1.3数组的应用示例)已知一个n×n矩阵B按行优先存于一个一维数组A[0..n(n-1)]中，试给出一个就地算法将原矩阵转置后仍存于数组A中。
点此输入资料
55. (教材p190-p202，7.2.1邻接矩阵, 7.3.1深度优先遍历算法)假设图G采用邻接矩阵存储，给出图的深度优先遍历算法，并分析算法的时间复杂度。
点此输入资料
56. (教材p124-p126，5.1数组)假定数组A[0..n-1]的n个元素中有多个零元素，设计一个算法将A中所有的非零元素依次移到A的前端。
|
|
IP卡
狗仔卡
发表于 2016-11-11 15:49:27
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2016-12-1 22:16:26
客服一
