《西北工业大学21春《数据结构》在线作业三满分答案24》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》在线作业三满分答案24（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构在线作业三满分答案1. 空格串的长度是空格的个数。( )A、错误B、正确参考答案：B2. 在有向图中，以顶点v为终点的边的数目称为v的入度。( )A、错误B、正确参考答案：B3. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )。A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案：B4. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D5. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A6. 非
2、空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A7. 已知广义表LS=(a，b，c)，(d，e，f)，运算head和tail函数取出元素e的运算是( )。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)参考答案：C8. 具有线性结构的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B9. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A10. 取顺序表的第i个元素的时间与i的大小无关。( )
3、A.正确B.错误参考答案：A11. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D12. 可以用队列实现数值转换算法。( )A.正确B.错误参考答案：A13. 抽象数据类型是指数据逻辑结构及与之相关的操作。( )A、错误B、正确参考答案：B14. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A15. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表
4、示的循环单链表D.单链表参考答案：C16. 顺序查找法适合于存储结构为( )的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储参考答案：B17. 队列的修改是按先进先出的原则进行的。( )A、错误B、正确参考答案：B18. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B19. 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A20. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B21. head指向的带表头结点的单链表为空
5、的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B22. 指针p所指的元素是双向循环链表L的尾元素的条件是( )。A.p=LB.p=NULLC.p-prior=LD.p-next=L参考答案：D23. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A24. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A25. 无向图的邻接矩阵可用一维数组存储。( )A.正确B
6、.错误参考答案：A26. 数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是( )。A.线性表B.树形结构C.广义表D.图结构参考答案：A27. 下面程序段的时间复杂度是( )。for(i=0; in; i+) for(j=1; jm; j+) Aij=0;A、O(n)B、O(m+n+1)C、O(m+n)D、O(m*n)参考答案：D28. 下面说法错误的是( )。 (1)算法原地工作的含义是指不需要任何额外的辅助空间; (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法; (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界; (4)同一
7、个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)参考答案：C29. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A30. 栈是一种操作受限的线性结构，其操作的主要特征是( )。A、先进先出B、后进先出C、进优于出D、出优于进参考答案：B31. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A32. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B
8、33. 设有50行60列的二维数组A5060，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为( )。A.3700B.4376C.3900D.4620参考答案：D34. 广义表运算式tail(a，b)，(c，d)的操作结果是( )。A.dB.c，dC.(c，d)D.(c，d)参考答案：D35. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B36. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B37. 在计算机
9、内实现递归算法时所需的辅助数据结构是( )。A、栈B、队列C、树D、图参考答案：A38. 一个具有767个结点的完全二叉树，其叶子结点个数为( )。A.383B.384C.385D.386参考答案：B39. 有关二叉树下列说法正确的是( )。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为2参考答案：B40. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B.发生改变C.不能确定D.不发生改变参考答案：D41. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，
10、其平均查找长度ASL为( )。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C42. 二叉树中结点只有一个孩子时无左右之分。( )A、错误B、正确参考答案：A43. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B44. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B45. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。( )A.正确B.错误参考答案：A46. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参考答案：A47. 在以单链表为存储结构的线性表中，
11、数据元素之间的逻辑关系用( )。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示参考答案：C48. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。( )A.正确B.错误参考答案：A49. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A50. 串是一种特殊的线性表，其特殊性体现在( )。A.数据元素是一个字符B.数据元素可以是多个字符C.可以顺序存储D.可以链接存储参考答案：A51. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是(
12、)。A.栈B.队列C.树D.图参考答案：C52. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。( )A.正确B.错误参考答案：A53. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)参考答案：B54. 不含任何字符的串称为空串。( )A、错误B、正确参考答案：B55. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A56. 链接存储结构属动态存储方式。( )A.正确B.错误参考答案：A57. 假设以S和X分别
13、表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为abbccddedc。( )A、错误B、正确参考答案：A58. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )。A.1.0B.2.9C.3.4D.5.5参考答案：B59. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。A.直接选择排序B.直接插入排序C.快速排序D.堆排序参考答案：C60. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.直接插入排序C.快速排序D.冒泡排序参考答案：A
