当前位置:首页 » 数据结构习题解析 » 正文

数据结构习题及解析四

1786 人参与  2018年08月19日 21:19  分类 : 数据结构习题解析  评论
  • 一、选择题

    • 1、非空循环链表head 的尾结点 p 满足下列(     )条件。 
         A.head->next==p
         B.head==p
         C.p->next==head
         D.p->next==NULL

    • image.png

    • 数据结构习题解析及答案解析:本题考点是非空循环链表的特性。
      因为是非空循环链表,所以尾结点的下一个结点应该是头结点。因此,本题参考答案是C。 
    • 2、设栈s的类型为sqstack ,判定栈空的条件是(     )。 
         A.s == NULL
         B.s->top == 0 
         C.s.top == 0
         D.s.top == NULL

    • 数据结构习题解析及答案解析:本题考点是栈空的条件。
      判断栈空的条件是栈顶元素是否为0。因此,本题参考答案是B。 
    • 3、具有4个顶点的无向完全图有(     )边。 
         A. 20         
         B. 12            
         C.6           
         D.8

    • 数据结构习题解析及答案解析:本题考点是无向完全图的特性。
      4个点,最多可以连出6条线。n顶点完全图的边数为C(n,2)=n(n-1)/2,因此,本题参考答案是C。 
    • 4、一个向量的第一个元素的地址是100,每个元素的长度是2 ,则第五个元素的地址是(     )。 
         A.102
         B.110
         C.108
         D.120

    • 数据结构习题解析及答案解析:本题考点是向量中存储地址的计算方法。
      向量首地址是100,那么第i个元素的地址是100+(i-1)*2。因此,本题参考答案是C。 
    • 5、一个栈的输入序列是a,b,c,d,e ,则不可能输出是(     )。 
         A.ecdab
         B.cdeba
         C.decba
         D.abcde

    • 数据结构习题解析及答案解析:本题考点是栈的基本原理。
      由于输入序列中d在c之后输入,若在e输入之前d和c还未输出,那么将来输出时d一定在c之前输出。因此,本题参考答案是A。 
    • 6、已知二叉树的前、中根序列分别是abdefcg 和 defbagc,则该二叉树的后根遍历序列是(     )。 
         A.defbgca
         B.fedbgca
         C.abcdefg
         D.gfedcba

    • 数据结构习题解析及答案解析:本题考点是二叉树的遍历方法。
      由二叉树的前、中根序列可以确定这棵二叉树,再运用后根遍历方法得到后序序列。或者可以用排除法,因为先根序列为abdefcg,中根为defbagc,可以看出a为根结点,defb和gc分别为左、右子树,那么a必然是后根遍历序列的末结点,这样可排除C选项。再对defb和gc采用上述方法进行判定,可以排除A和D。因此,本题参考答案是B。 
    • 7、深度为4 的二叉树至多有个(     )结点。 
         A.12
         B.13
         C.14
         D.15

    • 数据结构习题解析及答案解析:本题考点是二叉树的特性。
      最少k个,最多2k-1个,因为你没有说明这是什么二叉树。如果是满二叉树那就是2k-1个。如果是完全二叉树,那最少是2k个,最多2k-1个。如果既不是满二叉树,也不是完全二叉树,那普通二叉树深度为k时的结点数量就是最少k个,最多2k-1个。因此,本题参考答案是D。 
    • 8、具有6个顶点的无向图至少要有(     )条边才能确保是一个连通图。 
         A.4
         B.5
         C.6
         D.7

    • 数据结构习题解析及答案解析:本题考点是连通图的基本概念。
      六个顶点在一条线上时,最少5条边,连通而不存在回路。因此,本题参考答案是B。 
    • 9、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为(     )
         A.da1+(i-1)*m
         B.da1+i*m
         C.da1-i*m
         D.da1+(i+1)*m

    • 数据结构习题解析及答案解析:本题考点是顺序表存储地址计算方法。
      由于第一个结点的地址为da1,那么第二个结点的地址就是da1+(2-1)*m=da1+m,以此类推,第i个结点的地址为da1+(i-1)*m。因此,本题参考答案是A。 
    • 10、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是(     ) 
         A.访问第i个结点(1<=i<=n)和求第i个结点的直接前趋(2<=i<=n)
         B.在第i个结点后插入一个新的结点(1<=i<=n)
         C.删除第i个结点(1<=i<=n)
         D.将n个结点从小到大排序.

    • 数据结构习题解析及答案解析:本题考点是操作顺序表时时间复杂度的计算方法。
      假设顺序表L,长度为n,求第i个节点L[i],直接前驱L[i-1],因此为O(1),答案B需要移动n-i个节点,因此为O(n),答案C也需要移动n-i个节点,答案D根据排序方法不同最慢O(n2),最快O(nlogn)。因此,本题参考答案是A。 
    • 11、直接插入排序算法的时间复杂度为(     ) 
         A.O(N) 
         B.O(1) 
         C.O(N2)
         D.O(LOGN)

    • 数据结构习题解析及答案解析:本题考点是直接插入排序算法的时间复杂度。
      直接插入排序的做法是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。插入过程的时间复杂度是O(N2)。因此,本题参考答案是C。 
    • 12、下列排序方法中,从平均时间而言最佳的是(     ) 
         A.快速 
         B.希尔 
         C.基数 
         D.归并

    • 数据结构习题解析及答案解析:本题考点是各种排序算法的时间复杂度。
      快速排序的平均时间为O(nlogn),速度最佳。因此,本题参考答案是A。 
    • 13、下列是稳定的排序方法的(     ) 
         A.快速 
         B.希尔 
         C.堆 
         D.基数

    • 数据结构习题解析及答案解析:本题考点是排序方法稳定性的判定。
      假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。上述选项只有基数排序满足稳定性的定义。因此,本题参考答案是D。 
    • 14.所需辅助空间为O(N)的排序方法为(     ) 
         A.快速 
         B.希尔 
         C.基数 
         D.归并

    • 数据结构习题解析及答案解析:本题考点是排序算法所需辅助空间的计算。
      快速排序为O(logn ),为栈所需的辅助空间;归并排序所需辅助空间最多,其空间复杂度为O(n);链式基数排序需附设队列首尾指针,则空间复杂度为O(rd )。希尔排序空间复杂度是O(1) 因为只有一个缓冲单元。因此,本题参考答案是D。 
    • 15、表达式通常用(     )表示 
         A.二叉树的先序 
         B.二叉树的中序 
         C.二叉树的后序 
         D.二叉树的层次

    • 数据结构习题解析及答案解析:本题考点是二叉树遍历的应用。
      表达式通常用二叉树的中序来表示,得到的表达式是中缀表达式。因此,本题参考答案是B。 
    • 16、构造哈希函数的方法不包括(     ) 
         A.直接定址 
         B.数字分析 
         C.折叠法 
         D.二分查找

    • 数据结构习题解析及答案解析:本题考点是构造哈希函数的方法。
      二分查找是查找算法,不能用来构造哈希函数。因此,本题参考答案是D。 
    • 17、哈希表中常用的处理冲突的方法不包括(     ) 
         A.开放定址 
         B.再哈希 
         C.链地址 
         D.折叠

    • 数据结构习题解析及答案解析:本题考点是哈希表中常用的处理冲突的方法。
      哈希表中常用的处理冲突的方法有开放定址法、再哈希法、链地址法和建立公共溢出区方法四种。因此,本题参考答案是D。 
    • 18、二叉排序树的特点不包括(     ) 
         A.右子树大于根的值 
         B.左子树小于根的值 
         C.左右子树为二叉排序树 
         D.左子树大于右子树的值

    • 数据结构习题解析及答案解析:本题考点是二叉排序树的特点。
      二叉排序树又称二叉查找树,亦称二叉搜索树。 它或者是一棵空树;或者是具有下列性质的二叉树:
      (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
      (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
      (3)左、右子树也分别为二叉排序树;
      因此,本题参考答案是D。 
    • 19、三个结点可以构成多少种二叉树(     ) 
         A.5
         B.6
         C.7
         D.4

    • 数据结构习题解析及答案解析:本题考点是二叉树的构造方法。
      3个结点的二叉树有5种形态:两层树:根左右;三层树: 根左(第二层)左(第三层)、根左(第二层)右(第三层)、根右(第二层)左(第三层)、根右(第二层)右(第三层)。因此,本题参考答案是A。 
    • 20、假设一个栈的进栈顺序为a,b,c,d,则不可能的出栈顺序为(     ) 
         A.a,b,c,d
         B.a,d,b,c
         C.d,c,b,a
         D.c,b,a,d

    • 数据结构习题解析及答案解析:本题考点是栈的特性。
      由于输入序列中c在b之后输入,若在d输入之前b和c还未输出,那么将来输出时c一定在b之前输出。因此,本题参考答案是B。 
    • 21、用邻接表表示图进行深度优先遍历时,通常采用(     )来实现算法.
         A.栈 
         B.队列 
         C.树 
         D.图

    • 数据结构习题解析及答案解析:本题考点是图的遍历过程。
      图进行深度优先遍历时采用栈作为存储结构,广度优先遍历时采用队列作为存储结构。 因此,本题参考答案是A。 
    • 22、已知L是带头结点的单链表,p指向表中某结点,则要删除p结点的后继结点应执行操作(     )。 
         A.p->next = p->next->next;
         B.p->next->next = p->next
         C.p->next = s; s->next = p->next;
         D.s->next = p->next; p->next = s;

    • 数据结构习题解析及答案解析:本题考点是单链表的删除操作。
      要删除单链表中的某结点,只要令该结点的前驱结点的next指向该结点的后继结点即可。 因此,本题参考答案是A。 
    • 23、求关键路径的时间复杂度为(     ) 
         A.O(N+E) 
         B.O(N+1)
         C.O(1+E)
         D.O(N2+1)

    • 数据结构习题解析及答案解析:本题考点是关键路径的时间复杂度的求法。
      设AOE网有n个顶点,e条边,在求事件可能的最早发生时间及允许的最迟发生时间,以及活动的最早开始时间和最晚开始时间时,都要对图中所有顶点及每个顶点边表中所有的边结点进行检查,时间花费为O(N+E)。因此,本题参考答案是A。 
    • 24、从具有n个结点的单链表中查找值等于x的结点时,在查找成功的情况下,平均需比较(     )个结点。 
         A.n
         B.n/2
         C.(n-1)/2
         D.(n+1)/2

    • 数据结构习题解析及答案解析:本题考点是单链表的查找操作。
      如果查找的是第一个是比较1次,第二个是2次,第n个是n次,要查找的元素每个概率相等即每个为1/n,所以平均是(1/n)(1+2+3+……n)=(1+n)/2次。查找失败是即是每个都查找了一遍都没找到所以是n次。因此,本题参考答案是D。 
    • 25、顺序结构中删除一个元素的平均时间为(     ) 
         A.1/N
         B.1/(N+1)
         C.1
         D.1/N2

    • 数据结构习题解析及答案解析:本题考点是顺序结构中元素的删除操作。
      在等概率的条件下,顺序结构中删除一个元素的平均时间为1/N。 因此,本题参考答案是A。 
    • 26、以下不属于数据结构的是(     ) 
         A.集合 
         B.线性结构 
         C.树形结构 
         D.环形结构

    • 数据结构习题解析及答案解析:本题考点是数据结构的种类。
      线性结构、图、树和集合等都属于数据结构,环形结构不属于数据结构。因此,本题参考答案是D。 
    • 27、以下不属于算法的特性的是(     ) 
         A.确定性 
         B.有穷性 
         C.输入 
         D.判断

    • 数据结构习题解析及答案解析:本题考点是算法的特性。
      一般说来,算法必须具备以下五个重要特性:确定性、可行性、输入、输出和有穷性,判断不是算法的特性。因此,本题参考答案是D。 
    • 28、线性表中插入元素的平均效率为(     ) 
         A.1/(n+1) 
         B.1/n
         C.O(1)
         D.O(N)

    • 数据结构习题解析及答案解析:本题考点是线性表中插入元素平均效率的计算方法。
      0,1,2,3,4,5,6,...n-1,n,每一个的可能是1/(n+1)。因此,本题参考答案是A。 
    • 29、空栈的判断条件是(     ) 
         A.top=n
         B.top=0
         C.bottom=n
         D.bottom=0

    • 数据结构习题解析及答案解析:本题考点是空栈的判断条件。
      栈顶元素为0的栈是空栈。因此,本题参考答案是B。
    • 30、栈的特点是(     ) 
         A.先进先出       
         B.一同进出       
         C.后进先出      
         D.后进后出

    • 数据结构习题解析及答案解析:本题考点是栈的特点。
      后进先出是栈最大的特点。这是因为前面先进栈的元素被后进栈的元素压在栈底,只有后进栈的元素出栈,先进栈的元素才有可能出栈。因此,本题参考答案是C。 
  • 二、填空题

    • 1、在n个结点的顺序表中,删除一个结点需平均移动_______个结点,具体的移动次数取决于____________。

    • 数据结构习题解析及答案解析:本题考点是顺序表的删除操作。
      具体移动次数取决于待删除元素所在的位置,比如删除倒数第1个,则移动次数为0,删除倒数第2个则移动次数为1,依此类推,删除倒数第i个,则需移动i-1次。而平均移动次数则取决于表长n、各待删除元素的位置及其被删除概率。设pi为删除第i个元素的概率,则平均移动次数为:p1*(n-1)+p2*(n-2)+p3*(n-3)+......+pn*0,如果是等概率,则pi=1/n,则平均移动次数为:(1/n)*(n-1)+(1/n)*(n-2)+...+(1/n)*1 = (1/n)*(1+2+...+(n-1)) = (n - 1) / 2。 
    • 2、在循环链表中,可根据在一结点的地址遍历整个链表,而单链表中需要知道_________才能遍历整个链表。

    • 数据结构习题解析及答案解析:本题考点是单链表的基本操作。
      双链表中,在任一结点可以向两边遍历。而在单链表中,只能从前往后遍历,不可以逆向,所以必须知道单链表的头指针才能遍历整个单链表。 
    • 3、在栈中存取数据的原则是:____________。

    • 数据结构习题解析及答案解析:本题考点是栈的特点。
      后进先出是栈最大的特点,也是栈中存取数据的原则。 
    • 4、在栈结构中,允许插入,删除的一端称为______,另一端称为_________。

    • 数据结构习题解析及答案解析:本题考点是栈的基本结构。
      在栈中,栈顶一端允许元素的插入和删除,栈底不能。 
    • 5、顺序表相对于链表的优点有_______和_________。

    • 数据结构习题解析及答案解析:本题考点是顺序表的优点。
      顺序表相对于链表主要优点有随机存取访问快、操作简单、容易实现等。 
  • 三、解答题

    • 1、49,38,65,97,76,13,27,49,55,4的希尔排序过程。

    • 数据结构习题解析及答案解析:本题考点是希尔排序的基本过程。
      上述数据希尔排序过程如下:
      image.png 
    • 2、描述 49,38,65,97,76,13,27快速排序的过程。

    • 数据结构习题解析及答案解析:本题考点是快速排序的基本过程。
      上述数据快速排序的基本过程如下:
      image.png 
    • 3、从时间复杂度,空间复杂度方面简单分析快速排序,基数排序,堆排序,归并排序,简单排序。

    • 数据结构习题解析及答案解析:本题考点是各类排序算法的时间复杂度和空间复杂度。
      答题要点:
      image.png 
  • 四、算法题

    • 1、2-路归并排序算法的实现。

    • 数据结构习题解析及答案解析:本题考点是2-路归并排序算法的具体实现。
      本题参考答案如下:
      image.png 
    • 2、先序遍历二叉树算法的实现。

    • 数据结构习题解析及答案解析:本题考点是先序遍历二叉树算法的具体实现。
      本题参考答案如下:
      image.png 

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=44

数据结构习题解析  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!