数据结构模拟试题及答案

数据结构模拟试题3I .选择题1.头节点的单向链表为空的判断条件是()(将头指针设为头)。A.head=空B.head！=空头下一个=头下一个=空2.非空单向循环链表的尾节点满足()(将头指针设置为头，指针P指向尾节点)。下一个=空，下一个=头3.该算法的时间复杂度与()。A.计算机操作系统C.算法本身d .数据结构4.有一个长度为n的序列表。要移动以删除第I个元素的元素数是()。A.n-i 1 B.n-i C.n-i-1 D.i5.在单个链表中，当在由P表示的节点之后插入由S表示的节点时，可以执行()。A.p=新文本A.p文本=新文本；C.snext=pnext。pnext=s。D.pnext=s。snext=pnext6.在链式团队中，假设F和R分别是团队头指针和团队尾指针，删除节点的操作是()。A.r=fnext。B.r=rnext。C.f=fnext。D.f=rnext。7.如果元素1、3、5和7按顺序堆叠，那么堆叠的不可能输出序列是()(堆叠可以交替进行)。A.7，5，3，1 B.7，5，1，3C.3，1，7，5 D1，3，5，78.在C语言中，长度为3的字符串按顺序存储，这需要()字节。a4 b . 3 c . 6d . 129.在二叉树中，如果编号为I的节点有左子节点，则左子节点的序号为()。a2i b . 2i-1 c . 2i 1d . 2i 210.一个完整的二叉树有35个节点，最后一层有()个节点。a4 b . 6 c . 16d . 811.在无向图中，所有顶点的度数之和等于()乘以边数。a3 b . 2 c . 2.5d . 1.512.称为图3所示的图，如果从顶点V1开始，按照广度优先法进行遍历，可能得到的顶点序列是()。A.v1v 2v 4v 8v 5v 3v 6v 7 B . v1v 2v 4v 5v 8v 3v 6v 7C.v1v 2v 4v 8v 3v 5v 6v 7D . v1v 3v 6v 7v 2v 4v 5v 8V6V7第五颅神经的眼支V2V3V8V4V5图313.二叉树()遍历可以使通过遍历获得的序列成为有序序列。A.根据b级，按照顺序c，中间顺序d，前一个顺序14.按顺序设置现有的M个元素，在没有良好顺序的序列中选择m 1个元素，并在仅交换一次元素后使m 1个元素就位。方法是()。A.二进制排序b .冒泡排序c .合并排序d .简单选择排序15.一组记录的关键序列是(47，80，57，39，41，46)，通过堆排序建立的初始堆(堆的顶部元素是最小的元素)是()。39，47，46，80，41，5739，80，46，47，41，57，80二。填空1.该算法的五个特征是_ _ _ _ _ _。2.需要在N个数据元素中找到值最大的元素，并将基本操作设置为元素之间的比较。那么比较的次数和算法的时间复杂度分别是_ _ _ _ _ _和_ _ _ _ _ _。3.在单向链表中，当在由P指向的节点后插入一个由S指向的节点时，应该执行S-next=P-next；和的操作。4.在单向链表中，要删除由P表示的节点，已知Q指向由P表示的节点的前一个节点。5.当将由s指向的节点插入栈顶指针为h的链栈时，可以执行s-next=h；和操作。(节点的指针字段是下一个)6.在链式团队中，如果F和R分别是团队头指针和团队尾指针，那么插入S所指向的节点的操作是R-next=S；和(节点的指针字段是下一个)。7.两个字符串相等的充要条件是_ _ _ _ _ _。8.在二叉树的链式存储结构中，通常在每个节点上设置三个字段，即_ _ _ _ _ _、9.二叉树有2n-2条边(节点之间的连接)，每个非叶节点的度数为2，因此该树有_ _ _ _ _ _个非叶节点。10.图1所示的二叉树，其中序列遍历序列是_ _ _ _ _ _。gfabdecefgibachd图2图111.如图1所示，二叉树具有_ _ _ _ _ _ _ _序列。12.哈希函数是在记录键值和记录存储地址之间构造的对应关系。13.n个元素按冒泡方法排序，这通常需要_ _ _ _ _ _个冒泡行程，j个冒泡行程需要_ _ _ _ _ _个元素比较。三。综合问题1.已知序列11，19，5，4，7，13，2，10(1)当序列通过合并排序方法按升序排序时，尝试给出每次通过的结果。(2)对于上述序列，通过堆排序方法建立初始堆(需要小根堆，堆构建过程用二叉树描述)。2.将查找表设置为(7，15，21，22，40，58，68，80，88，89，120)，元素的下标为1，2，3，依次11。(1)绘制对应于查找表的二进制搜索的决策树(树中的节点由下标表示)(2)解释成功找到元素40需要多少次比较？(3)在等概率条件下，找到平均成功搜索次数？3.(1)如果二叉树中任何节点的值大于其左子节点的值，小于其右子节点的值，则该树为二进制排序树。这个陈述正确吗？如果你认为它是正确的，答案是正确的；如果你认为这不正确，举个例子。(2)有数据集40，29，7，73，101，4，55，2，81，92，39，该集中的每一个数据被依次用来构造二进制排序树。4.(1)“如果二叉树的根节点的值大于左子树的所有节点的值并且小于右子树的所有节点的值，则该树必须是二进制排序树”。这句话是否正确，如果被认为是正确的，那么答案是正确的，如果不是，那么给出理由？(2)有查找表7，16，4，8，20，9，6，18，5，这些表中的数据被依次用来构造二进制排序树。给出了二叉树后续遍历的结果。5.(1)为给定的权重2，1，3，3，4，5构造霍夫曼树。(2)用上述权重构造另一个哈夫曼树，使两个哈夫曼树具有不同的高度，并分别计算两个树的加权路径长度。四、程序填空1.以下是通过尾部插入法建立一个有n个节点和一个头节点的单向链表的过程。节点中的数据字段是1、2、3，n，从前到后依次完成程序的空白部分。节点*创建(n)NODE *head，*p，* q；int I；p=(NODE *)malloc(sizeof(NODE)；head=；pnext=空；/*创建头节点*/对于(I=1；i=n。(I) p=；p-数据=I；p-next=空；q-next=；返回(头)；2.将线性表设置为(6，10，16，4)。下面的程序通过解释结构变量建立一个单向链表，并输出链表中每个节点的数据。#定义空值0void main()NODE a，b，c，d，*head，* p；a .数据=6；b .数据=10；c.data=16d .数据=4；/*d是尾部节点*/head=；a.next=b。b . next=c；c . next=d；/*以上表构建过程完成*/p=head/*p是工作指针，准备输出链表*/做printf(%dn ，)； while()；3.下面的程序是遍历二叉树的递归算法程序，完成了程序的空白部分(在树形结构中，左、右指针字段分别为左、右，数据字段数据为字符型，BT指向根节点)。无效排序器(结构BTreeNode *BT)如果(英国电信！=空)；4.下面的程序是遍历二叉树的递归算法程序，完成了程序的空白部分(在树形结构中，左、右指针字段分别为左、右，数据字段数据为字符型，BT指向根节点)。无效排序器(结构BTreeNode *BT)efabcd如果(英国电信！=空)(1)；(2)；一级(英国电信-右)；使用上面的程序遍历正确的图片，结果是：综合练习题的答案I .选择题1.D 2。D 3。C 4。B 5。C 6。C 7。B 8。A 9。A 10。A 11。B 12。A 13。C 14。D 15。B第二，填空1.贫困、确定性、可行性、零个或多个投入、一个或多个投入2.n-1，O(n)3 . s-next=p-next；4 . q-next=p-next；5 . s-next=h；6 . r-next=s；7.字符串长度相等，对应位置的字符相等。8.范围，左指针，右指针9.n-110 . dgbaeachif11.gdbeihfca12.存储器地址13.n-1，n-j三。综合问题1.(1)初始11、19、5、4、7、13、2、10第一次旅行11，19 4，5 7，13 2，10第二趟4，5，11，19 2，7，10，13第三趟2，4，5，7，11，10，11，13(2)2101151974131351011197247131013191125419247105112.(1)4711852101396(2)4次(3)ASL=(1 2*2 3*4 4*4)/11=33.1542(1)不正确，例如395592814101724073529(2)4.(1)不正确，二进制排序树要求其子树也是二进制排序树。468952071618(2)后续遍历5，6，4，9，8，18，20，16，7534181176