[东北大学]19年11月考试《数据结构I》考核作业（资料）
东 北 大 学 继 续 教 育 学 院数据结构I_ 试 卷（作业考核 线下） A 卷（共 7 页）
总分 题号 一 二 三 四 五 六 七 八 九 十
得分
注：请您单面打印，使用黑色或蓝色笔，手写完成作业。杜绝打印，抄袭作业。
一、单选题（每小题2分，共10小题，20分）
[] 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. 第一个不等字符的大小
[] 6．栈的两种常用存储结构分别为
A．顺序存储结构和链式存储结构 B．顺序存储结构和散列存储结构
C．链式存储结构和索引存储结构 D．链式存储结构和散列存储结构
[] 7. 下列陈述中正确的是
A.二叉树是度为2的有序树
B.二叉树中结点只有一个孩子时无左右之分
C.二叉树中必有度为2的结点
D.二叉树中最多只有两棵子树，并且有左右之分
[] 8．设无向图的顶点个数为n，则该图最多的边数目是
A．n-1 B．n(n-1)/2
C． n(n+1)/2 D．0
[] 9. 采用ISAM或VSAM组织的文件是
A. 索引非顺序文件 B. 顺序文件
C. 索引顺序文件 D. 散列文件
[] 10．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为
A．插入排序 B．归并排序
C．冒泡排序 D．堆排序
二、填空题（每小题1分，共10小题，10分）
11．数据的逻辑结构在计算机存储器内的表示，称为数据的（ ）。
12． 一个算法具有五个特性:（ ）、确定性、可行性、有零个或多个输入、有输出。
13．顺序存储结构是通过（ ）表示元素之间的关系的。
14. 在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作（ ）。
15．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是（ ）p的后继。
16．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为cdba，不可能得到的出栈序列为（ ）。
17．结点数为20的二叉树可能达期的最大高度为（ ）。
18．在有向图中，以顶点v为终点的边的数目称为v的（ ）。
19．索引顺序查找适宜对（ ）的顺序表进行查找。
20．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，则应该选用（ ）排序方法。
三、应用题（每小题8分，共5小题，40分）
21．链表与顺序表的应用比较。
22．证明：深度为k的二叉树中至多含有 2k-1 个结点，(k≥1)。
23．采用简单选择排序算法，将数组中n个元素（52、49、80、36、14、58、61、23）由小到大进行排序。
24．已知无向图G的邻接矩阵如图所示。
（1）画出该无向图G。（2）写出按广度优先搜索时的访问序列。
V1V2V3 V4V5
V1 0 1 0 1 0
V2 1 0 1 0 1
V3 0 1 0 0 0
V4 1 0 0 0 0
V5 0 1 0 0 0
25．已知如图所示，用普里姆（prim）算法从顶点A开始求最小生成树。试按照最小生成树的生成过程，分步给出加入顶点和边的过程。
四、算法阅读题（本题10分）
26．下面的算法是实现图的邻接矩阵的广度优先搜索遍历。阅读算法，在横线处填入语句或注释。
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）
（2）
（3）
（4）
（5）
五、算法阅读题（本题10分）
27．已知二叉树的存储结构为二叉链表，阅读算法：
BiTree Change_T(BiTree T1) {
if(!T1) T2=NULL;
else {
T2=(BiTNode *)malloc(sizeof(BiTNode));
T2->data= T1->data;
T2->rchild= Change_T (T1->lchild);
T2->lchild= Change_T (T1->rchild);
}// else
return T2;
}// Change_T
（1）指出功能。
（2）指出T2->lchild=Change_T (T1->rchild)语句的作用。
（1）功能:
（2）作用:
六、算法设计题（本题10分）
28．设计算法InsertLinkList实现有序顺序表OrderList的插入算法，并指出其时间复杂度。（LinkList为已知的单链表类型）。
页:
[1]