1、数据结构导论自考题模拟 15 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下列程序段的时间复杂度为_ s=0; for(i=1;in;i+) for(j=1;jn;j+) s+=i*j; A.O(1) B.O(n) C.O(2n) D.O(n2)（分数：2.00）A.B.C.D.2.若进栈次序为 a，b，c，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是_（分数：2.00）A.3B.5C.6D.73.线性表采用链式存储时，结点的存储地址_（分数：2.00）A.必须是不连续的B.必须是连续的C.连续与否均可D.和
2、头结点的存储地址相连续4.假设以数组 An存放循环队列的元素，其头、尾指针分别为 front 和 rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为_（分数：2.00）A.(rear-front)%nB.(rear-front-1)%nC.(front-rear+1)%nD.(rear-front+n)%n5.一个栈的输入序列为 1，2，3，m，若输出序列的第一个元素是 m，则输出的第 i(1im)个元素是_（分数：2.00）A.不确定B.m-iCiD.m-i+16.无向图中一个顶点的度是指图中_（分数：2.00）A.通过该顶点的简单
3、路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数7.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为_（分数：2.00）A.1024B.1036C.1020D.12408.具有 11 个顶点的有向完全图应具有_（分数：2.00）A.110 条弧B.50 条弧C.90 条弧D.100 条弧9.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为_（分数：2.00）A.FEDCBAB.ABCDEFC.FDECBAD.FBDCEA10.已知含 6 个顶点(v 0
4、，v 1 ，v 2 ，v 3 ，v 4 ，v 5 )的无向图的邻接矩阵如下图所示，则从顶点 v 0 出发进行深度优先遍历可能得到的顶点访问序列为_ （分数：2.00）A.(v0，v1，v5，v2，v3，v4)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v2，v5，v4，v3)D.(v0，v1，v4，v5，v2，v3)11.在下列排序方法中，平均时间性能为 O(nlog 2 n)且空间性能最好的是_（分数：2.00）A.快速排序B.堆排序C.归并排序D.基数排序12.一个有序表为(2，5，8，12，32，41，45，62，75，77，84，95，100)，当二分查找值为 84 的
5、结点时，查找成功时的比较次数为_（分数：2.00）A.1B.2C.4D.813.用某种排序方法对关键字序列(30，84，21，47，15，27，68，35，20)进行排序时，序列的变化情况如下： 20，15，21，30，47，27，68，35，84 15，20，21，30，35，27，47，68，84 15，20，21，30，27，35，47，68，84 则所采用的排序方法是_（分数：2.00）A.选择排序B.希尔排序C.归并排序D.快速排序14.对一棵有 120 个结点的完全二叉树按层编号，则编号为 51 的结点，它的父结点的编号为_（分数：2.00）A.24B.25C.98D.9915.由
6、同一关键字集合构造的各棵二叉排序树_（分数：2.00）A.其形态不一定相同，平均查找长度也不一定相同B.其形态不一定相同，但平均查找长度相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同二、填空题(总题数：13，分数：26.00)16.数据的逻辑结构在计算机存储器内的表示，称为数据的 1。 （分数：2.00）17.在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针 head 可用 p 表示为head= 1。 （分数：2.00）18.如果需要对线性表频繁进行 1 或 2 操作，则不宜采用顺序存储结构。 （分数：2.00）19.深度为 k(
7、k1)的完全二叉树至多有 1 个结点。 （分数：2.00）20.任意一棵完全二叉树中，度为 1 的结点数最多为 1。 （分数：2.00）21.已知一棵完全二叉树中共有 768 结点，则该树中共有 1 个叶子结点。 （分数：2.00）22.树在数据结构中常采用孩子链表法、孩子兄弟链表法和 1 三种存储结构表示。 （分数：2.00）23.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 1 的数目正相关。 （分数：2.00）24.具有 m 个叶子结点的哈夫曼树，其结点总数为 1。 （分数：2.00）25.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。 （
8、分数：2.00）26.对序列55，46，13，05，94，17，42进行冒泡排序，第一趟排序后的结果是 1。 （分数：2.00）27.快速排序是不稳定的，在最坏情况下，其时间复杂度为 1。 （分数：2.00）28.在最好的情况下，对于具有 n 个元素的有序序列，若采用冒泡排序，所需的比较次数为 1 次。 （分数：2.00）三、应用题(总题数：5，分数：30.00)从空树起，依次插入关键字 40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。（分数：6.00）(1).画出该二叉排序树。（分数：3.00）(2).画出删去该树中元素值为 90 的结点之后的二叉排序树。（分数
9、：3.00）29.设栈 S 1 的入栈序列为 1，2，3，4(每个数字为 13 个元素)，则不可能得到出栈序列 3，1，4，2。但可通过增设栈 S 2 来实现。例如，按下图中的箭头指示，依次经过栈 S 1 和 S 2 ，便可得到序列3，1，4，2。 （分数：6.00）30.已知一个无向图的顶点集为a，b，c，d，e，其邻接矩阵如下图所示 （分数：6.00）31.已知一组键值序列(14，12，16，17，15，14，10)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。 （分数：6.00）32.有一颗二叉树，如下图所示，试画出它的顺序存储结构示意图。 （分数：6.00）四、算
10、法设计题(总题数：2，分数：14.00)33.带头结点的单链表的结点结构如下： typedef struct node int data; struct node * next; Node,*LinkList; 试编写单链表的删除运算算法 void DeleteLinklist(LinkList head, int i)。 （分数：7.00）_34.试写出在有序表 T 中用二分查找法查找键值为 key 的元素的算法。 （分数：7.00）_数据结构导论自考题模拟 15 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下列程序段的时间复杂度为
11、_ s=0; for(i=1;in;i+) for(j=1;jn;j+) s+=i*j; A.O(1) B.O(n) C.O(2n) D.O(n2)（分数：2.00）A.B.C.D. 解析：考点 时间复杂度的计算 解析 循环嵌套，时间复杂度为 O(n 2 )。2.若进栈次序为 a，b，c，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是_（分数：2.00）A.3B.5 C.6D.7解析：考点 栈的存取原则 解析 可能的 5 种序列分别为：abc，acb，bca，bac，cba。3.线性表采用链式存储时，结点的存储地址_（分数：2.00）A.必须是不连续的B.必须是连续的C.
12、连续与否均可 D.和头结点的存储地址相连续解析：考点 线性表采用链式存储的特点 解析 线性表采用链式存储，结点的存储地址连续与否均可。4.假设以数组 An存放循环队列的元素，其头、尾指针分别为 front 和 rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为_（分数：2.00）A.(rear-front)%n B.(rear-front-1)%nC.(front-rear+1)%nD.(rear-front+n)%n解析：考点 循环队列数据元素个数的求取 解析 (rear-front)%n。5.一个栈的输入序列为 1，2，3，m，若
13、输出序列的第一个元素是 m，则输出的第 i(1im)个元素是_（分数：2.00）A.不确定B.m-i CiD.m-i+1解析：考点 栈的存取原则 解析 后进先出。6.无向图中一个顶点的度是指图中_（分数：2.00）A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数 C.通过该顶点的回路数D.与该顶点连通的顶点数解析：考点 无向图中顶点的度的定义 解析 无向图中一个顶点的度是与该顶点相邻接的顶点数。7.二维数组 A106采用行优先的存储方法，若每个元素占 4 个存储单元，已知元素 A34的存储地址为 1000，则元素 A43的存储地址为_（分数：2.00）A.1024B.1036C.1020
14、D.1240解析：考点 本题主要考查的是数组元素地址的运算 解析 对于 m*n 的数组采取，行优先存储，A43比 A34多 5 个元素，则多 5*4=20 个存储单元，所以存储位置为 1000+20=1020。8.具有 11 个顶点的有向完全图应具有_（分数：2.00）A.110 条弧 B.50 条弧C.90 条弧D.100 条弧解析：考点 本题主要考查的是一个具有 n 个顶点的有向完全的弧数 解析 任何两点之间都有弧的有向图称为有向完全图。个具有 n 个顶点的有向完全的弧数为 n(n-1)=11*10=110 条。9.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为_
15、（分数：2.00）A.FEDCBA B.ABCDEFC.FDECBAD.FBDCEA解析：考点 由二叉树的中序序列和后序序列求取先序序列 解析 根据后序序列判定根结点，再根据中序序列判定左右子树。10.已知含 6 个顶点(v 0 ，v 1 ，v 2 ，v 3 ，v 4 ，v 5 )的无向图的邻接矩阵如下图所示，则从顶点 v 0 出发进行深度优先遍历可能得到的顶点访问序列为_ （分数：2.00）A.(v0，v1，v5，v2，v3，v4)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v2，v5，v4，v3) D.(v0，v1，v4，v5，v2，v3)解析：考点 图的深度优先遍历 解析
16、 图的深度优先遍历算法。11.在下列排序方法中，平均时间性能为 O(nlog 2 n)且空间性能最好的是_（分数：2.00）A.快速排序B.堆排序 C.归并排序D.基数排序解析：考点 各种排序方法的平均时间性能和空间性能 解析 由下表比较可知选 B。 排序方法 平均时间 最坏情况 辅助存储 简单排序 O(n 2 ) O(n 2 ) O(1) 快速排序 O(nlog 2 nlog 2 n) O(n 2 ) O(log 2 n) 堆排序 O(nlog 2 nlog 2 n) O(nlog 2 nlog 2 n) O(1) 归并排序 O(nlog 2 nlog 2 n) O(nlog 2 nlog
17、2 n) O(n) 基数排序 O(d(n+rd) O(d(n+rd) O(rd) 12.一个有序表为(2，5，8，12，32，41，45，62，75，77，84，95，100)，当二分查找值为 84 的结点时，查找成功时的比较次数为_（分数：2.00）A.1B.2C.4 D.8解析：考点 本题主要考查的知识点为二分查找法 解析 二分查找法的基本思想是：每次将处于查找区间中间位置 E 的数据元素的键值与给定值 K 比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为 0(即查找不成功)为止。而本题中，第一次比较时查找区间为2，5，8，12，32，41，45，62，7
18、5，77，84，95，100，用84 与 45 进行比较；第二次比较时查找区间为62，75，77，84，95，100，用 84 与 77 比较；第三次比较时查找区间为84，95，100，用 84 与 95 比较；第四次比较时查找区间为84，则比较后查找成功。13.用某种排序方法对关键字序列(30，84，21，47，15，27，68，35，20)进行排序时，序列的变化情况如下： 20，15，21，30，47，27，68，35，84 15，20，21，30，35，27，47，68，84 15，20，21，30，27，35，47，68，84 则所采用的排序方法是_（分数：2.00）A.选择排序B.希
19、尔排序C.归并排序D.快速排序 解析：考点 排序算法 解析 几种排序算法的排序规则不同，根据序列的变化可知，此排序方法为快速排序。14.对一棵有 120 个结点的完全二叉树按层编号，则编号为 51 的结点，它的父结点的编号为_（分数：2.00）A.24B.25 C.98D.99解析：考点 完全二叉树中某结点 m 的父节点编号的求取 解析 完全二叉树中某结点的父节点编号= 15.由同一关键字集合构造的各棵二叉排序树_（分数：2.00）A.其形态不一定相同，平均查找长度也不一定相同 B.其形态不一定相同，但平均查找长度相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都
20、相同解析：考点 根据键值建立二叉排序树 解析 由同一关键字集合构造的各棵二叉排序树，其形态不一定相同，平均查找长度也不一定相同。二、填空题(总题数：13，分数：26.00)16.数据的逻辑结构在计算机存储器内的表示，称为数据的 1。 （分数：2.00）解析：存储结构 考点 数据的存储结构 解析 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。17.在一个带头结点的单循环链表中，p 指向尾结点的直接前驱，则指向头结点的指针 head 可用 p 表示为head= 1。 （分数：2.00）解析：p-next-next 考点 带头结点的单循环链表 解析 带头结点的单循环链表的指针。18.如果
21、需要对线性表频繁进行 1 或 2 操作，则不宜采用顺序存储结构。 （分数：2.00）解析：插入 删除 考点 线性表的存储结构及其适用的操作 解析 如果需要对线性表频繁进行插入或删除操作，则不宜采用顺序存储结构。19.深度为 k(k1)的完全二叉树至多有 1 个结点。 （分数：2.00）解析：2 k -1 考点 二叉树的性质 2 解析 深度为 k(k1)的二叉树最多有 2 k -1 个结点。20.任意一棵完全二叉树中，度为 1 的结点数最多为 1。 （分数：2.00）解析：1 考点 完全二叉树的特性 解析 由完全二叉树的定义可知，任意一棵完全二叉树中，度为 1 的结点数最多为 1。21.已知一棵
22、完全二叉树中共有 768 结点，则该树中共有 1 个叶子结点。 （分数：2.00）解析：384 考点 完全二叉树性质 解析 完全二叉树的深度为 第九层的结点个数为 2 9-1 =256 个，前 9 层的结点个数为 2 k -1=2 9 -1=511，最后一层结点个数为 768-511=257，则叶子结点个数= 22.树在数据结构中常采用孩子链表法、孩子兄弟链表法和 1 三种存储结构表示。 （分数：2.00）解析：双亲表示法 考点 树在数据结构中常采用的存储结构 解析 树在数据结构中常采用孩子链表法、孩子兄弟链表法和双亲表示法三种存储结构表示。23.求最小生成树的克鲁斯卡尔(Kruskal)算法
23、耗用的时间与图中 1 的数目正相关。 （分数：2.00）解析：边 考点 (Kruskal)算法 解析 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中边的数目正相关。24.具有 m 个叶子结点的哈夫曼树，其结点总数为 1。 （分数：2.00）解析：2m-1 考点 哈夫曼树结点总数 解析 具有 m 个叶子结点的哈夫曼树的结点总数为 2m-1。25.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。 （分数：2.00）解析：稳定的 考点 排序算法稳定性的考察 解析 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是稳定的。26.对序列55，4
24、6，13，05，94，17，42进行冒泡排序，第一趟排序后的结果是 1。 （分数：2.00）解析：46，13，05，55，17，42，94 考点 冒泡排序算法 解析 对序列55，46，13，05，94，17，42进行冒泡排序，第一趟排序后的结果是46，13，05，55，17，42，94。27.快速排序是不稳定的，在最坏情况下，其时间复杂度为 1。 （分数：2.00）解析：O(n 2 ) 考点 快速排序最坏情况下的时间复杂度 解析 快速排序最坏情况下的时间复杂度是 O(n 2 )。28.在最好的情况下，对于具有 n 个元素的有序序列，若采用冒泡排序，所需的比较次数为 1 次。 （分数：2.00）
25、解析：n-1 考点 冒泡排序的最好情况下的比较次数 解析 冒泡排序的最好情况下的比较次数是仅进行一趟排序，所以要比较 n-1 次。三、应用题(总题数：5，分数：30.00)从空树起，依次插入关键字 40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。（分数：6.00）(1).画出该二叉排序树。（分数：3.00）解析：(2).画出删去该树中元素值为 90 的结点之后的二叉排序树。（分数：3.00）解析：29.设栈 S 1 的入栈序列为 1，2，3，4(每个数字为 13 个元素)，则不可能得到出栈序列 3，1，4，2。但可通过增设栈 S 2 来实现。例如，按下图中的箭头指
26、示，依次经过栈 S 1 和 S 2 ，便可得到序列3，1，4，2。 （分数：6.00）解析：利用两个栈从 1，2，3，4 得到 4，1，3，2 的操作步骤为：H 1 ，P 1 ，H 2 ，H 1 ，H 1 ，H 1 ，P 1 ，H 2 ，P 2 ，P 2 ，P 1 ，H 2 ，P 2 ，P 1 ，H 2 ，P 2 。 考点 栈的存取规则：先进后出30.已知一个无向图的顶点集为a，b，c，d，e，其邻接矩阵如下图所示 （分数：6.00）解析：见下图 31.已知一组键值序列(14，12，16，17，15，14，10)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。 （分数：6.
27、00）解析：初始关键字：14 12 16 17 15 14 10 第一趟：12 14 16 17 14 15 10 第二趟：12 14 16 1710 14 15 第三趟：10 12 14 14 15 16 17 考点 二路归并排序32.有一颗二叉树，如下图所示，试画出它的顺序存储结构示意图。 （分数：6.00）解析：一棵二叉树只有先转换成完全二叉树后，才能用顺序存储结构进行存储。转换后的完全二叉树和二叉树的顺序存储结构示意图如下所示。 转换后的完全二叉树四、算法设计题(总题数：2，分数：14.00)33.带头结点的单链表的结点结构如下： typedef struct node int dat
28、a; struct node * next; Node,*LinkList; 试编写单链表的删除运算算法 void DeleteLinklist(LinkList head, int i)。 （分数：7.00）_正确答案：()解析：Void DeleteLinklist(LinkList head,int i) Node * q; if(i=1) q=head; else q=head-next; int e=1; while(ci-1) c+ if(q!=NULL q-next=p-next; free(p); else exit(|找不到删除的结点|); 考点 单链表的删除34.试写出在有
29、序表 T 中用二分查找法查找键值为 key 的元素的算法。 （分数：7.00）_正确答案：()解析：int Search_Bin(SSTable T,KeyType key) /在有序表 T 中二分查找其关键字等于 key 的数据元素 /若找到，则函数值为该元素在表中的位置，否则为 0 low=1;high=T.1ength; /置区间初值 while(low=high) mid=(low+high)/2; if(EQ(key,T.elemmid.key) return mid; /找到待查元素 else if(LT(key,T.elemmid.key) high=mid-1; /继续在前半区间进行查找 else low=mid+1; /继续在后半区间进行查找 return 0; /顺序表中不存在待查元素 /Search_Bin 考点 二分查找算法
