1、数据结构自考题-6 及答案解析(总分：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
2、.D.3.设栈 S 和队列 Q 的初始状态为空，元素 e1、e 2、e 3、e 4、e 5和 e6依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序是 e2、e 3、e 4、e 5、e 6、e 1，则栈 S 的容量至少应该是( ) A6 B4 C3 D2（分数：2.00）A.B.C.D.4.在 Hash 函数 H(k)=k MOD m 中，一般来讲，m 应取( ) A奇数 B偶数 C素数 D充分大的数（分数：2.00）A.B.C.D.5.已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时，前两趟排序的结果为 (35,51,24,
3、13,68,56,42,77,93) (35,24,13,51,56,42,68,77,93) 所采用的排序方法是 ( ) A插入排序 B冒泡排序 C快速排序 D归并排序（分数：2.00）A.B.C.D.6.如图所示二叉树的中序遍历序列是( ) （分数：2.00）A.B.C.D.7.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00）A.B.C.D.8.森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4
4、，那么当把森林 T 转换成一棵二叉树后，其根结点的左孩子上有( )个结点。 An 1-1 Bn 1 Cn 1+n2+n3 Dn 2+n3+n4（分数：2.00）A.B.C.D.9.循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是( ) A(rear-front+m)MODm Brear-fomt+1 Crear-fribt-1 Drear-front（分数：2.00）A.B.C.D.10.在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p，q 之间插入 s 结点，则执行( )操作。 Asnext=pnext;p
5、next=s; Bqnext=s;snext=p; Cpnext=snext;snext=p; Dpnext=s;snext=q;（分数：2.00）A.B.C.D.11.堆(Heap)是( ) A完全二叉树 B线性表 C二叉排序树 D平衡二叉树（分数：2.00）A.B.C.D.12.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 ( ) Apnext=r; qnext=rnext; rnext=q; Bpnext=r; rnext=q; qnext=rnext; Crnext=q; qnext=rnext; pnext=r; Drnex
6、t=q; pnext=r; qnext=rnext;（分数：2.00）A.B.C.D.13.下列说法中正确的是( ) A二叉树中任何一个结点的度都为 2 B二叉树的度为 2 C任何一棵二叉树中至少有一个结点的度为 2 D一棵二叉树的度可以小于 2（分数：2.00）A.B.C.D.14.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( ) A数据元素具有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等（分数：2.00）A.B.C.D.15.下列排序算法中，其时间复杂度和记录的初始排列无关的是
7、( ) A插入排序 B堆排序 C快速排序 D冒泡排序（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.设线性表 L=(a1，a 2，a n)(n2)，表中元素按值的递增顺序排列。对一个给定的值 k，分别用顺序检索和二分法检索查找与 k 相等的元素，比较次数分别为 s 和 b，若检索不成功，则 s 和 b 的数量关系是 1。（分数：2.00）填空项 1:_17.由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_18.在二叉排序树中，其左子树中任何一个结点的关键字一定 1 其右子树的各结点的
8、关键字。（分数：2.00）填空项 1:_19.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。（分数：2.00）填空项 1:_20.对无向图，其邻接矩阵是一个关于 1 对称的矩阵。（分数：2.00）填空项 1:_21.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 1 结构也无特殊要求。（分数：2.00）填空项 1:_22.含 n 个顶点的无向连通图中至少含有 1 条边。（分数：2.00）填空项 1:_23.对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功
9、的平均查找长度为 1。（分数：2.00）填空项 1:_24.查找表中主关键字指的是_，次关键字指的是_。（分数：2.00）填空项 1:_25.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_三、解答题(总题数：4，分数：20.00)26.已知连通图如下： （分数：5.00）_27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode
10、; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_28.对于如图所示的二叉树，请画出其顺序存储结构图。 （分数：5.00）_29.假设有一个长度为 n 的有序序列，在进行查找时，可以
11、借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。（分数：5.00）_四、算法阅读题(总题数：3，分数：20.00)30.请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft(i-); （分数：5.00）_31.求下面算法中变量 count 的值：(假设 n 为 2 的乘幂，并且 n2) int Time int n count=0;x=2; while(xn/2) x*=2;count+; return(count) （分数：5.00）_假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下
12、： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）_五、算法设计题(总题数：1，分数：10.00)32.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。（分数：10.00）_数据结构自考题-6 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.线性
13、结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( ) A每个结点所代表的数据元素都一样 B每个结点所代表的数据元素包含的数据项的个数要相等 C不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 D结点所代表的数据元素有同一特点（分数：2.00）A.B.C. D.解析：2.邻接表存储结构下图的广度优先遍历算法结构类似于树的( ) A先根遍历 B后根遍历 C按层遍历 D先序遍历（分数：2.00）A.B.C. D.解析：3.设栈 S 和队列 Q 的初始状态为空，元素 e1、e 2、e 3、e 4、e 5和 e6依次通过栈 S，
14、一个元素出栈后即进入队列 Q，若 6 个元素出列的顺序是 e2、e 3、e 4、e 5、e 6、e 1，则栈 S 的容量至少应该是( ) A6 B4 C3 D2（分数：2.00）A.B.C. D.解析：4.在 Hash 函数 H(k)=k MOD m 中，一般来讲，m 应取( ) A奇数 B偶数 C素数 D充分大的数（分数：2.00）A.B.C. D.解析：5.已知用某种排序方法对关键字序列(51,35,93,24,13,68,56,42,77)进行排序时，前两趟排序的结果为 (35,51,24,13,68,56,42,77,93) (35,24,13,51,56,42,68,77,93) 所
15、采用的排序方法是 ( ) A插入排序 B冒泡排序 C快速排序 D归并排序（分数：2.00）A.B. C.D.解析：解析 由题目中第一趟排序的结果是将所有关键字中最大的关键字(97)放在了序列最后，第二趟排序的结果是将除 97 以外的所有关键字中最大的关键字放在了序列中倒数第二个位置，可知此排序方法为冒泡排序。6.如图所示二叉树的中序遍历序列是( ) （分数：2.00）A.B.C. D.解析：7.考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( ) A直接插入排序和快速排序 B快速排序和归并排序 C直接选择排序和归并排序 D直接插入排序和归并排序（分数：2.00
16、）A.B.C. D.解析：8.森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4，那么当把森林 T 转换成一棵二叉树后，其根结点的左孩子上有( )个结点。 An 1-1 Bn 1 Cn 1+n2+n3 Dn 2+n3+n4（分数：2.00）A. B.C.D.解析：9.循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别是 front 和 rear，则当前队列中的元素个数是( ) A(rear-front+m)MODm Brear-fomt+1 Crear-fribt-1 Drear-front（分数：2.00）A. B.C.D.解析：10.在一个
17、单链表中，已知 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.解析：11.堆(Heap)是( ) A完全二叉树 B线性表 C二叉排序树 D平衡二叉树（分数：2.00）A.B. C.D.解析：12.指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是 ( ) Apnext=r; qnext=rnext; r
18、next=q; Bpnext=r; rnext=q; qnext=rnext; Crnext=q; qnext=rnext; pnext=r; Drnext=q; pnext=r; qnext=rnext;（分数：2.00）A. B.C.D.解析：13.下列说法中正确的是( ) A二叉树中任何一个结点的度都为 2 B二叉树的度为 2 C任何一棵二叉树中至少有一个结点的度为 2 D一棵二叉树的度可以小于 2（分数：2.00）A.B.C.D. 解析：14.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( ) A数据元素具有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数
19、据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等（分数：2.00）A.B. C.D.解析：15.下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( ) A插入排序 B堆排序 C快速排序 D冒泡排序（分数：2.00）A.B. C.D.解析：二、填空题(总题数：10，分数：20.00)16.设线性表 L=(a1，a 2，a n)(n2)，表中元素按值的递增顺序排列。对一个给定的值 k，分别用顺序检索和二分法检索查找与 k 相等的元素，比较次数分别为 s 和 b，若检索不成功，则 s 和 b 的数量关系是 1。（分数：2.00）填空项 1:_ （正确答案：sb）解析
20、：17.由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_ （正确答案：55）解析：18.在二叉排序树中，其左子树中任何一个结点的关键字一定 1 其右子树的各结点的关键字。（分数：2.00）填空项 1:_ （正确答案：小于）解析：19.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。（分数：2.00）填空项 1:_ （正确答案：稳定）解析：20.对无向图，其邻接矩阵是一个关于 1 对称的矩阵。（分数：2.00）填空项 1:_ （正确答案：主对角线）解析：21.和二分查找相比，顺序查找的优点是除
21、了不要求表中数据元素有序之外，对 1 结构也无特殊要求。（分数：2.00）填空项 1:_ （正确答案：存储）解析：22.含 n 个顶点的无向连通图中至少含有 1 条边。（分数：2.00）填空项 1:_ （正确答案：n-1）解析：23.对表长为 9000 的索引顺序表进行分块查找，假设每一块的长度均为 15，且以顺序查找确定块，则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 1。（分数：2.00）填空项 1:_ （正确答案：308.5）解析：24.查找表中主关键字指的是_，次关键字指的是_。（分数：2.00）填空项 1:_ （正确答案：能惟一标识数据元素的数据项 不能惟一标识数据
22、元素的数据项）解析：25.设二维数组 A1020,510按行优先存储，每个元素占 4 个存储单元，A10,5的存储地址是1000，则 A15,10的存储地址是 1。（分数：2.00）填空项 1:_ （正确答案：1700）解析：三、解答题(总题数：4，分数：20.00)26.已知连通图如下： （分数：5.00）_正确答案：( )解析：27.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode; typedef struct VertexType vert
23、ex; 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; /指向下一条弧的指针 ArcNod
24、e; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef struct AdjList adjList; int n,e; ALGraph;)解析：28.对于如图所示的二叉树，请画出其顺序存储结构图。 （分数：5.00）_正确答案：(二叉树的顺序存储就是将二叉树的结点按编号存在向量 B0,n中，其中 B0用来存放结点 T数，如果树中某些编号对应的结点不存在，则对应存储空间为“
25、空”，根据上述规则，我们得到： )解析：29.假设有一个长度为 n 的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。（分数：5.00）_正确答案：(假设判定树的内部结点的总数为 n=2h-1。则判定树是深度为 h=lg(n+1)的满二叉树，树中第k 层上的结点的个数为 2h-1，查找它们所需要比较的次数是 k。则在等概率下，二分查找成功时的平均查找长度为： )解析：四、算法阅读题(总题数：3，分数：20.00)30.请将下面的程序改成递归的过程。 voide ditui(int n) int i; i=n; while(i1) prinft
26、(i-); （分数：5.00）_正确答案：(此递推过程可以改写成如下递归过程： voide dkui(int j) if(i1) prind(j); digui(j-1); )解析：31.求下面算法中变量 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 struct Node int id; /*学号*/ i
27、nt score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后 A 所指的链表； （分数：10.00）_正确答案：()解析：_正确答案：(对于表 A 中成绩低于 60 的学生，如果在表 B 中也有成绩记录，则将表 A 中的成绩修改为其在表 B 中的成绩；但若其在表 B 中的成绩高于 60 分，则只改为 60 分。)解析：五、算法设计题(总题数：1，分数：10.00)32.设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。（分数：
28、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*/)解析：
