2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试.pdf
上传人:文库****品店 上传时间:2024-09-15 格式:PDF 页数:13 大小:2.5MB 金币:10 举报 版权申诉
预览加载中,请您耐心等待几秒...

2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试.pdf

2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试.pdf

预览

免费试读已结束,剩余 3 页请下载文档后查看

10 金币

下载此文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

2022年兰州交通大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)一、选择题1、用有向无环图描述表达式(A+B)*((A+B)//A),至少需要顶点的数目为()。A.5B.6C.8D.92、用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中结点,使j沿链移动的操作为()。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、链表不具有的特点是()。A.插入、删除不需要移动元素可随机B.访问任一元素C.不必事先估计存储空间所需空D.间与线性长度成正比4、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时()。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab',其next数组值为()。A.0123B.1123C.1231D.12116、若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点()。A.只有eB.有e、b.C有e、c.D无法确定7、循环队列放在一维数组A中,end1指向队头元素,end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳M-1个元素。初始时为空,下列判断队空和队满的条件中,正确的是()。A.队空:end1==end2;队满:end1==(end2+1)modMB.队空:end1==end2;队满:end2==(end1+1)mod(M-1)C.队空:end2==(end1+1)modM;队满:end1==(end2+1)modMD.队空:end1==(end2+1)modM;队满:end2==(end1+1)mod(M-1)8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有()个叶子。A.lognB.(n-1)/2C.logn+1D.(n+1)/2229、一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足()。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对{05,46,13,55,94,17,42}进行基数排序,一趟排序的结果是:A.05,46,13,55,94,17,42B.05,13,17,42,46,55.94C.42,13,94,05,55,46,17D.05,13,46,55,17,42,94二、填空题11、设用希尔排序对数组{98,36,-9,0,47,23,1,8,10,7}进行排序,给出的步长(也称增量序列)依次是4,2,1则排序需______趟,写出第一趟结束后,数组中数据的排列次序______。12、分别采用堆排序,快速排序,起泡排序和归并排序,对初态为有序的表,则最省时间的是______算法,最费时间的是______算法。13、数据结构是研讨数据的______和______以及它们之间的相互关系,并对与这种结构定义相应的______,设计出相应的______。14、文件可按其记录的类型不同而分成两类,即______和______文件。15、索引顺序文件既可以顺序存取,也可以______存取。16、下列程序是快速排序的非递归算法,请填写适当的语句,完成该功能。17、模式串P=‘abaabcac’的next函数值序列为______。18、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中,则非零元素A9.9在B中的存储位置k=______。(注:矩阵元素下标从1开始)三、判断题19、对处理大量数据的外存介质而言,索引顺序存取方法是一种方便的文件组织方法。()20、直接访问文件也能顺序访问,只是一般效率不高。()21、设模式串的长度为m,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省。()22、串是一种数据对象和操作都特殊的线性表。()23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。()24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。()25、数据元素是数据的最小单位。()26、为提高排序速度,进行外排序时,必须选用最快的内排序算法。()27、连通图上各边权值均不相同,则该图的最小生成树是唯一的。()28、B-树中所有结点的平衡因子都为零。()四、简答题29、设目
立即下载