《数据结构(含答案)》由会员分享，可在线阅读，更多相关《数据结构(含答案)（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构综合练习一、选择题1数据的存储结构包括顺序、链接、散列和( )4 种基本类型。A索引B数组C集合D向量2下面程序的时间复杂性的量级为()。int i=0，s1=0，s2=0；while(i+n)if (i%2)s1+=i;else s2+=i;A. 0(1) B.O(lbn) C.O (n)D.O(2n)3下面程序段的时间复杂度为( )。for(int i=0;im;i+)for(int j=0;jn ext=ph; B. p_n ext=ph; ph=p;C. p-next=ph; p=ph; D. p-next=ph-next; ph-next=p;11. 在一个表头指针为ph的单
2、链表中，若要在指针q所指结点的后面插入一个由指针p所 指向的结点，则执行（）操作。A. q-next=p-next; p-next=q;B. p-next=q-next; q=p;C. q-next=p-next; p-next=q;D. p-next=q-next; q-next=p;12. 在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（ ）操作。A. p=q-next; p-next=q-next;B. p=q-next; q-next=p;C. p=q-next; q-next=p-next;D. q-next=q-next-next; q-next=q
3、;13. 栈的插入和删除操作在（ ）进行。A.栈顶B.栈底C.任意位置D.指定位置14. 若让元素1， 2， 3， 4 依次进栈，则出栈次序不可能出现（ ）的 情况。A.3， 2， 1， 4 B.2， 1， 4， 3C.4，3，2，1 D.1，4，2，3.15. 假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则 判断队空的条件为（）。A.f+1=r B.r+1=f C.f=O D.f=r16. 假定一个顺序循环队列存储于数组aN，其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。A. （r-1） %N=f B. （r+1） %N=fC.（f-1） %N=r D.（f+1） %N
4、=r 17.二维数组A12,10采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（A0，0的地址）为1200，则A6，5的地址为（）。A.1400 B.1404 C.1372 D.146018在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.n B.n-1 C.n+1 D.2n19. 有如图1所示的一棵二叉树，则该二叉树的中序遍历序列为（）。A. ABCDEFG B. CDBGFEA C. CBDAEGF D. ABECDFG20. 有如图1所示的一棵二叉树，则该二叉树的先序遍历序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG
5、21. 有如图1所示的一棵二叉树，则该二叉树的后序便利序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG22利用n个值生成的哈夫曼树中共有（）个结 点。A.n B.n+1 C.2n D.2n-123.利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。A.55 B.29 C.58 D.3824在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的 度数为（）。A.n B.e C.n+e D.2e 25.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。A.n B.ne
6、C.e D.2e 26.若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点A开始 对该图进行深度优先搜索，得到的顶点序列可能为()。A. ABCFDE B. ACFDEB C. ABDCFE D. ABDFEC27. 若一个图的边集为 (A, B)(A, C) (B, D)(C, F)(D, E)(D, F)，则从顶点A开始 对该图进行广度优先搜索，得到的顶点序列可能为()。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE28. 对于顺序存储的有序表(5, 12, 20, 26, 37, 42, 46, 50, 64), 若采用二分查找
7、,则 查找元素 26 的查找长度为()。A.2 B.3 C.4 D.529. 若根据查找表(23, 44, 36, 48, 52, 73, 64, 58)建立线性哈希表，采用H (K) =K%13 计算哈希地址,则元素64的哈希地址为()。A.4 B.8 C.12 D.1330. 若根据查找表(23, 44, 36, 48, 52, 73, 64, 58)建立线形哈希表，采用H (K) =K%13 计算哈希地址,则哈希地址为 3 的元素个数为()。A.1 B.2 C.3 D.4 答案为 031. 若一个元素序列基本有序,则选用()方法较快。A.直接插入排序B.简单选择排序C.堆排序D.快速排序
8、二、填空题1数据的逻辑结构可分为和两大类。线性；非线性2. 数据的存储结构被分为, , 和4种。顺序；链式；索引；散列存储结构3. 种数据结构的元素集合K和它的二元关系R为：K=a,b,c,d,e,f,g,hR=，则该数据结构具有结构。线性4. 一种数据结构的元素集合K和它的二元关系R为：K=a,b,c,d,e,f,g,hR=, , , , , , 贝V该数据结构具有结构。非线性5线性表的两种存储结构分别为和。顺序；链式6. 在一个单链表中删除指针p所指向结点的后继结点时，需要把 的值赋给p-next指针 域。.p-n ext-n ext7. 栈又称为表，队列又称为表。先进后出；先进先出8.
9、假定一个链栈的栈顶指针为top,每个结点包含值域data和指针域next，当p所指向的结点入栈时，则首先执行操作，然后执行操作。 p-next=top;top=pABCE图 2DGIHF9队列的插入操作在进行，删除操作在进行。队尾；对头10. 在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为611. 对于一棵二叉树，若一个结点的编号i,若它的左孩子结点存在,则其编号为，若右孩子结点存在，则其编号为，若双亲结 点存在，则其编号为。2i； 2i+1； i/2国 L.912. 个森林转换成二叉树后如图1.9所示，则该森林中包含棵树。313. 若由3，6，8，12，10作为叶
10、子结点的值生成一棵哈夫曼树，则该树的深度为，带权路径长度为。4； 8714. 一种数据结构的元素集合K和它的二元关系R为：K=1, 2，3，4，5，6R=（1， 2）（2， 3）（2， 4）（3， 4）（3， 5）（3， 6）（4， 5）（4， 6）则该数据结构具有数据结构。图状15.假定对线性表（38，25, 74, 52, 48），进行散列存储，采用H （K） =K%7作为哈希函数,采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰到次冲突，平均查找长度为。5； 216.若对一组记录（46， 79， 56， 38， 40， 80， 35， 50， 74）进行直接插入排序，当把第 8
11、个记录插入到前面已排序的有序表时，为寻找插入位置需比 次。4三、简答题1.已知一棵二叉树的中序遍历序列为CDBAEGF，先序遍历序列为ABCDEFG，试问能不能唯一确定一棵二叉树？若能，画出该二叉树。若给定先序遍历序列和后序遍历序列，能否唯一 确定？18.（1）由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以唯一确定颗二叉树。由先序序列知，根结点最先被访问，就可确定根结点为A,而又由中序序列得 知一棵树的根结点是其左，右子树的分隔点,从而可确定以A为根的左子树的结点为B,C,D, 右子树的结点为E,F,G。重复进行就可得到二叉树。(2)由先序遍历序列和后序遍历序列不能唯一确定一
12、棵二叉树。因为两种遍历方法只能确 定根结点，而分不清左右子树。2.将图1.12所示的树转换成二叉树。3.试分别画出具有3个结点的树和3 个结点的二叉树的所有不同形态。树的状态如图1.21 所示.3 个结点的二叉树的状态如图 1.22 所示4.假定用于通信的电文由8个字母组成，分别是A，B，C，D，E，F，G,和H,各字母在电文中出现的 概率为：5%， 25%， 4%， 7%， 9%，12%， 30%， 8%，试为 8 个字母设计哈夫曼编码。5.给出一组关键字(19，01，26，92，87，11，43，87，21)，进行冒泡排序，列出每一遍排序后关键字的排列次序，并统计每遍排序进行的关键字比较次
13、数。初始关键字序列为：(19, 01, 26, 92, 87, 11, 43, 87, 21)第一遍排序比较8次，交换6次后成为：(01, 19, 26, 87, 11, 43, 87, 21, 92)第二遍排序比较7次，交换3次后成为：(01, 19, 26, 11, 43, 87, 21, 87, 92)第三遍排序比较6次，交换2次后成为：(01, 19, 11, 26, 43, 21, 87, 87, 92)第四遍排序比较5次，交换2次后成为：(01, 11, 19, 26, 21, 43, 87, 87, 92)第五遍排序比较4次，交换1次后成为：(01, 11, 19, 21, 26, 43, 87, 87, 92)第六遍排序比较3次，交换0次。排序完毕。6.已知一个顺
