1、数据结构自考题分类模拟 1及答案解析(总分：71.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.内部排序的方法有许多种， _ 方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（分数：2.00）A.归并排序B.插入排序C.快速排序D.选择排序2.对长度为 n的关键字序列进行堆排序的空间复杂度为 _（分数：2.00）A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)3.在一棵完全二叉树的顺序存储方式中，若编号为 t的结点有右孩子，则此结点右孩子的编号为 _（分数：2.00）A.2tB.2t-1C.2t
2、+1D.t/24.排序的重要目的是为了以后对已排序的数据元素进行 _（分数：2.00）A.打印输出B.分类C.查找D.合并5.设有一个无向图 G=(V,E)和 G“=(V“,E“)，如果 G“是 G的生成树，则下面不正确的说法是 _（分数：2.00）A.G“为 G的子图B.G“为 G的连通分量C.G“为 G的极小连通子图且 V“=VD.G“是 G的一个无环子图6.广义表()和()的长度分别是_和()的长度分别是_（分数：2.00）A.0；1B.1；1C.0；0D.1；07.含有 n个顶点和 e条边的有向图的邻接矩阵中，零元素的个数是_ A.e B.2e C.n2-2e D.n2-e（分数：2.
3、00）A.B.C.D.8.堆(Heap)是 _（分数：2.00）A.完全二叉树B.线性表C.二叉排序树D.平衡二叉树9.如图所示二叉树的中序遍历序列是 _ （分数：2.00）A.a b c d g e fB.d f e b a g cC.d b a e f c gD.d e f b a g c10.对于栈顶指针为 top的顺序栈 S，判断栈空的条件是_（分数：2.00）A.top=0B.top0C.top=StackSize-1D.top=StackSize二、填空题(总题数：8，分数：16.00)11.就文件而言，按用户的观点所确定的基本存储单元称为 1。按外设的观点所确定的基本存储单元称为
4、 2。 （分数：2.00）12.在 5阶 B-树中，每个结点至多含 4个关键字，除根结点之外，其他结点至少含 1 个关键字。 （分数：2.00）13.对表长为 9000的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。 （分数：2.00）14.已知广义表 A=(a,b,c)，(d,e,f)，则运算 head(head(tail(tail(A)= 1。 （分数：2.00）15.在双向链表中，每个结点含有两个指针域，一个指向其 1 结点，另一个指向 2 结点。 （分数：2.00）16.N个顶点的连通图，至少
5、有 1 条边。 （分数：2.00）17.设有一元多项式 A(x)=7+3x+10x 30 -4X 100 +13x 101 ，用单链表给出 A(x)的存储表示为 1。 （分数：2.00）18.一组字符(a，b，c，d)在文中出现的次数分别为(7，6，3，5)，字符“d“的哈夫曼编码的长度为 1。 （分数：2.00）三、解答题(总题数：2，分数：15.00)(1)画出对表长为 13的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37时所需进行的比较次数。（分数：10.00）_19.
6、图的邻接表的类型定义如下所示： #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; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示
7、实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_四、算法阅读题(总题数：2，分数：10.00)阅读下列算法，并回答问题： void f32(int r, int n) Int i, j; for(i=2; in; i+) r0=ri; j=i-1; while(r0rj) rj+1=rj; j=j-1; rj+1=r0; （分数：5.00）(1).这是哪一种插入排序算法?该算法是否稳定?（分数：2.50）_(2).设置 r0的作用是什么?（分数：2.50）_20.求下面算法中变量 count的值：(假设 n为 2的乘幂，并且 n2) int Time int n count=0
8、;x=2; while(xn/2) x * =2;count+; return(count) （分数：5.00）_五、算法设计题(总题数：1，分数：10.00)21.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。 （分数：10.00）_数据结构自考题分类模拟 1答案解析(总分：71.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.内部排序的方法有许多种， _ 方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（分数：2.00）A.归并排序B.插入排序 C.快速排序D.选择排序解析：2.对长度为 n的关键字序
9、列进行堆排序的空间复杂度为 _（分数：2.00）A.O(log2n)B.O(1) C.O(n)D.O(n*log2n)解析：解析 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 0(1)，但它是不稳定的。3.在一棵完全二叉树的顺序存储方式中，若编号为 t的结点有右孩子，则此结点右孩子的编号为 _（分数：2.00）A.2tB.2t-1C.2t+1 D.t/2解析：4.排序的重要目的是为了以后对已排序的数据元素进行 _（分数：2.00）A.打印输出B.分类C.查找 D.合并解析：5.设有一个无向图 G=(V,E)和 G“=(V“,E“)，如果 G“
10、是 G的生成树，则下面不正确的说法是 _（分数：2.00）A.G“为 G的子图B.G“为 G的连通分量 C.G“为 G的极小连通子图且 V“=VD.G“是 G的一个无环子图解析：6.广义表()和()的长度分别是_和()的长度分别是_（分数：2.00）A.0；1 B.1；1C.0；0D.1；0解析：考点 广义表的长度的计算 解析 根据广义表长度的计算公式，广义表()和()的长度分别是 0和 1。7.含有 n个顶点和 e条边的有向图的邻接矩阵中，零元素的个数是_ A.e B.2e C.n2-2e D.n2-e（分数：2.00）A.B.C.D. 解析：考点 图的邻接矩阵中零元素的个数 解析 含有 n
11、个顶点和 e条边的有向图的邻接矩阵中，零元素的个数是 n 2 -e。8.堆(Heap)是 _（分数：2.00）A.完全二叉树B.线性表 C.二叉排序树D.平衡二叉树解析：9.如图所示二叉树的中序遍历序列是 _ （分数：2.00）A.a b c d g e fB.d f e b a g cC.d b a e f c g D.d e f b a g c解析：10.对于栈顶指针为 top的顺序栈 S，判断栈空的条件是_（分数：2.00）A.top=0B.top0 C.top=StackSize-1D.top=StackSize解析：考点 判断栈空的条件 解析 对于栈顶指针为 top的顺序栈 S，判断
12、栈空的条件是 S.top0。二、填空题(总题数：8，分数：16.00)11.就文件而言，按用户的观点所确定的基本存储单元称为 1。按外设的观点所确定的基本存储单元称为 2。 （分数：2.00）解析：逻辑记录 物理记录12.在 5阶 B-树中，每个结点至多含 4个关键字，除根结点之外，其他结点至少含 1 个关键字。 （分数：2.00）解析：213.对表长为 9000的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。 （分数：2.00）解析：308.514.已知广义表 A=(a,b,c)，(d,e,f)，则
13、运算 head(head(tail(tail(A)= 1。 （分数：2.00）解析：e15.在双向链表中，每个结点含有两个指针域，一个指向其 1 结点，另一个指向 2 结点。 （分数：2.00）解析：前趋 后继16.N个顶点的连通图，至少有 1 条边。 （分数：2.00）解析：N117.设有一元多项式 A(x)=7+3x+10x 30 -4X 100 +13x 101 ，用单链表给出 A(x)的存储表示为 1。 （分数：2.00）解析：18.一组字符(a，b，c，d)在文中出现的次数分别为(7，6，3，5)，字符“d“的哈夫曼编码的长度为 1。 （分数：2.00）解析：2 考点 哈夫曼编码 解
14、析 先构造出相应的哈夫曼树，然后进行编码。三、解答题(总题数：2，分数：15.00)(1)画出对表长为 13的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37时所需进行的比较次数。（分数：10.00）_正确答案：()解析：_正确答案：()解析：319.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode; typedef struct
15、VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_正确答案：()解析：typeclef struct ArcNode VNode*adjvex; /该弧所指向的顶点的位置 struct ArcNode*nextarc
16、; /指向下一条弧的指针 ArcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef struct AdjList adjList; int n,e; ALGraph;四、算法阅读题(总题数：2，分数：10.00)阅读下列算法，并回答问题： void f32(int r, int n) Int i, j; for(i=2; in; i+) r0=ri; j=i-1;
17、 while(r0rj) rj+1=rj; j=j-1; rj+1=r0; （分数：5.00）(1).这是哪一种插入排序算法?该算法是否稳定?（分数：2.50）_正确答案：()解析：直接插入排序，该算法是稳定的。(2).设置 r0的作用是什么?（分数：2.50）_正确答案：()解析：r0的作用是监视哨兵。 考点 排序算法的判定 解析 根据算法，可知其为直接插入排序的算法，该算法是稳定的。程序中 r0的作用是监视哨兵。20.求下面算法中变量 count的值：(假设 n为 2的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x * =2;coun
18、t+; return(count) （分数：5.00）_正确答案：()解析：count=log 2 n五、算法设计题(总题数：1，分数：10.00)21.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。 （分数：10.00）_正确答案：()解析：可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下： Alterbubblesort(r) /*交替扫描法起泡排序*/ Reetype R; int i,j，temp，flag; /*设置扫描标志 flag*/ flag=True; i=0; while(flag) /*开始扫描*/ flag=False; for(j=n=i,ji,j-) if(Rj,keyRj-1,key) flag=True; temp=Rj; Rj=Rj-1; Rj-1=temp; for(j=l;jn-1;j+) if(Rj.keyRj+1.key) flag=True; temp=Rj; Rj=Ri+1; Rj-1=temp; i+; /*往右扫描*/ /*AIterbubblesort*/
