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

数据结构期末考试试卷试题及答案一、简答题（每题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、在顺序存储的线性表上R3上，从前向后进行顺序查找。若查找第一个元素的概率是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）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的入度为（ ）。 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=，则该图的一种拓扑序列为_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分) 设一棵树T中边的集合为(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)，要求： 用孩子兄弟表示法（二叉链表）表示出该树的存储结构；（2分） 将该树转化成对应的二叉树。（2分） 写出该树的先序和后序遍历序列。（4分）2、（8分）某图的邻接表存储结构为图1所示： 画出从V1出发的深度优先生成树； 给出该图的邻接矩阵存储结构。图1 第四题 第2小题图3、（8分）一个线性序列（36，13，40，63，22，6），假定采用散列函数Hash(key)=key%7来计算散列地址，将其散列存储在A09中，采用线性探测再散列解决冲突。构造哈希表，并计算等概率情况下的查找成功和不成功的平均查找长度。4、（6分）欲对关键字36，15,13，40，63，22，6从小到大排序，若采用堆排序，写出将关键字序列建初堆过程。五、算法设计题（每小题10分，共20分）注：只要求给出描述算法的子函数，不需要编写完整的实现程序。1、 编写折半查找算法。（递归、非递归均可） 2、已知二叉树采用二叉链表存放，该结点结构为：LChilddataRChildlevel编写算法，将二叉树中每个结点所在的层次值置入相应的level域。数据结构期末考试试卷2参考答案一、简答题1、n个结点的k叉树采用k叉链表存储，链域总数为k*n，又：n=B+1,B为分支总数即非空链域总数，B=n-1,所以空链域总数为：（k-1）*n+1。2、访问标志数组的作用是：保证图中的每个顶点都被访问到，且仅访问一次。3、折半查找的前提条件是1）列表元素顺序存储；2）列表元素按关键字有序存储；4、冒泡排序最好情况：移动元素次数为0，关键字比较次数为：n-1次；冒泡排序最坏情况：移动元素次数为3n*(n-1)/2,关键字比较次数为n*(n-1)/2。二、选择题1.A2.D3.D4.C5.C6. A 7.D8.B9.D10.B三、填空题1、O（log2n）2、p-ltag= =1&p-rtag= =1 3、n-14、稠密5、最少k,最多 2k-16、1,4,2,37、高度为48、快速排序四、构造题1.1) 该树的孩子兄弟表示法为：（2分）2)转化的二叉树为:（2分）3）先序遍历序列为：ABECFGD（2分）后序遍历序列为:EBFGCDA（2分）2. 1）此为有向图的邻接表表示法，该图为：2）深度优先搜索得到的遍历序列为：V1，V4，V5，V6，V2，V7，V3;深度优先生成树为： 3）其邻接矩阵表示法为：顶点数组： 邻接矩阵：1V12V23V34V45V56V67V700011010001000000001100000000100010000000000111003、1）构造的哈希表为：（4分）地址0123456789元素63362240136比较次数1121122）（2分）查找成功时的（）/（2分）查找不成功时的（）/4、据题意，欲得到递增有序，需要建大根堆（1分）。建初堆过程如下：五算法设计题1、折半查找算法：1）非递归算法：int BinSearch (RecordList L,KeyType k)low=1;high=L.length; while(lowrmid.key= =k) return mid;else if(krmid.key) high=mid-1;else low=mid+1; return 0;2)递归算法int BinSearch (RecordList L,KeyType k，int low,int high)/首次调用，low=1，high=L.length; if(lowrmid.key= =k) return mid;else if(krmid.key) return(BinSearch (L, k,low,mid-1);else return(BinSearch (L, k,mid+1,high);2、二叉树中每个结点的level域置值算法：利用二叉树的先序遍历给每个结点的level域置值。void SetLevel（BiTree bt，int layer）/首次调用时，bt参数为二叉树的根指针，layer参数值为1。 if（bt）bt-level=layer; SetLevel（bt-lchild，layer+1）；SetLevel(bt-)rchild，layer+1）；注：此题也可以借助层次遍历完成。