1 / 6东 北 大 学 继 续 教 育 学 院数据结构 I 复习题 一、单选题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-14．在一个单链表中，已知 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. 数据的逻辑结构在计算机存储器内的表示，称为数据的（ ）。课程名称: 数据结构 I 2 / 62．一个算法具有五个特性:（ ）、确定性、可行性、有零个或多个输入、有输出。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. 入度三、应用题1．链表与顺序表的应用比较。2．证明：深度为 k 的二叉树中至多含有 2k-1 个结点，(k≥1)。3．采用直接插入排序算法，将数组中 n 个元素（52 49 80 36 14 58 61 23 ）由小到大进行排序。4．已知无向图 G 的邻接矩阵如图所示。（1）画出该无向图 G。（2）写出按广度优先搜索时的访问序列。课程名称: 数据结构 I 3 / 6参考答案：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]课程名称: 数据结构 I 4 / 6 排序结果 [14 23 36 49 52 58 61 80]4．（1）画出该无向图 G。（略）（2）广度优先搜索时的访问序列 V0 V1 V3 V2 V4。四、算法阅读题下面的算法是实现图的邻接矩阵的广度优先搜索遍历。阅读算法，在横线处填入语句或注释。 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++; )课程名称: 数据结构 I 5 / 6 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五、算法设计题设计算法 InsertOrderList 实现有序顺序表 OrderList 的插入算法，并指出其时间复杂度。参考答案 void InsertOrderList(OrderList &L, ElemType x){ // 在有序顺序表 L 中插入新的元素 e for (i= L.length-1;i>=0&&x<L.elem[i]; --i) L.elem[i+1] = L.elem[i]; // 从表尾向前查找,元素右移 L.elem[i+1] = e; // 插入 e ++L.length;//表长增 1 } // InsertOrderList 课程名称: 数据结构 I 6 / 6 此算法的时间复杂度为 O (L.length ) 。课程名称: 数据结构 I