数据结构模拟题B

1、广州大学松田学院数据结构模拟题(B)卷(适用专业：计算机科学与技术考试方式：闭卷考试时间：120分)题目-一一-二二-三四五总分分值30分20分10分30分10分100分一、单项选择题，在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入答题纸上对应题号后的括号内。不准不填，否则无分。(共15小题，每小题2分，共30 分)1. 树中所有结点的度数之和等于结点总数加 。A. 0 B. 1 C. -1 D. 22. 在一棵树中，每个结点最多有 个直接前驱结点。A. 0B. 1C. 2D.任意多个3. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加。A. 2B. 1C. 0D. -1

2、4. 顶点个数为n的无向图最多有 条边。级一班 一( 业 专A. n-1 B. n(n-1)/2C. n(n+1)/2D. n(n-1)5. n个顶点的连通图至少有条边。A. n-1 B. n C. n+1 D. 06. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。A. 3 B. 2 C. 1 D. 1/27. 对于顺序存储的有序表 (5, 12, 20, 26, 37, 42, 46, 50, 64)，为查找元素 26，若采用顺序查找，需要比较 次才能查找成功。A. 3 B. 4 C. 5 D. 68. 设哈希表长为14，哈希函数f( k)=k% 11,已知表中已有4个元素，关键字

3、分别为15,38, 61, 84,存储位置分别为4, 5, 6, 7,其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是A. 8 B. 3 C. 5 D. 99、在对n个元素进行简单选择排序的过程中，需要进行 趟选择和交换。A. n/2 B. n-1 C. n D. n+110、在对n个元素进行快速排序的过程中，第一趟排序最多需要交换 对元素。A. n/2 B. n-1 C. n D. n+111、 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A存储结构B逻辑结构C顺序存储结构D链式存储结构12、 一个向量第一个元素的存储地址是100，每个元素的

4、长度为 2,则第5个元素的地址是.（A）110（ B）108（ C）100（ D）12013、在一个单链表 HL中，若要向表头插入一个由指针 p指向的结点，则执行 。（A） HL=p; p->next=HL;（ B） p-next=HL; HL=p;（C） p_>next=HL; p=HL;（ D） p_>next=HL->next; HL_>next=p;14、 栈的插入和删除操作在进行。A、栈顶 B、栈底 C、任意位置D、指定位置15、若在子程序A中包含了调用子程序A的语句，这就称为（）。A 直接递归调用B间接递归调用 C互相调用D 传递参数二、填空题。根据上

5、下文在下划线处填入一个正确的答案，并将其填入答题纸上对应题号后的括号内。不准不填，否则无分。（共10小题，每空2分，共20分）1. 假定一棵二叉树的结点个数为32,则它的最小深度为。2. 在一棵二叉树中，度为 2的结点有5个，度为1的结点有6个，那么叶子结点有个。3. 一棵深度为5的满二叉树的结点总数为 个。4. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为 。5. 元素关键字转换为该元素存储位置的函数f称为。6. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做排序。7. 数组的存储结构采用存储方式。8. 对于一棵具有n个结点的二叉树，若一个结点的编号

6、为i（1 < i w n）,则它的左孩子结点的编号为2i，右孩子结点的编号为2i+1，双亲结点的编号为 9. 向一个长度为n的向量的第i个元素（1 < i< n+1）之前插入一个元素时，需向后移动个元素。10. 向栈中压入元素的操作是先 ，后存入元素。三、判断题。根据题目的论述，你认为是正确的则在小题前面的括号内打上（“）不正确则打上（x ）,并将其填入答题纸上对应题号后的括号内。不准不填，否则无分。（共10小题，每小题1分，共10分）1. 栈和队列逻辑上都是操作受限的线性表，堆栈的插入和删除操作在分别堆栈的两端进行，队列的插入和删除操作都是在队列的一端进行的。（）2. 线性

7、表中的每个结点最多只有一个前驱和一个后继。（）3. 堆栈是一个先进先出的线性表。（）4. 单链表形式的队列，头指针 F指向队列的第一个结点，尾指针R指向队列的最后一个结点。（）5. 树的逻辑结构是层次的。（）6. 单链表从任何一个结点出发，都能访问到所有结点。（）7. 常用的排序方法中，直接选择排序、堆排序、快速排序是稳定的，冒泡排序、简单插入排序等是不稳定的。（）&线性的数据结构可以顺序存储，也可以链接存储。（）9. 在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从 Vi到Vj的路径。（）10. 若一个有n个顶点的无向图为完全图，则该图有n*（n-1）条边。 （）四、简答题。请把

8、答案写在答题纸上，否则无分。（共5小题，每题6分共30分）1、 已知一棵二叉树的先根遍历序列和中根遍历序列分别是ABDGHECFI及GDHBEACIJF画 出这棵二叉树。2、写出下面有向图的拓扑排序序列。3、给定权值3, 12, 3, 15, 5, 4, 6, 8，构造相应的哈夫曼树，并求出其WPL4、已知一组元素的关键字46,74,16,53,14,26,40,38,86,65,27,34写出每次向前面的有序表插入一个元素后的排列结果。（6分），利用直接插入排序法,5、请采用普里姆（Prim）算法（从顶点1开始）和克鲁斯卡尔（ 图的最小生成树（请画出每一步的过程）。Kruskal ）算法分别

9、生成下112425522143783696 1六、程序题(共 2小题：每空1分)1. 将下面算法填完整。int Search_B in( SSTable ST, KeyType key)/在有序表ST中折半查找其关键字等于key的数据元素，若找到，则返回该元素/在表中的位置，否则返回 0low=1 ;high=ST .len gth;while(low<=high)mid= if(EQ(key, ST.elemmid.key) return;else if(LT(key, ST.elemmid.key) high=;else low= ;return ;2. 将下面算法填完整。void

10、In sertSort(SqList & L)/对顺序表L作直接插入排序for(i=2;i<=L .len gth;+i)if(LT(L.ri.key, L.ri-1.key)L.ri= ；for(j= ;LT(L.rO.key, L.rj.key);-j)L.rj+1=；L.rj+1= ；When you are old and grey and full of sleep,And no ddi ng by the fire, take down this book,And slowly read, and dream of the soft lookYour eyes had

11、 once, and of their shadows deep;How many loved your mome nts of glad grace,And loved your beauty with love false or true,But one man loved the pilgrim soul in you,And loved the sorrows of your cha nging face;And bending dow n beside the glow ing bars,Murmur, a little sadly, how love fledAnd paced u

12、pon the mountains overheadAnd hid his face amid a crowd of stars.The furthest dista nee in the worldIs not betwee n life and deathBut whe n I sta nd in front of youYet you don't know thatI love you.The furthest dista nee in the worldIs not whe n I sta nd in front of youYet you can't see my loveBut whe n un doubtedly knowing the love from bothYet cannot be together.The furthest dista nee in the worldIs not being apart while being in loveBut whe n I pla inly cannot resist the year ningYet prete nding