数据结构答疑2014资料.ppt

数据结构答疑;一、考试方式 闭卷笔试 二、考试的基本要求 本课程要求了解各种常用的数据结构、各种数据结构内涵的逻辑关系及其在计算机中的存储表示以及这些数据结构上的运算和实际的执行算法。掌握线性表、栈、队列的数据结构及各种操作和算法实现，树、图的逻辑结构及物理存储，常用的排序和查找算法。 ;三、考试题型及试卷结构 试卷有选择题占20%、是非题占20%、数据处理题占30%、编写算法题占30%。 四、例题解析 按照以上四种题型，选取部分例题，介绍解题思路及解答方法。 ;（一）选择题 1．采用线性链表表示一个向量时，要求占用的存储空间地址(??D? )。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．可连续可不连续 2．在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行( D )。 A．s-link=p-link; p-link=s; B．p-link=s; s-link=q; C．p-link=s-link; s-link=p; D．q-link=s; s-link=p; 3．设有两个串t和p，求p在t中首次出现的位置的运算叫做( B )。 A．求子串 B．模式匹配 C．串替换 D．串连接 4．将一个递归算法改为对应的非递归算法时，通常需要使用( A )。 A．栈 B．队列 C．循环队列 D．优先队列 ;5．在循环队列中用数组A[0..m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是( D )。 A．(front-rear+1)%m B．(rear-front+1)%m C．(front-rear+m)%m D．(rear-front+m)%m 6．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ D ）。 A．q一next=p一next；p一next=q； B．p一next=q一next；q=p； C．q一next=p；p一next=q； D．p一next=q一next；q一next=p； ;7．向二叉排序树中插入一个元素时，其时间复杂度大致为（ B ）。 A．O（1） B．O（1og2n） C．O（n） D O（nlog2n） 8．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（ D ）条边。 A．n B．n*(n+1)/2 C．n*n D．n-1 9．假定一棵完全二叉树的结点个数为50，则它的深度为（ D ）。 A．3 B．4 C．5 D．6 10．队列的另外一个别称是（ A ） A．先进先出表 B．后进先出表 C．链队列 D．顺序队列 ;11．一个算法的实现依赖于采用的（B ） A．逻辑结构 B．存储结构 C．时间复杂度 D．空间复杂度 12．一个数组第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是（ B ） A．110 B．108 C．100　　　　 D．120 13．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（ C ） A．edcba B．decba C．dceab　　　 D．abcde ;14．判断一个循环队列QU（最多元素为maxsize）为空的条件是（ A ） A．QU－front＝QU－rear B．QU－front！＝QU－rear C．QU－front＝（QU－rear＋1）％maxsize D．QU－front！＝（QU－rear＋1）％maxsize 15．如果一棵二叉树任意一层的结点数都达到该层的最多数,该二叉树称为（ C ） A．平衡二叉树 B．二叉排序树 C．满二叉树 D．完全二叉树 ;16．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（ A ）个元素。 A n-i B n-i+1 C n-i-1 D i 17．一个深度为k的满二叉树有（ B ）个结点 A．2k B．2k－1