东大17年12月考试《数据结构Ⅰ》复习题题目
数据结构I笔试复习题（高起专）（2017-04-20）一、单选题（每小题2分）
1. 数据的不可分割的最小标识单位是
A. 数据项 B. 数据记录
C. 数据元素 D. 数据变量
2．下列程序段 for(i=1;i<=n;i++) A=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、A2、D3、A4、B5、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 49803614586123）由小到大进行排序。
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．初始状态 5249803614586123
i=1 803614586123
i=2 3614586123
i=3 14586123
i=4 586123
i=5 6123
i=6 23
i=7
排序结果
4．（1）画出该无向图G。（略）
（2）广度优先搜索时的访问序列 V0 V1 V3 V2 V4。四、算法阅读题（本题10分）
下面的算法是实现图的邻接矩阵的广度优先搜索遍历。阅读算法，在横线处填入语句或注释。
void BFSTraverse(MGraph G) {
// 对以邻接矩阵存储表示的图G进行广度优先搜索遍历
bool visited;// 附设访问标识数组
Queue Q;// 附设队列 Q
for (v=0; v<G.vexnum; ++v)visited = （1）
InitQueue(Q，G.vexnum);// （2）
for ( v=0; v<G.vexnum; ++v )
if ( （3）) {
visited = TRUE; VisitFunc(G.vexs);// 访问图中第 v 个顶点
（4）// 顶点v 入队列
while (!QueueEmpty(Q)) {
DeQueue(Q, u); // 队头元素出队并置为 u
for ( w=0; w<G.vexnum; w++; )
if ( G.arcs.adj && ! visited ) {
visited = TRUE; VisitFunc(w); // （5）
EnQueue(Q, w); // 当前访问的顶点 w 入队列 Q
} // if
} // while
} // if
DestroyQueue(Q);
} // BFSTraverse
参考答案
（1）FALSE;
（2）初始化空队列
（3）!visited
（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 = L.elem; // 从表尾向前查找,元素右移 L.elem = e; // 插入 e
++L.length;//表长增1
} // InsertOrderList
此算法的时间复杂度为O (L.length ) 。
东北大学免费答案
页:
[1]