数据结构（宁夏大学）期末答案2023秋

1.

如下图所示二叉树的后序遍历序列是

A:GDBEHFJKIMCA B:GDJKIMBAEHCF C:GJKHDEBMIFCA  D:GDJKIMABCEFH
答案:AI参考:正确选项是：D:GDJKIMABCEFH\n\n根据题目所给的二叉树图像，我们可以按照后序遍历的顺序进行遍历，即先访问右子树，再访问左子树，最后访问根节点。后序遍历的顺序为：右子树、左子树、根节点。根据这个顺序，我们可以得到以下选项：\n\nA选项：G→D→B→G→D→E→H→F→K→I→M→C\nB选项：G→D→J→K→I→M→B→A→H→C\nC选项：G→J→H→D→E→B→M→I→F→C\nD选项：G→D→J→K→I→M→B→A→C→E→H\n\n根据题目要求，我们需要选择一个后序遍历序列，因此我们需要考虑选项中是否存在重复的节点。在D选项中，我们可以看到所有的节点都只出现一次，因此D选项是唯一的后序遍历序列。因此，正确答案是D:GDJKIMABCEFH。'
2.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（    ）。
A:选择排序 B:希尔排序 C:冒泡排序 D:插入排序
答案:插入排序
3.广义表B=（(a,b,(e,h)),(c,d)）,则下面式子tail(head(B) ) 的值为 （    ）。
A:(b,(e,h)) B:d C:(a,b) D:(c,d)
答案:(b,(e,h))
4.对线性表进行折半查找时，要求线性表必须（   ）。
A:以顺序方式存储，且结点按关键字有序排列 B:以链式方式存储 C:以顺序方式存储 D:以链式方式存储，且结点按关键字有序排列
答案:以顺序方式存储，且结点按关键字有序排列
5.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为（     ）。
A:n-i+1 B:i C:n-i D:i-1
答案:n-i+1
6.已知一棵二叉树的前序遍历序列为abdgcehf，中序遍历序列为 dgbaehcf,则该二叉树的后序遍历序列是（   ）。
A:gdbaehcf B:gdbhefca C:gdbehfca D:gdabcefh
答案:gdbhefca
7.一个具有n个顶点的连通无向图的生成树中有(   )条边。
A:n-1 B:n/2 C:n+1 D:n
答案:n-1
8.如果最常用的操作是取第i个结点及其前驱，则采用（   ）存储方式最节省时间。
A:单循环链表 B:顺序表 C:单链表 D:双链表
答案:顺序表
9.若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(   ) 。
A:CDBAGFE B:CDBGFEA C:BCDAGFE D:CDBFGEA
答案:CDBGFEA
10.子串“ABC”在主串“AABCABCDABCD”中的位置为 (   )。
A:9 B:2 C:5 D:1
答案:2
11.在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（   ）。
A:希尔排序 B:冒泡排序 C:直接选择排序 D:直接插入排序 12.广义表A=（(a,b,(e,h)),(c,d)）,则下面式子tail(head(A) ) 的值为 （    ）。
A:(c,d) B:(b,(e,h)) C:(a,b) D:a 13.串是一种特殊的线性表，其特殊性体现在（   ）。
A:可以顺序存储 B:数据元素可以是多个字符 C:可以链式存储 D:数据元素是一个字符 14.具有10个叶子结点的二叉树中有（   ）个度为2的结点。
A:9 B:8 C:10 D:11 15.在以下的叙述中，正确的是（     ）。
A:栈的操作方式是先进先出                    B:线性表的线性存储结构优于链表存储结构 C:队列的操作方式是先进后出 D:二维数组是其数据元素为线性表的线性表 16.用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴ 25，84，21，47，15，27，68，35，20⑵ 20，15，21，25，47，27，68，35，84⑶ 15，20，21，25，35，27，47，68，84⑷ 15，20，21，25，27，35，47，68，84则所采用的排序方法是（   ）。
A:选择排序 B:归并排序 C:希尔排序 D:快速排序 17.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（   ）倍。
A:1/2 B:1 C:2 D:4 18.关键路径是事件结点网络中（     ）。
A:从源点到汇点的最长路径           B:从源点到汇点的最短路径 C:最短的回路 D:最长的回路           19.有一个有序表为{1,4,9,12,30,41,45,62,75,77,88,95,120},当折半查找值为62的结点时，（  ）次比较后查找成功。
A:3 B:8 C:1 D:4 20.设有向无环图G中的有向边集合E={<1，2>，<1，3>，<2，3>，<2，5>，<4，5>}，则下列属于该有向图G的一种拓扑排序序列的是（  ）。
A:1，4，2，5，3 B:2，3，4，1，5 C:1，5，2，4，3 D:1，3，2，5，4 21.已知一个图的顶点集V各边集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}，用广度优先遍历的序列是（  ）
A:0，1，4，2，7，3，8，6，5，9 B:0，1，2，8，3，4，5，6，7，9 C:0，4，3，8，9，5，6，7，1，2 D:0，4，1，3，7，2，8，6，9，5 22.希尔排序的增量序列必须是（   ）。
A:非递减的 B:递减的 C:递增的 D:随机的 23.已知二叉树中叶子数为41，仅一个孩子的结点数为50，则总结点数为 （    ）。   
A:128 B:131 C:130 D:129 24.设p指向线索二叉树的某结点，该结点没有左孩子的主要条件是（   ）。
A:p->lchild==NULL B:p->ltag==0 C:p->ltag==1 D:p->rchild==NULL 25.若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下为二路归并排序过程。第二趟为(   ):
A:[129 265 301 694 742 751 863 937] [076 438]   B:[076 129 265 301 438 694 742 751 863 937]   C:[265 301] [129 751] [863 937] [694 742] [076 438]   D:[129 265 301 751] [694 742 863 937] [076 438] 26.在一个有向图中,所有顶点的入度之和等于所有弧数和（   ）倍。
A:4 B:1 C:3 D:2 27.允许对队列进行的基本操作有（   ）。
A:对队列中的元素排序 B:在队头元素之前插入元素 C:取出最近进队的元素 D:删除队头元素 28.某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用（     ）存储方法时间性能最好。
A:单向循环链表 B:顺序表 C:双向循环链表 D:双向链表 29.链表不具备的特点是（   ）。
A:不必事先估计存储空间 B:插入删除不需要移动元素 C:所需空间与其长度成正比 D:可随机访问任一结点 30.邻接表是图的一种（   ）。
A:索引存储结构 B:顺序存储结构 C:散列存储结构 D:链式存储结构    31.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。（ ）
A:错误 B:正确 32.空串是任何串的子串。（ ）
A:错误 B:正确