西安交通大学18年9月课程考试《数据结构》作业考核试题 （100分

西安交通大学18年9月课程考试《数据结构》作业考核试题 
试卷总分:100    得分:100

一、 单选题 (共 30 道试题,共 60 分)
1.字符串的长度是指（）
A.串中不同字符的个数
B.串中不同字母的个数
C.串中所含字符的个数
D.串中不同数字的个数
正确答案: C

2.两个字符串相等的条件是（ ）。
A.两串的长度相等；
B.两串包含的字符相同；
C.两串的长度相等，并且两串包含的字符相同；
D.两串的长度相等，并且对应位置上的字符相同。
正确答案: D

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

4.对稀疏矩阵进行压缩存储目的是（ ）。
A.便于进行矩阵运算
B.便于输入和输出
C.节省存储空间
D.降低运算的时间复杂度
正确答案: C

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

6.执行一趟快速排序能够得到的序列是（）。
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，63，72
正确答案: A

7.二叉树的第k层的结点数最多为（）.
A.2-1
B.2K+1
C.2K-1
D.2
正确答案: D

8.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。
A.n-i
B.n+l-i
C.n-1-i
D.i
正确答案: A

9.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）
A.p->right=s；s->left=p；p->right->left=s；s->right=p->right；
B.s->left=p；s->right=p->right；p->right=s；p->right->left=s；
C.p->right=s；p->right->left=s；s->left=p；s->right=p->right；
D.s->left=p；s->right=p->right；p->right->left=s；p->right=s；
正确答案: D

10.一个非空广义表的表头（）
A.不可能是子表
B.只能是子表
C.只能是原子
D.可以是子表或原子
正确答案:www.youxue100f.com

11.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。
A.99
B.100
C.101
D.102
正确答案:

12.一个循环队列一旦说明，其占用空间的大小（ ）。
A.已固定
B.可以变动
C.不能固定
D.动态变化
正确答案:

13.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。
A.8
B.7
C.6
D.5
正确答案:

14.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。
A.(rear+1) MOD n=front
B.rear=front
C.rear+1=front
D.(rear-l) MOD n=front
正确答案:

15.若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）
A.上三角矩阵
B.稀疏矩阵
C.对角矩阵
D.对称矩阵
正确答案:

16.下面关于线性表的叙述中，错误的是（ ）关系。
A.顺序表必须占一片地址连续的存储单元
B.顺序表可以随机存取任一元素
C.链表不必占用一片地址连续的存储单元
D.链表可以随机存取任一元素
正确答案:

17.建立一个长度为n的有序单链表的时间复杂度为（）
A.O(n)
B.O(1)
C.O(n)
D.O(log2n)
正确答案:

18.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。
A.q=p->next；p->data=q->data；p->next=q->next；free(q)；
B.q=p->next；q->data=p->data；p->next=q->next；free(q)；
C.q=p->next；p->next=q->next；free(q)；
D.q=p->next；p->data=q->data；free(q)；
正确答案:

19.二分查找有序表{4，6，10，12，20，30，50，70，88，100}，若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
A.30，88，70，50
B.20，70，30，50
C.20，50
D.30，88，50
正确答案:

20.设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。
A.1
B.n
C.nlog2n
D.n
正确答案:

21.深度为h且有（ ）个结点的二叉树称为满二叉树。
A.2h-1
B.2h
C.2h-1
D.2h
正确答案:

22.以下数据结构中哪一个是非线性结构？（）
A.队列
B.栈
C.线性表
D.二叉树
正确答案:

23.
A.A
B.B
C.C
D.D
正确答案:

24.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。
A.10
B.19
C.28
D.55
正确答案:

25.下列四种排序中（）的空间复杂度最大。
A.插入排序
B.冒泡排序
C.堆排序
D.归并排序
正确答案:

26.用链表存储的线性表，其优点是（ ）。
A.便于随机存取
B.花费的存储空间比顺序表少
C.便于插入和删除
D.数据元素的物理顺序与逻辑顺序相同
正确答案:

27.二路归并排序的时间复杂度为（）。
A.O(n)
B.O(n)
C.O(nlog2n)
D.O(1og2n)
正确答案:

28.链表适用于（ ）查找。
A.顺序
B.二分
C.随机
D.顺序或二分
正确答案:

29.对一棵二叉排序树进行（ ）遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。
A.前序
B.中序
C.后序
D.按层次
正确答案:

30.设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。
A.3
B.4
C.5
D.6
正确答案:

二、 判断题 (共 20 道试题,共 40 分)
1.对有序表而言采用二分查找总比采用顺序查找法速度快。（ ）
A.错误
B.正确
正确答案:

2.快速排序是排序算法中平均性能最好的一种排序。
A.错误
B.正确
正确答案:

3.从本质上看，文件是一种非线性结构。 ( )
A.错误
B.正确
正确答案:

4.哈夫曼树中没有度数为1的结点。
A.错误
B.正确
正确答案:

5.哈夫曼树中没有度数为2的结点。
A.错误
B.正确
正确答案:

6.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。
A.错误
B.正确
正确答案:

7.栈和队列都是限制存取点的线性结构。 ( )
A.错误
B.正确
正确答案:

8.算法与程序没有区别。 ( )
A.错误
B.正确
正确答案:

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

10.堆排序所需的时间与待排序的记录个数无关。（ ）
A.错误
B.正确
正确答案:

11.设串S的长度为n,则S的子串个数为n(n+1)/2。 ( )
A.错误
B.正确
正确答案:

12.调用一次深度优先遍历可以访问到图中的所有顶点。
A.错误
B.正确
正确答案:

13.一个完整的算法可以没有输入，但必须有输出。 ( )
A.错误
B.正确
正确答案:

14.由树转化成二叉树，该二叉树的右子树不一定为空。
A.错误
B.正确
正确答案:

15.完全二叉树中的叶子结点只可能在最后两层中出现。（ ）
A.错误
B.正确
正确答案:

16.如果某种排序算法不稳定，则该排序方法就没有实用价值。（ ）
A.错误
B.正确
正确答案:

17.冒泡排序是不稳定的排序。（ ）
A.错误
B.正确
正确答案:

18.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
A.错误
B.正确
正确答案:

19.
A.错误
B.正确
正确答案:

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