程序员-数据结构
(总分127,考试时间90分钟)
单选题
60．前序遍历序列与中序遍历序列相同的二叉树为 (1) ，前序遍历序列与后序遍历序列相同的二叉树为 (2) 。   
1. (1)
A. 根结点无左子树的二叉树
B. 根结点无右子树的二叉树
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树
2. (2)
A. 非叶子结点只有左子树的二叉树        B. 只有根结点的二叉树
C. 根结点无右子树的二叉树        D. 非叶子结点只有右子树的二叉树
3. (1)
A. 1        B. 2
C. 5        D. 15
4. (2)
5. 在深度为5的满二叉树中，结点的个数为______。
A. 32        B. 31
C. 16        D. 15
6. 若push、pop分别表示入栈、出栈操作，初始栈为空且元素1、2、3依次进栈，则经过操作序列push、push、pop、pop、push、pop之后，得到的出栈序列为______。
A. 321        B. 213
C. 231        D. 123
7. 栈和队列的共同点是______。
A. 都是先进先出        B. 都是先进后出
C. 只允许在端点处插入和删除元素        D. 没有共同点
8. 对长度为n的线性表进行顺序查，在最坏情况下，所需要的比较次数为______。
A. 1og2n        B. n/2
C. n        D. n+1
9. 下列叙述中正确的是______。
A. 数据的逻辑结构与存储结构必定是一一对应的
B. 由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构
C. 程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构
D. 以上三种说法都不对
10. 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 ______。
A. 冒泡排序为n/2        B. 冒泡排序为n
C. 快速排序为n        D. 快速排序为n(n-1)/2
11. 用二分法来检索数据，最确切的说法是______。
A. 仅当数据随机排列时，才能正确地检索数据
B. 仅当数据有序排列时，才能正确地检索数据
C. 仅当数据量较大时，才能有效地检索数据
D. 仅当数据量较小时，才能有效地检索数据
96．堆排序是一种基于______的排序方法，______不是堆。   
12. (1)
A. 计数        B. 插入
C. 选择        D. 归并
13. (2)
A. 15,28,25,56,68,63,30
B. 15,28,25,30,68,63,56
C. 68,28,63,25,15,56,30
D. 68,56,39,63,28,25,15
14. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i(1≤i≤n)个元素是______。
A. 不确定        B. n-i+l
C. i        D. n-i
66．图的存储结构主要有邻接表和 (1) ，若用邻接表来存储一个图，则需要保存一个 (2) 存储的结点表和若干个 (3) 存储的关系表(又称边表)。
15. (1) A．转移矩阵      B．邻接矩阵       
C．状态矩阵        D．优先矩阵   
16. (2) A．顺序        B．链接       
C．散列        D．分块   
17. (3) A．顺序        B．链接       
C．散列        D．分块   
94．设有n个结点进行排序，不稳定排序是 (1) ；快速排序的最大比较次数是 (2) 。   
18. (1)
A. 直接插入排序        B. 冒泡排序
C. Shell排序        D. 归并排序
19. (2) A．nlog2n    C．n2    C．n2/2      D．n
20. 字符串computer中长度为3的子串有______个。
A. 4        B. 5
C. 6        D. 7
21. n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，______。
A. 元素的出队次序与进栈次序相同        B. 元素的出队次序与进栈次序相反
C. 元素的进栈次序与进队次序相同        D. 元素的出栈次序与出队次序相反
22. 设初始栈为空，s表示入栈操作，x表示出栈操作，则______是合法的操作序列。
A. sxxsssxxx        B. xxssxxss
C. sxsxssxx        D. xssssxxx
88．在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是 (1) 排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是 (2) 排序。   
23. (1)
A. 插入        B. 枚举
C. 交换        D. 归并
E. 基数  选择  希尔
24. (2)
A. 插入        B. 枚举
C. 交换        D. 归并
E. 基数  选择  希尔
25. 设栈S初始状态为空。元素a、b、c、d、e、f依次通过栈S，若出栈的顺序为c、f、 e、 d、b、a，则栈S的容量至少应该为______。
A. 6        B. 5
C. 4        D. 3
26. 在深度为7的满二叉树中，叶子结点的个数为______。
A. 32        B. 31
C. 64        D. 63
27. 以下数据结构中属于线性数据结构的是______。
A. 集合        B. 线性表
C. 二叉树        D. 图
28. 对长度为n的线性表排序，在最坏的情况下，比较次数不是n(n-1)/2的排序方法是______。
A. 快速排序        B. 冒泡排序
C. 直接插入排序        D. 堆排序
29. 已知N个数已存入数组A[1..M]的前N个元素中(N＜M)，为在A[i](1≤i≤N)之前插入一个新数，应先______，以挪出一个空闲位置插入该数。
A. 从A开始直到A[1]，每个数向后移动一个位置
B. 从A[1]开始直到A，每个数向后移动一个位置
C. 从A开始直到A，每个数向前移动一个位置
D. 从A开始直到A，每个数向后移动一个位置
30. 数据结构主要研究数据的______。
A. 逻辑结构        B. 存储结构
C. 逻辑结构和存储结构        D. 逻辑结构和存储结构及其运算的实现
31. 假设一棵二叉树的后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，则其前序遍历序列为______。
A. ABCDEFGHIJ        B. ABDEGHJCFI
C. ABDEGHJFIC        D. ABDEGJHCFI
32. 广度优先遍历的含义是：从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。______是图8-32的广度优先遍历序列。 
A. 1 2 6 3 4 5        B. 1 2 3 4 5 6
C. 1 6 5 2 3 4        D. 1 6 4 5 2 3
33. 采用哈希(或散列)技术构造查表时，需要考虑冲突(碰撞)的处理，冲突是指______。
A. 关键字相同的记录被映射到不同的哈希地址
B. 关键字依次被映射到编号连续的哈希地址
C. 关键字不同的记录被映射到同一个哈希地址
D. 关键字的数目超过哈希地址的数目
34. 若二维数组P[1..5,0..8]的首地址为base，数组元素按行存储，且每个元素占用1个存储单元，则元素P[3,3]在该数组空间的地址为______。
A. base+13        B. base+16
C. base+18        D. base+21
35. 数据结构中的树最适合用来表示______的情况。
A. 数据元素有序        B. 数据元素之间具有多对多关系
C. 数据元素无序        D. 数据元素之间具有一对多关系
36. 设数组a[1..3,1..4]中的元素以列为主序存放，每个元素占用1个存储单元，则数组元素 a[2,3]相对于数组空间首地址的偏移量为______。 A．6  B．7  C．8  D．9
37. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是______。
A. 6        B. 4
C. 3        D. 2
38. 堆栈操作中，______保持不变。
A. 堆栈的顶        B. 堆栈中的数据
C. 堆栈指针        D. 堆栈的底
39. 以下关于字符串的判定语句中正确的是______。
A. 字符串是一种特殊的线性表        B. 串的长度必须大于零
C. 字符串不属于线性表的一种        D. 空格字符组成的串就是空串
40. 已知有一维数组*n-1]，其中m＞n。从数组T的第一个元素(T[0])开始，每隔n个元素取出一个元素依次存入数组]中，即B[1]=T[0]，D[2]=T[n]，依此类推，那么放入B[k](1≤k≤n)的元素是______。
A. T[(k-1)*n]        B. T(k*
C. T[(k-1)*m]        D. T[k*m]
41. 以下各图用树结构描述了7个元素之间的逻辑关系，其中，______适合采用二分法查元素。
A.
B.
C.
字符串长度的正确表示
D.
42. 为了描述n个人之间的同学关系，可用______结构表示。
A. 线性表        B. 树
C. 图        D. 队列
43. 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为______。
可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈操作。对算术表达式“(a+b*(a+b))/c)+(a+b)”，检查时，  (1)  ；对算术表达式“((a+b/(a+b)-c/a)/b”，检查时，  (2)  。这两种情况都表明所检查的算术表达式括号不匹配。
44. (1) A．栈为空却要进行出栈操作    B．栈已满却要进行入栈操作    C．表达式处理已结束，栈中仍留下有字符“(”    D．表达式处理已结束，栈中仍留下有字符“)”       
45. (2) A．栈为空却要进行出栈操作    B．栈已满却要进行入栈操作    C．表达式处理已结束，栈中仍留下有字符“(”    D．表达式处理已结束，栈中仍留下有字符“)”   

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。