1、数据结构自考题-3 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.采用分治法进行排序的方法是( ) A快速排序 B插入排序 C堆排序 D希尔排序（分数：2.00）A.B.C.D.2.图的邻接矩阵表示法适用于表示 ( ) A无向图 B有向图 C稠密图 D稀疏图（分数：2.00）A.B.C.D.3.假设有一个数组，它的行号从 0 到 8，列号从 0 到 10，数组中每个元素所占的存储空间为 3 个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。 A240 B297 C270
2、 D300（分数：2.00）A.B.C.D.4.顺序存储结构 ( ) A仅适合于静态查找表的存储 B仅适合干动态查找表的存储 C既适合静态又适合动态查找表的存储 D既不适合静态又不适合动态查找表的存储（分数：2.00）A.B.C.D.5.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( ) A(5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8) C(5,1,4,3,2,6,8,7) D(8,7,6,5,4,3,2,1)（分数：2.00）A.B.C.D.6.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现
3、的含 3 个元素的出栈序列个数是 ( ) A3 B5 C6 D7（分数：2.00）A.B.C.D.7.在一棵具有 5 层的满二叉树中，结点总数为( )个。 A33 B32 C31 D30（分数：2.00）A.B.C.D.8.设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是( ) A2 h B2 h-1 C2 h-1 D2 h+1-1（分数：2.00）A.B.C.D.9.下面关于线性表的叙述错误的是( ) A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性袁采用链接存储，不便
4、于插入和删除操作（分数：2.00）A.B.C.D.10.数据结构是 ( ) A一种数据类型 B数据的存储结构 C一组性质相同的数据元素的集合 D相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00）A.B.C.D.11.设有一个用线性探测法解决冲突得到的散列表： （分数：2.00）A.B.C.D.12.二维数组 Mi,j的元素是 4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5。M 按行存储时元素 M3,5的起始地址与 M 按列存储时元素( )的起始地址相同。AM2,4 BM3,4 CM3,5 DM4,4（分数：2.00
5、）A.B.C.D.13.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据（分数：2.00）A.B.C.D.14.若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( ) A3,2,6,1,4,5 B3,4,2,1,6,5 C1,2,5,3,4,6 D5,6,4,2,3,1（分数：2.00）A.B.C.D.15.如图所示二叉树的中序遍历序列是( ) （分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩
6、子树的后序遍历序中的 1个结点。（分数：2.00）填空项 1:_17. 1 与数据元素本身的内容和形式无关。（分数：2.00）填空项 1:_18.具有 N 个顶点的无向完全图的边为_，具有 N 个顶点无向完全图的弧为_。（分数：2.00）填空项 1:_19.数组 A110，-26，28以行优先顺序存储，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5,0,7的存储地址为 1。（分数：2.00）填空项 1:_20.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00
7、）填空项 1:_21.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_22.由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_23.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_24.N 个顶点的连通图，至少有 1 条边。（分数：2.00）填空项 1:_25.n 个顶点且含有环路的无向连通图中，至少含有 1 条边。（分数：2.00）填空项 1:_三、解答题(总题数：3，分数：20.00)26.已知有一关键字序列为 97,86,53,1
8、08,72,34,215,146,11,68，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_利用广义表的 head 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(head(tail(L); 分别写出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。（分数：10.00）_27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int ad
9、jvex; struct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_四、算法阅读题(总题数：2，分数：20.00)28.求下面算法中变量
10、 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.
11、00）填空项 1:_五、算法设计题(总题数：1，分数：10.00)29.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_数据结构自考题-3 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.采用分治法进行排序的方法是( ) A快速排序 B插入排序 C堆排序 D希尔排序（分数：2.00）A. B.C.D.解析：2.图的邻接矩阵表示法适用于表示 ( ) A无向图 B有向图 C稠密图 D稀疏图（分数：2.00）A.B.C. D.解析：3.假设有一个数组，它的行号从 0 到 8，列号从 0 到 10，数组中每个元素所占的存储空间为 3
12、 个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。 A240 B297 C270 D300（分数：2.00）A.B. C.D.解析：4.顺序存储结构 ( ) A仅适合于静态查找表的存储 B仅适合干动态查找表的存储 C既适合静态又适合动态查找表的存储 D既不适合静态又不适合动态查找表的存储（分数：2.00）A.B.C. D.解析：5.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第 1 个元素为基准的一次划分的结果为 ( ) A(5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8) C(5,1
13、,4,3,2,6,8,7) D(8,7,6,5,4,3,2,1)（分数：2.00）A.B.C. D.解析：6.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( ) A3 B5 C6 D7（分数：2.00）A.B. C.D.解析：7.在一棵具有 5 层的满二叉树中，结点总数为( )个。 A33 B32 C31 D30（分数：2.00）A.B.C. D.解析：8.设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是( ) A2 h B2 h-1 C2 h-1 D2 h+1-1（分数：2.00）A.B.C.D. 解析：9.下面关于线性
14、表的叙述错误的是( ) A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性袁采用链接存储，不便于插入和删除操作（分数：2.00）A. B.C.D.解析：10.数据结构是 ( ) A一种数据类型 B数据的存储结构 C一组性质相同的数据元素的集合 D相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00）A.B.C.D. 解析：11.设有一个用线性探测法解决冲突得到的散列表： （分数：2.00）A.B.C.D. 解析：12.二维数组 Mi,j的元素是 4 个字符(每个字符占一个存储单元)组
15、成的串，行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5。M 按行存储时元素 M3,5的起始地址与 M 按列存储时元素( )的起始地址相同。AM2,4 BM3,4 CM3,5 DM4,4（分数：2.00）A.B. C.D.解析：13.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据（分数：2.00）A.B.C. D.解析：14.若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为( ) A3,2,6,1,4,5 B3,4,2,1,6,5 C1,2,5,3,4,6 D5,6,4,2
16、,3,1（分数：2.00）A.B. C.D.解析：15.如图所示二叉树的中序遍历序列是( ) （分数：2.00）A.B.C. D.解析：二、填空题(总题数：10，分数：20.00)16.若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的 1个结点。（分数：2.00）填空项 1:_ （正确答案：第一）解析：17. 1 与数据元素本身的内容和形式无关。（分数：2.00）填空项 1:_ （正确答案：数据的逻辑结构）解析：18.具有 N 个顶点的无向完全图的边为_，具有 N 个顶点无向完全图的弧为_。（分数：2.00）填空项 1:_ （正确答案：n(n-1)/2 n
17、(n-1)）解析：19.数组 A110，-26，28以行优先顺序存储，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5,0,7的存储地址为 1。（分数：2.00）填空项 1:_ （正确答案：913）解析：20.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_ （正确答案：15,02,21,24,26,57,43,66,80,48,73）解析：21.多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1。（分数：2.00）填空项 1:_
18、 （正确答案：一个数据元素可能有多个直接前趋和多个直接后继）解析：22.由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_ （正确答案：55）解析：23.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_ （正确答案：索引表块）解析：24.N 个顶点的连通图，至少有 1 条边。（分数：2.00）填空项 1:_ （正确答案：N1）解析：25.n 个顶点且含有环路的无向连通图中，至少含有 1 条边。（分数：2.00）填空项 1:_ （正确答案：n）解析：解析 n 个顶点的无向连通图有环路且边
19、最少时，此图仅有一个环路且所有顶点均在此环路中，此时边数为 n。三、解答题(总题数：3，分数：20.00)26.已知有一关键字序列为 97,86,53,108,72,34,215,146,11,68，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_正确答案：(直接选择排序的过程为：从第 i 趟开始时，当前的有序区和无序区分别为 R1i和 R1n(1-1n-1)，则在该趟排序是从当前无序区中选出关键字最小的记录 RK，将它与无序区中的第 1 个记录 Ri交换，使 R1i和 Ri+1n分别变成新的有序区和新的无序区，每次排序都使有序区增加一
20、个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下：初始：97,86,53,108,72,34,215,232,11,68 第 1 趟：1186,53,108,72,34,215,232,97,68 第 2 趟：11,3453,108,72,86,215,232,97,68 第 3 趟：11,34,531108,72,86,215,232,97,68 第 4 趟：11,34,53,6872,86,215,232,97,108 第 5 趟：11,34,53,68,7286,215,232,97,108 第 6 趟：11,34,53,68,72,86215,232,97,108 第 7
21、 趟：11,34,53,68,72,86,97232,215,108 第 8 趟：11,34,53,68,72,86,97,108215,232 第 9 趟：11,34,53,68,72,86,97,108,215,232)解析：利用广义表的 head 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(head(tail(L); 分别写出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。（分数：10.00）_正确答案：(head(tail(L1)解析：_正确答案：(h
22、ead(head(tail(head(L2)解析：27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作
23、，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_正确答案：(typeclef struct ArcNode VNode*adjvex; /该弧所指向的顶点的位置 struct ArcNode*nextarc; /指向下一条弧的指针 ArcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef st
24、ruct AdjList adjList; int n,e; ALGraph;)解析：四、算法阅读题(总题数：2，分数：20.00)28.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_正确答案：(count=log 2n)解析：二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType ot
25、herinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）填空项 1:_ （正确答案：10）解析：_正确答案：(T 是空树或 T 中所有结点的关键字均不大于给定值 X 时，返回空指针。)解析：_正确答案：(如果二叉排序树 T 中存在含有关键字大于给定值 X 的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。)解析：五、算法设计题(总题数：1，分数：10.00)29.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_正确答案：(
26、所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第 3 个参数，且设为 d。若原文件中没有数据，则 d 写入文件；若有数据，则找到第 1 个比 d 大的数据 i，先写入 d，再将 i 和其后各数据写回文件中，可通过调用 fseek 函数采实现插入。相应程序为： #includestdio.h #includestdlib.h #includeio.h #includefcntl.h #define LEN sizeof(int) void main(int argi,char*ar
27、gc) int fp,i,d; if(argi3) printf(“filename int/11“) exit(0); d=atoi(argc2); fp=open(argc1,O_GREAT| O_RDWRI O_BINARY,s_IREAD| S_IWRITE); while(1) if( read(fp,) if(i=d) /*文件中读出数据 i，若 i=d，则先存 d*/ do fseek(fp,-1L*lan,SEEK_CUR); /*文件指针后退 1 个记录*/ write(fp, /*d 写到文件中*/ d=i; /*原 i 作 d，以便处理其他数据*/ while(read(fp, write(fp，/*继续读数据，并判别文件是否结束*/ break; close(fp); /*main*/)解析：
