西交17年3月课程《数据结构》作业考核标准答案
西安交通大学17年3月课程考试《数据结构》作业考核试题一、单选题：
1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) (满分:2)
A. 存储结构
B. 逻辑结构
C. 算法
D. 操作
2.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为( )。 (满分:2)
A. 8
B. 7
C. 6
D. 5
3.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。 (满分:2)
A. O(n)
B. O(nlog2n)
C. O(n)
D. O(1og2n)
4.栈的插入和删除操作在( )进行。 (满分:2)
A. 栈顶
B. 栈底
C. 任意位置
D. 指定位置
5.二路归并排序的时间复杂度为( )。 (满分:2)
A. O(n)
B. O(n)
C. O(nlog2n)
D. O(1og2n)
6.设某强连通图中有n个顶点，则该强连通图中至少有( )条边。 (满分:2)
A. n(n-1)
B. n+1
C. n
D. n(n+1)
7.设一个顺序有序表A中有14个元素，则采用二分法查找元素A的过程中比较元素的顺序为( ) (满分:2)
A. A，A，A，A
B. A，A，A，A
C. A，A，A，A
D. A，A，A，A
8.下列各种排序算法中平均时间复杂度为O（n）是( )。 (满分:2)
A. 快速排序
B. 堆排序
C. 归并排序
D. 冒泡排序
9.如下陈述中正确的是( ) (满分:2)
A. 串是一种特殊的线性表
B. 串的长度必须大于零
C. 串中元素只能是字母
D. 空串就是空白串
10.设有一个二维数组A，假设A存放位置在644(10)，A存放位置在676(10)，每个元素占一个空间，问A(10)存放在什么位置( )？脚注(10)表示用10进制表示。 (满分:2)
A. 688
B. 678
C. 692
D. 696
11.适于对动态查找表进行高效率查找的组织结构是( ) (满分:2)
A. 有序表
B. 分块有序表
C. 三叉排序树
D. 线性链表
12.设某完全无向图中有n个顶点，则该完全无向图中有( )条边。 (满分:2)
A. n(n-1)/2
B. n(n-1)
C. n
D. n-1
13.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为( )。 (满分:2)
A. O(n+e)
B. O(n)
C. O(ne)
D. O(n)
14.在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。 (满分:2)
A. s→link=p→link;p→link=s
B. p→link=s;s→link=q
C. p→link=s→link;s→link=p
D. q→link=s;s→link=p
15.设某哈夫曼树中有199个结点，则该哈夫曼树中有( )个叶子结点。 (满分:2)
A. 99
B. 100
C. 101
D. 102
16.若有18个元素的有序表存放在一维数组A中，第一个元素放A中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) (满分:2)
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
17.用链表表示线性表的优点是( ) (满分:2)
A. 便于随机存取
B. 花费的存储空间比顺序表少
C. 便于插入与删除
D. 数据元素的物理顺序与逻辑顺序相同
18.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为( )。 (满分:2)
A. 2i+1
B. 2i
C. i/2
D. 2i-1
19.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是( )。 (满分:2)
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
20.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H( )=K%9作为散列函数，则散列地址为1的元素有( )个 (满分:2)
A. 1
B. 2
C. 3
D. 4
21.以下数据结构中哪一个是非线性结构？( ) (满分:2)
A. 队列
B. 栈
C. 线性表
D. 二叉树
22.一个非空广义表的表头( ) (满分:2)
A. 不可能是子表
B. 只能是子表
C. 只能是原子
D. 可以是子表或原子
23.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (满分:2)
A. 6
B. 7
C. 8
D. 9
24.设某有向图中有n个顶点，则该有向图对应的邻接表中有( )个表头结点。 (满分:2)
A. n-1
B. n
C. n+1
D. 2n-1
25.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。 (满分:2)
A. s->next=p->next；p->next=-s；
B. q->next=s；s->next=p；
C. p->next=s->next；s->next=p；
D. p->next=s；s->next=q；
26.设有一个二维数组A，假设A存放位置在644(10)，A存放位置在676(10)，每个元素占一个空间，问A(10)存放在什么位置( )？脚注(10)表示用10进制表示。 (满分:2)
A. 688
B. 678
C. 692
D. 696
27.下列四种排序中( )的空间复杂度最大。 (满分:2)
A. 插入排序
B. 冒泡排序
C. 堆排序
D. 归并排序
28.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。 (满分:2)
A. n-i
B. n+l-i
C. n-1-i
D. i
29.在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为( ) (满分:2)
A. 4
B. 5
C. 6
D. 7
30.对5个不同的数据元素进行直接插入排序，最多需要进行( )次比较。 (满分:2)
A. 8
B. 10
C. 15
D. 25
三、判断题：
1.闭散列法通常比开散列法时间效率更高。 (满分:2)
A. 错误
B. 正确
2.希尔排序算法的时间复杂度为O(n2)。 (满分:2)
A. 错误
B. 正确
3.子串“ABC”在主串“AABCABCD”中的位置为3。 (满分:2)
A. 错误
B. 正确
4.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。 (满分:2)
A. 错误
B. 正确
5.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。 (满分:2)
A. 错误
B. 正确
6.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。 (满分:2)
A. 错误
B. 正确
7.对链表进行插入和删除操作时不必移动链表中结点。 (满分:2)
A. 错误
B. 正确
8.中序遍历一棵二叉排序树可以得到一个有序的序列。 (满分:2)
A. 错误
B. 正确
9.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。 (满分:2)
A. 错误
B. 正确
10.希尔排序算法的时间复杂度为O（n）。 (满分:2)
A. 错误
B. 正确
11.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。 (满分:2)
A. 错误
B. 正确
12.层次遍历初始堆可以得到一个有序的序列。 (满分:2)
A. 错误
B. 正确
13.顺序表查找指的是在顺序存储结构上进行查找。 (满分:2)
A. 错误
B. 正确
14.带权无向图的最小生成树是唯一的。 (满分:2)
A. 错误
B. 正确
15.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。 (满分:2)
A. 错误
B. 正确
16.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。 (满分:2)
A. 错误
B. 正确
17.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。 (满分:2)
A. 错误
B. 正确
18.有向图的邻接表和逆邻接表中表结点的个数不一定相等。 (满分:2)
A. 错误
B. 正确
19.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。 (满分:2)
A. 错误
B. 正确
20.堆是完全二叉树，完全二叉树不一定是堆。 (满分:2)
A. 错误
B. 正确
回复贴子下载标准答案
**** Hidden Message *****
页:
[1]