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

第一部分1.在一个单链表中，已知指针p 指向其中的某个结点，若在该结点前插入一个由指针s 指向的结点，则需执行（ ）。As-next = p-next; p-next = s; Bp-next = s; s-next = p;C r = p-next; p-next = s; s-next = r; D仅靠已知条件无法实现2.设顺序表长度为n，从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是（ ）。A(n1)/2 Bn/2 Cn(n 1)/2 Dn(n + 1)/23.在一个具有n 个单元的顺序栈中，假定以高端（即第n1 单元）作为栈底，以top 为栈顶指针，则当作出栈运算时，top 变化为（ ）。Atop 不变 Btop = 0 Ctop- Dtop +4.若一个栈以向量Vn存储，设栈空时，栈顶指针top 为n1，则下面x 进栈的正确操作是（ ）。Atop = top + 1；Vtop = x BVtop = x；top = top + 1Ctop = top 1；Vtop = x DVtop = 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. a Bb Cc Dd6.若一棵二叉树有126 个节点，在第7 层（根结点在第1 层）的结点个数至多有（ ）。A32 B64 C63 D不存在第7 层7.具有n 个顶点的有向图的边最多有（ ）。An Bn(n1) Cn(n+1) Dn28.设连通图G 的顶点数为n，则G 的生成树的边数为（ ）。An Bn1 C2n D2n19.散列查找中k 个关键字具有同一哈希值，若用线性探测法将这k 个关键字对应的记录存入哈希表中，至少要进行（ ）次探测。Ak Bk + 1 Ck(k + 1)/2 D.1 + k(k + 1)/2 10.一组记录的关键字为(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 个初始归并段，若要使多路归并三趟完成排序，则应取归并的路数至少为多少？（ ）。A2 B3 C4 D5第二部分1. 判断带头结点的线性链表L 是否为空的条件是（ ）。AL.elem=NULL BL.length = 0 CL-next=NULL DL = NULL2. 设有多项式A 和B 的项数分别为m 和n ，均采用单链表表示，进行A 加B 运算的时间复杂度为（ ）。AO(m )（当mn 时） BO(n)（当nm 时） CO(m + n) DO(m *n)3.若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3。当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（ ）。A1 和5 B2 和4 C4 和2 D5 和14.在具有n 个单元的顺序存储的循环队列中，假定front 和rear 分别为队头指针和队尾指针，则队空的条件为（ ）。Arear=front B(rear+1)%n=frontC(rear1)%n=front D(front+1)%n=rear5.将一个A1.100，1.100的三对角矩阵以行序为主存入一维数组B1.298中，元素a66，65 B 数组中的位置k 等于（ ）。A198 B197 C196 D1956.由3 个结点可以构造出（ ）种不同形态的二叉树。A3 B4 C5 D67.无向图G 是一个连通图，有9 条边，则该图的顶点个量至少为（ ）。A4 B5 C6 D78.采用顺序检索的方法检索长度为n 的线性表，则检索每个元素的平均比较次数为（ ）。An Bn2 C(n + 1)/2 Dlog2(n + 1)9.表长为25 的散列表，如果采用除留余数法，即按公式H(key) = key mod p 建立哈希函数，则最适宜的p 取值应为（ ）。A23 B24 C25 D2610.一组记录的关键字为20，15，14，18，21，36，40，10，则利用快速排序的方法，以第一个记录为基准得到一次划分结果是（ ）。A10，15，14，18，20，40，36，21 B10，15，14，18，20，36，40，21C10，15，14，20，18，40，36，21 D15，10，14，18，20，36，40，2111. 以下关于排序方法的描述，不正确的是（ ）。A排序是将一组记录的任意序列，调整为按关键字“有序”的序列B排序方法都是不稳定的C排序方法可以分为内部排序和外部排序D排序中需要比较关键字的大小第三部分1.对于线性链表，在p 所指向的结点后插入由q 指向的新结点的语句序列是（ ）。Ap-next = q; q -next = p-next; Bq = p-next; p-next = q;Cq-next = p-next; p-next = q; Dp = p-next; q-next = p;2.向一个栈顶指针为h 的带头结点链栈中插入指针s 所指的结点时，应执行的语句序列是（ ）。Ahnext = s； Bs-next = h；Csnext = h；h = hnext； Dsnext = hnext；hnext = s；3.设有一个栈，元素的进栈次序为A，B，C，D，E，下列中不可能的出栈序列是（ ）。AA，B，C，D，E BB，C，D，E，ACE，A，B，C，D DE，D，C，B，A4.在一个无头结点的链队列中，假定front 和rear 分别为队头和队尾指针，则删除一个结点的主要操作为（ ）。Afront = frontnext Brear = rearnextCrear = frontnext Dfront = rearnext5.若用一维数组保存一个深度为5、结点个数10 的二叉树，数组的长度至少为（ ）。A10 B16 C31 D646.假定在一棵二叉树中，双分支结点数为15 个，单分支结点数为30 个，则叶子结点数为（ ）个。A15 B16 C17 D477.在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（ ）。AG 中有弧 BG 中有一条从Vi 到Vj 的路径CG 中没有弧 DG 中有一条从Vj 到Vi 的路径8.在对长度为n 的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（ ）。An Bn2 Clog2(n + 1) 1 D(n + 1)/29.若对n 个元素进行堆排序，则在初始建堆的过程中需要进行（ ）次筛选。A1 Bn/2 C(n1)/2 Dn10.有一组数据（15，9，7，8，20，1，7，4），用堆排序的筛选方法建立的初始堆为（ ）。A1，4，8，9，20，7，15，7 B1，7，15