西华大学数据结构综合期未试题

年级专业： 教学班号： 学号： 姓名：装 订 线 课程名称： 数 据 结 构 考试时间： 110 分钟 课程代码： 试卷总分： 100 分一、选择题（在每个小题四个备选答案中选出一个正确答案）（本大题共20小题，每小题1.5分，总计30分）1、数据的基本单位是（ B ）。A.数组元素 B.数据元素 C.数据项 D.数据对象1、性质相同的数据元素的集合是（ D ）。A.数组元素 B.数据元素 C.数据项 D.数据对象2、下列选项中哪个不属于算法重要特性？（ D ）A.有穷性和确定性 B.可行性 C.输入和输出 D.可视化和模块化2、算法的效率一般是指（ A ）。 A.算法的执行时间 B.算法所需要存储空间 C.算法的可读性 D.算法处理的数据量3、如一个线性表中的数据元素是由若干个数据项组成，人们通常把这样的数据元素又称为（ A）。 A.记录 B.字段 C.属性 D.数据项集合3、在线性表的抽象数据类型定义中，下列哪个是其数据关系的描述？其中ai指数据元素，D指数据对象。 （ B ）A. R= |ai,anD,i=1,2,n B. R= |ai,anD,i=1,2,n-1 C. R= |ai,anD,i=1,2,n D. R= |ai,anD,i=2,3,n-14、与数组相比，用链表表示线性表的主要优点是 ( C )。A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同4、与链表相比，采用数组表示性线表的主要优点是（ A ）。A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序不一定相同5、下列关于栈说法正确的是（ A ）。A. 栈是限定在表尾部进行插入和删除操作的线性表 B . 一般使用链作栈存储结构，不可使用数组 C. 栈是先进先出的一种结构 D. 栈有栈顶和栈底，可从栈顶或栈底开始取元素5、下列关于栈的说法正确的是（ C） A.在顺序栈中，栈底指针是可随意移动的 B . 空栈时，栈顶和栈底指针只相差1 . C。非空栈时，栈顶指针始终是指向栈顶元素的下一个位置上 D. 删除栈顶元素时，栈顶指针加16、如果入栈的序列为（A,B,C,D），则不可能的出栈序列为（ ）。A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 7、下列哪种情况不使用队列作存储结构（ C ）。 A.操作系统中的作业管理 B . 打印时的多个任务输出 C. 数制转换 D. 模拟银行业务窗口客户等待状态7、在用数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。A. front=maxSize B. rear=maxSizeC. (rear+1)%maxSize=front D. rear=front8、下列关于串的说法正确的是（ B ）。A. 串是由n个字符组成的有限序列（n0） B. 串有任意个必须连续的字符组成的子序列称为原串的子串C. 截取子串的操作通常称为模式匹配 D. 串只能采用定长存储8、下列关于串的说法正确的是（ D ）。A. 串一般记为s=a1a2an（n0） B. 空串和空格串是同一个概念C. 串的堆分配存储表示中，存储单元是在程序执行之前分配好的 D. 模式串中的每个字符必须与依次和主串中的一个连续字符序列相等才叫模式匹配成功9、若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) 。A. BCDAGFE B. CDBFGEA C. CDBAGFE D. CDBGFEA 9、若度为m的广义哈夫曼树中，总叶子个数为n，其非叶子结点的个数有（ A ）个。 A. (n-1)/(m-1) B. (n-1)/(m) C. (n)/(m-1) D. 无法确定 10、下列存储形式中，( ) 不是树的存储形式。A. 广义表表示法 B. 顺序存储表示法C. 双亲表示法 D. 左子女右兄弟表示法10、向一个有51个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。 A 8 B。 25.5 C。 25 D。 5111、n个顶点的无向完全图有（ ）条边。 A n*(n-1)/2 B. n C. n+1 D. 2N11、要连通n个顶点至少需要（ ）条边 A、nB、n+1C、n-1D、n/2 12、下列有关图的概念中，不正确的是（ ）。 A、与图的边或孤相关的数字叫做权B、任何图中与某顶点相连的边或孤叫出度C、在图中，起点与终点相同的路径称为回路D、连通分量是指无向图中的极大连通子图12、下列有关图的概念中，不正确的是（ ）。A、在图中常用（w,v）表示一条边B、一个连通图的生成树是一个极小连通子图C、一般情况下，图是可以用数据元素在存储区中的物理位置来表示元素之间的关系的D、在无向图中，第i个链表中的结点数就是顶点vi的度。 13、下列什么情况下适合采用顺序查找法（ C ）。A、数据元素事前基本有序B、数据元素呈非递减顺序C、数据元素无序D、数据元素分块时，块间有序，块内无序13、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）A、插入排序B、选择排序C、快速排序D、归并排序14、下面程序段的时间复杂性为( C )。 y=0;while(n=(y+1)*(y+1) y+; A、O(n) B、O(n2) C、 O(sqrt(n) D、 O(1)14、下面程序段的时间复杂性为( )。 m=0for (I=1;I=n; I+)for(j=1;j=I;j+) m+;A、O(n) B、O(n2) C、 O(sqrt(n) D、 O(1)15、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( C )A、二叉排序树 B、哈夫曼树 C、堆 D、AVL树15、如果一个二叉树满足堆的条件且任意一个非叶子结点的关键字天于其孩子的关键字，则此时的n个元素的序列满足的条件是（ B ）。A、ki=k2i 且 ki=k2i 且 ki=k2i+1 C、ki+1=k2i 且 ki+1=k2i+1 D、ki=k2i+1 且 ki+1lchild=NULLB、t-ltag= =1C、t-ltag= =1且t-lchild= =NULLD、以上答案都不对17、在线索化二叉树中，节点t没有右子树的充要条件是（ B）A、t-rchild=NULLB、t-rtag= =1C、t-rtag= =1且t-rchild= =NULLD、以上答案都不对18、采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构18、就平均查找速度而言，下列几种查找速度从慢至快的关系是（ ）。A.顺序 折半 哈希 分块 B.顺序 分块 折半 哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半19、将递归算法转换为非递归算法时，一般要设置一个（ ）辅助结构。A、堆栈或队列B、数组C、堆栈D、队列19、在广度优先遍历树时，需要设置一个（ C ）辅助结构。A、数组B、堆栈或队列C、队列D、堆栈20、由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为( )。 A. 60 B. 66 C. 67 D. 5020、有一文件的关键字序列为：9 5 7 2 3 8 4 6 11 43，如采用二路归并排序算法，则第二趟归并结果为:（ ） A. 2 5 7 9 3 4 6 8 11 43 B. 2 5 7 9 3 4 6 8 11 43 C. 2 5 7 9 3 4 6 8 11 43 D. 9 5 7 2 3 8 4 6 11 43二、填空题（本大题共10题，每空2分，总计20分）1、数据元素相互之间的关系存在四种基本结构，它们是集合、线性结构、树结构、 图 。1、 数据元素在计算机内的两种不同的存储结构是：顺序存储结构和 链式 。2、线性表中的一个结点包括：数据域和 指针域 。2、若二叉树有m个叶子结点，则度为2的结点有 m-1 个 .3、栈和队列都是限制存取点的 线性 结构。3、在用栈实现表达式求值的过程中，使用了两个栈，一个用来寄存操作数或运算结果，另一个用来寄存 运算符 .4、树中某结点的子树的数目称为： 叶子结点 。4、树内各结点的度的最大值称为：树的度 。5、深度为k的二叉树最大结点数为: 2k-1 。5、如果一棵二叉树终端结点数为n0, 度为2的结点数为n2，则n0和n2满足的数学关系式为： N0=n2+1 。6、中缀表达式a*b-c对应的前缀表达式为 -*abc .6、中缀表达式a*b-c对应的后缀表达式为 ab*c- .7、对二叉树以某种次序遍历使其变为线索二叉树的过程叫 线索化 .7、用一维数组存放一颗完全二叉树：ABCDEFGHIJKL，则后序遍历该二叉树的结点序列为 。 8、若一棵二叉树的任意非叶子结点值大于其左子树上所有结点值，同时小于其右子树上所有结点值，则此二叉树是一棵 排序二叉树 树。8、若一棵二叉树的任意结点的左子树和右子树的深度之差不超过1，则此二叉树是 平衡二叉 树。9、设图G有n个顶点和e条边，则进行深度优先的时间复杂性为_O(n+e) _。9、设图G有5个顶点，若采用邻接矩阵存储结构，则此矩阵有 25 个元素。10、如果查找表内的各子表的最大关键字呈有序状态，则最适合的查找算法是 分块 。10、能使用折半查找方法的线性表的前提条件是 有序 。 三、判断题（本大题共10题，每小题1分，总计10分1. 每一种数据的逻辑结构和物理结构总是一致的.（N ） 1. 顺序结构存储方式只能用于存储线性结构。（N ）2. 消除递归不一定要使用栈. (Y) 2. 中序遍历二叉排序树就可以得到排好序的结点序列。（Y） 3. 图的深度优先遍历类似于树的中序遍历。（N）3 图的广度优先遍历类似于树的层次遍历（ Y ）4栈通常有两种存储表示方法，即顺序栈和链式栈（Y）4二叉树的左右子树不能随意颠倒（Y ）5在树中，其双亲在同一层的结点相互称为堂兄弟结点（Y ）5二叉树的第I层上至少有2I-1个结点（N ）6完全二叉树中，叶子结点只可能出现在层次最大的最后一层上。（ N）6具有n个结点的完全二叉树的深度为log2n+1 。（ Y ）7二叉树的线索化的目的是尽可能方便地直接访问结点的前驱和后继。（Y ）7任何一棵和树对应的二叉树的右子树不一定为空（N ）8图的邻接矩阵中，第I列上的数字1的个数表示第I个顶点的出度（N ）8图的邻接矩阵中，第I行上的数字1的个数表示第I个顶点的入度（ N ）9赫夫曼树又叫最优二叉树（Y ）9树的双亲表示法中，从任意一结点出发，可方便地找到根结点，但查找孩子结点则要遍历整个树（Y ）。10堆排序涉及到的两个核心问题，一是如何把一无序序列建立一个堆，二是在输出堆顶后再调整成一个新堆。（Y ）10由于排序过程中涉及到的存储器不同，可将排序方法分为内部排序和外部排序两大类（ Y ）。四、算法及应用（本大题共3小题，共40分）求线性表的长度：请分别编写一个计算单链表的长度的递归和非递归算法1 已知两个有序(非递减)的带头指针的单链表La和Lb,其结点结构相同,数据域为整形data。请实现把La和Lb合并成Lc。（本小题共15分） 具体要求：（1）写出本题所用单链表的存储结构；（3分） （2）合并过程中，不增加额外的存储空间（提示：修改La和Lb中结点指针，使其最终成为一个链）；（3）写出合并的详细算法,Lc中要求无重复值。（2，3共12分） (1) Typedef struct Lnode Int data; Struct Lnode *next;Lnode, *LinkList; /3分(2)void UniList(LinkList &La, LinkList &Lb, LinkList &Lc) / UniList结构正确2分 pa=La-next; pb=Lb-next; Lc=pc=La; /准备工作2分 While (pa & pb If (pa-datadata) Pc-next= pa; pc=pa; pa=pa-next ; /2分 Else if (pa-data=pb-data) Pc-next= pa; pc=pa; pa=pa-next ; pb=pb-next ; /2分else Pc-next= pb; pc=pb; pb=pb-next ; /2分pc-next =pa? Pa:pb; /2分 free(Lb) 1 求无头结点单链表的长度。具体要求： （本小题共15分）（1） 写出本题所用单链表的存储结构；（3分）（2） 写出计算单链表的长度的递归算法（6分）（3） 写出计算单链表的长度的非递归算法（6分）（1）Typedef struct Lnode ElemType data; Struct Lnode *next;Lnode, *LinkList; /3分（2）递归算法（/6分）static Listlen1(p) if (p=NULL) len=0; /1分 else len=1+Listlen1(p-next); /3分 retrun(len); /整体结构正确2分 （3）非递归算法（/6分） static Listlen1(p) int len=0; /1 分 while (p!=NULL ) len+; p=p-next ; /3分 retrun(len); /2分2请写出先序遍历二叉树的非递归算法(提示：利用栈)。 (本小题共15 分)void PreBT (BiTree T) InitStack(S); /2分p=T; WHILE(p!=NULL | !stackEmpty(s) /循环结构3分if (p!=NULL) visit(p-data); /2分 push(s,p); p=p-lchild; / 4分 else pop(s,p); /出栈 /2分 p=p-rchild; / 2分 2请写出按层次顺序遍历二叉树的算法（提示：利用队列）。(本小题共15 分)void layorder (tree T) initqueue (q) /2分 if(T!=NULL) enqueue (q, T); /2分 while (not emptyqueue (q) ) /循环整体结构5分 outqueue (q, p) ; visit(p-data); /出队及访问2分 if (p-lchild!=NULL) enqueue (q, p-lchild); /2分 if (p-rchild!=NULL) enque