山东师范大学数据结构期末考试试题

1、山东师范大学第一学期期末考试试题（时间：120分钟 共100分）课程编号:_ 课程名称： 算法与数据结构 适用年级: _ 学制:4适用专业:试题类别：JL （A/B/C）考试形式 闭卷（开、闭卷）、单项选择题：下面每题的选项中，只有一个是正确的，请将正确答案填在括号内。（本题共20小题，每小题2分，共40分）1 从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D初等结构、构造型结构2 以下数据结构中，哪一个是线性结构（D ）?A广义表 B. 二叉树 C.稀疏矩阵D.串3. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插

2、入和删除运算，则 利用（A ）存储方式最节省时间。A顺序表 B.双链表C.带头结点的双循环链表D .单循环链表4. 链表不具有的特点是（B ）A插入、删除不需要移动元素B .可随机访问任一元素C.不必事先估计存储空间D .所需空间与线性长度成正比5. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（D）最节省时间。A. 单链表 B.单循环链表 C.带尾指针的单循环链表D.带头结点的双循环链表6. 在双向链表指针 P的结点前插入一个指针q的结点操作是（C ）。A. p->Lli nk=q;q->Rli nk=p;p->Lli nk->Rli nk=q;q-&g

3、t;Lli nk=q;B. p->Lli nk=q;p->Lli nk->Rli nk=q;q->Rli nk=p;q->Lli nk=p->Lli nk;C. q->Rli nk=p;q->Lli nk=p->Lli nk;p->Lli nk->Rli nk=q;p->Lli nk=q;D. q->Lli nk=p->Lli nk;q->Rli nk=q;p->Lli nk=q;p->Lli nk=q;7. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为(

4、D )oA.fedcbaB. bcafedC. dcefbaD. Cabdef8.栈和队列的共同点是（C )oA.都是先进先出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 . 50112. 由3个

5、结点可以构造出多少种不同的二叉树？ （ D ）A. 2 B . 3 C . 4 D . 513. 已知一棵二叉树的前序遍历结果为ABCDEF中序遍历结果为 CBAEDF则后序遍历的结果 为（A ） oA. CBEFDAB . 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+l16. 一个有n个结点的图，最多有（ D ）个连通分量。A. 0B. 1C. n-1D17 .关键路径是事件结点网络中（A.从

6、源点到汇点的最长路径C.最长回路DA ）。B .从源点到汇点的最短路径.最短回路18.适用于折半查找的表的存储方式及元素排列要求为（D ）A.链接方式存储，元素无序B .链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序19 .下列说法不正确的是（C ）。A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次C .图的深度遍历不适用于有 向图B. 遍历的基本算法有两种：深度遍历和广度遍历D .图的深度遍历是一个递归 过程20 .利用二叉链表存储树，则根结点的右指针是（ C ）。A.指向最左孩子B .指向最右孩子C .空 D .非空二、 填空题：请将正确答案填在对应的横线

7、上。（共5题，20分）1 .对于双向链表，在两个结点之间插入一个新结点需修改的指针共_4_个，单链表为2个。（2 分）2. 在一个长度为n的顺序表中第i个元素（1<=i<=n ）之前插入一个元素时，需向后移动 _n-i+1_ 个元素。（2分）front 禾口 rear ,贝U3. 循环队列用数组 A0.m-1存放其元素值，已知其头尾指针分别是当前队列的元素个数是（rear-front+m ） % m （2分）4. 用一维数组存放的一棵完全二叉树如下图所示：ABCDEFGHIJKLHlDJKEBLFGC（3 分）写出后序遍历该二叉 树时访问结点的顺序5现在拟建造一个如下图连接 11个

8、城市的铁路网络，要求任何两个城市或者直接可达或者 间接可达。用每个结点表示一个城市，两个结点之间边的权值表示两个城市之间直达铁路的 造价，由此可得如下各城市之间的造价图。若要求设计的铁路网络总造价最小，则这个最小60閒70造价为_ _。（4分）6. 若以4 , 5, 6, 7, 8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69 （4 分）7. 给出下图的合法的拓扑序列： 。（ 3分）三、应用题（共2题，20分）1. 一棵二叉树的结点数据采用顺序存储结构存储于数组中，如下:123456789101121314151617181920EAFDGCJHIB1）画出该树二叉树的表示形式（3分）

9、2）写出该树的前序周游的结果（3分）3）写出结点C的父结点，左右孩子（3分）4）画出此树还原成森林的图（3分）2.下面的邻接表表示一个给定的无向图（1） 给出从顶点Vl开始,对图G用广度优先搜索法进行遍历时的顶点序列；（4 分）（2）以顶点Vl为根，画出G的深度优先生成树（4分答案：（1） MVMMV5V6（ 2） VIVMVV5V6四、编程题（共 2题， 20分）1. 设有一带头结点的单链表,编程将链表颠倒过来 .要求不用另外的数组或结点完成.（ 10分）typedef struct node int data ;/假定结点数据域为整型。struct node *next ；node ,*L

10、inkedList ;LinkedList creat （ ） LinkedList head， pint x ;head= （ LinkedList ） malloc （sizeof （node）; head->next=null ; /* 设置头结点 */ scanf （“ %d”，&x）;while （x!=9999 ） /* 约定输入 9999 时退出本函数 */p=（LinkedList ）malloc （sizeof （ node）;p->data=x ;p->next=head->next ; /* 将新结点链入链表 */ head->next=p ;scanf（“ %d”， &x）;return （ head）; /结束 creat 函数。LinkedList invert1 （ LinkedList head ）/* 逆置单链表 */LinkedList p=head->next; /*p为工作指针 */head->next=null ;while （p!=null ）r=p->next ;/* 暂存 p 的后继 */p->next=head->next ;head->next=p ;p=r ;return （ head）;/*