《数据结构》期末考试试卷试题及答案2套.docxVIP

《数据结构》期末考试试卷试题及答案 一、简答题（每题5分，共20分）1、一棵有n个结点的k叉树采用k叉链表存储，空链域的总数目是多少？写出求解过程。 2、在图的遍历中，设置访问标志数组的作用是什么？ 3、折半查找的前提条件是什么？ 4、分析冒泡排序的最好性能和最坏性能（性能即关键字比拟次数和移动元素的次数）。 二、单项选择题（每题1分，共10分） 1、栈和队列的共同特点是（）oA）只允许在端点处插入和删除元素B）都是先进后出 C）都是先进先出D）没有共同点 2、100个结点的完全二叉树采用顺序存储，从工开始按层次编号，那么编号最小的叶子 结点的编号应该是（）o A） 100B）49C） 50 D） 51 3、在顺序存储的线性表上R⑶上，从前向后进行顺序查找。假设查找第一个元素的概率是 1/2,查找第二个元素的概率是1/3,查找第三个元素的概率是1/6。那么查找成功的平均查找 长度为（）oA） 7/3B） 2C） 3 D） 5/3 4、在一个有n个顶点的有向图中，假设所有顶点的出度之和为s,那么所有顶点的入度之和 为（）A） n-sB） nC） s D） s-1 5、设某二叉树中度数为。的结点数为NO,度数为1的结点数为NL度数为2的结点数 为N2,那么以下等式成立的是（ ）oA） NO=N1+1 B） N0=NI+N2 C） N0=N2+l D） NO=2N1+I 6、设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。 A） 5B） 6C） 7 D） 87、单链表中的指针p所指的结点不是链尾结点，假设在p结点后插入s结点，应执行（）。 A）s-next=p ; p-next=s ; B） p-next=s ;s-next=p ;C）s-next=p-next; p=s ; D） s-next=p-next ;p-next=s ; 8、设用邻接矩阵A表示有向图G的存储结构，那么有向图G中顶点i的入度为（）oA）第i行非0元素的个数之和B）第i列非0元素的个数之和 C）第i行。元素的个数之和D）第i列。元素的个数之和9、排序时扫描待排序记录序列，顺次比拟相邻的两个元素的大小，逆序时就交换位置。这 是（）排序方法的基本思想。 A）堆排序 B）直接插入排序C）快速排序 D）冒泡排序 10、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录 关键字，那么用以下（）方法可以到达此目的。 A）快速排序 B）堆排序 C）归并排序D）基数排序三、填空题（每空2分，共20分） 1、下面算法的时间复杂度是。 i=l；while（i=n） i=i*2; BiTNode* Parent(BiTree bt,ElemType e) 〃找 e 结点的双亲 BiTNode*p=NULL; if(bt==NULL) return NULL;if(bt-LChild-data==e 11 bt-RChild-data==e) 〃访 问根 return bt; p=Parent(bt-LChild,e); 〃在左子树上找 if(!p) p=parent(bt-RChild,e)〃在右子树上找 return p;) 2、设线索二叉树中，判断p所指向的结点为叶子结点的条件是2、对任意一棵有n个结点的树，这n个结点的度之和为。 3、Prim算法适合求解连通网的最小生成树。（填稀疏或稠密）4、关键路径是从源点到汇点的路径。 5、深度为k的二叉树中最少有个结点，最多有个结点。 6、设有向图G中有向边的集合E=｛1, 2, 2, 3, 1, 4, 4, 2, 4, 3｝,那么该图的 一种拓扑序列为7、根据初始关键字序列（25, 22, 11, 38, 10）建立的二叉排序树的高度为。 8、用某种排序方法对关键字序列（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排序 时，序列的变化情况如下： TOC \o 1-5 \h \z 20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84那么所采用的排序方法是。 四、构造题（共30分）1、（8 分）设一棵树 T 中边的集合为｛（A, B）, （A, C）, （A, D）, （B, E）, （C, F）, （C, G）｝,要 求： ①用孩子兄弟表示法（二叉链表）表示出该树的存储结构；（2分） ②将该树转化成对应的二叉树。（2分） ③写出该树的先序和后序遍历序列。（4分）2、（8分）某图的邻接表存储结构为图1所示： ①画出从VI出发的深度优先生成树；② 给出该图的邻接矩阵存储结构。 图1第四题第2小题图3、（8分）一个线性序列（36, 13, 40, 63, 22,