《数据结构试卷及答案》由会员分享，可在线阅读，更多相关《数据结构试卷及答案（61页珍藏版）》请在金锄头文库上搜索。
1、选择题（查找排序不考)1下面关于线性表的叙述错误的是（ D ）。(A) 线性表采用顺序存储必须占用一片连续的存储空间（B) 线性表采用链式存储不必占用一片连续的存储空间（C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。（A) 2m-1(B) 2m(C) 2m+1（D) 4m3设顺序循环队列Q0：M1的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为( C ）。(A)
2、R-F（B） F-R(C) (R-F+M)M（D） (F-R+M）M4设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）.(A） BADC（B） BCDA（C） CDAB（D） CBDA5设某完全无向图中有n个顶点,则该完全无向图中有（ A ）条边。（A） n（n-1)/2(B) n（n-1）(C) n2 （D） n2-16设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。(A) 9（B) 10(C） 11(D) 127设某有向图中有n个顶点,则该有向图对应的邻接表中有（ B）个表头结点。（A） n1(B） n(C) n+1（D
3、) 2n18设一组初始记录关键字序列（5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（ C )。（A） 2,3，5，8,6(B） 3，2,5，8，6(C) 3，2，5，6，8(D) 2，3,6，5，81.D2.B3.C4。A5。A6.C7.B8。C1设某数据结构的二元组形式表示为A=(D，R），D=01，02，03,04,05，06，07，08，09,R=r，r=01,02，,02，05,02，06，03，08，next;p-data=qdata；p-next=qnext;free（q）；（B） q=pnext；q-data=p-data；pnext=q-next；f
4、ree（q)；(C) q=pnext;p-next=qnext;free(q)；（D） q=p-next;p-data=q-data；free(q);4设有n个待排序的记录关键字，则在堆排序中需要（ A ）个辅助记录单元.(A) 1（B) n（C） nlog2n（D) n25设一组初始关键字记录关键字为（20，15，14,18,21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为（ A）.(A） 10，15,14，18，20，36，40，21(B） 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l（D) 15，10，14，
5、18,20，36，40，216设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为( B ）.（A） O（1)（B) O（log2n)(C）O(n）(D） O（n2）7设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ).（A） n，e（B） e，n（C） 2n，e(D) n，2e8. 设某强连通图中有n个顶点，则该强连通图中至少有（ C ）条边。(A) n（n-1)（B） n+1（C） n(D) n(n+1)9设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列( B )方法可以达到此目的.（A) 快速排序
6、(B) 堆排序(C) 归并排序（D) 插入排序10.下列四种排序中( D )的空间复杂度最大.(A) 插入排序(B) 冒泡排序（C） 堆排序（D) 归并排序1。B2。B3.A4.A5。A6。B7。D8。C9.B10.D1设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ C）。（A） O（n)(B) O（nlog2n）(C） O（1)(D） O（n2)2设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点.（A) 2k+1（B) 2k(C) 2k1(D） 2k13设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ D）。(A) n（B） e(C) 2n(D
7、) 2e4在二叉排序树中插入一个结点的时间复杂度为（ B ）。(A) O(1）(B） O(n)（C) O（log2n)(D) O（n2）5设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ C)条有向边。(A) n(B) n1（C) m（D） m-16设一组初始记录关键字序列为(345，253，674，924，627）,则用基数排序需要进行（A）趟的分配和回收才能使得初始关键字序列变成有序序列。(A） 3(B) 4(C） 5（D） 87设用链表作为栈的存储结构则退栈操作(B ）.(A) 必须判别栈是否为满（B） 必须判别栈是否为空（C） 判别栈元素的类型（D） 对栈不作任何判别8下列
8、四种排序中（A）的空间复杂度最大。(A） 快速排序（B) 冒泡排序（C） 希尔排序（D） 堆9设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl,度数为2的结点数为N2,则下列等式成立的是（C）。(A） N0=N1+1(B） N0=Nl+N2(C) N0=N2+1(D） N0=2N1+l10。设有序顺序表中有n个数据元素,则利用二分查找法查找数据元素X的最多比较次数不超过( A）。（A） log2n+1（B) log2n-1(C） log2n（D) log2(n+1)1C2D3D4B5C 6A7B8A9C10A1数据的最小单位是（A ）。(A） 数据项(B) 数据类型(C) 数据元素（
9、D） 数据变量2设一组初始记录关键字序列为(50，40，95，20，15，70，60，45）,则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ B ）。（A) 40，50，20,95（B） 15，40，60，20(C） 15，20，40，45（D） 45，40，15,203设一组初始记录关键字序列为（25，50，15，35，80，85，20,40，36，70),其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ A ）。(A） 15，25,35，50，20,40，80，85，36，70（B） 15，25，35，50，80，20,85,40，70，
10、36(C） 15，25，35，50,80，85，20，36,40,70(D) 15，25，35，50,80，20,36，40，70，854函数substr(“DATASTRUCTURE”，5,9)的返回值为（A )。(A) “STRUCTURE(B) “DATA”（C) “ASTRUCTUR（D) “DATASTRUCTURE5设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D）。（A) O(log2n）(B) O（1）（C） O(n2）(D） O（n)6设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为m的结点数为Nm，
11、则N0=（B ）。（A） Nl+N2+Nm(B) l+N2+2N3+3N4+（m1）Nm(C) N2+2N3+3N4+（m1）Nm（D) 2Nl+3N2+（m+1)Nm7设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B）次。（A） 25(B) 10（C） 7(D） 18设连通图G中的边集E=（a，b），(a，e），(a,c），（b，e），（e，d）,(d,f），（f,c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ B）。(A） abedfc（B) acfebd（C） aebdfc(D） aedfcb9设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个元素
12、是n,则输出序列中第i个输出元素是（C ）。（A） ni(B) n-1i(C） n+1i（D） 不能确定10。 设一组初始记录关键字序列为(45,80，55，40,42，85），则以第一个记录关键字45为基准而得到一趟快速排序的结果是（C）。(A） 40，42，45,55，80，83（B） 42，40,45，80,85,88(C) 42，40，45，55,80，85(D) 42,40，45，85，55,801A2B3A4A5D 6B7B8B9C10C1 设一组权值集合W=2,3,4,5，6，则由该权值集合构造的哈夫曼树中带权路径长度之和为（D ).(A） 20(B) 30（C) 40(D) 4
13、52执行一趟快速排序能够得到的序列是(A ）。(A） 41，12，34，45,27 55 72，63（B） 45，34,12，41 55 72，63，27(C) 63，12，34，45，27 55 41，72(D) 12,27，45,41 55 34，63,723设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A）。（A） head=0（B) head-next=0(C） headnext=head(D） head!=04时间复杂度不受数据初始状态影响而恒为O（nlog2n）的是（A ）.(A） 堆排序(B） 冒泡排序(C) 希尔排序（D) 快速排序5设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D）。（A) 空或只有一个结点（B) 高度等于其结点数(C) 任一结点无左孩子(D) 任一结点无右孩子6一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ D）。(A） 堆排序（B) 冒泡排序(C) 快速排序（D) 希尔排序7设某棵三叉树中有40个结点，则该三叉树的最小高度为（ B）。（A） 3（B) 4(C) 5(D） 6
