2023年烟台工程职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2023年烟台工程职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（　　）。 A.j=r[j].next B.j=j+l C.j=j-next D.j=r[j]-next 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（　　）存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表 4、已知串S=aaab，其next数组值为（　　）。 A.0123 B.1123 C.1231 D.1211 5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（　　）。 A.h-next=s B.s-next=h C.s-next=h;h-next=s D.s-next=h-next;h-next=s 6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 7、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 9、一个具有1025个结点的二叉树的高h为（　　）。 A.11 B.10 C.11至1025之间 D.10至1024之间 10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（　　）。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、在有n个顶点的有向图中，每个顶点的度最大可达______。 12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。 13、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有 ______检索和______检索。 14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。 16、模式串P=‘abaabcac’的next函数值序列为______。 17、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。 18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为 l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH， PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。 三、判断题 19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（　　） 20、文件系统采用索引结构是为了节省存储空间。（　　） 21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（　　） 22、数组不适合作为任何二叉树的存储结构。（　　） 23、对于有n个结点的二叉树，其高度为log2n。（　　） 24、树形结构中元素之间存在一对多的关系。（　　） 25、归并排序辅助存储为O（1）。（　　） 26、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（　　） 27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路