《西北工业大学21秋《数据结构》综合测试题库答案参考81》由会员分享，可在线阅读，更多相关《西北工业大学21秋《数据结构》综合测试题库答案参考81（13页珍藏版）》请在金锄头文库上搜索。
1、西北工业大学21秋数据结构综合测试题库答案参考1. 归并排序的辅助存储空间代价为O(1)。( )A.正确B.错误参考答案：B2. 如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为47。( )A、错误B、正确参考答案：B3. 一个加权的无向连通图的最小生成树( )。A.有一颗或多颗B.只有一颗C.一定有多颗D.可能不存在参考答案：A4. 栈下溢是指在栈空时进行出栈操作。( )A、错误B、正确参考答案：B5. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为( )A.O(nlog2e)B.O(n+e)C.O(ne)
2、D.O(n2)参考答案：B6. 具有n个结点的连通图至少有( )条边。A.n-1B.nC.n(n-1)/2D.2n参考答案：A7. 假设三维数组A1098按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A987的存储地址是501。( )A、错误B、正确参考答案：A8. 在一个单链表中，已知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参考答案：B9. 在对链队列作出队操
3、作时，不会改变front指针的值。( )A、错误B、正确参考答案：A10. AVL树是一种平衡的二叉排序树，树中任一结点的( )A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度参考答案：B11. 若让元素1，2，3依次进栈，则出栈次序不可能出现种情况( )A.3，2，1B.2，1，3C.3，1，2D.1，3，2参考答案：C12. 设s1=“abc”，则strlen(s1)=( )。A.3B.2C.1D.0参考答案：A13. 在二叉树中插入结点，则此二叉树便不再是二叉树了。( )A.正确B.错误参考答案：B14.
4、用ISAM组织文件适合于( )。A.磁盘B.磁带C.外存储器D.光盘参考答案：A15. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )。A.nB.2n-1C.2nD.n-1参考答案：A16. 设有100个数据元素，采用折半搜索时，最大比较次数为( )A.6B.7C.8D.10参考答案：B17. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p-next-next=head，则( )。A、p指向头结点B、p指向尾结点C、*p的直接后继是头结点D、*P的直接后继是尾结点参考答案：D18. 引入二叉线索树的目的是( )。A.加快查找结点的前驱或后继的速
5、度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A19. 数据项是数据的基本单位。( )A.正确B.错误参考答案：A20. 顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A21. 链接存储结构属静态存储方式。( )A.正确B.错误参考答案：B22. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是( )。A.单链表B.静态链表C.线性链表D.顺序存储结构参考答案：C23. 二叉树中结点只有一
6、个孩子时无左右之分。( )A、错误B、正确参考答案：A24. 数据的逻辑结构在计算机存储器内的表示，称为数据的逻辑结构。( )A、错误B、正确参考答案：A25. 邻接表法只能用于有向图存储。( )A.正确B.错误参考答案：B26. 下列陈述中正确的是( )。A.二叉树是度为2的有序树B.二叉树中结点只有一个孩子时无左右之分C.二叉树中必有度为2的结点D.二叉树中最多只有两棵子树，并且有左右之分参考答案：D27. 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( )A、错误B、正确参考答案：B28. 设某算法的问题规模函数f(n)=300n2+8000n+900，则它的渐进
7、时间复杂度为( )A.O(n3)B.O(n2)C.O(n)D.O(1)参考答案：B29. 若有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑有序序列( )。A.存在B.可能不存在C.不存在D.不一定存在参考答案：A30. AOV网的含义是以顶点表示活动的网。( )A.正确B.错误参考答案：A31. 对于哈希函数H(key)=key%13，被称为同义词的关键字是( )。A、35和41B、23和39C、15和44D、25和51参考答案：D32. 具有65个结点的完全二叉树其深度为(根的层次号为1)( )。A.8B.7C.6D.5参考答案：B33. 顺序存储方式的优点是存储密度大，且插入、删
8、除运算效率高。( )A.正确B.错误参考答案：B34. 已知函数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参考答案：A35. 从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为( )。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D36. 向顺序栈中压入新元素时，应当( )A.先移动栈顶位置，再存入元素B.
9、先存入元素，再移动栈顶位置C.先后 次序无关紧要D.同时进行参考答案：A37. 设有50行60列的二维数组A5060，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为( )。A.3700B.4376C.3900D.4620参考答案：D38. 如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为( )。A.插入排序B.归并排序C.冒泡排序D.堆排序参考答案：A39. 稀疏矩阵压缩存储后，必会失去随机存取功能。( )A.正确B.错误参考答案：A40. 线性表的唯一存储形式就是链表。( )A.正确B.错误参考答
10、案：A41. 高度为5的完全二叉树中含有的结点数至少为( )。A、16B、17C、31D、32参考答案：A42. 单链表中，增加一个头结点的目的是为了( )。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储参考答案：C43. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )A.O(log2n)B.O(n)C.O(1)D.O(2n)参考答案：A44. 数据结构是指( )。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A45. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关?( )A.直接选择排序B.
11、直接插入排序C.快速排序D.冒泡排序参考答案：A46. 队列的插入操作是在( )。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A47. 设串s1=Data Structures with Java，s2=it，则子串定位函数index(s1,s2)的值为( )。A、15B、16C、17D、18参考答案：D48. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。A.先序遍历B.中序遍历C.后序遍历D.按层遍历参考答案：C49. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。( )A.正确B.错误参考答案：A50. 若一个广义表的表头为空表，则此广义
12、表亦为空表。( )A.正确B.错误参考答案：B51. 删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )A、错误B、正确参考答案：A52. 任何一个递归过程都可以转换成非递归过程。( )A.正确B.错误参考答案：A53. 下面关于线性表的叙述错误的是( )。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现参考答案：D54. 队列的修改是按照先进先出的原则进行的。( )A、错误B、正确参考答案：B55. 取顺序表的第i个元素的时间与
13、i的大小无关。( )A.正确B.错误参考答案：A56. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。( )A.正确B.错误参考答案：A57. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( )A.正确B.错误参考答案：A58. 无向图中一个顶点的度是指图中( )。A、通过该顶点的简单路径数B、与该顶点相邻接的顶点数C、通过该顶点的回路数D、与该顶点连通的顶点数参考答案：B59. 归并排序是一种稳定的排序方法。( )A.正确B.错误参考答案：A60. 按排序过程中依据的原则分类，快速排序属于( )。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法
