910数据结构（2019年真题）

算法设计题

问题1

有一种排序算法叫做计数排序。这种排序算法对一个待排序的表（采用顺序存储）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个元素，扫描待排序的表一趟，统计表中有多少个元素的关键字比该元素的关键字小。假设对某一个元素，统计出数值为count，那么这个元素在新的有序表中的合适的存放位置即为count。
(1)设计实现计数排序的算法。
(2)对于有n个元素的表，比较次数是多少？
(3)与简单选择排序相比，哪种方法更好？为什么？

void countSort(int A[], int B[], int n){int i,j,k,count;for(i=0; i<n; i++){count = 0;k = A[i];for(j=0; j<n; j++){if(A[j] < k){count++;}}B[count] = k;}
}

（2）对于有n个元素的表，每个元素都要与n个元素（含自身）进行比较，关键字的比较总次数是n^2。

（3）简单选择排序比这种计数排序好，因为对有n个元素的数据表进行简单排序只需进行1+2+...+(n-1)=n(n-1)/2，且可在原地进行排序。

问题2

设二叉树T采用二叉链表存储，设计一个算法，求指定结点p的父结点。要求：
(1)描述算法的基本设计思想。
(2)根据设计思想，给出C语言描述算法，关键之处请给出简要注释。

（1）算法思想：如果树为空或者p是T的孩子结点，返回T;如果T的左孩子为p的父结点，返回对左孩子进行递归调用的结果，无需找右孩子；如果T的右孩子为p的父结点，返回对右孩子进行递归调用的结果；如果左右孩子都不包含p，返回null。

BTNode *getParent(BTNode *T, BTNode *p){if(T==null || T->lchild==p || T->rchild==p){return T;}BTNode *lchild = getParent(T->lchild, p);if(lchild != null){return lchild;}BTNode *rchild = getParent(T->rchild, p);if(rchild != null){return rchild;}return lchild;
}

选择题错题整理

1.顺序存储表示中，数据元素之间的逻辑关系是由（）表示的。
A.指针 B.逻辑顺序 C.存储位置 D.问题上下文
正确答案：
C.存储位置
试题分析：
顺序存储中数据的逻辑关系是由存储位置表示的，链式存储中数据的逻辑关系是由指针表示的。

2.计算算法的时间复杂度属于（）。
A.事前统计的方法
B.事前分析估算的方法
C.事后统计的方法
D.事后分析估算的方法
正确答案：
B.事前分析估算的方法
试题分析：

3.对于链式队列，在这些插入操作时（）。
A.仅修改头指针
B.仅修改尾指针
C.头、尾指针都要修改
D.头、尾指针可能都要修改
正确答案：
D.头、尾指针可能都要修改
试题分析：
对于链式队列，一般插入新元素时仅修改队尾指针即可，但有一种特殊情况，即向空队列插入新元素时，需要同时修改队头指针和队尾指针。所以选D。

4.一个广义表(x,(a,b,c))的表尾是（）。
A.x B.(a,b,c) C.(a,b,©) D.((a,b,c))
正确答案：
D.((a,b,c))
试题分析：
广义表的表尾指的是除表头之外的其他元素组成的表。
注：表尾不是最后一个元素，而是一个子表。