西安交通大学17年5月补考《数据结构》作业考核试题 辅导资料

奥鹏在线作业

一、单选题（共 30 道试题，共 60 分。）  V 1.  设完全无向图中有n个顶点，则该完全无向图中有（）条边。
. n(n-1)/2
. n(n-1)
. n(n+1)/2
. (n-1)/2
标准资料：
2.  在一棵具有5层的满二叉树中结点数为（）
. 31
. 32
. 33
. 16
标准资料：
3.  设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。
. 1
. 2
. 3
. 4
标准资料：
4.  设有6个结点的无向图，该图至少应有（）条边才能确保是一个连通图。
. 5
. 6
. 7
. 8
标准资料：
5.  树最适合用来表示（）。
. 有序数据元素
. 无序数据元素
. 元素之间具有分支层次关系的数据
. 元素之间无联系的数据
标准资料：
6.  设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
. n-i
. n+l-i
. n-1-i
. i
标准资料：
7.  若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）
. O（1）
. O（n）
. O（n^2)
. O（n^3）
标准资料：
8.  设一个顺序有序表[1:14]中有14个元素，则采用二分法查找元素[4]的过程中比较元素的顺序为（）
. [1]，[2]，[3]，[4]
. [1]，[14]，[7]，[4]
. [7]，[3]，[5]，[4]
. [7]，[5]，[3]，[4]
标准资料：
9.  设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
. N0=N1+1
. N0=Nl+N2
. N0=N2+1
. N0=2N1+l
标准资料：
10.  对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）
. 直接选择排序
. 直接插入排序
. 快速排序
. 起泡排序
标准资料：
11.  设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
. 9
. 10
. 11
. 12
标准资料：
12.  在二叉排序树中插入一个结点的时间复杂度为（）。
. O(1)
. O(n)
. O(log2n)
. O(n)
标准资料：
13.  设带有头结点的单向循环链表的头指针变量为he，则其判空条件是（）。
. he==0
. he->next==0
. he->next==he
. he!=0
标准资料：
14.  设一条单链表的头指针变量为he且该链表没有头结点，则其判空条件是（）。
. he==0
. he->next==0
. he->next==he
. he!=0
标准资料：
15.  设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
. n-1
. n
. n+1
. 2n-1
标准资料：
16.  以下数据结构中哪一个是非线性结构？（）
. 队列
. 栈
. 线性表
. 二叉树
标准资料：
17.  设指针变量p指向单链表中结点，若删除单链表中结点，则需要修改指针的操作序列为（）。
. q=p->next；p->t=q->t；p->next=q->next；free(q)；
. q=p->next；q->t=p->t；p->next=q->next；free(q)；
. q=p->next；p->next=q->next；free(q)；
. q=p->next；p->t=q->t；free(q)；
标准资料：
18.  设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。
. 20
. 256
. 512
. 1024
标准资料：
19.  下面关于线性表的叙述错误的是（）。
. 线性表采用顺序存储必须占用一片连续的存储空间
. 线性表采用链式存储不必占用一片连续的存储空间
. 线性表采用链式存储便于插入和删除操作的实现
. 线性表采用顺序存储便于插入和删除操作的实现
标准资料：
20.  设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。
. 1
. 2
. 3
. 4
标准资料：
21.  一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。
. 堆排序
. 冒泡排序
. 快速排序
. 希尔排序
标准资料：
22.  用链接方式存储的队列，在进行插入运算时（）.
. 仅修改头指针
. 头、尾指针都要修改
. 仅修改尾指针
. 头、尾指针可能都要修改
标准资料：
23.  队列是一种（）的线性表。
. 先进先出
. 先进后出
. 只能插入
. 只能删除
标准资料：
24.  下列程序段的时间复杂度为（）。i=0，s=0；while(s<n){s=s+i；i++；}
. O(n)
. O(n)
. O(n)
. O(n)
标准资料：
25.  下列四种排序中（）的空间复杂度最大。
. 插入排序
. 冒泡排序
. 堆排序
. 归并排序
标准资料：
26.  设数组t[m]作为循环队列SQ的存储空间，front为队头指针，rer为队尾指针，则执行出队操作后其头指针front值为（）
. front=front+1
. front=(front+1)%(m-1)
. front=(front-1)%m
. front=(front+1)%m
标准资料：
27.  设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。
. 6
. 11
. 5
. 6.5
标准资料：
28.  栈和队列的共同特点是（）。
. 只允许在端点处插入和删除元素
. 都是先进后出
. 都是先进先出
. 没有共同点
标准资料：
29.  设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
. 99
. 100
. 101
. 102
标准资料：
30.  设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。
. 1，2，3，4
. 2，3，4，1
. 1，4，2，3
. 1，2，4，3
标准资料：


二、判断题（共 20 道试题，共 40 分。）  V 1.  对连通图进行深度优先遍历可以访问到该图中的所有顶点。
. 错误
. 正确
标准资料：
2.  哈夫曼树中没有度数为1的结点。
. 错误
. 正确
标准资料：
3.  非空的双向循环链表中任何结点的前驱指针均不为空。
. 错误
. 正确
标准资料：
4.  一棵m阶树中每个结点最多有m个关键码，最少有2个关键码。
. 错误
. 正确
标准资料：
5.  向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
. 错误
. 正确
标准资料：
6.  稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
. 错误
. 正确
标准资料：
7.  顺序表用一维数组作为存储结构，因此顺序表是一维数组。
. 错误
. 正确
标准资料：
8.  有向图的邻接表和逆邻接表中表结点的个数不一定相等。
. 错误
. 正确
标准资料：
9.  由树转化成二叉树，该二叉树的右子树不一定为空。
. 错误
. 正确
标准资料：
10.  为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。
. 错误
. 正确
标准资料：
11.  二维数组是数组元素为一维数组的线性表，因此它是线性结构。
. 错误
. 正确
标准资料：
12.  不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。
. 错误
. 正确
标准资料：
13.  完全二叉树中的叶子结点只可能在最后两层中出现。
. 错误
. 正确
标准资料：
14.  对链表进行插入和删除操作时不必移动链表中结点。
. 错误
. 正确
标准资料：
15.  分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
. 错误
. 正确
标准资料：
16.  对连通图进行深度优先遍历可以访问到该图中的所有顶点。
. 错误
. 正确
标准资料：
17.  稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
. 错误
. 正确
标准资料：
18.  子串“”在主串“”中的位置为3。
. 错误
. 正确
标准资料：
19.  设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。
. 错误
. 正确
标准资料：
20.  线性表中的所有元素都有一个前驱元素和后继元素。
. 错误
. 正确
标准资料：