2018年武汉体育学院体育工程与信息技术学院615C语言程序设计及数据结构之数据结构考研核心题库-一、填空题1 阅读下列程序，指出其功能，并写出空格处应填上的语句。 【答案】【解析】本题是在哈希表2 已知如下程序段: 语句1执行的时间复杂度为_:语句2执行的时间复杂度为_:语句3执行的时间复杂度为_:语句4执行的时间复杂度为_。【答案】(1)n1 (2)n(3)n(n3)/2 (4)n(nl)/2【解析】语s 句1执行到不符合条件情况下，执行了n 1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为234. (nl) 加起来就是n(n3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了123. n 即n(nl)/2。 第 2 页，共 59 页 中插入值为item 的元素，如该元素已在哈希表中，报告出错。 3 设用希尔排序对数组98，36，-9，0，47，23，1，8，10，7进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_趟，写出第一趟结束后，数组中数据的排列次序_。【答案】3; (10，7，-9，0，47，23，1，8，98，36) 4 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【答案】O(1)；O(n)；O(1)；O(1)【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 5 二叉树的前序序列和中序序列相同的条件是_。【答案】空树或任何结点至多只有右子树的二叉树【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。 6 数组的存储结构采用_存储方式。【答案】顺序存储结构【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。7 克鲁斯卡尔算法的时间复杂度为_，它对_图较为适合。【答案】8 对n 个记录的表【答案】n (n1) /2【解析】第一次需要n 1次比较，第i 此需要n i 此比较，所以共需要9 有向图G=(V, E) ，其中，用三元组表示弧权d 。E(G)为 ，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。【答案】50；4 10个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 第 3 页，共 59 页；边稀疏进行简单选择排序，所需进行的关键字间的比较次数为_。及弧上的 11一棵有11个结点的满二叉树有_个度为1的结点、有_个分支(非终端) 结点和_个叶子，该满二叉树的深度为_。【答案】或 【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。12设广义表L (（ ），（ ）) ，则head(L)是_tail(L)是_L的长度是_；深度是_。【答案】（ ）；(（ ）) ；2；2【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 二、单项选择题13某计算机存储器按字节编址, 主存地址空间大小为64MB ,现用32MB 的主存储器, 则存储器地址寄存器MAR 的位数至少是（ ）。A.22位 B.23位 C.25位 D.26位 【答案】D【解析】虽然实际的主存储器(RAM区) 只有32MB , 但不排除还有ROM 区, 考虑到存储器扩展的需要, MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。 14ARP 协议的功能是（ ）。A. 根据IP 地址查询MAC 地址 B. 根据MAC 地址查询IP 地址 C. 根据域名查询IP 地址 D. 根据IP 地址查询域名 【答案】A 。【解析】ARP 协议是网络层协议, 因此只能和传输层和数据链路层有关系, 从这一点出发, 域名是应用层的范畴, 选项C 和D 是不正确的, 根据MAC 地址查询IP 地址是RARP 协议的功能, 因此进而得出正确答案是A 。 15折半查找的时间复杂性为（ ）。A. B.O(n)第 4 页，共 59 页位的RAM 芯片组成-一、填空题-考研试题-