考 生 信 息 栏 系 专业 级 班级 姓名 学号 装 订 线厦门理工学院试卷20 20 学年 第 学期课程名称数据结构与算法试卷卷别A B 专业 级 班级 考试方式闭卷 开卷 本试卷共 6 大题( 6页)，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。一、判断题：（本题共10小题，每题1分，共10分）1、 线性表的逻辑顺序与存储顺序总是一致的。（ ）2、 线性表的链式存储结构是一种随机存取的存储结构。（ ）3、 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。（ ）4、 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。（ ）5、 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序是不一样的。（ ）6、 在一个图中，所有顶点的度数之和等于所有边数的2倍。（ ）7、 数据元素是数据的最小单位。 （ ）8、 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）9、 从长度为n的顺序表中删除一个元素，所需要的时间都是O（n）。 （ ）10、 凡是空的单链表都是不含任何结点的。 （ ）二、填空题：（本题共10小题，每空1分，共15分）1、数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。2、计算机算法指的是 ，它必具备输入、输出和 等五个特性。3、若已知一个栈的入栈序列是1，2，3，4，。，n，其输出序列为p1,p2,p3,pn，若p1=n，则pi为 。4、在一棵二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则有n0= 。5、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6、在分块查找方法中，首先查找 ，然后再查找相应的 。7、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 。8、下面程序段的时间复杂度是 。i=s=0;while (sn)i+;s+=i;9、9、分析以下程序段的时间复杂度 。int i,j,x=0;for (i=1;in;i+) for (j=i+1;j=n;j+) x+;10、下面程序段的时间复杂度是 ；i=1；While (inext=NULLC、head-next=head D、head!=NULL9、栈和队列的共同点是（ ）。 A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点10、某算法的时间复杂度为O（n2），表明该算法的（）。 A、问题规模是n2 B、执行时间等于n2 C、执行时间与n2成正比 D、问题规模与n2成正比11、若线性表最常用的运算是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。 A、单链表 B、双链表 C、单循环链表 D、顺序表。 12、在一个单链表中，删除*p结点之后的一个结点的操作是（）。 A、p-next=p; B、p-next-next=p-next; C、p-next-next=p; D、p-next=p-next-next;13、循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（1） A、（rear-front+m）%m B、rear-front+1 C、rear-front-1 D、rear-front14、在一非空二叉树的中序遍历序列中，根结点的左边（ ）。A、只有右子树上的所有结点 B、只有右子树上的部分结点C、只有左子树上的部分结点 D、只有左子树上的所有结点15、对一个满二叉树，m个树叶，n个结点，深度为h，则（ ）。A、n=h+m B、h+m=2n C、n=2h-1 D、m=2h-116、表达式a*(b+c)-d的后缀表达式是（ ） A、a*b+c-d B、abc+*d- C、abc+*-d D、-*a+bcd17、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。A、1/2 B、1 C、2 D、418、对线性表进行二分查找时，要求线性表必须（ ）。A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序四、程序填空题：（本题共2小题，每题6分，共12分）1、下面程序的功能是计算100至1000之间有多少个数其各位数字之和是5，请填空。#include Main() int i,s,k,count=0;考 生 信 息 栏 系 专业 级 班级 姓名 学号 装 订 线for(i=100;i=1000;i+) s =0; k=i;while ( (1) ) s=s+k%10; k= (2) ;if(s!=5) (3) ;else count+;printf(“%d”,count);2、实现在顺序表L的第i(1in+1)个位置上，插入一个新结点x。请填空。# define ListSize 100typedef int DataType;typedef struc DataType dataListSize; int length; Sqlist;Void InsertList(Sqlist*L，DataType x，int i) int j; if(iL.length+1) printf(“Position error”); return ERRORif(L.length= ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1; （1） ;j-) （2） ; （3） ; L.length+; 五、简答分析题：（本题共6小题，共37分）1、当为解决某一问题而选择数据结构时，应从哪些方面考虑？ （6分）2、在线性表的如下链表存储结构中，若未知链表头节点的指针，仅已知p指针指向的节点，能否将它（p）从该结构中删除？为什么？ （5分）1）单链表2）双链表3）循环链表3、有五个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ （5分） 4、一棵有11个结点的二叉树的存储情况如下图所示，lefti和righti分别为i结点的左右孩子，根结点为序号3的结点。画出该二叉树；并给出先序、中序和后序遍历该树的结点序列，并画出该二叉树的中序线索二叉树和后序线索二叉树。 （8分） 1 2 3 4 5 6 7 8 9 10 11Lefti67852DataimfakblcrdgeRighti91041115、 输入一个正整数序列40，28，6，72，100，3，54，1，80，91，38，完成下列各题： (