数据结构复习——wsdchong

数据结构复习

考试方式：闭卷，180分钟、满分150

题型：单选题（20*2）、综合应用题（70分，7题）

试卷结构：共四门课，数据结构、计算机组成原理、操作系统、计算机网络。其中数据结构占47分，单选（1-11）、综合应用题（41题算法设计题13分；42题应用题12分）

第一章  绪论

1程序段： c = 0 ;

         for( i=0 ; i<m ; i++ )

                 for( j=0 ; j<n ; j++ )

                    c = c + i*j ;

         的时间复杂度为＿＿＿＿

O( m2 )   B）O( n2 )   C）O(m×n)    D）O(m+n)

第二章  线性表

1在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）

  　 A．p->next=s;s->next=p->next;

  　 B．s->next=p->next;p->next=s;

　   C．p->next=s;p->next=s->next;

   　D．p->next=s->next;p->next=s;

第三章  栈与队列

1设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。
　　A. 1，2，4，3，     B. 2，1，3，4，     C. 1，4，3，2，
　　D. 4，3，1，2，     E. 3，2，1，4

第四章  串

1串‘ababaaababaa’的next数组为（ ） 。

      A. 012345678999      B 012121111212  

      C. 011234223456     D. 0123012322345

第五章  数组

1假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）

　　 A.808       B.818       C.1010      D.1020

第六章  树与二叉树

1已知二叉树的后序序列为：FDEBHGCA，中序序列为：BFEDAGHC，则其先序序列为：_________。

     A）ABEDFGCH                  B）ABCEGFDH   

     C）ABCEFDGH                  D）ABEFDCGH

2一棵共有23个结点的二叉树中，树中除度为2的结点外其它均为叶子结点，那么该树中叶子结点的个数是_________个。

     A）9       B）10      C）11        D） 12

3具有64个结点的完全二叉树的深度为_______。

       A) 5           B) 6             C) 7         D) 8

第七章  图

1要连通具有n个顶点的有向图，至少需要_______条边。

     A．n-l        B．n         C．n+l        D．2n

第八章  查找

1在长度为12的有序表中，按折半查找法对表进行查找，在表内各元素等概率情况下查找成功的平均查找长度为_______。

      A）43/12       B）39/12      C）37/12        D）35/12

第九章  排序

1下列排序方法中，时间效率最高的排序算法是______。

     A）直接插入排序  B）归并排序  C）简单选择排序  D）冒泡排序