算法与数据结构A

《算法与数据结构A》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、□I（时间：120分-Til共100分）山东师范大学2012-2013学年第一学期期末考试试题得分阅卷人复核人课稈编号：081230209课程名称：算法与数据结构适用年级：2011学制：四适用专业：电子信息科学与技术试题类别:A（A/B）题号—•二三四总分阅卷人复核人得分綜

2、^——祜单项选择题：下面每题的选项中，只有一个是正确的，请将正确答案填在括号内。（本题共20小题，每小题2分，共40分）1•从逻辑上可以把数据结构分为（）两人类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构2.以下数据结构中，哪一个是线性结构（）？A.

3、广义表B.二叉树C.稀疏矩阵D.串3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4.链表不具有的特点是（）A.插入、删除不需耍移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。A.单链表B•单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表6.在双向链表指针P的结点前插入一个指针q的结点操作是（）。A.p->Llink=q;q->Rli

4、nk=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以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为（）oA.fedcbaB.bcafedC.dcefbaD.cabdef8.栈

5、和队列的共同点是（）oA.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点2.用链接方式存储的队列，在进行删除运算吋（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都耍修改D.头、尾指针可能都耍修改3.串的长度是指（）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数11.…棵完全二叉树上有1001个结点，其屮叶子结点的个数是（）A.250B.500C.254D.50112•由3个结点可以构造出多少种不同的二叉树？（）A.2B.3C.4D.513.已知一棵二叉树的前序遍历结果为ABCDEF

6、,中序遍历结果为CBAEDF,则后序遍历的结果为（A.CBEFDAB.FEDCBAC.）。CBEDFAD.不定14.有n个叶子的哈夫曼树的结点总数为（A.不确定B.2nC.15.要连通具有n个顶点的有向图，至少需要（A.n-1B.n16.一个有n个结点的图，最多有A.0B.117.关键路径是事件结点网络中（A.从源点到汇点的最长路径C.最长回路)o2n+lD・2n-l条边。C.n+1）个连通分量。C.n~l）oB•从源点到汇点的最短路径D.最短回路D.n）链接方式存储，元素有序顺序方式存储，元素有序B.D.)。A.图的遍历是从给定的源点出发每-向图B.遍历的基本算法有两

7、种：深度遍历和广度遍彷过程20.利用二叉链表存储树，则根结点的右指针是（A.指向最左孩子B.指向最右孩子-个顶点仅被访问-次C.空C.D.图的深度遍历不适用于有图的深度遍历是一个递归D.非空18.适用于折半查找的表的存储方式及元素排列要求为（A.链接方式存储，元素无序C.顺序方式存储，元素无序19.下列说法不正确的是（得分阅卷人复核人填空题：请将正确答案填在对应的横线上。（共5题，20分）1.在一个长度为n的顺序表中第i个元素（lUiUn）之前插入一个元素时，需向后移动个元素。（2分）2.用一维数组存放的一棵完全二叉树如下图所示:ABCDEFGHIJKL写出后序遍历该二

8、叉树时访问结点的顺序。（3分）3•循环队列用数组A[O..m-l]存放其元素值,已知其头尾指针分别是front和rear,则当前队列的元素个数是o（2分）4.现在拟建造一个连接11个城市的铁路网络，要求任何两个城市或者直接可达或者间接可达。用每个结点表示一个城市，两个结点之间边的权值表示两个城市之间直达铁路的造价，由此可得如下各城市之间的造价图。若要求设计的铁路网络总造价最小，贝I」这个一最小造价为o（4分）5.给出下图的合法的拓扑序列：o（3分）6.已知一个带权图的顶点集Vv={0,1,2,3,4,5,6};E={(0,1)19,(0,