西北工业大学22春《数据结构》补考试题库答案参考16

《西北工业大学22春《数据结构》补考试题库答案参考16》由会员分享，可在线阅读，更多相关《西北工业大学22春《数据结构》补考试题库答案参考16（11页珍藏版）》请在装配图网上搜索。

1、西北工业大学22春数据结构补考试题库答案参考1. 对无序表用折半查找比顺序查找快。( )A.正确B.错误参考答案：B2. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C3. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B4. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C5. 某二叉树的前序和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点B.高度等于其结点数C

2、.任一结点无左孩子D.任一结点无右孩子参考答案：A6. 已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为( )。A.2B.3C.8D.9参考答案：C7. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A8. 链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操

3、作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B9. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A10. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B11. 一个队列的入队序列是1、2、3、4，则队列的首次输出元素是( )。A.1B.2C.3D.4参考答案：A12. 在目标串T0.n-1=“xwxxyxy”中，对模式串P0.m-1=“xy”进行子串定位操作的结果是( )。A.1B.2C.3D.5参考答案：C13. 数组是同类型值的集合。( )A.正确B.

4、错误参考答案：B14. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A15. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。A.0B.1C.2D.3参考答案：B16. 连通网的最小生成树是其所有生成树中( )。A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树参考答案：D17. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C18. 若一个算法中的语句频度之和为T(n)=3720n+4nl

5、ogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A19. 两个串相等的充分必要条件是两个串的长度相等且字母相同。( )A、错误B、正确参考答案：B20. 一个关键字序列为46，79，56，38，40，84，采用快速排序以位于最左位置的元素为基准而得到的第一次划分结果为( )A.38，46，79，56，40，84B.38，79，56，46，40，84C.40，38，46，56，79，84D.38，46，56，79，40，84参考答案：C21. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：

6、C22. 二叉树中必有度为2的结点。( )A、错误B、正确参考答案：A23. 假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为abbccddedc。( )A、错误B、正确参考答案：A24. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C25. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-nextD.f=f-next参考答案：D26. 数据的逻辑结构在计算机存

7、储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A27. 二叉树中结点只有一个孩子时无左右之分。( )A、错误B、正确参考答案：A28. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D29. 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。( )A、错误B、正确参考答案：B30. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。( )A、错误B、正确参考答案：B31. 设串

8、sl=DataStructureswithJava，s2=it，则子串定位函数index(s1,s2)的值为( )A.15B.16C.17D.18参考答案：D32. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考答案：A33. 栈和队列都是限制存取点的线性结构。( )A.正确B.错误参考答案：A34. 数据的不可分割的最小标识单位是( )。A.数据项B.数据记录C.数据元素D.数据变量参考答案：A35. 一个有向无环图的拓扑排序序列是( )。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C36. 队列允许在队尾删除，在队头插入。( )A.正确B.错误参考

9、答案：A37. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A38. 一个具有767个结点的完全二叉树，其叶子结点个数为( )。A.383B.384C.385D.386参考答案：B39. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案：ABCD40. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用( )。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法参考答案：B41. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( )A.正确B.错误参考答案：B42. 最大容量为n的循环队列，

10、队尾指针是rear，队头是front，则队空的条件是( )。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B43. 深度为15的满二叉树上，第11层有211个结点。( )A、错误B、正确参考答案：A44. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是( )。A.6B.4C.3D.2参考答案：C45. 深度为5的二叉树至多有( )个结点。A.16B.32C.31D.10

11、参考答案：C46. 队列的队尾位置通常是随着入队操作而变化的。( )A、错误B、正确参考答案：B47. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A48. 如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是( )。A.顺序查找B.折半查找C.基于属性的查找D.分块查找参考答案：D49. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共( )个，单链表为( )个。A.4，1B.4，2C.1，4D.2，4参考答案：B50. 结构的存储密度定义为数据本身所占的存储量与整个结构所占的存储量之比。( )A.正确B.错误参考答案：A