数据结构——用C语言描述（第3版）试卷答案2.docx

《数据结构（第三版）》 耿国华等编 高等教育出版社 《数据结构》期末考试 试卷2 简答题（每题5分，共20分） 1、一棵有n个结点的k叉树采用k叉链表存储，空链域的总数目是多少？写出求解过程。 2、在图的遍历中，设置访问标志数组的作用是什么？ 3、折半查找的前提条件是什么？ 4、分析冒泡排序的最好性能和最坏性能（性能即关键字比较次数和移动元素的次数）。 二、单项选择题（每题1分，共10分） 1、栈和队列的共同特点是( )。 A）只允许在端点处插入和删除元素 B）都是先进后出 C）都是先进先出 D）没有共同点 2、 100个结点的完全二叉树采用顺序存储，从1开始按层次编号，则编号最小的叶子结点的编号应该是（ ）。 A) 100 B) 49 C) 50 D) 51 3、在顺序存储的线性表上R[3]上，从前向后进行顺序查找。若查找第一个元素的概率是1/2，查找第二个元素的概率是1/3，查找第三个元素的概率是1/6。则查找成功的平均查找长度为（ ）。 A）7/3 B）2 C）3 D）5/3 4、在一个有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ） A) n-s B) n C) s D) s-1 5、设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ ）。 A) N0=N1+1 B) N0=Nl+N2 C) N0=N2+1 D) N0=2N1+l 6、设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A）5 B）6 C）7 D）8 7、已知单链表中的指针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的入度为（ ）。 A) 第i行非0元素的个数之和 B) 第i列非0元素的个数之和 C) 第i行0元素的个数之和 D) 第i列0元素的个数之和 9、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是（ ）排序方法的基本思想。 A）堆排序 B）直接插入排序 C）快速排序 D）冒泡排序 10、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。 A）快速排序 B）堆排序 C）归并排序 D）基数排序 三、填空题（每空2分，共20分） 1、下面算法的时间复杂度是 。 i=1; while(i=n) i=i*2; 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）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是 。 四、构造题（共30分） 1、(8