【计算机类职业资格】程序员-数据结构与算法及答案解析.doc

《【计算机类职业资格】程序员-数据结构与算法及答案解析.doc》由会员分享，可在线阅读，更多相关《【计算机类职业资格】程序员-数据结构与算法及答案解析.doc（25页珍藏版）》请在麦多课文档分享上搜索。

1、程序员-数据结构与算法及答案解析(总分：79.00，做题时间：90 分钟)一、B综合知识试题/B(总题数：33，分数：35.00)1.若二维数组 P15，08的首地址为 base，数组元素按行存储，且每个元素占用 1 个存储单元，则元素 P3，3在该数组空间的地址为_。（分数：1.00）A.base+13B.base+16C.base+18D.base+212.对图 8-22 所示的二叉树进行中序遍历(左子树、根、右子树)的结果是_。 （分数：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 13.在执行递归过程时，通常使用的数据结

2、构是_。（分数：1.00）A.堆栈(stack)B.队列(queue)C.图(graph)D.树(tree)4.广度优先遍历的含义是：从图中某个顶点 v 出发，在访问了 v 之后依次访问 v 的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有己被访问的顶点的邻接点都被访问到。_是图 8-21 的广度优先遍历序列。 （分数：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 35.若线性表(24，13，31，6，15，18，8)采用散列(

3、Hash)法进行存储和查找，设散列函数为 H(Key)=Key mod 11，则构造散列表时发生冲突的元素为_(其中的 mod 表示整除取余运算)。（分数：1.00）A.24 和 13B.6 和 15C.6 和 24D.18 和 86.采用一维数组 S 存储一个 n 阶对称矩阵 A 的下三角部分(按行存放，包括主对角线)，设元素 Aij存放在 Sk中(i、j、k 均从 1 开始取值)，且 S1=A11，则 k 与 i、j 的对应关系是_。例如，元素 A32存在 S5中。（分数：1.00）A.B.C.D.7.数据结构中的树最适合用来表示_的情况。（分数：1.00）A.数据元素有序B.数据元素之间

4、具有多对多关系C.数据元素无序D.数据元素之间具有一对多关系8.若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于 1，则该二叉树的_。（分数：1.00）A.只有根节点无左予树B.只有根节点无右子树C.非叶子节点只有左子树D.非叶子节点只有右子树9.线性表采用顺序存储结构，若表长为 m，且在任何一个合法插入位置上进行插入操作的概率相同，则插入一个元素平均移动_个元素。（分数：1.00）A.m-1B.m/2C.m/2+1D.m10.二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：特其左子树非空，则左子树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点

5、的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行_遍历，可得到一个节点元素的递增序列。（分数：1.00）A.前序(根、左、右)B.中序(左、根、右)C.后序(左、右、根)D.层序(从树根开始，按层次)若将图 8-23(a)所示的无向图改为完全图，则还需要增加U (24) /U条边；图(b)的邻接矩阵表示为U (25) /U(行列均以 A、B、C、D、E 为序)。（分数：2.00）A.1B.2C.5D.15A.B.C.D.11.数组 A-55，08按列存储。若第一个元素的首地址为 100，且每个元素占用 4 个存储单元，则元素 A2，3的存储地址为_。（分数：1.

6、00）A.244B.260C.364D.30012.某循环队列的容量为 M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-18 所示(M=8)，则队列中的元素数目为_(MOD 表示整除取余运算)。 （分数：1.00）A.rear-frontB.front-rearC.(rear-front+M)MOD MD.(front-rear+M)MOD M13.用二分法来检索数据，最确切的说法是_。（分数：1.00）A.仅当数据随机排列时，才能正确地检索数据B.仅当数据有序排列时，才能正确地检索数据C.仅当数据量较大时，才能有效地检索数据D.仅当数据量较小时，才能有效地检索数据14.设数组

7、a16，09的元素以行为主序存放，每个元素占用一个存储单元，则数组元素 a3，3的地址为_。（分数：1.00）A.a+23B.a+27C.a+39D.a+3515.与单向链表相比，双向链表_。（分数：1.00）A.需要较少的存储空间B.遍历元素需要的时问较短C.较易于访问相邻节点D.较易于插入和删除元素16.对如图 8-24 所示的二叉树进行后序遍历(左子树、右子树、根节点)的结果是_。 （分数：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 117.采用哈希(或散列)技术构造查找表时，需要考虑冲突(碰撞)的处理，冲突是指_。（分

8、数：1.00）A.关键字相同的记录被映射到不同的哈希地址B.关键字依次被映射到编号连续的哈希地址C.关键字不同的记录被映射到同一个哈希地址D.关键字的数目超过哈希地址的数目满二叉树的特点是每层上的节点数都达到最大值，因此对于高度为 h(h1)的满二叉树，其节点总数为U (18) /U。对非空满二叉树，由根节点开始，按照先根后子树、先左子树后右子树的次序，从 1，2，3，依次编号，则对于树中编号为 i 的非叶子节点，其右子树的编号为U (19) /U(高度为3 的满二叉树如图 8-20 所示)。（分数：2.00）A.2hB.2h-1C.2h-1D.2h-1+1A.2iB.2i-1C.2i+1D.

9、2i+218.设初始栈为空，s 表示入栈操作，x 表示出栈操作，则_是合法的操作序列。（分数：1.00）A.sxxsssxxxB.xxssxxssC.sxsxssxxD.xssssxxx19.由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根节点插入，此后对于任意关键字，若小于根节点的关键字，则插入左子树中，若大于根节点的关键字，则插入右子树中，且左、右子树均为二叉排序树)，该二叉排序树的高度(层数)为_。（分数：1.00）A.6B.5C.4D.320.两个递增序列 A 和 B 的长度分别为 m 和 n(mn)，将两者归并为一个长度为 m+n 的递增

10、序列时，_，归并过程中元素的比较次数最少。（分数：1.00）A.当 A 的最大元素大于 B 的最大元素时B.当 A 的最大元素小于 B 的最小元素时C.当 A 的最小元素大于 B 的最小元素时D.当 A 的最小元素小于 B 的最大元素时21.对于 n 个元素的关键字序列k 1，k 2，k n，若将其按次序对应到一棵具有 n 个节点的完全二叉树上，使得任意节点都不大于其孩子节点(若存在孩子节点)，则称其为小顶堆。根据以上定义，_是小顶堆。（分数：1.00）A.B.C.D.22.栈的运算特点是后进先出。元素 a、b、c、d 依次入栈，则不能得到的出栈序列是_。（分数：1.00）A.a b c dB

11、.c a b dC.d c b aD.b c d a23.对连通图进行遍历前设置所有顶点的访问标志为 false(未被访问)，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true(已访问)，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v 的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。_是图 8-19 的深度优先遍历序列。 （分数：1.00）A.1 2 3 4 6 5B.1 2 6 3 4 5C.

12、1 6 2 5 4 3D.1 2 3 4 5 624.对具有 n 个元素的顺序表(采用顺序存储的线性表)进行_操作，其耗时与 n 的大小无关。（分数：1.00）A.在第 i(1in)个元素之后插入一个新元素B.删除第 i(1in)个元素C.对顺序表中的元素进行排序D.访问第 i(1in)个元素的前驱和后继25.如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。_是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。（分数：1.00）A.冒泡排序B.希尔排序C.快速排序D.简单选择排序26.n 个元素依次全部进入栈后，再陆续出栈

13、并经过一个队列输出。那么，_。（分数：1.00）A.元素的出队次序与进栈次序相同B.元素的出队次序与进栈次序相反C.元素的进栈次序与进队次序相同D.元素的出栈次序与出队次序相反27.对于长度为 11 的顺序存储的有序表，若采用折半查找(向下取整)，则找到第 5 个元素需要与表中的_个元素进行比较操作(包括与第 5 个元素的比较)。（分数：1.00）A.5B.4C.3D.228.若一个栈以向量 V1n存储，且空栈的栈顶指针 top 为 n+1，则将元素 x 入栈的正确操作是_。（分数：1.00）A.top=top+1；Vtop=x；B.Vtop=x；top=top+1；C.top=top-1；V

14、top=x；D.Vtop=x；top=top-1；29.若原始数据序列(23，4，45，67，12，8，19，7)采用直接插入排序法(顺序地将每个元素插入到它之前的适当位置)排序，则进行完第 4 趟后的排序结果是_。（分数：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，730.若字符串 s 的长度为 n(n1)且其中的字符互不相同，则 s 的长度为 2 的子串有_个。（分数：1.00）A.nB.n-1C.n-2D.231.在任意一棵非空的二叉树中，终端节点(

15、叶子)的数目总是比具有两个孩子的非终端节点的数目_。（分数：1.00）A.多 0 个B.多 1 个C.多 2 个D.多 3 个二、B案例分析试题/B(总题数：8，分数：44.00)B试题一/B阅读以下说明和 C 语言函数，回答问题。说明函数 sort(NODE*head)的功能是：用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻节点中的元素，若较小的元素在后面，则交换这两个节点中的元素值。其中，head 指向链表的头节点。排序时，为了避免每趟都扫描到链表的尾节点，设置一个指针 endptr，使其指向下趟扫描需要到达的最后一个节点。例如，对于图 8-25(a)所示的链表进行一趟冒泡排序后

16、，得到图 8-25(b)所示的链表。（分数：5.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B试题二/B阅读以下说明和 C 程序，回答问题。说明下面的程序用 Dole Rob 算法生成 N 阶(N 为奇数)魔方阵(各行、列、对角线数字之和相等)。该算法的过程为：从 1 开始，按如下方法依次插入各自然数，直到 N2 为止。在第一行的正中插入 1。新位置应当处于最近插入位置的右上方，若该位置已超出方阵的上边界，则新位置取应选列的最下一个位置；若超出右边界，则新位置取应选行的最左一个位置。若最近插入的元素是 N 的整数倍，则选同列的下一行位置

17、为新位置。例如，3 阶魔方阵如下所示：8 1 63 5 74 9 2C 程序#includestdio.h#includestdlib.h#define SIZE 50main( )int row, col, n, value; int aSIZE+1SIZE+1; /*不使用下标为 0 的元素*/printf(“请输入要输出魔方阵的阶数 n(奇数, %d):n=“, SIZE); scanf(“%d“, if(!(n%2) | n1 | U(1) /U)printf(“输入数据有误!/n“); exit(0); row=1; col=(n+1)/2; value=1; while(value

18、=U (2) /U) arowcol=value; /*计算下一位置*/if(value%n!=0)row-; U(3) /U; if(row1)row=n; if(coln)U (4) /U; else row+; value=U (5) /U; printf(“/n%d 阶魔方阵如下所示：/n/n“, n); for(row=1; row=n; row+)for(col=1; col=n; col+)printf(“%5d“, arowcol); printf(“/n“); （分数：5.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B

19、试题三/B阅读以下说明和 C 函数，回答问题。说明计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式“46+5*(120-37)”的后缀表达式形式为“46 5 120 37- * +”。计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式“46 5 120 37 - * +”的汁算过程如下。依次将 46、5、120、37 压入栈中。遇到“-”，取出 37、120，计算 120-37=83，将其压入栈中。遇到“*”，取出 83、5，计算 583

20、=415，将其压入栈中。遇到“+”，取出 415、46，计算 46+415=461，将其压入栈中。表达式结束，则计算过程完成。函数 computing(char expt，int *result)的功能是基于栈计算后缀形式的表达式(以串形式存入字符数组 expr)的值，并通过参数 result 返回该值。函数的返回值为-1/0，分别表示表达式有/无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含加(“+”)、减(“-”)、乘(“*”)、除(“/”)。函数 computing 中所用栈的基本操作的函数原型说明如下。void InitStack(STACK

21、*s)：初始化栈。void Push(STACK *s, int e)：将一个整数压栈，栈中元素数目增 1。void Pop(STACK *s)：栈顶元素出栈，栈中元素数目减 1。int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。int IsEmpty(STACK s)：若 s 是空栈，则返回 1；否则返回 0。C 函数int computing(char expr, int *result)STACK s; int tnum, a, b; char *ptr; InitStack( ptr=expr; pstr /*字符指针指向后缀表达式串的第一个字符*/while

22、 (*ptr!=/0) if(*ptr= ) /*当前字符是空格*/U (1) /U; /*字符指针指向下一字符*/continue; elseif (isdigit(*ptr) /*当前字符是数字，则将该数字开始的数字串转换为数值*/tnum=U (2) /U; while (*ptr=0 ptr+; push(U (4) /U); else /*当前字符是运算符或其他符号*/if (*ptr=+|*ptr=-|*ptr=*|*ptr=/)if(!IsEmpty(S)a=Top(s); Pop( /*取运算符的第二个运算数*/if(!IsEmpty(S)b=Top(s); Pop( /*取运

23、算符的第一个运算数*/else return-1; else return -1; switch (*ptr) case+: Push( break; case-: Push( break; case+: Push( break; case/: Push( break; elsereturn -1; ptr+; /*字符指针指向下一字符*/*while*/if (IsEmpty(s) return -1; else U (5) /U=Top(s); Pop( /*取运算结果*/if (!IsEmpty(s) return -1; return 0; （分数：5.00）(1).（分数：1.00）

24、填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B试题四/B阅渎以下说叫和 C 函数，回答问题。说明已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组 Ht 中。节点结构及数组 Ht的定义如下：#define MAXLEAFNUM 30Struct nodechar ch; char *pstr; int parent; int lchild, rchiid; ; Struct node Ht2 *MAXLEAFNUM; 该二叉树的 n 个叶子节点存储在下标为 1n 的 Ht 数组元素中。例如，某二叉树如图 8-26 所示，其存储结构如图 8-27 所示

25、，其中，与叶子节点 a 对应的数组元素下标为 1，a 的父节点存储在 Ht5，表示为Ht1.parent=5。Ht7.parent=0 表示 7 号节点是树根，Ht7.lchild=3、Ht7.rchild=6 分别表示 7号节点的左孩子是 3 号节点、右孩子是 6 号节点。如果用“0”或“1”分别标识二叉树的左分支和右分支如图 8-26 所示，从根节点开始到叶子节点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、1 序列，称之为对应叶子节点的编码。例如，图 8-26 中 a、b、c、d 的编码分别是 100、101、0、11。函数 LeafCode(Ht，n)的功能是：求解存储在

26、 Ht 中的二叉树中所有叶子节点(n 个)的编码，叶子节点存储在 Ht1Htn中，求出的编码存储区由对应的数组元素 pstr 域指示。函数 LeafCode 从叶子到根逆向求叶子节点的编码。例如，对图 8-26 中叶子节点 a 求编码的过程如图 8-28 所示。（分数：5.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B试题五/B阅读以下说明和 C 语言函数，回答问题。说明已知包含头节点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。处

27、理过程中，当元素重复出现时，保留元素第一次出现所在的节点。图 8-29(a)、(b)是经函数 compress( )处理前后的链表结构示例图。（分数：5.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B试题六/B阅读以下说明和流程图，填补流程图中的空缺。说明下面流程图的功能是：在已知字符串 A 中查找特定字符串 B，如果存在，则输出 B 串首字符在 A 串中的位置，否则输出-1。设串 A 由 n 个字符 A(0)、A(1)、A(n-1)组成，串 B 由 m 个字符 B(0)、B(1)、B(m-1)组成，其中 nm0。在串 A 中查找串 B

28、 的基本算法如下：从串 A 的首字符 A(0)开始，取子串A(0)A(1)i(m-1)与串 B 比较；若不同，则再取子串 A(1)A(2)A(m)与串 B 比较，以此类推。例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出 3)，不存在字符子串“RFD”(输出-1)。在流程图中，i 用于访问串 A 中的字符(i=0，1，n-1)，j 用于访问串 B 中的字符(j=0，1，m-1)。在比较 A(i)A(i+1)A(i+m-1)与 B(0)B(1)B(m-1)时，需要对 A(i)与 B(0)、A(i+1)与 B(1)、A(i+j)与 B(j)、逐对字符进行比较。若发现不同，则需要取下一

29、个子串进行比较，以此类推。流程图本题流程图如图 8-30 所示。（分数：5.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B试题七/B阅读以下说明和流程图，填补流程图中的空缺。说明假设数组 A 中的各元素 A(1)，A(2)，A(M)已经按从小到大排序(M1)；数组 B 中的各元素 B(1)，B(2)，B(N)也已经按从小到大排序(N1)。执行下面的流程图后，可以将数组 A 与数组 B 中所有的元素全都存入数组 C 中，且按从小到大排序(注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组 A 中有元素：2，5，6，7，9；数组 B

30、 中有元素 2，3，4，7；则数组 C 中将有元素：2，2，3，4，5，6，7，7，9。流程图本题流程图如图 8-31 所示。（分数：9.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_B试题八/B阅读以下说明和流程图，填补流程图中的空缺。说明某单位动态收集的数据中常包含重复的数据，所以需要进行处理，使得重复的数据仅出现一次。下面流程图的功能是：在 n(n1)个数据 D1，D 2，D n中，选出其中所有不重复的 k 个数据，置于原来前 k 个数据的位置上。该流程图的算法如下：第 1 个

31、数据必然被选出，然后从第 2 个数据开始，逐个考察其余的数据。假设D1，D 2，D m(m1)是已经选出的、不重复的数据，则对于数据 Di(min)，将其依次与 Dm，D m-1，D 1进行比较，若没有发现与之相同者，则 Di被选出并置于 Dm+1的位置上；否则对 Di不做处理。例如，如下 10 个数据：5，2，2，7，4，4，7，1，9，1 (n=10)经过上述算法处理后的结果为：5，2，7，4，1，9 (k=6)流程图本题流程图如图 8-32 所示。（分数：5.00）(1).（分数：1.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_程序员-数据结构与算法答案解

32、析(总分：79.00，做题时间：90 分钟)一、B综合知识试题/B(总题数：33，分数：35.00)1.若二维数组 P15，08的首地址为 base，数组元素按行存储，且每个元素占用 1 个存储单元，则元素 P3，3在该数组空间的地址为_。（分数：1.00）A.base+13B.base+16C.base+18D.base+21 解析：解析 数组空间首地址为 base，所以，元素 P1，0的存储地址为 base，按行存储时，P3，3之前存储了 29+3 个元素，因此 P3，3在该数组空间的地址为 base+21。2.对图 8-22 所示的二叉树进行中序遍历(左子树、根、右子树)的结果是_。 （

33、分数：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 1 解析：解析 中序遍历的操作过程是：若二叉树为空，则进行空操作；否则先选中序遍历根的左子树，然后访问根节点，最后中序遍历根的右子树。因此，本题中的二叉树进行中序遍历，可以得到序列为 2 6 4 5 3 1。3.在执行递归过程时，通常使用的数据结构是_。（分数：1.00）A.堆栈(stack) B.队列(queue)C.图(graph)D.树(tree)解析：解析 在执行递归过程时，通常使用的数据结构是堆栈，要求先调用后返回。4.广度优先遍历的含义是：从图中某个顶点 v 出发，

34、在访问了 v 之后依次访问 v 的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有己被访问的顶点的邻接点都被访问到。_是图 8-21 的广度优先遍历序列。 （分数：1.00）A.1 2 6 3 4 5 B.1 2 3 4 5 6C.1 6 5 2 3 4D.1 6 4 5 2 3解析：解析 根据题目描述，对题中图进行广度优先遍历时，先访问顶点 1，由于 2 和 6 是顶点 1 的邻接顶点，因此接下来应访问顶点 2 或顶点 6，若先访问顶点 2，此时的访问序列为 1 2 6；反之，访问序列则为 1

35、 6 2，然后访问顶点 2、6(或 6、2)的邻接顶点。因此，最后的遍历序列为 1 2 6 3 4 5、1 2 6 3 5 4、1 6 2 5 4 3 或 1 6 2 4 5 3。5.若线性表(24，13，31，6，15，18，8)采用散列(Hash)法进行存储和查找，设散列函数为 H(Key)=Key mod 11，则构造散列表时发生冲突的元素为_(其中的 mod 表示整除取余运算)。（分数：1.00）A.24 和 13 B.6 和 15C.6 和 24D.18 和 8解析：解析 根据散列函数可得 H(24)=H(13)=2，所以 24 和 12 两个元素冲突。6.采用一维数组 S 存储一个

36、 n 阶对称矩阵 A 的下三角部分(按行存放，包括主对角线)，设元素 Aij存放在 Sk中(i、j、k 均从 1 开始取值)，且 S1=A11，则 k 与 i、j 的对应关系是_。例如，元素 A32存在 S5中。（分数：1.00）A.B.C.D. 解析：解析 本题考查特殊矩阵的压缩存储。对称矩阵下三角的元素按行存储时，对于元素 Aij，其前面的元素数目为 1+2+i-1+j-1=i(i-1)/2+j-1，因此元素 Aij存储在 Si(i-1)/2+j中。7.数据结构中的树最适合用来表示_的情况。（分数：1.00）A.数据元素有序B.数据元素之间具有多对多关系C.数据元素无序D.数据元素之间具有

37、一对多关系 解析：解析 本题考查数据结构中树的基本知识。数据结构中的树最适合用来表示数据元素之间具有一对多关系的情况。8.若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于 1，则该二叉树的_。（分数：1.00）A.只有根节点无左予树B.只有根节点无右子树C.非叶子节点只有左子树D.非叶子节点只有右子树 解析：解析 若二叉树的前序遍历序列与中序遍历序列相同，说明二叉树的根节点没有左子树，以此类推，二叉树所有节点都没有左子树，非叶子节点只有右子树。9.线性表采用顺序存储结构，若表长为 m，且在任何一个合法插入位置上进行插入操作的概率相同，则插入一个元素平均移动_个元素。（分数：1.00）A

38、.m-1B.m/2 C.m/2+1D.m解析：解析 线性表采用顺序存储结构，若表长为 m，且在任何一个合法插入位置上进行插入操作的概率相同，则插入一个元素平均移动 m/2 个元素。10.二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：特其左子树非空，则左子树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行_遍历，可得到一个节点元素的递增序列。（分数：1.00）A.前序(根、左、右)B.中序(左、根、右)C.后序(左、右、根)D.层序(从树根开始，按层次) 解析：解析 中序遍历

39、二叉树的过程为：若二叉树为空，则进行空操作；否则中序遍历根的左子树：访问根节点；中序遍历根的右子树。显然，对一棵非空的二叉排序树进行中序遍历，可得到一个节点元素的递增序列。若将图 8-23(a)所示的无向图改为完全图，则还需要增加U (24) /U条边；图(b)的邻接矩阵表示为U (25) /U(行列均以 A、B、C、D、E 为序)。（分数：2.00）A.1B.2C.5 D.15解析：A.B.C.D. 解析：解析 本题考查的是图的概念及存储结构。含有 n 个顶点的无向完全图共有 n(n-1)/2 条边。图的矩阵表示法利用一个矩阵来表示图中顶点之间的关系。根据邻接矩阵的特点可知 D 选项符合要求

40、。11.数组 A-55，08按列存储。若第一个元素的首地址为 100，且每个元素占用 4 个存储单元，则元素 A2，3的存储地址为_。（分数：1.00）A.244B.260 C.364D.300解析：解析 数组按列存储时，存储在 A2，3之前的元素个数为 113+7，因此，其存储地址为100+404=260。12.某循环队列的容量为 M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-18 所示(M=8)，则队列中的元素数目为_(MOD 表示整除取余运算)。 （分数：1.00）A.rear-frontB.front-rearC.(rear-front+M)MOD M D.(front

41、-rear+M)MOD M解析：解析 队列容量为 M 时，队头指针 front 和队尾指针 rear 的值在 0M-1 之间循环，当rearfront 时，元素数目为 rear-front；当 rearfront 时，元素数目为 rear-front+M。所以，队列中元素数目为(rear-front+M)MOD M。13.用二分法来检索数据，最确切的说法是_。（分数：1.00）A.仅当数据随机排列时，才能正确地检索数据B.仅当数据有序排列时，才能正确地检索数据 C.仅当数据量较大时，才能有效地检索数据D.仅当数据量较小时，才能有效地检索数据解析：解析 对于二分查找方法，只有元素进行有序排列时，

42、才能正确地进行查找。14.设数组 a16，09的元素以行为主序存放，每个元素占用一个存储单元，则数组元素 a3，3的地址为_。（分数：1.00）A.a+23 B.a+27C.a+39D.a+35解析：解析 以行为主序存储，元素 a3，3之前有 23 个元素，所以其相对于数组起始地址的偏移量为23，地址为 a+23。15.与单向链表相比，双向链表_。（分数：1.00）A.需要较少的存储空间B.遍历元素需要的时问较短C.较易于访问相邻节点 D.较易于插入和删除元素解析：解析 本题考查链表存储结构的基本特点。在单向链表中只能沿一个方向进行访问节点，而在双向链表中既可以向前遍历，也可以向后遍历。因此，

43、双向链表较易于访问相邻节点。16.对如图 8-24 所示的二叉树进行后序遍历(左子树、右子树、根节点)的结果是_。 （分数：1.00）A.5 2 3 4 6 1B.5 2 3 4 1 6C.2 6 4 1 3 5 D.2 5 6 4 3 1解析：解析 本题考查的是二叉树的遍历运算。后序遍历是指先遍历左子树，再遍历右子树，最后访问根节点。所以，本题后序遍历结果应为 264135。17.采用哈希(或散列)技术构造查找表时，需要考虑冲突(碰撞)的处理，冲突是指_。（分数：1.00）A.关键字相同的记录被映射到不同的哈希地址B.关键字依次被映射到编号连续的哈希地址C.关键字不同的记录被映射到同一个哈希

44、地址 D.关键字的数目超过哈希地址的数目解析：解析 采用哈希(或散列)技术构造查找表时，需要考虑冲突(碰撞)的处理，冲突是指关键字不同的记录被映射到同一个哈希地址。满二叉树的特点是每层上的节点数都达到最大值，因此对于高度为 h(h1)的满二叉树，其节点总数为U (18) /U。对非空满二叉树，由根节点开始，按照先根后子树、先左子树后右子树的次序，从 1，2，3，依次编号，则对于树中编号为 i 的非叶子节点，其右子树的编号为U (19) /U(高度为3 的满二叉树如图 8-20 所示)。（分数：2.00）A.2hB.2h-1C.2h-1 D.2h-1+1解析：A.2iB.2i-1C.2i+1 D.2i+2解析：解析 本题考查数据结构中二叉树的基本知识。满二叉树的第 1 层(树根)有 1 个节点，第二层有2 个节点，第三层有 4 个节点，以此类推，第 h 层有 2h-1 个节点。总节点数为 20+21+22+2h-1=2h-1。依题意，显然对非空满二叉树中的节点 i 的左子树编号为 2i，右子树编号为 2i+1。18.设初始栈为空，s 表示入栈操作，x 表示出栈操作，则_是合法的操作序列。（分数：1.00）A.sxxsss