山东师范大学第一学期期末考试试题
（时间：120分钟共100分）
课程编号：课程名称：算法与数据结构适用年级：学制: 4
适用专业：试题类别：A (A/B/C) 考试形式闭卷(开、闭卷)
一、
单项选择题：下面每题的选项中，只有一个是正确的，请将正确答案填在括号内。（本题共20小题，每小题2分，共40分）
1．从逻辑上可以把数据结构分为（ C ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构
2．以下数据结构中，哪一个是线性结构（D）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
4. 链表不具有的特点是（B）
A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
5．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。
A. 单链表
B.单循环链表
C. 带尾指针的单循环链表
D.带头结点的双循环链表6．在双向链表指针p的结点前插入一个指针q的结点操作是（ C ）。
A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
7.设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ D ）。
A．fedcba B. bcafed C. dcefba D. cabdef
8.栈和队列的共同点是（C ）。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
9.用链接方式存储的队列，在进行删除运算时（ D ）。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改
10. 广义表（a,(b,c),d,e）的表头为（ A ）。
A. a
B. a,(b,c)
C. (a,(b,c))
D. (a)
11．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ D ）
A． 250 B． 500 C．254 D．501
12.由3 个结点可以构造出多少种不同的二叉树？（ D ）
A．2 B．3 C．4 D．5
13．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（A ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
14. 有n个叶子的哈夫曼树的结点总数为（ D ）。
A．不确定 B．2n C．2n+1 D．2n-1
15．要连通具有n个顶点的有向图，至少需要（B ）条边。
A．n-l B．n C．n+l
16．一个有n个结点的图，最多有（ D ）个连通分量。
A．0 B．1 C．n-1 D．n
17．关键路径是事件结点网络中（A ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
18. 适用于折半查找的表的存储方式及元素排列要求为( D )
A．链接方式存储，元素无序 B．链接方式存储，元素有序
C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
19．下列说法不正确的是（C ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
20．利用二叉链表存储树，则根结点的右指针是（ C ）。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空
二、填空题：请将正确答案填在对应的横线上。（共5题，20分）
1．对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _4___个，单链表为____2___个。（2分）
2．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。（2分）
3．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是（rear-front+m）% m （2分）
4．用一维数组存放的一棵完全二叉树如下图所示：
写出后序遍历该二叉Array树时访问结点的顺序HIDJKEBLFGCA（3分）
5现在拟建造一个如下图连接11个城市的铁路网络，要求任何两个城市或者直接可达或者间接可达。用每个结点表示一个城市，两个结点之间边的权值表示两个城市之间直达铁路的
造价，由此可得如下各城市之间的造价图。若要求设计的铁路网络总造价最小，则这个最小