数据结构模拟考研冲刺三套卷

数据结构模拟考研冲刺三套卷数据结构模拟考研冲刺三套卷数据结构模拟考研冲刺三套卷数据结构模拟考研冲刺三套卷编制仅供参考审核批准生效日期地址：电话：传真:邮编:第一部分1.在一个单链表中，已知指针p指向其中的某个结点，若在该结点前插入一个由指针s指向的结点，则需执行（）。A．s->next=p->next;p->next=s;B．p->next=s;s->next=p;C．r=p->next;p->next=s;s->next=r;D．仅靠已知条件无法实现2.设顺序表长度为n，从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是（）。A．(n−1)/2B．n/2C．n(n−1)/2D．n(n+1)/23.在一个具有n个单元的顺序栈中，假定以高端（即第n−1单元）作为栈底，以top为栈顶指针，则当作出栈运算时，top变化为（）。A．top不变B．top=0C．top--D．top++4.若一个栈以向量V[n]存储，设栈空时，栈顶指针top为n−1，则下面x进栈的正确操作是（）。A．top=top+1；V[top]=xB．V[top]=x；top=top+1C．top=top−1；V[top]=xD．V[top]=x；top=top−15.经过以下栈运算后，x的值是（）。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Push(s,c);Pop(s,x);GetTop(s,x);A.aB．bC．cD．d6.若一棵二叉树有126个节点，在第7层（根结点在第1层）的结点个数至多有（）。A．32B．64C．63D．不存在第7层7.具有n个顶点的有向图的边最多有（）。A．nB．n(n−1)C．n(n+1)D．n8.设连通图G的顶点数为n，则G的生成树的边数为（）。A．nB．n−1C．2nD．2n−19.散列查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行（）次探测。A．kB．k+1C．k(k+1)/2+k(k+1)/210.一组记录的关键字为(45，80，55，40，42，85)则利用堆排序的方法建立的初始堆为（）。A．(80，45，55，40，42，85)B．(85，80，55，40，42，45)C．(85，80，55，45，42，40)D．(85，55，80，42，45，40)11.假设某文件经内部排序得到100个初始归并段，若要使多路归并三趟完成排序，则应取归并的路数至少为多少（）。A．2B．3C．4D．5第二部分1.判断带头结点的线性链表L是否为空的条件是（）。A．=NULLB．=0C．L->next=NULLD．L=NULL2.设有多项式A和B的项数分别为m和n，均采用单链表表示，进行A加B运算的时间复杂度为（）。A．O(m)（当m>n时）B．O(n)（当n>m时）C．O(m+n)D．O(m*n)3.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A．1和5B．2和4C．4和2D．5和14.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则队空的条件为（）。A．rear==frontB．(rear+1)%n==frontC．(rear−1)%n=frontD．(front+1)%n==rear5.将一个A[1..100，1..100]的三对角矩阵以行序为主存入一维数组B[1..298]中，元素a[66，65]B数组中的位置k等于（）。A．198B．197C．196D．1956.由3个结点可以构造出（）种不同形态的二叉树。A．3B．4C．5D．67.无向图G是一个连通图，有9条边，则该图的顶点个量至少为（）。A．4B．5C．6D．78.采用顺序检索的方法检索长度为n的线性表，则检索每个元素的平均比较次数为（）。A．nB．nC．(n+1)/2D．log(n+1)9.表长为25的散列表，如果采用除留余数法，即按公式H(key)=keymodp建立哈希函数，则最适宜的p取值应为（）。A．23B．24C．25D．2610.一组记录的关键字为{20，15，14，18，21，36，40，10}，则利用快速排序的方法，以第一个记录为基准得到一次划分结果是（）。A．10，15，14，18，20，40，36，21B．10，15，14，18，20，36，40，21C．10，15，14，20，18，40，36，21D．15，10，14，18，20，36，40，2111.以下关于排序方法的描述，不正确的是（）。A．排序是将一组记录的任意序列，调整为按关键字“有序”的序列B．排序方法都是不稳定的C．排序方法可以分为内部排序和外部排序D．排序中需要比较关键字的大小第三部分1.对于线性链表，在p所指向的结点后插入由q指向的新结点的语句序列是（）。A．p->next=q;q->next=p->next;B．q=p->next;p->next=q;C．q->next=p->next;p->next=q;D．p=p->next;q->next=p;2.向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行的语句序列是（）。A．h→next=s；B．s->next=h；C．s→next=h；h=h→next；D．s→next=h→next；h→next=s；3.设有一个栈，元素的进栈次序为A，B，C，D，E，下列中不可能的出栈序列是（）。A．A，B，C，D，EB．B，C，D，E，AC．E，A，B，C，DD．E，D，C，B，A4.在一个无头结点的链队列中，假定front和rear分别为队头和队尾指针，则删除一个结点的主要操作为（）。A．front=front→nextB．rear=rear→nextC．rear=front→nextD．front=rear→next5.若用一维数组保存一个深度为5、结点个数10的二叉树，数组的长度至少为（）。A．10B．16C．31D．646.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则叶子结点数为（）个。A．15B．16C．17D．477.在有向图G的拓扑序列中，若顶点V在顶点V之前，则下列情形不可能出现的是（）。A．G中有弧<V，V>B．G中有一条从V到V的路径C．G中没有弧<V,V>D．G中有一条从V到V的路径8.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。A．nB．nC．log(n+1)−1D．(n+1)/29.若对n个元素进行堆排序，则在初始建堆的过程中需要进行（）次筛选。A．1B．⎣n/2⎦C．(n−1)/2D．n10.有一组数据（15，9，7，8，20，−1，7，4），用堆排序的筛选方法建立的初始堆为（）。A．−1，4，8，9，20，7，15，7B．−1，