数据结构选择复习测试卷

第页数据结构选择复习测试卷1.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。A、20，70，30，50B、30，88，70，50C、20，50D、30，88，50【正确答案】：A2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以【正确答案】：D3.在一个含有n个顶点的有向图中，最多会有()条边。A、n-1B、nC、n(n-1)D、n+1【正确答案】：C4.一棵完全二叉树上有5000个结点，其中叶子结点的个数是（）。A、2500B、2501C、2499D、2450【正确答案】：A5.二叉树的第k层的结点数最多为()个。A、2k-1B、2K+1C、2K-1D、2^(K-1)【正确答案】：D6.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是（）。A、39B、52C、111D、119【正确答案】：C7.设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A、1和1B、1和3C、1和2D、2和3【正确答案】：C8.以下数据结构中，（）是非线性数据结构。A、树B、字符串C、队列D、栈【正确答案】：A9.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()A、O（1）B、O（n）C、O（1og2n）D、O（n2）【正确答案】：C10.用链接方式存储的队列，在进行插入运算时（）。A、仅修改头指针B、头、尾指针都要修改C、仅修改尾指针D、头、尾指针可能都要修改【正确答案】：D11.若用数组A[0„5]来实现循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A、3和4B、3和0C、5和0D、5和1【正确答案】：B12.算法的时间复杂度取决于()。A、问题规模B、待处理数据的初态C、编译程序的质量D、A和B【正确答案】：D13.链接存储的存储结构所占存储空间（）。A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B、只有一部分，存放结点值C、只有一部分，存储表示结点间关系的指针D、分两部分，一部分存放结点值，另一部分存放结点所占单元数【正确答案】：A14.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个。A、1B、2C、3D、4【正确答案】：D15.设哈希表长m=14,哈希函数h(key)=keymod11,表中已有4个元素，addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空，如果用二次探测法处理冲突，则关键字49的结点的地址是()。A、8B、3C、5D、9【正确答案】：D16.线性表L在（）情况下适用于使用链式结构实现。A、需经常修改L中的结点值B、需不断对L进行删除插入C、L中含有大量的结点D、L中结点结构复杂【正确答案】：B17.以下说法正确的是（）。A、串是一种特殊的线性表B、串的长度必须大于零C、串中的元素只能是字母D、空串就是空白串【正确答案】：A18.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。()A、688B、678C、692D．696【正确答案】：C19.若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）A、79,46,56,38,40,84B、84,79,56,38,40,46C、84,79,56,46,40,38D、84,56,79,40,46,38【正确答案】：B20.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A、存储结构B、存储实现C、逻辑结构D、运算实现【正确答案】：C21.若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84D、40,38,46,84,56,79【正确答案】：C22.G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A、7B、8C、9D、10【正确答案】：C23.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A、5B、6C、7D、8【正确答案】：A24.数据结构在计算机内存中的表示是指（）。A、数据的存储结构B、数据结构C、数据的逻辑结构D、数据元素之间的关系【正确答案】：A25.从逻辑上可以把数据结构分为（）两大类。A、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构【正确答案】：C26.下列关键字序列中，（）是堆。A、16,72,31,23,94,53B、94,23,31,72,16,53C、16,53,23,94,31,72D、16,23,53,31,94,72【正确答案】：D27.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()。A、1，2，3B、9，5，2，3C、9，5，3D、9，4，2，3【正确答案】：D28.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL【正确答案】：A29.设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维