2023年西安交通大学《数据结构》在线作业二

奥鹏西安交通大学新学期作业参考

西安交通大学新学期《数据结构》在线作业-00002

1.用链表表示线性表的优点是（）
选项A：便于随机存取
选项B：花费的存储空间比顺序表少
选项C：便于插入与删除
选项D：数据元素的物理顺序与逻辑顺序相同
正确答案问询微信：424329

2.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）
选项A：front=front+1
选项B：front=(front+1)%(m-1)
选项C：front=(front-1)%m
选项D：front=(front+1)%m
正确答案问询微信：424329

3.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ ）查找方法。
选项A：分块
选项B：顺序
选项C：二分
选项D：散列
正确答案问询微信：424329

4.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
选项A：2m-1
选项B：2m
选项C：2m+1
选项D：4m
正确答案问询微信：424329

5.求字符串T在字符串S中首次出现的位置的操作称为( )。
选项A：串的模式匹配
选项B：求子串
选项C：求串的长度
选项D：串的连接
正确答案问询微信：424329

6.哈希表的平均查找长度是( )的函数。
选项A：哈希表的长度
选项B：表中元素的多少
选项C：哈希函数
选项D：哈希表的装满程度
正确答案问询微信：424329

7.设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）
选项A：R-F
选项B：F-R
选项C：(R-F+M)％M
选项D：(F-R+M)％M
正确答案问询微信：424329

8.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。
选项A：head==0
选项B：head-next==0
选项C：head-next==head
选项D：head!=0
正确答案问询微信：424329

9.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
选项A：n
选项B：e
选项C：2n
选项D：2e
正确答案问询微信：424329

10.设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
选项A：n(n-1)/2
选项B：n(n-1)
选项C：n
选项D：n-1
正确答案问询微信：424329

11.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（ ）次比较后查找成功。
选项A：2
选项B：3
选项C：4
选项D：5
正确答案问询微信：424329

12.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。
选项A：O(n)
选项B：O(n^2)
选项C：O(n^3)
选项D：O(1og2n)
正确答案问询微信：424329

13.执行一趟快速排序能够得到的序列是（）。
选项A：[41，12，34，45，27]55[72，63]
选项B：[45，34，12，41]55[72，63，27]
选项C：[63，12，34，45，27]55[41，72]
选项D：[12，27，45，41]55[34，6奥鹏西安交通大学新学期作业参考3，72
正确答案问询微信：424329

14.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
选项A：直接插入
选项B：直接选择
选项C：堆
选项D：快速
正确答案问询微信：424329

15.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。
选项A：不确定
选项B：n-i+1
选项C：i
选项D：n-i
正确答案问询微信：424329

16.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。
选项A：空或只有一个结点
选项B：高度等于其结点数
选项C：任一结点无左孩子
选项D：任一结点无右孩子
正确答案问询微信：424329

17.一个具有n个顶点的无向图最多有( )条边。
选项A：n(n-1)/2
选项B：n(n-1)
选项C：n(n+1)/2
选项D：n2
正确答案问询微信：424329

18.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）
选项A：BADC
选项B：BCDA
选项C：CDAB
选项D：CBDA
正确答案问询微信：424329

19.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。
选项A：6
选项B：7
选项C：8
选项D：9
正确答案问询微信：424329

20.存放循环队列元素的数组data有10个元素，则data数组的下标范围是（ ）。
选项A：0～10
选项B：0～9
选项C：1～9
选项D：1～10
正确答案问询微信：424329

21.空串与空格字符组成的串的区别是（ ）。
选项A：没有区别；
选项B：两串的长度不等；
选项C：两串的长度相等；
选项D：两串包含的字符不相同。
正确答案问询微信：424329

22.在二叉排序树中插入一个结点的时间复杂度为（）。
选项A：O(1)
选项B：O(n)
选项C：O(log2n)
选项D：O(n)
正确答案问询微信：424329

23.在序列（2，5，8，11，15，16，22，24，27，35，50）中采用折半查找（二分查找）方法查找元素24，需要进行（ ）次元素之间的比较。
选项A：3
选项B：4
选项C：8
选项D：11
正确答案问询微信：424329

24.设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。
选项A：3
选项B：4
选项C：5
选项D：6
正确答案问询微信：424329

25.由两个栈共享一个向量空间的好处是：（）
选项A：减少存取时间，降低下溢发生的机率
选项B：节省存储空间，降低上溢发生的机率
选项C：减少存取时间，降低上溢发生的机率
选项D：节省存储空间，降低下溢发生的机率
正确答案问询微信：424329

26.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。
选项A：堆排序
选项B：冒泡排序
选项C：希尔排序
选项D：快速排序
正确答案问询微信：424329

27.设用链表作为栈的存储结构则退栈操作（）
选项A：必须判别栈是否为满
选项B：必须判别栈是否为空
选项C：判别栈元素的类型
选项D：对栈不作任何判别
正确答案问询微信：424329

28.设顺序表的长度为n，则顺序查找的平均比较次数为（）。
选项A：n
选项B：n/2
选项C：(n+1)/2
选项D：(n-1)/2
正确答案问询微信：424329

29.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，打印机依次从该缓冲区中取出数据打印，则该缓冲区的结构应该是（ ）。
选项A：线性表
选项B：数组
选项C：堆栈
选项D：队列
正确答案问询微信：424329

30.广度优先遍历类似于二叉树的（ ）。
选项A：先序遍历
选项B：中序遍历
选项C：后序遍历
选项D：层次遍历
正确答案问询微信：424329

31.中序遍历一棵二叉排序树可以得到一个有序的序列。
选项A：错误
选项B：正确
正确答案问询微信：424329

32.子串“ABC”在主串“AABCABCD”中的位置为3。
选项A：错误
选项B：正确
正确答案问询微信：424329

33.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。
选项A：错误
选项B：正确
正确答案问询微信：424329

34.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。
选项A：错误
选项B：正确
正确答案问询微信：424329

35.在B+树中查找和在B-树中查找的过程完全相同。 ( )
选项A：错误
选项B：正确
正确答案问询微信：424329

36.栈的特点是“后进先出”。（ ）
选项A：错误
选项B：正确
正确答案问询微信：424329

37.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O（n）。
选项A：错误
选项B：正确
正确答案问询微信：424329

38.设串S的长度为n,则S的子串个数为n(n+1)/2。
选项A：对
选项B：错
正确答案问询微信：424329

39.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）
选项A：错误
选项B：正确
正确答案问询微信：424329

40.由树转化成二叉树，该二叉树的右子树不一定为空。（ ）
选项A：错误
选项B：正确
正确答案问询微信：424329

41.磁带是顺序存取的外存储设备。
选项A：对
选项B：错
正确答案问询微信：424329

42.调用一次深度优先遍历可以访问到图中的所有顶点。
选项A：错误
选项B：正确
正确答案问询微信：424329

43.希尔排序算法的时间复杂度为O(n2)。
选项A：错误
选项B：正确
正确答案问询微信：424329

44.二维数组和多维数组均不是特殊的线性结构。
选项A：错误
选项B：正确
正确答案问询微信：424329

45.层次遍历初始堆可以得到一个有序的序列。
选项A：错误
选项B：正确
正确答案问询微信：424329

46.从本质上看,文件是一种非线性结构。
选项A：对
选项B：错
正确答案问询微信：424329

47.设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。
选项A：错误
选项B：正确
正确答案问询微信：424329

48.
选项A：错误
选项B：正确
正确答案问询微信：424329

49.对连通图进行深度优先遍历可以访问到该图中的所有顶点。
选项A：错误
选项B：正确
正确答案问询微信：424329

50.完全二叉树中的叶子结点只可能在最后两层中出现。（ ）
选项A：错误
选项B：正确
正确答案问询微信：424329