资源描述：
《数据结构试题-附答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、选择题1、在数据结构的讨论中把数据结构从逻辑上分为()A)内部结构与外部结构B)静态结构与动态结构C)线性结构与非线性结构D)紧凑结构与非紧凑结构。2、对线性表进行二分查找时，要求线性表必须()oA.以链接方式存储，且数据元素有序B.以链接方式存储C.以顺序方式存储,」[数据元素右序D.以顺序方式存储3、若长度为n的线性表釆用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为()A)O(n)B)0(1)C)0(n2)D)0(n3)4、顺序循环队列中(数组的大小为6),队头指示hont和队尾指示rear的值分别为3和0,当从队列中删除1个元素，再插入2个元素后
2、，front和rear的值分别为()A)5和1B)2和45.在下列排序方法中，(A.直接插入排序C.快速排序C)1和5P)4和2)的比较次数与记录的初始排列状态无关。B.起泡排序D.简单选择排序6、设有数组A[i,j],数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的存储首地址为()A)BA+41B)BA+180C)BA+222D)BA+2257、下面哪个术语与数据的存储结构无关()A)顺序表B)链表C)散列表D)队列8、在一棵高度为k的满二叉树中，结点总数为()A)2k_1B)2k上)
3、2-1D)Llog2kJ+l9、一棵完全二叉树上有10()1个结点，其中叶子结点的个数为()A)250B)500C)254D)50110、利用二叉链表存储树，则根结点的右指针是()A)指向最左孩子B)指向最右孩子C)空D)非空11、若邻接表中有奇数个边结点，则一定()A)图中有奇数个顶点B)图中有偶数个顶点C)图为无向图D)图为仃向图12、无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(%b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}^该图进行深度优先遍历，得到的顶点序列正确的是()A)abecdfB)acfebdC)a
4、ebcfdD)aedl'cb13、在一个带权连通图G中,权值最小的边一定包含在G的()A)最小生成树审B)深度优先生成树中C)广度优先生成树中D)深度优先生成森林中14、己知含1()个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()A)1.0B)2.9C)3.4D)5.515、下面的序列中初始序列构成最小堆(小根堆)的是()A)10、60、20、50、30、26、35、40B)70、40、36、30、20、16、2J10C)20、60、50、40、30、10、8、72二、应用题D)10、30、20、50、40、26、35、601
5、、已知一棵度为m的树中有山个度为1的结点，肥个度为2的结点，……，阳个度为m的结点，问该树中有多少个叶子结点？要求写出分析过程。2、己知一棵二叉树的中序遍历的结果为ABCEFGHD,后序遍历的结果为ABFHGEDC,试画出此二叉树。3、设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为：7,19,2,6,32,3,21,10。试为这八个字母设计哈夫曼编码，并求出总码长。4、对于下图，从顶点V0出发，按照普里姆算法求出它的最小生成树，画出求解过程。5、设散列表长度为11，散列函数H（a-）=a%11,给定的关键字序列为1,13,12,34,38,33,27,22。
6、试画出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率的情况下，这两种方法查找成功时的平均查找长度。6、对下面关键字序列，写出采用希尔排序算法进行排序的每一趟的结果。其中增量序列的取值为{5,3,l}o（125,11,22,34,15,44,76,66,100,8,14,20,2,5,1）三、编程题注意：先进行类型定义，再写算法。1、已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，使顺序表中的结点仍然是从小到大有序（不考虑空间不够用的情况）。2、设计一个算法，判断一个单链表中的各个结点值是否递增有序（带头结点的单链表）。3、
7、编写一个函数，求一棵给定二叉树中叶子结点的个数（提示：采用任何一种遍历方法都可以）。_、选择CCADBBDCDCDDABD二、1、设叶子个数为x总度数=ni+2*n2+3*n3+...+m*nm结点总数=ni+n2+...+nm+x而结点总数二总度数+1则x=l+n2+2*n3+...+(m-l)*nm厂V3、哈夫曼树的构造过程如下:5710(21假设八个字母分别为A、B、C、D.E、则这八个字母对应得编码为:A——1010B——00C——10000D——1001密封线内不要答题F——10001G——01H——1011WPL=
