东北师范大学23春“计算机科学与技术”《数据结构》补考试题库附答案

东北师范大学23春“计算机科学与技术”《数据结构》补考试题库附答案第I卷一.综合考核(共15题)1.最小生成树问题是构造带权连通图(网)的最小代价生成树。()A.错误B.正确2.栈和队列都是限制存取点的线性结构。()A.正确B.错误3.邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。()A.正确B.错误4.()的遍历仍需要栈的支持。A.前序线索二叉树B.中序线索二叉树C.后序线索二叉树D.前三种均需要5.在待排数据基本有序的情况下，快速排序效果最好。()A.错误B.正确6.顺序存储结构的主要缺点是不利于插入、删除操作。()A.错误B.正确7.求图的最小(代价)生成树问题，考虑的是下面的哪一种图?()A.有向图B.无向图C.带权的有向图D.带权的无向图8.直接选择排序算法对n个记录排序，在最好情况下的时间复杂度为O(n)。()A.错误B.正确9.在下列情况中，可称为二叉树的是()。A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树10.二叉树在线索化后，仍不能有效求解的问题是()。A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中序线索二叉树中求中序前驱11.用ISAM组织文件适合于()。A.磁盘B.磁带C.外存储器D.光盘12.下列描述中正确的是()。A.选择合适的数据结构是解决应用问题的关键步骤B.线性表的逻辑顺序与存储顺序总是一致的C.每种数据结构都具备查找、插入和删除三种基本运算D.数据结构实质上包括逻辑结构和存储结构两方面的内容13.数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。()A.正确B.错误14.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是()。A.r=r->nextB.r=f->nextC.f=r->nextD.f=f->next15.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行()。A.s->next=p->next;p->next=sB.q->next=s;s->next=pC.p->next=s;s->next=qD.p->next=s->next;s->next=p第II卷一.综合考核(共15题)1.若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。()A.正确B.错误2.经过下列栈的操作后，GetTop(ST)的值是()。InitStack(ST);push(ST，‘a’);push(ST，‘b’);pop(ST，x);A.aB.bC.1D.23.AOV网的含义是以顶点表示活动的网。()A.正确B.错误4.二叉树中除叶结点外，任一结点X，其左子树根结点的值小于该结点X的值;其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。()A.正确B.错误5.(101，88，46，70，34，39，45，58，66，10)是堆。()A.错误B.正确6.设s1=“abc”，则strlen(s1)=()。A.3B.2C.1D.07.归并排序的辅助存储空间代价为O(1)。()A.正确B.错误8.下列说法不正确的是()。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度优先遍历和广度优先遍历C.图的深度优先遍历不适用于有向图D.图的深度优先遍历是一个递归过程9.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。()A.错误B.正确10.递归过程的实现需用到()。A.线性表B.链表C.栈D.队列11.若要求尽可能快地对序列进行稳定的排序，则应选()。A.快速排序B.归并排序C.起泡排序D.希尔排序12.一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是()。A.不确定B.2C.1D.013.在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是()。A.直接插入排序B.快速排序C.直接选择排序D.归并排序14.下面关于串的叙述中，哪一个是不正确的?()A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储15.链表中的表头指针与表头结点起到相同的作用。()A.正确B.错误第III卷一.综合考核(共15题)1.程序一定是算法。()A.正确B.错误2.将一个A[1..100，1..100]的三对角矩阵，按行优先次序存入一维数组B[1..298]中，A中元素A[66，65]在数组B中的位置K为()。A.199B.197C.195D.1933.在下面的叙述中，正确的是()。A.树的先根遍历序列与其对应的二叉树的前序遍历序列相同B.树的先根遍历序列与其对应的二叉树的中序遍历序列相同C.树的先根遍历序列与其对应的二叉树的后序遍历序列相同D.树的后根遍历序列与其对应的二叉树的后序遍历序列相同4.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。()A.错误B.正确5.在一个图中，所有顶点的度数之和等于图的边数的几倍()。A.1/2B.1C.2D.46.设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为()。A.h+1B.2h-1C.2hD.2h+17.快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。()A.错误B.正确8.广义表(a，b，c，d)的表头是()。A.(b，c，d)B.(a，b，c，d)C.aD.(a)9.串是一种特殊的线性表，其特殊性体现在()。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储10.下面哪些方法可以判断出一个有向图是否有环(回路)?()A.求最短路径B.求关键路径C.拓扑排序D.广(宽)度优先遍历11.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是()。A.O(log2n)B.O(1)C.O(n)D.O(nlog2n)12.有n个顶点的有向图的边数最多为()。A.nB.n(n-1)C.n(n-1)/2D.2n13.文件系统采用索引结构是为了节省存储空间。()A.错误B.正确14.对于3个结点a、b、c，可构成不同的二叉树的棵数为()。A.32B.30C.28D.2415.有n个顶点的无向图的边数最多为()。A.nB.n(n-1)C.n(n-1)/2D.2n第I卷参考答案一.综合考核1.参考答案：B2.参考答案：A3.参考答案：B4.参考答案：C5.参考答案：A6.参考答案：B7.参考答案：D8.参考答案：A9.参考答案：B10.参考答案：A11.参考答案：A12.参考答案：A13.参考答案：A14.参考答案：D15.参考答案：B第II卷参考答案一.综合考核1.参考答案：A2.参考答案：A3.参考答案：A4.参考答案：B5.参考答案：B6.参考答案：A7.参考答案：B8.参考答案：C9.参考答案：B10.参考答案：C11.参考答案：B12.参考答案：C13.参考答案：C14.