数据结构试卷(八)及答案.pdf
文档从互联网中收集，已重新修正排版，word 格式支持编辑，如有帮助欢迎下载支持。数据结构试卷（八）数据结构试卷（八）一、选择题一、选择题(30(30 分分)1.字符串的长度是指（）。(A)串中不同字符的个数(B)串中不同字母的个数(C)串中所含字符的个数(D)串中不同数字的个数2.建立一个长度为 n 的有序单链表的时间复杂度为（）2(A)O(n)(B)O(1)(C)O(n)(D)O(log2n)3.两个字符串相等的充要条件是（）。(A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等(C)同时具备(A)和(B)两个条件(D)以上答案都不对4.设某散列表的长度为 100，散列函数 H(k)=k%P，则 P 通常情况下最好选择（）。(A)99(B)97(C)91(D)935.在二叉排序树中插入一个关键字值的平均时间复杂度为（）。2(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.设一个顺序有序表 A1:14中有 14 个元素，则采用二分法查找元素 A4的过程中比较元素的顺序为()。(A)A1，A2，A3，A4(B)A1，A14，A7，A4(C)A7，A3，A5，A4(D)A7，A5，A3，A47.设一棵完全二叉树中有 65 个结点，则该完全二叉树的深度为（）。(A)8(B)7(C)6(D)58.设一棵三叉树中有 2 个度数为 1 的结点，2 个度数为 2 的结点，2 个度数为 3 的结点，则该三叉链权中有（）个度数为 0 的结点。(A)5(B)6(C)7(D)89.设无向图 G 中的边的集合 E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点 a 出发进行深度优先遍历可以得到的一种顶点序列为（）。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc10.队列是一种（）的线性表。(A)先进先出(B)先进后出(C)只能插入(D)只能删除二、判断题二、判断题(20(20 分分)1.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）2.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）3.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）4.二维数组和多维数组均不是特殊的线性结构。（）5.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）6.如果某个有向图的邻接表中第i 条单链表为空，则第 i 个顶点的出度为零。（）7.非空的双向循环链表中任何结点的前驱指针均不为空。（）8.不论线性表采用顺序存储结构还是链式存储结构，删除值为 X 的结点的时间复杂度均为O(n)。（）9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）10.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0 元素。（）三、填空题三、填空题(30(30 分分)1word 格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word 格式支持编辑，如有帮助欢迎下载支持。1 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4 为增量的一趟希尔排序结束后的结果为_。2 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。typedef struct nodeint data;struct node*lchild;struct node*rchild;bitree;voidbstinsert(bitree*&t,int k)if(t=0)_;t-data=k;t-lchild=t-rchild=0;else if(t-datak)bstinsert(t-lchild,k);else_;3 设指针变量 p 指向单链表中结点 A，指针变量 s 指向被插入的结点 X，则在结点 A 的后面插入结点 X 需要执行的语句序列：s-next=p-next;_;。4 设指针变量 head 指向双向链表中的头结点，指针变量 p 指向双向链表中的第一个结点，则指针变量 p 和指针变量 head 之间的关系是 p=_和 head=_（设结点中的两个指针域分别为 llink 和 rlink）。5 设某棵二叉树的中序遍历序列为 ABCD，后序遍历序列为 BADC，则其前序遍历序列为_。6 完全二叉树中第 5 层上最少有_个结点，最多有_个结点。7 设有向图中不存在有向边，则其对应的邻接矩阵 A 中的数组元素 Aij的值等于_。8 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4 趟直接选择排序结束后的结果为_。9 设连通图 G 中有 n 个顶点 e 条边，则对应的最小生成树上有_条边。10设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把 16 与_相互交换即可。四、算法设计题四、算法设计题(20(20 分分)1.设计一个在链式存储结构上统计二叉树中结点个数的算法。2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。2word 格式支持编辑，如有帮助欢迎下载支持。文档从互联网中收集，已重新修正排版，word 格式支持编辑，如有帮助欢迎下载支持。数据结构试卷（八）参考答案数据结构试卷（八）参考答案一、选择题一、选择题1C2C3C4B5B6C7B8C9A10A二、判断题二、判断题1对2错3对4错5错6对7对8对9对10对三、填空题三、填空题1.(49，13，27，50，76，38，65，97)2.t=(bitree*)malloc(sizeof(bitree)，bstinsert(t-rchild,k)3.p-next=s4.head-rlink，p-llink5.CABD6.1，167.08.(13，27，38，50，76，49，65，97)9.n-110.50四、算法设计题四、算法设计题1.设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree*bt,int&count)if(bt!=0)count+;countnode(bt-lchild,count);countnode(bt-rchild,count);2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedef struct int vertexm;int edgemm;gadjmatrix;typedef struct node1int info;int adjvertex;struct node1*nextarc;glinklistnode;typedef struct node2int vertexinfo;glinklistnode*firstarc;glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1,glinkheadnode g2)int i,j;glinklistnode*p;for(i=0;i=n-1;i+)g2i.firstarc=0;for(i=0;i=n-1;i+)for(j=0;jadjvertex=j;p-nextarc=gi.firstarc;gi.firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode);p-adjvertex=i;p-nextarc=gj.firstarc;gj.firstarc=p;3word 格式支持编辑，如有帮助欢迎下载支持。
