数据结构(含答案)

1、数据结构的综合练习一、选择题1.数据存储结构包括四种基本类型：顺序、链接、哈希和()。数组集合向量2.以下程序的时间复杂度为()数量级。int i=0，s1=0，S2=0；而(i next=phb . p-next=ph；ph=p；C.p-next=ph；p=ph。d . p-next=ph-next；ph-next=p；11.在一个链表中，头中的指针是ph，如果你想在指针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-n

2、ext；q-next=p；12.在单个链表HL中，如果你想删除指针q所指向的节点的后继节点(如果有的话),那么执行()操作。A.p=q-下一个；p-next=q-next；B.p=q-下一个；q-next=p；C.p=q-下一个；q-next=p-next；D.q-next=q-next-next；q-next=q；13.在()中插入和删除堆栈。A.堆栈顶部堆栈底部任意位置指定位置14.如果元素1、2、3和4依次堆叠，堆叠顺序中不可能有()。A.3，2，1，4 B.2，1，4，3C.4，3，2，1 D1，4，2，315.假设顺序循环队列的头指针和尾指针分别由f和r表示，那么判断团队空缺的条件是

3、()。a . f 1=r . b . r 1=f . c . f=0 . d . f=r16.假设顺序循环队列存储在数组aN中，其队列头和队列尾指针分别为对于f和r，判断队列是否满的条件是()。A.(r-1)%N=f B.(r 1)%N=fC.(f1)% N=r d .(f1)% N=r17.二维数组A12，10采用先行存储，每个数据元素占用4个存储空间单位，数组的第一个地址(A 0，0的地址)是1200，然后是A 6，5的值地址是()。公元1400年至1404年，公元1372年至1460年18.在具有n个节点的二叉树中，所有节点的空子树的数量等于()。a . n . b . n-1 c .

4、n 1d . 2n19.如果有如图1所示的二叉树，二叉树的中间顺序遍历序列是()。A.ABCDEFG20.如果有如图1所示的二叉树，二叉树的第一个遍历序列是()。A.ABCDEFG银行21.如果有一棵二叉树，如图1所示，二叉树后一个顺序的方便顺序是()。A.ABCDEFG银行22.霍夫曼树中有()个节点由n个值生成。a . n . b . n . 1 c . 2n d . 2n-123.使用3、6、8和12作为叶结点的权重，生成一棵霍夫曼树，该树具有权重路径长度为()。公元前55年，公元前29年，公元58年24.在有n个顶点的无向图中，如果有e条边，那么所有的顶点学位是()。a . n . b

5、 . e . c . n . D225.在有n个顶点和e条边的无向图的邻接矩阵中，边是存在的中的元素数(也称为有效元素)是()。a . n . b . ne . c . e . d . 2e26.如果图的边集是(A，B)(A，C)(B，D)(C，F)(D，E)(D，F)，则首先从顶点A搜索图的深度，并且获得的顶点序列可以是()。A.美国对外经济合作委员会27.如果图的边集是(A，B)(A，C)(B，D)(C，F)(D，E)(D，F)，则首先从顶点A开始搜索图的宽度，并且获得的顶点序列可以是()。A.美国广播公司28.对于顺序存储的有序表(5，12，20，26，37，42，46，50，64)，如

6、果采用二分搜索法，搜索元素26的搜索长度为()。a2 b . 3 c . 4d . 529.如果根据查找表(23，44，36，48，52，73，64，58)建立线性哈希表，并且哈希地址由h (k)=k计算，则元素64的哈希地址是()。a4 b . 8 c . 12d . 1330.如果根据查找表(23，44，36，48，52，73，64，58)建立线性哈希表，并且哈希地址由h (k)=k计算，则哈希地址为3的元素的数量为()。答案是031.如果一个元素序列基本上是有序的，那么选择()方法会更快。A.直接插入排序简单选择排序堆排序快速排序第二，填空1.数据的逻辑结构可以分为两类：_ _ _ _和

7、_ _。线性度；非线性的2.数据存储结构分为四种类型：_ _ _ _ _、_ _ _ _、_ _ _ _和_ _ _ _ _。秩序。链条；索引；哈希存储结构3.数据结构的元素集K和它的二元关系r是：K=a，b，c，d，e，f，g，hR=，那么数据结构有一个_ _ _ _ _结构。线性的4.数据结构的元素集K和它的二元关系r是：K=a，b，c，d，e，f，g，hR=，则数据结构有_ _ _ _ _结构。非线性的5.线性表的两种存储结构是_ _ _ _ _和_ _ _ _ _。秩序。链式模式6.当删除单个链表中指针P指向的节点的后继节点时，有必要给下一个指针字段赋值_ _ _ _。p-下一个-下一

8、个7.堆栈也称为_ _ _ _ _表，队列也称为_ _ _ _ _表。先进后出；先入先出8.假设链栈的顶部指针是top，每个节点包含一个值字段数据和一个指针字段。当P指向的节点进入堆栈时，首先执行_ _ _ _ _操作，然后执行_ _ _ _ _操作。p-next=顶部；top=pABCE图2DGIHF9.队列在_ _ _ _ _插入，在_ _ _ _ _删除。团队尾。宾果游戏10.在二叉树中，假设双分支节点的数量是5，单分支节点的数量是6，叶节点的数量是_ _ _ _。611.对于二叉树，如果一个节点及其左子节点的个数为1，它的编号是_ _ _ _ _，如果存在正确的子节点，它的编号是_ _

9、 _ _ _，如果父母已经结婚。如果一个点存在，它的数目是_ _ _ _。2i；2i 1；i/212.如图1.9所示，将一个林转换成二叉树后，该林包含_ _ _ _ _棵树。313.如果使用3、6、8、12和10作为叶节点的值来生成霍夫曼树，则树的深度为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 4；8714.数据结构的元素集k及其二元关系r是：K=1，2，3，4，5，6R=(

10、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)被直接插入并排序，当将第八条记录插入到排序的有序表中时，有必要比较_ _ _ _ _次以找到插入位置。4Iii .简短回答问题1.众所周知，二叉树的中间顺序遍历

11、序列是CDBAEGF，第一顺序遍历序列是ABCDEFG。你能唯一地确定一棵二叉树吗？如果是，画二叉树。给定前序遍历序列和后序遍历序列，它能唯一确定吗？18.(1)二叉树可以由中间顺序遍历序列和第一顺序遍历序列，或者中间顺序遍历序列和最后顺序遍历序列唯一确定。根据前序序列，当首先访问根节点时，可以确定根节点是A，并且从中间序列，可以确定树的根节点是其左和右子树之间的分离点，使得以A为根的左子树的节点是B、C、D，而右子树的节点是E、F、G、F、G.重复得到二叉树。(2)二叉树不能由第一遍历序列和第二遍历序列唯一确定。因为这两种遍历方法只能确定根节点，而不能区分左右子树。2.将图1.12所示的树转

12、换成二叉树。3.试着画出所有不同形式的三节点树和三节点二叉树。树的状态如图1.21所示。三个节点的二叉树的状态如图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)，进行冒泡排序，列出每次排序后关键词的排序顺序，统计每次排序的关键词比较次数。初始关键字序列是：(19，01，26，92，87，11，43，87，21)第一次排序和比较是8次，经过6次交换，变成：(01，19，26，8

13、7，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次，交换一次后变成：(01，11，19，21，26，43，87，87，92)在第六次中，排序被比较3次并被交换0次。订购完成。6.知道按顺序存储的有序表是(15，26，34，39，45，56，58，63，74，6)，尝试画出相应的二分搜索法决策树并找到其平均搜索长度。二分搜索法决策树如图1.31所示。平均搜索长度：ASL=(1 22 34 43)/10=2.97.有一组关键字(17，13，14，153，29，35)要插入到长度为12的哈希表中。请回答以下问题：(1)设计一