2022年河北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2022年河北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 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、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 6、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（　　）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 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、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。 13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。 14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 15、建立索引文件的目的是______。 16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。 17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 18、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。 三、判断题 19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　） 20、倒排文件是对次关键字建立索引。（　　） 21、串是一种数据对象和操作都特殊的线性表。（　　） 22、稀疏矩阵压缩存储后，必会失去随机存取功能。（　　） 23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（　　） 24、对于有n个结点的二叉树，其高度为log2n。（　　）