数据结构(含答案).pdf

《数据结构(含答案).pdf》由会员分享，可在线阅读，更多相关《数据结构(含答案).pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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.O(1)B.O(1bn)C.O（n）D.O(2n)3下面程序段的时间复杂度为（）。for(int i=0;im;i+)for(int j=0;jnext=ph;B.p-next=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;13.栈的插入和删除操作在（）

3、进行。A.栈顶 B.栈底 C.任意位置 D.指定位置 14.若让元素 1，2，3，4 依次进栈，则出栈次序不可能出现（）的 情况。A.3，2，1，4 B.2，1，4，3 C.4，3，2，1 D.1，4，2，3.15.假定一个顺序循环队列的队首和队尾指针分别用 f 和 r 表示，则 判断队空的条件为（）。A.f+1=r B.r+1=f C.f=0 D.f=r 16.假定一个顺序循环队列存储于数组 aN，其队首和队尾指针分别 欢迎下载 3 用 f 和 r 表示，则判断队满的条件为（）。A.（r-1）%N=f B.（r+1）%N=f C.（f-1）%N=r D.（f+1）%N=r 17.二维数组 A

4、12,10采用行优先存储，每个数据元素占用 4 个存储 单元，该数组的首地址（A0，0的地址）为 1200，则 A6，5的 地址为（）。A.1400 B.1404 C.1372 D.1460 18.在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（）。A.n B.n-1 C.n+1 D.2n 19.有如图 1 所示的一棵二叉树，则该二叉树的中序遍历序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG 20.有如图 1 所示的一棵二叉树，则该二叉树的先序遍历序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG

5、21.有如图 1 所示的一棵二叉树，则该二叉树的后序便利序列为（）。A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG 22.利用 n 个值生成的哈夫曼树中共有（）个结点。A.n B.n+1 C.2n D.2n-1 23.利用 3，6，8，12 这 4 个值作为叶子结 点的权，生成一棵哈夫曼树，该树的带 权路径长度为（）。A.55 B.29 C.58 D.38 24.在一个具有 n 个顶点的无向图中，若具有 e条边，则所有顶点的 度数为（）。A.n B.e C.n+e D.2e 25.在一个具有 n 个顶点和 e 条边的无向图的邻接矩阵中，表示边存 在的元素（又称为

6、有效元素）的个数为（）。A.n B.ne C.e D.2e 26.若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点 A 开始 欢迎下载 4 对该图进行深度优先搜索，得到的顶点序列可能为（）。A.ABCFDE B.ACFDEB C.ABDCFE D.ABDFEC 27.若一个图的边集为（A，B）（A，C）（B，D）（C，F）（D，E）（D，F），则从顶点 A 开始对该图进行广度优先搜索，得到的顶点序列可能为（）。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE 28.对于顺序存储的有序表（5，12，20，26，37，42，46，50，6

7、4），若采用二分查找，则查找元素 26 的查找长度为（）。A.2 B.3 C.4 D.5 29.若根据查找表（23，44，36，48，52，73，64，58）建立线性哈希表，采用 H（K）=K%13计算哈希地址，则元素 64 的哈希地址为（）。A.4 B.8 C.12 D.13 30.若根据查找表（23，44，36，48，52，73，64，58）建立线形哈希表，采用 H（K）=K%13计算哈希地址，则哈希地址为 3 的元素个数为（）。A.1 B.2 C.3 D.4 答案为 0 31.若一个元素序列基本有序，则选用（）方法较快。A.直接插入排序 B.简单选择排序 C.堆排序 D.快速排序 二填空

8、题 1.数据的逻辑结构可分为_ _和_ _两大类。线性；非线性 2.数据的存储结构被分为_，_，_和_4 种。顺序；链式；索引；散列存储结构 3.一种数据结构的元素集合 K 和它的二元关系 R 为：K=a,b,c,d,e,f,g,h R=，则该数据结构具有_结构。线性 4.一种数据结构的元素集合 K 和它的二元关系 R 为：K=a,b,c,d,e,f,g,h R=，则该数据 结构具有_结构。非线性 5.线性表的两种存储结构分别为_和_。顺序；链式 6.在一个单链表中删除指针 p 所指向结点的后继结点时，需要把_ 的值赋给 p-next 指针域。.p-next-next 7.栈又称为_表，队列又

9、称为_表。欢迎下载 5 先进后出；先进先出 8.假定一个链栈的栈顶指针为 top，每个结点包含值域 data 和指针域 next，当 p 所指向的结点入栈时，则首先执行_操作，然后执行_操作。p-next=top;top=p ABCE 图 2DGIHF 9.队列的插入操作在_进行，删除操作在_进行。队尾；对头 10.在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为_。6 11.对于一棵二叉树，若一个结点的编号 i，若它的左孩子结点存在，则其编号为_，若右孩子结点存在，则其编号为_，若双亲结 点存在，则其编号为_。2i；2i+1；i/2 12.一个森林转换成二叉树后如图

10、 1.9 所示，则该森林中包含_棵树。3 13.若由 3，6，8，12，10 作为叶子结点的值生成一棵哈夫曼树，则该树的深度为_，带权路径长度为_。4；87 14.一种数据结构的元素集合 K 和它的二元关系 R 为：K=1，2，3，4，5，6 R=（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；2 16.若对一组记录（46，79，56，

11、38，40，80，35，50，74）进行直接插入排序，当把第 8个记录插入到前面已排序的有序表时，为寻找插入位置需比较_次。4 三、简答题 1.已知一棵二叉树的中序遍历序列为 CDBAEGF，先序遍历序列为 ABCDEFG，试问能不能唯一确定一棵二叉树？若能，画出该二叉树。若给定先序遍历序列和后序遍历序列，能否唯一确定？18.(1)由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以唯一确定一 欢迎下载 6 颗二叉树。由先序序列知，根结点最先被访问，就可确定根结点为A，而又由中序序列得知一棵树的根结点是其左，右子树的分隔点，从而可确定以A 为根的左子树的结点为B,C,D,右子树的结

12、点为E,F,G。重复进行就可得到二叉树。（2）由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。因为两种遍历方法只能确定根结点，而分不清左右子树。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 个字母设计哈夫 欢迎下载 7 曼编码。5.给出一组关键字（19，01，26，92，8

13、7，11，43，87，21），进行冒泡排序，列出每一遍排序后关键字的排列次序，并统计每遍排序进行的关键字比较次数。初始关键字序列为：（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，

14、11，19，21，26，43，87，87，92）第六遍排序比较3次，交换0次。排序完毕。6.已知一个顺序存储的有序表为（15，26，34，39，45，56，58，63，74，6），试画出对应的二分查找判定树，求出其平均查找长度。折半查找判定树如图 131 所示。平均查找长度：ASL=（1+223443）/10=2.9 7.设有一组关键字（17，13，14，153，29，35）需插入到表长为 12 的散列表中，请回答下列问题：欢迎下载 8（1）设计一个适合该散列表的哈希函数。（2）用设计的哈希函数将上述关键字插入到散列表中，用线性探测再散列法解决冲突，画出其结构，并指出构造散列表的装填因子为多少？（1）由于散列表的长度为 12，则可选不超过表长的最大素数 11 作为除留余数法的模，则可得其哈希函数为 H（k）=k%11。（2）若用线性探测再散列法解决冲突，则可构造出散列表如下：此时，其装填因子为 6/12=1/2，若用链式法解决冲突，则其散列表如图 128 所示。