资源描述：
《数据结构试题（华南理工大学）数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构试卷(二)一、选择题(24分)1.下面关于线性表的叙述错误的是()。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表釆用顺序存储便于插入和删除操作的实现2.设哈夫曼树屮的叶子结点总数为m,若用二叉链表作为存储结构，则该哈夫曼树屮总共有()个空指针域。(A)2m-l(B)2m(C)2m+l(D)4m3.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的
2、元素个数为()。(A)R-F(B)F-R(C)(R-F+M)%M(D)(F-R+M)%M4.设某棵二叉树的屮序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。(A)BADC(B)BCDA(C)CDAB(D)CBDA5.设某完全无向图中有n个顶点，则该完全无向图中有()条边。(A)n(n-l)/2(B)n(n-l)(C)n2(D)n2-l6.设某棵二叉树屮有2000个结点，则该二叉树的最小髙度为()o(A)9(B)10(C)11(D)127.设某有向图屮有n个顶点，则该有向图对应的邻接表屮有()个表头结点。(A)n-1(B)n(C)n+
3、1(D)2n-18.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,8二、填空题(24分)1.1.为了能有效地应用HASH查找技术，必须解决的两个问题是和02.2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-l)printff'ov
4、erflow");else{;；}}3.3.中序遍历二叉排序树所得到的序列是序列(填有序或无序)。4.4.快速排序的最坏时间复杂度为,平均时间复杂度为。5.5.设某棵二叉树中度数为0的结点数为No,度数为1的结点数为M，则该二叉树中度数为2的结点数为:若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有个空指针域。6.6.设某无向图屮顶点数和边数分别为n和c,所有顶点的度数Z和为山则。=o7.7.设一组初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为o3-4.5.6.V]->3->2->4v2->1->3v3->
5、1->4->21.8.设某无向图G的邻接表为5->1-〉3,则从顶点V】开始的深度优先遍历序列为;广度优先遍历序列为o三、应用题(36分)1.1.设一组初始记录关键字序列为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2.2.设指针变量p指向双向链表川结点A,指针变量q指向被插入结点B,要求给出在结点A的后血插入结点B的操作序列(设双向链表中结点的两个指针域分别为llink和rlink)o3.设一组有序的记录关键字序列为(13,18,24,35,47,50,法用二分查找，要求计算出查找关键字62时的比较次数并计算
6、出查找成功时的平均查找长度。4.设一棵树T中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。5.设有无向图G(如右图所示)，要求给出用普里姆算法构造最小生成树所走过的边的集合。6.设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。四、算法设计题(16分)1.1.设有一组初始记录关键字序列(K,,K2,KQ,要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均
7、小于右半部分的每个关键字均大于等于Ki。2.2・设有两个集合A和集合B,要求设计生成集合C=AAB的算法，其中集合A、B和C用链式存储结构表示。数据结构试卷（二）参考答案一.选择题l.D2.B3.C4.A5.A6.C7.B8.C二.填空题1.1.构造一个好的HASH函数，确定解决冲突的方法2・2.stack.top++,stack.s[stack.top]=x1.3.有序2.4.O(n2),O(nlog2n)3.5.N()-l,2N()+M4.6.d/25.7.(31,38,54,56,75,80,55,63)6.8.(1,3,4,2),(1,3,2,4)三、应用
8、题1.1.
