浙江工业大学851数据结构与软件工程2020年考研初试真题

2022年浙江工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.332、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、以下数据结构中，（）是非线性数据结构。

A.树B.字符串C.队D.栈4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。

8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对{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、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。

考生姓名： 报考专业： 准考证号码：密封线内不要写题2020年全国硕士研究生招生考试初试自命题试题（ B 卷)科目代码： 855 科目名称： 数据结构与数据库技术注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

一、选择题(共 15 小题，每小题 2 分，共 30 分)1、关于算法的时间复杂度，下列说法错误的是（ ）。

A）算法中语句执行的最大次数作为算法的时间复杂度 B）一个算法的执行时间等于其所有语句执行时间的量度C）任一语句的执行时间为该语句执行一次所需的时间与执行次数的乘积 D）一般认为，随问题规模n 的增大，算法执行时间的增长速度较快的算法最优。

2、在一个单链表中，若要删除指针p 指向结点的后继结点，则执行（ ）。

A）p->next = p->next->next; B）p = p->next; p->next->next; C）free（p->next）; D）p = p->next->next； 3、链栈与顺序栈相比，有一个比较明显的优点是（ ）。

A）插入操作更加方便 B）通常不会出现栈满的情况 C）不会出现栈空的情况 D）删除操作更加方便4、设有下三角矩阵用数组A[0..10,0..10]表示，按行优先顺序存放其非零元素，每个非零元素占2个字节，存放的基址为100，则元素A[5,5]的存放地址为（ ）。

A）110 B）120 C）130 D）1405、将森林F 转换为对应的二叉树T，F 中叶子结点个数等于（ ）。

A）T 中叶子结点的个数 B）T 中度为1的结点数C）T 中左孩子指针为空的结点数 D）T 中右孩子指针为空的结点数 6、已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点,则完全二叉树的结点个数最多是( )。

A）39B）52C）110D）1117、若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑15、给定关系模式SL（Sno，Sdept，Mname），其元组的语义是学生Sno在Sdept 系学习，其系主任是Mname，并且一个学生只在一个系，一个系只有一名系主任。