《西北工业大学21秋《数据结构》综合测试题库答案参考42》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》综合测试题库答案参考42（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构综合测试题库答案参考1. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A.1234B.4132C.4231D.4213参考答案：C2. 一个具有4个顶点的无向完全图有6条边。( )A、错误B、正确参考答案：B3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( )。A.9B.11C.15D.不能确定参考答案：C4. 在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为( )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)参考答案：B5. 下列
2、关于数据结构基本概念的叙述中，正确的是( )。A.数据的逻辑结构分为表结构和树结构B.数据的存储结构分为线性结构和非线性结构C.数据元素是数据的基本单位D.结点是有独立含义的数据最小单位参考答案：C6. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A7. 以下关于线性表的说法不正确的是( )。A.线性表中的数据元素可以是数字、字符、记录等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每个结点都有且只有一个直接前趋和直接后继D.存在这样的线性表：表中各结点都没有直接前趋和直接后继参考答案：C8. 用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存
3、储器D.光盘参考答案：A9. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A10. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D11. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B12. 下列说法中，不正确的是( )。A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成参考答案：D13. 假设一棵完全二叉树含1000个结点,则其中度为2的结点数为512个。( )
4、A、错误B、正确参考答案：A14. 若用n表示图中顶点数目，则有( )条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C15. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是( )。A.r=r-nextB.r=f-nextC.f=r-nextD.f=f-next参考答案：D16. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为k。( )A、错误B、正确参考答案：A17. 如果某种排序算法是不稳定的，则这种算法不可用。( )A.正确B.错误参考答案：A18. 具有线性结构的数据结构是(
5、 )A.赫夫曼树B.栈C.图D.树参考答案：B19. 允许对队列进行的操作有( )。A.对队列中的元素排序B.取出最近进队的元素C.在队头元素之前插入元素D.删除队头元素参考答案：D20. 空格串的长度是空格的个数。( )A、错误B、正确参考答案：B21. 在含100个结点的完全二叉树中，叶子结点的个数为36。( )A、错误B、正确参考答案：A22. 对于3个结点a、b、c，可构成不同的二叉树的棵数为( )。A.32B.30C.28D.24参考答案：B23. 算法有以下几种特性( )。A、有穷性B、确定性C、可行性D、输入和输出参考答案：ABCD24. 分块查找在等概率查找情况下，其平均查找长
6、度不仅与表中元素个数有关，而且与每块中的元素个数有关。( )A.正确B.错误参考答案：A25. 串S=”I am a worker的长度是10。( )A、错误B、正确参考答案：A26. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A27. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行( )A.q-next=p-next;p=qB.p-next=q-next;q=pC.q-next=p-next;p-next=qD.p-next=q-next;q-next=p参考答案：D28. 深度为1
7、5的满二叉树上，第11层有211个结点。( )A、错误B、正确参考答案：A29. 一棵树可以只有1个结点。( )A、错误B、正确参考答案：B30. 内部排序是根据关键词的大小重新安排各( )的顺序。A.关键词B.数据项C.文件D.数据元素参考答案：B31. 二叉树是度为2的有序树。( )A、错误B、正确参考答案：A32. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )A.正确B.错误参考答案：A33. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插
8、入排序B.归并排序C.冒泡排序D.堆排序参考答案：A34. 产生冲突现象的两个关键字称为该散列函数的同义字。( )A、错误B、正确参考答案：B35. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B36. 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：( )A.s-next=p-next; p-next=sB.s-next=p; q-next=sC.q-next=s; s-next=pD.p-next=s; s-next=q参考答案：B37. 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。(
9、 )A、错误B、正确参考答案：A38. 对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为98。( )A、错误B、正确参考答案：B39. 非空的双向循环链表中任何结点的前驱指针均不为空。( )A.正确B.错误参考答案：A40. 若一个有向图的邻接距阵中，主对角线以下的元素均为零，则该图的拓扑有序序列( )。A.一定存在B.一定不存在C.不一定存在D.不确定参考答案：A41. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是( )。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表参考答案：A42. 链接存储结
10、构属静态存储方式。( )A.正确B.错误参考答案：B43. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。( )A.正确B.错误参考答案：B44. 向一个有127个元素原顺序表中插入一个新元素并保存原来顺序不变，平均要移动( )个元素。A.8B.63.5C.63D.7参考答案：B45. 若已知一个栈序列是1，2，3，.，n，其输出序列为p1，p2，p3，.，pn，若p1=n，则pi为( )。A.iB.n-iC.n-i+1D.不确定参考答案：C46. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、1
11、6C、17D、18参考答案：D47. 设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有( )个空指针域。A.2m-1B.2mC.2m+1D.4m参考答案：B48. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。A.插入B.选择C.交换D.二路归并参考答案：A49. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A50. 结构就是用户定义的，( )的一个集合体。参考答案：不同数据类型51. 若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t
12、)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为( )。A.f，c，bB.f，d，bC.g，c，bD.g，d，b参考答案：A52. 若哈希表(散列表)的负载因子l，则可避免冲突的产生。( )A.正确B.错误参考答案：B53. 线性表的链接实现有利于( )运算。A.插入B.读表元C.查找D.定位参考答案：A54. 以下( )不是队列的基本运算。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值参考答案：B55. 线性表是具有n个( )的有限序列。A.字符B.数据元素C.数据项D.表元素参考答案：B56. 一个有向无环图的拓扑排序序列是( )
13、。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对参考答案：C57. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行( )。A.s-next=p-next; p-next=sB.q-next=s; s-next=pC.p-next=s; s-next=qD.p-next=s-next; s-next=p参考答案：B58. 若一棵满三叉树中含有121个结点，则该树的深度为6。( )A、错误B、正确参考答案：A59. 对长度为n的关键字序列进行堆排序的空间复杂度为( )。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)参考答案：B60. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
