数据结构自考题-3

1、数据结构自考题 -3( 总分： 100.00 ，做题时间： 90 分钟 )一、单项选择题 ( 总题数： 15，分数： 30.00)1. 采用分治法进行排序的方法是 ( )A. 快速排序B 插入排序C.堆排序D 希尔排序(分数： 2.00 )A. VB.C.D.解析：2. 图的邻接矩阵表示法适用于表示 ( )A. 无向图B .有向图C .稠密图D .稀疏图(分数： 2.00 )A.B.C. VD.解析：3. 假设有一个数组，它的行号从 0到 8，列号从 0到 10，数组中每个元素所占的存储空间为3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要 ( ) 个存储单元才能完

2、全将此数组 存放进去。A. 240 B . 297C. 270 D . 300分数： 2.00 )A.B. VC.D.解析：4. 顺序存储结构 ( )A. 仅适合于静态查找表的存储B. 仅适合干动态查找表的存储C. 既适合静态又适合动态查找表的存储D. 既不适合静态又不适合动态查找表的存储分数： 2.00 )A.B.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)

3、(分数： 2.00 )A.B.C. VD.解析：6. 若进栈次序为 a,b,e ，且进栈和出栈可以穿插进行，则可能出现的含 3个元素的出栈序列个数是 ( ) A3 B5C6 D7分数： 2.00 )A.B. VC.D.解析：7. 在一棵具有 5 层的满二叉树中，结点总数为 ( ) 个A33 B32 C31 D30(分数： 2.00 )A.B.C. VD.解析：8. 设二叉树根结点的层次为0，一棵高度为 h 的满二叉树中的结点个数是 ( )A2h B 2h-1 C 2h-1 D2h+1-1(分数： 2.00 )A.B.C.D. V解析：9. 下面关于线性表的叙述错误的是 ( )A. 线性表采用顺

4、序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链接存储，不必占用一片连续的存储单元D. 线性袁采用链接存储，不便于插入和删除操作（分数:2.00 ）A. VB.C.D.解析：10. 数据结构是（）A. 种数据类型B. 数据的存储结构C. 一组性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00 ）A.B.C.D. V解析：11. 设有一个用线性探测法解决冲突得到的散列表:散列函数为H（k）=Kmod 11若要查找元素14，探测的次数（比较的次数）是A. 8 B . 9 C . 3 D . 6（分数：2.

5、00 ）A.B.C.D. V解析：12. 二维数组Mi,j的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4,列 下标j的范围从0到5。M按行存储时元素 M3,5的起始地址与 M按列存储时元素（）的起始地址相同。A. M2,4 B . M3,4 C . M3,5 D . M4,4（分数：2.00 ）A.B. VC.D.解析：13. 树最适合用来表示（）A.有序数据元素 B .无序数据元素C. 元素之间具有分支层次关系的数据D 元素之间无联系的数据（分数:2.00 ）A.B.C. VD.解析：14. 若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现

6、的出栈序列为（）A. 3,2,6,1,4,5 B . 3,4,2,1,6,5 C . 1,2,5,3,4,6 D . 5,6,4,2,3,1（分数：2.00 ）A.B. VC.D.解析：15. 如图所示二叉树的中序遍历序列是（）A. a b c d g e f B. d f e b a g cC. d b a e f c g D. d e f b a g c（分数：2.00 ）A.B.C. VD.解析：二、填空题（总题数：10,分数：20.00）16. 若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的1个结点。（分数：2.00 ）填空项1: （正确答案：第

7、一）解析：17. 1与数据元素本身的内容和形式无关。（分数：2.00 ）填空项1: （正确答案：数据的逻辑结构）解析：18. 具有N个顶点的无向完全图的边为，具有N个顶点无向完全图的弧为（分数：2.00 ）填空项 解析：1: (正确答案： n(n-1)/2 n(n-1) )19. 数组 A1.10 ，-2.6 ，2.8 以行优先顺序存储，设第一个元素的首地址是 100 ，每个元素占 3 个存储 长度的存储空间，则元素 A5,0,7 的存储地址为 1 。（分数： 2.00 ）填空项 1: （正确答案： 913 ）解析：进行一趟增量为 3的希尔排序， 则得到的结果为20. 若对关键字序列 （43,

8、02,80,48,26,57,15,73,21,24,66） 1。（分数： 2.00 ）填空项 1: （正确答案： 15,02,21,24,26,57,43,66,80,48,73 ）解析：21. 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是 1 。（分数： 2.00 ）填空项 1: （正确答案：一个数据元素可能有多个直接前趋和多个直接后继）解析：22. 由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1 。（分数： 2.00 ）填空项 1: （正确答案： 55）解析：23. 在分块查找法中，首先查找 1 ，然后再查找相应的 2（分数：

9、2.00 ）（正确答案：索引表块）1 条边。填空项 1:解析：24. N 个顶点的连通图，至少有（分数： 2.00 ）填空项 1: （正确答案： N 1）解析：25. n 个顶点且含有环路的无向连通图中，至少含有 1 条边 （分数： 2.00 ）填空项 1: （正确答案： n）解析： 解析 n 个顶点的无向连通图有环路且边最少时，此图仅有一个环路且所有顶点均在此环路中，此 时边数为 n 。三、解答题 （总题数： 3，分数： 20.00）26. 已知有一关键字序列为 97,86,53,108,72,34,215,146,11,68 ，如果我们采用直接选择排序方法对此序 列进行排序 ( 按照升序排

10、列 ) ，请给出每一趟的排序结果。分数： 5.00 )正确答案：(直接选择排序的过程为：从第 i趟开始时，当前的有序区和无序区分别为R1i和R1n(1 < -1<n-1)，则在该趟排序是从当前无序区中选出关键字最小的记录RK，将它与无序区中的第1个记录Ri交换，使R1i和Ri+1n分别变成新的有序区和新的无序区，每次排序都使有序区 增加一个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下：初始： 97,86,53,108,72,34,215,232,11,68第 1 趟： 1186,53,108,72,34,215,232,97,68第 2 趟： 11,3453,108

11、,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 趟： 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)解析：利用广义表的 h

12、ead 和 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)解析： 正确答案： (head(head(tail(head(L2) 解析：27. 图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex;struct node*next; Ed

13、geNode;typedef struct VertexType vertex;EdgeNode*firstedge; VertexNode;typedef VertexNode A djListMaxVertexNum; typedef structAdjList adjiist;int n,e;ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如 下图所示，请写岀重新定义的类型说明。（分数：5.00 ） 正确答案：(typeclef struct ArcNodeVNode*adjvex; / 该弧所指向的顶点的位置struct Arc

14、Node*nextarc; / 指向下一条弧的指针ArcNode;typedef struct VNodeVertexType data; / 顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针ArcNode*firstarc; / 指向第一条依附该顶点的弧 VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：四、算法阅读题(总题数：2,分数：20.00)28. 求下面算法中变量count的值：(假设n为2的乘幂，并且n >2)int Timeint ncount=0;x=2;w

15、hile(x < n/2) x*=2;count+;return(count)（分数：5.00 ） 正确答案：(count=log 2n)解析：二叉排序树的存储结构定义为以下类型：typedef int KeyType;typedef struct nodeKeyType key; /* 关键字项 */InfoType otherinfo; /*其它数据项 */struet node*lchild,*rchild; /*左、右孩子指针 */BSTNode,*BSTree;阅读算法f33，并回答问题: 对如图所示的二叉排序树T,写出f33(T,8)返回的指针所指结点的关键字;在哪些情况下算

16、法f33返回空指针？简述算法f33的功能。BSTNode*f33(BSTreeKeyType x)BSTNode*P;if(T=NULL)return NULL;p=f33(T > lehild,x);if(p!=NULL)return p;if(T > key > x)return T;return f33(T> rchild,x);(分数：15.00 )填空项1: (正确答案：10)解析：正确答案：仃是空树或T中所有结点的关键字均不大于给定值X时，返回空指针。)解析： 正确答案：(如果二叉排序树T中存在含有关键字大于给定值 X的结点，则返回指针指向它们中关键字最小

17、的结点，否则返回空指针。)解析：五、算法设计题(总题数：1,分数：10.00)29. 写岀向某个有序文件中插入一个记录的程序。(分数：10.00 )正确答案：(所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第3个参数，且设为d。若原文件中没有数据，则 d写入文件；若有数据，则找到第 1个比d大的数据i，先写入d，再将 i和其后各数据写回文件中，可通过调用fseek函数采实现插入。相应程序为：#include < stdio.h >#include < stdli

18、b.h >#include < io.h >#include < fcntl.h >#define LEN sizeof(int)void main(int argi,char*argc) int fp,i,d;if(argi < 3) printf("filename int/11")exit(0);d=atoi(argc2);fp=open(argc1,O_GREAT| 0_RDWRI O_BINARY,s_IREAD| S_IWRITE);while(1) if( read(fp,&I ,LEN)!=LEN)write(fp，&d,LEN):