超星尔雅学习通《数据结构与算法（西安邮电大学）》2023章节测试附答案.docx

1、超星尔雅学习通数据结构与算法（西安邮电大学）2023章节测试附答案1.7章节测试1、1.在数据结构中,从逻辑上可以把数据结构分成（）。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构正确答案：C2、2. 在数据结构中,从存储结构上可以将之分为（）。A、动态结构和静态结构B、顺序存储和非顺序存储C、紧凑结构和非紧凑结构D、线性结构和非线性结构正确答案：B3、3. 某算法的时间复杂度是O(n2),表明该算法的（）。A、执行时间与n2成正比B、问题规模是n2C、执行时间等于n2D、问题规模与n2成正比正确答案：A4、4. 在下面的程序段中,x=x+1;的语

2、句频度为（）。 for( i=1;i=n;i+) for( j=1;jnext=p-next;p-next=s;B、p-next=s;s-next=p-next;C、p-next=s;p-next=s-next;D、p-next=s-next;p-next=s;正确答案：A7、7. 对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是（）。A、headnext=NULL;B、head=NULL;C、headnext=he;D、head!=NULL;正确答案：A8、8. 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。正确答案：9、9. 顺序表适宜于顺序存取,而链表适

3、宜于随机存取。正确答案：X10、10. 线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。正确答案：3.9章节测试1、1. 栈和队列都是（）。A、限制存取点的非线性结构B、顺序存储的线性结构C、链式存储的非线性结构D、限制存取点的线性结构正确答案：D2、2. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后随即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是（）。A、3B、6C、4D、2正确答案：A3、3. 设计一个判别表达式中括号是否匹配出现的算法,采用（）的数据结构最佳。A、栈B

4、、顺序表C、队列D、单链表正确答案：A4、4. 表达式a*(b+c)-d的后缀表达式是（）。A、abc*+d-B、cb+a*d-C、abc+*d-D、abcd+*-正确答案：A5、5. 递归过程或函数调用时,处理参数及返回地址需要用一种（）的数据结构。A、栈B、队列C、多维数组D、线性表正确答案：A6、6. 最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是（）。A、rear=frontB、(rear+1)%n=frontC、rear+1=frontD、(rear-l)%n=front正确答案：A7、7. 用带头结点的单链表表示队长大于1的队列时,其队头指针指向队

5、头结点,其队尾指针指向队尾结点,则在进行删除操作时（）。A、仅修改队头指针B、仅修改队尾指针C、队头、队尾指针都要修改D、队头,队尾指针都可能要修改正确答案：A8、8. 对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（）。A、O(1),O(n)B、O(n),O(n)C、O(1),O(1)D、O(n),O(1)正确答案：A9、9. 两顺序栈共享空间,也存在空间溢出问题。正确答案：10、10.在对不带头结点的链队列作出队操作时,不会改变头指针的值。正确答案：X4.7章节测试1、1. 串是一种特殊的线性表,其特殊性体现

6、在（）A、数据元素是字符B、顺序存储C、链式存储D、逻辑结构是线性结构正确答案：A2、2. 若串S= software,其前缀真子串的数目是（）。A、7B、10C、9D、8正确答案：A3、3. 设有两个串p和q ,其中q是p的子串,求q在p中首次出现的位置的算法称为（）。A、串的模式匹配B、求子串C、串联接D、求串长正确答案：A4、4. 已知串 S=aaab,其next函数值为（）。A、0123B、1123C、1231D、1211正确答案：A5、5. 函数strcmp(stcabuc,stbabuc)的返回值是（）。A、0B、-1C、2D、1正确答案：D6、6. KMP算法的特点是在模式匹配时

7、指示主串的指针不会回溯。正确答案：7、7. 模式串 P=abaabcac的next函数值序列为01122312。正确答案：8、8. 串的存储结构有顺序串、堆串和块链串三种。正确答案：9、9. 子串的定位运算称为串的模式匹配。正确答案：10、10. 串student和Student相等。正确答案：X5.5章节测试1、1. 假设以行序为主序存储二维数组A=array1.100,1.100,设每个数组元素占2个存储单元,基地址为10,则LOC5,5=（）。A、818B、B 808C、1010D、1020正确答案：A2、2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素

8、)依次存放于一维数组B1.(n(n+1)/2中,则在B中确定aij(iA、j(j-1)/2+iB、i(i-1)/2+jC、i(i+1)/2+jD、j(j+1)/2+i正确答案：A3、3. 设广义表L=(a,b,c),则L的长度和深度分别为（）。A、1和2B、1和1C、1和3D、2和3正确答案：A4、4. 在稀疏矩阵的三元组顺序表中,每个三元组表示（）。A、矩阵中数据元素的行号、列号和数据值B、矩阵中非零元素的数据值C、矩阵中数据元素的行号和列号D、矩阵中非零元素的行号、列号和数据值正确答案：D5、5. 多维数组可以看作是一种特殊的线性表。正确答案：6、6. 一个稀疏矩阵Am,n采用三元组顺序表

9、形式表示,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am,n的转置运算。正确答案：X7、7.广义表B = (a, B) = (a, (a, (a, ) ) ) 的长度为无穷大。正确答案：8、8. 一个广义表可以为其它广义表所共享。正确答案：9、9. 稀疏矩阵中非零元素的个数远小于矩阵中元素的总数。正确答案：10、10. tail(head(a,b,c,d,e)=(a,b,c,d,e)。正确答案：X6.16章节测试1、1.树最适合用来表示的结构是（）。A、元素间具有分支及层次关系的结构B、元素间的有序结构C、元素间的无序结构D、元素间无联系的结构正确答案：A2、2.任

10、意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置（）。A、肯定发生变化B、肯定不发生变化C、有时发生变化D、无法确定正确答案：B3、3.判断线索二叉树中某结点P有左孩子的条件是（）。A、p-LTag=1B、p!=NULLC、p-lchild!=NULLD、p-LTag=0正确答案：D4、4.设森林T中有4棵树,其结点个数分别为n1,n2,n3,n4,那么当森林T转换成一棵二叉树后,则根结点的右子树上有（）个结点。A、n2+n3+n4B、n1-1C、n1D、n1+n2+n3正确答案：A5、5.以数据集4,5,6,7,10,12,18为叶结点权值所构造的哈夫曼树,其带权路径长度为（）。A

11、、155B、160C、165D、170正确答案：C6、6.以下属于前缀编码的是（）。A、0,1101,1110,1100,1111B、0,1,01,010,110C、00,01,10,11,101D、01,00,10,001,110,101正确答案：A7、7.一棵具有N个结点的二叉树采用二叉链表进行存储,其中空指针域有（）个。A、N+1B、NC、N-1D、不确定正确答案：A8、8.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有（）个叶子结点。A、10B、11C、12D、13正确答案：C9、9. 满二叉树一定完全是二叉树。正确答案：10、10.二叉树的遍历结

12、果不是唯一的。正确答案：7.15章节测试1、1.一个具有n个顶点的无向图最多有（）边。A、n(n-1)/2B、n(n-1)C、nD、2n正确答案：A2、2.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则占用的存储空间为（）。A、n+eB、eC、2eD、n+2e正确答案：D3、3.如果含有n个顶点的图形成一个环,则它有（）棵生成树。A、nB、n-1C、n+1D、不确定正确答案：A4、4.任何一个无向连通网的最小生成树（）。A、有一棵或多棵B、只有1棵C、一定有多棵D、可能不存在正确答案：A5、5.判断一个有向图是否存在回路,可以用（）。A、广度优先遍历算法B、求关键路径的方法C、Di

13、jkstra方法D、深度优先遍历算法正确答案：D6、6.关键路径是事件结点网络中（）。A、从源点到汇点的最长路径B、最长回路C、从源点到汇点的最短路径D、最短回路正确答案：A7、7.深度优先遍历类似于二叉树的（）。A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案：A8、8.广度优先遍历类似于二叉树的（）。A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案：D9、9.迪杰斯特拉算法求最短路径时,是按照路径长度递增的顺序求解的。正确答案：10、10.任何一个有向图都一定存在拓扑序列。正确答案：X8.9章节测试1、1. 具有12个关键字的有序表,折半查找的平均查找长度（）。A、10/1

14、2B、25C、25/12D、37/12正确答案：D2、2. 如果要求用线性表既能较快地查找,又能适应动态变化的要求,则可采用（）查找方法。A、分块查找B、顺序查找C、折半查找D、基于属性正确答案：A3、3. 已知一如下10个记录的表,其关键字序列为(2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55的记录,比较次数是（）。A、1次B、2次C、3次D、4次正确答案：B4、4. 如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,在等概率情况下查找成功时的平均查找长度ASL为（）。A、50B、48C、45D、47正确答案

15、：A5、5. 对包含n个元素的散列表进行查找,平均查找长度为（）。A、不直接依赖于nB、O(n2)C、O(log2n)D、O(n)正确答案：A6、6. 衡量查找算法效率的主要标准是（）。A、平均查找长度B、元素个数C、所需的存储量D、算法难易程度正确答案：A7、7. Hash表的平均查找长度与处理冲突的方法无关。正确答案：X8、8. 在二叉树排序树中插入一个新结点,总是插入到叶结点下面。正确答案：9、9. 哈希表是一种将关键字转换为存储地址的存储方法。正确答案：10、10.在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。正确答案：X9.11章节测试1

16、、1. 有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始小根堆为（）。A、-1,4,7,8,20,15,7,9B、-1,4,8,9,20,7,15,7C、-1,7,15,7,4,8,20,9D、A,B,C均不对。正确答案：A2、2. 一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（）。A、(40, 38, 46, 56, 79, 84)B、(38, 40, 46, 56, 79, 84)C、(40, 38, 46, 79, 56, 84)D、(40, 38, 46, 84, 56, 79)正

17、确答案：A3、3. 对下列整数序列使用基数排序,一趟分配收集之后的结果是（）。(179,208,93,306,55,859,984,9,271,33)A、271,93,33,984,55,306,208,179,859,9B、93,55,9,33,179,208,271,306,859,984C、208,306,9,33,55,859,179,271,984,93D、9,33,55,93,179,208,271,306,859,984正确答案：A4、4. 对序列15,9,7,8,20,-1,4进行排序,进行一趟后数据的排列变为9,15,7,8,20,-1,4,则采用的排序方法是（）。A、直接插

18、入排序B、选择排序C、堆排序D、希尔排序正确答案：A5、5. 评价排序算法好坏的标准主要是（）。A、执行时间和所需的辅助空间B、执行时间C、辅助空间D、算法本身的复杂度正确答案：A6、6. 对n个不同的排序码进行冒泡(递增)排序,在下列（）情况比较的次数最多。A、从大到小排列好的B、从小到大排列好的C、元素无序D、元素基本有序正确答案：A7、7. 简单选择排序和堆排序性能都受初始序列顺序的影响。正确答案：X8、8. 快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。正确答案：9、9. 堆排序所需的时间与待排序的记录个数无关。正确答案：X10、10. 采用希尔方法排序时,若关键字的排列杂乱无序,则效率最高。正确答案：11.6章节测试1、文件压缩产品最主要的功能是（）。A、压缩B、解压C、广告D、传送正确答案：B2、哈夫曼树最典型、最广泛的应用是在编码技术上。利用哈夫曼树，构造所得的哈弗曼编码是一种最优前缀编码。正确答案：3、在设计产品时，只需要办好程序员的角色就可以了。正确答案：X