1、程序员-数据结构与算法(一)及答案解析(总分：79.00，做题时间：90 分钟)一、综合知识试题(总题数：33，分数：35.00)1.对具有 n 个元素的顺序表(采用顺序存储的线性表)进行_操作，其耗时与 n 的大小无关。A在第 i(1in)个元素之后插入一个新元素B删除第 i(1in)个元素C对顺序表中的元素进行排序D访问第 i(1in)个元素的前驱和后继（分数：1.00）A.B.C.D.2.若字符串 s 的长度为 n(n1)且其中的字符互不相同，则 s 的长度为 2 的子串有_个。An Bn-1 Cn-2 D2（分数：1.00）A.B.C.D.3.栈的运算特点是后进先出。元素 a、b、c、
2、d 依次入栈，则不能得到的出栈序列是_。Aa b c d Bc a b d Cd c b a Db c d a（分数：1.00）A.B.C.D.4.某循环队列的容量为 M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-18 所示(M=8)，则队列中的元素数目为_(MOD 表示整除取余运算)。（分数：1.00）A.B.C.D.5.设初始栈为空，s 表示入栈操作，x 表示出栈操作，则_是合法的操作序列。Asxxsssxxx Bxxssxxss Csxsxssxx Dxssssxxx（分数：1.00）A.B.C.D.6.n 个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，_。
3、A元素的出队次序与进栈次序相同B元素的出队次序与进栈次序相反C元素的进栈次序与进队次序相同D元素的出栈次序与出队次序相反（分数：1.00）A.B.C.D.7.与单向链表相比，双向链表_。A需要较少的存储空间 B遍历元素需要的时问较短C较易于访问相邻节点 D较易于插入和删除元素（分数：1.00）A.B.C.D.8.若一个栈以向量 V1n存储，且空栈的栈顶指针 top 为 n+1，则将元素 x 入栈的正确操作是_。Atop=top+1；Vtop=x； BVtop=x；top=top+1；Ctop=top-1；Vtop=x； DVtop=x；top=top-1；（分数：1.00）A.B.C.D.9.
4、在执行递归过程时，通常使用的数据结构是_。A堆栈(stack) B队列(queue) C图(graph) D树(tree)（分数：1.00）A.B.C.D.10.设数组 a16，09的元素以行为主序存放，每个元素占用一个存储单元，则数组元素 a3，3的地址为_。Aa+23 Ba+27 Ca+39 Da+35（分数：1.00）A.B.C.D.11.若二维数组 P15，08的首地址为 base，数组元素按行存储，且每个元素占用 1 个存储单元，则元素 P3，3在该数组空间的地址为_。Abase+13 Bbase+16 Cbase+18 Dbase+21（分数：1.00）A.B.C.D.12.采用一
5、维数组 S 存储一个 n 阶对称矩阵 A 的下三角部分(按行存放，包括主对角线)，设元素 Aij存放在 Sk中(i、j、k 均从 1 开始取值)，且 S1=A11，则 k 与 i、j 的对应关系是_。例如，元素 A32存在 S5中。A BC D （分数：1.00）A.B.C.D.13.数组 A-55，08按列存储。若第一个元素的首地址为 100，且每个元素占用 4 个存储单元，则元素 A2，3的存储地址为_。A244 B260 C364 D300（分数：1.00）A.B.C.D.14.若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于 1，则该二叉树的_。A只有根节点无左予树 B只有根节
6、点无右子树C非叶子节点只有左子树 D非叶子节点只有右子树（分数：1.00）A.B.C.D.15.由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根节点插入，此后对于任意关键字，若小于根节点的关键字，则插入左子树中，若大于根节点的关键字，则插入右子树中，且左、右子树均为二叉排序树)，该二叉排序树的高度(层数)为_。A6 B5 C4 D3（分数：1.00）A.B.C.D.16.对连通图进行遍历前设置所有顶点的访问标志为 false(未被访问)，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问
7、 v 并设置其访问标志为 true(已访问)，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v 的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。_是图 8-19 的深度优先遍历序列。（分数：1.00）A.B.C.D.17.在任意一棵非空的二叉树中，终端节点(叶子)的数目总是比具有两个孩子的非终端节点的数目_。A多 0 个 B多 1 个 C多 2 个 D多 3 个（分数：1.00）A.B.C.D.满二叉树的特点是每层上的节点数都达到最大值，因此对于高度为 h(h1)的满二叉树，其节点总数为 (
8、18) 。对非空满二叉树，由根节点开始，按照先根后子树、先左子树后右子树的次序，从 1，2，3，依次编号，则对于树中编号为 i 的非叶子节点，其右子树的编号为 (19) (高度为 3 的满二叉树如图 8-20所示)。（分数：2.00）(1).A2h B2h-1 C2h-1 D2h-1+1（分数：1.00）A.B.C.D.(2).A2i B2i-1 C2i+1 D2i+2（分数：1.00）A.B.C.D.18.数据结构中的树最适合用来表示_的情况。A数据元素有序 B数据元素之间具有多对多关系C数据元素无序 D数据元素之间具有一对多关系（分数：1.00）A.B.C.D.19.二叉排序树或者是一棵空
9、树，或者是具有如下性质的二叉树：特其左子树非空，则左子树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行_遍历，可得到一个节点元素的递增序列。A前序(根、左、右) B中序(左、根、右)C后序(左、右、根) D层序(从树根开始，按层次)（分数：1.00）A.B.C.D.20.广度优先遍历的含义是：从图中某个顶点 v 出发，在访问了 v 之后依次访问 v 的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被
10、访问，直至图中所有己被访问的顶点的邻接点都被访问到。_是图 8-21 的广度优先遍历序列。（分数：1.00）A.B.C.D.21.对图 8-22 所示的二叉树进行中序遍历(左子树、根、右子树)的结果是_。（分数：1.00）A.B.C.D.若将图 8-23(a)所示的无向图改为完全图，则还需要增加 (24) 条边；图(b)的邻接矩阵表示为 (25) (行列均以 A、B、C、D、E 为序)。（分数：2.00）(1).A1 B2 C5 D15（分数：1.00）A.B.C.D.(2).ABCD （分数：1.00）A.B.C.D.22.对如图 8-24 所示的二叉树进行后序遍历(左子树、右子树、根节点)
11、的结果是_。（分数：1.00）A.B.C.D.23.若线性表(24，13，31，6，15，18，8)采用散列(Hash)法进行存储和查找，设散列函数为 H(Key)=Key mod 11，则构造散列表时发生冲突的元素为_(其中的 mod 表示整除取余运算)。A24 和 13 B6 和 15 C6 和 24 D18 和 8（分数：1.00）A.B.C.D.24.线性表采用顺序存储结构，若表长为 m，且在任何一个合法插入位置上进行插入操作的概率相同，则插入一个元素平均移动_个元素。Am-1 Bm/2 Cm/2+1 Dm（分数：1.00）A.B.C.D.25.两个递增序列 A 和 B 的长度分别为
12、m 和 n(mn)，将两者归并为一个长度为 m+n 的递增序列时，_，归并过程中元素的比较次数最少。A当 A 的最大元素大于 B 的最大元素时B当 A 的最大元素小于 B 的最小元素时C当 A 的最小元素大于 B 的最小元素时D当 A 的最小元素小于 B 的最大元素时（分数：1.00）A.B.C.D.26.对于 n 个元素的关键字序列 k1，k 2，k n，若将其按次序对应到一棵具有 n 个节点的完全二叉树上，使得任意节点都不大于其孩子节点(若存在孩子节点)，则称其为小顶堆。根据以上定义，_是小顶堆。A B C D （分数：1.00）A.B.C.D.27.采用哈希(或散列)技术构造查找表时，需
13、要考虑冲突(碰撞)的处理，冲突是指_。A关键字相同的记录被映射到不同的哈希地址B关键字依次被映射到编号连续的哈希地址C关键字不同的记录被映射到同一个哈希地址D关键字的数目超过哈希地址的数目（分数：1.00）A.B.C.D.28.对于长度为 11 的顺序存储的有序表，若采用折半查找(向下取整)，则找到第 5 个元素需要与表中的_个元素进行比较操作(包括与第 5 个元素的比较)。A5 B4 C3 D2（分数：1.00）A.B.C.D.29.如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。_是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素
14、并不进行交换。A冒泡排序 B希尔排序 C快速排序 D简单选择排序（分数：1.00）A.B.C.D.30.用二分法来检索数据，最确切的说法是_。A仅当数据随机排列时，才能正确地检索数据B仅当数据有序排列时，才能正确地检索数据C仅当数据量较大时，才能有效地检索数据D仅当数据量较小时，才能有效地检索数据（分数：1.00）A.B.C.D.31.若原始数据序列(23，4，45，67，12，8，19，7)采用直接插入排序法(顺序地将每个元素插入到它之前的适当位置)排序，则进行完第 4 趟后的排序结果是_。A4，8，45，23，67，12，19，7B4，7，8，12，23，45，67，19C4，12，8，1
15、9，7，23，45，67D4，12，23，45，67，8，19，7（分数：1.00）A.B.C.D.二、案例分析试题(总题数：0，分数：0.00)三、试题一(总题数：1，分数：5.00)说明函数 sort(NODE*head)的功能是：用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻节点中的元素，若较小的元素在后面，则交换这两个节点中的元素值。其中，head 指向链表的头节点。排序时，为了避免每趟都扫描到链表的尾节点，设置一个指针 endptr，使其指向下趟扫描需要到达的最后一个节点。例如，对于图 8-25(a)所示的链表进行一趟冒泡排序后，得到图 8-25(b)所示的链表。（分数：5
16、.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_四、试题二(总题数：1，分数：5.00)说明下面的程序用 Dole Rob 算法生成 N 阶(N 为奇数)魔方阵(各行、列、对角线数字之和相等)。该算法的过程为：从 1 开始，按如下方法依次插入各自然数，直到 N2 为止。在第一行的正中插入 1。新位置应当处于最近插入位置的右上方，若该位置已超出方阵的上边界，则新位置取应选列的最下一个位置；若超出右边界，则新位置取应选行的最左一个位置。若最近插入的元素是 N 的整数倍，则选同列的下一行位置为新位置。例如，3 阶魔方阵如下所示：8 1 63 5 74 9 2C 程序#i
17、ncludestdio.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 | (1) )printf(“输入数据有误!/n“); exit(0); row=1; col=(n+1)/2; value=1; while(value= (2) ) arowcol=value; /*计算下一位置*/if(value%n
18、!=0)row-; (3) ; if(row1)row=n; if(coln) (4) ; else row+; value= (5) ; 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:_填空项 1:_填空项 1:_填空项 1:_五、试题三(总题数：1，分数：5.00)说明计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式“46+5*(120-37)”
19、的后缀表达式形式为“46 5 120 37- * +”。计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式“46 5 120 37 - * +”的汁算过程如下。依次将 46、5、120、37 压入栈中。遇到“-”，取出 37、120，计算 120-37=83，将其压入栈中。遇到“*”，取出 83、5，计算 583=415，将其压入栈中。遇到“+”，取出 415、46，计算 46+415=461，将其压入栈中。表达式结束，则计算过程完成。函数 comput
20、ing(char expt，int *result)的功能是基于栈计算后缀形式的表达式(以串形式存入字符数组 expr)的值，并通过参数 result 返回该值。函数的返回值为-1/0，分别表示表达式有/无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含加(“+”)、减(“-”)、乘(“*”)、除(“/”)。函数 computing 中所用栈的基本操作的函数原型说明如下。void InitStack(STACK *s)：初始化栈。void Push(STACK *s, int e)：将一个整数压栈，栈中元素数目增 1。void Pop(STACK *s)
21、：栈顶元素出栈，栈中元素数目减 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 (*ptr!=/0) if(*ptr= ) /*当前字符是空格*/(1) ; /*字符指针指向下一字符*/continue; elseif (
22、isdigit(*ptr) /*当前字符是数字，则将该数字开始的数字串转换为数值*/tnum= (2) ; while (*ptr=0 ptr+; push( (4) ); else /*当前字符是运算符或其他符号*/if (*ptr=+|*ptr=-|*ptr=*|*ptr=/)if(!IsEmpty(S)a=Top(s); Pop( /*取运算符的第二个运算数*/if(!IsEmpty(S)b=Top(s); Pop( /*取运算符的第一个运算数*/else return-1; else return -1; switch (*ptr) case+: Push( break; case-:
23、 Push( break; case+: Push( break; case/: Push( break; elsereturn -1; ptr+; /*字符指针指向下一字符*/*while*/if (IsEmpty(s) return -1; else (5) =Top(s); Pop( /*取运算结果*/if (!IsEmpty(s) return -1; return 0; （分数：5.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_六、试题四(总题数：1，分数：5.00)说明已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组 Ht 中。节点
24、结构及数组 Ht的定义如下：#define MAXLEAFNUM 30Struct nodechar ch; char *pstr; int parent; int lchild, rchiid; ; Struct node Ht2 *MAXLEAFNUM; 该二叉树的 n 个叶子节点存储在下标为 1n 的 Ht 数组元素中。例如，某二叉树如图 8-26 所示，其存储结构如图 8-27 所示，其中，与叶子节点 a 对应的数组元素下标为 1，a 的父节点存储在 Ht5，表示为Ht1.parent=5。Ht7.parent=0 表示 7 号节点是树根，Ht7.lchild=3、Ht7.rchild
25、=6 分别表示 7号节点的左孩子是 3 号节点、右孩子是 6 号节点。如果用“0”或“1”分别标识二叉树的左分支和右分支如图 8-26 所示，从根节点开始到叶子节点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、1 序列，称之为对应叶子节点的编码。例如，图 8-26 中 a、b、c、d 的编码分别是 100、101、0、11。函数 LeafCode(Ht，n)的功能是：求解存储在 Ht 中的二叉树中所有叶子节点(n 个)的编码，叶子节点存储在 Ht1Htn中，求出的编码存储区由对应的数组元素 pstr 域指示。函数 LeafCode 从叶子到根逆向求叶子节点的编码。例如，对图 8-
26、26 中叶子节点 a 求编码的过程如图 8-28 所示。（分数：5.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_七、试题五(总题数：1，分数：5.00)说明已知包含头节点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。处理过程中，当元素重复出现时，保留元素第一次出现所在的节点。图 8-29(a)、(b)是经函数 compress( )处理前后的链表结构示例图。（分数：5.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_八、试题六(总
27、题数：1，分数：5.00)说明下面流程图的功能是：在已知字符串 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 的基本算法如下：从串 A 的首字符 A(0)开始，取子串A(0)A(1)i(m-1)与串 B 比较；若不同，则再取子串 A(1)A(2)A(m)与串 B 比较，以此类推。例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出 3)，不存在字符子串“RFD”(输出-1)。在流
28、程图中，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)、逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，以此类推。流程图本题流程图如图 8-30 所示。（分数：5.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_九、试题七(总题数：1，分数：9.00)说明假设数组 A 中的各元素 A(1)，A(2)，A(M)已经按从小到大排序(M1)；数组 B
29、 中的各元素 B(1)，B(2)，B(N)也已经按从小到大排序(N1)。执行下面的流程图后，可以将数组 A 与数组 B 中所有的元素全都存入数组 C 中，且按从小到大排序(注意：序列中相同的数全部保留并不计排列顺序)。例如，设数组 A 中有元素：2，5，6，7，9；数组 B 中有元素 2，3，4，7；则数组 C 中将有元素：2，2，3，4，5，6，7，7，9。流程图本题流程图如图 8-31 所示。（分数：9.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_十、试题八(总题数：1，分数：5.00)说明某单位动态收
30、集的数据中常包含重复的数据，所以需要进行处理，使得重复的数据仅出现一次。下面流程图的功能是：在 n(n1)个数据 D1，D 2，D n中，选出其中所有不重复的 k 个数据，置于原来前 k 个数据的位置上。该流程图的算法如下：第 1 个数据必然被选出，然后从第 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)经过上述
31、算法处理后的结果为：5，2，7，4，1，9 (k=6)流程图本题流程图如图 8-32 所示。（分数：5.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_程序员-数据结构与算法(一)答案解析(总分：79.00，做题时间：90 分钟)一、综合知识试题(总题数：33，分数：35.00)1.对具有 n 个元素的顺序表(采用顺序存储的线性表)进行_操作，其耗时与 n 的大小无关。A在第 i(1in)个元素之后插入一个新元素B删除第 i(1in)个元素C对顺序表中的元素进行排序D访问第 i(1in)个元素的前驱和后继（分数：1.00）A.B.C.D. 解析：解析 对具有 n 个
32、元素的顺序表访问第 i(1in)个元素的前驱和后继，其耗时与 n 的大小无关。2.若字符串 s 的长度为 n(n1)且其中的字符互不相同，则 s 的长度为 2 的子串有_个。An Bn-1 Cn-2 D2（分数：1.00）A.B. C.D.解析：解析 若字符串 s 的长度为 n(n1)且其中的字符互不相同，则 s 的长度为 2 的子串有 n-1 个。3.栈的运算特点是后进先出。元素 a、b、c、d 依次入栈，则不能得到的出栈序列是_。Aa b c d Bc a b d Cd c b a Db c d a（分数：1.00）A.B. C.D.解析：解析 首先可用得到出栈序列 dcba，如果每个元素
33、入栈后即出栈，则可得 abcd，若 c 位于栈顶，而 ab 在栈中，则可得 cbad，但不能得到 cabd。4.某循环队列的容量为 M，队头指针指向队头元素，队尾指针指向队尾元素之后，如图 8-18 所示(M=8)，则队列中的元素数目为_(MOD 表示整除取余运算)。（分数：1.00）A.B.C. D.解析：解析 队列容量为 M 时，队头指针 front 和队尾指针 rear 的值在 0M-1 之间循环，当rearfront 时，元素数目为 rear-front；当 rearfront 时，元素数目为 rear-front+M。所以，队列中元素数目为(rear-front+M)MOD M。5.
34、设初始栈为空，s 表示入栈操作，x 表示出栈操作，则_是合法的操作序列。Asxxsssxxx Bxxssxxss Csxsxssxx Dxssssxxx（分数：1.00）A.B.C. D.解析：解析 本题考查数据结构巾栈的基本知识。栈的特点是后进先出。对于一个关于初始为空的栈的操作序列，要求序列中任何一个操作之前，入栈操作的次数要大于等于出栈操作的次数。操作序列sxsxssxx 满足条件。6.n 个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么，_。A元素的出队次序与进栈次序相同B元素的出队次序与进栈次序相反C元素的进栈次序与进队次序相同D元素的出栈次序与出队次序相反（分数：1.00
35、）A.B. C.D.解析：解析 栈是先进后出的线性表，n 个元素全部进入栈后再依次出栈，则得到原序列的逆序。队列是先进先出的线性表，元素的进入次序与输出次序相同，因此，n 个元素先后经过栈和队列，得到的序列与进入栈的序列相反。7.与单向链表相比，双向链表_。A需要较少的存储空间 B遍历元素需要的时问较短C较易于访问相邻节点 D较易于插入和删除元素（分数：1.00）A.B.C. D.解析：解析 本题考查链表存储结构的基本特点。在单向链表中只能沿一个方向进行访问节点，而在双向链表中既可以向前遍历，也可以向后遍历。因此，双向链表较易于访问相邻节点。8.若一个栈以向量 V1n存储，且空栈的栈顶指针 t
36、op 为 n+1，则将元素 x 入栈的正确操作是_。Atop=top+1；Vtop=x； BVtop=x；top=top+1；Ctop=top-1；Vtop=x； DVtop=x；top=top-1；（分数：1.00）A.B.C. D.解析：解析 空栈的栈顶指针 top 为 n+1，说明栈顶指针随着元素入栈而减小，随着元素出栈而增加，所以元素 x 入栈的正确操作是 top=top-1；Vtop=x。9.在执行递归过程时，通常使用的数据结构是_。A堆栈(stack) B队列(queue) C图(graph) D树(tree)（分数：1.00）A. B.C.D.解析：解析 在执行递归过程时，通常使
37、用的数据结构是堆栈，要求先调用后返回。10.设数组 a16，09的元素以行为主序存放，每个元素占用一个存储单元，则数组元素 a3，3的地址为_。Aa+23 Ba+27 Ca+39 Da+35（分数：1.00）A. B.C.D.解析：解析 以行为主序存储，元素 a3，3之前有 23 个元素，所以其相对于数组起始地址的偏移量为23，地址为 a+23。11.若二维数组 P15，08的首地址为 base，数组元素按行存储，且每个元素占用 1 个存储单元，则元素 P3，3在该数组空间的地址为_。Abase+13 Bbase+16 Cbase+18 Dbase+21（分数：1.00）A.B.C.D. 解析
38、：解析 数组空间首地址为 base，所以，元素 P1，0的存储地址为 base，按行存储时，P3，3之前存储了 29+3 个元素，因此 P3，3在该数组空间的地址为 base+21。12.采用一维数组 S 存储一个 n 阶对称矩阵 A 的下三角部分(按行存放，包括主对角线)，设元素 Aij存放在 Sk中(i、j、k 均从 1 开始取值)，且 S1=A11，则 k 与 i、j 的对应关系是_。例如，元素 A32存在 S5中。A BC D （分数：1.00）A.B.C.D. 解析：解析 本题考查特殊矩阵的压缩存储。对称矩阵下三角的元素按行存储时，对于元素 Aij，其前面的元素数目为 1+2+i-1
39、+j-1=i(i-1)/2+j-1，因此元素 Aij存储在 Si(i-1)/2+j中。13.数组 A-55，08按列存储。若第一个元素的首地址为 100，且每个元素占用 4 个存储单元，则元素 A2，3的存储地址为_。A244 B260 C364 D300（分数：1.00）A.B. C.D.解析：解析 数组按列存储时，存储在 A2，3之前的元素个数为 113+7，因此，其存储地址为100+404=260。14.若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于 1，则该二叉树的_。A只有根节点无左予树 B只有根节点无右子树C非叶子节点只有左子树 D非叶子节点只有右子树（分数：1.00）A
40、.B.C.D. 解析：解析 若二叉树的前序遍历序列与中序遍历序列相同，说明二叉树的根节点没有左子树，以此类推，二叉树所有节点都没有左子树，非叶子节点只有右子树。15.由关键字序列(12，7，36，25，18，2)构造一棵二叉排序树(初始为空，第一个关键字作为根节点插入，此后对于任意关键字，若小于根节点的关键字，则插入左子树中，若大于根节点的关键字，则插入右子树中，且左、右子树均为二叉排序树)，该二叉排序树的高度(层数)为_。A6 B5 C4 D3（分数：1.00）A.B.C. D.解析：解析 根据题意，由关键字序列(12，7，36，25，18，2)构造的二叉排序树的高度应该为 4 层，第一层为
41、 12，第二层为 7 和 36，第三层为 2 和 25，最后一层为 18。16.对连通图进行遍历前设置所有顶点的访问标志为 false(未被访问)，遍历图后得到一个遍历序列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点 v 出发开始遍历，先访问 v 并设置其访问标志为 true(已访问)，同时将 v 加入遍历序列，再从 v 的未被访问的邻接顶点中选一个顶点，进行深度优先遍历；若 v 的所有邻接点都已访问，则回到 v 在遍历序列的直接前驱顶点，再进行深度优先遍历，直至图中所有顶点被访问过。_是图 8-19 的深度优先遍历序列。（分数：1.00）A. B.C.D.解析：解析 根据图
42、中的邻接关系，顼点 4 后应该就是顶点 6，所以 A 选项正确。17.在任意一棵非空的二叉树中，终端节点(叶子)的数目总是比具有两个孩子的非终端节点的数目_。A多 0 个 B多 1 个 C多 2 个 D多 3 个（分数：1.00）A.B. C.D.解析：解析 在任意一棵非空的二叉树中，终端节点(叶子)的数目总是比具有两个孩子的非终端节点的数目多 1 个。满二叉树的特点是每层上的节点数都达到最大值，因此对于高度为 h(h1)的满二叉树，其节点总数为 (18) 。对非空满二叉树，由根节点开始，按照先根后子树、先左子树后右子树的次序，从 1，2，3，依次编号，则对于树中编号为 i 的非叶子节点，其右
43、子树的编号为 (19) (高度为 3 的满二叉树如图 8-20所示)。（分数：2.00）(1).A2h B2h-1 C2h-1 D2h-1+1（分数：1.00）A.B.C. D.解析：(2).A2i B2i-1 C2i+1 D2i+2（分数：1.00）A.B.C. D.解析：解析 本题考查数据结构中二叉树的基本知识。满二叉树的第 1 层(树根)有 1 个节点，第二层有2 个节点，第三层有 4 个节点，以此类推，第 h 层有 2h-1 个节点。总节点数为 20+21+22+2h-1=2h-1。依题意，显然对非空满二叉树中的节点 i 的左子树编号为 2i，右子树编号为 2i+1。18.数据结构中的
44、树最适合用来表示_的情况。A数据元素有序 B数据元素之间具有多对多关系C数据元素无序 D数据元素之间具有一对多关系（分数：1.00）A.B.C.D. 解析：解析 本题考查数据结构中树的基本知识。数据结构中的树最适合用来表示数据元素之间具有一对多关系的情况。19.二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：特其左子树非空，则左子树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行_遍历，可得到一个节点元素的递增序列。A前序(根、左、右) B中序(左、根、右)C后序(左、右、根) D层序(从树根开始，按层次)（分数：1.00）A.B.C.D. 解析：解析 中序遍历二叉树的过程为：若二叉树为空，则进行空操作；否则中序遍历根的左子树：访问根节点；中序遍历根的右子树。显然，对一棵非空的二叉排序树进行中序遍历，可得到一个节点元素的递增序列。20.广度优先遍历的含义是：从图中某个顶点 v 出发，在访问了 v 之后依次访问 v 的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有己
