1、数据结构自考题-8 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.在下面的程序中，语句 S 的执行次数为( ) for(i=1;i=n-1;i+) for(j=n;j=i;j-) S; （分数：2.00）A.B.C.D.2.数据结构是 ( ) A一种数据类型 B数据的存储结构 C一组性质相同的数据元素的集合 D相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00）A.B.C.D.3.已知一个向量的第一个元素的存储地址是 100，每个元素的长度为 2，则第 6 个元素的地址是 ( ) A120 B112 C110 D114（分
2、数：2.00）A.B.C.D.4.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( ) A每个结点所代表的数据元素都一样 B每个结点所代表的数据元素包含的数据项的个数要相等 C不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 D结点所代表的数据元素有同一特点（分数：2.00）A.B.C.D.5.若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录，则查询条件为 ( ) A(性别=“男“)OR(年龄60)OR(性别=“女“)OR(年龄55) B(性别=“男“)OR(年龄60)AND(性别=“
3、女“)OR(年龄55) C(性别=“男“)AND(年龄60)OR(性别=“女“)AND(年龄55) D(性别=“男“)AND(年龄60)AND(性别=“女“)AND(年龄55)（分数：2.00）A.B.C.D.6.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( ) AFEDCBA BABCDEF CFDECBA DFBDCEA（分数：2.00）A.B.C.D.7.下面的查找方式中，可以对无序表进行查找的是( ) A顺序查找 B二分查找 C二叉排序树 DB-树上的查找（分数：2.00）A.B.C.D.8.在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，
4、若在 p，q 之间插入 s 结点，则执行( )操作。 Asnext=pnext;pnext=s; Bqnext=s;snext=p; Cpnext=snext;snext=p; Dpnext=s;snext=q;（分数：2.00）A.B.C.D.9.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( ) A不一定相同 B都相同 C都不相同 D互为逆序（分数：2.00）A.B.C.D.10.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2.00）A.B.C.
5、D.11.按值可否分解，数据类型通常可分为两类，它们是 ( ) A静态类型和动态类型 B原子类型和表类型 C原子类型和结构类型 D数组类型和指针类型（分数：2.00）A.B.C.D.12.带行表的三元组表是稀疏矩阵的一种 ( ) A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构（分数：2.00）A.B.C.D.13.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目（分数：2.00）A.B.C.D.14.如图所示的带权无向图的最小生成树的权为 ( ) （分数：2.00）A.B.C.
6、D.15.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( ) A3 B5 C6 D7（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.设线性表(a 1，a 2，a 500)元素的值由小到大排列。对一个给定的 k 值，用二分法检索查找表中与 k相等的元素，在检索不成功的情况下，至多需比较 1 次。（分数：2.00）填空项 1:_17.删除双向循环链表中*p 的前驱结点(存在)应执行的语句是_。（分数：2.00）填空项 1:_18.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单
7、元称为_。（分数：2.00）填空项 1:_19.广义表的深度是指 1。（分数：2.00）填空项 1:_20.ISAM 文件采用_索引结构，而 VSAM 文件采用_索引结构。（分数：2.00）填空项 1:_21.如图所示的有向图中含有_个强连通分量。 （分数：2.00）填空项 1:_22.对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是_。（分数：2.00）填空项 1:_23.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_24.对无向图，其邻接矩阵是一个关于 1 对称的矩阵
8、。（分数：2.00）填空项 1:_25.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_三、解答题(总题数：4，分数：20.00)26.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi表示)。 （分数：5.00）_27.在一棵二叉树中，度为 O 的结点个数与度为 2 的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有 200 个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为 2 的结点?多少个度为 1 的结点?如果有 201 个结点呢?（分数：5.00）_28.已知有一关键字序列为 486,79,596
9、,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_29.已知连通图如下： （分数：5.00）_四、算法阅读题(总题数：3，分数：20.00)30.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)； push(s,e); push(s,x); pop(s,x); push(s,h);
10、 while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) （分数：5.00）_阅读下列算法，并回答问题： （分数：10.00）_31.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_五、算法设计题(总题数：1，分数：10.00)32.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_数据结构自考题-8 答案解析(总分：10
11、0.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.在下面的程序中，语句 S 的执行次数为( ) for(i=1;i=n-1;i+) for(j=n;j=i;j-) S; （分数：2.00）A.B. C.D.解析：2.数据结构是 ( ) A一种数据类型 B数据的存储结构 C一组性质相同的数据元素的集合 D相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00）A.B.C.D. 解析：3.已知一个向量的第一个元素的存储地址是 100，每个元素的长度为 2，则第 6 个元素的地址是 ( ) A120 B112 C110 D114（分数：2.00）A.B.C.
12、 D.解析：4.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( ) A每个结点所代表的数据元素都一样 B每个结点所代表的数据元素包含的数据项的个数要相等 C不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 D结点所代表的数据元素有同一特点（分数：2.00）A.B.C. D.解析：5.若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录，则查询条件为 ( ) A(性别=“男“)OR(年龄60)OR(性别=“女“)OR(年龄55) B(性别=“男“)OR(年龄60)AND(性别=“女“)OR
13、(年龄55) C(性别=“男“)AND(年龄60)OR(性别=“女“)AND(年龄55) D(性别=“男“)AND(年龄60)AND(性别=“女“)AND(年龄55)（分数：2.00）A.B.C. D.解析：6.已知二叉树的中序序列和后序序列均为 ABCDEF，则该二叉树的先序序列为 ( ) AFEDCBA BABCDEF CFDECBA DFBDCEA（分数：2.00）A. B.C.D.解析：解析 对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列、中序序列和后序序列。7.下面的查找方式中，可以对无序表进行查找的是( ) A顺序查找 B二分查
14、找 C二叉排序树 DB-树上的查找（分数：2.00）A. B.C.D.解析：8.在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行( )操作。 Asnext=pnext;pnext=s; Bqnext=s;snext=p; Cpnext=snext;snext=p; Dpnext=s;snext=q;（分数：2.00）A.B. C.D.解析：9.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 ( ) A不一定相同 B都相同 C都不相同 D互为逆序（分数：2.00）A.B. C.D.解析：10.如果我们采用二分查找法查找一个长
15、度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2.00）A.B. C.D.解析：11.按值可否分解，数据类型通常可分为两类，它们是 ( ) A静态类型和动态类型 B原子类型和表类型 C原子类型和结构类型 D数组类型和指针类型（分数：2.00）A.B.C. D.解析：解析 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。12.带行表的三元组表是稀疏矩阵的一种 ( ) A顺序存储结构 B链式存储结构 C索引存储结构 D散列存储结构（分数：2.00）A. B
16、.C.D.解析：13.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目（分数：2.00）A. B.C.D.解析：14.如图所示的带权无向图的最小生成树的权为 ( ) （分数：2.00）A.B.C. D.解析：解析 根据最小生成树的构造过程，可知在构造本题中无向图的最少生成树时，将选取权值分别为 10、14、12、18 的边，所以此最小生成树的权即各边权值之和即 54。15.若进栈次序为 a,b,e，且进栈和出栈可以穿插进行，则可能出现的含 3 个元素的出栈序列个数是 ( ) A3 B5 C6
17、D7（分数：2.00）A.B. C.D.解析：二、填空题(总题数：10，分数：20.00)16.设线性表(a 1，a 2，a 500)元素的值由小到大排列。对一个给定的 k 值，用二分法检索查找表中与 k相等的元素，在检索不成功的情况下，至多需比较 1 次。（分数：2.00）填空项 1:_ （正确答案：9）解析：17.删除双向循环链表中*p 的前驱结点(存在)应执行的语句是_。（分数：2.00）填空项 1:_ （正确答案：pprior=ppriorprior; ppriornext=p; (或 ppriorpriornext=p; pprior=ppriorprior;）解析：18.就文件而言
18、，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单元称为_。（分数：2.00）填空项 1:_ （正确答案：逻辑记录 物理记录）解析：19.广义表的深度是指 1。（分数：2.00）填空项 1:_ （正确答案：广义表展开后所含括号的最大层数）解析：20.ISAM 文件采用_索引结构，而 VSAM 文件采用_索引结构。（分数：2.00）填空项 1:_ （正确答案：静态 动态）解析：21.如图所示的有向图中含有_个强连通分量。 （分数：2.00）填空项 1:_ （正确答案：2）解析：22.对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是_。（分数：2.00
19、）填空项 1:_ （正确答案：O(nlog 2n) O(n2)）解析：23.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_ （正确答案：基地址）解析：24.对无向图，其邻接矩阵是一个关于 1 对称的矩阵。（分数：2.00）填空项 1:_ （正确答案：主对角线）解析：25.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_ （正确答案：索引表块）解析：三、解答题(总题数：4，分数：20.00)26.请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi
20、表示)。 （分数：5.00）_正确答案：(答：A，B，C 对应的图分别为： )解析：27.在一棵二叉树中，度为 O 的结点个数与度为 2 的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有 200 个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为 2 的结点?多少个度为 1 的结点?如果有 201 个结点呢?（分数：5.00）_正确答案：(在一棵二叉树中，度数为 0 的结点(叶结点)的个数总是比度为 2 的结点的个数多 1。根据完全二叉树的定义：若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2，并且最下一层上的结点都集中在该层最左边的若干住置上，则
21、我们可以得出这样一个结论：在一棵完全二叉树上，或者没有度为1 的结点。则根据以上分析，我们可以这样计算此题：设度数为 2 的结点有 n 个，则必有 n+1 个度为 0 的结点，即度数为 2 和度数为 0 的结点数之和为 2n+1(是奇数)，于是得出，如果一棵完全二叉树的结点总数为奇数，则此树中必然不存在度为 1 的结点，若完全二叉树中结点总数为偶数，则必然有 1 个度为 1 的结点存在，于是若完全二叉树中有 200 个结点，就必有 100 个对结点，99 个度数为 2 的结点，12 个度数为 1 的结点，如果二叉树中有 201 个结点，则必有 101 个叶结点，100 个度数为 2 的结点，没
22、有度数为 1的结点。)解析：28.已知有一关键字序列为 486,79,596,34,900,120,789,179,703,307)，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。（分数：5.00）_正确答案：(基数排序的基本思想是：从低位到高位依次对 kj(j=d-1，d-20)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果： 初始：486,79,596,34,900,120,789,179,703,307 第 1 趟：(按个位进行排序)：120,900,703,34,486,596,307,79,179,389 第 2 趟：(按十位进行排序
23、)：307,703,900,120,34,79,179,486,789,596 第 3 趟：(按百位进行排序)：34,79,120,179,307,486,596,703,789,900)解析：29.已知连通图如下： （分数：5.00）_正确答案：( )解析：四、算法阅读题(总题数：3，分数：20.00)30.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)； push(s,e); pus
24、h(s,x); pop(s,x); push(s,h); while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) （分数：5.00）_正确答案：(此题的输出结果是 hello。)解析：阅读下列算法，并回答问题： （分数：10.00）_正确答案：(3)解析：_正确答案：(返回无向图 g 中连通分量的个数。)解析：31.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok
25、; )/A（分数：5.00）_正确答案：(本程序实现的功能就是：如果 L 的长度不小于 2，则将首元结点删去并插入到表尾。)解析：五、算法设计题(总题数：1，分数：10.00)32.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_正确答案：(所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第 3 个参数，且设为 d。若原文件中没有数据，则 d 写入文件；若有数据，则找到第 1 个比 d 大的数据 i，先写入 d，再将 i 和其后各数据写回文件中，可通过调用 fseek
26、 函数采实现插入。相应程序为： #includestdio.h #includestdlib.h #includeio.h #includefcntl.h #define LEN sizeof(int) void main(int argi,char*argc) 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*/)解析：
