1、数据结构自考题-2 及答案解析(总分：105.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.用二分查找法对具有 n 个结点的线性表查找一个结点所需的平均比较次数为( ) AO(n 2) BO(nlog 2n) CO(n) DO(log 2n)（分数：2.00）A.B.C.D.2.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2.00）A.B.C.D.3.对一棵非空二叉树进行中序遍历，则根结点的左边( ) A只有左子树上的所有结点 B只有右子
2、树上的所有结点 C只有左子树上的部分结点 D只有右子树上的部分结点（分数：2.00）A.B.C.D.4.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 ( ) A队列 B栈 C线性表 D有序表（分数：2.00）A.B.C.D.5.从具有 n 个结点的单链表中查找值等于 x 的结点时，在查找成功的情况下，平均需比较( )个结点。 An Bn/2 C(n-1)/2 D(n+1)/2（分数：2.00）A.B.C.D.6.设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是( ) A2 h B2 h-1 C2 h-1 D2 h+1-1（分数：2.00）A.B.C.D.7.下面的查
3、找方式中，可以对无序表进行查找的是( ) A顺序查找 B二分查找 C二叉排序树 DB-树上的查找（分数：2.00）A.B.C.D.8.具有 12 个记录的序列，采用冒泡排序最少的比较次数是( ) A1 B144 C11 D66（分数：2.00）A.B.C.D.9.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( ) A每个结点所代表的数据元素都一样 B每个结点所代表的数据元素包含的数据项的个数要相等 C不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 D结点所代表的数据元素有同一特点（分数：2.00）A.B.C.D
4、.10.下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( ) A插入排序 B堆排序 C快速排序 D冒泡排序（分数：2.00）A.B.C.D.11.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目（分数：2.00）A.B.C.D.12.具有 24 个记录的序列，采用冒泡排序最少的比较次数是( ) A1 B23 C24 D529（分数：2.00）A.B.C.D.13.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的( ) A先序遍历 B中序遍历 C后序遍历 D按层遍历（分数：2.00
5、）A.B.C.D.14.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据（分数：2.00）A.B.C.D.15.若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24 从小到大进行排序，共要进行( )次比较。 A33 B45 C70 D91（分数：2.00）A.B.C.D.二、填空题(总题数：10，分数：20.00)16.对于一个二维数组 Amn，若按行序为主序存储，则任一元素 Aij相对于 A00的地址为 1。（分数：2.00）填空项 1:_17.已知 L 是无表头结点的单链表，且
6、P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 (1)在 P 结点之前插入 S 结点的语句序列是_； (2)在表首插入 S 结点的语句序列是_。 a Pnex=S b Pnext=Pnextnext c Pnext=Snext d Snext=Pnext e Snext=L f Q=P g while(Pnext!=QP=Pnext h while(Pnext!=NULL)P=Pnext i P=L j L=S（分数：2.00）填空项 1:_18.任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为 1 个。（分数：2.00）
7、填空项 1:_19.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。（分数：2.00）填空项 1:_20.由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_21.数组 A110，-26，28以行优先顺序存储，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5,0,7的存储地址为 1。（分数：2.00）填空项 1:_22.如果一个图中有 n 条边，则此图的生成树含有_条边，所以生成树是图的边数_的连通图。（分数：2.00）填空项 1:_23.在二叉排序树中，其左子树中
8、任何一个结点的关键字一定 1 其右子树的各结点的关键字。（分数：2.00）填空项 1:_24.在线性结构中， 1 决定了它的遍历路线只有一条。（分数：2.00）填空项 1:_25.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_三、解答题(总题数：3，分数：25.00)已知带权图的邻接表如下所示，其中边表结点的结构为： （分数：10.00）_26.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; stru
9、ct node*next; EdgeNode; typedef struct VertexType vertex; EdgeNode*firstedge; VertexNode; typedef VertexNode A djListMaxVertexNum; typedef struct AdjList adjiist; int n,e; ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （分数：5.00）_从空树起，依次插入关键字 37,50,42,18,48,12,56,30,23，构造一棵
10、二叉排序树。 (1)画出该二叉排序树； (2)画出从(1)所得树中删除关键字为 37 的结点之后的二叉排序树。（分数：10.00）_四、算法阅读题(总题数：2，分数：20.00)二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）填空项 1:_27.简述一下算法
11、的功能： 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)28.假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node DataType data; struct node*next LinkNode,*LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_数据结
12、构自考题-2 答案解析(总分：105.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.用二分查找法对具有 n 个结点的线性表查找一个结点所需的平均比较次数为( ) AO(n 2) BO(nlog 2n) CO(n) DO(log 2n)（分数：2.00）A.B. C.D. 解析：2.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定（分数：2.00）A.B. C.D.解析：3.对一棵非空二叉树进行中序遍历，则根结点的左边( ) A只有左子树上的所有结点
13、B只有右子树上的所有结点 C只有左子树上的部分结点 D只有右子树上的部分结点（分数：2.00）A. B.C.D.解析：4.在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 ( ) A队列 B栈 C线性表 D有序表（分数：2.00）A. B.C.D.解析：5.从具有 n 个结点的单链表中查找值等于 x 的结点时，在查找成功的情况下，平均需比较( )个结点。 An Bn/2 C(n-1)/2 D(n+1)/2（分数：2.00）A.B.C.D. 解析：6.设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是( ) A2 h B2 h-1 C2 h-1 D2 h+1-1（分数：2.
14、00）A.B.C.D. 解析：7.下面的查找方式中，可以对无序表进行查找的是( ) A顺序查找 B二分查找 C二叉排序树 DB-树上的查找（分数：2.00）A. B.C.D.解析：8.具有 12 个记录的序列，采用冒泡排序最少的比较次数是( ) A1 B144 C11 D66（分数：2.00）A.B.C. D.解析：9.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( ) A每个结点所代表的数据元素都一样 B每个结点所代表的数据元素包含的数据项的个数要相等 C不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 D结点
15、所代表的数据元素有同一特点（分数：2.00）A.B.C. D.解析：10.下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( ) A插入排序 B堆排序 C快速排序 D冒泡排序（分数：2.00）A.B. C.D.解析：11.若用邻接矩阵表示一个有向图，则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目（分数：2.00）A. B.C.D.解析：12.具有 24 个记录的序列，采用冒泡排序最少的比较次数是( ) A1 B23 C24 D529（分数：2.00）A.B. C.D.解析：13.邻接表存储结构下图的深度优先遍历算
16、法结构类似于于叉树的( ) A先序遍历 B中序遍历 C后序遍历 D按层遍历（分数：2.00）A. B.C.D.解析：14.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据（分数：2.00）A.B.C. D.解析：15.若用冒泡排序法对序列 18,14,6,27,8,12,16,52,10,26,47,29,41,24 从小到大进行排序，共要进行( )次比较。 A33 B45 C70 D91（分数：2.00）A.B.C. D.解析：二、填空题(总题数：10，分数：20.00)16.对于一个二维数组 Amn，若按行序为主序存储，则任一
17、元素 Aij相对于 A00的地址为 1。（分数：2.00）填空项 1:_ （正确答案：ij+i 全元素位置）解析：17.已知 L 是无表头结点的单链表，且 P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 (1)在 P 结点之前插入 S 结点的语句序列是_； (2)在表首插入 S 结点的语句序列是_。 a Pnex=S b Pnext=Pnextnext c Pnext=Snext d Snext=Pnext e Snext=L f Q=P g while(Pnext!=QP=Pnext h while(Pnext!=NULL)P=Pnext i P=L j L
18、=S（分数：2.00）填空项 1:_ （正确答案：figda ej）解析：18.任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为 1 个。（分数：2.00）填空项 1:_ （正确答案：n-2m+1）解析：19.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。（分数：2.00）填空项 1:_ （正确答案：二分查找法 分块查找）解析：20.由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_ （正确答案：55）解析：21.数组 A110，-26，28以行优先顺序存储
19、，设第一个元素的首地址是 100，每个元素占 3 个存储长度的存储空间，则元素 A5,0,7的存储地址为 1。（分数：2.00）填空项 1:_ （正确答案：913）解析：22.如果一个图中有 n 条边，则此图的生成树含有_条边，所以生成树是图的边数_的连通图。（分数：2.00）填空项 1:_ （正确答案：n-1 最少）解析：23.在二叉排序树中，其左子树中任何一个结点的关键字一定 1 其右子树的各结点的关键字。（分数：2.00）填空项 1:_ （正确答案：小于）解析：24.在线性结构中， 1 决定了它的遍历路线只有一条。（分数：2.00）填空项 1:_ （正确答案：线性结构中后继的惟一性）解析
20、：25.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_ （正确答案：基地址）解析：三、解答题(总题数：3，分数：25.00)已知带权图的邻接表如下所示，其中边表结点的结构为： （分数：10.00）_正确答案：( )解析：_正确答案：( )解析：26.图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node int adjvex; struct node*next; EdgeNode; typedef struct VertexType
21、 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; /指向下一条弧的指针 A
22、rcNode; typedef struct VNode VertexType data; /顶点信息 struct VNode*nextVertex; /指向下一个顶点的指针 ArcNode*firstarc; /指向第一条依附该顶点的弧 VNode.*AdjList; typedef struct AdjList adjList; int n,e; ALGraph;)解析：从空树起，依次插入关键字 37,50,42,18,48,12,56,30,23，构造一棵二叉排序树。 (1)画出该二叉排序树； (2)画出从(1)所得树中删除关键字为 37 的结点之后的二叉排序树。（分数：10.00）_
23、正确答案：( )解析：_正确答案：( )解析：四、算法阅读题(总题数：2，分数：20.00)二叉排序树的存储结构定义为以下类型： typedef int KeyType; typedef struct node KeyType key; /*关键字项*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33，并回答问题： （分数：15.00）填空项 1:_ （正确答案：10）解析：_正确答案：(T 是空树或 T 中所有结点的关键字均不大于给定值 X 时，返回
24、空指针。)解析：_正确答案：(如果二叉排序树 T 中存在含有关键字大于给定值 X 的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。)解析：27.简述一下算法的功能： status A (1inkedlist L) /L 是无表头结点的单链表 if (LL=Lnext;P=L; while(Pnext)P=Pnext; Pnext=Q;Qnext=NULL; return ok; )/A（分数：5.00）_正确答案：(本程序实现的功能就是：如果 L 的长度不小于 2，则将首元结点删去并插入到表尾。)解析：五、算法设计题(总题数：1，分数：10.00)28.假设以带头结点的单链表表示
25、有序表，单链表的类型定义如下： typedef struct node DataType data; struct node*next LinkNode,*LinkList; 编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数：10.00）_正确答案：(参考答案一： void f34(LinkList ha,LinkList hb) /hb 和 hb 分剐为存放 A 和 B 有序链表的头指针 LinkList p,q,r; p=ha; q=hbnext; while(pnext else if(pnextdata=qdata) r=pnext; pnext=rnext; free(r); /从 A 表删除相同的元素结点 q=qnext; 参考答案二： void f34(LinkList ha,LinkList hb) /hb 和 hb 分别为存放 A 和 B 有序链表的头指针 LinkList p,q,r; r=ha;p=hanext; q=hbnext; while(pp=p-next; else if(pdata=qdata) rnext=pnext; free(p); p=rnext; /从 A 表删除相同的元素结点 q=qnext )解析：
