1、程序员-数据结构及答案解析(总分：127.00，做题时间：90 分钟)一、B单选题/B(总题数：99，分数：127.00)60前序遍历序列与中序遍历序列相同的二叉树为U (1) /U，前序遍历序列与后序遍历序列相同的二叉树为U (2) /U。（分数：4.00）(1).(1)（分数：1.00）A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树或非叶子结点只有右子树的二叉树(2).(2)（分数：1.00）A.非叶子结点只有左子树的二叉树B.只有根结点的二叉树C.根结点无右子树的二叉树D.非叶子结点只有右子树的二叉树(3).
2、(1)（分数：1.00）A.1B.2C.5D.15(4).(2) （分数：1.00）A.B.C.D.1.在深度为 5的满二叉树中，结点的个数为_。（分数：1.00）A.32B.31C.16D.152.若 push、pop 分别表示入栈、出栈操作，初始栈为空且元素 1、2、3 依次进栈，则经过操作序列push、push、pop、pop、push、pop 之后，得到的出栈序列为_。（分数：1.00）A.321B.213C.231D.1233.栈和队列的共同点是_。（分数：1.00）A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点4.对长度为 n的线性表进行顺序查找，在
3、最坏情况下，所需要的比较次数为_。（分数：1.00）A.1og2nB.n/2C.nD.n+15.下列叙述中正确的是_。（分数：1.00）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上三种说法都不对6.对于长度为 n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 _。（分数：1.00）A.冒泡排序为 n/2B.冒泡排序为 nC.快速排序为 nD.快速排序为 n(n-1)/27.用二分法来检索数据，最确切的说法是_。（分数：1.
4、00）A.仅当数据随机排列时，才能正确地检索数据B.仅当数据有序排列时，才能正确地检索数据C.仅当数据量较大时，才能有效地检索数据D.仅当数据量较小时，才能有效地检索数据96堆排序是一种基于_的排序方法，_不是堆。（分数：2.00）(1).(1)（分数：1.00）A.计数B.插入C.选择D.归并(2).(2)（分数：1.00）A.15,28,25,56,68,63,30B.15,28,25,30,68,63,56C.68,28,63,25,15,56,30D.68,56,39,63,28,25,158.一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i(1in)个元素是_。
5、（分数：1.00）A.不确定B.n-i+lC.iD.n-i66图的存储结构主要有邻接表和U (1) /U，若用邻接表来存储一个图，则需要保存一个U (2) /U存储的结点表和若干个U (3) /U存储的关系表(又称边表)。（分数：3.00）(1).(1) A转移矩阵 B邻接矩阵 C状态矩阵 D优先矩阵（分数：1.00）_(2).(2) A顺序 B链接 C散列 D分块（分数：1.00）_(3).(3) A顺序 B链接 C散列 D分块（分数：1.00）_94设有 n个结点进行排序，不稳定排序是U (1) /U；快速排序的最大比较次数是U (2) /U。（分数：2.00）(1).(1)（分数：1.0
6、0）A.直接插入排序B.冒泡排序C.Shell排序D.归并排序(2).(2) Anlog 2n Cn 2 Cn 2/2 Dn（分数：1.00）A.B.C.D.9.字符串 computer中长度为 3的子串有_个。（分数：1.00）A.4B.5C.6D.710.n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，_。（分数：1.00）A.元素的出队次序与进栈次序相同B.元素的出队次序与进栈次序相反C.元素的进栈次序与进队次序相同D.元素的出栈次序与出队次序相反11.设初始栈为空，s 表示入栈操作，x 表示出栈操作，则_是合法的操作序列。（分数：1.00）A.sxxsssxxxB.xxs
7、sxxssC.sxsxssxxD.xssssxxx88在排序算法中，两两比较待排序的记录，当发现不满足顺序要求时，变更它们的相对位置，这就是U (1) /U排序。每次从未排序的记录中挑出最小(或最大)关键码值的记录，加入到已排序记录的末尾，这是U (2) /U排序。（分数：2.00）(1).(1)（分数：1.00）A.插入B.枚举C.交换D.归并E.基数 选择 希尔(2).(2)（分数：1.00）A.插入B.枚举C.交换D.归并E.基数 选择 希尔12.设栈 S初始状态为空。元素 a、b、c、d、e、f 依次通过栈 S，若出栈的顺序为 c、f、 e、 d、b、a，则栈 S的容量至少应该为_。（
8、分数：1.00）A.6B.5C.4D.313.在深度为 7的满二叉树中，叶子结点的个数为_。（分数：1.00）A.32B.31C.64D.6314.以下数据结构中属于线性数据结构的是_。（分数：1.00）A.集合B.线性表C.二叉树D.图15.对长度为 n的线性表排序，在最坏的情况下，比较次数不是 n(n-1)/2的排序方法是_。（分数：1.00）A.快速排序B.冒泡排序C.直接插入排序D.堆排序16.已知 N个数已存入数组 A1M的前 N个元素中(NM)，为在 Ai(1iN)之前插入一个新数，应先_，以挪出一个空闲位置插入该数。（分数：1.00）A.从 A开始直到 A1，每个数向后移动一个位
9、置B.从 A1开始直到 A，每个数向后移动一个位置C.从 A开始直到 A，每个数向前移动一个位置D.从 A开始直到 A，每个数向后移动一个位置17.数据结构主要研究数据的_。（分数：1.00）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现18.假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为_。（分数：1.00）A.ABCDEFGHIJB.ABDEGHJCFIC.ABDEGHJFICD.ABDEGJHCFI19.广度优先遍历的含义是：从图中某个顶点 v出发，在访问了 v之后依次访问 v的各个未被访
10、问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。_是图 8-32的广度优先遍历序列。 （分数：1.00）A.1 2 6 3 4 5B.1 2 3 4 5 6C.1 6 5 2 3 4D.1 6 4 5 2 320.采用哈希(或散列)技术构造查找表时，需要考虑冲突(碰撞)的处理，冲突是指_。（分数：1.00）A.关键字相同的记录被映射到不同的哈希地址B.关键字依次被映射到编号连续的哈希地址C.关键字不同的记录被映射到同一个哈希地址D.关键字的数目超过哈希地址的数目21.若二
11、维数组 P15,08的首地址为 base，数组元素按行存储，且每个元素占用 1个存储单元，则元素 P3,3在该数组空间的地址为_。（分数：1.00）A.base+13B.base+16C.base+18D.base+2122.数据结构中的树最适合用来表示_的情况。（分数：1.00）A.数据元素有序B.数据元素之间具有多对多关系C.数据元素无序D.数据元素之间具有一对多关系23.设数组 a13,14中的元素以列为主序存放，每个元素占用 1个存储单元，则数组元素 a2,3相对于数组空间首地址的偏移量为_。 A6 B7 C8 D9（分数：1.00）_24.设栈 S和队列 Q的初始状态为空，元素 e1
12、、e2、e3、e4、e5 和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6个元素出队的序列是 e2、e4、e3、e6、e5、e1，则栈 S的容量至少应该是_。（分数：1.00）A.6B.4C.3D.225.堆栈操作中，_保持不变。（分数：1.00）A.堆栈的顶B.堆栈中的数据C.堆栈指针D.堆栈的底26.以下关于字符串的判定语句中正确的是_。（分数：1.00）A.字符串是一种特殊的线性表B.串的长度必须大于零C.字符串不属于线性表的一种D.空格字符组成的串就是空串27.已知有一维数组 T0m*n-1，其中 mn。从数组 T的第一个元素(T0)开始，每隔 n个元素取出一个元素依次存入
13、数组 B1m中，即 B1=T0，D2=Tn，依此类推，那么放入 Bk(1kn)的元素是_。（分数：1.00）A.T(k-1)*nB.T(k*C.T(k-1)*mD.Tk*m28.以下各图用树结构描述了 7个元素之间的逻辑关系，其中，_适合采用二分法查找元素。（分数：1.00）A.B.C.D.29.为了描述 n个人之间的同学关系，可用_结构表示。（分数：1.00）A.线性表B.树C.图D.队列30.设一棵二叉树的中序遍历结果为 DBEAFC，前序遍历结果为 ABDECF，则后序遍历结果为_。（分数：1.00）填空项 1:_可以用栈来检查算术表达式中的括号是否匹配。分析算术表达式时，初始栈为空，从
14、左到右扫描字符，遇到字符“(”就将其入栈，遇到“)”就执行出栈操作。对算术表达式“(a+b*(a+b)/c)+(a+b)”，检查时，U (1) /U；对算术表达式“(a+b/(a+b)-c/a)/b”，检查时，U (2) /U。这两种情况都表明所检查的算术表达式括号不匹配。（分数：2.00）(1).(1) A栈为空却要进行出栈操作 B栈已满却要进行入栈操作 C表达式处理已结束，栈中仍留下有字符“(” D表达式处理已结束，栈中仍留下有字符“)” （分数：1.00）_(2).(2) A栈为空却要进行出栈操作 B栈已满却要进行入栈操作 C表达式处理已结束，栈中仍留下有字符“(” D表达式处理已结束，
15、栈中仍留下有字符“)”（分数：1.00）_31.在文件“局部有序”或文件长度较小的情况下，最佳内部排序方法是_。（分数：1.00）A.直接插入排序B.冒泡排序C.简单选择排序D.归并排序32.数组 A-55,08按列存储。若第一个元素的首地址为 100，且每个元素占用 4个存储单元，则元素A2,3的存储地址为_。（分数：1.00）A.244B.260C.364D.30047满二叉树的特点是每层上的结点数都达到最大值，因此对于高度为h(h1)的满二叉树，其结点总数为 U(1) /U。对非空满二叉树，由根结点开始，按照先根后子树、先左子树后右子树的次序，从 1、2、3、依次编号，则对于树中编号为
16、i的非叶子结点，其右子树的编号为U (2) /U(高度为 3的满二叉树如图 8-17所示)。（分数：6.00）(1).(1)（分数：1.00）A.2hB.2h-1C.2h-1D.2h-1+1(2).(2)（分数：1.00）A.2iB.2i-1C.2i+1D.2i+2(3).(1)（分数：1.00）A.1B.2C.3D.4E.5 6 7 8 9(4).(2)（分数：1.00）A.1B.2C.3D.4E.5 6 7 8 9(5).(3)（分数：1.00）A.1B.2C.3D.4E.5 6 7 8 9(6).(4) （分数：1.00）A.N1下面B.N8下面C.N9下面D.N6下面52二叉树U (1
17、) /U。在完全的二叉树中，若一个结点没有U (2) /U，则它必定是叶结点。每棵树都能唯一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点 N的左子结点是 N在原树里对应结点的U (3) /U，而 N的右子结点是它在原树里对应结点的U (4) /U。（分数：4.00）(1).(1)（分数：1.00）A.是特殊的树B.不是树的特殊形式C.是两棵树的总称D.是只有两个根结点的树形结构(2).(2)（分数：1.00）A.左子结点B.右子结点C.左子结点或者没有右子结点D.兄弟(3).(3)（分数：1.00）A.最左子结点B.最右子结点C.最邻近的右兄弟D.最邻近的左兄弟E.最左的兄弟 最右
18、的兄弟(4).(4)（分数：1.00）A.最左子结点B.最右子结点C.最邻近的右兄弟D.最邻近的左兄弟E.最左的兄弟 最右的兄弟33.为了用一个数代表一批数，人们常用这批数据的算术平均值(简称平均值)或中位数来代表。中位数就是位于这批数中间的数(大于它的数与小于它的数一样多)。对于奇数个数而言，排序后很容易确定中间那个数；对于偶数个数而言，排序后中间会有两个数，再取这两个数的算术平均，就是中位数。以下关于平均值与中位数的叙述中，_是不正确的。（分数：1.00）A.中位数比平均值稳健，不易受极端值影响B.每个数据加倍后，平均值也加倍；每个数据增加 1后，平均值也增加 1C.三组各有 n个数据有三
19、个中位数，它们的中位数就是这三组数据全体的中位数D.三组各有 n个数据有三个平均值，它们的平均值就是这三组数据全体的平均值34.判断“链式队列为空”的条件是_(front 为头指针，rear 为尾指针)。（分数：1.00）A.front=NULLB.rear=NULLC.front=rearD.front!=rear35.某二叉树中度为 2的结点有 18个，则该二叉树中有_个叶子结点。（分数：1.00）A.18B.19C.8D.2036.若线性表(23,14,45,12,8,19,7)采用散列法进行存储和查找。设散列函数为 H(Key)=Key mod 7 并采用线性探查法(顺序地探查可用存储
20、单元)解决冲突，则构造的散列表为_，其中，mod 表示整除取余运算。（分数：1.00）A.哈希地址 0 1 2 3 4 5 6 关键字 14 8 23 45 7 12 19B.哈希地址 0 1 2 3 4 5 6 关键字 7 8 12 14 19 23 45C.哈希地址 0 1 2 3 4 5 6 关键字 7 8 23 45 12 19 14D.哈希地址 0 1 2 3 4 5 6 关键字 14 7 12 8 45 23 1937.下面的排序方法中，关键字比较次数与记录的初始排列无关的是_。（分数：1.00）A.希尔排序B.冒泡排序C.直接插入排序D.直接选择排序39对于二维数组 a14,36
21、，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素 a3,4相对于数组空间起始地址的偏移量分别是U (1) /U和U (2) /U。（分数：6.00）(1).(1)（分数：1.00）A.12B.14C.16D.18(2).(2) （分数：1.00）A.12B.14C.16D.18(3).(1)（分数：1.00）A.480B.192C.216D.144(4).(2)（分数：1.00）A.78B.72C.66D.84(5).(3)（分数：1.00）A.310B.311C.315D.314(6).(4)（分数：1.00）A.179B.178C.184D.18538.无向图的邻接矩阵一定是_
22、。（分数：1.00）A.对角矩阵B.稀疏矩阵C.三角矩阵D.对称矩阵39.在具有 100个结点的树中，其边的数目为_。（分数：1.00）A.101B.100C.99D.9840.在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。（分数：1.00）A.63B.64C.6D.741.下面叙述不正确的是_。（分数：1.00）A.算法的执行效率与数据的存储结构有关B.算法的空间复杂度是指执行这个算法所需要的内存空间C.算法的有穷性是指算法必须能在执行有限个步骤之后终止D.算法的时间复杂度是指执行这个算法所需要的时间42.设有 100个结点，用二分法查找时，最大比较次数是_。（分数
23、：1.00）A.25B.50C.10D.743.在排序算法中每一项都与其他诸项进行比较，计算出小于该项的项的个数，以确定该项的位置叫_。（分数：1.00）A.插入排序B.交换排序C.选择排序D.枚举排序44.设最优的分配方案为完成这三项工作所需的总天数最少，则在最优分配方案中，_。（分数：1.00）A.甲执行 PB.甲执行 QC.乙执行 PD.乙执行 R45.若需将一个栈 S中的元素逆置，则以下处理方式中正确的是_。（分数：1.00）A.将栈 S中元素依次出栈并入栈 T，然后栈 T中元素依次出栈并进入栈 SB.将栈 S中元素依次出栈并入队，然后使该队列元素依次出队并进入栈 SC.直接交换栈顶元
24、素和栈底元素D.直接交换栈顶指针和栈底指针46.二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行_遍历，可得到一个结点元素的递增序列。（分数：1.00）A.先序(根、左、右)B.中序(左、根、右)C.后序(左、右、根)D.层序(从树根开始，按层次)47.若原始数据序列(23,4,45,67,12,8,19,7)采用直接插入排序法(顺序地将每个元素插入到它之前的适当位置)排序，则进行完第 4趟后的排序结果是
25、_。（分数：1.00）A.4,8,45,23,67,12,19,7B.4,7,8,12,23,45,67,19C.4,12,8,19,7,23,45,67D.4,12,23,45,67,8,19,748.n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为_。（分数：1.00）A.O(1)B.O(1og2C.O(n2)D.O(49.在长度为 64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。（分数：1.00）A.63B.64C.6D.750.对于 n个元素的关键字序列k 1,k2,kn，若将其按次序对应到一棵具有 n个结点的完全二叉树上，使得任意结点都不大于其孩子结点(若存在孩子
26、结点)，则称其为小顶堆。根据以上定义，_是小顶堆。（分数：1.00）A.B.C.D.51.对图 8-16所示的二叉树进行中序遍历(左子树，根，右子树)的结果是_。 （分数：1.00）A.2 5 3 4 6 1B.2 5 3 4 1 6C.2 6 5 4 1 3D.2 6 4 5 3 152.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，则可采用_的方法。（分数：1.00）A.分块B.顺序C.二分法D.基于属性53.若一个栈以向量 V1n)存储，且空栈的栈顶指针 top为 n+1，则将元素 x入栈的正确操作是_。（分数：1.00）A.top=top+1；Vtop=x；B.Vtop=x
27、；top=top+1；C.top=top-1；Vtop=x；D.Vtop=x；top=top-1；54.一棵二叉树中共有 70个叶子结点与 80个度为 1的结点，则该二叉树中的总结点数为 _。（分数：1.00）A.219B.221C.229D.23155.如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。_是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。（分数：1.00）A.冒泡排序B.希尔排序C.快速排序D.简单选择排序91设有 n个结点进行排序，不稳定排序是U (1) /U；快速排序的最坏时间是U (2) /U。（分
28、数：2.00）(1).(1)（分数：1.00）A.直接插入排序B.冒泡排序C.希尔排序D.归并排序(2).(2)（分数：1.00）A.O(nlog2B.O(n2)C.O(n2/2)D.O(56.对于长度为 11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第 5个元素需要与表中的_个元素进行比较操作(包括与第 5个元素的比较)。（分数：1.00）A.5B.4C.3D.257.若 in、out 分别表示入、出队操作，初始队列为空且元素 a、b、c 依次入队，则经过操作序列in、in、out、out、in、out 之后，得到的出队序列为_。（分数：1.00）A.cbaB.bacC.bcaD
29、.abe58.冒泡排序在最坏情况下的比较次数是_。（分数：1.00）A.n(n+1)/2B.nlog2nC.n(n-1)/2D.n/259.在程序的执行过程中，用_结构可以实现嵌套调用函数的正确返回。（分数：1.00）A.队列B.栈C.树D.图101正规式(1|3|5)(202)(c|de)表示的正规集合中元素数目为 (1) ， (2) 是该正规集合中的元素。（分数：2.00）(1).(1)（分数：1.00）A.6B.7C.8D.无穷(2).(2)（分数：1.00）A.135202cdeB.1202cC.302cdeD.52c60.设有二叉树如图 8-15所示。 （分数：1.00）A.ABCD
30、EFB.BDAECFC.ABDCEFD.DBEFCA61.对具有 n个元素的有序序列进行二分查找时，_。（分数：1.00）A.查找元素所需的比较次数与元素的位置无关B.查找序列中任何一个元素所需要的比较次数不超过 log2(n+1)C.元素位置越靠近序列后端，查找该元素所需的比较次数越少D.元素位置越靠近序列前端，查找该元素所需的比较次数越少98阅读下列说明、流程图和算法进行填空。下面的流程图用 N-S盒图形式描述了数组 A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向高下标端移动。当划分结束时，基准数定位于 Ai，并
31、且数组中下标小于 i的元素的值均小于基准数，下标大于 i的元素的值均大于基准数。设数组 A的下界为 low，上界为 high，数组中的元素互不相同。例如，对数组(4,2,8,3,6)，以 4为基准数的划分过程如图 8-34所示。算法说明：将上述划分的思想进一步用于被划分出的数组的两部分，就可以对整个数组实现递增排序。设函数 int p(int A,int low,int high)实现了上述流程图的划分过程并返回基准数在数组 A中的下标。递归函数 void sort(int A,int L,int H)的功能是实现数组 A中元素的递增排序。算法如下。void sort(int A，int L，
32、int H) if (LH) k=p(A,L,H)； /p()返回基准数在数组 A中的下标sort(U (4) /U)； /小于基准数的元素排序sort(U (5) /U)； /大于基准数的元素排序（分数：5.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_62.设某种二叉树有如下特点：结点的子树数目不是 2个，则是 0个。这样的一棵二叉树中有 m(m0)个子树为 0的结点时，该二叉树上的结点总数为_。（分数：1.00）A.2m+1B.2m-1C.2(m-1)D.2(m+1)63.在下列算法中，_算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置
33、上。（分数：1.00）A.堆排序B.冒泡排序C.插入排序D.快速排序64.若线性表采用链式存储结构，则适用的查找方法为_。（分数：1.00）A.随机查找B.散列查找C.二分查找D.顺序查找65.已知递归函数 f(n)的功能是计算 1+2+n，且 n1，应采用的代码段是_。（分数：1.00）A.if n1 then return 1 else return n+f(n-1)B.if n1 then return 1 else return n+f(n+1)C.if n1 then return 0 else return n+f(n-1)D.if n1 then return 0 else re
34、turn n+f(n+1)66.对矩阵压缩存储的主要目的是_。（分数：1.00）A.方便运算B.节省存储空间C.降低计算复杂度D.提高运算效率67.与单向链表相比，双向链表_。（分数：1.00）A.需要较少的存储空间B.遍历元素需要的时间较长C.较易于访问相邻结点D.较易于插入和删除元素68.在一棵非空二叉树中，叶子节点的总数比度为 2的节点总数多U (43) /U个。（分数：1.00）A.-1B.0C.1D.269.在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终位置上的排序算法是_。 （分数：1.00）A.冒泡排序B.基数排序C.快速排序D.归并排序70.下列数据结构中，能用二分
35、法进行查找的是_（分数：1.00）A.顺序存储的有序线性表B.线性链表C.二叉链表D.有序线性链表71._是线性结构的数据结构。（分数：1.00）A.列表B.高维数组C.双端队列D.二叉树72.字符串是一种线性表，其特殊性表现在_。（分数：1.00）A.它的数据元素是一个字符B.它可以链式存储C.它可以顺序存储D.它的数据元素可以是多个字符73.下列对于线性链表的描述中正确的是_。（分数：1.00）A.存储空间不一定连续，且各元素的存储顺序是任意的B.存储空间不一定连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存
36、储顺序是任意的74.在最坏情况下，下列排序方法中时间复杂度最小的是_。（分数：1.00）A.冒泡排序B.快速排序C.插入排序D.堆排序75.在数据结构中，结点(数据元素)及结点间的相互关系组成数据的逻辑结构。按逻辑结构的不同，数据结构通常可分为_两类。（分数：1.00）A.线性结构和非线性结构B.紧凑结构和稀疏结构C.动态结构和静态结构D.内部结构和外部结构76.链表不具备的特点是_。（分数：1.00）A.可随机访问任何一个元素B.插入、删除操作不需要移动元素C.无需事先估计存储空间大小D.所需存储空间与线性表长度成正比77.判断一个表达式中左右括号是否匹配，采用_实现较为方便。（分数：1.0
37、0）A.线性表的顺序存储B.队列C.线性表的链式存储D.栈78.某循环队列的容量为 M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-8 所示(M=8)，则队列中的元素数目为_(MOD 表示整除取余运算)。 （分数：1.00）A.rear-frontB.front-rearC.(rear-front+MODMD.(front-rear+MODM79.在链表结构中，采用_可以用最少的空间代价和最高的时间效率实现队列结构。（分数：1.00）A.仅设置尾指针的单向循环链表B.仅设置头指针的单向循环链表C.仅设置尾指针的双向链表D.仅设置头指针的双向链表80.从未排序的序列中依次取出一个元
38、素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为_。（分数：1.00）A.插入排序B.选择排序C.希尔排序D.归并排序81.采用邻接表表示一有向图，若图中某顶点的入度和出度分别为 d1和 d2，则该顶点对应的单链表的结点数为_。（分数：1.00）A.d1B.d2C.d1-d2D.d1+d282.二叉树的查找有深度优先和广度优先二类，深度优先包括_。（分数：1.00）A.前序遍历、后序遍历、中序遍历B.前序遍历、后序遍历、层次遍历C.前序遍历、中序遍历、层次遍历D.中序遍历、后序遍历、层次遍历83.在执行递归过程时，通常使用的数据结构是_。（分数：1.00）A.
39、堆栈(stacB.队列(queuC.图(grapD.树(tre84.PUSH和 POP命令常用于_操作。（分数：1.00）A.队列B.数组C.栈D.记录85.对图 8-30所示的二叉树进行后序遍历(左子树，右子树，根)的结果是_。 （分数：1.00）A.5 2 3 4 6 1B.5 2 3 4 1 6C.2 6 4 1 3 5D.2 5 6 4 3 186.数据的存储结构是指_。（分数：1.00）A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据87.下列对于线性链表的描述中正确的是_。（分数：1.00）A.存储空间不一定连续，且各
40、元素的存储顺序是任意的B.存储空间不一定连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的程序员-数据结构答案解析(总分：127.00，做题时间：90 分钟)一、B单选题/B(总题数：99，分数：127.00)60前序遍历序列与中序遍历序列相同的二叉树为U (1) /U，前序遍历序列与后序遍历序列相同的二叉树为U (2) /U。（分数：4.00）(1).(1)（分数：1.00）A.根结点无左子树的二叉树B.根结点无右子树的二叉树C.只有根结点的二叉树或非叶子结点只有左子树的二叉树D.只有根结点的二叉树
41、或非叶子结点只有右子树的二叉树 解析：(2).(2)（分数：1.00）A.非叶子结点只有左子树的二叉树B.只有根结点的二叉树 C.根结点无右子树的二叉树D.非叶子结点只有右子树的二叉树解析：解析 前序遍历的顺序是：根，左子树，右子树。中序遍历的顺序是：左子树，根，右子树。后序遍历的顺序是：左子树，右子树，根。如果前序遍历与中序遍历相同，那么，中序遍历访问的所有左子树访问为空。所以，如果只有根结点，满足此条件。另外，非叶子结点只有右子树，也满足此条件。所以，第 1问的正确答案为选项 D。如果前序遍历与后序遍历相同，那么，左右子树必然为空，所以，只有根结点。第 2问的正确答案为选项 B。(3).(
42、1)（分数：1.00）A.1B.2C.5 D.15解析：(4).(2) （分数：1.00）A.B.C.D. 解析：解析 对于完全无向图，其中任何 2个不同的结点都有一条邻接边；如果结点个数为 m，则完全无向图的边数为：m(m-1)/2对于本题，结点有 5个，那么，完全无向图的边数应当是：5(5-1)/2=101.在深度为 5的满二叉树中，结点的个数为_。（分数：1.00）A.32B.31 C.16D.15解析：解析 二叉树有如下性质：深度为 m的二叉树最多有 2的 m次方再减 1个结点，也就是 2m-1=25-1=32-1=31。由此可知答案为 B。2.若 push、pop 分别表示入栈、出栈
43、操作，初始栈为空且元素 1、2、3 依次进栈，则经过操作序列push、push、pop、pop、push、pop 之后，得到的出栈序列为_。（分数：1.00）A.321B.213 C.231D.123解析：解析 栈的运算特点是先进后出。对于元素 1、2、3，经过操作序列 push、push、pop、 pop、push、pop 的过程如图 8-3(ag)所示。 通过图可以看出，出栈序列为 213。本题正确答案为选项B。3.栈和队列的共同点是_。（分数：1.00）A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素 D.没有共同点解析：解析 栈和队列都是运算受限的线性表，只允许在表端点
44、处进行操作。本题正确答案为选项 C。4.对长度为 n的线性表进行顺序查找，在最坏情况下，所需要的比较次数为_。（分数：1.00）A.1og2nB.n/2C.n D.n+1解析：解析 在长度为 n的线性表中进行顺序查找，最坏情况下需要比较 n次。选项 C正确。5.下列叙述中正确的是_。（分数：1.00）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上三种说法都不对 解析：解析 数据之间的相互关系称为逻辑结构。存储结构是逻辑结构在存储器中的映像，
45、它包含数据元素的映像和关系的映像。存储结构在计算机中有两种，即顺序存储结构和链式存储结构。 顺序存储结构是把数据元素存储在一块连续地址空间的内存中。 链式存储结构是使用指针把相互直接关联的结点链接起来。 因此，这两种存储结构都是线性的。可见，逻辑结构和存储结构不是一一对应的。 因此，选项 A和选项 B的说法都是错误的。 无论数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构来实现存储。程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构的存储，比如二叉树。因此，选项 C的说法是错误的。6.对于长度为 n的线性表，在最坏情况下，下列各排序法所对应的比较次数中
