东大17年12月考试《数据结构Ⅰ》复习题题目

网院作业

数据结构I笔试复习题（高起专）（2017-04-20）
一、单选题（每小题2分）
1. 数据的不可分割的最小标识单位是
    A. 数据项                           B. 数据记录
    C. 数据元素                         D. 数据变量
2．下列程序段 for(i=1;i<=n;i++) A[i,j]=0;的时间复杂度是
A. O(1)                             B. O(n/2)   
C. O(n2)                             D.  O(n)  
3. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
    A.n-i+1                             B.n-i
    C.i                                 D.i-1
4．在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
    A. s->next=p->next;p->next=s;       B. s->next=p; q->next=s
    C. q->next=s;s->next=p;             D. p->next=s;s->next=q;
5. 判断两个串大小的基本准则是
A. 两个串长度的大小                B. 两个串中首字符的大小
C. 两个串中大写字母的多少          D. 第一个不等字符的大小参考答案：1、A  2、D  3、A  4、B  5、D  二、填空题（每小题1分）
1. 数据的逻辑结构在计算机存储器内的表示，称为数据的（           ）。
2． 一个算法具有五个特性:（          ）、确定性、可行性、有零个或多个输入、有输出。
3．顺序存储结构是通过（          ）表示元素之间的关系的。
4. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作（           ）。
5．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是（         ）p的后继。
6．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为cdba，不可能得到的出栈序列为（               ）。
7．结点数为20的二叉树可能达期的最大高度为（                 ）。
8. 在有向图中，以顶点v为终点的边的数目称为v的（                ）。
参考答案：
1. 存储结构2．有穷性3．物理上相邻4. 存储密度5. 删除 6．cdab 7.20 8. 入度三、应用题（每小题8分）
1．链表与顺序表的应用比较。
2．证明：深度为k的二叉树中至多含有 2k-1 个结点，(k≥1)。
3．采用直接插入排序算法，将数组中n个元素（52   49  80  36  14  58  61  23  ）由小到大进行排序。
4．已知无向图G的邻接矩阵如图所示。
（1）画出该无向图G。（2）写出按广度优先搜索时的访问序列。参考答案：
1．（1）用顺序的方式存储线性表，内存的存储密度高，可以随机地存取结点；在顺序表中插入或删除一个数据元素，平均约需移动表中一半元素，效率比较低。
  （2） 顺序表要求占用连续的存储空间，存储分配只能预先进行。如果插入操作超出了预先分配的存储区间, 需要临时扩大是非常困难的。
  （3）采用链表存储结构时则可以克服上述不足,它适合于频繁插入和删除，并且存储空间大小不能预先确定的线性表。  
2．利用归纳法。
    i=1 时，只有一个根结点。显然 2i-1=20=1 是对的。
    设对所有的j(1≤j<i)，命题成立，即第j层上至多有 2j-1 个结点。  归纳证明：由归纳假设“第 i-1 层上至多有 2i-2 个结点”，又二叉树的每个结点的度至多为2，则第 i 层上
的最大结点数为第 i-1 层上最大结点数的2倍，
     即 2×2i-2=2i-1。
    由在二叉树的第 i 层上至多有 2i-1 个结点可推出，深度为k的二叉树上最大结点数为
        20+21+ ( ( ( ( ( ( +2k-1 = 2k-1
3．初始状态 52  49  80  36  14  58  61  23  
          i=1   [49  52]  80  36  14  58  61  23
          i=2   [49  52  80]  36  14  58  61  23
          i=3   [36  49  52  80]  14  58  61  23
          i=4   [14  36  49  52  80]  58  61  23
          i=5   [14  36  49  52  58  80]  61  23
          i=6   [14  36  49  52  58  61  80]  23
          i=7   [14  23  36  49  52  58   61  80]
    排序结果     [14  23  36  49   52  58  61  80]
4．（1）画出该无向图G。（略）
（2）广度优先搜索时的访问序列 V0 V1 V3 V2 V4。四、算法阅读题（本题10分）
下面的算法是实现图的邻接矩阵的广度优先搜索遍历。阅读算法，在横线处填入语句或注释。
    void BFSTraverse(MGraph G) {
   // 对以邻接矩阵存储表示的图G进行广度优先搜索遍历
    bool visited[G.vexnum];// 附设访问标识数组
    Queue Q;// 附设队列 Q
    for (v=0; v<G.vexnum; ++v)  visited[v] = （1）
         InitQueue(Q，G.vexnum);// （2）
    for ( v=0; v<G.vexnum; ++v )
      if ( （3）) {
        visited[v] = TRUE; VisitFunc(G.vexs[v]);// 访问图中第 v 个顶点
        （4）// 顶点v 入队列
        while (!QueueEmpty(Q)) {
           DeQueue(Q, u); // 队头元素出队并置为 u
           for ( w=0; w<G.vexnum; w++; )
               if ( G.arcs[u, w].adj && ! visited[w] ) {
                visited[w] = TRUE; VisitFunc(w); // （5）
                EnQueue(Q, w); // 当前访问的顶点 w 入队列 Q
                } // if
       } // while
      } // if
    DestroyQueue(Q);
   } // BFSTraverse
参考答案
（1）FALSE;
（2）初始化空队列
（3）!visited[v]
（4）EnQueue(Q, v);
（5）访问顶点w
五、算法设计题（本题10分）
设计算法InsertOrderList实现有序顺序表OrderList的插入算法，并指出其时间复杂度。
参考答案
     void InsertOrderList(OrderList &L, ElemType x){   
         // 在有序顺序表L中插入新的元素 e          for (i= L.length-1;i>=0&&x<L.elem; --i)              L.elem[i+1] = L.elem;   // 从表尾向前查找,元素右移              L.elem[i+1] = e; // 插入 e
              ++L.length;//表长增1
    } // InsertOrderList
    此算法的时间复杂度为O (L.length ) 。
东北大学免费答案