数据结构自考题-2

1、( ) 对应的判定树( ) 个结点数据结构自考题 -2( 总分： 105.00 ，做题时间： 90 分钟 )一、单项选择题 ( 总题数： 15，分数： 30.00)1. 用二分查找法对具有 n 个结点的线性表查找一个结点所需的平均比较次数为 ( ) 2A O(n2) B O(nlog 2n) C O(n) D O(log 2n)(分数： 2.00 )A.B.VC.D.V解析：2. 如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数 的高度(假设树高h>2)。A. 大于B .小于C 等于D .无法确定(分数： 2.00 )A.B. VC.D.解析：3. 对一棵

2、非空二叉树进行中序遍历，则根结点的左边 ( )A. 只有左子树上的所有结点B 只有右子树上的所有结点C.只有左子树上的部分结点D 只有右子树上的部分结点(分数： 2.00 )A. VB.C.D.解析：4. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 ( )A. 队列B .栈C .线性表D .有序表(分数： 2.00 )A. VB.C.D.解析：5. 从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较A. n B . n/2 C . (n-1)/2 D . (n+1)/2(分数： 2.00 )A.B.C.D. V解析：6. 设二叉树根结点的层次为0，一棵高度为

3、 h 的满二叉树中的结点个数是 ( )A2h B 2h-1 C 2h-1 D 2h+1-1(分数： 2.00 )A.B.C.D. V解析：7. 下面的查找方式中，可以对无序表进行查找的是 ( )A. 顺序查找B .二分查找C .二叉排序树D . B-树上的查找(分数： 2.00 )A. VB.C.D.解析：8. 具有 12 个记录的序列，采用冒泡排序最少的比较次数是 ( )A1 B144 C11 D66(分数： 2.00 )A.B.C. VD.解析：9. 线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相 同的特性，这意味着 ( )A. 每个结点所代表的

4、数据元素都一样B. 每个结点所代表的数据元素包含的数据项的个数要相等C. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致D. 结点所代表的数据元素有同一特点分数： 2.00 )A.B.D.解析：10. 下列排序算法中，其时间复杂度和记录的初始排列无关的是 ( )A.插入排序B 堆排序C 快速排序D 冒泡排序(分数： 2.00 )A.B. VC.D.解析：11. 若用邻接矩阵表示一个有向图，则其中每一列包含的 "1" 的个数为 ( )A.图中每个顶点的入度B .图中每个顶点的出度B. 图中弧的条数 D 图中连通分量的数目(分数： 2.00 )A. VB.C

5、.D.解析：12. 具有 24 个记录的序列，采用冒泡排序最少的比较次数是 ( )A. 1 B. 23 C. 24 D. 529(分数： 2.00 )A.B. VC.D.解析：13. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的 ( )A.先序遍历B .中序遍历C .后序遍历D .按层遍历(分数： 2.00 )A. VB.C.D.解析：14. 树最适合用来表示 ( )A.有序数据元素 B .无序数据元素C.元素之间具有分支层次关系的数据D .元素之间无联系的数据（分数： 2.00 ）A.B.C. VD.解析：15. 若用冒泡排序法对序列 18,14,6,27,8,12,16,52,1

6、0,26,47,29,41,24 从小到大进行排序，共要进行 （ ） 次比较。A33 B45 C70 D91（分数： 2.00 ）A.B.C. VD.解析：二、填空题（总题数： 10，分数： 20.00）16. 对于一个二维数组 Amn ，若按行序为主序存储，则任一元素 Aij 相对于 A00 的地址为 1（分数： 2.00 ）填空项1: （正确答案：i Xj+i 全元素位置）解析：17. 已知 L 是无表头结点的单链表， 且 P 结点既不是首元结点， 也不是尾元结点， 试从下列提供的答案中选 择合适的语句序列。（1）在P结点之前插入S结点的语句序列是 ；（2）在表首插入 S 结点的语句序列是

7、 。a P > nex=S b P > next=P > next > nextc P > next=S > next d S > next=P > nexte S > next=L f Q=Pg while（P > next!=Q > P=P> nexth while（P > next!=NULL）P=P > nexti P=L j L=S（分数： 2.00 ）填空项 1: （正确答案： figda ej）解析：18. 任意一棵具有n个结点的二叉树，若它有 m个叶子，则该二叉树上度数为1的结点为1个（分数：

8、2.00 ）填空项 1: （正确答案： n-2m+1）解析：19. 存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用 和进行查找（分数:2.00 ）填空项1： （正确答案：二分查找法分块查找）解析：20. 由权值为1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为1（分数:2.00）填空项1： （正确答案：55）解析：21. 数组A1.10，-2.6 ，2.8以行优先顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A5,0,7的存储地址为1。（分数：2.00）填空项1: （正确答案：913）解析：22. 如果一个图中有n条边，则

9、此图的生成树含有 条边，所以生成树是图的边数 的连通图（分数：2.00）填空项1: （正确答案：n-1最少）解析：23. 在二叉排序树中，其左子树中任何一个结点的关键字一定1其右子树的各结点的关键字。（分数：2.00）填空项1： （正确答案：小于）解析：24. 在线性结构中，1决定了它的遍历路线只有一条。（分数：2.00）填空项1: （正确答案：线性结构中后继的惟一性）解析：25. 在按照顺序存储方式存储的数组中，元素aj的存储地址应该是数组的 1加上排在aj前面的元素所占用的单元数。（分数：2.00）填空项1: （正确答案：基地址）解析：三、解答题（总题数：3,分数：25.00）已知带权图的

10、邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点 C岀发进行深度优先遍历。（1）画岀由此得到的深度优先生成树；（2）写岀遍历过程中得到的从顶点C到其他各顶点的带权路径及其长度。（分数：10.00）正确答案：（ 解析:26. 图的邻接表的类型定义如下所示: #define MaxVertexNum 50 typedef struct nodeint adjvex;struct node*next;EdgeNode;typedef structVertexType vertex;EdgeNode*firstedge;VertexNode;typedef VertexNode A djList

11、MaxVertexNum;typedef structAdjList adjiist;int n,e;ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如 下图所示，请写岀重新定义的类型说明。（分数：5.00 ） 正确答案：(typeclef struct ArcNodeVNode*adjvex; /该弧所指向的顶点的位置struct ArcNode*nextarc; /指向下一条弧的指针ArcNode;typedef struct VNodeVertexType data; /顶点信息struct VNode*nextVertex; /

12、指向下一个顶点的指针ArcNode*firstarc; / 指向第一条依附该顶点的弧VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：从空树起，依次插入关键字37,50,42,18,48,12,56,30,23，构造一棵二叉排序树(1)画出该二叉排序树； 画出从 所得树中删除关键字为 37的结点之后的二叉排序树。（分数：10.00）正确答案：（解析:正确答案：（解析：四、算法阅读题（总题数：2,分数：20.00）二叉排序树的存储结构定义为以下类型：typedef int KeyType;typedef struct

13、 nodeKeyType key; /* 关键字项 */InfoType otherinfo; /*其它数据项 */struet node*lchild,*rchild; /*左、右孩子指针 */BSTNode,*BSTree;阅读算法f33，并回答问题： 对如图所示的二叉排序树T，写出f33(T,8)返回的指针所指结点的关键字;在哪些情况下算法f33返回空指针？简述算法f33的功能。BSTNode*f33(BSTree T,KeyType x)BSTNode*P;if(T=NULL)return NULL;p=f33(T > lehild,x);if(p!=NULL)return p;

14、if(T > key > x)return T;return f33(T> rchild,x);（分数：15.00 ）填空项1: （正确答案：10）解析：正确答案：仃是空树或T中所有结点的关键字均不大于给定值X时，返回空指针。）解析：while(P > next)P=P > next; P> next=Q;Q > next=NULL;return ok;)/A(分数： 5.00 )正确答案： （ 本程序实现的功能就是：如果 L 的长度不小于 2，则将首元结点删去并插入到表尾。）解析：五、算法设计题 （ 总题数： 1，分数： 10.00）28. 假设以带

15、头结点的单链表表示有序表，单链表的类型定义如下：typedef struct nodeDataType data;struct node*nextLinkNode,*LinkList;编写算法，从有序表 A 中删除所有和有序表 B 中元素相同的结点。（分数： 10.00 ） 正确答案： ( 参考答案一：void f34(LinkList ha,LinkList hb) hb和hb分剐为存放A和B有序链表的头指针LinkList p,q,r;p=ha;q=hb> next;while(p > next&&q)if(p > next > data <q- >data) p=p> next;elseif(p > next > data=q > data) r=p > next;p> next=r > next; free(r); / 从 A 表删除相同的元素结点q=q> next; 参考答案二：void f34(LinkList ha,LinkList hb) /hb 和hb分