《西北工业大学21秋《数据结构》复习考核试题库答案参考套卷47》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》复习考核试题库答案参考套卷47（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构复习考核试题库答案参考1. 一个有向无环图的拓扑排序序列( )是唯一的。A.可能B.不一定C.三者均不对D.一定参考答案：B2. 算法分析的两个主要方面是( )。A.正确性与健壮性B.时间复杂度与空间复杂度C.数据复杂性与程序复杂性D.可读性与可用性参考答案：B3. 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为( )。A.5B.6C.8D.9参考答案：A4. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A5. 含n个顶点的无向连通图中至少含有n条边。( )A、错误B、正确参考
2、答案：A6. 右图中的拓扑序列为( )A.C1，C2，C6，C7，C5，C4，C3B.C1，C2，C6，C3，C4，C5，C7C.C1，C4，C2，C3，C5，C6，C7D.C5，C7，C4，C1，C2，C6，C3参考答案：D7. 设s1=“abc”，则strlen(s1)=( )。A.3B.2C.1D.0参考答案：A8. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head，则( )。A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D9. 下列四种排序中( )的空间复杂度最大。A.插入排序B.冒
3、泡排序C.堆排序D.归并排序参考答案：C10. 四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU，x)操作后，队头元素是( )。A.YB.XC.VD.U参考答案：C11. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B12. 与单链表相比，双链表的优点之一是( )。A.插入、删除操作更简单B.可以进行随机访问C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活参考答案：C13. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC.dceabD.
4、abcde参考答案：C14. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C15. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A16. 线性表的顺序存储结构是一种( )存储结构。A.散列存取B.顺序存取C.随机存取D.索引存取参考答案：C17. n个结点的线索二叉树上含有的线索数为( )。A.n-1B.n+1C.nD.2n参考答案：B18. 按层次次序将一颗有n个结点的完全二叉树的所有结点从1到n编号，当iA.2i-1B.2iC.2i+1D.不确定参考答案：B19. 具有n个结点
5、的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A20. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )。A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA参考答案：B21. 下列存储表示中，哪一个不是树的存储形式( )。A.双亲表示法B.孩子链表表示法C.顺序存储表示法D.孩子兄弟表示法参考答案：C22. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。A.逆拓扑有序B.拓扑有序C.无序的D.A和B参考答案：A23. 任何一个无向连通图的最小生成树( )。A.只有一棵B
6、.有一棵或多棵C.一定有多棵D.可能不存在参考答案：B24. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B25. 线性表(a1，a2，.，an)以链式方式存储，访问第i位置元素的时间复杂度为( )。A.O(0)B.O(1)C.O(n)D.O(n2)参考答案：C26. 具有线性结构的数据结构是( )A.赫夫曼树B.栈C.图D.树参考答案：B27. 数组的逻辑结构不同于下列( )的逻辑结构。A.线性表B.栈C.队列D.树参考答案：D28. 由带权为9，2，5，7的四个叶子结点构造一颗哈夫曼树，该
7、树的带权路径长度为( )。A.23B.37C.46D.44参考答案：D29. 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为( )。A.3B.2C.4D.5参考答案：C30. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现6个不同的出栈序列。( )A、错误B、正确参考答案：A31. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A32. 串S=”I am a worker的长度是10。( )A、错误B、正确参考答案：A33. 下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储必须占用一片
8、连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：D34. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为( )。A.9B.10C.11D.12参考答案：C35. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案：B36. 在对链队列作出队操作时，不会改变front指针的值。( )A、错误B、正确参考答案：A37. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参
9、考答案：A38. 下面关于串的叙述中，哪一个是不正确的?( )A.空串是由空格构成的串B.模式匹配是串的一种重要运算C.串是字符的有限序列D.串既可以采用顺序存储，也可以采用链式存储参考答案：A39. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A40. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案：ABCD41. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答案：A42. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。( )A.正确B
10、.错误参考答案：A43. 在长度为n的顺表表的第i个位置上插入一个元素(1in+1)，元素的移动次数为( )。A.n-i+1B.n-iC.iD.i-1参考答案：C44. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B45. 广义表(a，b，c，d)的表头是( )。A.(b，c，d)B.(a，b，c，d)C.aD.(a)参考答案：B46. 已知函数Sub(s,I,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=SCIENCESTUDY，则调用函数Scopy(P,Sub(S,1,7)后得到( )。
11、A、P=SCIENCEB、P=STUDYC、S=SCIENCED、S=STUDY参考答案：A47. 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A987的存储地址是501。( )A、错误B、正确参考答案：A48. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是( )。A.10B.11C.12D.15参考答案：A49. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的( )。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法参考答案：C50. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A
