加载中…西安交通大学18年3月课程考试《数据结构》作业考核试题满分
(2018-03-15 18:40:50)西安交通大学18年3月课程考试《数据结构》作业考核试题
一、 单选题 (共 30 道试题,共 60 分)
1.对一棵二叉排序树进行（ ）遍历，可以得到该二叉树的多有结点按值从小到大排列的序列。
A.前序
B.中序
C.后序
D.按层次
2.对稀疏矩阵进行压缩存储目的是（ ）。
A.便于进行矩阵运算
B.便于输入和输出
C.节省存储空间
D.降低运算的时间复杂度
3.对算法进行分析的前提是（ ）
A.算法必须简单
B..算法必须正确
C.算法运行时间少
D.算法占有空间少
4.设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。
A.1
B.n
C.nlog2n
D.n
5.若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）
A.O（1）
B.O（n）
C.O（n^2)
D.O（n^3）
6.下面关于线性表的叙述错误的是（）。
A.线性表采用顺序存储必须占用一片连续的存储空间
B.线性表采用链式存储不必占用一片连续的存储空间
C.线性表采用链式存储便于插入和删除操作的实现
D.线性表采用顺序存储便于插入和删除操作的实现
7.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。
A.8
B.10
C.15
D.25
8.按照二叉树的定义，具有3个结点的二叉树有（ ）种形态。
A.2
B.3
C.4
D.5
9.线性表采用链式存储时，结点的存储地址（）
A.必须是不连续的
B.连续与否均可
C.必须是连续的
D.和头结点的存储地址相连续
10.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。
A.堆排序
B.冒泡排序
C.快速排序
D.希尔排序
11.设有100个数据元素，采用折半搜索时，最大比较次数为（）
A.6
B.7
C.8
D.10
12.两个字符串相等的充要条件是（）。
A.两个字符串的长度相等
B.两个字符串中对应位置上的字符相等
C.同时具备(A)和(B)两个条件
D.以上答案都不对
13.二叉排序树中左子树上所有结点的值均（）根结点的值。
A.<</div>
B.>
C.=
D.!=
14.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（
）次比较后查找成功。
A.2
B.3
C.4
D.5
15.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
A.O（1）
B.O（n）
C.O（1og2n）
D.O（n2)
16.算法指的是（）
A.计算机程序
B.解决问题的计算方法
C.排序算法
D.解决问题的有限运算序列
17.一个具有n个顶点的无向图最多有（ ）条边。
A.n×(n-1)/2
B.n×(n-1)
C.n×(n+1)/2
D.n2
18.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A.前序
B.中序
C.后序
D.按层次
19.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置（）？脚注(10)表示用10进制表示。
A.688
B.678
C.692
D.696
20.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。
A.1
B.2
C.3
D.4
21.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）
A.20
B.30
C.40
D.45
22.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
A.n(n-1)
B.n+1
C.n
D.n(n+1)
23.设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
A.n-1
B.n
C.n+1
D.2n-1
24.适于对动态查找表进行高效率查找的组织结构是（）
A.有序表
B.分块有序表
C.三叉排序树
D.线性链表
25.线性链表各结点之间的地址（ ）。
A.必须连续
B.一定不连续
C.部分地址必须连续
D.连续与否无所谓
26.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。
A.单向链表
B.单向循环链表
C.双向链表
D.双向循环链表
27.在一棵具有5层的满二叉树中结点数为（）
A.31
B.32
C.33
D.16
28.下述文件中适合于磁带存储的是（ ）。
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件
29.以下说法错误的是（ ）。
A.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B.若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点
C.二叉树的前序遍历和后序遍历并不能唯一地确定这棵树，因为不能确定树的根结点
D.在前序遍历二叉树的结点序列中，任一结点其子树的结点都直接跟在该结点之后
30.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。
A.8
B.7
C.6
D.5
二、 判断题 (共 20 道试题,共 40 分)
1.哈夫曼树中有度数为1的结点。
A.错误
B.正确
2.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（ ）
A.错误
B.正确
3.对连通图进行深度优先遍历可以访问到该图中的所有顶点。
A.错误
B.正确
4.希尔排序是不稳定的排序。（ ）
A.错误
B.正确
5.线性表的顺序存储结构比链式存储结构更好。
A.错误
B.正确
6.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
A.错误
B.正确
7.非空的双向循环链表中任何结点的前驱指针均不为空。
A.错误
B.正确
8.一般树和二叉树的结点数目都可以为0。 ( )
A.错误
B.正确
9.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）
A.错误
B.正确
10.中序遍历二叉排序树可以得到一个有序的序列。
A.错误
B.正确
11.具有n个结点的完全二叉树的高度为┖log2n┘+1。
A.错误
B.正确
12.对链表进行插入和删除操作时不必移动链表中结点。
A.错误
B.正确
13.中序遍历一棵二叉排序树可以得到一个有序的序列。
A.错误
B.正确
14.哈夫曼树中没有度数为1的结点。
A.错误
B.正确
15.在B+树中查找和在B-树中查找的过程完全相同。 ( )
A.错误
B.正确
16.二分查找法要求待查表的关键字值必须有序。（ ）
A.错误
B.正确
17.希尔排序算法的时间复杂度为O(n2)。
A.错误
B.正确
18.如果某种排序算法不稳定，则该排序方法就没有实用价值。（ ）
A.错误
B.正确
19.调用一次深度优先遍历可以访问到图中的所有顶点。
A.错误
B.正确
20.通常使用两个类来协同表示单链表，即链表的结点类和链表类。
A.错误
B.正确
喜欢
0
赠金笔