• 一、选择题

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

• 
  

解析：本题考点是非空循环链表的特性。
因为是非空循环链表，所以尾结点的下一个结点应该是头结点。因此，本题参考答案是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的希尔排序过程。

解析：本题考点是希尔排序的基本过程。
上述数据希尔排序过程如下：
 


• 2、描述 49，38，65，97，76，13，27快速排序的过程。

解析：本题考点是快速排序的基本过程。
上述数据快速排序的基本过程如下：
 


• 3、从时间复杂度，空间复杂度方面简单分析快速排序，基数排序，堆排序，归并排序，简单排序。

解析：本题考点是各类排序算法的时间复杂度和空间复杂度。
答题要点：
 


• 四、算法题

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

解析：本题考点是2-路归并排序算法的具体实现。
本题参考答案如下：
 


• 2、先序遍历二叉树算法的实现。

解析：本题考点是先序遍历二叉树算法的具体实现。
本题参考答案如下：
 

来源：我是码农，转载请保留出处和链接！

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

• 数据结构习题及解析二2018-08-19 20:59
• 数据结构习题及解析三2018-08-19 21:09
• 数据结构习题及解析一2018-08-19 20:37