《西北工业大学21春《数据结构》离线作业一辅导答案24》由会员分享，可在线阅读，更多相关《西北工业大学21春《数据结构》离线作业一辅导答案24（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21春数据结构离线作业一辅导答案1. 下面程序段的时间复杂度是( )。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)参考答案：D2. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C3. 若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A4. 具有线性结构
2、的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B5. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B6. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A7. 二叉树在线索化后，仍不能有效求解的问题是( )。A.后序线索二叉树中求后序后继B.前序线索二叉树中求前序后继C.中序线索二叉树中求中序后继D.中序线索二叉树中求中序前驱参考答案：A8. 数据元素及其关系在计算机存储器内的表示，称为数据的(
3、)。A.逻辑结构B.存储结构C.线性结构D.非线性结构参考答案：B9. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C10. 在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度( )。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B11. 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。( )A.正确B.错误参考答案：A12. 假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是( )A.O(
4、n)B.O(e)C.O(n+e)D.O(n*e)参考答案：C13. 下列程序段for(i=1; iA.O(1)B.O(0)C.O(1+n)D.O(n)参考答案：D14. 哈希表不需要进行比较便可以直接取得所查记录。( )A.正确B.错误参考答案：A15. 设有100个关键字，用折半查找法进行查找时，最大比较次数为( )。A.7B.6C.50D.25参考答案：A16. 采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。A.10B.25C.6D.625参考答案：B17. 一个有向无环图的拓扑排序序列( )是唯一的。A
5、.可能B.不一定C.三者均不对D.一定参考答案：B18. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：D19. 完全二叉树中的叶子结点只可能在最后两层中出现。( )A.正确B.错误参考答案：A20. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A21. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C22. 用链表表示线性表的优点是( )A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除
6、D.数据元素的物理顺序与逻辑顺序相同参考答案：C23. 二叉树是度为2的有序树。( )A、错误B、正确参考答案：A24. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )。A.4B.5C.8D.9参考答案：C25. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C26. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )A.正确B.错误参考答案：B27. n个顶点的强连通图中至少含有( )。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n
7、(n-1)条有向边参考答案：B28. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A29. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是( )。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)参考答案：B30. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )。A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案：B31. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rea
8、r和front的值分别为( )。A.1和5B.2和4C.4和2D.5和1参考答案：B32. 数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。( )A.正确B.错误参考答案：A33. 按照二叉树的定义，具有3个结点的二叉树有( )种。A.3B.4C.5D.6参考答案：C34. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A35. 队列的队尾位置通常是随着入队操作而变化的。( )A、错误B、正确参考答案：B36. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A37. 采用邻接表存储的图的深度优先遍历算法类似于二叉树
9、的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C38. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A39. 如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案：D40. 内部排序是根据关键词的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B41. 带行表的三元组表是稀疏矩阵的一种( )。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构参考答案：A42. 若输入序列为1，2，3，4，5，6，则通过一个栈可以
10、输出序列3，2，5，6，4，1。( )A.正确B.错误参考答案：A43. 一棵左右子树均不空的二叉树在前序线索化后，其中空的链域的个数是( )。A.不确定B.2C.1D.0参考答案：C44. 通用的处理哈希冲突的方法有( )。A、开放定址法B、再哈希法C、链地址法D、建立公共溢出区参考答案：ABCD45. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A46. 一个队列的入队序列是a、b、c、d，则队列的输出序列是( )。A.dcbaB.cbdaC.adcbD.abcd参考答案：D47. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。( )A.正确B.错误参考答案：A48. 一个有向无环图的拓扑排序序列是( )。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C49. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A50. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B
