数据结构练习

1、.填空题1.在顺序表中访问任意一个元素的时间复杂度均为O(1)，因此顺序表也称为随机存取的数据结构。2二维数组a43(下标从0开始)，假设a00的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a21地址是64。3.直接插入排序用监视哨的作用是防止数组下标越界。4.已知广义表Ls=(a, (b, c), (d, e),运用head和tail函数取出Ls中的原子d的运算是Head（Head（Tail（Tail（LS）。5对有14个元素的有序表A1.14进行折半查找，当比较到A4时算法结束。被比较元素除A4外，还有A3A5A7。6.在AOV网中，顶点表示活动，边表示活动之间的先后关系

2、。7.有向图G可进行拓扑排序的判别条件是有向无环图。8.若串S1=ABCDEFGHIJK,S2=451223,S3=#,则执行Substring(S1,Strlength(S3),Index(S2,12,1)的结果是DEF。选择题1.在下列存储形式中，哪一个不是树的存储形式？（ D）A双亲表示法B孩子链表表示法C孩子兄弟表示法D顺序存储表示法2.查找n个元素的有序表时，最有效的查找方法是（C）。A顺序查找B分块查找C折半查找D二叉查找3.将所示的s所指结点加到p所指结点之后，其语句应为（D）。As-next=p+1 ; p-next=s;B(*p).next=s; (*s).next=(*p)

3、.next;Cs-next=p-next ; p-next=s-next;Ds-next=p-next ; p-next=s;4.在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（C）。A.顶点v的度B.顶点v的出度C.顶点v的入度D.依附于顶点v的边数5.算法的时间复杂度为O（nlog2n）、空间复杂度为O(1)的排序算法是（A）。A.堆排序B.快速排序C.归并排序D.直接选择1. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij),在一维数组B中下标k的值是（B ）：i(i-1)

4、/2+j-1i(i-1)/2+ji(i+1)/2+j-1i(i+1)/2+j2.由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功的平均查找长度是（C）。A29/11B. 31/11C. 33/11D.35/113.AVL树是一种平衡的二叉排序树，树中任一结点的（B）。A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度4.下列四种排序方法中，不稳定的方法是（D）。A.直接插入排序B.冒泡排序C.归并排序D.堆排序5.设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2,

5、 ,1, 1,则T中的叶子数为（D）。A5B6C7D8判断题1.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ F）2.数组不适合作任何二叉树的存储结构。（F）3.广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（F）4.在含有n个结点的树中，边数只能是n-1条。（T ）5.所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（F）6.简单选择排序在最好情况下的时间复杂度为O(n)。（ F）7.在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ F）8.采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置空，因为这会影响以后的查找。

6、（ T）9.n个数存放在一维数组A1.n中，在进行顺序查找时，这n个数的排列有序或无序，其平均查找长度不同。（F ）10.广义表中原子个数即为广义表的长度。(F)将下列由三棵树组成的森林转换为二叉树。给定下列图，完成以下问题（1）画出该图的邻接矩阵和邻接表（2）根据所画的邻接表，从顶点B出发，画出图的深度优先搜索树（3）根据普里姆（Prim）算法，求它的最小生成树（不必写出全部过程，在生成树中标出边生成的次序即可）(1)邻接矩阵：邻接表：(2)深度优先搜索树为：(3)最小生成树：输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题：（1）构造一棵二叉

7、排序树，计算查找成功的平均查找长度；（2）依此二叉排序树，如何得到一个从大到小的有序序列；（3）画出在此二叉排序树中，删除“66”后的树结构。(1)二叉排序树如下：平均查找长度ASL=(1+2X2+4X3+3X4)/10=2.9(2) 按照右子树根节点左子树的顺序遍历该二叉树，即可得到从大到小的顺序(3)将序列25, 34, 12, 7, 15, 47, 65, 79，47+，16中的关键字按升序重新排列，请写出（1）冒泡排序一趟扫描的结果（2）以第一个元素为分界点的快速排序一趟扫描的结果（3）堆排序所建的初始堆和第一趟排序结果。（1）25、12、7、15、34、47、65、47+、16、79

8、（2）16、15、12、7、25、47、65、79、47+、34（3）初始堆：79、47+、65、34、16、47、12、7、25、15第一趟排序后：65、47+、47、34、16、15、12、7、25、79（最好划出二叉树表示）程序填空题下列算法是建立单链表的算法，请填写适当的语句，完成该功能。typedef struct LnodeElemTypedata;struct Lnode*next;LNode, *LinkList;Status CreatList_L(LinkList &L, int n)/正序输入n个元素的值,建立带表头结点的单链线性表LL=(LinkList) malloc

9、(sizeof(LNode);if(!L) return ERROR;L-next=NULL;p=( 1 );for(i=0;idata);(2);(3);p-next=NULL;return OK;/CreatList_L1.L2.p-next = s3.p = s用链表实现的简单选择排序。设链表头指针为L,链表无头结点，请填写适当的语句，完成该功能。void SelectSort(LinkList L)p=L;while(p)q=p; r=q-next;while( r )if(1)q=r;r=(2);tmp=q-data; q-data=p-data; p-data=tmp;p=(3);

10、1.q-data r-data2.r-next3.p-next1.栈和队列的共同特点是(A)。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时(D).A.仅修改头指针B.头、尾指针都要修改 C.仅修改尾指针D. 头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？(D)A.队列B.栈C.线性表D.二叉树4.设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示（C）。A688B678C692D6965.树最适合用来表示(C)。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据1.二叉树的第k层的结点数最多为(D).A2k-1B.2K+1C.2K-1 D. 2k-12.若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，现进行二分查找，则查找A3的比较序列的下标依次为(D)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，33.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（C）A. O（1）B. O（n）C. O（1og2n）D. O（n2）4.对于线性表（7，34，55，25，64，46，20，1