【计算机类职业资格】软件设计师-数据结构(二)及答案解析.doc

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

1、软件设计师-数据结构(二)及答案解析(总分：131.00，做题时间：90 分钟)一、综合知识试题(总题数：36，分数：41.00)1.具有 n 个顶点、e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为_。（分数：1.00）A.O(n2)B.O(e2)C.(n*e)D.D(n+e)2.对于长度为，m(m1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是_。（分数：1.00）A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C.入队序列与出队序列关系为 1:1，而入栈序列与出栈序列关系是

2、 1:n(n1)D.入栈序列与出栈序列关系为 1:1，而入队序列与出队序列关系是 1:n(n1)3.下面关于二叉排序树的叙述中，错误的是_。（分数：1.00）A.对二叉排序树进行中序遍历，必定得到节点关键字的有序序列B.依据关键字无序的序列建立二叉排序树，也可能构造出单支树C.若构造二叉排序树时进行平衡化处理，则根节点的左子树节点数与右子树节点数的差值一定不超过 1D.若构造二叉排序树时进行平衡化处理，则根节点的左子树高度与右子树高度的差值一定不超过 14.邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有，n 个顶点、e 条边的图，_。（分数：1.00）A.进行深度优先遍历运算所消耗的时

3、间与采用哪一种存储结构无关B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n*e)D.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n2)5.用关键字序列 10、20、30、40、50 构造的二叉树排序(二叉查找树)为_。（分数：1.00）A.B.C.D.6.设有如下所示的下三角矩阵 A08，08，将该三角矩阵的非零元素(即行下标不小于列下标的所有元素)按行优先压缩存储在数组 M1m中，则元素 Ai,j(0i8，ji)存储在数组 M 的_中。（分数：1.00）A.B.C.D.7._的邻接矩阵是一个对

4、称矩阵。（分数：1.00）A.无向图B.AOV 网C.AOE 网D.有向图8.设循环队列 Q 的定义中有 rear 和 len 两个域变量，其中 rear 表示队尾元素的指针，len 表示队列的长度，如下图所示(队列长度为 3，队头元素为 e)。设队列的存储空间容量为 M，则队头元素的指针为_。（分数：1.00）A.(Q.rear+Q.len-1)B.(Q.rear+Q.len-1+M)%MC.(Q.rear-Q.len+1)D.(Q.rear-Q.len+1+M)%M9.若将某有序树 T 转换为二叉树 T1，则 T 中节点的后根序列就是 T1中节点的 (8) 遍历序列。例如，下图(a)所示的

5、有序树转化为二叉树后如图(b)所示。（分数：1.00）A.先序B.中序C.后序D.层序10.下面关于查找运算及查找表的叙述中，错误的是_。（分数：1.00）A.哈希表可以动态创建B.二叉排序树属于动态查找表C.折半查找要求查找表采用顺序存储结构或循环链表结构D.顺序查找方法既适用于顺序存储结构，也适用于链表结构11.下面关于栈和队列的叙述中，错误的是_。（分数：1.00）A.栈和队列都是操作受限的线性表B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为 O(1)C.若队列的数据规模 n 可以确定，则采用顺序存储结构比链式存储结构效率更高D.利用两个栈可以模拟一个

6、队列的操作，反之亦可设一个包含 N 个顶点、E 条边的简单有向图采用邻接矩阵存储结构(矩阵元素 Aij等于 1/0 分别表示顶点 i 与顶点 j 之间有/无弧)，则该矩阵的元素数目为 (11) ，其中非零元素数目为 (12) 。（分数：2.00）A.E2B.N2C.N2-E2D.N2+E2A.NB.N+EC.ED.N-E12.栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，_必须用栈。（分数：1.00）A.实现函数或过程的递归调用及返回处理时B.将一个元素序列进行逆置C.链表节点的申请和释放D.可执行程序的装入和卸载已知一个线性表(16，25，35，43，51，62，87，93)

7、，采用散列函数 H(Key)=Key mod 7 将元素散列到表长为 9 的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (15) ，在该散列表上进行等概率成功查找的平均查找长度为 (16) (确定为记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。（分数：2.00）(1).0 1 2 3 4 56 7 83543165125 628793 0 1 2 3 4 5 6 7 835431693255162870 1 2 3 4 5 6 7 835431651258762930 1 2 3 4 5 6

8、7835431651258762 93（分数：1.00）A.B.C.D.A.(5*1+2+3+6)/8B.(5*1+2+3+6)/9C.(8*1)/8D.(8*1)/913.单向链表中往往含有一个头节点，该节点不存储数据元素，一般令链表的头指针指向该节点，而该节点指针域的值为第一个元素节点的指针。以下关于单链表头节点的叙述中，错误的是_。（分数：1.00）A.若在头节点中存入链表长度值，则求链表长度运算的时间复杂度为 O(1)B.在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C.加入头节点后，代表链表的头指针不因为链表为空而改变D.加入头节点后，在链表中进行查找运算的时间复杂

9、度为 O(1)14.某双向链表中的节点如下图所示，删除 t 所指节点的操作为_。（分数：1.00）A.t-prior-next= t-next; t-next-prior= t-prior;B.t-prior-prior= t-prior, t-next-next= t-next,C.t-prior-next= t-prior; t-next-prior= t-next;D.t-prior-prior= t-next; t-next-prior= t-prior;15.下面关于图(网)的叙述中，正确的是_。（分数：1.00）A.连通无向网的最小生成树中，顶点数恰好比边数多 1B.若有向图是强连

10、通的，则其边数至少是顶点数的 2 倍C.可以采用 AOV 网估算工程的工期D.关键路径是 AOE 网中源点至汇点的最短路径16.对以下 4 个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是_。（分数：1.00）A.89, 27, 35, 78, 41, 15B.27, 35, 41, 16, 89, 70C.15, 27, 46, 40, 64, 85D.90, 80, 45, 38, 30, 2517.广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是_。（分数：1.00）A.链表B.静态数组C.动态数组D.散列表18.若有数组声明 a03，02，14，设编译时

11、为 a 分配的存储空间首地址为 base_a，且每个数组元素占据一个存储单元。当元素以行为序存放(即按 a0，0，1，a0,0，2，a0，0，3，a0,0，4，a0，1，1，a0,1，2，a3，2，4顺序存储)，则数组元素 a2，2，2在其存储空间中相对base_a 的偏移量是_。（分数：1.00）A.8B.12C.33D.4819.某一维数组中依次存放了数据元素 12，23，30，38，41，52，54，76，85，在用折半(二分)查找方法(向上取整)查找元素 54 时，所经历“比较”运算的数据元素依次为_。（分数：1.00）A.41, 52, 54B.41, 76, 54C.41, 76,

12、 52, 54D.41, 30, 76, 5420.对 n 个元素的有序表 A1n进行二分(折半)查找(除 2 取商时向下取整)，查找元素 Ai(1in)时，最多于 A 中的_个元素进行比较。（分数：1.00）A.B.C.D.21.设 L 为广义表，将 head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表 L=(x，y，z)，a，(u，t，w)，则从 L 中取出原子项 y 的运算是_。（分数：1.00）A.head(tail(taiI(L)B.tail(head(head(L)C.head(tail(head(L)D.tai

13、l(tail(head(L)22.已知一棵度为 3 的树(一个节点的度是指其子树的数目，树的度是指该树中所有节点的度的最大值)中有 5 个度为 1 的节点，4 个度为 2 的节点，2 个度为 3 的节点，那么，该树中的叶子节点数目为_。（分数：1.00）A.10B.9C.8D.723.字符串采用链表存储方式时，每个节点存储多个字符有助于提高存储密度。若采用节点大小相同的链表存储串，则串比较、求子串、串连接、串替换等串的基本运算中，_。（分数：1.00）A.进行串的比较运算最不方便B.进行求子串运算最不方便C.进行串连接最不方便D.进行串替换最不方便24._是右图的合法拓扑序列。（分数：1.00

14、）A.6 5 4 3 2 1B.1 2 3 4 5 6C.5 6 3 4 2 1D.5 6 4 2 1 325.下面关于二叉树的叙述，正确的是_。（分数：1.00）A.完全二叉树的高度 h 与其节点数 n 之间存在确定的关系B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构C.完全二叉树中一定不存在度为 1 的节点D.完全二叉树中必定有偶数个叶子节点26.某一维数组中依次存放了数据元素 15，23，38，47，55，62，88，95，102，123，采用折半(二分)法查找元素 95 时，依次与_进行了比较。（分数：1.00）A.62，88，95B.62，95C.55，88

15、，95D.55，9527.若用 n 个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的结点总数为_。（分数：1.00）A.2nB.2n-1C.2n+1D.2n+2一个具有 m 个节点的二叉树，其二叉链表节点(左、右孩子指针分别用 left 和 right 表示)中的空指针总数必定为 (6) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有节点进行如下操作：若节点 p 的左孩子指针为空，则将该左指针改为指向 p 在中序(先序、后序)遍历序列的前驱节点；若 p 的右孩子指针为空，则将该右指针改为指向 p 在中序(先序、后序)遍历序列的后继节点。假设指针 s 指向中序(先序、后序)线索二叉

16、树中的某节点，则 (7) 。（分数：2.00）A.m+2B.m+1C.mD.m-1A.sright 指向的节点一定是 s 所指节点的直接后继节点B.sleft 指向的节点一定是 s 所指节点的直接前驱节点C.从 s 所指节点出发的 right 链可能构成环D.s 所指节点的 left 和 right 指针一定指向不同的节点28.将一个无序序列中的元素依次插入到一棵_，并进行中序遍历，可得到一个有序序列。（分数：1.00）A.完全二叉树B.最小生成树C.二叉排序树D.最优叉二树29.对于哈希表，如果将装填因子 定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，_。（分数：1.00）A

17、. 的值随冲突次数的增加而递减B. 越大发生冲突的可能性就越大C. 等于 1 时不会再发生冲突D. 低于 0.5 时不会发生冲突以下关于快速排序算法的描述中，错误的是 (35) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素 12，25，30，45，52，67，85 构成，则初始排列为 (36) 时，排序效率最高(令序列的第一个元素为基准元素)。（分数：2.00）A.快速排序算法是不稳定的排序算法B.快速排序算法在最坏情况下的时间复杂度为 O(log2n)C.快速排序算法是一种分治算法D.当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度A.45, 12, 3

18、0, 25,67, 52, 85B.85, 67, 52, 45, 30, 25, 12C.12, 25, 30, 45, 52, 67, 85D.45, 12, 25, 30, 85, 67, 5230.下面关于哈夫曼树的叙述中，正确的是_。（分数：1.00）A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个结点互为兄弟结点D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点31.给定一个有 n 个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动_个元素。（分数：1.00）A.(n+1)/2B.n/2C.(n-1)/

19、2D.1已知一个二叉树的先序遍历序列为、，中序遍历序列为、，则该二叉树的后序遍历序列为 (29) 。对于任意一棵二叉树，叙述错误的是 (30) 。（分数：2.00）A.、B.、C.、D.、A.由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列B.由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列C.由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列D.由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列二、案例分析试题(总题数：6，分数：90.00)32.阅读下列说明和 C 代码，回答问题。说明堆数据结构定义如下。对于 n 个元素的关键字序列 a1，a 2

20、，a n，当且仅当满足下列关系时称其为堆。在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图 8.7 是一个大顶堆的例子。（分数：15.00）_33.阅读下列说明和 C 代码，回答问题。说明对有向图进行拓扑排序的方法是：(1)初始时拓扑序列为空。(2)任意选择一个入度为 0 的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧。(3)重复(2)，直到不存在入度为 0 的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。函数 int* TopSort(LinkedDigraph

21、G)的功能是对有向图 G 中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图 G 中的顶点从 1 开始依次编号，顶点序列为v1，v 2，.，v n，图 G 采用邻接表示，其数据类型定义如下。#define MAXVNUM 50 /*最大顶点数*/typedef struct ArcNode /*表节点类型*/int adjvex; /*邻接顶点编号*/struct ArcNode *nextarc; /*指示下一个邻接顶点*/ArcNode；typedef struct AdjList /*头节点类型*/char vdata; /*顶点的数据信息*/

22、ArcNode *firstarc; /*指向邻接表的第一个表结点*/AdjList;typedef struct LinkedDigraph /*图的类型*/int n; /*图中顶点个数*/AdjList Vhead MAXVNUM； /*所有顶点的头结点数组*/LinkedDigraph;例如，某有向图 G 如图 8.8 所示，其邻接表如图 8.9 所示。函数 TopSort 中用到了队列结构(Queue 的定义省略)，实现队列基本操作的函数原型如下表所示：函数原型 说明void InitQueue(Queue* Q) 初始化队列(构造一个空队列)bool IsEmpty(Queue Q

23、) 判断队列是否为空，若是则返回 true，否则返回 falsevoid EnQueue(Queue* Q,int e) 元素入队列void DeQueue(Queue* Q, int* p) 元素出队列C 代码int *TODSort (LinkedDigraph G) ArcNode *p; /*临时指针，指示表结点*/Queue Q;/*临时队列，保存入度为 0 的顶点编号*/int k=0； /*临时变量，用作数组元素的下标*/int j=0，w=0； /*临时变量，用作顶点编号*/int *topOrdert *inDegree;topOrder=(int*)malloc(G.n+1

24、)*sizeof (int);/*存储拓扑序列中的顶点编号*/inDegree=(int+)malloc( (G.n+l)+sizeof (int)j/*存储图 G 中各顶点的入度*/if (!inDegree | !topOrder) return NULL;(1) ;/*构造一个空队列*/for(j=1;j=G.n; j+) /*初始化*/topOrderj =0; inDegreej =0;for(j=1；j=G.n；j+) /*求图 G 中各顶点的入度*/for(p=G.Vheadj.firstarc; p;p=p-nextarc)inDegree p- adjvex +=1;for(

25、j=1；j=Gn; j+) /*将图 G 中入度为 0 的顶点保存在队列中*/if(0=inDegreej )EnQueue(Q,j)；while(!IsEmpty (Q) (2) ; /*队头顶点出队列并用 w 保存该顶点的编号*/topOrderk+=w;/*将顶点 w 的所有邻接顶点的入度减 1(模拟删除顶点 w 及从该顶点出发的弧的操作)*/for(p=G.Vheadw.firstarc; p;p=p-nextarc) (3) -=1；if (0= (4) ) EnQueue (Q, p-adjvex);/*for*/*while*/free (inDegree)；if ( (5) )

26、return NULL;return topOrder;/*TopSort*/问题 1 根据以上说明和 C 代码，填充 C 代码中的空(1)(5)。问题 2 对于图 8.8 所示的有向图 G，写出函数 TopSort 执行后得到的拓扑序列。若将函数 TopSort 中的队列改为栈，写出函数 TopSort 执行后得到的拓扑序列。问题 3 设某有向无环图的顶点个数为 n、弧数为 e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort 的时间复杂度是 (6) 。若有向图采用邻接矩阵表示(例如，图 8.8 所示有向图的邻接矩阵如图 8.10 所示)，且将函数 TopSort 中有关邻接

27、表的操作修改为针对邻接矩阵的操作，那么对于有 n 个顶点、e 条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是 (7) 。（分数：15.00）_34.阅读以下说明和 C 程序，在(n)处填入适当的字句。说明现有 n(n1000)节火车车厢，顺序编号为 1，2，3，n，按编号连续依次从 A 方向的铁轨驶入，从 B方向铁轨驶出，一旦车厢进入车站(Station)就不能再回到 A 方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 8.11 所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。（分数：15.00）_35.阅读下列说明和 C 函数代码，在(n)

28、处填入适当的字句。说明对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，节点类型定义如下。typedef struct BtNodeElemType data; /*节点的数据域，ElemType 的具体定义省略*/struct BtNode *lchild，*rchild; /*节点的左、右孩子指针域*/BtNode, *BTree；在函数 InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表(简称链栈)，其节点类

29、型定义如下。typedef struct StNode /*链栈的节点类型*/BTree elem; /*栈中的元素是指向二叉链表节点的指针*/struct StNode *link;StNode;假设从栈顶到栈底的元素为 en，e e-1，e 1，则不含头节点的链栈示意图如图 8.12 所示。（分数：15.00）_36.阅读下列说明和 C 函数，在(n)处填入适当的字句。说明已知集合 A 和 B 的元素分别用不含头节点的单链表存储，函数 Difference()用于求解集合 A 与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合 A=5，10，20，15，25，30，集合 B=

30、5，15，35，25，如图 8.13(a)所示，运算完成后的结果如图 8.13(b)所示。（分数：15.00）_37.阅读下列说明和 C 代码，在(n)处填入适当的子句。说明栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stack Top)，而另一端称为栈底(Stack Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为空(IsEmpty)、判断栈是否己满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中

31、各数据项不必连续存储，如图 8.14 所示。（分数：15.00）_软件设计师-数据结构(二)答案解析(总分：131.00，做题时间：90 分钟)一、综合知识试题(总题数：36，分数：41.00)1.具有 n 个顶点、e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为_。（分数：1.00）A.O(n2)B.O(e2)C.(n*e)D.D(n+e) 解析：分析 深度优先遍历要对每个节点都进行遍历，广度优先遍历是要把每条边都遍历一遍，所以是O(n+e)。2.对于长度为，m(m1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是_。（分数：1.00）A.若入栈

32、和入队的序列相同，则出栈序列和出队序列可能相同B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C.入队序列与出队序列关系为 1:1，而入栈序列与出栈序列关系是 1:n(n1)D.入栈序列与出栈序列关系为 1:1，而入队序列与出队序列关系是 1:n(n1) 解析：要点解析 如果入栈和入队的序列相同，则出栈序列和出对序列既可以相同，也可以互为逆序。例如，设入栈和入队序列为 1，2，3。对于栈来说，如果每次进去一个后就出来，则出栈序列为1，2，3；而出队序列也为 1，2，3。因为栈是“后进先出”的数据结构，而队列是“先进先出”的数据结构，因此二者可互为逆序。如果入队序列与出队序列关系为

33、1:1，那么由于栈的后进先出的特性，则入栈序列与出栈序列关系是 1:n(n1)，比如，abcde 入队，它出队只可能是 abcde，而入栈 abcde，则出栈的序列却不止一种。所以 A 选项、B 选项、C 选项都是正确的。3.下面关于二叉排序树的叙述中，错误的是_。（分数：1.00）A.对二叉排序树进行中序遍历，必定得到节点关键字的有序序列B.依据关键字无序的序列建立二叉排序树，也可能构造出单支树C.若构造二叉排序树时进行平衡化处理，则根节点的左子树节点数与右子树节点数的差值一定不超过1 D.若构造二叉排序树时进行平衡化处理，则根节点的左子树高度与右子树高度的差值一定不超过 1解析：要点解析

34、二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。(1)若左子树不空，则左子树上所有节点的值均小于它的根节点的值。(2)若右子树不空，则右子树上所有节点的值均大于它的根节点的值。(3)左、右子树也分别为二叉排序树。中序遍历二叉树，即是先遍历左子树，再访问根节点，最后遍历右子树，根据二叉排序树的定义可知，进行中序遍历后，得到有序序列。而平衡二叉树的是这样的，要求任何一个节点的左、右子树的高度差都不大于 1，显然，D 选项的说法是正确的，而 C 选项的说法是不正确的。4.邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有，n 个顶点、e

35、 条边的图，_。（分数：1.00）A.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n*e)D.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n2) 解析：要点解析 深度优先遍历图的实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图采用邻接矩阵表示时，查找所有邻接点所需要的时间是 O(n2)，若以邻接表作为图的存储结构，则需要 O(e)的时间复杂度查找所有顶点的邻接点。广度优先遍历和深度优先遍历的时间复杂度相同，其

36、实质都是通过边或弧找邻接点的过程。5.用关键字序列 10、20、30、40、50 构造的二叉树排序(二叉查找树)为_。（分数：1.00）A.B.C. D.解析：要点解析 根据关键字序列构造二叉排序树的基本过程是：若需插入的关键字大于树根，则插入到右子树上，若小于树根，则插入到左予树上，若为空，则作为树根节点。6.设有如下所示的下三角矩阵 A08，08，将该三角矩阵的非零元素(即行下标不小于列下标的所有元素)按行优先压缩存储在数组 M1m中，则元素 Ai,j(0i8，ji)存储在数组 M 的_中。（分数：1.00）A. B.C.D.解析：要点解析 如图所示，按行方式压缩存储时，Ai,j之前的元素

37、数目为(1+2+i+j)个，数组 M的下标从 1 开始，因此 Ai,j的值存储在*中。7._的邻接矩阵是一个对称矩阵。（分数：1.00）A.无向图 B.AOV 网C.AOE 网D.有向图解析：分析 邻接矩阵(Adjacency Matrix)：是表示顶点之间相邻关系的矩阵。其特点是无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。8.设循环队列 Q 的定义中有 rear 和 len 两个域变量，其中 rear 表示队尾元素的指针，len 表示队列的长度，如下图所示(队列长度为 3，队头元素为 e)。设队列的存储空间容量为 M，则队头元素的指针为_。（分数：1.00）A.(Q.rear

38、+Q.len-1)B.(Q.rear+Q.len-1+M)%MC.(Q.rear-Q.len+1)D.(Q.rear-Q.len+1+M)%M 解析：要点解析 设队列的队头指针为 front，front 指向队头元素。队列的存储空间容量为 M，说明队列中最多可以有 M 个元素；队列的长度为 len，说明当前队列中有 len 个元素。则有：Q.rea=(Q.front+Q.len-1)%MQ.front=(Q.rear-Q.len+1+M)%M*9.若将某有序树 T 转换为二叉树 T1，则 T 中节点的后根序列就是 T1中节点的 (8) 遍历序列。例如，下图(a)所示的有序树转化为二叉树后如图(

39、b)所示。（分数：1.00）A.先序B.中序 C.后序D.层序解析：分析 树转换成二叉树的规则是：树中某节点 M 的孩子节点，在生成二叉树后放在 M 节点的左孩子位置；M 的兄弟节点，在生成二叉树后放在 M 节点的右孩子位置。图(a)的后序序列是 2、5、6、3、7、4、1，和图(b)的中序序列一样。10.下面关于查找运算及查找表的叙述中，错误的是_。（分数：1.00）A.哈希表可以动态创建B.二叉排序树属于动态查找表C.折半查找要求查找表采用顺序存储结构或循环链表结构 D.顺序查找方法既适用于顺序存储结构，也适用于链表结构解析：要点解析 对于选项 A，哈希函数即在记录的关键字与记录的存储位置

40、之间建立的一种对应关系。应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。对于选项 B，若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，即为动态查找表。显然在二叉排序树中，进行排序时也插入了新节点。故正确。对于选项 C，二分查找法只适用于顺序存储结构。对于选项 D，以顺序表或线性链表表示静态查找表，则查找函数可用顺序查找来实现。11.下面关于栈和队列的叙述中，错误的是_。（分数：1.00）A.栈和队列都是操作受限的线性表B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为

41、 O(1)C.若队列的数据规模 n 可以确定，则采用顺序存储结构比链式存储结构效率更高D.利用两个栈可以模拟一个队列的操作，反之亦可 解析：要点解析 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。栈的修改是按后进先出的原则进行的，所以，栈称为后进先出(Last In First Oust)的线性表，简称 LIFO 表。队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队首(front)，允许插入的一端称为队尾(rear)。先

42、进入队列的成员总是先离开队列。队列亦称作先进先出(First In First Out)的线性表，简称 FIFO 表。尾指针是指向终端节点的指针，用它来表示单循环链表可以使得查找链表的开始节点和终端节点都很方便，设一带头节点的单循环链表，其尾指针为 rear，则开始节点和终端节点的位置分别是 rearnextnext和 rear，查找时间都是 O(1)。链表是指用一组任意的存储单元来依次存放数据，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中节点的逻辑次序和物理次序不一定相同。顺序存储是把数据按逻辑顺序依次存放在一组地址连续的存储单元里。因此，

43、如果队列的数据规模确定，则在顺序存储结构中存取数据的速度会比链式存储结构中的要快。假设两个栈 A 和 B，且都为空。可以认为栈 A 为提供入队列的功能，栈 B 提供出队列的功能。入队列：入栈 A。出队列：如果栈 B 不为空，直接弹出栈 B 的数据；如果栈 B 为空，则依次弹出栈 A 的数据，放入栈 B中，再弹出栈 B 的数据。因此两个栈可以模拟一个队列的操作，但反之不可。设一个包含 N 个顶点、E 条边的简单有向图采用邻接矩阵存储结构(矩阵元素 Aij等于 1/0 分别表示顶点 i 与顶点 j 之间有/无弧)，则该矩阵的元素数目为 (11) ，其中非零元素数目为 (12) 。（分数：2.00）

44、A.E2B.N2 C.N2-E2D.N2+E2解析：A.NB.N+EC.E D.N-E解析：分析 对于有 N 个节点的邻接矩阵有 N2个元素。对于有向图，其邻接矩阵中非零元素为正方向的边的个数，题目中给出此有向图有 E 条边，所以其邻接矩阵中的非零元素为 E 个。12.栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，_必须用栈。（分数：1.00）A.实现函数或过程的递归调用及返回处理时 B.将一个元素序列进行逆置C.链表节点的申请和释放D.可执行程序的装入和卸载解析：要点解析 栈是一种后进先出的数据结构。将一个元素序列逆置时，可以使用栈也可以不用。链表节点的申请和释放次序与应用要

45、求相关，不存在“先申请后释放”的操作要求。可执行程序的装入与卸载，也不存在“后进先出”的操作要求。对于函数的递归调用与返回，一定是后被调用执行的先返回。已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数 H(Key)=Key mod 7 将元素散列到表长为 9 的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (15) ，在该散列表上进行等概率成功查找的平均查找长度为 (16) (确定为记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度)。（分数：2.00）(1).0 1 2

46、3 4 56 7 83543165125 628793 0 1 2 3 4 5 6 7 835431693255162870 1 2 3 4 5 6 7 835 43 16 51 25 87 62 930 1 2 3 4 5 6 7 835 43 16 51 25 87 62 93（分数：1.00）A.B.C. D.解析：A.(5*1+2+3+6)/8 B.(5*1+2+3+6)/9C.(8*1)/8D.(8*1)/9解析：分析 哈希表的构造是软件设计师常考知识点，考生需重点掌握。在本题中，表长为 9 的散列表初始时为空，散列函数为：H(Key)=Key mod 7 根据哈希表的构造方法有：H(16)=16 mod 7=2; H(25)=25 mod 7=4; H(35)=35 mod 7=0; H(43)=43 mod 7=1。前 4 个数都不冲突，可以直接填入散列表的相应位置，即：0 1 2 3 4 5 6 7 835 43 16 25继续取第五个元素 51，有：H(51)=51mod 7=2，第 2 个单元已经填入 16 了，冲突了