第1章 绪论1.1 数据结构是什么随堂测验1、用计算机求解的问题可以分为（ ）？
a、简单型问题、复杂型问题
b、文本型问题、二进制型问题
c、数值型问题、非数值型问题
d、基本型问题、结构型问题
2、用计算机求解问题的一般步骤是什么？
a、分析问题、设计算法、编程/调试、得到结果
b、分析问题、建立数学模型、编程/调试、得到结果
c、分析问题、设计算法、建立数学模型、编程/调试、得到结果
d、分析问题、建立数学模型、设计算法、编程/调试、得到结果
3、建模的本质包括（ ）。
a、从问题中抽取出关键对象
b、找出问题中关键对象之间的关系
c、以合适的语言(或符号)描述问题中的关键对象以及它们之间的关系
d、以上三者均是
4、数据结构是一门介于（ ）三者之间的课程。
a、数学、程序设计、硬件系统
b、数学、操作系统、硬件系统
c、程序设计、操作系统、硬件系统
d、程序设计、计算机网络、硬件系统
1.2 概念和术语随堂测验1、下列哪一个不是逻辑结构？
a、栈
b、链表
c、二叉树
d、有向图
2、下列哪一个不是物理结构？
a、顺序表
b、链表
c、二叉链表
d、哈希表
3、windows中的文件系统是一种（ ）。
a、队列
b、树
c、二叉树
d、图
4、微信朋友圈的好友关系是一种（ ）。
a、树
b、线性表
c、数组
d、图
1.2 概念和术语随堂测验1、参与击鼓传花游戏的n个人是一种（ ）。
a、树
b、线性表
c、数组
d、图
2、下列哪一个说法是正确的？
a、数据项是数据的基本组成单元
b、数据元素是数据的基本组成单元
c、数据项能拆分为更小的单元
d、结构类型一定由原子类型组合而成
3、在实际应用中，决定选取何种物理结构时，一般不考虑（ ）。
a、数据元素要支持的操作
b、数据元素的总个数
c、数据元素的具体值
d、所用的编程语言实现该种结构是否方便
4、京东/淘宝中的商品分类是一种（ ）。
a、树
b、线性表
c、数组
d、图
1.3 抽象数据类型随堂测验1、抽象数据类型从（ ）结构的角度来描述（ ）、（ ）及（ ）。
a、逻辑、元素、关系、操作
b、逻辑、元素、关系、类型
c、物理、元素、关系、操作
d、物理、元素、关系、类型
2、数据类型可分为原子类型和（ ）。
a、数值类型
b、非数值类型
c、数组类型
d、结构类型
3、设某数据结构ds=(d,r)，d={1,2,3,4,5,6,7,8,9}，r={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>,<3,7>}，则ds是（ ）。
a、线性结构
b、树型结构
c、物理结构
d、图型结构
4、所有的编程语言都支持相同的数据类型。
5、不同的数据类型支持的操作可能不一样。
6、c 的引用参数是对函数的实参而言的。
1.4 算法及其设计要求随堂测验1、算法必须具备输入、输出、（ ）等5个特性。
a、可行性、可移植性和可扩展性
b、确定性、有穷性和稳定性
c、可行性、确定性和有穷性
d、可读性、可扩展性和安全性
2、下面的程序段违反了算法的（ ）。 void sum() { int n=2; while (!odd(n)) n =2; printf(n); }
a、确定性
b、可行性
c、健壮性
d、有穷性
3、算法能正确处理其接收的非法或恶意输入，称为算法的（ ）。
a、健壮性
b、安全性
c、可读性
d、正确性
单元测验1、下列哪一个说法是错误的？
a、空间复杂度为o(1)是指算法只占用一个临时存储单元
b、时间复杂度通常是指最坏情况下的时间复杂度
c、所用编程语言和输入数据都相同时，2个算法分别在同一台计算机上运行，花费时间较长的算法可能具有更低的时间复杂度
d、同一个算法，分别用编译型语言和解释型语言编写为程序，后者运行耗时可能更少
2、某算法的时间复杂度为o(n^2)，表明该算法的（ ）。
a、问题规模是n^2
b、问题规模与n^2成正比
c、执行时间等于n^2
d、执行时间与n^2成正比
3、分析算法的时间复杂度时，不用关注（ ）。
a、输入的量
b、输入的具体状态
c、完成的功能
d、基本步骤的执行总次数
4、算法分析的目的是（ ）。
a、分析算法所用的数据结构是否合理
b、分析算法完成的功能
c、分析算法的时空效率以求改进
d、分析算法的可读性和可扩展性
5、设n为偶数，下列伪码中，注释所在行的总执行次数是（ ）。 for i = 1 to n do for j = 2*i to n do m = m 1; // 此行的总执行次数
a、n^2
b、(n^2)/4
c、(n^2)/2
d、不确定
6、下列程序段的时间复杂度是（ ）。 s=i=0; do { i ; s =i; } while(i<=n);
a、o(n)
b、o(log2(n))
c、o(n*log2(n))
d、o(n^2)
7、下列程序段的时间复杂度是（ ）。 for(i=0; i
a、o(m n t)
b、o(m n*t)
c、o(m*t n)
d、o(m*n*t)
第0章 课程简介
单元测验
1、既然高级语言通常都内建了数据结构语法和api，学习数据结构就没有必要了。
2、在开发实际项目时，应优先考虑自己来实现常见的数据结构。
3、实现某种数据结构时，通常对使用的编程语言没有限定。
第2章 线性表
2.1 概念及adt随堂测验
1、线性表是具有n个（ ）的有限序列。
a、整数
b、字符
c、数据元素
d、数据项
2、线性表中的每个元素都有且仅有一个前驱。
3、线性表至少要包含一个元素。
2.2 线性表的顺序实现——顺序表随堂测验
1、设线性表长度为n，以下哪个操作在顺序表上实现比其在链表上的效率更高？
a、交换第1个元素与第2个元素的值
b、输出第i（1<=i<=n）个元素的值
c、依次输出n个元素的值
d、输出值为x的元素在线性表中的序号
2、对于顺序存储的线性表，增加、删除元素的时间复杂度为（ ）。
a、o(0)
b、o(1)
c、o(n)
d、o(n^2)
3、若一维数组的首个元素是a0，每个元素占d个字节，则其随机存取公式是（ ）?
a、loc(ai) = loc(a0) (i 1)*d
b、loc(ai) = loc(a0) i*d
c、loc(ai) = loc(a0) (i-1)*d
d、loc(ai) = loc(a0) i
4、关于下列代码段，错误的说法是（ ）？ typedef struct { elemtype *elem; int length; int size; } sqlist;
a、可以把elem当做数组名来用
b、size是表容量，length是表长
c、size一定大于或等于length
d、sqlist是一个结构体变量名
2.2 线性表的顺序实现——顺序表随堂测验
1、对于c语言中的数组，&a[i]等价于a i，后者中的i是指字节数。
2、高级语言通常不关心一个占了多个字节的数据元素的非首字节。
3、顺序表就是以元素在内存中的相邻来表示它们在逻辑上的相邻。
2.3 线性表的链式实现——链表随堂测验
1、下面关于链表l的说法正确的是（ ）？
a、l代表链表在内存中的整体结构
b、l是一个指针数组，其各元素分别指向链表的每个元素结点
c、l仅是指向链表头结点的指针
d、l是链表的头结点
2、若某线性表最常用的操作是存取任意位置的元素，则（ ）存储方式最合适。
a、顺序表
b、双向链表
c、双向循环链表
d、单循环链表
3、链表不具备的特点是（ ）。
a、可随机访问任一结点
b、插入删除不需要移动元素
c、不必预估存储空间容量
d、所需存储空间与其长度成正比
4、带头结点的单链表head为空表的条件是（ ）。
a、head==null
b、head->next==null
c、head->next==head
d、head!=null
5、设p为单链表中某结点的指针（指向后继的指针名为next），则在p结点后插入新结点（指针为s）的语句是（ ）和 p->next = s。
a、s->next = p
b、s = p->next
c、s = p
d、s->next = p->next
6、删除单链表中指针p所指结点的语句序列为（ ）。
a、q=p->next; p->data=q->data; p->next=q->next; free(q);
b、q=p->next; q->data=p->data; p->next=q->next; free(q);
c、q=p->next; p->next=q->next; free(q);
d、q=p->next; p->data=q->data; free(q);
7、若希望以o(1)的时间复杂度找到当前结点的前驱，则链表最好采用（ ）。
a、单链表
b、单循环链表
c、双向链表
d、以上均可
2.3 线性表的链式实现——链表随堂测验
1、循环链表的主要优点是（ ）？
a、不再需要头指针了
b、已知某个结点的位置后，能很容易找到它的直接前驱结点
c、在进行删除操作后，能保证链表不断开
d、从表中任一结点出发，都能遍历整个链表
2、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
a、顺序表
b、单链表
c、单循环链表
d、双向链表
3、对于单链表，要得到某个结点的值，只需要知道该结点的指针即可，因此，单链表也支持随机存取。
4、若使用的编程语言不支持指针语法，则无法用该语言实现链表。
5、l指向以头插法创建的单链表的头结点，对l进行遍历得到的序列与创建链表时的输入序列一致。
6、删除单链表的第i个结点不需要移动元素，故其时间复杂度为o(1)。
单元测验
1、以链式存储并按指数递增的2个多项式（各有n项）相加，最少的比较次数是（ ）？
a、n
b、n 1
c、2*n
d、2*n 1
2、以线性表存储多项式，链式存储一定比顺序存储好。
3、稀疏多项式适合以链表来存储。
第3章 栈和队列
3.1 栈的定义及adt随堂测验
1、下面的哪个例子不具有栈的特性？
a、多个人依次过独木桥时，最前面的人发现前方有危险，需要退回到入口
b、弹夹的装填与发射
c、一条单向车道上，最前面的车抛锚了，需要清空道路等待救援
d、多辆车依次通过高速收费站的某个窗口
2、下列关于栈的说法错误的是？
a、栈具有后进先出特性
b、栈具有先进后出特性
c、元素的入栈顺序和出栈顺序相反
d、栈允许在中间位置插入、删除元素
3、入栈顺序为1、2、3，共有（ ）种不同的出栈序列（2次入栈之间可能有0到多次出栈）。
a、6
b、5
c、3
d、1
4、栈顶元素和栈底元素有可能是同一个元素。
5、栈底元素不可能被删除。
6、和线性表不同，栈不需要显式指定插入和删除的位置。
3.2 栈的顺序实现——顺序栈随堂测验
1、设入栈序列是p1，p2，p3，…，pn（2次入栈间可能有零至多次出栈），出栈序列是1，2，3，…，n，若p3=3，则p1（ ）。
a、可能是2
b、一定是2
c、不可能是1
d、一定是1
2、指针top指向链栈的栈顶，则出栈操作对应的语句为（ ）。
a、top=top 1;
b、top=top-1;
c、top->next=top;
d、top=top->next;
3、对于顺序栈和链栈， 它们的入栈和出栈操作的时间复杂度均为（ ）。
a、o(n)
b、o(n^2)
c、o(1)
d、o(log2(n))
3.3 栈的应用随堂测验
1、使用栈将十进制数n转换为r进制数时，每次入栈的是（ ）？
a、n/r
b、n%r
c、n-r
d、r
2、使用栈判断括号串是否匹配，当读入左括号时应（ ），算法结束时，若栈（ ），则括号串是匹配的。
a、出栈、为空
b、出栈、非空
c、入栈、为空
d、入栈、非空
3.4 栈与递归随堂测验
1、一个递归算法必须包括（ ）。
a、递归部分
b、终结条件和递归部分
c、迭代部分
d、终结条件和迭代部分
2、将递归算法转换成等价的非递归算法，一定要借助栈。
3、解决同一问题，递归形式的算法的执行效率通常比非递归形式要高。
4、任何递归形式的算法，都可以转换为非递归的形式。
3.5 队列的定义及adt随堂测验
1、栈和队列的共同特点是（ ）。
a、只允许在端点处插入和删除元素
b、都是先进后出
c、都是先进先出
d、没有共同点
2、队列中允许插入元素的一端称为（ ），允许删除元素的一端称为（ ）。
a、队尾、队尾
b、队尾、队头
c、队头、队尾
d、队头、队头
3、下面的场景中，不符合队列操作特性的是？
a、食堂窗口取餐
b、发送到打印机的多个word文件
c、按退格键删除已输入的字符
d、高速etc收费车道
4、栈和队列都是限制了存取点的线性表。
单元测验
1、容量为m的循环队列q，队头和队尾位置分别是front和rear，则队列满的条件是（ ）？
a、q.rear==q.front 1
b、(q.rear 1)%m==q.front
c、q.rear 1==q.front
d、q.rear==q.front
2、容量为m的循环队列q，队头和队尾位置分别是front和rear，则队列长度是（ ）？
a、q.rear-q.front
b、q.front-q.rear
c、(q.rear-q.front m)％m
d、(q.front-q.rear m)％m
3、容量为m的循环队列q，队尾位置是rear，则入队时对rear的操作是（ ）？
a、q.rear=q.rear-1
b、q.rear=(q.rear-1)%m
c、q.rear=q.rear 1
d、q.rear=(q.rear 1)%m
4、容量为m的循环队列q，队头位置是front，则出队时对front的操作是（ ）？
a、q.front=q.front-1
b、q.front=(q.front-1)%m
c、q.front=q.front 1
d、q.front=(q.front 1)%m
5、循环队列的容量为6，rear和front分别是0和3，则从队列中删除3个元素，再加入2个元素后，rear和front分别是（ ）？
a、2和6
b、2和0
c、0和2
d、6和2
第4章 数组
4.1 数组的定义随堂测验
1、无论是几维数组，都可视为线性表。
2、通常不会对数组进行增删元素的操作。
3、与其他数据结构不同，数组通常只采用顺序存储结构。
4.2 数组的顺序实现随堂测验
1、所有高级语言的二维数组都是严格占据一段连续的存储空间。
2、随机存取是顺序存储才有的特性。
3、随机存取就是随机地读写一段连续内存中的某个位置。
4、访问一段连续存储空间中某个位置的时间复杂度与该段空间的大小和要访问的位置有关。
5、将随机存取中的“随机”理解为“任意”、“随意”、“直接”，更能体现随机存取的本质。
6、机械硬盘的工作原理决定了其不支持随机存取。
4.2 数组的顺序实现随堂测验
1、将m行n列的二维数组按行为主序存放，首个元素a00存于地址b（占d个字节），则元素aij的地址是（ ）？
a、b (i*m j)*d
b、b (i*n j)*d
c、b (j*m i)*d
d、b (j*n i)*d
2、将m行n列的二维数组按列为主序存放，首个元素a00存于地址b（占d个字节），则元素aij的地址是（ ）？
a、b (i*m j)*d
b、b (i*n j)*d
c、b (j*m i)*d
d、b (j*n i)*d
3、二维数组a[0..5][0..6]按列为主序存储在起始地址为1000的内存单元中，每个元素占5个字节，则元素a[5][5]的地址是（ ）。
a、1175
b、1180
c、1205
d、1210
4、设有数组a[i, j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址ba开始顺序存放，当用以列为主存放时，元素a[5，8]的存储首地址为（ ）。
a、ba 141
b、ba 180
c、ba 222
d、ba 225
5、如果计算机主板上插有2根及以上的内存条，则此计算机的内存空间是二维的。
6、无论是几维数组，都要转换为一维数组才能存放到内存中。
7、故意不用编程语言原生提供的数组语法来实现数组这种数据结构，通常是没有必要的。
8、所有高级语言的二维数组都是按行为主序存放的。
4.3 特殊矩阵的压缩存储随堂测验
1、10阶对称矩阵以行为主序存储，a[1][1]为首个元素，其地址为1，每个元素占1个字节，则a[8][5]的地址是（ ）。
a、40
b、13
c、33
d、18
2、将三对角矩阵a[1..100][1..100]按行为主序存入一维数组b[1..298]中，则元素a[66][65]在b中的位置为（ ）？
a、198
b、195
c、197
d、196
3、三对角线矩阵a[1..n][1..n]以行序为主顺序存储，其存储始址是b，每个元素占一个字节，则元素a[i][j] (1≤i, j≤n)的存储起始地址为（ ）。
a、b 2*j i-2
b、b 2*i j-2
c、b 2*j i-3
d、b 2*i j-3
单元测验
1、对m行n列的未经压缩（即以二维数组表示）的稀疏矩阵进行转置，时间复杂度是（ ）？
a、o(m)
b、o(n)
c、o(m*n)
d、o(max(m, n))
2、以三元组顺序表存储的稀疏矩阵（m行n列，非零元个数为t）的常规转置算法，时间复杂度是（ ）？
a、o(n*t)
b、o(m*t)
c、o(m*n)
d、o(m*n*t)
3、以三元组顺序表存储的稀疏矩阵（m行n列，非零元个数为t）的快速转置算法，时间复杂度是（ ）？
a、o(n*t)
b、o(n t)
c、o(m t)
d、o(m n t)
4、对稀疏矩阵进行压缩存储的目的是节省存储空间。
5、稀疏矩阵被压缩存储后，仍具有随机存取的特性。
第5章 树和二叉树
5.1 概念及术语随堂测验
1、下列不是树的是（ ）？
a、企业的部门组织架构
b、windows中的文件系统
c、书的目录
d、多个人之间的同学关系
2、下列关于树的说法正确的是（ ）？
a、parent经常译为“父母”、“双亲”，因此，树中某个结点的双亲结点可能有2个。
b、结点的度与树的度是同一个概念。
c、父节点是兄弟的那些结点互称为堂兄弟。
d、树是一种非线性结构。
3、树的定义本身就是递归的。
5.2 二叉树及其性质随堂测验
1、具有2048个结点的二叉树的最小高度是（ ）？
a、11
b、12
c、13
d、2048
2、下列有关二叉树的说法正确的是（ ）。
a、二叉树的度为2
b、一棵二叉树的度可以小于2
c、二叉树中至少有一个结点的度为2
d、二叉树中任何一个结点的度都为2
3、在一棵高度为k的满二叉树中，结点总数为（ ）。
a、2^(k-1)
b、2^k
c、2^k-1
d、向下取整(log2(k)) 1
4、一棵树高为k的完全二叉树至少有（ ）个结点。
a、2^k -1
b、2^(k-1) -1
c、2^(k-1)
d、2^k
5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。
a、9
b、11
c、15
d、不确定
5.2 二叉树及其性质随堂测验
1、设一棵三叉树中有50个度为0的结点，21个度为2的结点，则度为3的结点有（ ）个。
a、51
b、22
c、14
d、15
2、设完全二叉树的根结点序号为1，（ ）可判定序号分别为p和q的两个结点在同一层。
a、⌊log2(p)⌋=⌊log2(q)⌋
b、log2(p)=log2(q)
c、⌊log2(p)⌋ 1=⌊log2(q)⌋
d、⌊log2(p)⌋=⌊log2(q)⌋ 1
3、若根的层次为1，具有61个结点的完全二叉树的高度为（ ）。
a、5
b、6
c、7
d、8
4、高度为h的二叉树中只有度为0和2的结点，则此二叉树的结点数至少有（ ）个。
a、h 1
b、2*h 1
c、2*h
d、2*h-1
5.3 二叉树的存储随堂测验
1、以二叉链表存放一棵含有n个节点的二叉树，共有（ ）个空指针？
a、n 1
b、n-1
c、n
d、2*n
2、以二叉链表存放一棵含有n个节点的二叉树，共有（ ）个非空指针？
a、n 1
b、n-1
c、n
d、2*n
3、下列关于二叉树的说法中错误的是（ ）？
a、若二叉树使用顺序方式存储，则必须先将该二叉树补全为满二叉树。
b、若二叉树使用顺序方式存储，结点所在的下标对应着其在二叉树中的编号。
c、以顺序方式存储的二叉树可能会浪费大量空间。
d、若知道了二叉链表中根结点的指针，则整棵二叉树就唯一确定了。
5.4 二叉树的遍历及创建随堂测验
1、在二叉树的先序、中序和后序序列中，所有叶结点的先后顺序（ ）。
a、都不相同
b、完全相同
c、先序和中序相同，而后序不同
d、中序和后序相同，而先序不同
2、若二叉树的先序序列为abdecf，中序序列为dbeafc，则其后序序列为（ ）。
a、debafc
b、defbca
c、debcfa
d、debfca
3、若二叉树的中序序列为a b*c-d/e，后序序列为abc* de/-，则其先序序列为（ ）。
a、-a b*c/de
b、-a b*cd/e
c、- *abc/de
d、- a*bc/de
4、前序序列与中序序列相同的二叉树为（ ）。
a、根结点无左孩子的二叉树
b、所有结点只有右孩子的二叉树
c、只有根结点的二叉树
d、所有的结点只有左孩子的二叉树
5、前序序列和后序序列相同的二叉树为（ ）。
a、根结点无左孩子的二叉树
b、所有结点只有右孩子的二叉树
c、只有根结点的二叉树
d、所有的结点只有左孩子的二叉树
6、给定先序序列和后序序列，不能唯一确定二叉树。
7、一棵非空二叉树一定满足：某个结点若有左孩子，则其中序前驱一定没有右孩子。
5.5 线索二叉树随堂测验
1、在线索二叉树中，结点t没有左子树的充要条件是（ ）。
a、t->lchild==null
b、t->ltag==thread
c、t->ltag==thread && t->lchild==null
d、以上都不对
2、二叉树在线索后，仍不能有效求解的问题是（ ）？
a、先序线索二叉树中求先序后继
b、中序线索二叉树中求中序后继
c、中序线索二叉树中求中序前驱
d、后序线索二叉树中求后序后继
3、二叉树线索化后，任一结点均有指向其前驱和后继的线索。
4、中序线索树中，结点的前驱是其左子树上最左的结点。
5、中序线索树中，结点的后继是其右子树上最左的结点。
6、二叉树的中序序列中，最后一个结点是整棵树最右的那个结点。
7、二叉树经中序线索化后，不存在空指针。
5.6 树与森林随堂测验
1、以孩子-兄弟表示法表示的树，每个结点包含两个指针成员，分别指向当前结点的（ ）和（ ）。
a、第一个孩子、第一个兄弟
b、下一个孩子、下一个兄弟
c、第一个孩子、下一个兄弟
d、下一个孩子、第一个兄弟
2、如果bt是由树t转换而来的二叉树，则对t的后序遍历就是对bt的（ ）遍历。
a、先序
b、中序
c、后序
d、层序
3、利用二叉链表存储树，则根结点的右指针是（ ）。
a、指向最左孩子
b、指向最右孩子
c、空
d、非空
4、下列哪一个不是树的存储形式？
a、双亲表示法
b、孩子链表表示法
c、孩子兄弟表示法
d、顺序存储表示法
5、一棵树必须转换成二叉树后才能存储。
6、树的叶子数一定等于其对应的二叉树的叶子数。
7、对树进行先序遍历，等价于以先序遍历该树对应的二叉树。
8、对树进行后序遍历，等价于以后序遍历该树对应的二叉树。
单元测验
1、关于哈夫曼树的叙述正确的是（ ）。
a、树的左分支必须编码成0，右分支必须编码成1
b、权值较大的结点对应的哈夫曼编码通常较短
c、对于给定的若干结点，哈夫曼树总是唯一的
d、给定m个叶结点，构造的哈夫曼树共包含2m 1个结点
2、由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的wpl为（ ）。
a、23
b、37
c、44
d、46
3、根据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。
a、111, 110, 10, 01, 00
b、000, 001, 010, 011, 1
c、100, 11, 10, 00, 01
d、001, 000, 01, 11, 10
4、哈夫曼树是带权路径长度最短的树，路径上权值较小的结点通常离根（ ）。
a、不确定
b、较近
c、较远
d、不远不近
5、设给定权值的叶子总数有n个，其哈夫曼树的结点总数为（ ）。
a、不确定
b、2n
c、2n 1
d、2n-1
6、哈夫曼编码是前缀编码。
7、在哈夫曼树中，权值相同的叶结点一定在同一层。
第6章 图
6.1 概念和术语随堂测验
1、无向图中一个顶点的度是指图中（ ）。
a、通过该顶点的简单路径数
b、通过该顶点的环数
c、与该顶点相邻接的顶点数
d、与该顶点连通的顶点数
2、无向图中所有顶点的度数之和等于所有边数（ ）倍，有向图中所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
a、2，1
b、1，2
c、1/2，1
d、1，1/2
3、下列关于图和树的说法，错误的是（ ）？
a、树可以看作图的特例
b、树中有一个特殊的元素(根)，而图中每个元素的“地位”是一样的
c、图和树中的边沿任意轴旋转后，各元素间的逻辑关系保持不变
d、树中任意两个元素间有唯一的简单路径，而图中任意两个元素间可能有零或多条简单路径
4、有向图中有一条边，则v称为弧头。
5、n个顶点的有向完全图有n(n-1)条边。
6、有向图中，顶点的入度是以v为弧尾的边的数量。
6.2 存储与实现随堂测验
1、若含有n个顶点的有向图的边数远小于n*(n-1)，且要方便地求得某个顶点的出度，则采用（ ）存储结构较为合适。
a、邻接矩阵
b、逆邻接表
c、邻接表
d、前述3者都一样
2、下列哪一种图的邻接矩阵是对称矩阵？
a、有向图
b、无向图
c、aov网
d、以上均是
3、采用邻接表表示有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的表结点数为（ ）。
a、d1
b、d2
c、d1-d2
d、d1 d2
4、无向图的邻接矩阵一定是对称矩阵。
5、若图的邻接矩阵不是对称矩阵，则该图一定是有向图。
6、若图的邻接矩阵是对称矩阵，则该图一定是无向图。
7、一个有向图的邻接表和逆邻接表中结点的个数可能不相等。
6.3 遍历随堂测验
1、图的深度优先搜索类似于树的（ ）遍历，图的广度优先搜索类似于树的（ ）遍历。
a、先序，层序
b、层序，先序
c、中序、层序
d、先序，中序
2、下列关于图的遍历的说法，错误的是（ ）。
a、图的遍历是从给定的起始顶点出发，将每一个顶点访问且仅访问一次
b、深度优先搜索可以不用递归方式来实现
c、从给定顶点开始，深度和广度优先搜索可能无法访问到其他某些顶点
d、深度优先搜索会先找到“最近解”
3、无向图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)}，对该图进行深度优先搜索，得到的顶点序列是（ ）。
a、a,b,e,c,d,f
b、a,c,f,e,b,d
c、a,e,b,c,f,d
d、a,e,d,f,c,b
4、深度优先搜索只适用于以邻接矩阵存储的图。
5、广度优先搜索每访问一个顶点后，都要将其放到栈中。
6.4 最小生成树随堂测验
1、n个顶点的无向连通图，至少有（ ）条边，至多有（ ）条边。
a、n，n*(n-1)
b、n-1，n*(n-1)/2
c、n-1，n*(n-1)
d、n，n*(n-1)/2
2、n个顶点的有向连通图，至少有（ ）条边，至多有（ ）条边。
a、n，n*(n-1)
b、n-1，n*(n-1)/2
c、n-1，n*(n-1)
d、n，n*(n-1)/2
3、n个顶点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
a、0，n
b、1，n-1
c、1，n
d、0，n-1
4、有28条边的非连通无向图，至少有（ ）个顶点。
a、6
b、7
c、8
d、9
5、连通分量是图的最小连通子图。
6、生成树是连通图的最大连通子图。
6.4 最小生成树随堂测验
1、求稠密图的最小生成树， 最好用prim算法。
2、连通图上各边权值均不相同，则该图的最小生成树一定是唯一的。
3、从有向图g中的给定起始顶点v0出发，若能到达其他任一顶点，则g是强连通图。
4、n个顶点的无向图，若边数大于2n，则该图必是连通图。
6.5 拓扑排序随堂测验
1、对有向图g进行拓扑排序的目的不是（ ）。
a、判断g是否包含环
b、查看g中顶点所代表的活动的先后关系
c、检查g表示的工序图是否合理
d、将g中所有顶点按大小关系排序
2、无向图g=(v,e)，其中v={a,b,c,d,e}，e={,,,,,}，对该图进行拓扑排序，下面哪一个不是其拓朴序列？
a、a,d,c,b,e
b、d,a,b,c,e
c、a,b,d,c,e
d、a,b,c,e,d
3、在有向图g的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是（ ）。
a、g中有一条从vj到vi的路径
b、g中有一条从vi到vj的路径
c、g中有弧
d、g中没有弧
4、若有向图的邻接矩阵中，主对角线以下元素均为0， 则该图一定无环。
5、拓扑排序算法中，必须使用队列来存放入度为0的顶点。
单元测验
1、对于下图，以顶点1为起始顶点，使用dijkstra算法依次找到的多条最短路径所到达的终点分别是（ ）？
a、3，4，6，2，5
b、2，3，4，5，6
c、6，5，4，3，2
d、4，2，6，3，5
第7章 查找
7.1 概念和术语随堂测验
1、查找表可分为（ ）？
a、定长查找表、变长查找表
b、静态查找表、动态查找表
c、简单查找表、复杂查找表
d、数值型查找表、非数值型查找表
2、下列关于关键字的说法中正确的是（ ）？
a、学生的姓名可以作为主关键字
b、只要某个数据项是可比较的，其就能作为关键字
c、主关键字可能对应多个数据元素
d、关键字的具体数据类型会影响采用的查找算法
3、除非特别说明，谈到平均查找长度，通常暗含了等概率和查找成功这两个前提。
7.2 静态查找表随堂测验
1、在长度为n的查找表中做顺序查找，查找成功时的平均查找长度是（ ）。
a、(n 1)/2
b、n/2
c、n 1
d、n
2、采用折半查找，在长度为18的有序顺序表（下标从1开始）中查找第3个关键字，依次比较的关键字的下标是（ ）。
a、1,2,3
b、9,5,2,3
c、9,5,3
d、9,4,2,3
3、下面关于折半查找（或二分查找）的叙述正确的是（ ）。
a、表必须有序，表可以顺序方式存储，也可以链表方式存储
b、表必须有序，且表只能以顺序方式存储
c、表必须有序且表中数据元素的类型必须是整型，实型或字符型
d、表必须有序，而且只能从小到大排列
4、在n个关键字构成的有序顺序表中进行折半查找，最大比较次数是（ ）。
a、向下取整(log2(n))
b、向上取整(log2(n))
c、向下取整(log2(n)) 1
d、n
5、在长度为n的查找表中做顺序查找，查找失败时的平均查找长度是（ ）。
a、(n 1)/2
b、n/2
c、n 1
d、n
6、索引顺序表的数据组织方式是（ ）？
a、数据分成若干块，每块内数据有序
b、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
c、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
d、数据分成若干块，每块（除最后一块外）的数据个数相同
7、顺序查找仅适用于顺序存储。
8、折半查找不适用于链式存储。
9、分块查找同时使用了顺序查找和折半查找，故一般而言，其性能介于顺序查找和折半查找之间。
10、折半查找的查找性能一定高于顺序查找。
7.3 二叉排序树随堂测验
1、将序列{50,72,43,85,75,20,35,45,65,30}逐个插入初始为空的二叉排序树后，查找30要进行（ ）次比较。
a、4
b、5
c、6
d、7
2、对二叉排序树进行（）遍历将得到递增序列。
a、先序
b、中序
c、后序
d、层序
3、以二叉链表存储二叉排序树，关键字最大的结点（ ）。
a、左指针一定为空
b、右指针一定为空
c、左右指针均为空
d、左右指针均不空
4、当bst每层仅有一个结点时，其查找算法退化成（ ），asl上升为（ ）。
a、顺序查找、(n 1)/2
b、顺序查找、n
c、折半查找、(n 1)/2
d、折半查找、n
7.4 平衡二叉树随堂测验
1、高度为5的avl树至少有（ ）个结点。
a、10
b、12
c、15
d、17
2、平衡二叉树中根结点的平衡因子是1，若新结点插入到根的左子树上，则必定需要调整。
3、将长度为n的元素序列组织成avl树时，无论序列如何排列，总能保证树的asl为log2(n)的量级。
单元测验
1、采用哈希函数h(k)=k%7，依次存放关键字{38,25,74,63,52,48}到a[0..6]中，若采用线性探测法解决冲突，则该哈希表在查找成功时的平均查找长度为（ ）。
a、1.5
b、1.7
c、2
d、2.3
2、下列以链地址法处理哈希表冲突的叙述中，错误的是（ ）。
a、此时的哈希表整体上是一个数组
b、此时的哈希表整体上是一个链表
c、此时的哈希表中可能存在空链表
d、位于同一个横向链表中的结点的hash地址都相同
3、将10个元素存放到容量为100000的哈希表中，则（ ）产生冲突。
a、一定会
b、一定不会
c、仍可能会
d、至少一次
4、通过（ ）法构造的哈希函数一定不会发生冲突。
a、除留余数
b、平方取中
c、直接定址
d、以上均可能发生冲突
5、k个关键字互为同义词，采用线性探测法处理冲突，则至少要进行（ ）次探测？
a、k(k-1)/2
b、k
c、k-1
d、k(k 1)/2
6、下面关于哈希函数的说法中正确的是（ ）。
a、哈希函数越复杂越好，因为这样随机性好，冲突可能性低
b、除留余数法是所有哈希函数中最好的
c、直接定址法是所有哈希函数中最好的
d、不存在特别好与坏的哈希函数， 要视具体情况而定
7、在哈希表中查找元素时，元素的存放地址是算出来的，故无需比较元素。
8、hash表的平均查找长度与处理冲突的方法无关。
第8章 排序
8.1 概念随堂测验
1、通常将元素的比较和移动操作视为排序算法的基本步骤。
2、某个序列经排序算法a排序后，相同关键字的先后位置没有变化，则排序算法a是稳定的。
3、某个序列经排序算法a排序后，相同关键字的先后位置发生了变化，则排序算法a是不稳定的。
4、稳定的排序算法一定能修改成不稳定的。
5、不稳定的排序算法或许能修改成稳定的。
8.2 插入排序随堂测验
1、对关键字序列{15,9,7,8,20,-1,4}进行希尔排序，第一趟排序结果的首个关键字是15，则该趟采用的增量是（ ）。
a、1
b、2
c、3
d、4
2、直接插入排序中，监视哨的作用是暂存待插入的元素以及（ ）？
a、减少元素的比较次数
b、减少元素的移动次数
c、避免在元素比较过程中检查当前位置是否越界
d、减少临时空间的使用量
3、若待排序列越杂乱无序，则shell排序的效率就越低。
4、shell排序的最后一趟就是直接插入排序。
5、若选取的增量序列是{8,4,2,1}，shell排序依然能正确工作。
6、对于同一待排序列，选取的增量序列不同，希尔排序的性能也不同。
8.3 交换排序随堂测验
1、对n个元素进行冒泡排序，第一趟共要比较（ ）对元素。
a、n-1
b、n/2
c、n 1
d、n
2、快速排序在最好和最坏情况下的空间复杂度分别是（ ）。
a、o(1og2(n))和o(1og2(n))
b、o(n)和o(1og2(n))
c、o(1og2(n))和o(n)
d、o(n)和o(n)
3、快速排序是一种（ ）。
a、插入排序
b、交换排序
c、归并排序
d、选择排序
4、快速排序在最坏情况下的时间复杂度是（ ），此时其退化成了（ ）。
a、o(n^2)，冒泡排序
b、o(n^2)，简单选择排序
c、o(n*log2(n))，冒泡排序
d、o(n*log2(n))，归并排序
5、关键字序列{46,79,56,38,40,84}经快速排序的第一趟划分之后（以46为基准），得到的序列是（ ）。
a、38,40,46,56,79,84
b、40,38,46,79,56,84
c、40,38,46,56,79,84
d、40,38,46,84,56,79
6、关键字序列为{20，15，14，18，21，36，40，10}，则以20为基准的一趟快速排序结束后的结果为（ ）。
a、10，15，14，18，20，36，40，21
b、10，15，14，18，20，40，36，21
c、10，15，14，20，18，40，36，21
d、15，10，14，18，20，36，40，21
7、一般而言，快速排序是所有排序算法中最快的，并且所需的额外空间也最少。
8、待排序列越有序，快速排序越慢，简单选择排序则恰好相反。
8.4 选择排序随堂测验
1、关键字序列（ ）是一个堆。
a、20,76,35,23,80,54
b、20,54,23,80,35,76
c、80,23,35,76,20,54
d、20,35,23,80,54,76
2、堆排序中一趟筛选的时间复杂度是（ ）。
a、o(n*log2(n))
b、o(log2(n))
c、o(n)
d、o(1)
3、对n个元素建立初始堆时，首个要调整的结点的编号是（ ）？
a、n
b、向下取整(n/2)
c、向上取整(n/2)
d、1
4、为关键字序列{45,80,55,40,42,85}建立的初始大顶堆是（ ）。
a、{ 80, 45, 50, 40, 42, 85}
b、{85, 80, 55, 40, 42, 45}
c、{ 85, 80, 55, 45, 42, 40}
d、{85, 55, 80, 42, 45, 40}
5、对n个元素进行简单选择排序，一定会执行n-1趟。
6、简单选择排序的最好和最坏时间复杂度是一样的。
7、若要排为正序，需要建立小顶堆。
单元测验
1、每趟排序选取一个元素，将所有不大于该元素的元素放在其左边，将所有不小于该元素的元素放在其右边，此时的排序算法是（ ）。
a、插入排序
b、shell排序
c、归并排序
d、快速排序
2、每趟排序将无序子序列中的一个元素插入到有序子序列中的合适位置，使得有序子序列的长度增加1，此时的排序算法是（ ）。
a、归并排序
b、直接插入排序
c、快速排序
d、shell排序
3、最好和最坏情况下的时间复杂度均为o(n*log2(n))且稳定的排序算法是（ ）。
a、插入排序
b、快速排序
c、堆排序
d、归并排序
4、在第一趟排序之后，一定能将最大或最小者放在其最终位置的排序算法是（ ）。
a、冒泡排序
b、插入排序
c、快速排序
d、归并排序
5、稳定的排序算法是（ ）。
a、简单选择排序
b、直接插入排序
c、堆排序
d、快速排序
6、不稳定的排序算法是（ ）。
a、直接插入排序
b、冒泡排序
c、shell排序
d、归并排序
7、下列排序算法中，其中（ ）是稳定的。
a、堆排序，冒泡排序
b、快速排序，堆排序
c、简单选择排序，归并排序
d、归并排序， 冒泡排序
8、以下时间复杂度不是o(n*log2(n))的排序方法是（ ）？
a、堆排序
b、直接插入排序
c、二路归并排序
d、快速排序
9、比较次数与待排序列的初始状态无关的排序方法是（ ）。
a、直接插入排序
b、冒泡排序
c、快速排序
d、简单选择排序
10、需在o(n*log2(n))的时间内完成对数组排序，且要求排序是稳定的，则可选择（ ）？
a、快速排序
b、堆排序
c、直接插入排序
d、归并排序
11、获得1000种商品中单价最贵的前5种商品，采用（ ）最合适。
a、堆排序
b、shell排序
c、简单选择排序
d、快速排序
12、在待排序序列基本有序时，效率最高的是（ ）？
a、直接插入排序
b、快速排序
c、简单选择排序
d、归并排序
期末考试
数据结构期末考试
1、设某数据结构ds=(d,r)，d={1,2,3,4,5,6,7,8,9}，r={<1,2>,<1,3>,<1,4>,<2,5>,<2,6>,<3,7>}，则ds是（ ）。
a、线性结构
b、树型结构
c、物理结构
d、图型结构
2、在实际应用中，决定选取何种物理结构时，一般不考虑（ ）。
a、数据元素要支持的操作
b、数据元素的总个数
c、数据元素的具体值
d、所用的编程语言实现该种结构是否方便
3、设n为偶数，下列伪码中，注释所在行的总执行次数是（ ）。 for i = 1 to n do for j = 2*i to n do m = m 1; // 此行的总执行次数
a、n^2
b、(n^2)/4
c、(n^2)/2
d、不确定
4、在一个长度为n的顺序表中第i个元素（1 <= i <= n 1）之前插入一个元素，然后（前面的插入操作完成后）再删除第i个（1 <= i <= n 1）元素, 需向前移动（ ）个元素。
a、i
b、n-i
c、n-i 1
d、n-i-1
5、删除单链表中指针p所指结点的语句序列为（ ）。
a、q=p->next; p->data=q->data; p->next=q->next; free(q);
b、q=p->next; q->data=p->data; p->next=q->next; free(q);
c、q=p->next; p->next=q->next; free(q);
d、q=p->next; p->data=q->data; free(q);
6、6个元素按3，2，1，4，5，6 的顺序进栈（2次入栈间可能有零至多次出栈），下列哪个不是合法的出栈序列？
a、2，1，4，3，6，5
b、1，2，4，6，5，3
c、4，1，3，2，5，6
d、5，4，1，6，2，3
7、下列关于递归错误的说法是（ ）。
a、递归函数可以没有返回值
b、递归算法一定有终结条件
c、递归算法执行时会在内存中自动维护一个工作栈
d、递归算法一定包含循环结构
8、容量为m的循环队列q，队头和队尾位置分别是front和rear，则队列长度是（ ）？
a、q.rear-q.front
b、q.front-q.rear
c、(q.rear-q.front m)％m
d、(q.front-q.rear m)％m
9、循环队列的容量为6，rear和front分别是0和3，则从队列中删除3个元素，再加入2个元素后，rear和front分别是（ ）？
a、2和6
b、2和0
c、0和2
d、6和2
10、二维数组a[0..5][0..6]按列为主序存储在起始地址为1000的内存单元中，每个元素占5个字节，则元素a[5][5]的地址是（ ）。
a、1175
b、1180
c、1205
d、1210
11、将三对角矩阵a[1..100][1..100]按行为主序存入一维数组b[1..298]中，则元素a[66][65]在b中的位置为（ ）？
a、198
b、195
c、197
d、196
12、设一棵三叉树中有50个度为0的结点，21个度为2的结点，则度为3的结点有（ ）个。
a、51
b、22
c、14
d、15
13、设完全二叉树的根结点序号为1，（ ）可判定序号分别为p和q的两个结点在同一层。
a、⌊log2(p)⌋=⌊log2(q)⌋
b、log2(p)=log2(q)
c、⌊log2(p)⌋ 1=⌊log2(q)⌋
d、⌊log2(p)⌋=⌊log2(q)⌋ 1
14、高度为h的二叉树中只有度为0和2的结点，则此二叉树的结点数至少有（ ）个。
a、h 1
b、2*h 1
c、2*h
d、2*h-1
15、在二叉树的先序、中序和后序序列中，所有叶结点的先后顺序（ ）。
a、都不相同
b、完全相同
c、先序和中序相同，而后序不同
d、中序和后序相同，而先序不同
16、若二叉树的中序序列为a b*c-d/e，后序序列为abc* de/-，则其先序序列为（ ）。
a、-a b*c/de
b、-a b*cd/e
c、- *abc/de
d、- a*bc/de
17、前序序列与中序序列相同的二叉树为（ ）。
a、根结点无左孩子的二叉树
b、所有结点只有右孩子的二叉树
c、只有根结点的二叉树
d、所有的结点只有左孩子的二叉树
18、根据使用频率，为5个字符设计的哈夫曼编码不可能是（ ）。
a、111, 110, 10, 01, 00
b、000, 001, 010, 011, 1
c、100, 11, 10, 00, 01
d、001, 000, 01, 11, 10
19、n个顶点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
a、0，n
b、1，n-1
c、1，n
d、0，n-1
20、在有向图g的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是（ ）。
a、g中有一条从vj到vi的路径
b、g中有一条从vi到vj的路径
c、g中有弧
d、g中没有弧
21、采用折半查找，在长度为18的有序顺序表（下标从1开始）中查找第3个关键字，依次比较的关键字的下标是（ ）。
a、1,2,3
b、9,5,2,3
c、9,5,3
d、9,4,2,3
22、以二叉链表存储二叉排序树，关键字最大的结点（ ）。
a、左指针一定为空
b、右指针一定为空
c、左右指针均为空
d、左右指针均不空
23、采用哈希函数h(k)=k%7，依次存放关键字{38,25,74,63,52,48}到a[0..6]中，若采用线性探测法解决冲突，则该哈希表在查找成功时的平均查找长度为（ ）。
a、插入排序
b、shell排序
c、归并排序
d、快速排序
24、最好和最坏情况下的时间复杂度均为o(n*log2(n))且稳定的排序算法是（ ）。
a、插入排序
b、快速排序
c、堆排序
d、归并排序
25、稳定的排序算法是（ ）。
a、简单选择排序
b、直接插入排序
c、堆排序
d、快速排序
26、关键字序列（ ）是一个堆。
a、20,76,35,23,80,54
b、20,54,23,80,35,76
c、80,23,35,76,20,54
d、20,35,23,80,54,76
27、获得1000种商品中单价最贵的前5种商品，采用（ ）最合适。
a、堆排序
b、shell排序
c、简单选择排序
d、快速排序
28、关键字序列为{20，15，14，18，21，36，40，10}，则以20为基准的一趟快速排序结束后的结果为（ ）。
a、10，15，14，18，20，36，40，21
b、10，15，14，18，20，40，36，21
c、10，15，14，20，18，40，36，21
d、15，10，14，18，20，36，40，21
29、对关键字序列{15,9,7,8,20,-1,4}进行希尔排序，第一趟排序结果的首个关键字是15，则该趟采用的增量是（ ）。
a、1
b、2
c、3
d、4
30、下面的哪个例子不具有栈的特性？
a、多个人依次过独木桥时，最前面的人发现前方有危险，需要退回到入口
b、弹夹的装填与发射
c、一条单向车道上，最前面的车抛锚了，需要清空道路等待救援
d、多辆车依次通过高速收费站的某个窗口
31、容量为m的循环队列q，队头位置是front，则出队时对front的操作是（ ）？
a、q.front=q.front-1
b、q.front=(q.front-1)%m
c、q.front=q.front 1
d、q.front=(q.front 1)%m
32、设有数组a[i, j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址ba开始顺序存放，当用以列为主存放时，元素a[5，8]的存储首地址为（ ）。
a、ba 141
b、ba 180
c、ba 222
d、ba 225
33、一棵树高为k的完全二叉树至少有（ ）个结点。
a、2^k -1
b、2^(k-1) -1
c、2^(k-1)
d、2^k
34、下列哪一个不是树的存储形式？
a、双亲表示法
b、孩子链表表示法
c、孩子兄弟表示法
d、顺序存储表示法
35、设给定权值的叶子总数有n个，其哈夫曼树的结点总数为（ ）。
a、不确定
b、2n
c、2n 1
d、2n-1
36、下列关于图的遍历的说法，错误的是（ ）。
a、图的遍历是从给定的起始顶点出发，将每一个顶点访问且仅访问一次
b、深度优先搜索可以不用递归方式来实现
c、从给定顶点开始，深度和广度优先搜索可能无法访问到其他某些顶点
d、深度优先搜索会先找到“最近解”
37、下列以链地址法处理哈希表冲突的叙述中，错误的是（ ）。
a、此时的哈希表整体上是一个数组
b、此时的哈希表整体上是一个链表
c、此时的哈希表中可能存在空链表
d、位于同一个横向链表中的结点的hash地址都相同
38、以三元组顺序表存储的稀疏矩阵（m行n列，非零元个数为t）的快速转置算法，时间复杂度是（ ）？
a、o(n*t)
b、o(n t)
c、o(m t)
d、o(m n t)
39、比较次数与待排序列的初始状态无关的排序方法是（ ）。
a、直接插入排序
b、冒泡排序
c、快速排序
d、简单选择排序
40、在n个关键字构成的有序顺序表中进行折半查找，最大比较次数是（ ）。
a、向下取整(log2(n))
b、向上取整(log2(n))
c、向下取整(log2(n)) 1
d、n
41、用计算机求解的问题可以分为（ ）？
a、简单型问题、复杂型问题
b、文本型问题、二进制型问题
c、数值型问题、非数值型问题
d、基本型问题、结构型问题
42、建模的本质包括（ ）。
a、从问题中抽取出关键对象
b、找出问题中关键对象之间的关系
c、以合适的语言(或符号)描述问题中的关键对象以及它们之间的关系
d、以上三者均是
43、关于下列代码段，错误的说法是（ ）? typedef struct { elemtype *elem; int length; int size; } sqlist;
a、可以把elem当做数组名来用
b、size是表容量，length是表长
c、size一定大于或等于length
d、sqlist是一个结构体变量名
44、下面关于链表l的说法正确的是（ ）？
a、l代表链表在内存中的整体结构
b、l是一个指针数组，其各元素分别指向链表的每个元素结点
c、l仅是指向链表头结点的指针
d、l是链表的头结点
45、抽象数据类型从________结构的角度来描述________、________及________。
a、逻辑、元素、关系、操作
b、逻辑、元素、关系、类型
c、物理、元素、关系、操作
d、物理、元素、关系、类型
46、下列关于二叉树的说法中错误的是（ ）？
a、若二叉树使用顺序方式存储，则必须先将该二叉树补全为满二叉树。
b、若二叉树使用顺序方式存储，结点所在的下标对应着其在二叉树中的编号。
c、以顺序方式存储的二叉树可能会浪费大量空间。
d、若知道了二叉链表中根结点的指针，则整棵二叉树就唯一确定了。
47、二叉树在线索后，仍不能有效求解的问题是（ ）？
a、先序线索二叉树中求先序后继
b、中序线索二叉树中求中序后继
c、中序线索二叉树中求中序前驱
d、后序线索二叉树中求后序后继
48、下列关于图和树的说法，错误的是（ ）？
a、树可以看作图的特例
b、树中有一个特殊的元素(根)，而图中每个元素的“地位”是一样的
c、图和树中的边沿任意轴旋转后，各元素间的逻辑关系保持不变
d、树中任意两个元素间有唯一的简单路径，而图中任意两个元素间可能有零或多条简单路径
49、无向图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)}，对该图进行深度优先搜索，得到的顶点序列是（ ）。
a、a,b,e,c,d,f
b、a,c,f,e,b,d
c、a,e,b,c,f,d
d、a,e,d,f,c,b
50、在长度为n的查找表中做顺序查找，查找失败时的平均查找长度是（ ）。
a、(n 1)/2
b、n/2
c、n 1
d、n
51、索引顺序表的数据组织方式是（ ）？
a、数据分成若干块，每块内数据有序
b、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
c、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
d、数据分成若干块，每块（除最后一块外）的数据个数相同
52、k个关键字互为同义词，采用线性探测法处理冲突，则至少要进行（ ）次探测？
a、k(k-1)/2
b、k
c、k-1
d、k(k 1)/2
53、当bst每层仅有一个结点时，其查找算法退化成（ ），asl上升为（ ）。
a、顺序查找、(n 1)/2
b、顺序查找、n
c、折半查找、(n 1)/2
d、折半查找、n
54、对n个元素建立初始堆时，首个要调整的结点的编号是（ ）？
a、n
b、向下取整(n/2)
c、向上取整(n/2)
d、1
55、为关键字序列{45,80,55,40,42,85}建立的初始大顶堆是（ ）。
a、{ 80, 45, 50, 40, 42, 85}
b、{85, 80, 55, 40, 42, 45}
c、{ 85, 80, 55, 45, 42, 40}
d、{85, 55, 80, 42, 45, 40}
56、在待排序序列基本有序时，效率最高的是（ ）？
a、直接插入排序
b、快速排序
c、简单选择排序
d、归并排序
57、直接插入排序中，监视哨的作用是暂存待插入的元素以及（ ）？
a、减少元素的比较次数
b、减少元素的移动次数
c、避免在元素比较过程中检查当前位置是否越界
d、减少临时空间的使用量
58、对于顺序栈和链栈， 它们的入栈和出栈操作的时间复杂度均为（ ）。
a、o(n)
b、o(n^2)
c、o(1)
d、o(log2(n))
59、用计算机求解问题的一般步骤
a、分析问题、设计算法、编程/调试、得到结果
b、分析问题、建立数学模型、编程/调试、得到结果
c、分析问题、设计算法、建立数学模型、编程/调试、得到结果
d、分析问题、建立数学模型、设计算法、编程/调试、得到结果
60、若一维数组的首个元素是a0，每个元素占d个字节，则其随机存取公式是（ ）?
a、loc(ai) = loc(a0) (i 1)*d
b、loc(ai) = loc(a0) i*d
c、loc(ai) = loc(a0) (i-1)*d
d、loc(ai) = loc(a0) i
61、使用栈将十进制数n转换为r进制数时，每次入栈的是（ ）？
a、n/r
b、n%r
c、n-r
d、r
62、下面的场景中，不符合队列操作特性的是？
a、食堂窗口取餐
b、发送到打印机的多个word文件
c、按退格键删除已输入的字符
d、高速etc收费车道
63、将m行n列的二维数组按行为主序存放，首个元素a00存于地址b（占d个字节），则元素aij的地址是（ ）？
a、b (i*m j)*d
b、b (i*n j)*d
c、b (j*m i)*d
d、b (j*n i)*d
64、对于下图，以顶点1为起始顶点，使用dijkstra算法依次找到的多条最短路径所到达的终点分别是（ ）？
a、3，4，6，2，5
b、2，3，4，5，6
c、6，5，4，3，2
d、4，2，6，3，5
65、将递归算法转换成等价的非递归算法，一定要借助栈。
66、所有高级语言的二维数组都是按行为主序存放的。
67、顺序查找仅适用于顺序存储。
68、折半查找不适用于链式存储。
69、栈顶元素和栈底元素有可能是同一个元素。
70、栈底元素不可能被删除。
71、稀疏矩阵被压缩存储后，仍具有随机存取的特性。
72、若图的邻接矩阵不是对称矩阵，则该图一定是有向图。
73、连通分量是图的最小连通子图。
74、c 的引用参数是对函数的实参而言的。
75、对于c语言中的数组，&a[i]等价于a i，后者中的i是指字节数。
76、高级语言通常不关心一个占了多个字节的数据元素的非首字节。
77、对于单链表，要得到某个结点的值，只需要知道该结点的指针即可，因此，单链表也支持随机存取。
78、若使用的编程语言不支持指针语法，则无法用该语言实现链表。
79、l指向以头插法创建的单链表的头结点，对l进行遍历得到的序列与创建链表时的输入序列一致。
80、稀疏多项式适合以链表来存储。
81、在开发实际项目时，应优先考虑自己来实现常见的数据结构。
82、任何递归形式的算法，都可以转换为非递归的形式。
83、无论是几维数组，都可视为线性表。
84、随机存取是顺序存储才有的特性。
85、将随机存取中的“随机”理解为“任意”、“随意”、“直接”，更能体现随机存取的本质。
86、一棵非空二叉树一定满足：某个结点若有左孩子，则其中序前驱一定没有右孩子。
87、给定先序序列和后序序列，不能唯一确定二叉树。
88、二叉树经中序线索化后，不存在空指针。
89、中序线索树中，结点的后继是其右子树上最左的结点。
90、二叉树的中序序列中，最后一个结点是整棵树最右的那个结点。
91、对树进行后序遍历，等价于以后序遍历该树对应的二叉树。
92、在哈夫曼树中，权值相同的叶结点一定在同一层。
93、广度优先搜索每访问一个顶点后，都要将其放到栈中。
94、深度优先搜索只适用于以邻接矩阵存储的图。
95、求稠密图的最小生成树， 最好用prim算法。
96、连通图上各边权值均不相同，则该图的最小生成树一定是唯一的。
97、从有向图g中的给定起始顶点v0出发，若能到达其他任一顶点，则g是强连通图。
98、n个顶点的无向图，若边数大于2n，则该图必是连通图。
99、若有向图的邻接矩阵中，主对角线以下元素均为0， 则该图一定无环。
100、拓扑排序算法中，必须使用队列来存放入度为0的顶点。
101、在哈希表中查找元素时，元素的存放地址是算出来的，故无需比较元素。
102、将长度为n的元素序列组织成avl树时，无论序列如何排列，总能保证树的asl为log2(n)的量级。
103、平衡二叉树中根结点的平衡因子是1，若新结点插入到根的左子树上，则必定需要调整。
104、hash表的平均查找长度与处理冲突的方法无关。
105、对n个元素进行简单选择排序，一定会执行n-1趟。
106、简单选择排序的最好和最坏时间复杂度是一样的。
107、若要排为正序，需要建立小顶堆。
108、某个序列经排序算法a排序后，相同关键字的先后位置没有变化，则排序算法a是稳定的。
109、某个序列经排序算法a排序后，相同关键字的先后位置发生了变化，则排序算法a是不稳定的。
110、稳定的排序算法一定能修改成不稳定的。
111、不稳定的排序算法或许能修改成稳定的。
112、若待排序列越杂乱无序，则shell排序的效率就越低。
113、待排序列越有序，快速排序越慢，简单选择排序则恰好相反。
114、shell排序的最后一趟就是直接插入排序。
115、若选取的增量序列是{8,4,2,1}，shell排序依然能正确工作。
116、对于同一待排序列，选取的增量序列不同，希尔排序的性能也不同。
猜你喜欢
- 2023-02-27 01:29
- 2023-02-27 01:15
- 2023-02-27 01:00
- 2023-02-27 00:36食品营养与健康-超星尔雅-学习通-题库零氪超星学习通慕课题库
- 2023-02-26 23:42
- 2023-02-26 23:37
- 2023-02-26 23:20
- 2023-02-26 23:06
- 2023-02-26 22:55
- 2023-02-26 22:52