数据结构-试题和答案.docx

数据结构试题和答案 A卷 一、填空题 （共 8 小题，每空 1 分，共计 20 分） 1． 栈和队列都是_线性_结构；对于栈只能在_栈顶_插入和删除元素；对于队列只能在_队尾_插入元素和在_队头_删除元素。 2．一个广义表中的元素分为 单 元素和 表 元素两类。 3．对于一个长度为n的顺序存储的线形表，在表头插入元素的时间复杂度为__ O(n)_______，在表尾插入元素的时间复杂度为____ O(1)_______。 5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于 n+1 。 6．若一个图的顶点集为{a,b,c,d,e,f},边集为{（a,b）,(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。 7．在进行直接插入排序时，其数据比较次数与数据的初始排列__有___关；而在进行直接选择排序时，其数据比较次数与数据的初始排列__无___关。 8．若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为（15，02，21，24，26，57，43，66，80，48，73）。 9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为__2___。? 10.在线形表的散列存储中，处理冲突有 开放定址法 和 链地址法 两种方法。 11. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有______12______ 个叶子的结点。 12. 设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二叉树中叶子结点是_ E,F,H ___。 13．若由3，6，8，12，10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 4 ,带权路径长度为 87 。 二、选择题 （共 15小题，每题 1 分，共计 15 分） 1．算法指的是（?D? ） ?? A．计算机程序?????? B．解决问题的计算方法 C．排序算法???????? D．解决问题的有限运算序列 2．如下陈述中正确的是（A???） ?? A．串是一种特殊的线性表????????B．串的长度必须大于零 C．串中元素只能是字母??????????D．空串就是空白串 3．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　B　　） A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1 4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B ) A． s-next=p；p-next=s B． s-next=p-next；p-next=s C． s-next=p-next；p=s D． p-next=s；s-next=p 5．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（　A　　） A．队列 B．栈 C．线性表 D．有序表 6．图的邻接矩阵表示法适用于表示（　C　　） A．无向图 B．有向图 C．稠密图 D．稀疏图 7．深度为5的二叉树其结点数最多为 C 。 A、16； B、30； C、31； D、32。 8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ） A． s=rear； rear=rear-next； delete s； B． rear=rear-next； delete rear； C． rear=rear-next-next； delete rear； D．s=rear-next-next； rear-next-next=s-next； delete s； 9．线性表采用链式存储时，结点的存储地址（?B? ） ?? A．必须是不连续的 B．连续与否均可 ?? C．必须是连续的 D．和头结点的存储地址相连续 10．线性链表不具有的特点是（A ）。 A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 11. 含n个顶点和e条边的无向图