《2017年南京理工大学计算机科学与工程学院877计算机专业基础C之数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年南京理工大学计算机科学与工程学院877计算机专业基础C之数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年南京理工大学计算机科学与工程学院877计算机专业基础C之数据结构考研仿真模拟题一、填空题1 属于不稳定排序的有_。【答案】希尔排序、简单选择排序、快速排序、堆排序等 2 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。 【答案】【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除
2、即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 3 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_; 对于有向图来说等于该顶点的_。【答案】度；出度 4 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。（1）若是边，则的值等于_，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若【答案】（1） 5 中缀式运算结果为_。 【答案】【解析】中
3、缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边 对应的前缀式为_，若则后缀式的（3）算法结束时，相邻矩阵中。6 从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。 7 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_。 【答案】要加“虚结点”。设编号为和的结点在顺序存储中的下标为和。 8 设有个结点的完全二叉树顺序存放在向量【答案】 中，其下标值最大的分支结点为_。 ，则结点和在同一层上的条件是 【解析】用顺序
4、存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，【解析】最大的分支结点是最后一个叶子结点的父结点。 9 已知如下程序段： 语句1执行的时间复杂度为_；语句2执行的时间复杂度为_；语句3执行的时间复杂度为_；语句4执行的时间复杂度为_。【答案】（1）n 1（2）n（3）n （n 3）/2（4）n （n l ）/2【解析】语s 句1执行到不符合条件情况下，执行了n 1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为234. （n l ）加起来就是n （n 3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了
5、123. n 即n （n l ）/2。 10在一棵m阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_。 【答案】【解析】m阶树除根结点和叶子结点外，结点中关键字个数最多是最少11棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _。【答案】2【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。 12深度为H 的完全二叉树至少有_个结点; 至多有_个结点; H 和结点总数N 之间的关系是_。 【答案】 二、选择题13下面关于串的叙述中，不正确的是（ ）。A. 串是字符
6、的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储【答案】B【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。 14已知程序如下： 程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（ ）。A. B. C. D.【答案】A【解析】函数S （intn ）是一个递归函数：当实际参数小于等于零时则返回0, 并终止递归；，并将S （n-1）的结果加上n 作为返回值。程序从当实际参数大于零时则递归调用S （n-1）main （ ）函数开始，首先调用main （ ）函数；在main （ ）函数中调用S （1）；由于函数S （1）的函数时，将main （ ）函数的上下文保存到栈中，并进入函数S （1）；在S 实际参数大于零，需要调用S （0）, 故将S （1）函数的上下文保存到栈中，进入S （0）（0）中，实际参数小于等于零，递归终止。 一、填空题考研试题
