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

2023年江苏经贸职业技术学院计算机应用技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 2、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（　　）。 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、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（　　）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 6、已知字符串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 7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。 A．只有e B．有e、b C．有e、c D．无法确定 8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（　　）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 9、在下述结论中，正确的有（　　）。 ①只有一个结点的二叉树的度为0。 ②二叉树的度为2。 ③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.⑦③④ C.②④ D.①④ 10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是： A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94 二、填空题 11、无用单元是指______，例______ 12、在哈希函数H（key）=key%p中，p值最好取______。 13、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 14、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有 ______检索和______检索。 15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。 16、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。 17、模式串P=‘abaabcac’的next函数值序列为______。 18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。 三、判断题 19、倒排文件是对次关键字建立索引。（　　） 20、文件系统采用索引结构是为了节省存储空间。（　　） 21、串是一种数据对象和操作都特殊的线性表。（　　） 22、在链队列中，即使不设置尾指针也能进行入队操作。（　　） 23、对于有n个结点的二叉树，其高度为log2n。（　　） 24、二叉树是一般树的特殊情形。（　　） 25、算法的优劣与算法描述语言无关，但与所用计算机有关。（　　） 26、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（　　） 27、B-树中所有结点的平衡因子都为零。（　　） 28、无环有向图才能进行拓扑排序。（　　） 四、简答题 29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排