《西北工业大学21秋《数据结构》复习考核试题库答案参考套卷13》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》复习考核试题库答案参考套卷13（11页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构复习考核试题库答案参考1. 下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。A.直接插入排序B.冒泡排序C.快速排序D.堆排序参考答案：A2. 在一个单链表中，若删除*p结点的后继结点，则执行操作( )。A.q=p-next; p-next=q-next; free(q)B.p=p-next; p-next=p-next-next; free(p)C.p-next=q-next; free(p-next)D.p=p-next-next; free(p-next)参考答案：A3. 二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )A、错误B、
2、正确参考答案：B4. 数据的逻辑结构描述数据元素之间的逻辑关系，与存储方式无关。( )A、错误B、正确参考答案：B5. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A6. 若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为O(n)。( )A、错误B、正确参考答案：A7. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( )。A.栈B.队列C.树D.图参考答案：C8. 任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。A.稍有改变B
3、.发生改变C.不能确定D.不发生改变参考答案：D9. 中序遍历的递归算法平均空间复杂度为( )。A.2(n)B.n(2)C.0(n)D.2n参考答案：C10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )A.正确B.错误参考答案：B11. 数据结构是带有结构的数据元素的集合。( )A.正确B.错误参考答案：A12. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A13. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A14. 平衡二叉树的平衡因子只可能是-1、0、1。( )A.正确B.错误参考答案：A15. 栈和队列都是限制存取点的线性结构。( )A
4、.正确B.错误参考答案：A16. 邻接表法只能用于有向图存储。( )A.正确B.错误参考答案：B17. 一个好的算法有( )设计要求。A、正确性B、可读性C、健壮性D、效率与低存储量要求参考答案：ABCD18. 如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。A.单链表B.双链表C.单循环链表D.顺序表参考答案：D19. 若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为2/6。( )A、错误B、正确参考答案：B20. 已知完全二叉树T的第5层只有7个结点，则该树共有15个叶子结点。( )A、错误B、正确参考答案：A21. 在一个长度为n
5、的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为( )。A.nB.n/2C.(n+1)/2D.(n-1)/2参考答案：C22. 在二叉树的第i层上至多可以有2i个结点。( )A、错误B、正确参考答案：A23. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B24. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D25. Prim(普里姆)算法适用于求( )的网的最小生
6、成树; kruskal(克鲁斯卡尔)算法适用于求( )的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A26. 右图中的拓扑序列为( )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参考答案：D27. 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是( )A.XB.YC.ZD.W参考答案：C28. 线性链表是通过( )方式表示元素之间的关系A.后继元素地址B.元素的存储顺序
7、C.左、右孩子地址D.元素的相对存储位置参考答案：A29. head指向的带表头结点的单链表为空的判定条件是( )。A.head-next=headB.head-next=NULLC.head=NULLD.head!=NULL参考答案：B30. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，8，列下标为j=1，2，10。设每个字符占一个字节，若按行先存储，元素A8，5的起始地址与A按列存储时起始地址相同的元素是( )。A.A8，5B.A3，10C.A5，8D.A0，9参考答案：B31. 一个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。A.edcbaB.decbaC
8、.dceabD.abcde参考答案：C32. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值?( )A.最小概率B.最大概率C.平均概率D.同等概率参考答案：D33. 快速排序是排序算法中平均性能最好的一种排序。( )A.正确B.错误参考答案：A34. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表参考答案：C35. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。A.(n-1)2B.n2C.(n+1)2
9、D.n参考答案：C36. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A37. 若有18个元素的有序表存放在一堆数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为( )。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3参考答案：D38. 顺序查找法适合于存储结构为( )的线性表。A.散列存储B.顺序存储或链式存储C.压缩存储D.索引存储参考答案：B39. 链表不具备的特点是( )。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A4
10、0. 空格串的长度是空格的个数。( )A、错误B、正确参考答案：B41. 在队列中，允许进行删除操作的一端称为队尾。( )A、错误B、正确参考答案：B42. 在一个图中所有顶点的度数之和等于所有边数的( )倍。A.1/2B.2C.1D.4参考答案：B43. 算法分析的两个主要方面是( )。A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性参考答案：A44. 字符串“sgabacbadfgbacst”中存在有6个与字符串“ba”相同的子串。( )A、错误B、正确参考答案：A45. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B46. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D47. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B48. 在指定结点之前插入新结点时，双链表比单链表更方便。( )A.正确B.错误参考答案：A49. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A50. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )A、错误B、正确参考答案：A
