《数据结构与算法》章节测试题与答案

《数据结构与算法》章节测试题与答案

‎《数据结构与算法》章节测试题与答案 课程简介：数据结构是一门面向设计，且处于计算机学科核心地位的技术基础和主干必修课，也是算法分析与……‎ 课程简介：数据结构是一门面向设计，且处于计算机学科核心地位的技术基础和主干必修课，也是算法分析与设计、操作系统、编译技术、计算机图形与图像处理等专业课程的先修课程。‎ 引论 ‎1.【单选题】1.在数据结构中,从逻辑上可以把数据结构分成( )。‎ A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 答案：C ‎2.【单选题】2. 在数据结构中,从存储结构上可以将之分为( )。‎ A、动态结构和静态结构 B、顺序存储和非顺序存储 C、紧凑结构和非紧凑结构 D、线性结构和非线性结构 答案：B ‎3.【单选题】3. 某算法的时间复杂度是O(n^2),表明该算法的( )。‎ A、执行时间与n^2成正比 B、问题规模是n^2‎ C、执行时间等于n^2‎ D、问题规模与n^2成正比 答案：A ‎4.【单选题】4. 在下面的程序段中,x=x+1;的语句频度为( )。 for( i=1;i<=n;i++) for( j=1;j<=n;j++) x=x+1;‎ A、O(2n)‎ B、O(n)‎ C、O(n^2)‎ D、O(log2n)‎ 答案：C ‎5.【单选题】5. 以下数据结构中,( )是非线性数据结构。‎ A、树 B、字符串 C、队 D、栈 答案：A ‎6.【单选题】6. 顺序存储,存储单元的地址( )。‎ A、一定连续 B、一定不连续 C、不一定连续 D、部分连续,部分不连续 答案：A ‎7.【单选题】7.评价一个算法性能好坏的重要标准是( )。‎ A、算法的正确性 B、算法易于调试 C、算法的时间和空间复杂度 D、算法易于理解 答案：C ‎8.【单选题】8. 若需要利用形式参数直接访问修改实参值,则应将形参说明为( )参数。‎ A、值参数 B、实地址 C、指针 D、地址参数 答案：C ‎9.【判断题】9. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。‎ 答案：×‎ ‎10.【判断题】10. 数据结构中评价算法的两个重要指标是算法 的时间复杂度和空间复杂度。‎ 答案：√‎ 线性表 ‎1.【单选题】1. 下述哪一条是顺序存储结构的优点()。‎ A、可方便地用于各种逻辑结构的存储表示 B、插入运算方便 C、删除运算方便 D、存储密度大 答案：D ‎2.【单选题】2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用()存储方式最节省时间。‎ A、顺序表 B、双链表 C、带头结点的双循环链表 D、单循环链表 答案：A ‎3.【单选题】3. 设某顺序表中第一个元素的地址是se(下标从1开始),每个结点占m个单元,则第i个结点的地址为()。‎ A、se+(i-1)×m B、se+(i+1)×m C、se+i×m D、se-i×m 答案：A ‎4.【单选题】4. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。‎ A、单链表 B、仅有尾指针的单循环链表 C、仅有头指针的单循环链表 D、双链表 答案：B ‎5.【单选题】5. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为()。‎ A、O(n)‎ B、O(0)‎ C、O(1)‎ D、O(n^2)‎ 答案：A ‎6.【单选题】6. 在单链表指针为p的结点之后插入指针为s的结点,正确的操作是()。‎ A、s->next=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;‎ 答案：A ‎7.【单选题】7. 对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是()。‎ A、head→next==NULL;‎ B、head==NULL;‎ C、head→next==he;‎ D、head!=NULL;‎ 答案：A ‎8.【判断题】8. 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。‎ 答案：√‎ ‎9.【判断题】9. 顺序表适宜于顺序存取,而链表适宜于随机存取。‎ 答案：×‎ ‎10.【判断题】10. 线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定相邻。‎ 答案：√‎ 栈和队列 ‎1.【单选题】1. 栈和队列都是( )。‎ A、限制存取点的非线性结构 B、顺序存储的线性结构 C、链式存储的非线性结构 D、限制存取点的线性结构 答案：D ‎2.【单选题】2. 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后随即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是( )。‎ A、3‎ B、6‎ C、4‎ D、2‎ 答案：A ‎3.【单选题】3. 设计一个判别表达式中括号是否匹配出现的算法,采用( )的数据结构最佳。‎ A、栈 B、顺序表 C、队列 D、单链表 答案：A ‎4.【单选题】4. 表达式a*(b+c)-d的后缀表达式是( )。‎ A、abc*+d-‎ B、cb+a*d-‎ C、abc+*d-‎ D、abcd+*-‎ 答案：C ‎5.【单选题】5. 递归过程或函数调用时,处理参数及返回地址需要用一种( )的数据结构。‎ A、栈 B、队列 C、多维数组 D、线性表 答案：A ‎6.【单选题】6. 最大容量为n的循环队列,队尾指针为rear,队头指针为front,则队空的条件是( )。‎ A、rear==front B、(rear+1)%n==front C、rear+1==front D、(rear-l)%n==front 答案：A ‎7.【单选题】7. 用带头结点的单链表表示队长大于1的队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( )。‎ A、仅修改队头指针 B、仅修改队尾指针 C、队头、队尾指针都要修改 D、队头,队尾指针都可能要修改 答案：A ‎8.【单选题】8. 对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为( )。‎ A、O(1),O(n)‎ B、O(n),O(n)‎ C、O(1),O(1)‎ D、O(n),O(1)‎ 答案：A ‎9.【判断题】9. 两顺序栈共享空间,也存在空间溢出问题。‎ 答案：√‎ ‎10.【判断题】10.在对不带头结点的链队列作出队操作时,不会改变头指针的值。‎ 答案：×‎ 数据结构与算法 完整 超星尔雅答案 可首页在线搜题 ‎1.【单选题】1. 串是一种特殊的线性表,其特殊性体现在( )。A A、数据元素是字符 B、顺序存储 C、链式存储 D、逻辑结构是线性结构 ‎2.【单选题】2. 若串S= ‘software’,其前缀真子串的数目是( )。A A、7‎ B、10‎ C、9‎ D、8‎ ‎3.【单选题】3. 设有两个串p和q ,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。A A、串的模式匹配 B、求子串 C、串联接 D、求串长 ‎4.【单选题】4. 已知串 S=‘aaab’,其next函数值为( )。A A、0123‎ B、1123‎ C、1231‎ D、1211‎ ‎5.【单选题】5. 函数strcmp(‘stcabuc’,’stbabuc’)的返回值是( )。D A、0‎ B、-1‎ C、2‎ D、1‎ ‎6.【判断题】6. KMP算法的特点是在模式匹配时指示主串的指针不会回溯。√‎ ‎7.【判断题】7. 模式串 P=‘abaabcac’的next函数值序列为01122312。√‎ ‎8.【判断题】8. 串的存储结构有顺序串、堆串和块链串三种。‎ ‎9.【判断题】9. 子串的定位运算称为串的模式匹配。√‎ ‎10.【判断题】10. 串’student’和’Student’相等。‎ 多维数组和广义表 ‎1.【单选题】1. 假设以行序为主序存储二维数组A=array[1…100,1…100],设每个数组元素占2个存储单元,基地址为10,则LOC[5,5]=( )。A A、818‎ B、B 808‎ C、1010‎ D、1020‎ ‎2.【单选题】2. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1…(n(n+1))/2]中,则在B中确定aij(i A A、j(j-1)/2+i B、i(i-1)/2+j C、i(i+1)/2+j D、j(j+1)/2+i ‎3.【单选题】3. 设广义表L=((a,b,c)),则L的长度和深度分别为( )。A A、1和2‎ B、1和1‎ C、1和3‎ D、2和3‎ ‎4.【单选题】4. 在稀疏矩阵的三元组顺序表中,每个三元组表示( )。D A、矩阵中数据元素的行号、列号和数据值 B、矩阵中非零元素的数据值 C、矩阵中数据元素的行号和列号 D、矩阵中非零元素的行号、列号和数据值 ‎5.【判断题】5. 多维数组可以看作是一种特殊的线性表。正确 ‎6.【判断题】6. 一个稀疏矩阵A[m,n]采用三元组顺序表形式表示,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了A[m,n]的转置运算。X ‎7.【判断题】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)。X ‎1.【单选题】1.树最适合用来表示的结构是( )。A A、元素间具有分支及层次关系的结构 B、元素间的有序结构 C、元素间的无序结构 D、元素间无联系的结构 ‎2.【单选题】2.任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置( )。B A、肯定发生变化 B、肯定不发生变化 C、有时发生变化 D、无法确定 ‎3.【单选题】3.判断线索二叉树中某结点P有左孩子的条件是( )。D A、p->LTag==1‎ B、p!=NULL C、p->lchild!=NULL D、p->LTag==0‎ ‎4.【单选题】4.设森林T中有4棵树,其结点个数分别为n1,n2,n3,n4,那么当森林T转换成一棵二叉树后,则根结点的右子树上有( )个结点。A A、n2+n3+n4‎ B、n1-1‎ C、n1‎ D、n1+n2+n3‎ ‎5.【单选题】5.以数据集{4,5,6,7,10,12,18}为叶结点权值所构造的哈夫曼树,其带权路径长度为( )。C A、155‎ B、160‎ C、165‎ D、170‎ ‎6.【单选题】6.以下属于前缀编码的是( )。‎ A、{0,1101,1110,1100,1111}‎ B、{0,1,01,010,110}‎ C、{00,01,10,11,101}‎ D、{01,00,10,001,110,101}‎ ‎7.【单选题】7.一棵具有N个结点的二叉树采用二叉链表进行存储,其中空指针域有( )个。A A、N+1‎ B、N C、N-1‎ D、不确定 ‎8.【单选题】8.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点,则该树中有( )个叶子结点。C A、10‎ B、11‎ C、12‎ D、13‎ ‎9.【判断题】9. 满二叉树一定完全是二叉树。√‎ ‎10.【判断题】10.二叉树的遍历结果不是唯一的。√‎ ‎1.【单选题】1.一个具有n个顶点的无向图最多有( )边。A A、n(n-1)/2‎ B、n(n-1)‎ C、n D、2n ‎2.【单选题】2.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则占用的存储空间为( )。D A、n+e B、e C、2e D、n+2e ‎3.【单选题】3.如果含有n个顶点的图形成一个环,则它有( )‎ 棵生成树。A A、n B、n-1‎ C、n+1‎ D、不确定 ‎4.【单选题】4.任何一个无向连通网的最小生成树( )。A A、有一棵或多棵 B、只有1棵 C、一定有多棵 D、可能不存在 ‎5.【单选题】5.判断一个有向图是否存在回路,可以用( )。D A、广度优先遍历算法 B、求关键路径的方法 C、Dijkstra方法 D、深度优先遍历算法 ‎6.【单选题】6.关键路径是事件结点网络中( )。A A、从源点到汇点的最长路径 B、最长回路 C、从源点到汇点的最短路径 D、最短回路 ‎7.【单选题】7.深度优先遍历类似于二叉树的( )。A A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 ‎8.【单选题】8.广度优先遍历类似于二叉树的( )。D A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 ‎9.【判断题】9.迪杰斯特拉算法求最短路径时,是按照路径长度递增的顺序求解的。√‎ ‎10.【判断题】10.任何一个有向图都一定存在拓扑序列。X 查找 ‎1.【单选题】1. 具有12个关键字的有序表,折半查找的平均查找长度( )。D A、‘10/12‎ B、25‎ C、’25/12‎ D、‘37/12‎ ‎2.【单选题】2. 如果要求用线性表既能较快地查找,又能适应动态变化的要求,则可采用( )查找方法。A A、分块查找 B、顺序查找 C、折半查找 D、基于属性 ‎3.【单选题】3. 已知一如下10个记录的表,其关键字序列为(2,15,19,25,30,34,44,55,58,80),用折半查找法查找关键字为55的记录,比较次数是( )。B A、1次 B、2次 C、3次 D、4次 ‎4.【单选题】4. 如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,在等概率情况下查找成功时的平均查找长度ASL为( )。A A、50‎ B、48‎ C、45‎ D、47‎ ‎5.【单选题】5. 对包含n个元素的散列表进行查找,平均查找长度为( )。A A、不直接依赖于n B、O(n2)‎ C、O(log2n)‎ D、O(n)‎ ‎6.【单选题】6. 衡量查找算法效率的主要标准是( )。A A、平均查找长度 B、元素个数 C、所需的存储量 D、算法难易程度 ‎7.【判断题】7. Hash表的平均查找长度与处理冲突的方法无关。X ‎8.【判断题】8. 在二叉树排序树中插入一个新结点,总是插入到叶结点下面。√‎ ‎9.【判断题】9. 哈希表是一种将关键字转换为存储地址的存储方法。√‎ ‎10.【判断题】10.在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。X 排序 ‎1.【单选题】1. 有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始小根堆为( )。A A、-1,4,7,8,20,15,7,9‎ B、-1,4,8,9,20,7,15,7‎ C、-1,7,15,7,4,8,20,9‎ D、A,B,C均不对。‎ ‎2.【单选题】2. 一组记录的关键字为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( )。A 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)‎ ‎3.【单选题】3. 对下列整数序列使用基数排序,一趟分配收集之后的结果是( )。(179,208,93,306,55,859,984,9,271,33)A A、{271,93,33,984,55,306,208,179,859,9}‎ B、{93,55,9,33,179,208,271,306,859,984}‎ C、{208,306,9,33,55,859,179,271,984,93}‎ D、{9,33,55,93,179,208,271,306,859,984}‎ ‎4.【单选题】4. 对序列{15,9,7,8,20,-1,4}进行排序,进行一趟后数据的排列变为{9,15,7,8,20,-1,4},则采用的排序方法是( )。A A、直接插入排序 B、选择排序 C、堆排序 D、希尔排序 ‎5.【单选题】5. 评价排序算法好坏的标准主要是( )。A A、执行时间和所需的辅助空间 B、执行时间 C、辅助空间 D、算法本身的复杂度 ‎6.【单选题】6. 对n个不同的排序码进行冒泡(递增)排序,在下列( )情况比较的次数最多。。A A、从大到小排列好的 B、从小到大排列好的 C、元素无序 D、元素基本有序 ‎7.【判断题】7. 简单选择排序和堆排序性能都受初始序列顺序的影响。X ‎8.【判断题】8. 快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。√‎ ‎9.【判断题】9. 堆排序所需的时间与待排序的记录个数无关。X ‎10.【判断题】10. 采用希尔方法排序时,若关键字的排列杂乱无序,则效率最高。√‎ 第十一章章节测验 ‎1.【多选题】‎ 文件压缩产品最主要的功能是（）。AB A、压缩 B、解压 C、广告 D、传送 ‎2.【判断题】‎ 哈夫曼树最典型、最广泛的应用是在编码技术上。利用哈夫曼树，构造所得的哈弗曼编码是一种最优前缀编码。√‎ ‎3.【判断题】‎ 在设计产品时，只需要办好程序员的角色就可以了。X