数据结构试题及答案一、选择题（每小题2分，共20分），每个题的备选答案中，只有一个是正确的，请将答案填写在试题的括号中。

1、对顺序存储的线性表，设其长度为20，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（ A ）个元素。

A．10 B．9 C．11 D．122、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表3、当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行（ B ）语句修改top指针。

A．top++ B．top-- C．top = 0 D．top4、设入栈顺序为A，B，C，D，E，则出栈序列不可能是（ C ）。

A．EDCBA B．ABCDE C．ADEBC D．ABDEC5、已知关键字序列（46, 79, 56, 38, 40, 84），采用快速排序（以位于最左位置的关键字为基准）得到的第一次划分结果为：（ A ）A．{ 40, 38, 46, 56, 79, 84 } B．{ 38, 46, 79, 56, 40, 84 }C．{ 38, 46, 56, 79, 40, 84 } D．{ 40, 38, 46, 79, 56, 84 }6、一个有n个顶点和n条边的无向图一定是（ C ）。

A．不连通的 B．连通的 C．有环的 D．无环的7、在一棵具有n个结点的二叉树的第i层上，最多具有（ B ）个结点。

A．2i B．2i-1 C．2i+1 D．2n8、对线性表采用折半查找法，该线性表必须（ B ）。

A．采用顺序存储结构B．采用顺序存储结构，且元素按值有序C．采用链式存储结构 D．采用链式存储结构，且元素按值有序9、在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ C ）。

A．?(n-1)/2? B．?n/2? C．?n/2? D．?n/2? -110、在一个无向图中，所有顶点的度数之和等于所有边数的 ( D ) 倍。

A．3 B．1/2 C．1 D．2二、填空题（每小题2分，共20分），请将正确的结果，填写在试题的横线上。

1、带头结点的循环链表L为空的条件是。

2、序列A={12, 70, 33, 65, 24, 56}给出对应于序列A的大顶堆HA（以线性数组表示）。

3、每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做________排序。

4、设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队空的条件为Q.front = = Q.rear，则队列的长度为。

5、已知数组A[0..11][0..8]按行优先存储，每个元素占有5个存储单元，且A[0][0]的地址为1000（十进制），则A[6][7]的地址为________________。

6、已知广义表A=(a，()，(b，(c)))，则其深度为。

7、在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶子结点数为__ ____个。

8、设森林F中有3棵树，第1、2、3棵树的结点个数分别为n1、n2、n3，当把森林F转换成一棵二叉树后，其根结点的右子树中有________个结点。

9、将含有64个结点的完全二叉树从根结点开始顺序编号，根结点为第1号，其他结点自上向下，同一层自左向右连续编号。

则第30号结点的双亲结点的编号为。

10、有序表(1,2,3,4,5,6,7,8,9)用折半查找方法，查找元素3的比较次数为。

三、判断题（每小题2分，共20分），下列说法正确的在前面括号内画“√”，错误的画“×”。

（）1、线性表的逻辑顺序与存储顺序总是一致的。

（）2、在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

（）4、栈是仅限定在一端进行插入和删除的线性表。

（）5、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的顶点个数无关，只与图的边数有关。

（）6、对于AOE网络，加速任一关键活动就能使整个工程提前完成。

（）7、对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。

（）8、有向网中从一个顶点到另一个顶点的最短路径只有一条。

（）9、对于一棵具有n个结点，其深度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。

（）10、快速排序和堆排序是不稳定的排序方法。

四、应用题（共40分）1、（10分）假定一个待哈希存储的线性表为{32,75,63,48,94,25,36,18}，哈希地址空间为[0…10]，若采用哈希函数H(k)=k MOD 11和线性探测再散列法处理冲突，试给出对应的哈希表（给出求解过程），并求出在等概率情况下查找成功时的平均查找长度。

2、（10分）有8个带权结点，其权值分别为4，26，12，8，7，13，15，15，试以它们为叶结点生成一棵Haffman树（给出过程），然后求出该树的带权路径长度WPL。

3、（10分）已知一棵二叉树，其先序序列为：ABDEGMNCFH，中序序列为：DBMGNEACHF，请画出这棵二叉树（给出过程），并给出其后序序列。

4、（10分）已知关键字序列（37，23，42，55，61，36，28，33），请给出采用快速排序法对序列作升序排序时每一趟的过程。

答案一、选择题（每小题2分，共20分）题号 1 2 3 4 5 6 7 8 9 10答案 A D B C A C B B C D二、填空题（每小题2分，共20分）1、 L->next==L2、{70，65，56，12，24，33}3、归并4、 (Q.rearQ.front+MaxSize)%MaxSize 5、1305 6、3 7、6 8、n2+n3 9、1510、3三、判断题（每小题2分，共20分）题号 1 2 3 4 5 6 7 8 9 10答案× × × √ × × √ × √ √四、应用题（共40分）1、过程4分，哈希表4分，平均查找长度2分，共10分H(32)=32 Mod 11=10 H(75) =75 Mod 11=9 H(63) =63 Mod 11=8H(48) =48 Mod 11=4 H(94) =94 Mod 11=6 H(25) =25 Mod 11=3H(36) =36 Mod 11=3，与25冲突，所以H1=（3+1）Mod 11=4，与48冲突，H2=（3+2）Mod 11=5，所以36的哈希地址是5， H(18) =18 Mod 11=70 1 2 3 4 5 6 7 8 9 1025 48 36 94 18 63 75 32查找成功时，36将比较3次，其它都是比较1次，所以平均查找长度是：ASL=（1+1+1+1+1+1+3+1）/8=10/8=5/4=1.252、WPL值正确3分；过程每步1分；共7分WPL=4*4+7*4+12*3+13*3+8*3+15*3+15*3+26*2=2853、过程8分，后序序列2分，共10分后序序列：DMNGEBHFCA4、快速排序的每一趟的过程：(共10分)初始序列 37 23 42 55 61 36 28 33[33 23 28 36] 37 [61 55 42] （2分） [28 23] 33 [36] 37[61 55 42] （2分）[23] 28 33 36 37 [61 55 42] （2分）23 28 33 36 37 [42 55] 61 （2分）23 28 33 36 37 42 [55] 61 （2分）数据结构综合测试题一、单选题1. 以下数据结构中哪一个是线性结构？( B )A. 有向图B. 栈C. 线索二叉树D. B树2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(B )。

A. HL=p; p->next=HL;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. p->next=HL->next; HL->next=p;3. 在一个带有头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( D )。

A. HL=p; p->next=HL;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. p->next=HL->next; HL->next=p;4. 单链表的每个结点中包括一个指针next，它指向该结点的后继结点。

现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作序列中哪一个是正确的？（C ）A．q=p->next; p->next=q->next; B.p->next=q->next;q=p->nextC. q->next=p->next; p->next=q;D. P->next=q; q->next=p->next;5. 在一个循环顺序存储的队列中，队首指针指向队首元素的（B ）位置。

A．前一个 B. 后一个 C. 当前6. 以下哪一个不是队列的基本运算？（B ）A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值7. 用链接方式存储的队列，在进行删除运算时(D ).A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改8. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变9. 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( A )个不同的字符串？A.5B.4C.6D.110. 下述哪一条是顺序存储方式的优点？（A ）A．存储密度大 B.插入运算方便C. 删除运算方便D.可方便地用于各种逻辑结构的存储表示11. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。

A. O(n)B. O(1)C. O(logn) D. O(n2)212. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为____D____。

A 24B 48C 72D 5313. 下列关于二叉树遍历的叙述中，正确的是( D ) 。

A.若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点C．若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点14. 高度k的二叉树的最大结点数为(A ).A．2k-1 B.2K+1 C.2K-1 D. 2k-115. 下面关于图的存储的叙述中正确的是( C ).A．用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关B．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关C. 用邻接矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关16. 在顺序表(2,5,7,10,14,15,18,23,35,41,52)中,用二分法查找关键码值10,所需的关键码比较次数为 BA.2B.3C.4D.517. 对线性表进行二分法查找，其前提条件是(A ).A.线性表以顺序方式存储，并且按关键码值排好序B.线性表以顺序方式存储，并且按关键码值的检索频率排好序C.线性表以链接方式存储，并且按关键码值排好序D.线性表以链接方式存储，并且按关键码值的检索频率排好序18. 下列哪一个关键码序列不符合堆的定义？(C )A. a、c、d、g、h、m、p、q、r、xB. a、c、m、d、h、p、x、g、o、rC. a、d、p、r、c、q、x、m、h、gD.a、d、c、m、p、g、h、x、r、q19. 对n个记录的文件进行快速排序，所需要的辅助存储空间为 Bn） C. O（n） D.A. O（1）B. O（1og2O（n2）20. 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是 AA.直接插入排序B.直接选择排序C.快速排序D.归并排序21. 设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z22.下列关于数据结构的叙述中，正确的是( A ).A. 数组是同类型值的集合B. 递归算法的程序结构比迭代算法的程序结构更为精炼C. 树是一种线性结构D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点二、填空题1. 数据的逻辑结构被分为_________、________、__________和___________四种。