2022年天津理工大学计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年天津理工大学计算机科学与技术专业《数据结构与算法》科目 期末试卷A （有答案） 一、选择题 1、下述文件中适合于磁带存储的是（ ）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数 是一对一的关系，则选择好的（ ）方法是哈希文件的关键。 A.哈希函数 B.除余法中的质数 C.冲突处理 D.哈希函数和冲突处理 3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则 采用（ ）存储方式最节省运算时间。 A.单链表 仅有头B.指针的单循环链表 双链C.表 仅有尾指D. 针的单循环链表 4、循环队列 A[0..m-1]存放其元素值，用 front和 rear分别表示队头和队尾，则当前队列 中的元素数是（ ）。 A. （rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 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 中，end1 指向队头元素，end2 指向队尾元素的后一个位置。 假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空， 下列判断队空和队满的条件中，正确的是（ ）。 A．队空：end1＝＝end2 ；队满 ：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2 ；队满 ：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满 ：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满 ：end2＝＝（end1＋1） mod（M－1） 7、下列关于无向连通图特性的叙述中，正确的是（ ）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减 1Ⅲ．至少有一个顶点的度为1 A．只有 Ⅰ ．只有B Ⅱ ．CⅠ和 Ⅱ ． ⅠD和Ⅲ 8、有关二叉树下列说法正确的是（ ）。 A.二叉树的度为2 B.一棵二叉树的度可以小于 2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中 有（ ）个叶子。 A.log n （nB.－1）/2 C.logn+1 （D.n＋1）/2 2 2 10、对关键码序列 28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果 为 （ ）。 A. （2，5，12，16）26 （60，32，72） B. （5，16，2，12）28 （60，32，72） C. （2，16，12，5）28 （60，32，72） D. （5，16，2，12）28 （32，60，72） 二、填空题 11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。 12、对 n 个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 13、设有两个算法在同一机器上运行，其执行时闻分别为 100n2和2n，要使前者快于后 者，n 至少为______。 14、如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法， 请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为 （lflag，left，data， right，rflag），其中：lflag=0，left 指向其左孩子，lflag=1，left 指向其前驱 ；rflag=0， right 指向其右孩子，rflag=1，right 指向其后继。 15、索引顺序文件既可以顺序存取，也可以______存取。 16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序