《东北大学22春“计算机科学与技术”《数据结构Ⅱ》作业考核易错、难点汇编⑥（带答案）试卷号：15》由会员分享，可在线阅读，更多相关《东北大学22春“计算机科学与技术”《数据结构Ⅱ》作业考核易错、难点汇编⑥（带答案）试卷号：15（14页珍藏版）》请在装配图网上搜索。
1、书山有路勤为径，学海无涯苦作舟！ 住在富人区的她东北大学22春“计算机科学与技术”数据结构作业考核易错、难点汇编（带答案）一.综合考核(共45题)1.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为()。A.7B.8C.9D.10参考答案：D2.当采用分快查找时，数据的组织方式为A.数据分成若干块，每块(除最后一块外)中数据个数需相同B.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序D.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块参考答案：D3.下面关于线性表的叙述中，错误的是A.
2、线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，便于插入和删除操作D.线性表采用链接存储，不必占用一片连续的存储单元参考答案：B4.采用ISAM或VSAM组织的文件是()。A.索引非顺序文件B.顺序文件C.索引顺序文件D.散列文件参考答案：C5.n个顶点的强连通图中至少含有()。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边参考答案：B6.下述哪一条是顺序存储结构的优点A.插入运算方便B.存储密度大C.可方便地用于各种逻辑结构的存储表示D.删除运算方便参考答案：B7.设顺序存储的线性表共有
3、123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为()。A.21B.23C.41D.62参考答案：C8.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为()。A.4，4，3B.4，3，3C.3，4，4D.3，3，4参考答案：B9.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A.O(n2)B.O(n)C.O(1)D.O(0)参考答案：B10.在按层次遍历二叉树的算
4、法中，需要借助的辅助数据结构是A.队列B.线性表C.栈D.有序表参考答案：A11.下面说法错误的是()。 (1)算法原地工作的含义是指不需要任何额外的辅助空间; (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法; (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界; (4)同一个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)参考答案：C12.要求具有同一逻辑结构的数据元素具有相同的特性，其含义为A.每个数据元素都一样B.数据元素具有同一的特点C.仅需要数据元素包含的数据项的个数相同D.不仅数据元素
5、包含的数据项的个数相同，而且其对应数据项的类型要一致参考答案：D13.希尔排序的增量序列必须是()。A.递增的B.随机的C.递减的D.非递减的参考答案：C14.下列说法正确的是：(1)二叉树按某种方式线索化后，任一节点均有指向前趋和后继的线索;(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前;(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值。A.(1)(2)(3)B.(1)(2)C.(1)(3)D.前面的可选答案都不对参考答案：D15.以下与数据的存储结构无关的术语是()。A.循环队列B.链表C.哈希表D.栈参考答案：D16.快速排序在最坏情况下的时间复杂度是A.O(
6、nlog2n)B.O(n2log2n)C.O(n2)D.O(log2n)参考答案：C17.已知循环队列的存储空间为数组data21，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为()。A.5B.6C.16D.17参考答案：C18.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()。A.1和5B.2和4C.4和2D.5和1参考答案：B19.已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为()。A.2B
7、.3C.8D.9参考答案：C20.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是()。A.栈B.线性表C.队列D.二叉排序树参考答案：A21.以下数据结构中，属于线性结构的是()。A.广义表B.二叉树C.稀疏矩阵D.串参考答案：A22.某二叉树中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E。则该二叉树对应的森林包括的树的棵树是()。A.1B.2C.3D.4参考答案：B23.下列编码中属于前缀编码的是()。A.1，01，000，001B.1，01，011，010C.0，10，110，11D.0，1，00，11参考答案：A2
8、4.能进行二分查找的线性表，必须以()。A.顺序方式存储，且元素按关键字有序B.链式方式存储，且元素按关键字有序C.顺序方式存储，且元素按关键字分块有序D.链式方式存储，且元素按关键字分块有序参考答案：A25.在目标串T0.n-1=xwxxyxy中，对模式串P0.m-1=xy 进行子串定位操作的结果是A.5B.3C.2D.1参考答案：B26.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A27.引入二叉线索树的目的是A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找
9、到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A28.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用()。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B29.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()。A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点参考答案：C30.二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是()。
10、A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B31.设一个栈的输入序列为1、2、3、4、5，则借助一个栈所得到的输出序列不可能是()。A.23415B.54132C.23145D.15432参考答案：B32.在下列各种文件中，不能进行顺序查找的文件是A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C33.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为A.DEFBCAB.DEBFCAC.DEBCFAD.DEBAFC参考答案：A34.队列和栈的主要区别是A.限定插入和删除的位置不同B.逻辑结构不同C.所包含的运算个数不同D.存储结构不同参考答案
11、：A35.若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列()。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A36.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是()。A.分块查找B.顺序查找C.二分查找D.散列查找参考答案：D37.在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是()。A.1B.2C.3D.5参考答案：C38.在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.查找B.插入C.排序D.删除参考答案：A39.上溢现象通常出现在A.顺序栈的出栈操作过程中B.顺序栈的入
12、栈操作过程中C.链栈的出栈操作过程中D.链栈的入栈操作过程中参考答案：B40.已知一组关键字为25，48，36，72，79，82，23，40，16，35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是()。A.25，36，48，72，23，40，79，82，16，35B.25，36，48，72，16，23，40，79，82，35C.25，36，48，72，16，23，35，40，79，82D.16，23，25，35，36，40，48，72，79，82参考答案：D41.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列
13、是()。A.1234B.4132C.4231D.4213参考答案：C42.栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构参考答案：A43.抽象数据类型的三个组成部分分别为()。A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型参考答案：A44.对有18个元素的有序表作二分查找，则查找A3的比较序列的下标为()。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D45.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是A.O(nlogn)B.O(n2)C.O(n)D.O(1)参考答案：C
东北大学22春“计算机科学与技术”《数据结构Ⅱ》作业考核易错、难点汇编⑥（带答案）试卷号：15
