第0章 课程简介
既然高级语言通常都内建了数据结构语法和API,学习数据结构就没有必要了。…
在开发实际项目时,应优先考虑自己来实现常见的数据结构。
实现某种数据结构时,通常对使用的编程语言没有限定。
第1章 绪论
用计算机求解的问题可以分为( )? A简单型问题、复杂型问题 B文本型问题、二进制型问题 C数值型问…
用计算机求解问题的一般步骤是什么? A分析问题、设计算法、编程/调试、得到结果 B分析问题、建立…
建模的本质包括( )。 A从问题中抽取出关键对象 B找出问题中关键对象之间的关系 C以合适的语言(或…
数据结构是一门介于( )三者之间的课程。 A数学、程序设计、硬件系统 B数学、操作系统、硬件系统 …
下列哪一个不是逻辑结构? A栈 B链表 C二叉树 D有向图
下列哪一个不是物理结构? A顺序表 B链表 C二叉链表 D哈希表
Windows中的文件系统是一种( )。 A队列 B树 C二叉树 D图
微信朋友圈的好友关系是一种( )。 A树 B线性表 C数组 D图
参与击鼓传花游戏的N个人是一种( )。 A树 B线性表 C数组 D图
下列哪一个说法是正确的? A数据项是数据的基本组成单元 B数据元素是数据的基本组成单元 C数据项…
在实际应用中,决定选取何种物理结构时,一般不考虑( )。 A数据元素要支持的操作 B数据元素的总个数 …
京东/淘宝中的商品分类是一种( )。 A树 B线性表 C数组 D图
抽象数据类型从( )结构的角度来描述( )、( )及( )。 A逻辑、元素、关系、操作 B逻辑、元素、关系、类型 …
数据类型可分为原子类型和( )。 A数值类型 B非数值类型 C数组类型 D结构类型…
设某数据结构DS=(D,R),D={1,2,3,4,5,6,7,8,9},R={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>,…
所有的编程语言都支持相同的数据类型。
不同的数据类型支持的操作可能不一样。
C++的引用参数是对函数的实参而言的。
算法必须具备输入、输出、( )等5个特性。 A可行性、可移植性和可扩展性 B确定性、有穷性和稳定性 …
算法能正确处理其接收的非法或恶意输入,称为算法的( )。 A健壮性 B安全性 C可读性 D正确性…
下面的程序段违反了算法的( )。 1 2 3 4 5 6 void sum() { int n=2; while (…
下列哪一个说法是错误的? A空间复杂度为O(1)是指算法只占用一个临时存储单元 B时间复杂度通常是…
某算法的时间复杂度为O(n^2),表明该算法的( )。 A问题规模是n^2 B问题规模与n^2成正比 C执行时间…
分析算法的时间复杂度时,不用关注( )。 A输入的量 B输入的具体状态 C完成的功能 D基本步骤的执行…
算法分析的目的是( )。 A分析算法所用的数据结构是否合理 B分析算法完成的功能 C分析算法的时空…
设n为偶数,下列伪码中,注释所在行的总执行次数是( )。 1 2 3 4 5 FOR i = 1 TO n DO …
下列程序段的时间复杂度是( )。 1 2 3 4 5 s=i=0; do { i++; s+=i; } while(…
下列程序段的时间复杂度是( )。 1 2 3 4 5 6 7 for(i=0; i<m; i++) for(j=0; j<t; j+…
第2章 线性表
线性表是具有n个( )的有限序列。 A整数 B字符 C数据元素 D数据项…
线性表中的每个元素都有且仅有一个前驱。
线性表至少要包含一个元素。
设线性表长度为n,以下哪个操作在顺序表上实现比其在链表上的效率更高? A交换第1个元素与第2个元素…
对于顺序存储的线性表,增加、删除元素的时间复杂度为( )。 AO(0) BO(1) CO(n) DO(n^2)…
若一维数组的首个元素是a0,每个元素占d个字节,则其随机存取公式是( )? ALoc(ai) = Loc(a0) + (i+1)*d…
关于下列代码段,错误的说法是( )? 1 2 3 4 5 typedef struct { ElemType *elem; …
在一个长度为N的顺序表中第i个元素(1 <= i <= N+1)之前插入一个元素,需向后移动( )个元素? Ai BN-i C…
在一个长度为N的顺序表中第i个元素(1 <= i <= N+1)之前插入一个元素,然后(前面的插入操作完成后)再删…
对于C语言中的数组,&a[i]等价于a+i,后者中的i是指字节数。
高级语言通常不关心一个占了多个字节的数据元素的非首字节。
顺序表就是以元素在内存中的相邻来表示它们在逻辑上的相邻。
下面关于链表L的说法正确的是( )? AL代表链表在内存中的整体结构 BL是一个指针数组,其各元素分别指…
若某线性表最常用的操作是存取任意位置的元素,则( )存储方式最合适。 A顺序表 B双向链表 C双向循…
链表不具备的特点是( )。 A可随机访问任一结点 B插入删除不需要移动元素 C不必预估存储空间容量 …
带头结点的单链表head为空表的条件是( )。 Ahead==NULL Bhead->next==NULL Chead->next==head D…
设p为单链表中某结点的指针(指向后继的指针名为next),则在p结点后插入新结点(指针为s)的语句是( )和 p->…
下面关于线性表的叙述中,错误的是哪一个? A线性表采用顺序存储,必须占用一段连续的存储单元 B线性…
指针p指向双向循环链表L的表尾元素的条件是( )。 Ap==L Bp==NULL Cp->prior==L Dp->next==L…
在单链表中删除p所指结点的后继结点的语句是( )。 Ap->next=p->next->next; Bp->next=NULL; Cp=p…
删除单链表中指针p所指结点的语句序列为( )。 Aq=p->next; p->data=q->data; p->next=q->next; fre…
若希望以O(1)的时间复杂度找到当前结点的前驱,则链表最好采用( )。 A单链表 B单循环链表 C双向链…
循环链表的主要优点是( )? A不再需要头指针了 B已知某个结点的位置后,能很容易找到它的直接前驱结点…
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最…
对于单链表,要得到某个结点的值,只需要知道该结点的指针即可,因此,单链表也支持随机存取。…
若使用的编程语言不支持指针语法,则无法用该语言实现链表。
L指向以头插法创建的单链表的头结点,对L进行遍历得到的序列与创建链表时的输入序列一致。…
删除单链表的第i个结点不需要移动元素,故其时间复杂度为O(1)。
以链式存储并按指数递增的2个多项式(各有n项)相加,最少的比较次数是( )? An Bn+1 C2*n D2*n+1…
以线性表存储多项式,链式存储一定比顺序存储好。
稀疏多项式适合以链表来存储。
第3章 栈和队列
下面的哪个例子不具有栈的特性? A多个人依次过独木桥时,最前面的人发现前方有危险,需要退回到入口 …
下列关于栈的说法错误的是? A栈具有后进先出特性 B栈具有先进后出特性 C元素的入栈顺序和出栈顺…
入栈顺序为1、2、3,共有( )种不同的出栈序列(2次入栈之间可能有0到多次出栈)。 A6 B5 C3 D1…
栈顶元素和栈底元素有可能是同一个元素。
栈底元素不可能被删除。
和线性表不同,栈不需要显式指定插入和删除的位置。
6个元素按3,2,1,4,5,6 的顺序进栈(2次入栈间可能有零至多次出栈),下列哪个不是合法的出栈序列? A2,1,4,3,6,5 B…
设入栈序列是p1,p2,p3,…,pn(2次入栈间可能有零至多次出栈),出栈序列是1,2,3,…,n,若p3=3,则p1( )。 A可能是2 B…
指针top指向链栈的栈顶,则出栈操作对应的语句为( )。 Atop=top+1; Btop=top-1; Ctop->next=top; …
对于顺序栈和链栈, 它们的入栈和出栈操作的时间复杂度均为( )。 AO(n) BO(n^2) CO(1) DO(log2(n)…
使用栈将十进制数N转换为r进制数时,每次入栈的是( )? AN/r BN%r CN-r Dr…
使用栈判断括号串是否匹配,当读入左括号时应( ),算法结束时,若栈( ),则括号串是匹配的。 A出栈、为空 B…
一个递归算法必须包括( )。 A递归部分 B终结条件和递归部分 C迭代部分 D终结条件和迭代部分…
下列关于递归错误的说法是( )。 A递归函数一定有返回值 B递归算法一定有终结条件 C递归算法执行…
将递归算法转换成等价的非递归算法,通常应借助( )。 A树 B队列 C数组 D栈…
将递归算法转换成等价的非递归算法,一定要借助栈。
解决同一问题,递归形式的算法的执行效率通常比非递归形式要高。
任何递归形式的算法,都可以转换为非递归的形式。
栈和队列的共同特点是( )。 A只允许在端点处插入和删除元素 B都是先进后出 C都是先进先出 D没有…
队列中允许插入元素的一端称为( ),允许删除元素的一端称为( )。 A队尾、队尾 B队尾、队头 C队头、队…
下列关于队列的说法错误的是? A队列具有先进先出特性 B队列具有后进后出特性 C元素的入队顺序和…
下面的场景中,不符合队列操作特性的是? A食堂窗口取餐 B发送到打印机的多个Word文件 C按退格键删…
栈和队列都是限制了存取点的线性表。
容量为m的循环队列Q,队头和队尾位置分别是front和rear,则队列满的条件是( )? AQ.rear==Q.front+1 B(Q…
容量为m的循环队列Q,队头和队尾位置分别是front和rear,则队列长度是( )? AQ.rear-Q.front BQ.front-Q…
容量为m的循环队列Q,队尾位置是rear,则入队时对rear的操作是( )? AQ.rear=Q.rear-1 BQ.rear=(Q.rear-…
容量为m的循环队列Q,队头位置是front,则出队时对front的操作是( )? AQ.front=Q.front-1 BQ.front=(Q.…
循环队列的容量为6,rear和front分别是0和3,则从队列中删除3个元素,再加入2个元素后,rear和front分别…
第4章 数组
无论是几维数组,都可视为线性表。
通常不会对数组进行增删元素的操作。
与其他数据结构不同,数组通常只采用顺序存储结构。
将M行N列的二维数组按行为主序存放,首个元素a00存于地址B(占d个字节),则元素aij的地址是( )? AB+(i*M+j)…
将M行N列的二维数组按列为主序存放,首个元素a00存于地址B(占d个字节),则元素aij的地址是( )? AB+(i*M+j)…
二维数组A[0..5][0..6]按列为主序存储在起始地址为1000的内存单元中,每个元素占5个字节,则元素A[5]…
设有数组A[i, j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序…
如果计算机主板上插有2根及以上的内存条,则此计算机的内存空间是二维的。…
无论是几维数组,都要转换为一维数组才能存放到内存中。
故意不用编程语言原生提供的数组语法来实现数组这种数据结构,通常是没有必要的。…
所有高级语言的二维数组都是按行为主序存放的。
所有高级语言的二维数组都是严格占据一段连续的存储空间。
随机存取是顺序存储才有的特性。
随机存取就是随机地读写一段连续内存中的某个位置。
访问一段连续存储空间中某个位置的时间复杂度与该段空间的大小和要访问的位置有关。…
将随机存取中的“随机”理解为“任意”、“随意”、“直接”,更能体现随机存取的本质。…
机械硬盘的工作原理决定了其不支持随机存取。
10阶对称矩阵以行为主序存储,a[1][1]为首个元素,其地址为1,每个元素占1个字节,则a[8][5]的地址是( )。 …
将三对角矩阵A[1..100][1..100]按行为主序存入一维数组B[1..298]中,则元素A[66][65]在B中的位置为…
三对角线矩阵A[1..n][1..n]以行序为主顺序存储,其存储始址是b,每个元素占一个字节,则元素A[i][j] (1…
对m行n列的未经压缩(即以二维数组表示)的稀疏矩阵进行转置,时间复杂度是( )? AO(m) BO(n) CO(m*n) D…
以三元组顺序表存储的稀疏矩阵(m行n列,非零元个数为t)的常规转置算法,时间复杂度是( )? AO(n*t) BO(m*t…
以三元组顺序表存储的稀疏矩阵(m行n列,非零元个数为t)的快速转置算法,时间复杂度是( )? AO(n*t) BO(n+t…
对稀疏矩阵进行压缩存储的目的是节省存储空间。
稀疏矩阵被压缩存储后,仍具有随机存取的特性。
第5章 树和二叉树
下列不是树的是( )? A企业的部门组织架构 BWindows中的文件系统 C书的目录 D多个人之间的同学关…
下列关于树的说法正确的是( )? AParent经常译为“父母”、“双亲”,因此,树中某个结点的双亲结点可能…
树的定义本身就是递归的。
二叉树中孩子数为1和2的结点个数分别是10和20,则该二叉树共有( )个结点。 A41 B51 C49 D39…
设一棵三叉树中有50个度为0的结点,21个度为2的结点,则度为3的结点有( )个。 A51 B22 C14 D15…
规定根结点在第1层,则具有K层的二叉树至少有( )个结点? AK BK-1 C2^(K-1) D2^K-1…
规定根结点在第1层,则具有K层的二叉树至多有( )个结点? AK BK-1 C2^(K-1) D2^K-1…
设完全二叉树的根结点序号为1,( )可判定序号分别为p和q的两个结点在同一层。 A⌊log2(p)⌋=⌊log2(q…
若根的层次为1,具有61个结点的完全二叉树的高度为( )。 A5 B6 C7 D8…
高度为h的二叉树中只有度为0和2的结点,则此二叉树的结点数至少有( )个。 Ah+1 B2*h+1 C2*h D2*h-…
具有2048个结点的二叉树的最小高度是( )? A11 B12 C13 D2048
下列有关二叉树的说法正确的是( )。 A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有…
在一棵高度为k的满二叉树中,结点总数为( )。 A2^(k-1) B2^k C2^k-1 D向下取整(log2(k))+1…
一棵树高为k的完全二叉树至少有( )个结点。 A2^k -1 B2^(k-1) -1 C2^(k-1) D2^k…
若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是( )。 A9 B11 C15 D不确定…
以二叉链表存放一棵含有N个节点的二叉树,共有( )个空指针? AN+1 BN-1 CN D2*N…
以二叉链表存放一棵含有N个节点的二叉树,共有( )个非空指针? AN+1 BN-1 CN D2*N…
下列关于二叉树的说法中错误的是( )? A若二叉树使用顺序方式存储,则必须先将该二叉树补全为满二叉树…
在二叉树的先序、中序和后序序列中,所有叶结点的先后顺序( )。 A都不相同 B完全相同 C先序和中序…
若二叉树的先序序列为ABDECF,中序序列为DBEAFC,则其后序序列为( )。 ADEBAFC BDEFBCA CDEBCFA DDE…
若二叉树的中序序列为A+B*C-D/E,后序序列为ABC*+DE/-,则其先序序列为( )。 A-A+B*C/DE B-A+B*CD/E …
前序序列与中序序列相同的二叉树为( )。 A根结点无左孩子的二叉树 B所有结点只有右孩子的二叉树 …
前序序列和后序序列相同的二叉树为( )。 A根结点无左孩子的二叉树 B所有结点只有右孩子的二叉树 …
给定先序序列和后序序列,不能唯一确定二叉树。
一棵非空二叉树一定满足:某个结点若有左孩子,则其中序前驱一定没有右孩子。…
在线索二叉树中,结点t没有左子树的充要条件是( )。 At->lchild==NULL Bt->ltag==THREAD Ct->ltag=…
n个结点的线索二叉树上含有的非空线索数为( )。 A2n Bn-1 Cn+1 Dn
二叉树在线索后,仍不能有效求解的问题是( )? A先序线索二叉树中求先序后继 B中序线索二叉树中求中序…
二叉树线索化后,任一结点均有指向其前驱和后继的线索。
中序线索树中,结点的前驱是其左子树上最左的结点。
中序线索树中,结点的后继是其右子树上最左的结点。
二叉树的中序序列中,最后一个结点是整棵树最右的那个结点。
二叉树经中序线索化后,不存在空指针。
以孩子-兄弟表示法表示的树,每个结点包含两个指针成员,分别指向当前结点的( )和( )。 A第一个孩子、第…
如果BT是由树T转换而来的二叉树,则对T的后序遍历就是对BT的( )遍历。 A先序 B中序 C后序 D层序…
利用二叉链表存储树,则根结点的右指针是( )。 A指向最左孩子 B指向最右孩子 C空 D非空…
下列哪一个不是树的存储形式? A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法…
一棵树必须转换成二叉树后才能存储。
树的叶子数一定等于其对应的二叉树的叶子数。
对树进行先序遍历,等价于以先序遍历该树对应的二叉树。
对树进行后序遍历,等价于以后序遍历该树对应的二叉树。
关于哈夫曼树的叙述正确的是( )。 A树的左分支必须编码成0,右分支必须编码成1 B权值较大的结点对应…
由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的WPL为( )。 A23 B37 C44 D46…
根据使用频率,为5个字符设计的哈夫曼编码不可能是( )。 A111, 110, 10, 01, 00 B000, 001, 010, 01…
哈夫曼树是带权路径长度最短的树,路径上权值较小的结点通常离根( )。 A不确定 B较近 C较远…
设给定权值的叶子总数有n个,其哈夫曼树的结点总数为( )。 A不确定 B2n C2n+1 D2n-1…
哈夫曼编码是前缀编码。
在哈夫曼树中,权值相同的叶结点一定在同一层。
第6章 图
无向图中一个顶点的度是指图中( )。 A通过该顶点的简单路径数 B通过该顶点的环数 C与该顶点相邻…
无向图中所有顶点的度数之和等于所有边数( )倍,有向图中所有顶点的入度之和等于所有顶点出度之和的( …
下列关于图和树的说法,错误的是( )? A树可以看作图的特例 B树中有一个特殊的元素(根),而图中每个元素…
有向图中有一条边,则v称为弧头。
N个顶点的有向完全图有N(N-1)条边。
有向图中,顶点的入度是以v为弧尾的边的数量。
若含有N个顶点的有向图的边数远小于N*(N-1),且要方便地求得某个顶点的出度,则采用( )存储结构较为合…
下列哪一种图的邻接矩阵是对称矩阵? A有向图 B无向图 CAOV网 D以上均是…
采用邻接表表示有向图,若图中某顶点的入度和出度分别为d1和d2,则该顶点对应的单链表的表结点数为( )…
无向图的邻接矩阵一定是对称矩阵。
若图的邻接矩阵不是对称矩阵,则该图一定是有向图。
若图的邻接矩阵是对称矩阵,则该图一定是无向图。
一个有向图的邻接表和逆邻接表中结点的个数可能不相等。
图的深度优先搜索类似于树的( )遍历,图的广度优先搜索类似于树的( )遍历。 A先序,层序 B层序,先序 C中…
下列关于图的遍历的说法,错误的是( )。 A图的遍历是从给定的起始顶点出发,将每一个顶点访问且仅访问…
无向图G=(V,E),其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深…
深度优先搜索只适用于以邻接矩阵存储的图。
广度优先搜索每访问一个顶点后,都要将其放到栈中。
N个顶点的无向连通图,至少有( )条边,至多有( )条边。 AN,N*(N-1) BN-1,N*(N-1)/2 CN-1,N*(N-1) DN,N*(N-…
N个顶点的有向连通图,至少有( )条边,至多有( )条边。 AN,N*(N-1) BN-1,N*(N-1)/2 CN-1,N*(N-1) DN,N*(N-…
n个顶点的图,最少有( )个连通分量,最多有( )个连通分量。 A0,n B1,n-1 C1,n D0,n-1…
有28条边的非连通无向图,至少有( )个顶点。 A6 B7 C8 D9
连通分量是图的最小连通子图。
生成树是连通图的最大连通子图。
求稠密图的最小生成树, 最好用Prim算法。
连通图上各边权值均不相同,则该图的最小生成树一定是唯一的。
从有向图G中的给定起始顶点v0出发,若能到达其他任一顶点,则G是强连通图。…
N个顶点的无向图,若边数大于2N,则该图必是连通图。
对有向图G进行拓扑排序的目的不是( )。 A判断G是否包含环 B查看G中顶点所代表的活动的先后关系 C…
无向图G=(V,E),其中V={a,b,c,d,e},E={,,,,,},对该图进行拓扑排序,下面哪一个不是其拓朴序列? Aa,d,c,…
在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( )。 G中有一条从Vj到Vi的路…
若有向图的邻接矩阵中,主对角线以下元素均为0, 则该图一定无环。…
拓扑排序算法中,必须使用队列来存放入度为0的顶点。
对于下图,以顶点1为起始顶点,使用Dijkstra算法依次找到的多条最短路径所到达的终点分别是( )? A3,4,6…
第7章 查找
查找表可分为( )? A定长查找表、变长查找表 B静态查找表、动态查找表 C简单查找表、复杂查找表 D…
下列关于关键字的说法中正确的是( )? A学生的姓名可以作为主关键字 B只要某个数据项是可比较的,其就…
除非特别说明,谈到平均查找长度,通常暗含了等概率和查找成功这两个前提。…
在长度为n的查找表中做顺序查找,查找成功时的平均查找长度是( )。 A(n+1)/2 Bn/2 Cn+1 Dn…
采用折半查找,在长度为18的有序顺序表(下标从1开始)中查找第3个关键字,依次比较的关键字的下标是( )。 …
下面关于折半查找(或二分查找)的叙述正确的是( )。 A表必须有序,表可以顺序方式存储,也可以链表方式存…
在n个关键字构成的有序顺序表中进行折半查找,最大比较次数是( )。 A向下取整(log2(n)) B向上取整(l…
在长度为n的查找表中做顺序查找,查找失败时的平均查找长度是( )。 A(n+1)/2 Bn/2 Cn+1 Dn…
索引顺序表的数据组织方式是( )? A数据分成若干块,每块内数据有序 B数据分成若干块,每块内数据不必有…
顺序查找仅适用于顺序存储。
折半查找不适用于链式存储。
分块查找同时使用了顺序查找和折半查找,故一般而言,其性能介于顺序查找和折半查找之间。…
折半查找的查找性能一定高于顺序查找。
将序列{50,72,43,85,75,20,35,45,65,30}逐个插入初始为空的二叉排序树后,查找30要进行( )次比较。 A…
对二叉排序树进行()遍历将得到递增序列。 A先序 B中序 C后序 D层序…
以二叉链表存储二叉排序树,关键字最大的结点( )。 A左指针一定为空 B右指针一定为空 C左右指针均…
当BST每层仅有一个结点时,其查找算法退化成( ),ASL上升为( )。 A顺序查找、(n+1)/2 B顺序查找、n C折…
高度为5的AVL树至少有( )个结点。 A10 B12 C15 D17
平衡二叉树中根结点的平衡因子是1,若新结点插入到根的左子树上,则必定需要调整。…
将长度为n的元素序列组织成AVL树时,无论序列如何排列,总能保证树的ASL为log2(n)的量级。…
采用哈希函数H(k)=k%7,依次存放关键字{38,25,74,63,52,48}到A[0..6]中,若采用线性探测法解决冲突,则…
下列以链地址法处理哈希表冲突的叙述中,错误的是( )。 A此时的哈希表整体上是一个数组 B此时的哈希…
将10个元素存放到容量为100000的哈希表中,则( )产生冲突。 A一定会 B一定不会 C仍可能会…
通过( )法构造的哈希函数一定不会发生冲突。 A除留余数 B平方取中 C直接定址 D以上均可能发生冲…
k个关键字互为同义词,采用线性探测法处理冲突,则至少要进行( )次探测? Ak(k-1)/2 Bk Ck-1 Dk(k+1)/…
下面关于哈希函数的说法中正确的是( )。 A哈希函数越复杂越好,因为这样随机性好,冲突可能性低 B除留…
在哈希表中查找元素时,元素的存放地址是算出来的,故无需比较元素。…
Hash表的平均查找长度与处理冲突的方法无关。