云南省-专升本十套-数据结构(试题及答案)

1、数据结构试卷(一)首先是选择题(每题2分，共20分)1.堆栈和队列的共同特征是()。A.仅在端点插入和删除元素B.他们都是先进后出C.他们都是先进先出D.没有共同点2.插入由链接存储的队列()。A.只修改头部指针。头部指针和尾部指针都应该被修改C.只修改尾部指针。头部指针和尾部指针都需要修改3.以下哪种数据结构是非线性的？()A.队列堆栈线性表格二叉树4.有一个二维数组。假设A00存储在644(10)，A22存储在676(10)，并且每个元素占用一个空间。询问A33(10)存放在哪里。脚注(10)用十进制表示。公元688年公元前678年公元前692年公元696年5.该树最适合用来表示()。A.

2、有序数据元素C.元素之间具有分支层次关系的数据6.二叉树第k层的最大节点数是()。A.2k-1 B.2K 1 C.2K-1 D. 2k-17.如果18个元素的有序列表被存储在一维数组A19中，第一个元素被放置在A1中，并且现在执行二分搜索法，则用于搜索A 3的比较序列的下标依次是()A.1，2，3B。9，5，2，3C.9，5，3D。9，4，2，38.为了快速排序N个记录的文件，所需的辅助存储空间大致如下A.O(1) B. O(n) C. O(1og2n) D. O(n2)9.当线性表(7，34，55，25，64，46，20，10)被散列时，如果选择H(K)=K %9作为散列函数，则存在散列地址

3、为1的()元素。a1 b . 2 c . 3d . 410.一个有6个节点的无向图应该至少有()条边，以确保它是一个连通图。A.5 B.6 C.7 D.8第二，填空(每空格1分，共26分)1.一般来说，算法的质量是从四个方面来评价的：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。2.算法的时间复杂度为(n3 n2log2n 14n)/n2，其数量级表示为_ _ _ _ _ _ _ _ _。3.假设树的广义表表示为A(C，D(E，F，G)，H(I，J)，树中的节点数为_ _ _ _ _ _ _

4、_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _4.后缀公式9 2 3-10 2/-的值是_ _ _ _ _ _ _ _。中缀公式(3 4X)-2Y/3对应的后缀公式为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。5.当使用链表存储二叉树时，除了数据字段之外，每个节点都有两个指向左子节点和右子节点的指针。在这种存储结构中，具有n个节点的二叉树有_ _ _ _ _ _ _ _ _ _个指针字段，其中_ _ _ _ _ _ _ _ _ _个指针为空指针。6.对于有向图和有N个顶点

5、和E条边的无向图，有_ _ _ _ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _7.AOV网络是_ _ _ _ _ _ _ _ _ _ _ _的图形。8.在有N个顶点的无向图中，有_ _ _ _ _ _ _ _ _条边，在有N个顶点的有向完全图中，有_ _ _ _ _ _ _ _ _条边。9.假设一个线性表是(12，23，74，55，63，40)。如果具有相同余数的元素成为子表，则四个子表是_ _ _ _ _ _ _ _ _ _

6、_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _10.在向B_树插入元素的过程中，如果根节点被拆分，新树的高度为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。11.在堆排序过程中，筛选任何分支节点的时间复杂度为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _12._ _ _ _ _ _ _ _

7、排序在快速排序、堆排序和合并排序中是稳定的。第三，计算题(每题6分，共24分)1.一个线性表被链接并存储在下面的数组A中，并且头指针是A 0。A 0 1 2 3 4 5 6 7数据605078903440然后35720412.请在下面画出邻接矩阵和邻接表。3.已知图的顶点集V和边集e是：V=1，2，3，4，5，6，7 ；E=(1，2)3，(1，3)5，(1，4)8，(2，5)10，(2，3)6，(3，4)15，(3，5)12，(3，6)9，(4，6)4，(4，7)20，(5，6)18，(6，7)25 ；最小生成树由Kruskar算法得到，最小生成树中依次得到的每条边都被写出。4.将数据4、2、

8、5、8和3添加到小根堆时，会绘制添加每个数据后堆的变化。第四，阅读算法(每题7分，共14分)1.链接列表我的笔记(链接列表L)/L是没有头节点的单个链表的头指针如果(L1-下一个)q=L；L=L-下一个；p=L；S1:而(p-next)p=p-next；S2:p-next=q；下一个=空；返回L；请回答以下问题：说明陈述S1的作用；(2)说明报表组S2的功能；(3)让链表表示的线性表为(a1，a2，an)，并在算法执行后写出返回值表示的线性表。2.作废作业成本法如果英国电信英国电信(英国电信-左)；英国电信(右)；coutdata该算法的功能是：V.用算法填空(共8分)搜索二叉查找树递归算法：

9、bool查找(b重新编码* BST，电子类型项目)如果(英国标准时间=空)返回false/搜索失败否则if(项目=BST-数据)项目=BST-数据；/搜索成功返回_ _ _ _ _ _ _ _ _ _ _ _ _ _；else if(itemdata)返回查找(_，项目)；否则返回查找(_，项目)；/如果六.编译算法(共8分)计算单个链表HL中值等于给定值x的节点数。int CountX(LNode* HL，ElemType x)数据结构试卷(2)第一，选择题(24分)1.下面关于线性表的说法是错误的()。(a)当按顺序存储时，线性表必须占据连续的存储空间线性表使用链式存储，不占用连续的存储空

10、间线性表采用链式存储，便于执行插入和删除操作线性表按顺序存储，以便于执行插入和删除操作2.让哈夫曼树的叶节点总数为m。如果使用二进制链表作为存储结构，哈夫曼树中有()个空指针字段。(甲)2m-1(乙)2m(丙)2m 1(丁)4m3.让顺序循环队列Q 0: m-1的头指针和尾指针分别为F和R。头指针F总是指向队列头元素的前一个位置，尾指针R总是指向队列尾元素的当前位置，因此循环队列中的元素数是()。甲、乙、丙、丁、丁、丁、丁、丁、丁、丁、丁4.假设二叉树的中序遍历序列是ABCD，前序遍历序列是CABD，那么通过以后序遍历二叉树得到的序列是()。(一)BADC(二)BCDA(三)CDAB(四)CB

11、DA5.如果完全无向图中有n个顶点，那么完全无向图中有()条边。(A)n(n-1)/2(B)n(n-1)(C)N2(D)N2-16.如果二叉树中有2000个节点，二叉树的最小高度为()。(甲)9(乙)10(丙)11(丁)127.如果有向图中有n个顶点，则有向图对应的相邻表中有()个头节点。(甲)n-1(乙)n(丙)n 1(丁)2n-18.让一组初始记录键序列(5，2，6，3，8)，并以第一个记录键5为基准进行快速排序，结果是()。(甲)2，3，5，8，6(乙)3，2，5，8，6(丙)3，2，5，6，8(丁)2，3，6，5，8第二，填空(24分)1.为了有效地应用HASH查找技术，必须解决两个问

12、题_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。2.以下程序段的功能是实现数据x的堆栈，并要求在下划线处填写正确的语句。typedef结构 int s100；int top sqstackvoid push(sqstack stack，int x)if (stack.top=m-1) printf(“溢出”)；否则 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _；3.通过以中间顺序遍历二进制排序树获得的序列是_ _ _ _ _ _ _ _ _ _序列

13、(按顺序或无序填充)。4.快速排序的最大时间复杂性是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。5.如果二叉树中0度节点数为N0，1度节点数为N1，则二叉树中2度节点数为_ _ _ _ _ _ _ _ _。如果使用二进制链表作为二叉树的存储结构，则二叉树中有_ _ _ _ _ _个空指针字段。6.设无向图的顶点数和边数分别为N和E，所有顶点的度数之和为D，则E=_ _ _ _ _ _。7.假设一组初始记录密钥序列是(55，63，44，38，75，80，31，56)，那么通过筛选方法建立的初始堆是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _。

14、8.众所周知，有向图的邻接表存储结构如下：从顶点1开始，DFS遍历的输出序列为，BFS遍历的输出序列是三、应用问题(36分)1.假设一组初始记录键序列为(45，80，48，40，22，78)，然后分别给出第4次简单选择排序和第4次直接插入排序的结果。2.让指针变量p指向双链表中的节点a，指针变量q指向插入的节点b，并要求在节点a后面插入节点b的操作序列(让双链表中节点的两个指针字段分别为llink和rlink)。3.让一组有序的记录键序列为(13，18，24，35，47，50，62，83，90)。搜索方法使用二分搜索法，这需要在搜索关键字62时计算比较次数，并在搜索成功时计算平均搜索长度。4.让树的边集是(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)。需要用孩子和兄弟的表示来表示树的存储结构(二进制链表)，并将树转换成相应的二叉树。5.有一个无向图G，它需要给出通过prim算法构造最小生成树的边集。6.有一组初始记录关键字(45，80，48，40，22，78)，这需要构造一个二进制排序树并给出构造过程。第四，算法设计题(16分)1.有一组初始记录密钥序列(K1，K2，Kn)。需要设计一种算法，在O(n)的时间复杂度内将线性表分成两部分，其中左半部分的每个键都小于Ki，右半部分的每个