1、数据结构导论自考题模拟 6 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.能正确地实现预定的功能，满足具体问题的需要是指算法的_（分数：2.00）A.正确性B.易读性C.健壮性D.时空性2.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是_（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表3.已知一个顺序存储的线性表，设每个结点需占 m 个存储单元，若第一个结点的地址为 d，则第 i 个结点的地址为_（分数：2.00）A.d+(i-1)*mB
2、.d+i*mC.d-i*mD.d+(i+1)*m4.如果以链表作为栈的存储结构，则退栈操作时_（分数：2.00）A.必须判别栈是否满B.必须判别栈是否空C.判别栈元素的类型D.对栈不作任何判别5.若用一个有 6 个单元的数组来实现循环队列，rear 和 front 的初值分别为 0 和 3。则从队列中删除一个元素，再添加两个元素后，rear 和 front 的值分别为_（分数：2.00）A.1 和 5B.2 和 4C.4 和 2D.5 和 16.根据定义，树的叶子结点的度数_（分数：2.00）A.必大于 0B.必等于 0C.必等于 1D.必等于 27.在一棵深度为 H 的完全二叉树中，所含结点
3、的个数不少于_ A.2H-1-1 B.2H-1 C.2H-1 D.2H（分数：2.00）A.B.C.D.8.二叉树若采用二叉链表结构表示，则对于 n 个结点的二叉树一定有_（分数：2.00）A.2n 个指针域，其中 n 个指针为 NULLB.2n 个指针域，其中 n+1 个指针为 NULLC.2n-1 个指针域，其中 n 个指针为 NULLD.2n-1 个指针域，其中 n+1 个指针为 NULL9.下列有关图的遍历的说法中不正确的是_（分数：2.00）A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法D.图的遍历要求每
4、一结点仅被访问一次10.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用_（分数：2.00）A.求关键路径的方法B.求最短路径的 Dijkstra 方法C.广度优先遍历方法D.深度优先遍历方法11.散列表中由于散列到同一个地址而引起的“堆积”现象，是由_（分数：2.00）A.同义词之间发生冲突引起的B.非同义词之间发生冲突引起的C.同义词之间或非同义词之间发生冲突引起的D.散列表“溢出”引起的12.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为_（分数：2.00）A.索引存储方法B.顺序存储方法C.链式存储方法D.散列存储方法13.下列说法
5、中不正确的是_（分数：2.00）A.无向图的极大连通子图称为连通分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索算法14.一组记录的键值为(46，74，18，53，14，20，40，38，86，65)，利用堆排序的方法建立的初始堆为_（分数：2.00）A.(14，18，38，46，65，40，20，53，86，74)B.(14，38，18，46，65，20，40，53，86，74)C.(14，18，20，38，40，46，53，65，74，86)D.(14，86，20，38，40，46
6、，53，65，74，18)15.对序列(22，86，19，49，12，30，65，35，18)进行一趟排序后得到的结果如下：(18，12，19，22，49，30，65，35，86)，则可以认为使用的排序方法是_（分数：2.00）A.选择排序B.冒泡排序C.快速排序D.插入排序二、填空题(总题数：13，分数：26.00)16.算法的时间性能是指算法包含的 1。 （分数：2.00）17.设有一批数据元素，为了最快地存储某元素，数据结构宜用 1 结构，为了方便插入一个元素，数据结构宜用链式存储结构。 （分数：2.00）18.单链表中逻辑上相邻的两个元素在物理位置上 1 相邻。 （分数：2.00）19
7、.用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234，为了得到 1342 的出栈顺序，相应的 S和 X 操作串为 1。 （分数：2.00）20.循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是 1。 （分数：2.00）21.一个顺序队列的第 5 个元素的存储地址是 200，第 10 个元素的存储地址是 225。每个元素的长度是5，则第 20 个元素的地址是 1。 （分数：2.00）22.若用后序遍历法遍历题下图所示的二叉树，其输出序列为 1。 （分数：2.00）23.一棵具有 n 个结点的树，所有非终端结点的度均为
8、k，则该树中叶子结点个数为 1。 （分数：2.00）24.若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 1。 （分数：2.00）25. 1 是顺序存储与链式存储相结合的存储方法。 （分数：2.00）26.一个图的最小生成树是图所有生成树中 1 最小的生成树。 （分数：2.00）27.查找表的逻辑结构是 1。 （分数：2.00）28.在对一组关键字为(54，38，96，23，15，72，60，45，83)的记录采用直接选择排序法进行排序时，整个排序过程需进行 1 趟才能够完成。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.已知某二叉树如下图所示，
9、试给出其二叉链表及顺序存储结构表示。 （分数：6.00）_30.设二维数组 A 56 的每个元素占 4 个字节，已知 Loc(a 00 )=1000，A 共占多少个字节?A 的终端结点 a 45 的起始地址为何?按行和按列优先存储时，a 25 的起始地址分别为何? （分数：6.00）_31.已知连通图的邻接矩阵如下，试画出它所表示的连通网及连通网的最小生成树。 （分数：6.00）_32.设散列函数为 H(key)=key%11，散列表长度为 11(散列地址空间为 010)，在给定表(SUN，MON，TUE，WED，THU，FRI，SAT)中，取单词的第一个字母在英语字母表中的序号为键值 K，构
10、造一散列表，并用线性探测法解决有关的地址冲突。 （分数：6.00）_33.画出对应于序列10，20，7，75，41，67，3，9，30，45的初始堆(堆顶元素取最小值)。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.设二叉树的结点类型定义如下： typedef struct node datatype data； struct node*lchild，*rchild； BinTree BinTree*t； 试编写一个计算二叉树深度的递归算法 int Depth(BinTree*t)。 （分数：7.00）_35.写出将一个无向图的邻接表转换或邻接矩阵的算法。 （分数：
11、7.00）_数据结构导论自考题模拟 6 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.能正确地实现预定的功能，满足具体问题的需要是指算法的_（分数：2.00）A.正确性 B.易读性C.健壮性D.时空性解析：考点 本题主要考查的知识点是算法的正确性。 算法的正确性是指能正确地实现预定的功能，满足具体问题的需要。2.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是_（分数：2.00）A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表 解析：3.已知一个顺序存储的线性
12、表，设每个结点需占 m 个存储单元，若第一个结点的地址为 d，则第 i 个结点的地址为_（分数：2.00）A.d+(i-1)*m B.d+i*mC.d-i*mD.d+(i+1)*m解析：考点 本题主要考查的知识点址顺序表结点存储地址的计算。 第 i 个结点的存储地址为 LOC(a i )=LOC(a 1 )+(i-1)*m=d+(i-1)*m。4.如果以链表作为栈的存储结构，则退栈操作时_（分数：2.00）A.必须判别栈是否满B.必须判别栈是否空 C.判别栈元素的类型D.对栈不作任何判别解析：5.若用一个有 6 个单元的数组来实现循环队列，rear 和 front 的初值分别为 0 和 3。则
13、从队列中删除一个元素，再添加两个元素后，rear 和 front 的值分别为_（分数：2.00）A.1 和 5B.2 和 4 C.4 和 2D.5 和 1解析：考点 主要考查的知识点是循环队列。 由此循环队列的 rear 和 front 的初值分别为 0 和 3，可知此时循环队列的 1、2、3 号单元为空，而4、5、0 号单元有元素存在，删除一个元素后，4 号单元元素被删除且 front+1，其后添加的两个元素将添加到 1 号和 2 号单元且：rear+2，则此时 rear 和 front 的值分别为 2 和 4。6.根据定义，树的叶子结点的度数_（分数：2.00）A.必大于 0B.必等于 0
14、 C.必等于 1D.必等于 2解析：7.在一棵深度为 H 的完全二叉树中，所含结点的个数不少于_ A.2H-1-1 B.2H-1 C.2H-1 D.2H（分数：2.00）A.B. C.D.解析：考点 主要考查的知识点是完全二叉树。 如果在一棵深度为 k(k1)的满二叉树上删去第 k 层上最右边的连续 j(0j2 k-1 )个结点，就得到一棵深度为 k 的完全二叉树。由此可知深度为 H 的完全二叉树结点数最少时其第 H 层的结点仅有一个，此时二叉树的结点总数为 2 H-1 个。8.二叉树若采用二叉链表结构表示，则对于 n 个结点的二叉树一定有_（分数：2.00）A.2n 个指针域，其中 n 个指
15、针为 NULLB.2n 个指针域，其中 n+1 个指针为 NULL C.2n-1 个指针域，其中 n 个指针为 NULLD.2n-1 个指针域，其中 n+1 个指针为 NULL解析：9.下列有关图的遍历的说法中不正确的是_（分数：2.00）A.连通图的深度优先搜索是一个递归过程B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C.非连通图不能用深度优先搜索法 D.图的遍历要求每一结点仅被访问一次解析：10.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用_（分数：2.00）A.求关键路径的方法B.求最短路径的 Dijkstra 方法C.广度优先遍历方法D.深度优先遍历方法
16、 解析：考点 本题主要考查的知识点是深度优先遍历方法。 采用深度优先遍历方法，若图中存在回路，同一结点将会在遍历序列中出现两次。11.散列表中由于散列到同一个地址而引起的“堆积”现象，是由_（分数：2.00）A.同义词之间发生冲突引起的B.非同义词之间发生冲突引起的 C.同义词之间或非同义词之间发生冲突引起的D.散列表“溢出”引起的解析：12.数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为_（分数：2.00）A.索引存储方法B.顺序存储方法C.链式存储方法D.散列存储方法 解析：13.下列说法中不正确的是_（分数：2.00）A.无向图的极大连通子图称为连通
17、分量B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索算法 解析：考点 主要考查的知识点是有向图的遍历。 遍历图的基本方法有两种：深度优先搜索和广度优先搜索。这两种方法都适用于有向图和无向图。14.一组记录的键值为(46，74，18，53，14，20，40，38，86，65)，利用堆排序的方法建立的初始堆为_（分数：2.00）A.(14，18，38，46，65，40，20，53，86，74)B.(14，38，18，46，65，20，40，53，86，74) C.(14，18，20，38，40
18、，46，53，65，74，86)D.(14，86，20，38，40，46，53，65，74，18)解析：15.对序列(22，86，19，49，12，30，65，35，18)进行一趟排序后得到的结果如下：(18，12，19，22，49，30，65，35，86)，则可以认为使用的排序方法是_（分数：2.00）A.选择排序B.冒泡排序C.快速排序 D.插入排序解析：二、填空题(总题数：13，分数：26.00)16.算法的时间性能是指算法包含的 1。 （分数：2.00）解析：计算量17.设有一批数据元素，为了最快地存储某元素，数据结构宜用 1 结构，为了方便插入一个元素，数据结构宜用链式存储结构。 （
19、分数：2.00）解析：顺序存储18.单链表中逻辑上相邻的两个元素在物理位置上 1 相邻。 （分数：2.00）解析：不一定19.用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234，为了得到 1342 的出栈顺序，相应的 S和 X 操作串为 1。 （分数：2.00）解析：SXSSXSXX20.循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列的元素个数是 1。 （分数：2.00）解析：(rear-front+m)%m21.一个顺序队列的第 5 个元素的存储地址是 200，第 10 个元素的存储地址是 225。每个元素的长度是5，则第
20、20 个元素的地址是 1。 （分数：2.00）解析：27522.若用后序遍历法遍历题下图所示的二叉树，其输出序列为 1。 （分数：2.00）解析：DBFHGECA23.一棵具有 n 个结点的树，所有非终端结点的度均为 k，则该树中叶子结点个数为 1。 （分数：2.00）解析：24.若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 1。 （分数：2.00）解析：6925. 1 是顺序存储与链式存储相结合的存储方法。 （分数：2.00）解析：邻接表26.一个图的最小生成树是图所有生成树中 1 最小的生成树。 （分数：2.00）解析：权总和27.查找表的逻辑结构是 1。 （分
21、数：2.00）解析：集合28.在对一组关键字为(54，38，96，23，15，72，60，45，83)的记录采用直接选择排序法进行排序时，整个排序过程需进行 1 趟才能够完成。 （分数：2.00）解析：8三、应用题(总题数：5，分数：30.00)29.已知某二叉树如下图所示，试给出其二叉链表及顺序存储结构表示。 （分数：6.00）_正确答案：()解析：二叉链表如下图所示： 顺序存储结构为： 30.设二维数组 A 56 的每个元素占 4 个字节，已知 Loc(a 00 )=1000，A 共占多少个字节?A 的终端结点 a 45 的起始地址为何?按行和按列优先存储时，a 25 的起始地址分别为何?
22、 （分数：6.00）_正确答案：()解析：因 4*5*6=120，所以 A04，05共占 120 个字节。 (2)a 45 的起始地址为： Loc(a 45 )=1000+120-4=1116 (3)按行优先顺序排列时： Loc(a 25 )=1000+(2*6+5)*4=1068 (4)按列优先顺序排列时： Loc(a 25 )=1000+(5*5+2)*4=110831.已知连通图的邻接矩阵如下，试画出它所表示的连通网及连通网的最小生成树。 （分数：6.00）_正确答案：()解析：所求连通网及最小生成树如下： 32.设散列函数为 H(key)=key%11，散列表长度为 11(散列地址空间
23、为 010)，在给定表(SUN，MON，TUE，WED，THU，FRI，SAT)中，取单词的第一个字母在英语字母表中的序号为键值 K，构造一散列表，并用线性探测法解决有关的地址冲突。 （分数：6.00）_正确答案：()解析：根据字母的顺序，所产生的序列为：19，13，20，23，20，6，19 则所求散列表为： 33.画出对应于序列10，20，7，75，41，67，3，9，30，45的初始堆(堆顶元素取最小值)。 （分数：6.00）_正确答案：()解析：所求初始堆如下图所示： 四、算法设计题(总题数：2，分数：14.00)34.设二叉树的结点类型定义如下： typedef struct nod
24、e datatype data； struct node*lchild，*rchild； BinTree BinTree*t； 试编写一个计算二叉树深度的递归算法 int Depth(BinTree*t)。 （分数：7.00）_正确答案：()解析：int Depth(BinTree*t) int hl，hr； if(t=NULL) return(0)； else hl=Depth(t-lchild)； hr=Depth(t-rchild)： if(hlhr) return(hl+1)： else return(hr+1)； 35.写出将一个无向图的邻接表转换或邻接矩阵的算法。 （分数：7.00
25、）_正确答案：()解析：算法描述如下： void Adjlist_to_Matrix(GraphTP_Adj*ga，GraphTp_Mat*gb) int i，j； ArcNodeTp*p； gb-vexnum=ga-vexnum； /读入顶点个数和边数 gb-arcnum=ga-arcnum； for(i=0；iga-vexnum；i+) for(j=0；jga-vexnum；j+) gb-arcsij=0； /初始化邻接矩阵 for(i=0；iga-vexnum；i+) p=ga-adjlisi.firstarc； while(p!=NULL) j=p-adjvex； ga-arcsij=1： p=p-nextarc；
